论文学习_Precise and Accurate Patch Presence Test for Binaries

摘要：打补丁是应对软件漏洞的主要手段，及时将补丁应用到所有受影响的软件上至关重要，然而这一点在实际中常常难以做到，研究背景。因此，准确检测安全补丁是否已被集成进软件发行版本的能力，对于防御者和攻击者而言都极为关键，研究意义。FIBER 正是基于此需求而提出的自动化系统，它的设计灵感来自人类分析者的行为模式——通常只检查代码中局部且有限的区域，核心思想。该系统首先会对开源安全补丁进行深入解析与分析，然后生成高度精细的二进制签名，这些签名能够精准反映补丁引入的关键语法和语义变化，并可用于在目标二进制文件中进行匹配搜索。与以往的方法相比，FIBER 更加策略性地利用源代码层面的信息，专注于补丁的局部改动和最小上下文，而非整个函数或文件的对比。在评估方面，研究者选取了107个真实的安全补丁和来自三个主流厂商的8个Android内核镜像进行系统测试，结果显示FIBER平均检测准确率达到94%，且未出现误报情况。

引言

近年来，新发现的安全漏洞数量迅速上升，给各类软件系统及终端用户带来了严重威胁。虽然打补丁是应对漏洞的主要手段，但要确保安全补丁能够在短时间内被传播到众多受影响的软件发行版中，尤其是在拥有多个并行开发分支（如上游与下游）的庞大项目中，仍面临极大挑战。这一困难主要源于现代软件工程实践中广泛存在的代码重用现象。因此，具备检测某个特定安全补丁是否已被应用于某一软件发行版本的能力，对于防御方和攻击方来说都显得尤为重要。研究背景

为了更清晰地展开论述，有必要将“补丁存在性检测”与更通用的“漏洞搜索”在目标和范围上加以区分。补丁检测顾名思义，是在已知补丁内容及其影响函数的前提下，用于判断某个未知目标中是否已经应用了特定补丁，openssl中的heartbleed漏洞是否已在tls1_process_heartbeat()函数中被修复。相比之下，漏洞搜索则不预设目标函数的信息，而是更广泛地查找与已知漏洞函数相似的所有代码片段或函数，在某个软件发行版本中，哪些函数与存在漏洞的tls1_process_heartbeat()函数相似。当前研究聚焦于更具针对性的补丁存在性检测问题，其核心目标是提供精准、明确的判断结果。在这一前提下，学界对这两个方向分别进行了探索：

Source to sourve：完全在源代码层面进行，在近年来的相关工作中，通常还假设可获取与特定漏洞相关的补丁信息。

Binary to binary：不依赖任何源代码，因此所有比对工作均基于二进制层面的特征进行。这类方法也不要求掌握与补丁相关的任何信息，例如哪些二进制指令与补丁内容有关。

在该研究中，提出了一种介于上述两类方法之间的新范式——source to binary方式，其设立基于以下几点观察。首先，开源已成为当今计算领域的发展趋势，越来越多的软件以开源形式发布，并保留了完整的提交记录和补丁历史（例如托管在 GitHub 上）。事实上，即便是许多仅基于二进制的漏洞搜索研究，也普遍涵盖了如 Linux 和 OpenSSL 这类软件。其次，许多开源代码或组件在闭源软件中被广泛复用，例如用于物联网固件中的各类库或基于 Linux 的内核。这一变化至关重要，使得研究者能够借助源代码层面的信息优势，用以指导对二进制中补丁存在性的检测。原来是他们首先提出source to binary

遗憾的是，现有与之相关的仅基于二进制的漏洞搜索方法在转用于精确的补丁存在性检测时，往往缺失了关键的一环。由于其搜索范围极其广泛，这类方法通常不得不依赖基于相似度的模糊匹配策略，以提高处理速度，但这类策略本质上难以保证准确性。因此，大多数现有方案往往是以整个函数为单位进行比对。然而，现实中安全补丁往往仅涉及细微而局部的改动，这使得基于相似度的方法难以有效区分已打补丁与未打补丁的版本。

补丁或者说是漏洞往往仅涉及细微而局部的改动

为弥补上述缺失环节，该研究提出了FIBER系统，作为现有相似度基础漏洞搜索方法的有力补充，并将其扩展至能够实现精确补丁存在性检测的新阶段。FIBER的核心在于解决一个关键技术问题：如何生成能够准确反映源代码层补丁特征的二进制签名？对此，系统采用了两个主要步骤：首先，借鉴人类分析者的典型行为方式，从补丁中挑选出最具代表性、最适合作为签名的部分；其次，在签名生成过程中尽可能保留源代码层的丰富信息，不仅涵盖补丁本身，也包括其所在函数的整体上下文。根据源码生成二进制补丁（漏洞）代码签名

相关工作

面向源码的漏洞检测：许多工作致力于在同一软件版本内部或不同发行版之间查找代码克隆，其总体目标是定位与已知漏洞代码相似的代码片段——这一通用目标也可被转化为补丁存在性检测任务。由于漏洞搜索通常不限定在单一函数范围内，而是在大型软件中面对可能上百万行代码的搜索空间，因此在可扩展性的考虑下，这类方法通常采用某种形式的相似度匹配机制，基于源代码提取的特征进行比对，这些特征包括字符串、标记序列以及语法解析树等。然而，这种方法在判断匹配代码是否已被打补丁方面存在困难，原因在于补丁前后的代码版本可能非常相似，尤其当安全补丁仅涉及细微改动时更是如此。

面向二进制的漏洞检测：由于缺乏源代码信息（如变量类型和名称），这类方法通常依赖其他替代特征，例如代码的结构特征来进行比对。由于 binary to binary 的漏洞搜索方法无法依赖符号表，它们往往需要检查目标程序中的每一个函数，即使只是为了对某个特定函数进行精确的补丁存在性检测。例如，在给定一个含有漏洞的函数的情况下，像 Genius 和 Gemini 这类工具实际上是要在整个目标二进制文件中检索所有函数，以寻找同样受影响的函数。出于对可扩展性的考虑，这些方法的特征提取和比对策略更侧重于速度而非精度。像 BinDiff 和 BinSlayer 会通过控制流图之间的同构关系来判断相似性；更先进的方法如 Genius 和 Gemini 则从控制流图中提取特征表示，并将其编码为高维数值向量，即图嵌入，从而显著加快匹配过程。然而，面对庞大的搜索空间，那些基于语义、具备更高精度的方案普遍被认为难以扩展。例如，有研究通过比较基本块的输入/输出对来匹配相似的目标代码块，而 BinHunt 和 iBinHunt 则采用符号执行和定理验证器，以形式化手段确认基本块级别的语义等价关系。无论是面向源码还是面向二进制，目前的方法为了实现精度和效率的平衡，无法实现细粒度的补丁（漏洞）检测

FIBER 所处的位置颇具独特性，它能够利用源代码层的信息来回答一个更具体的问题——目标二进制中，某个明确受影响的函数是否已经打了补丁。据了解，迄今只有 Pewny 等人的研究提出可以借助源代码层的补丁信息来生成更细粒度的签名用于漏洞搜索，尽管该工作并未提供具体的实现或评估。然而，其研究重点依然停留在漏洞搜索，而非补丁存在性检测，这意味着其方法依旧是在整个目标二进制中查找相似的（已或未补丁的）代码片段，这种模糊的方式难以直接而准确地回答补丁是否存在的问题。FIBER从源码中提取二进制部分

内容概述

Motivation Example：以CVE-2015-8955这一Linux内核漏洞的安全补丁为例，通过这个案例可以直观展示检测补丁是否存在于目标二进制中的具体步骤。该补丁内容如图1所示。若要判断该补丁是否已应用于某个目标二进制，通常会自然地遵循以下几个步骤展开操作：

• 代码段选择：在补丁检测的流程中，首要步骤是选取一个变更位置，即一段被修改的语句序列。整体来看，该补丁包含多个改动点，但并非所有变更都适合作为判断补丁是否存在的依据。其中，第11行新增的 if 语句不仅引入了控制流结构的变化，还涉及了新增函数参数的使用，具有明显的语义特征。因此，将第11行作为判断补丁是否已应用的标志，更具代表性和可行性。

• 粗粒度匹配：在确定从目标二进制中的函数内查找第11行对应的代码，通常会从匹配控制流图（CFG）结构入手，因为这种方式相对快速且实现简单。类似的操作也可以在源代码层面进行。具体来说，条件语句中的 if 通常会对应一个拥有两个后继节点的基本块（出度为2的基本块），此外由于 if 语句中存在函数返回的操作因此基本块中应有一个后继节点指向函数的结束部分。在图1中展示了一个从已打补丁的Android内核镜像中生成的部分CFG，可以看到，加粗的基本块及其右侧的基本块都符合上述特征。

• 细粒度匹配：在仅有有限二进制信息的条件下，就需要设法将二进制指令映射回源代码中的语句。这一过程对人工分析而言通常十分耗时，因为分析者需要弄清楚某个寄存器或内存位置具体对应源代码中的哪个变量。以图1中的示例为例，分析者需要检查候选基本块中“cmp”指令所使用的寄存器，具体做法是回溯这些寄存器的来源（图1底部列出了相关信息）。通过这种方式，最终可以识别出两个“cmp”指令之间的差异，并准确判断出加粗的基本块正是对应源代码第11行的位置。

系统架构：系统由代码段选择模块、签名生成模块以及补丁匹配模块三部分组成：

• 代码段选择模块通过细致分析每个变更点及其对应的参考函数，从中筛选出最具代表性、唯一性和可匹配性的源代码改动；
• 签名生成模块通过二进制符号执行，在信息丢失的编译背景下实现源代码变更位置向二进制签名的映射，实现源码与二进制之间桥梁的搭建。
• 补丁匹配模块通过符号表定位目标函数后，先以局部控制流图拓扑进行快速语法匹配，再借助符号执行完成语义匹配，从而实现源代码签名在目标二进制中的精确搜索。

系统设计

签名用于表征补丁的核心内容。理想的签名通常需满足两个基本标准：（1）唯一性。签名应仅存在于补丁相关位置，若在补丁前后版本中都能找到该签名，便失去了对补丁的唯一标识性。因此，签名不宜过于简单，以免在与补丁无关的代码中也频繁出现；（2）稳定性。签名应对代码库的正常演进具有一定鲁棒性，例如由于版本差异，目标函数在结构上可能已与参考函数不同，因此签名也不宜过于复杂，避免因涉及过多源代码行而在目标中因细微无关变动产生误判，从而降低匹配准确性。

可以看出，前述两个看似矛盾的要求在签名生成中实际需要精巧的平衡，后续内容将对此展开具体说明。归根结底，关键在于从补丁中选取一个既具有唯一性、又有望在二进制层生成有效签名的源代码变更点。对这一任务有利的是，参考函数与目标函数之间通常在变量层的语义上具有高度一致性。假设两个版本均已打补丁，那么诸如“变量是如何被赋值与解引用的”以及“条件语句是如何构造的”等语义行为应基本一致。二进制签名所要做的，就是尽可能携带这些关键信息，从而还原出源代码中的语义特征。签名需要满足的两大特性

代码段选择模块

代码段发现：补丁可能涉及代码的新增或删除，因此我们既可以依据补丁未被应用（即删除行仍然存在）来判断，也可以依据补丁已被应用（即新增行出现）来识别。为便于讨论，这里以补丁已应用为前提，将签名生成聚焦于新增的代码行；若反向操作，思路也基本一致。整体策略是从一条新增语句出发，视情况逐步扩展。在处理每一条新增语句时，通常会依照以下步骤展开：

• 唯一性测试：某条语句必须仅出现在补丁新增的代码行中，而不能出现在其他位置（例如未打补丁的代码库中）。为实现这一目标，可采用基于词法分析器的简单标记序列匹配方法。需要特别指出的是，这一唯一性检测不仅关注语法层面的标记信息，还隐含了与语义相关的特征。例如，图1中第11行的源代码签名就体现了一个特定的语义关系——第一个函数参数被用于与最后一个参数的某个字段进行比较，这种语义结构本身具有唯一性，也是我们在生成二进制签名时必须保留的关键要素。
• 上下文补充：为解决单条语句无法满足唯一性要求的情况，系统会将该语句在控制流层面上的相邻语句作为潜在的上下文进行考虑。这种“相邻”关系是双向的，例如一个“if”语句通常对应两个后继分支，二者都可视为其上下文，因此可能存在多个可选的上下文语句。具体操作上，会以渐进式的方式逐步扩展上下文范围，例如当一条上下文语句仍不足以实现唯一性时，就尝试引入两条。
• 细粒度检测：旨在识别补丁中同一语句或源代码行内的具体改动。通常，补丁以源代码行的增删形式呈现，即便只对一行中的部分内容进行了修改，也会在补丁中显示为一行被删除、一行被新增。为避免将无关内容纳入签名从而导致签名冗长，系统会通过对比相邻的新增与删除行，精确定位实际改动的部分。举例来说，如果一个函数调用语句中仅修改了某一个参数，那么在匹配过程中，完全可以忽略其他未变的参数，从而降低干扰，提高签名的“稳定性”。
• 类型信息过滤：类型信息在源代码语句中同样扮演着重要角色，因为它直接影响后续二进制签名的生成与匹配过程。从理论上讲，可以为参考二进制中的每个变量（即寄存器或内存位置）标注其对应的类型，并在匹配时确保目标二进制中推断出的类型保持一致。然而，类型匹配有时并不足以唯一确定一个签名。一个典型的特殊情况是常量字符串，其通常以静态形式存储在固定内存地址中。如果某个补丁唯一的改动就是修改了该字符串的内容，那么在进行签名生成与匹配时，就必须解引用对应的 char* 指针，获取实际的字符串内容。否则，生成的签名将只包含一个常量指针地址，而该地址在不同二进制版本中可能有所不同。即便目标中该指针的类型依然是 char*，也无法据此判断其是否属于已打补丁或未打补丁的版本。在后续的案例分析中也会提供这类实际示例。

代码段排序：在前述步骤中，一个补丁可能对应多个具有唯一性的源代码变更候选项，而在实际应用中，只要其中一个变更存在，通常就已足以表明补丁已被应用。此外，不同的源代码变更在生成二进制签名时的适用性也存在差异。FIBER 的做法是先对所有候选变更进行排序，并选取排名靠前的若干项（Top N）用于后续的签名转换。排序依据主要参考三个因素，按重要性由低到高排列：

• 语句与函数入口之间的距离是一个重要考量因素。源代码签名中语句距离函数入口越近，签名生成过程通常就越高效，这与系统内部的具体实现机制有关。
• 函数体积的大小也是一个关键考量因素。如果源代码签名位于一个较小的函数中，匹配引擎将更具优势，因为搜索空间更小，受到无关代码干扰的可能性也更低，同时匹配过程的执行速度也会更快。值得注意的是，相较于前述“语句与函数入口的距离”，这一因素更为重要，因为签名生成只需执行一次，而匹配过程可能会在多个目标二进制上重复进行。
• 变更所涉及的语句类型同样具有重要影响。如果变更涉及结构性或控制流相关的语句（例如“if”语句），那么在匹配时可以快速将搜索范围缩小至结构上相似的候选区域，从而加快匹配速度。更关键的是，这类变更对二进制签名的稳定性也有积极作用。与函数调用等语句不同，结构性改动通常不会因编译器选项变化（如函数内联）而发生变化，因此在不同版本或编译配置下表现得更加稳健。

签名生成模块

二进制签名生成：借助调试信息，可以将源代码行映射到对应的二进制指令位置，从而完成初步定位。随后，会基于这些指令构建一个局部控制流图（CFG），该图包含所有相关指令所在的节点。如果这些节点本身已经互相连通，构建过程将非常直接；但若存在断裂，还需引入一些补充节点以形成一个连通的局部CFG，这本质上属于Steiner树问题。在实际操作中，可利用 NetworkX 包中实现的近似 Steiner 树算法来完成该任务。这样的局部CFG结构能够较好地反映源代码变更的控制流特征。相较于整个函数级别的CFG，局部CFG更能抵抗不同编译器选项和架构所带来的影响，因为它排除了无关代码。然而，即便如此，编译配置本身仍可能对签名造成影响。因此，理想情况下应确保参考内核与目标内核使用相同的编译配置。具体操作中，会采用一种主动探测方法来识别目标内核的编译配置。识别并整理与源代码变更相关的二进制指令，根指令签名

理论上，前述局部控制流图中识别出的所有指令都可以作为二进制签名的一部分，但在实际应用中，这并非理想做法。事实上，只有其中一部分指令真正体现了核心行为和数据流语义，这类指令被称为“根指令”。二进制签名中包含的指令越多，签名就越具体，也越不具备“稳定性”。例如，编译器可能会插入一些中间指令来释放寄存器（如将其值暂存到内存中），如果这些无关指令也被纳入签名，就可能导致在目标二进制中无法成功匹配。以图3中的两条源代码语句为例，第一条赋值语句在编译后生成了3条二进制指令，但仅捕获最后一条指令就足以表达其语义，因为通过数据流分析可知，X1 等于 X0 加上 0x4，因此前两条指令可以被安全忽略。类似地，第二条语句对应的第03和04号指令已充分表达其语义，因为前面的00至02号指令的输出将在后续由其他指令消耗，不影响关键语义的提取。

简单来说，“根指令”被定义为数据流链中的末尾指令，即那些其输出数据不会再被后续指令继续传递的指令，同时还包括一些用于补全源代码语义的辅助指令。例如，在这种定义下，cmp 指令可视为根指令，但为了完整表达其条件判断语义，还需补充紧随其后的条件跳转指令。再如函数调用的场景中，根指令通常包括用于传递参数的 push 指令（以 x86 架构为例，每条 push 指令在各自的数据流链中构成末尾节点），以及最终的 call 指令，以完整体现函数调用的语义结构。从局部控制流图中提取根指令，局部控制流图

需要注意的是，即便面对相同的源代码语句，不同编译器或编译优化策略仍可能生成略有差异的根指令。为了提升签名匹配的适应性，系统在处理时会将类型相同的根指令视为等价，借此实现根指令的标准化。在表1中展示了多个源代码变更可能对应的不同指令类型示例。例如，在处理某条赋值语句时，编译器可能选择使用位运算代替乘法操作，从而生成不同的底层指令序列。

接下来，需要对根指令进行充分标注，使其能够唯一对应到具体的源代码变更——这些标注内容即构成二进制签名。基于前文第4.1节中的观察，既然目标函数与参考函数本质上是同一函数的不同版本，它们在变量层面的语义应当保持一致，因此，关键就在于将根指令中的操作数（如寄存器或内存地址）映射回其对应的源代码变量。只要目标函数确实应用了补丁，那么这些操作数所涉及的变量应与参考函数中看到的一致。因此，我们的任务就是确保生成的二进制签名能够完整保留这类语义信息。为实现这一目标，系统会为每个操作数计算其对应的全函数级语义表达式，直到其在根指令处的使用位置为止。如图1所示，这些表达式以抽象语法树（AST）的形式呈现，本质上是一种符合图4中记号定义的语义表达结构。语义表达式

二进制签名验证：尽管在源代码变更选择阶段已尽力保证其唯一性与稳定性，但由于在转化为二进制签名过程中不可避免的信息损失，仍需对生成的候选二进制签名进行进一步验证，以确保其仍符合预期要求。（1）唯一性方面：针对每个补丁，会分别准备对应的已打补丁和未打补丁版本的参考二进制文件，并利用匹配引擎（详见第4.4节）将所生成的二进制签名与它们进行比对。若某个签名基于已打补丁的代码生成，只有在未打补丁的参考版本中无法找到匹配项时，才被视为具备唯一性。即便如此，在参考的已打补丁二进制中，该签名仍可能存在多个匹配项（尽管这种情况较少见），此时会将匹配次数作为辅助信息记录下来。今后在真实环境中用于检测目标二进制时，只有当匹配次数不少于先前记录的值，才能判断该补丁确实存在于目标中。（2）稳定性方面：此前在第4.2节中所做的努力，即尽可能缩小源代码变更范围，也有助于增强所生成二进制签名的稳定性，因为源变更的规模与对应签名的复杂度密切相关。此外，如果有更多真实数据可用，还可以准备多个版本的已打补丁和未打补丁的函数二进制文件，并将候选签名在这些版本间进行交叉验证，以进一步筛选出那些在所有已打补丁版本中均存在、而在所有未打补丁版本中均不存在的高度稳定签名。

补丁匹配模块

粗粒度匹配：这一阶段属于快速匹配流程，旨在借助一些易于提取的特征对二进制签名进行初步比对：

• 控制流图（CFG）结构是其中一项关键特征，因为二进制签名本质上就是函数控制流图中的一个子图。除非签名仅位于单个基本块内（例如某条赋值语句所对应的签名），否则该步骤通常能够提供有效的匹配线索。
• 基本块的出口类型也是一种可用于快速比对的特征。通常情况下，每个基本块的出口可分为两类：无条件跳转和条件跳转。其中，无条件跳转在大多数指令集架构（ISA）中又可细分为函数调用、返回以及其他常规的控制流转移。因此，不同基本块可以通过其出口类型实现高效对比。
• 根指令类型也是用于快速比对的重要特征，系统会分析签名中的每个基本块，并确定其对应的根指令集合。通过这些指令的类型，可以高效对比两个基本块是否相似。为此，需要先为目标函数二进制中的每个基本块构建数据流图，虽然这一操作相较前几步计算开销更高，但整体仍在可控范围内。

借助上述特征，可以在目标函数中迅速缩小搜索范围。如果在这一阶段未能找到任何匹配项，基本即可判断该签名在目标二进制中不存在；反之，若发现候选匹配点，则仍需对每一个候选项进行更精确的比对分析，以确保匹配结果的准确性。

细粒度匹配：在这一阶段，系统利用生成的标注信息，对两组根指令进行精确匹配。核心任务是比对它们各自关联的语义表达式（即语义公式），以判断是否在语义层面实现了一致的功能逻辑。

为了完成语义层的比对，首先需要为所有候选匹配的根指令生成对应的语义公式。若签名中的所有根指令公式在候选根指令中均能找到匹配项，即可认为两者在语义上是等价的，即它们可映射至相同的源代码语句。对于公式之间的比对，本质上是两个抽象语法树（AST）的比较，已有一些方法通过计算树编辑距离来生成相似度评分；然而，FIBER 的目标并非输出一个相似度分数，而是要给出明确的匹配判断。

另一种方式是使用定理证明器验证两个公式的语义等价性，这种方式虽然最为精确，但计算开销极大，难以应用于实际大规模场景。因此，FIBER 采取了一种折中方案。根据观察，语义公式表达的是依赖关系，也就是指令之间的执行顺序，在保持语义不变的前提下，其结构通常不会发生变动（如评估所示），例如表达式 (a + b) * 2 不会变成 a * 2 + b * 2。此外，借助对公式中基本元素的标准化处理，匹配过程还具备一定的抗干扰能力。具体操作中，通过递归地比对AST中的操作符与操作数来完成匹配，同时允许适当的灵活性，例如对可交换的运算符，操作数的顺序不作严格要求。在比对前，系统还会通过 Z3 求解器对AST进行简化处理，以提升匹配效率与准确性。