Digger：采用新路径记录方法的fuzzing工具

梁洪亮， 陈奕修， 裴霄潇， 谢卓思

(北京邮电大学 计算机学院，北京 100876)

本文关注软件测试的两个重要技术：fuzzing和混合执行. fuzzing背后的关键思想是生成大量测试用例并将其提供给目标程序，以便发现潜在的缺陷. fuzzing的原则之一是最大化计算资源的使用. 研究人员可能希望他们的fuzzer(即fuzzing工具)每秒评估上百万个测试用例[1]. 然而，由于其固有的盲目性(即在测试用例生成过程期间缺乏足够的引导)，fuzzer通常不能到达目标程序较深的代码分支. 相比之下，混合执行使用白盒方法来生成测试用例，这可以引导目标程序执行某些路径. 从理论上讲，它可以覆盖大多数程序路径. 然而，路径爆炸、约束求解等实际挑战使其成为一种耗时且相对复杂的技术[2].

因此，fuzzing和混合执行之间互补的优势使得它们的组合成为有价值的研究方向. 例如，Stephens等[3]实现了一个名为Driller的二进制分析工具. Driller的设计基于以下观察：程序的输入可以分为两类：“一般输入”，具有广泛的有效值，“特定输入”，只能从几个可能的值中选择. “特定输入”将程序分成几个区域，这些区域中不同的程序路径映射到不同的“一般输入”，并且这些“一般输入”可以通过fuzzing来产生. 此外，由于混合执行有出色的约束求解能力，因此它适合于生成“特定输入”. 实验显示，这种以混合执行为辅、fuzzing为主的方法找的程序缺陷数量要超过单独使用fuzzing和混合执行找到的程序缺陷数量的总和.

但是，由于无法区分同一函数的不同调用，Driller可能会错过潜在的缺陷. 具体来说，在fuzzing阶段，Driller会记录探索的路径. 当它遇到一对新的路径时，会根据路径的地址计算一个值，并使用该值来表示新的路径对. 这种路径记录方法很简单，但不能区分同一函数的不同调用之间的路径. 因此，在执行阶段，Driller将忽略一些程序分支，从而错过这些路径中的潜在缺陷.

本文提出了一种新方法来表示对程序进行fuzzing时的探索路径并在Digger工具中实现了新方法. 具体来说，在状态转换信息中添加函数的返回地址，因此本文的fuzzer可以在不同的调用点区分同一函数的不同路径. 此外，还解决了Driller无法检测输入为文件的被测程序的局限.

本文有如下内容：

① 提出了一种新的路径记录方法，以结合混合执行和fuzzing技术. 该方法在不同的调用点区分同一函数的不同路径；

② 实现了一个应用了新路径记录方法的混合执行辅助的fuzzing工具，Digger. 该工具可对32位和64位二进制程序进行测试，且能够支持从文件读取输入的被测程序；

③ 在现实应用程序(如GNU Coreutils)上进行了对比实验，结果显示Digger较现有工具Driller能够达到更高的代码覆盖率，且能够发现更多程序缺陷.

1 背 景

本节描述必要的背景知识，主要包括fuzzing、混合执行和插桩3种技术，以及与这3种技术对应的3个工具：AFL、angr和DynamoRIO，本文工具Digger是基于它们开发的.

① fuzzing.

fuzzing生成测试用例的方式主要有两种：基于变异的和基于语法的. 在本文中主要关注基于变异的fuzzing.

基于变异的fuzzing通常需要研究人员提供初始测试用例. 基于这些用例，使用替换、比特反转、数据添加或删除等不同的变异策略来生成大量新的测试用例[4]. 但其中只有部分能够探索新的程序路径. 因此，对于基于变异的fuzzer，了解测试用例如何影响目标程序的执行，如何调整变异策略，如何调整测试用例的数量和大小可以影响测试的结果和效率.

AFL[5]是一个流行的覆盖率引导fuzzer. 当目标程序是二进制时，它使用QEMU[6]来获取分支覆盖的运行时信息和分支命中计数. AFL根据这些信息来快速评估当前的测试用例. 能够找到新的程序状态转换的测试用例将被保留并进入下一轮变异. 在此过程中，引发崩溃的测试用例将被保留，供测试人员稍后进行分析.

② 混合执行.

混合执行是一种结合具体执行和符号执行的技术. 给定具体的输入，目标程序在特定路径上执行，同时，混合执行工具符号化输入，并收集对应路径上输入变量的约束[7]. 然后它选择性地忽略或者求解约束以生成新的具体值输入，引导程序执行其他路径. 混合执行是一种颇具潜力的程序分析技术，因为理论上它可以涵盖几乎所有的程序路径. 但是，其可行性受到许多实际问题的限制. 路径爆炸是混合执行主要的瓶颈，因为即使是一个小程序也可以拥有大量的分支. 不精确的约束求解是另一个瓶颈，当前SMT求解器的能力是有限的，无法求解很复杂的路径约束[2].

Angr是一个集成了许多先进的二进制分析技术的二进制分析框架[8]，混合执行就是其中之一. 它为用户提供了大量API来实现特定的功能. 例如，用户可以决定忽略和求解哪些路径，是否应该探索一条分支以及应该探索多远等等.

③ 插桩.

插桩是用来辅助程序分析的一种非常有用的技术. 通过插入不会影响目标程序原始逻辑的额外代码，测试人员可以在运行时获取程序的状态信息和行为信息. 该技术广泛用于fuzzing. 通过插桩，fuzzer能够知道程序路径是否已被执行，及其执行次数等. fuzzer根据这些信息评估测试用例并在不会丢失代码覆盖率的基础上对其进行剪枝[1]. 插桩的其他应用场景包括污点分析、程序调试、性能分析等[9-10].

DynamoRIO是一款专业的二进制检测工具. 它为用户提供了充足的API来构建自己的插件(也称为客户端)以满足需求[11]. 具体而言，它采用了回调机制，提供了许多事件供用户注册，在程序运行时，每当发生被注册的事件，它就会执行用户自己写的回调函数，回调函数中就是用户希望进行的操作，如通过插桩得到基本块的地址、函数名等[12].

2 动 机

本节首先描述了Driller采用的路径记录方法，然后举例说明为什么这种方法会导致问题及其带来的影响.

Driller中有两个模块，一个用于fuzzing，另一个模块用于混合执行. fuzzing模块基于AFL. Driller无法处理的情况是由AFL使用的程序路径记录方法引起的. AFL是一个覆盖引导的fuzzer，它在运行时获取探索的程序路径，并使用数组记录这些路径的信息. 如果它找到一对新的相邻路径(由prev_loc和cur_loc表示)，它首先计算prev_loc^cur_loc的值并将该值视为数组的索引，然后，它标记索引相应的值来记录新的路径对. 如果当前测试用例能够引发新的状态转换，AFL将此测试用例视为“感兴趣”的测试用例，并将其作为下一轮突变的基础放入特殊队列. 该程序路径重新编码方法相对简单且有效，因此Driller将其应用于fuzzing和混合执行模块.

图1展示了Driller不能很好处理的一种情形. 这段代码旨在处理多种命令. 在主函数中，字符串比较函数static_strcmp()分别在3个不同的条件语句中被调用. 因为user_command是一个“特定输入”，意味着它有特定的值，很难由fuzzing生成，在这种情况下，混合执行会被调用. 然而，Driller使用的程序路径记录方法不能区分不同调用点处static_strcmp()的函数内部路径(第4部分RQ1实证了这一点). 因此，混合执行第一次执行static_strcmp()并探索它所有路径之后，接下来两次调用都不会再求解约束. 如果没有合理的输入，程序就永远不会执行到后两条条件分支中的代码，而其中有一个程序缺陷. 实际上这种代码结构很常见，因此解决这个问题对于提高代码覆盖率以及找到潜在缺陷的概率有很大帮助.

图1 由Driller路径记录方式所引发的问题的示例代码[3] Fig.1 Sample code for problems caused by Driller’s path-recording method[3]

3 设 计

3.1 解决方案

为了解决在第2节描述的问题，提出了一种改进的路径编码方法，该方法使用三元组代替两元组来表示Driller中使用的状态转换. 添加函数标签(即函数的返回地址)以区分在不同调用点的相同函数.

图2显示了混合执行模块调用SMT约束求解器的算法，其中branches代表目前分支点处所有可能的分支路径(一般只有两条)，“t”代表在给定的具体输入下混合执行模块所走的路径，branches.active代表在当前分支点处所真正执行的路径，branches.missed代表在当前分支点处所没有选择的路径，一般正常情况下branches.active和branches.missed都各有一条.

图2 混合执行所采用的算法Fig.2 Concolic execution algorithm

这个算法可以判断branches.missed中的路径是否值得求解，具体过程为：首先获取并处理3个所需的地址信息，即上一条路径的地址，当前也就是处于branches.missed中的路径的地址，以及当前所在函数的返回地址，这3条地址信息在经过一定的处理后得到长度大小合适的3个数值prev_loc、cur_loc和func_label，接着将这3个数值进行异或运算，将得到的数值作为索引，查看fuzz_bitmap中对应的数值，fuzz_bitmap是用于记录已覆盖路径的数组，如果对应位置的数值为0则说明该分支对以前没有被覆盖过，此时混合执行模块就会调用其SMT求解器对该分支路径上的约束条件进行求解，得到能够使得程序执行该路径的测试用例. 在处理完一个分支点处的路径后，继续往下执行，通过t.next_branch()走到下一个分支点处. 该过程一直持续下去，直到在具体输入下的这条路径执行结束为止.

3.2 架构设计

本文用模块化的方式设计了Digger，并基于跨平台的工具来进行实现. 因此Digger在具有可拓展性的同时，还可以轻松地移植到其他操作系统. 如图3所示，Digger有3个模块. 以下详细介绍所有模块的功能和各模块之间如何协同工作.

图3 Digger系统架构图Fig.3 System architecture of Digger

调度模块主要负责两个任务：第一，开启和结束整个程序的运行；第二，监控fuzzing模块，在恰当的时间开启混合执行模块，使其能够辅助fuzzing模块的执行. 具体来说，调度程序模块提供了一个配置文件来帮助用户设置一些必要参数，例如被测程序的存放路径、测试结果的存放路径、测试时长、被测程序的参数、被测程序的输入是标准输入还是文件、插桩参数等. 测试开始后，调度模块首先开启fuzzing模块的功能，并监控该模块记录测试用例状态的文件. 如果fuzzing模块变异运行完所有“感兴趣的”测试用例后，还是没能发现新的程序路径，则调度模块就会开启混合执行. 而在进行混合执行的过程中，fuzzing模块会一直在后台运行.

fuzzing模块采用了基于变异的技术，需要外界提供至少一个种子(seed)作为初始测试用例. 这个种子以格式良好且大小小于1 kB为佳. 在测试期间，该模块保存引起崩溃的测试用例以供后续进一步分析. 在fuzzing模块运行的过程中，它会通过代码插桩技术来获取当前测试用例所覆盖的程序路径信息，并用数组(在图3中显示为fuzz_bitmap)来记录这些信息. 基于该信息，fuzzing模块可以确定当前测试用例是否可以发现新的状态转换. 如果是，则更新fuzz_bitmap并将该输入保留下来作为“感兴趣的”测试用例以供后续变异使用. 当调度程序发现fuzzing模块找不到更多新的程序路径时，则会开启混合执行模块.

混合执行模块的功能就是在需要时以fuzzing模块传递过来的测试用例为输入对被测程序进行混合执行，以生成能够突破fuzzing模块所遇到的程序瓶颈的测试用例，并将它们返回给fuzzing模块. 混合执行需要具体的输入来运行目标程序. 在本文的工具中，具体的输入是“感兴趣的”测试用例，这些测试用例可以覆盖所有fuzzing模块探索过的程序路径. 在执行的过程中，每当遇到一个条件分支，就与fuzz_bitmap进行对比，由此可判断另一条分支以前是否被覆盖过，如果没有就使用约束求解器求解与另一条分支对应的路径约束，得到能够使得程序走向另一条分支的外界输入，如果覆盖过就继续向下执行. 最后得到的新的测试用例传递给fuzzing模块，以帮助其突破所遇到的程序瓶颈.

3.3 系统流程

分析过程从fuzzing开始. 在fuzzing期间，它会把能够发现新的程序状态转移的测试用例保留下来. 这些测试用例被视为下一轮变异的基础，并周期性地对该“感兴趣的”测试用例集进行大小和数量上的精简，前提是保证该集合所覆盖的整体程序路径不变. 如果fuzzing遇到一些复杂的条件语句，若想通过这些条件语句就需要获得特定的外界输入，而这些特定的数值很难通过fuzzing的变异得来，则启动混合执行. 混合执行模块接收从fuzzing模块传递过来“感兴趣的”测试用例，如果遇到一个分支点，就通过与fuzz_bitmap的对比判断另一条当前没有执行的分支以前是否被覆盖过，如果没有就使用约束求解器求解出能够使得程序执行另一条分支的具体输入. 当执行完所有“感兴趣的”测试用例后，混合执行模块就将所生成的新的测试用例传递给fuzzing模块，帮助其通过程序中的复杂条件语句继续执行. 当达到最大测试时间或手动停止时，整个分析过程停止，fuzzing模块导出可以触发崩溃的测试用例.

4 评 估

本文基于AFL 2.35b，DynamoRIO-Linux-6.2.0-2和angr 5.6.12开发Digger. Digger使用DynamoRIO获取运行时信息，AFL和angr分别用于fuzzing和混合执行.

在本节中将展示3个实验的结果，这些实验用于从不同方面评估Digger.

① 新提出的程序路径编码方法能否比成熟工具Driller更有效地工作？

本文在一个Driller无法处理的程序上分别运行Driller和Digger. 编写了与图1相同结构的目标程序，以保证Driller无法处理. 程序的主函数中共有3个判断语句，且在每个条件语句中都调用了相同的字符串比较函数. 该函数有一个由外界传入的参数，当外界输入为first_cmd和Second_cmd时，程序分别能够进入两个没有缺陷存在的分支. 但当外界输入为crash_cmd时会走到存在程序缺陷的分支，引发程序崩溃.

表1显示了该实验的结果. Digger很快就生成导致程序崩溃的输入，相比之下，无论Driller运行多长时间，它都无法触发目标程序的崩溃. 至于代码覆盖率，Driller覆盖了60%的分支并执行了约78%的语句，而Digger覆盖了程序的所有分支和所有语句.

表1 实验1的结果Tab.1 Result of experiment 1

结果表明，通过本文方法，Digger可以有效地解决Driller的问题，并在Driller错过的程序路径中找到漏洞. 本文提出的路径记录方法能够有效地区分原本方法所不能区分的程序路径，从而帮助生成能够覆盖新的程序路径的测试用例，实现代码覆盖率的提高，并提高发现隐藏在目标程序中的缺陷的可能性.

② Digger能否实现比Driller更高的代码覆盖率？

第2个实验中的目标程序选自GNU Coreutils. Driller可测试的软件必须为能够从标准输入读取数据的软件，故本文所选取的10个软件都可以从标准输入读取数据. Driller与Digger 2列数据为执行基本命令的结果，Digger*为执行附加了其他参数的结果，三者的执行时间一致. 为了看看Digger的附加功能(即设置目标程序的参数)会带来什么影响，本文设置了1个控制组(Driller)和2个实验组(Digger和Digger*). 前两个不带任何参数地运行目标程序，而Digger*使用额外的参数运行. 例如，使用参数“-a”运行“who”. 在测试时间相同的情况下，Driller，Digger和Digger*的语句覆盖和分支覆盖结果分别如表2和表3所示. 图4为更加直观的实验结果条形对比图.

图4 Coreutils实验的语句和分支覆盖率Fig.4 Line coverage and branch coverage of Coreutils experiment

表2 Coreutils实验语句覆盖率Tab.2 Line coverage of Coreutils experiment %

表3 Coreutils实验分支覆盖率Tab.3 Branch coverage of CoreUtils experiment %

表2中的结果表明，在相同的输入和时间限制下，语句覆盖上，Digger比Driller有小幅提高. 具体而言，10个命令中，平均增幅约为2%. 分支覆盖上，整体增幅比较明显，平均增幅约为4%. 这说明在测试时间相同、不添加任何参数的情况下，较Driller而言，Digger具有更多的代码覆盖.

此外，表2和表3中的结果表明，在测试时间相同，添加了附加参数的情况下，Digger较Driller而言在语句和分支覆盖方面均有明显的增长. 语句覆盖上，10个软件中最高增幅为37.2%，平均增幅为12.31%. 分支覆盖上，10个软件中最高增幅为36%，平均增幅为12.14%. 这说明能够添加参数这一功能可以有效帮助Digger覆盖更多的程序路径.

③ Digger可以在实际软件中找到更多缺陷吗？

为了检验Digger测试实际软件的能力，本文进行了第3次对比实验，用Digger和Driller测试3个文件格式转换软件：catdvi-0.14、gif2png-2.5.9和pdf2svg-0.2.3. 测试所得数据如表4所示.

表4 catdvi,gif2png,pdf2svg的测试结果Tab.4 Test result of catdvi,gif2png,pdf2svg

在相同的时间限制下，对于被测软件catdvi和gif2png来说，Digger在语句覆盖范围和分支覆盖范围方面取得了进步(增加约10%～20%). 而对于pdf2svg来说，由于该软件只能从文件读取输入，故用Driller测试得到的覆盖率很低，即被测程序在运行伊始就终止了. 相对较高的覆盖率说明Digger在处理从文件读取输入的目标程序上具有明显的优势.

在测试结束后，本文使用GDB的exploitable插件对能够导致程序崩溃的测试用例进行了分析. 根据缺陷发生的位置，Digger在3个被测程序中的两个发现更多的崩溃. 具体来说，对于catdvi，Digger发现了空指针解引用、超出数组边界和除零3种缺陷. 对于gif2png，这2个工具都会发现超出数组边界缺陷. 对于pdf2svg，Digger在它的lib poppler中找到一个空指针解引用缺陷. 这些缺陷都是新发现的. 以catdvi为例，漏洞的详细信息见表5.

表5 catdvi的测试结果Tab.5 Test result of catdvi

总之，上述3个实验的结果表明：本文的路径记录方法可以有效地工作，并且应用此方法的工具Digger在测试实际软件时能够在较短的时间内达到较高的代码覆盖率，且能够有效地触发导致软件崩溃的程序缺陷，具有良好的实用性.

5 相关工作

本节介绍在结合fuzzing和符号执行技术，以及覆盖引导fuzzing方面的相关工作. 对于具有特定程序路径约束来说，符号执行很有效，而fuzzing可以非常有效地生成测试用例. 这2种技术相结合的研究方向最近引起了人们的广泛关注. 在fuzzing中使用的各种方法中，覆盖引导方法因其出色的表现脱颖而出.

① fuzzing结合符合执行.

传统的符号执行可以最大化代码覆盖率来找到程序缺陷[13-14]，但是路径爆炸还有约束求解带来的困难使得传统符号执行难以继续拓展[8,15]. 因此出现了一些工具试图将其与fuzzing结合来解决这种困难[3,16-18]. DART[16]和SAGE[17]使用混合执行引擎来修改fuzzing中的输入. SYMFUZZ[18]利用对于执行路径上对的符号分析来检测输入中比特位的依赖，然后利用这个依赖来计算最佳突变比率来指导fuzzing. Driller[3]只有在AFL的模糊测试卡住时才使用动态符号执行. Angora[19]也可以处理大型真实世界的程序以及利用符号执行的强大功能来解决难以通过的约束. Fietkau等[20]提出了另一种用混合执行辅助fuzzing的方法. 先运行动态符号工具执行一段时间，再将其生成的测试用例作为种子传递给fuzzing工具. 但他们的方法只在最开始调用混合执行一次.

② 覆盖引导fuzzing.

反馈fuzzing因其在真实应用中发现缺陷的突出能力而备受关注. 覆盖的程序路径信息是最常用的反馈. 覆盖引导的fuzzer使用此反馈来生成高质量的测试用例. 目前，许多灰盒式fuzzer(如AFL，Syzkaller，LibFuzzer等)都采用了这种方法并取得了丰硕的成果.

Syzkaller[21]的目标程序是Linux内核. 虽然该工具需要依据模板(用于描述每个系统调用的参数取值范围)来生成测试用例，但它也会在运行时收集有关被覆盖路径的信息，并据此指导变异过程. LibFuzzer[22]是专门用于测试库函数的fuzzing工具. 它可以在没有种子用例的情况下运行，但是当被测库函数接收的是结构化的、复杂的参数时，该工具的效率会有所下降. AFLFast[23]观察到大多数fuzzing最后都陷入了相同的几条高频路径，而他们使用马尔可夫链来识别低频路径，优先考虑包含此类路径的输入. AFLGo[24]提出模拟退火的能量调度算法来到达某些特定的程序位置. VUzzer[25]使用控制流特征来为路径建模，优先考虑执行到难以到达的路径的输入. 此外，VUzzer会检测错误处理的基本块，并优先考虑不包含这些基本块的有效输入. FAIRFUZZ[26]旨在探索被测程序的罕见部分，它首先优先生成可以执行到程序罕见部分的输入，然后提高变异后的输入能执行到相同的罕见部分，并且探索到不同路径的概率.

6 结 论

本文提出了一种新的程序路径记录方法，并将其应用于二进制分析工具Digger. 除了路径记录方法，与Driller相比，本文的工具还具有一些附加功能，如处理目标程序，从文件中读取输入，设置目标程序的参数等. 实验表明，与Driller相比，Digger能够达到更高的代码覆盖率，能够发现Driller不能探查到的程序缺陷，且在测试实际应用程序时也达到了良好的效果，由此证明了本文提出的方法的有效性和工具的实用性.

在未来，作者将使用DynamoRIO和angr的能力使Digger支持更多类型的架构，还考虑提高Digger的性能，使其更有效地执行.