工作来源
ACM Computing Surveys 2022
工作背景
二进制代码相似判断有着广泛的用途，如 Bug 搜索、恶意软件聚类、恶意软件检测、恶意软件谱系跟踪、补丁生成、跨程序版本移植信息和软件剽窃检测等应用场景。其常见的八种应用如下所示：
但判断二进制代码相似性是很有挑战的，不仅是函数名、变量名和数据结构等在编译过程中丢失了大量的程序语义。当使用不同的编译器、更改编译器优化选项以及选择不同的目标操作系统和 CPU 架构时，生成的二进制代码都可能会发生显著变化。
编译过程
标准的编译过程将程序源代码作为输入，选定编译器、优化级别和体系架构等进行编译，生成目标文件再链接成二进制程序。如下所示：
可以在编译过程中增强对抗，比如应用混淆。混淆的方法多种多样，大类可分为源代码转换和二进制转换两类。
加壳就是典型的二进制转换方式，且很多恶意软件已经开始使用自定义壳。
通过相同的源代码生成语义等效的不同二进制程序的方式很多，修改编译器的优化级别或者更换编译器都可以达到目的。与此同时，为不同架构编译的程序由于使用不同的指令集，生成的二进制代码可能完全不同。
历史发展
二进制代码相似源于比较程序不同版本间的差异。由于重新编译时会产生大量非源码更改导致的程序改变，例如重新编译时可能会改变的寄存器分配。
二进制代码相似判断工作首次出现在 1999 年。名为 EXEDIFF 的工具为 DEC Alpha 生成补丁，比较指令序列。名为 BMAT 的工具为 DLL 文件对其配置信息，比较基本块与函数。
接下来的十年中，相继出现了 7 种二进制代码相似判断工作，这些工作从语法相似提升到语义相似、扩大应用范围到恶意软件等。
2004 年，Thomas Dullien 首次提出构造函数调用图基于图进行二进制代码相似判断，以应对编译器优化中的函数指令重排。后续的工作基于此又引入了基本块的匹配，使用 Some Primes Product 哈希来识别相似的基本块。这两项研究也是 IDA 的 BINDIFF 插件的基础。
2005 年，Kruegel 将相似功能的指令分为 14 类，据此为过程间控制流图（Inter-procedural Control-flow Graph，ICFG）进行着色，以此对抗部分混淆手段（垃圾指令、指令重排、指令替换等），利用该方法检测恶意软件多态变种。
2008 年，Gao 设计的 BINHUNT 工具使用符号执行和约束求解器检查基本块的功能是否相似。
2009 年，Xin 设计的 SMIT 工具检索恶意软件的调用图并使用图编辑距离查找相似的恶意软件。
在最近的十年间，出现了52种二进制代码相似判断的工作。2015 年，Pewny 提出的 MULTI-MH 是第一个跨架构的二进制代码搜索工具。
2016 年，Lageman 设计了一个神经网络来判断两个函数是否是从相同的源代码编译的。
工作设计
二进制代码相似判断方案的三个主要区别在于：（1）比较的类型（相同、相似、等效）、（2）比较的粒度（指令、基本块、函数）、（3）比较的数量（一对一、一对多、多对多）。
比较的类型
检查相同很容易，但检查相似很难。使用相同的编译参数（相同的编译器版本、相同的优化级别、相同的目标平台）两次编译相同的程序源代码都可能会产生两个具有不同文件哈希的可执行文件。因为两次编译的文件中包含不同的元数据，例如编译时间戳等。例如，mov %eax,$0 和 xor %eax,%eax 在语义上是等效的 x86 指令，都是将寄存器 EAX 的值设置为零。
证明两个任意程序在功能上等价是一个不可能问题，类似停机问题。
相似可以从语法、结构和语义上进行判断：
语法相似比较代码。语法相似的计算成本最低，但鲁棒性差，无法应对寄存器重新分配、指令序列重排、等效指令替换等情况。
结构相似比较图（如控制流图、函数调用图等）。结构相似能够应对语法转换，但无法应对代码结构的转换（内联函数或删除未使用的函数参数）。
语义相似比较功能（系统调用/API）。语义相似的鲁棒性最好，但计算代价也最大。
比较的粒度
常见的粒度是基本块、函数和整个程序。具体来说，还区分为输入片段的粒度和比较方法的粒度。
如上所示，细粒度的相似不能用于推断粗粒度的等效或相同，但反之可以。例如函数的所有基本块都相似，并不能说明函数的功能是相同或等效的。
比较的数量
比较方法中可分为:
一对一（OO），一对一方法大多是为了发现修改的内容。
一对多（OM），一对多方法大多是为了检索与目标相似的片段。
多对多（MM），多对多方法大多是用于聚类任务。
工作准备
首先排除掉需要源代码的工作、需要操作字节码的工作、需要调用系统 API 的工作、需要将二进制代码视为没有结构的字节序列的工作。
阅读过去 20 年的 14 个会议（IEEE S&P、ACM CCS、USENIX Security、NDSS、ACSAC、RAID、ESORICS、ASIACCS、DIMVA、ICSE 、FSE、ISSTA、ASE 和 MSR）的一百多篇论文，整理了以下 61 个工作。
在 61 个工作中，36 个至少对一个程序进行了定量评估。
技术平台
下表显示了各个工作使用的静态分析和动态分析工具、实现的编程语言、支持的目标程序架构和操作系统等信息：
最受欢迎的静态分析工具是 IDA，各个工作主要用它来进行反汇编和构建控制流图。最受欢迎的动态分析工具是 PIN，其次是 TEMU 和 ANUBIS。还有其他一些优秀的分析工具，如下所示：
最受欢迎的编程语言是 Python，多达 20 个工作都采用了它，其次是有 14 个工作都采用的 C++。这种趋势也与 IDA 被广泛采用有关，IDA 支持 C++ 和 Python 两个接口。
在二进制代码分析中使用 IR 的优点在于重用建立在 IR 之上的分析模块更容易。比如支持一个新的架构只需要增加一个新的前端就可以翻译成 IR，但是分析代码是可以复用的。有 15 个工作使用 IR，并且大多数工作都使用底层平台提供的 IR。在 15 个使用 IR 的工作中，5 个工作使用 BITBLAZE 提供的 VINE，另外 5 个工作使用 VALGRIND 提供的 VEX，另外 2 个工作使用 LLVM-IR。其余 3 个工作使用的是 SAGE III、METASM 和 REIL。而令人惊讶的是，16 个跨架构匹配的工作中只有 6 个工作使用了 IR，其余工作都是为每个架构实现了单独的分析模块，这些模块通常输出通用格式的特征向量。
支持架构最多的是 x86/x86-64（59 个工作），其次是 ARM（16 个工作）和 MIPS（10 个工作）。
在这 42 个使用 IDA 的工作中，大多数只分析了 x86/x86-64，尽管 IDA 实际上支持很多其他架构。
支持操作系统最多的是 Linux（41 个工作），其次是 Windows（35 个工作），只有 4 个工作支持 MacOS。
其中只有 12 个工作是开源的（BINSLAYER、TRACY、QSM2015、ESH、GENIUS、KAM1N0、GEMINI、ASM2VEC、VULSEEKER、RLZ2019、INNEREYE、SAFE），其中 4 个工作（ESH、GENIUS、RLZ2019、INNEREYE）发布了源码和机器学习模型。
数据方法
各工作的实验评估如下所示：
数据集
大多数工作都使用自定义数据集，有 18 个工作都采用的通用数据集是 Corutils。
使用的两个公开固件是 ReadyNAS 和 DD-WRT。
超过一半的工作评估的样本数量都小于 100 个，7 个工作小于 1000 个，8 个工作小于 1 万个，只有 8 个工作评估了超过 1 万个样本。
在 61 个工作中有 37 个工作只评估了良性程序，8 个工作只评估了恶意软件，16 个工作对二者都进行了评估。特别的，在评估恶意软件的 24 个工作中，只有 5 个（SMIT、BEAGLE、MUTANTXS、CXZ2014、BINSIM）工作额外处理了加壳的样本。
对于处理函数的这些工作来说，最大的数据集来自GENIUS，它评估了从 8126 个固件中提取的 4.2 亿个函数，其余工作均不超过五千万。
评估方法
对方法的评估集中在鲁棒性、准确性、可比性和性能上：
鲁棒性：通过不同编译器、不同编译选项等方式来评估是否具备鲁棒性。早期工作一般都没有评估鲁棒性，但后期工作都很重视。
准确性：大多数工作都使用基本事实对准确性进行定量评估，也有一小部分工作通过案例研究进行准确性评估。
可比性：比较很难，因为大多数工作的程序都不是公开可用的，数据集也是自定义的。但最近的工作越来越倾向于对外开放代码和数据集。评价指标其实也难以进行衡量和比较。
性能：测量运行时性能很常见，有 49 个工作都完成了。
工作评估
比较类型
输入比较
有 21 个工作是一对一、有 30 个工作是一对多、有 10 个是多对多。
可以通过一对一的方法扩展到一对多和多对多，但如果只是简单应用在大量样本上会遇到效率问题。提高匹配效率的一般做法就是从每个输入中提取特征向量，使用特征向量间的相似度来代表样本间的相似度。在特征向量的特征子集上添加索引，也可以减少比对次数。
比较方法
相似性比较有 42 个工作、等价性比较有 5 个工作、相同性比较有 2 个工作。
粒度
所有工作共有八个粒度：指令、指令集合、基本块、基本块集合、函数、函数集合、Trace、整个程序。
最常见的输入粒度是函数（26 个工作），其次是整个程序（25 个工作）。
最常见的比较粒度是函数（30 个工作），其次是基本块（20 个工作）。
语法相似
通过比较指令序列来判断相似性。序列中的指令在虚拟地址空间中是连续的，并且属于同一个函数。序列中的指令可以首先被规范化，例如仅保留操作码或将操作数规范化等。
指令序列可以是固定或可变长度的。固定大小的序列是通过在指令流上滑动窗口获得的，例如 n-gram、nperms 等。比较指令序列的方法主要是计算哈希、Embedding 和 Alignment：
6 个工作（BMAT、DR2005、SWPQS2006、SMIT、BINCLONE、SPAIN）使用哈希从可变长度指令序列中计算固定长度哈希。
5 个工作（IDEA、MBC、MUANTX-S、EXPOS´E、KAM1N0）通过 n-gram 序列生成 Embedding。
3 个工作（EXEDIFF、TRACY、BINSEQUENCE）使用 Alignment 通过在任一序列中插入 gap 来对齐两个序列以生成它们之间的映射，解释插入、删除和修改的指令。
结构相似
常见方式是通过图结构判断结构相似性，最常见的图是控制流图（CFG）、过程间控制流图（ICFG）和函数调用图（CG）。在 CFG 和 ICFG 中，节点是基本块，边表示控制流跳转。在 CG 中，节点是函数，边表示调用关系。判断图相似的子图同构是一个 NP 完全问题，其他方法如最大公共子图同构也是一个 NP 完全问题，比较时需要减少比对的图的数量和大小才能提高效率。
有 27 个工作采用了结构相似性判断。其中，14 个工作只使用了 CFG、4 个工作只使用了 ICFG、2 个工作只使用了 CG。
语义相似
一共有 26 个计算语义相似度的工作，大部分在基本块的粒度上捕获语义，捕获语义的三种基本方法是：指令分类、输入输出对、符号公式。
特征相似
有 28 个工作将二进制代码表示为一个向量或者一组特征，确保相似的二进制代码具有相似的特征向量，特征可以是布尔型、数值型或类别型。衡量特征相似通常使用 Jaccard 系数、位向量的点积以及数字向量的欧几里得或余弦距离。
最近 Embedding 很火热，有助于降低特征维度并增加特征向量的密度。下图是两种特征提取方式：
特别的，近五年来机器学习在该领域也得到了广泛应用，可用于无监督相似聚类/分类等任务。
哈希
主要有三类哈希可用：密码学哈希、局部敏感哈希和可执行文件哈希。共有 11 个工作使用了局部敏感哈希，其中 7 个都使用了 MinHash（BINHASH、MULTIMH、GENIUS、BINSEQUENCE、BINSHAPE、CACOMPARE、BINSIGN）。其他局部敏感哈希如 ssdeep、tlsh 等，所有的工作都没有使用，有研究表明这些局部敏感哈希作用于整个程序的相似性效果会比部分内容的相似性更好，这可能和工作的预期目标不太相符。
架构
不同体系结构的代码语法可能有很大不同，因为它们可能使用具有不同指令助记符、寄存器组和默认调用约定的单独指令集。所有 16 个跨架构比较的工作都是在 2015 年以后提出的，主要有两条技术路线：7 个工作选择将二进制代码提升为与体系结构无关的中间表示（IR），另外 9 个工作为每个架构设计独立的模块提取特征再判断相似性。
分析类型
可以使用静态分析、动态分析或两者结合的方式进行分析。有 51 个工作只使用静态分析，有 4 个工作只使用动态分析，有 6 个工作将二者结合使用。此外，也有工作使用污点分析与符号执行。
二进制代码相似中的动态分析普遍用于恶意软件脱壳（SMIT、BEAGLE、MUANTX-S、CXZ2014、BINSIM）、Trace 粒度跟踪（BINSIM、KS2017）以及收集语义相似性的运行时值（BLEX、 BINSIM、IMF-SIM）。
规范化
在 33 个工作中使用了指令规范化，共有三种：操作数移除（9 个工作）、操作数规范化（17 个工作）、助记符归一化（3 个工作）。
另一种规范化是删除不影响语义的、编译器添加的用于加载程序的函数、无法访问的僵尸代码等部分代码。
工作思考
作者提出了以下几点的思考，觉得可能是未来发展方向的突破点：
小块二进制代码。许多工作都忽略相对较小的二进制代码，因为这些小块二进制代码会影响相似性的判断，进一步结合上下文有可能对解决该问题有帮助。
源码到二进制的相似性。可以用该方法确认某些二进制程序中是否存在开源代码中的已知漏洞。
数据相似性。其实，程序同时包含代码和数据，数据可能存储在复杂的数据结构中。也许可以结合类型推断来判断数据结构的相似性。
语义关系。语义相似性的另一个路径是识别具有相关函数的二进制代码，例如加密或网络通信函数。这是更有挑战性的，因为功能相关的代码可能没有相同的语义。
可扩展性。程序、样本、固件数量越来越多，二进制代码相似性判断的方案需要能够具备极好的可扩展性，才能较好地应对数据爆炸。
混淆。混淆代码的二进制代码相似性仍然存在许多挑战。例如 Themida 和 VMProtect 等基于虚拟化的加壳程序，就很难以处理。
方法比较。构建基准数据集和相同实验条件下的独立验证是非常重要的。