Adv4：代码查重

什么是查重系统？¶

查重系统用于检测不同用户提交的代码之间的相似度，防止抄袭和作弊。OJ 查重不仅要能检测文本相似，还要能适应变量名变化、代码结构调整等常见抄袭方式。

模块目标¶

引入基于程序依赖图（PDG）的代码相似性检测功能，提升系统识别抄袭代码的能力。
支持对提交代码进行静态分析，构建 PDG，并计算结构相似度。
实现查重报告的生成与查询，供管理员使用。

前置知识要求¶

技术点	推荐学习内容
PDG 理论基础	程序依赖图构造、控制/数据依赖
静态分析	抽象语法树（AST）、控制流图（CFG）
相似度算法	图同构、子图匹配、图嵌入方法

算法原理介绍：基于程序依赖图（PDG, Program Dependency Graph）的代码查重¶

一、背景概述¶

代码克隆指两段源代码在结构或语义上存在较高相似度的现象。传统查重技术主要依赖于文本匹配或抽象语法树对比，但对变量名重命名、控制结构调整等小修改往往不鲁棒。PDG-Based Clone Detection 提供一种更语义敏感的方法，利用程序依赖图刻画代码的控制和数据依赖，从而实现更准确的相似性判断。

二、程序依赖图（PDG）概念¶

一个 程序依赖图 PDG 是一个图结构，其中：

每个节点表示一个语句或表达式（通常从 AST/CFG 中提取）。
边表示程序中的两类依赖：
控制依赖（Control Dependence）：表示一条语句的执行是否取决于某条件（如 if/while）。
数据依赖（Data Dependence）：表示两个语句之间通过变量读写形成的数据传递关系。

形式化表示一个 PDG 为有向图：

\[ PDG = (V, E_c \cup E_d) \]

\(V\)：语句/表达式集合
\(E_c\)：控制依赖边集合
\(E_d\)：数据依赖边集合

三、相似度计算方法¶

要比较两个 PDG \(G_1 = (V_1, E_1)\) 和 \(G_2 = (V_2, E_2)\)，可以使用如下方法：

图编辑距离法（Graph Edit Distance, GED）¶

图编辑距离衡量将 \(G_1\) 转换为 \(G_2\) 所需的最小编辑代价（添加、删除节点或边）：

\[ GED(G_1, G_2) = \min_{\pi \in \Pi} \sum_{(u,v) \in \pi} \text{cost}(u, v) \]

其中 \(\pi\) 是两个图节点之间的映射，cost 是匹配或不匹配的代价函数。

然后用归一化方式得到相似度分数：

\[ sim(G_1, G_2) = 1 - \frac{GED(G_1, G_2)}{\max(|V_1|, |V_2|)} \]

四、实际流程¶

解析代码 -> 构造 AST
AST -> 控制流图（CFG）
CFG -> PDG（添加控制/数据依赖）
PDG 存储/建模
对比新提交与历史提交的 PDG 相似度
生成查重报告

任务分解¶

任务 1：PDG 构建与持久化¶

目标：对每次提交的代码构建 PDG，保存为结构化数据以供后续比较。
要点：
使用已有解析器（如 Python 的 ast 模块或 Clang）生成 AST。
构造 CFG 和 PDG，节点表示语句或表达式，边表示依赖关系。
将 PDG 以图数据库或自定义结构存储（如 JSON 格式）。

任务 2：代码相似性检测¶

目标：在指定题目范围内，对新提交代码与历史代码进行相似度匹配。
要点：
使用图匹配或图嵌入模型计算两个 PDG 的结构相似度。
支持设置相似度阈值（如 >80% 认为是 clone）。
记录每次查重结果，包括匹配对象、相似度、位置映射等。

任务 3：查重结果查询与权限控制¶

目标：实现查重报告查询接口，并进行权限管理。
要点：
普通用户不可查看他人查重报告。
管理员/教师可查询某题下所有用户的查重情况。
查重报告内容包括：对比对象、相似度评分、可视化摘要等。

评分细则¶

功能/接口	分值	评分说明
PDG 构建与存储	5	支持 AST → CFG → PDG 流程，结构持久化
相似度检测与匹配	3	匹配算法正确，有效检测结构相似性
查重报告与权限控制	2	查询接口、权限策略、简明报告展示
小计	10

参考文献¶

作者：Haoran Wang