Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Precise and Accurate Patch Presence Test for Binaries

题目:Precise and Accurate Patch Presence Test for Binaries 作者:Hang Zhang, Zhiyun Qian

单位:University of California, Riverside (加州大学河滨分校)

出处 USENIX Security Symposium (USENIX) 2018

原文:https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-zhang.pdf

相关材料:会议:USENIX 2018个人主页PPT演讲视频Github


一、背景

在软件中,如果出现漏洞或者是瑕疵,一般是使用打补丁的方式来修复或者更新软件。但是就目前的实际开发情况来看,软件代码的复用已经是一种常态,特别是针对大型的开源项目,往往会被很多不同的开发者复用。这本来不是什么严重的问题,因为开源出来的项目代码,本就是想提供给大家使用,并获得大家的认可,或者是获得大家的一些宝贵的修改意见和建议,以便于进一步完善开源项目,为开源社区提供更好的服务。开发者在遵循开源协议的前提下,既可以把开源代码应用到自己创建的新的开源项目中,也可以应用到自己的闭源项目中。因此,一个重要的问题就出现在我们眼前:当一个备受欢迎的开源项目被无数开发者所复用时,这个开源项目中所出现的任何问题(例如 BUG 或者漏洞等)都会影响到所有复用该项目的应用,当开源项目中的代码更新、或者是修复漏洞之后,那些复用该项目的应用能不能及时的更新相应的代码,这就成为一个比较严重的问题。特别的,当某一个备受欢迎的开源项目中出现严重的安全漏洞之后,该开源项目可能很快的就修复了这个漏洞,并更新了代码,但是复用该开源项目的众多应用能不能都及时的更新代码、修复漏洞,这就会严重的影响这些应用的安全性,甚至使得这些应用(未更新的应用)直接暴露在不安全的网络环境中,极易被攻击者所攻击。

因此,如何能够有效的检测目标应用中是否更新了相应的补丁,这是一个非常有意义的研究方向。就目前的研究情况而言,有两个明显的分支,一个是“源到源(Source to Source)”的检测方法,该方法操作的对象都是源代码,并且通常需要提供补丁的相应信息(例如,删除了一行代码并且添加了另一行代码);另一种方式是“二进制到二进制(Binary to Binary)”的检测方法,该方法单纯的比较二进制文件,因此,一般不需要相应的补丁信息。

## 二、提出的方法以及解决的问题

在这篇文章中,作者首先观察到两种有意义的情景:第一是开源越来越成为一种趋势,并且开源软件的代码通常都在 Github 上有完整的“Commit”或者是“Patch”历史;第二是开源代码被闭源的软件广泛复用(例如,OpenSSL、Linux-Base Kernel 等)。因此,针对背景中提到的“源到源”的检测方法无法适用于第二种情形,并且一般基于相似度进行模糊匹配,精度不高;而“二进制到二进制”的检测方法不能很好的利用开源代码所提供的语法和语义信息。由此,作者就提出了一种“源到二进制(Source to Binary)”的检测方法 – FIBER,能够充分的利用上述两种情形所带来的优势,用于检测目标二进制文件中是否已经安装了或者更新了相应的补丁。

三、技术方法

图1-FIBER工作流程

如图 1 所示是 FIBER 的工作流程,它分为三个主要组成部分,分别是:Change Site AnalyzerSignature GeneratorMatching Engine。输入分为四个部分,分别是: Source PatchedRef. function (src)Ref. function (bin)Tgt. function (bin)

首先,Change Site Analyzer 用于分析补丁(Patch)对代码所产生的改动,它所需要的输入信息包含两个部分:一部分是补丁信息 Source Patched,包含了对代码的改动信息(例如,增、删、改代码等),另一部分是参考的原始代码 Ref. function (src),也就是打补丁之前的完整代码。由于一个补丁可能会导致多处代码修改,或者导致多行代码改动等,因此,Change Site Analyzer 还需要负责找到一个最具有代表性的、唯一的并且容易匹配的代码改动信息(Change Site),来提供给下一步 Signature Generator 使用。Signature Generator 根据已经选出的一处最具代表性的代码改动位置,并结合源代码中所对应的二进制信息 Ref. function (bin),来生成对应的二进制级别的一个签名信息(Signature),并提供给 Matching EngineMatching Engine 根据这个签名信息,到目标二进制文件 Tgt. function (bin) 中匹配,以此来检测目标二进制文件是否已经打上该补丁。

下面开始对 FIBER 的三个主要组成部分进行详细的介绍:

1. Change Site Analyzer

Change Site Analyzer 的目的是为了找到一处合适的代码改动位置,让 Signature Generator 能够根据这个改动位置来生成一个 唯一的(Unique)稳定的(Stable) 签名信息。前文中也提到,Change Site Analyzer 需要提供两个输入:一个是源代码的补丁信息(Source Patch),另一个是完整的源代码(Reference Code Base)。因为一个补丁可能会多处的代码改动,而这些改动甚至会跨越不同的函数,因此,需要找到一个比较适合生成签名信息的一处改动来作为参考。

(1). 找到一个唯一的代码改动位置

由于补丁修复的方式并不唯一,有些通过删除一行代码实现,有些通过添加一行代码来实现,,还有些通过修改一行代码来实现等等,而文中作者只关注后两种实现方式。首先通过一个字符串匹配(Token-Based Sequence Matching)工具 lexer 来检测每一处新添加的代码是否是唯一存在的(相对于未打补丁的代码),如果没有找到这样的改动位置,则适当的添加一些 上下文信息(例如,相邻的语句) 或者 语义信息(例如,改动处的代码是否使用了所在函数的参数,如果使用则是使用第几个参数等)等,然后再做一些简化,以及利用变量的类型等信息一起构成一个唯一的代码改动位置。

由于所找到的唯一的代码改动位置可能不止一处,因此,就需要从中选出一处最具代表性的改动(更适合生成二进制签名信息的位置),作者把这些改动进行排序,按照优先级从低到高进行排序,首先是检测该处代码距离函数入口的距离,距离越近越好;然后是该处代码所在的函数大小,函数越小越好;最后是代码改动的类型(例如,打补丁之后使得原来的结构/控制流发生改变,比如插入 IF 语句等),有类型改变的情形所生成的二进制签名信息更加稳定,因此它的优先级最高。

最后,作者把补丁中出现的代码改变情况分为 3 类:

  • 函数调用类型(出现新的函数调用或者改变函数调用的参数)。该类型的优先级最高,因为 FIBER 可以很容易的根据目标二进制文件中是否拥有对该函数的调用来判断是否有补丁。
  • 条件相关类型(出现新的条件语句或者改变原有的条件语句)。该类型的优先级次高,因为条件语句会改变代码结构或语义信息。
  • 赋值相关(可能还包含一些算术运算)。该类型的优先级最低,因为它通常不会改变代码结构,并且可能需要一些额外的信息才能构成一个唯一的代码改动位置。

2. Signature Generator

Signature Generator 根据上一步提供的信息,以及由参考代码所编译出来的参考二进制文件信息来生成一个唯一的签名。并且在编译过程中所生成的调试信息要提供给后续使用。

(1). 定位和组织指令

首先,定位到已选出的补丁修改处的源代码所对应的指令(多条指令),并利用编译器生成的调试信息,构建一个本地的控制流图(CFG),该控制流图只包含与这些指令相关的节点;

(2). 定位 Root Instructions

理论上来说,上述 CFG 中所包含的所有指令就可以当做一个签名的一部分,但是这样做不是一个很好地选择,因为,往往是 CFG 中的一部分指令就可以代表该 CFG 的关键行为(Key Behavior, Data Flow Semantic),并且,作者把这部分指令称作 Root Instructions(关键数据到此处停止传播),Root Instructions 是 CFG 中所包含的所有指令的一个子集。这里的 Root Instructions 越少越好(因为如果根指令较多,就可能会由于不同的编译器在编译过程中可能会插入一些中间变量,导致生成的签名不稳定)。为了简单起见,作者把数据流链条(Data Flow Chains)末尾的指令和一些临近的语义相关指令定义为 Root Instructions,并把 Root Instructions 进行标准化。例如,对于 cmp 指令,作者把它和它之后的一条跳转指令作为 Root Instructions,对于 call 指令,作者把它和对应的 push 指令(相对于 X86架构)作为 Root Instructions,如表 1 所示。

表1-Root_Instruction类型

(3). 注解 Root Instructions

有了 Root Instructions 之后,还需要对这些指令进行标记,给它们打上相应的标签,打标签的目的就是为了让二进制的签名信息能够唯一的映射到原始的代码修改中。注解信息如图 2 所示。

图2-指令操作数的注解形式

从一个函数的角度来看,指令的操作数来源有四个:

  • 函数参数(外部输入)
  • 本地局部变量
  • 函数调用的返回值
  • 立即数(常数)

这四个来源在源代码中都有相应的语义信息,作者在签名信息中利用这些已有的语义信息,使得所产生的签名唯一且稳定。但就目前的情况来看,即使签名中没有这些语义信息,它也能够达到唯一性和稳定性的需求,

(4). 验证 Signature

签名信息生成好之后,作者还对它进行一轮验证,以确保签名信息在二进制文件中还能保持唯一性和稳定性(和源代码中找出来的候选代码修改处保持一致)。

对于唯一性,作者把补丁之后的代码和补丁之前的代码都编译成二进制文件,然后使用匹配引擎,用签名信息去这两份二进制文件中匹配,如果在已经打补丁的文件中能够匹配到,而在未打补丁的文件中匹配不到,则说明这个签名信息依然保持它的唯一性。此外,签名信息可能会在已经打补丁的文件中出现多次匹配的情况,在这种情况下,需要记录匹配的次数,当使用该签名到目标文件中匹配的时候,匹配次数大于等于记录的匹配次数才能说明补丁已经打上,否则认为补丁还没有打上。

对于稳定性,作者给出的方法是准备多个不同版本的已打补丁和未打补丁的二进制文件,然后用所生成的签名去检测哪一个更加稳定,选出最佳的签名。

3. Matching Engine

Matching Engine 用于检测目标二进制文件中的补丁修复情况,由于拥有目标二进制文件的符号表,因此,很容易定位到补丁所在的函数,所以作者就直接从目标二进制文件的目标函数开始进行分析,这就极大的缩小了匹配引擎的搜索范围。对于一个给定的补丁所对应的签名,使用该匹配引擎去目标二进制文件中匹配,该过程分为两个阶段:

(1). Rough Matching

第一轮的粗略匹配会根据一些明显的(Easy-To-Collect)特征去目标二进制文件中快速查找,这些特征包括以下三个:

  • CFG Topology。由于签名本身就是函数控制流图的一个子图,因此,可以根据该拓扑图去粗略匹配目标文件。
  • Exit of Basic Block。对于每一个基本块,都会有它的退出类型,包括无条件跳转(jmp、call、return等)和有条件跳转(与 ISA 有关),因此,可以通过判断它们的退出类型来粗略比较。
  • Root Instructions Types。根据 Root Instructions Types 也可以快速判断两个基本快是否相似或不同,但是这就需要生成目标基本块的数据流图,因此,相对前面的两个步骤会更加耗时一些。

通过上诉的快速匹配方法进行匹配之后,如果在目标二进制文件中没有找到对应的信息(没有匹配到),则说明目标二进制文件没有打上相应的补丁,否则,还需要进一步使用精确匹配方案来检测是否真的打上补丁。

(2). Precise Matching

经过第一步的快速匹配之后,可能找到了多个候选的 Root Instructions,因此,就需要把签名中包含的 Root Instructions 和候选的 Root Instructions 进行逐一的精确匹配,这个匹配的过程就需要用到前面生产的对 Root Instructions 的注解信息(语义表达式, Semantic Formulas)。

为了实现这种语义表达式的比较,作者首先需要对候选的 Root Instructions 生产对应的语义表达式(其实是 AST),然后对它进行简化,并使用 Z3 引擎 来比较它们是否相同。

4. Case Study

图 3 CVE-2015-8955的补丁

如图 3 所示是 CVE-2015-8955 的安全补丁,以及 FIBER 的一些处理过程。

FIBER 首先需要找到一个代码修改的位置,FIBER 找到的是 11 行和 12 行插入的 IF 语句,因为这里的条件判断语句改变了代码的控制流图,在二进制文件中比较容易匹配到。此外,为了保证该处代码语义的唯一性,FIBER 还把判断语句里面用到的一个变量 pmu 加入签名中,并且该变量是来自原所在函数的第一个参数(补丁中新增的),这样就能够保证该处的代码语义唯一。

FIBER 利用这个找到的代码修改位置和已经编译好的参考二进制文件生成一个该补丁的签名,然后到目标二进制文件中匹配,先是一个粗略匹配,根据 CFG 结构等信息匹配到两个候选的地方(11 行和 13 行),因为这两处的 CFG 结构相同。然后再做一个精细的匹配,根据注解信息以及语义信息(Root Instructions 使用到第一个参数等),匹配到图中加粗框部分就是补丁信息,因此匹配成功。

5. Implementation

FIBER 是基于 Angr 之上开发的,并对 Angr 做了一定的定制(增加了 1348 行代码,删除了 89 行代码),在 Angr 之上开发了 5097 行的 Python 代码。主要是利用 Angr 强大的符号执行引擎,可以生成语义表达式。FIBER 支持任意的架构,它会把二进制文件提升到中间语言 VEX,并且在查找 Root Instructions 的过程中所使用到的数据流分析也是基于 VEX 之上。

在注解 Root Instructions 的过程中,需要使用符号执行引擎来分析 Root Instructions 所在的函数,但是符号执行引擎需要处理路径爆炸问题,因此,作者还做了一些优化,包括以下三个部分:

  • 剪枝(Path Pruning),例如,循环只展开 2 次。
  • 受限下的符号执行(Under-Constraint Symbolic Execution),比如,不约束函数的参数,因为生成的表达式不需要求解,只需要比较而已;只在本函数内执行符号执行(Intra-Function Symbolic Execution),遇到函数调用,直接把返回值标记为 “Un-Constraint” 类型。
  • Symbolic Execution in Veritesting Mode,把静态符号执行和动态符号执行结合,提高静态符号执行的效率。

四、实验评估

作者评估了 FIBER 的有效性和它的性能。

实验环境

  • CPU:Intel Xeon E5-2640 v2
  • 内存:64 GB
  • OS: Unknow

数据集:

作者选择 Android Kernel 作为评估的数据集,评估数据集又划分为两种:

  • 一种是参考类型(Reference Kernel Source Code and Security Patches)。作者选择开源的 “angler” 安卓内核 v3.10 作为参考,该内核被 Google Nexus 6P 所使用。然后从安卓的安全公告中爬取自2016年6月到2017年5月之间的、与安全补丁相关的漏洞信息,总共包括 107 个安全补丁。
  • 另一种是目标内核镜像及相应的源代码。作者从 3 个主流的供应商中收集 8 个安卓内核镜像,并收集了它们的不同版本,如表 2 所示,作者只收集有源代码的内核版本。

表 2 数据集、准确度和时间表

1. 准确性

由于不知道目标镜像所使用的编译器和编译选项,因此,作者尝试不同的编译器和编译选项,以此来选出最接近的配置信息(通过 BinDiff 工具来查看相似性),来生成参考的二进制文件。最后发现表中的 6 和 7 所使用的配置是:gcc-with-O2,而其它使用的配置是:gcc-with-Os。此外,所有的内核镜像都带有符号表。

表 2 中的 Accuracy 列表明了 FIBER 的准确性,从表中可以知道,FP 列全为 0,也就是说,没有误报的情况。这个结果是最好的,因为在这种情况下,误报会导致很危险的行为,既:工具认为该内核已经打上补丁了,但其实没有。而漏报相对来说没有这么危险,只需要手工去确认一下是否真的未打补丁。

对于漏报的情况,作者认为有以下 5 个原因导致:

  • 函数被内联。签名和目标文件中不一样,一个被内联了,另一个未被内联。
  • 函数原型发生改变。例如函数参数个数,参数类型等发生改变。
  • 代码被定制。补丁修复方式不一致导致。
  • 补丁自适应(Patch Adaptation)。当补丁应用于老版本的代码时会出现这种情况。
  • 工程原因(Engineering Issues)。Angr 的前端无法识别或者解码目标代码。

2. 性能

性能分析分为两个部分,一个是离线的签名生成过程,对于某一个具体的补丁,该过程只需要执行一次即可;另一个是在线的匹配过程。

表 3 离线性能测试

吐槽 作者的数据解释不够详细,部分数据甚至未做任何说明和解释,特别是 ~70% 这一列,这一列作者没有给出任何的解释。

离线性能测试结果如表 3 所示,表中的第一行表示对源代码和补丁的分析,既 Change Site Analyzer 阶段,, 第二行表示签名生成过程,包括 Root Instructions 的识别与注解等,第三行和第四行表示对所生成的签名进行确认/验证的过程,通过把已打补丁的和未打补丁的代码编译成二进制文件之后去匹配签名信息。Cnt. 列表示补丁的数量(第一行)或签名的数量(其它行)。另外,在匹配的时候,一个签名可能会在目标二进制中匹配到多处,因此,签名数量会明显多于补丁的数量。

在线性能测试结果如表 2 所示,从表中可以看出,平均时间都在 10 秒到 25 秒之间,但某些情况下最大值会比较大。例如,在编号为 2 的内核版本中,最大值达到了 1047.10 秒。作者分析了原因,是因为某些函数非常大,并且很复杂,而 Root Instructions 又在函数的末尾,这就会导致匹配程序花费比较长的时间去匹配,但是平均值都在可接受范围之内。

3. 结果

表 2 中有一列是 TN,表明的是 FIBER 报出来未打补丁的、实际上也没有打补丁的数量,作者把它们整理到表 4 中(为了安全性着想,作者没有给出哪个内核版本没有打上哪个安全补丁),作者发现,即使对于一些高危的漏洞,部分厂商任然未能在补丁发放出来之后及时修复,这种情况最严重的例子是:对于这其中的一个高危漏洞(可以攻破整个系统内核并执行任意代码),当相应的补丁发放出来之后,某个厂商(A Major Vendor)甚至延期了一年半的时间才打上补丁。

表 4 潜在的安全漏洞

五、优缺点

优点:

  • FIBER 可以支持不同的体系架构(Architecture),以及不同的编译器和编译选项等,因为 FIBER 需要拥有被检测软件的源代码,因此,目标软件可以被编译到所需要的平台之上。
  • FIBER 可以支持不同的编程语言,因为它是以二进制形式来匹配目标文件,而对源代码的要求,只是提供一些语法与语义信息,以及一些符号信息(调试信息),并且能编译到目标平台上(虽然在这篇文章中作者评估的只是 C 语言实现的项目)。

缺点:

  • FIBER 需要拥有目标项目的源代码,因此,对于闭源项目,FIBER 无法正常工作。
  • FIBER 目前评估的结果,默认是已经拥有目标二进制文件的符号信息,因此,作者可以直接定位到补丁所在的函数位置。而匹配引擎则是从目标函数处开始进行匹配,匹配范围仅限于某一个具体的函数之内,这在实际中可能会不一样,实际中可能是没有目标文件的符号信息的。
  • 有一种明显的安全漏洞补丁 FIBER 是不支持的,就是只改变变量的类型,比如,原来是 unsigned int 类型,补丁中把它改为 unsigned long long 类型,像这种类型的补丁,FIBER 是无能为力的。
  • 评估环节对数据的说明不够详细,只是说了个大概,甚至没有说明那一列数据是什么意思(特别是 “~70%”这一列),“差评”。

六、总结和看法

总体上看,这篇文章就是做了一件事,那就是检测一个给定的目标二进制文件是否已经打上了(特定的)补丁,文章的一个优势就是它可以利用源代码中的一些信息来提高软件的检测精度,但这既可以说是 FIBER 的一个优点,也可以说是它的一个缺点,因为在没有源代码的情况下它就没法正常工作了。此外,作者在实验的过程中一直强调需要使用到目标文件的符号表,因为 FIBER 需要根据符号表来快速定位到补丁所在的函数(目标二进制文件中),从而使得 FIBER 的所有工作基本上都是在某一个特定的函数内进行,因此,在这个前提下, FIBER 能取得比较好的评估结果也是正常的,毕竟它都已经把工作限定在某一个特定的函数内了,而不再是针对整个目标二进制文件。对于这个问题,作者也提到了如何去寻找目标函数的方法(如果没有目标二进制文件的符号表或者是调试信息的话),但他把这项工作留给了将来实现。