如何比较两个 C 函数的相似度

约 965 字大约 3 分钟

2025-11-02

1. 二进制层面比较

这是最直接但最不健壮的方法，通常只作为初步筛选

字符串哈希 (MD5/SHA-256)：这是最简单的方法。将函数编译后的机器码提取出来，然后计算其哈希值。
- 优点：速度快，可以快速识别完全相同的函数
- 缺点：非常脆弱。任何微小的改动，比如插入一条 NOP 指令、改变局部变量的顺序，都会导致哈希值完全不同。因此，它无法检测代码克隆或相似的代码
模糊哈希 (Fuzzy Hashing)：与传统的哈希算法不同，模糊哈希（如 ssdeep 或 TLSH）能够生成一个代表文件或代码块结构特征的哈希值。两个哈希值之间的距离可以用来衡量它们的相似度
- 优点：能够容忍代码中的小改动，可以发现有细微变化的函数
- 缺点：对于较大的代码重构（如改变控制流），效果不佳

2. 结构层面比较

这种方法比二进制比较更抽象，对编译器的影响和一些代码改动不敏感

控制流图 (Control Flow Graph, CFG) 比较：
- 方法：将每个函数表示为一个控制流图，其中节点是基本块（一系列没有跳转的连续指令），边代表控制流。比较两个函数的相似度就变成了比较它们 CFG 的结构相似度。这通常通过图匹配算法来实现，比如子图同构或图编辑距离（graph edit distance）
- 优点：非常健壮。它对寄存器分配、指令顺序等改动不敏感。如果两个函数的逻辑结构相同，即使它们用不同的编译器编译，CFG 也会非常相似
- 缺点：算法复杂，计算量大，尤其是在面对大型函数时
函数特征向量 (Function Feature Vectors)：
- 方法：为每个函数提取一系列特征，并将其表示为一个向量。这些特征可以包括：
  - 基本块数量
  - 指令数量
  - 算术指令、逻辑指令、跳转指令的比例
  - 循环嵌套深度
  - 函数调用的数量和类型
- 优点：将函数简化为数值向量，可以使用简单的距离度量（如欧几里得距离或余弦相似度）进行快速比较，非常适合大规模数据集
- 缺点：丢失了结构信息。两个结构完全不同的函数可能会有相似的特征向量，反之亦然

3. 语义层面比较

这是最强大但也是最困难的方法，旨在比较函数的行为和功能，而不是其形式

抽象语法树 (Abstract Syntax Tree, AST) 比较：
- 方法：将源代码或反编译代码解析成抽象语法树。比较两个函数的相似度就变成了比较它们 AST 的结构。这通常通过树编辑距离（tree edit distance）算法来实现
- 优点：高度抽象，对变量名、代码格式等变化完全免疫，能够准确反映代码的逻辑结构
- 缺点：依赖于高质量的反编译器，并且 AST 比较算法同样非常耗时
污点分析 (Taint Analysis) 或数据流分析：
- 方法：分析函数的输入如何影响其输出。如果两个函数在给定相同输入时产生相同的输出，并且内部数据流路径相似，它们就是相似的
- 优点：能够发现功能上完全相同的代码，即使它们的实现方式天差地别
- 缺点：非常复杂，很难自动化，且无法处理所有情况

版权所有