代码相似度检测：用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 i"，B 中是 "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] = f"v{self._counter}" self._counter += 1 return ast.Name(id=self._var_map[node.id], ctx=node.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] = f"v{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(threshold=0.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(key=lambda x: x["similarity"], reverse=True) 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(threshold=0.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 方法的误报率取决于阈值设置：

检测率随代码复杂度变化的趋势：代码越复杂（更多分支、更多循环嵌套），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 高度相似（只是微调参数），说明他的思路没有任何改变——此时系统可以提示"试试另一种思路？"而非等待更多次无效的提交。