Question

基本原理

软件开发商为了修补软件系统的各种漏洞或缺陷所提供的修补程序被称为软件补丁。对于开源软件，补丁本身就是程序源代码，打补丁的过程就是用补丁中的源代码替换原有的代码。而对于闭源软件，厂商只提供修改后的二进制代码，例如微软的Windows系统补丁。这时就需要使用二进制代码比对技术，定位补丁所修补的软件漏洞。

二进制代码比对的根本目的是寻找补丁前后程序的差异。这里所说的差异是指语义上的差异，即程序在执行时所表现出的不同的逻辑行为。通过二进制代码比对定位出有差异的函数，再经过进一步的人工分析，可以确定出二进制补丁对程序执行逻辑上的修改，从而推测漏洞位置及成因，辅助漏洞挖掘工作。

主要的实现原理有如下几种：

• 基于文本的比对：最简单的比对方式，其比对的对象分为两种，即二进制文件和反汇编代码
  • 二进制文件的文本比对：对打补丁前后的两个二进制文件逐字节进行比对，能够全面地检测出程序中微小的变化，缺点是完全不考虑程序的逻辑信息，漏洞定位精度差，误报率高。
  • 反汇编代码的文本比对：将二进制程序先经过反汇编，然后对反汇编代码进行文本比对，比对结果中包含一定的程序逻辑信息，但同样对程序的变得十分敏感，有很大的局限性。
• 基于同构图的比对：依托于图论知识，首先对可执行程序的控制流图进行抽象，将二进制程序转化为一个有向图，即将二进制比对问题转化为图论中的图同构问题。这种方法的优点是不会漏掉非结构化的差异，但其受编译器优化的影响较大。
• 基于结构化的比对：为了克服基于同构图比对的缺陷，该技术主要关注可执行文件逻辑结构上的变化，而不是某一条反汇编指令的变化。
• 综合比对技术：在上述基本比对技术的基础上，进行多种比对技术的综合应用。

方法实现

基于文本的比对

基于二进制文件的文本比对仅适用于查找文件中极少量字节差异。过程如下：

• 将两个二进制文件作为两个输入字符串，每一个二进制字节就相当于字符串中的一个字符
• 通过最长公共子序列算法，在两个文件中从头向后搜索最长公共子序列，进行比对
• 每当找到一个最长公共子序列，意味着找到了一段指令的匹配，并继续向后搜索最长公共子序列
• 比对进行到文件结尾，比对结束

基于反汇编代码的文本比对实际上是一种指令级别的比对方法，研究指令之间的相似性和差异性：

• 相似：即两条指令的语义完全相同。判定规则如下：
  • 两条指令的二进制字节完全相同
  • 指令的 opcode 相同或者两条指令同为无条件跳转或条件跳转指令
  • 同时满足这些条件：opcode完全相同；两条指令的opcode格式的对应域值相等
• 相近：即两条指令具有相同的 opcode 和操作数列表
• 可忽略：如果某条指令为NOP指令，或者是只有唯一后继节点的JMP指令
• 不同：两条指令中的一条被标记为“可忽略”

基于图同构的比对

在构造可执行文件的图的时候，做出如下假设：

• 不同版本的两个目标文件从本质上是不同构的，算法的目标是找到一个最佳匹配映射，而不需要穷尽所有匹配
• 可执行文件提供的基本信息可作为匹配的起点
• 生成的有向图中，大部分顶点只有一个入口和一个出口
• 图中的顶点有可比较的属性，包括操作码、操作数等
• 不对整个图进行同构匹配，而是寻找图中某一部分的同构匹配

基于同构图比对的技术可分为两种：

• 指令级图同构比对算法：两个需要比对的可执行文件分别构造成图，以指令、数据常量、函数调用指令等作为顶点，以控制流图的边作为图的边。对生成的两个图做同构识别，用同构算法找到最相似的两个部分作为同构部分。然后，对两个图的非同构部分继续识别其是否同构，直至全部识别结束
  1. 分析两个二进制文件，获得函数、引用表、字符串等。对于函数，生成函数流程图。图中的节点表示单一的指令，图中的边表示指令间所有可能的执行顺序
  2. 识别比较的开始点，可以是程序入口点，也可以分析导出函数表，匹配相应的导出函数，作为比较的起始点。将这些地址放入一个分析队列中
  3. 处理队列，对于每一个需要比对的地址对，分析该地址处对象的类型，并进行比较。如果类型不同，则失败；否则，比较对象，相同则加入到同构图中，并向队列中加入新的比较地址对
• 函数级图形化比对算法：基于指令级图同构算法，从导出函数和程序入口点开始，根据函数名字的对应关系把相应函数的地址作为比较的入口。从导出函数的入口地址出发，把指令作为图的节点，每一个函数都画出一个完整的图，然后根据算法比对两个图是否同构。比对算法如下：
  1. 以两个函数的入口地址开始，维护一个地址对队列
  2. 如果队列非空，从队列中取出一对地址，比较两个地址处的指令，如果已经同构，跳回2；如果“相似”，归为同构一类并标记为“相似”，然后将两个对应的后继地址添加到队列中，跳回2；如果“可忽略”，将忽略的指令放入忽略节点集合，并将忽略指令的后继指令的地址与另一条指令地址组合成一个地址对，加入队列，跳回2；如果“相近”，归为同构一类并标记为“相近”，然后将两个对应的后继地址加入队列，跳回2
  3. 比对完成，判断两个函数对应的图形是否同构