一种基于时间分片的定向模糊测试

张晨辉，周安民，贾 鹏

（四川大学网络空间安全学院，成都 610041）

0 引言

模糊测试是现代漏洞挖掘最有效的技术之一，其为被测程序提供大量输入，并监视其出现的异常行为（例如堆栈溢出、越界读写、内存泄漏等）。自从模糊测试方法问世以来，其在业界和学界受到广泛关注并不断发展，研究人员开发了各种工具应用于不同的测试场景。近年来，随着AFL（American Fuzzing Loop）家族的出现，灰盒模糊测试的发展不断完善，并取得了优秀的成果。定向灰盒模糊测试的概念提出于2017年发表于CCS 的《Directed Greybox Fuzzing》，定向模糊测试需要事先指定目标点，例如，在有源码的情况下可以指定代码行数，定向模糊测试的目的就是为了使输入到达目标点，以探测该代码段是否存在安全问题。定向模糊测试主要应用在补丁检测、漏洞PoC复现以及静态分析验证等场景。但目前的定向模糊测试存在种子能量分配不均的问题，由于能量分配采用模拟退火算法，距离目标点近的种子分配的能量过多，而距离远的种子可能会被“饿死”；又或者设置种子能量与时间不相关，可以使每个种子得到对应的能量但同时忽视了时间有限这一因素。

基于此，本文在定向模糊测试中加入了时间分片的思想，将运行时间分为四个阶段，分别为探索阶段、短距离优先阶段、长距离探索阶段和长距离优先阶段。每个阶段采用不同的能量调度算法，使得每一个种子会在不同的阶段发挥其本身的优势；并且，在保证短距离种子分配到更多能量的同时，长距离种子在某些阶段也会分配到更多的能量。实验中，我们在binutils 测试集共7 个真实程序上进行实验，结果远优于AFLGo和Hawkeye。

1 相关技术介绍

1.1 模糊测试

模糊测试是指向待测程序提供大量畸形数据作为输入，监视程序的异常情况，基于导致异常的输入进行分析发现漏洞的一种方法。根据测试用例生成的方法，可以分为基于生成的模糊测试和基于变异的模糊测试。前者需要已知的数据格式，在不破坏格式的前提下生成测试用例；后者是将初始数据进行大量变异生成测试用例。按照对待测程序的分析程度，可以分为白盒模糊测试、灰盒模糊测试和黑盒模糊测试。白盒模糊测需要全部源代码，黑盒则不需要任何待测程序的信息，灰盒模糊测试介于二者之间，通过运行时的反馈来指导模糊测试。模糊测试已在漏洞挖掘领域发挥重要作用，但其仍然面临着许多问题：如代码覆盖率不高、不能完全探索程序空间等。目前主流的模糊测试工具有AFL、Peach、AFLGo、Hawkeye等。

1.2 定向模糊测试

定向模糊测试主要应用在补丁检测、漏洞PoC复现以及静态分析验证等场景。对于补丁测试，在程序出现漏洞时通常会打补丁，对打补丁后的版本可以针对补丁代码段进行测试，查看补丁的有效性；对于漏洞重现，因为部分CVE由于隐私问题不会提供PoC，只会在报告中展示漏洞代码出现的位置，因此可以利用定向模糊测试进行CVE 复现；在静态分析验证中，通过静态分析得到的可能存在漏洞的代码，需要通过动态测试来验证。

定向模糊测试的基本原理如下：定向模糊测试实现给定目标代码段，通过静态分析提取函数调用图（Call Graph，CG）和控制流图（Control Flow Graph，CFG），计算所有基本块到达目标点的最小距离，如Dijkstra 距离，这些距离用于在模糊测试时计算种子的优先度、能量分配等，使定向模糊测试趋向于目标点。在静态分析中，由于LLVM 可跨平台、编译速度显著优于gcc，并且可以设计插件提取CFG 和CG，因此在定向模糊测试中，通过LLVM 插桩的方式将距离和覆盖率信息插入目标程序。

1.3 符号执行

符号执行是指将程序的约束条件转化为抽象的符号，则一个程序的输出即可转化为一个关于输入的函数，符号执行可以得出到达目标代码段所需要的输入条件。符号执行分为静态符号执行和动态符号执行，其中静态符号执行是通过符号值模拟程序执行，而动态符号执行是在程序运行时进行约束求解。虽然符号执行可以达到较高的代码覆盖率，但是其状态空间爆炸、复杂约束无法求解、资源开销过大等问题限制了符号执行的实际使用。目前，主流的符号执行工具有KLEE、CUTE等。

2 整体流程和核心模块设计

如图1所示，SliceAFL 分为两个部分，静态分析阶段基于AFLGo，通过构建CG（call graph）和CFG（control flow graph），计算每一个基本块距离目标点的最短距离，距离基于Dijkstra 算法，基本块级别距离和函数级别距离基于AFLGo 实现。将每一个基本块的距离编译时插桩，插桩基于LLVM-Clang。

图1 SliceAFL整体框架示意图

在Fuzzing Loop 中，SliceAFL 设置1h 为一轮探索时间，每一轮分为四个阶段：前20 分钟为无差别探索阶段，接下来的20 分钟为短距离优先阶段，第40-50 分钟为长距离探索阶段，第50-60 分钟为长距离优先阶段。除了探索阶段，其余阶段按照需求进行基于模拟退火的能量调度。

2.1 基于时间分片的四个阶段

2.1.1 无差别探索阶段

本阶段旨在为Fuzzer 探索更多状态的初始种子。基于距离引导的定向模糊测试中，距离越短的种子越可能到达目标点，但是从模糊测试早期一直选择距离最短的种子很容易使Fuzzer陷入某个局部路径。所以，无差别探索阶段的目的就是尽可能地探索早期程序空间，得到各种状态的种子，为接下来的几个阶段提供种子基础。该阶段按照种子队列顺序选择种子，对每一个种子不进行基于模拟退火的能量调度，每一个种子的能量都取决于种子本身的性质而不是时间。因此，经过一段时间的探索后，种子队列里应当存在各种状态下的种子。

2.1.2 短距离优先阶段

在定向模糊测试中，时间是一个宝贵的资源，所以应当尽早到达目标点。在该阶段Fuzzer将全部能量投入到探索短距离的种子，距离越短的种子能量越大，越优先运行，意图在该阶段以最快的速度逼近目标点。但是该阶段的问题是一直选择短距离种子，会忽略长距离种子，而长距离种子也有可能触发crash，因此需要后续的阶段解决这个问题。

2.1.3 长路径探索阶段

该阶段是为了弥补第二阶段趋向于短路径的问题，该阶段将能量投入到基本块数量更多的种子。通过插桩时定义bb_passed 标志，以记录当前种子经过的基本块数量。本文认为，经过的基本块数量越多，该种子就探索了程序中更复杂的状态，这样的种子具有更大的探索价值。本文在该阶段没有选择距离最远的种子，理由如下：距离最远的种子可能位于程序的初始阶段，离目标点过于远，探索该类种子需要的时间消耗过大；其次，该类种子可以在无差别探索阶段被执行，所以长路径探索阶段不追求一味地探索距离最远的种子，而是探索基本块数量更多的种子，更复杂的程序状态意味着更多的可能性，会给目标函数带来更多触发crash的可能。

2.1.4 长距离优先阶段

该阶段作为长路径探索阶段的辅助阶段，优先选取上一阶段中产生的距离最近的种子，并给予较高的能量。特殊情况下，如果上一阶段没有产生新种子或者所有新种子都已经过一轮变异且没有产生新路径，则转入短距离优先阶段。这种情况意味着当前种子队列中的长路径探索效果不明显，所以将当前模糊测试的目标重新变为追求距离更近的种子以快速到达目标点。

2.2 基于基本块数量的模拟退火算法

在定向模糊测试中，我们通常只有有限的时间，因此AFLGo 采用了模拟退火的能量调度算法。模拟退火是指在随机游走过程中，该算法总是接受更好的解决方案，但偶尔也会接受较差的方案。温度是模拟退火算法的一个参数，用来调节接受较差解的概率，并随退火过程逐渐降低。初始时当=0=1 时，模拟退火算法总是能够接受较差解，当接近0 时，退化为经典的梯度下降算法，只接受更好的解。

换句话说，当=1 时，Fuzzer 刚开始运行，对于距离长和距离短的种子，都能够获得一定的能量，当接近0 时，距离长的种子的能量逐渐变少，距离越近的种子能量越高。然而，AFLGo 的模拟退火算法会导致长路径“饿死”。由于距离远的种子可能探索了更多的基本块数量，基本块数量越多可能代表着越复杂的程序状态，因此，在SliceAFL 中认为，程序空间复杂度和经过的基本块数量正相关，本文保留AFLGo 原有的基于距离的模拟退火算法的同时，增加一个基于基本块数量的退火算法：

定义annealing-based power schedule（APS），对于给定的seeds 和目标基本块，APS 将能量定义为：

其中，() =/，表示当前种子经过的基本块数量和所有种子经过的最大基本块数量的比值，保证了能量∈[0,1]；，表示探索的时间。在长路径探索阶段，刚开始运行时，APS 将相同的能量分配给经过不同基本块数量的种子，随着时间的推移，经过基本块数量越多的种子获得越来越多的能量，而经过基本块数量较少的种子获得的能量越来越少。SliceAFL在长距离探索阶段和长距离优先阶段不采用原有的基于距离退火，而是采用上述的基于基本块数量退火，保证了在短路径优先的前提下，同时探索了长路径的可能性。

注意，即使在第四阶段，即长距离优先阶段，虽然优先选择距离最近的种子，但仍然采用基于基本块数量的退火算法，因为该阶段的种子距离可能离目标点仍然较远，如果采用基于距离的退火算法可能会造成大部分种子分配的能量过少，详情参考AFLGo的模拟退火算法。

3 实验部分

为了验证SliceAFL 的有效性，本文选取AFLGo 和Hawkeye 为对比对象。由于本文关注复现漏洞时间快慢的对比，以及长路径的探索能力，所以使用Binutils测试集以及AFLGo 曾经复现过的部分漏洞程序进行实验对比。由于Hawkeye 并没有公开源码，所以本文中关于Hawkeye 的对比参考Hawkeye 文章中的数据结果。本文的实验运行在Inter Xeon CPU E5-2697 v3@ 2.60 GHz，包括14 个核心处理器，实验中使用10 个核心处理器，另外4 个留给其他程序。系统版本为Ubuntu 16.04 LTS。本文在Binutils上进行了测试，并与AFLGo，Hawkeye 进行对比。同样地，本文将每个实验运行20 次，时间预算设置为8个小时，初始种子输入文件只包含一个换行符（由echo“”＞in/file）生成，结果见表1。

表1 SliceAFL与AFLGo和Hawkeye的crash速度对比

其中Runs 代表复现该CVE 的次数，µTTE（s）表示平均复现该CVE 需要的时间，Factors 表示与SliceAFL 的µTTE（s）的倍数关系。在这些漏洞中，除了CVE-2016-4491 和CVE-2016-6131，其他CVE 漏洞的复现时间都很短。AFLGo 在文章中同时对比了AFL 的复现能力，AFL 也仅仅比AFLGo 慢了几分钟，因此在这些漏洞上对比定向模糊测试的能力并不准确。而对于CVE-2016-4491 和CVE-2016-6131，AFLGo 与Hawkeye 发现探测到这两个漏洞的时间都需要5 个小时以上，这种探索时间较长的CVE 才更能体现出定向Fuzz 的能力。SliceAFL 对于CVE-2016-4491 和CVE-2016-6131 都取得了更好的成果，击中次数略高于Hawkeye（分别为9 次和10 次），TTE远短于Hawkeye（15006 s和15872 s）。这种基于时间分片的思想取得了更好的效果。

4 结语

本文提出了一种新的定向模糊测试工具SliceAFL。SliceAFL 在时间有限的前提下将时间分段，并在不同的时间片段采取不同的模拟退火策略，从而更加快速地到达目标点。通过对比实验可以看出，SliceAFL 在探索长距离crash方面更有优势，并且在探索目标更多状态上取得了很好的效果。在未来的工作中，将会进一步完善种子选择策略，并在提高命中率方面作更多的研究工作。