代码相似度检测：用AST分析发现“换皮“的提交

代码相似度检测用AST分析发现换皮的提交一、这代码为什么看着像参考答案群里有同事说一个新用户的代码和官方题解几乎一模一样——变量名换成了拼音、数组从nums改成arr、while 循环改成了 for 循环。但如果只看文本差异diff algorithm会给出巨大的不相似度这不是完全不同吗文本级别的对比无法捕捉代码的语义等价。你需要的是 AST抽象语法树级别的分析将代码解析为语法树比较树的结构相似度而非文本字符串的匹配。AST 对比的核心优势在于它忽略变量名、空格、注释等换皮手段直接比较代码的结构本质。两段代码即使变量名完全不同的只要语法树结构一致就会被判定为高度相似。二、AST 标准化让相同的逻辑看起来一样使用 Python 的ast标准库解析代码。第一步不是直接比较而是标准化——消除不改变语义的差异import ast import hashlib import json from typing import List, Set, Dict, Tuple from collections import defaultdict class ASTSimilarity: 基于 AST 的代码相似度检测 核心思想 1. 将代码解析为 AST 2. 标准化 AST变量重命名、常量归一化 3. 生成子树哈希集合 4. 计算 Jaccard 相似度 相似度 |A ∩ B| / |A ∪ B|交集大小 / 并集大小 def __init__(self, threshold: float 0.85): self.threshold threshold self._var_counter 0 def normalize_ast(self, code: str) - ast.AST: 将代码解析并标准化为 AST Python 的 ast 模块提供完整的语法树解析。 ast.dump() 输出 JSON 可读的树结构。 try: tree ast.parse(code) except SyntaxError: return None # 使用 NodeTransformer 做变量重命名 transformer VariableNormalizer() return transformer.visit(tree) def generate_subtree_hashes(self, tree: ast.AST) - Set[str]: 生成子树的哈希集合 对树中的每个节点递归计算其子树的哈希值。 如果两段代码结构相同它们的子树哈希集合会有大量交集。 例如 - 代码 A 的 for 循环子树 → 哈希 ABC - 代码 B 的 for 循环子树 → 哈希 ABC因为标准化后完全相同 而文本比较只会发现在 A 中是 for iB 中是 for j。 hashes set() self._collect_node_hashes(tree, hashes) return hashes def _collect_node_hashes(self, node: ast.AST, hashes: Set[str]): DFS 遍历 AST收集每个节点的子树哈希 if node is None: return # 将当前节点的类型和属性序列化为字符串 node_type type(node).__name__ # 只保留语法结构过滤掉变量名等差异 node_repr self._node_signature(node) node_hash hashlib.md5(node_repr.encode()).hexdigest()[:12] hashes.add(node_hash) # 递归处理子节点 for child in ast.iter_child_nodes(node): self._collect_node_hashes(child, hashes) def _node_signature(self, node: ast.AST) - str: 生成节点的结构签名非语义签名 关键设计签名中包含节点类型和子节点类型 但不包含具体的变量名和常量值。 parts [type(node).__name__] # 统计子节点的类型分布 child_types defaultdict(int) for child in ast.iter_child_nodes(node): child_types[type(child).__name__] 1 # 有序的签名字符串 parts.append(json.dumps(dict(sorted(child_types.items())))) return |.join(parts) staticmethod def jaccard_similarity(set_a: Set[str], set_b: Set[str]) - float: 计算 Jaccard 相似度 Jaccard(A, B) |A ∩ B| / |A ∪ B| 范围 [0, 1] - 0: 完全不同 - 1: 完全相同 - 0.85: 高度相似推荐作为阈值 if not set_a and not set_b: return 1.0 if not set_a or not set_b: return 0.0 intersection len(set_a set_b) union len(set_a | set_b) return intersection / union if union 0 else 0.0 def compare(self, code_a: str, code_b: str) - dict: 比较两段代码的相似度 Returns: { similarity: float, # Jaccard 相似度 [0, 1] is_suspicious: bool, # 是否超过阈值 hash_count_a: int, hash_count_b: int, shared_hashes: int, error: str # 解析错误信息如果有 } tree_a self.normalize_ast(code_a) tree_b self.normalize_ast(code_b) if tree_a is None or tree_b is None: return { similarity: 0.0, is_suspicious: False, error: 代码解析失败 } hashes_a self.generate_subtree_hashes(tree_a) hashes_b self.generate_subtree_hashes(tree_b) sim self.jaccard_similarity(hashes_a, hashes_b) return { similarity: round(sim, 4), is_suspicious: sim self.threshold, hash_count_a: len(hashes_a), hash_count_b: len(hashes_b), shared_hashes: len(hashes_a hashes_b), error: None } class VariableNormalizer(ast.NodeTransformer): AST 节点变换器将变量名标准化为 v0, v1, v2, ... 遍历整棵 AST将所有 Name 节点变量引用 替换为统一的编号名称消除变量命名差异。 这样以下两段代码会被识别为相同 def solve(nums): result 0 for i in range(len(nums)): result nums[i] return result def solve(arr): total 0 for j in range(len(arr)): total arr[j] return total 标准化后都变成 def v0(v1): v2 0 for v3 in range(len(v1)): v2 v1[v3] return v2 def __init__(self): self._var_map: Dict[str, str] {} # 原始变量名 → 标准化名 self._counter 0 # 保留关键字不重命名 self._reserved { range, len, print, int, str, list, dict, set, True, False, None, min, max, sum, abs, sorted, enumerate, zip, map, filter, type, isinstance, append, insert, pop, remove, reverse } def visit_Name(self, node: ast.Name): 替换变量名为标准化编号 注意不改变函数名和保留字段名只改变普通变量。 if node.id in self._reserved: return node if node.id not in self._var_map: self._var_map[node.id] fv{self._counter} self._counter 1 return ast.Name(idself._var_map[node.id], ctxnode.ctx) def visit_FunctionDef(self, node: ast.FunctionDef): 函数定义的标准化重命名函数名但不递归替换内部变量 # 先标准化函数体 self.generic_visit(node) # 函数名也标准化 if node.name not in self._var_map: self._var_map[node.name] fv{self._counter} self._counter 1 node.name self._var_map[node.name] # 用标准化的名字替换 return node def detect_batch_similarity(submissions: List[dict]) - List[dict]: 批量检测多个提交之间的相似度 典型使用场景 - 检查新用户的多次提交之间是否存在相似模式 - 检查某个题目的所有提交中是否有参考答案 - 排行榜反作弊 Args: submissions: 提交列表每条包含 {id: str, code: str} Returns: 可疑提交对列表 detector ASTSimilarity(threshold0.80) suspicious_pairs [] n len(submissions) for i in range(n): for j in range(i 1, n): result detector.compare( submissions[i][code], submissions[j][code] ) if result[is_suspicious]: suspicious_pairs.append({ submission_a: submissions[i][id], submission_b: submissions[j][id], similarity: result[similarity], shared_hashes: result[shared_hashes] }) # 按相似度降序排列 suspicious_pairs.sort(keylambda x: x[similarity], reverseTrue) return suspicious_pairs def demo(): 演示检测两段变量名不同但结构相同的代码 code_original def two_sum(nums, target): seen {} for i, num in enumerate(nums): complement target - num if complement in seen: return [seen[complement], i] seen[num] i return [] code_renamed def find_pair(arr, goal): visited {} for idx, val in enumerate(arr): need goal - val if need in visited: return [visited[need], idx] visited[val] idx return [] detector ASTSimilarity(threshold0.70) result detector.compare(code_original, code_renamed) print( * 50) print(代码相似度检测结果) print( * 50) print(f相似度: {result[similarity]:.2%}) print(f子树哈希A: {result[hash_count_a]}) print(f子树哈希B: {result[hash_count_b]}) print(f共享哈希: {result[shared_hashes]}) print(f判定: {⚠️ 可疑 if result[is_suspicious] else ✅ 正常}) print() print(代码A原始) print(code_original.strip()) print() print(代码B换名) print(code_renamed.strip()) # 对比文本级相似度 from difflib import SequenceMatcher text_sim SequenceMatcher(None, code_original, code_renamed).ratio() print(f\n作为对比文本级相似度: {text_sim:.2%}) print(f文本认为不同但 AST 认为完全相同) if __name__ __main__: demo()上面的代码对比清晰展示了 AST 方法的威力。文本级相似度只有约 40%因为变量名完全不同但 AST 标准化后的相似度接近 95%。三、检测效果的多维评估AST 方法的误报率取决于阈值设置阈值检出率误报率适用场景0.95低极低反作弊需高置信度0.85中低代码审查推荐0.75高中学习分析发现参考模式0.65极高高宽松检测手动复审检测率随代码复杂度变化的趋势代码越复杂更多分支、更多循环嵌套AST 的子树越多误报率越低。简单函数如 3-5 行由于子树少碰巧匹配的概率更高需要更高的阈值。四、边界与局限局限 1语义等价但结构不同两段代码逻辑相同但写法不同如递归 vs 迭代AST 会判定为低相似。这是设计上正确的——代码抄袭检测应该区分照抄和相同思路但不同实现。局限 2语言依赖AST 解析器是语言相关的。Python 的ast只能解析 Python要支持多语言需要集成 Tree-sitter支持 30 语言。局限 3大型文件的性能O(N^2) 的两两比较不适合大规模提交。实际系统需要先用简化的指纹如抽取前 5 个函数的 AST 哈希做快速过滤只对候选对做完整比较。五、总结AST 对比 语义指纹文本 diff 对比代码相似度是盲人摸象——它看到的只是字符串的排列而非代码的结构。AST 标准化 子树哈希提供了一种语义指纹相同逻辑的代码无论怎么换皮都生成相同的指纹。在刷题系统中这个技术不仅用于反作弊还有更积极的应用发现用户卡住了。如果一个用户连续 3 次提交的 AST 高度相似只是微调参数说明他的思路没有任何改变——此时系统可以提示试试另一种思路而非等待更多次无效的提交。