一种模块化可拓展策略的模糊测试工具

陈 鹏

（1.上海微系统与信息技术研究所上海200050；2.上海科技大学信息学院，上海201210；3.中国科学院大学北京100029）

近年来，由于软件漏洞导致的安全问题屡屡发生。软件漏洞作为当前计算机安全的主要缺陷，给计算机用户带来了极大的威胁。这些漏洞会被攻击者利用，入侵用户的系统和软件，从而导致隐私泄露、系统破坏等安全问题。虽然类型安全和带有垃圾回收机制的编程语言（如JAVA）可以帮助开发者避免一些内存安全问问题。此外，Rust语言的出现，也给内存和线程安全问题带来了极大的改善，减少出现软件漏洞的可能。但由于历史原因，大量核心系统和软件仍然采用C/C++语言来实现。C／C++语言并没有提供这些安全机制，因此通过软件测试的手段来发现漏洞成为了主要的方法。虽然现在有多种用来检测软件漏洞的技术，模糊测试（Fuzzing）[1-2]仍然是最有效的一种软件测试手段，并在产业界中被广泛应用。

1 模糊测试的类型

模糊测试（Fuzzing）是一种发现软件漏洞的自动化测试技术。它最早被提出用来测试UNIX utilities软件的可靠性[1]。自那以后，它被不断的改进，并被广泛使用在不同的场景下。基于对程序内在结构的不同了解程度，我们可以把模糊测试工具（Fuzzer）分为3类：白盒，黑盒，和灰盒[3]。黑盒模糊测试工具不需要了解程序的内部状态，而白盒模糊测试工具需要程序的源代码来执行高级的程序分析得到详细的内部状态。灰盒模糊测试是黑盒和白盒之间的一种折中的办法。它只需要对程序做轻量级的程序分析来得到部分程序的内部状态。从如何生成程序输入的角度来看，我们可以把模糊测试工具分为基于修改的和基于生成的两种。基于修改的模糊测试工具通过修改原先存在的输入样本来得到新的输入，基于生成的模糊测试工具在根据已知的输入格式生成新的输入。

2 American Ffuzzy Lop（AFL）

American fuzzy lop（AFL）[4]是目前应用最广的模糊测试工具。它是一种基于修改的灰盒模糊测试工具。AFL在编译时对程序插入轻量的代码来获取程序内部状态，并使用基因算法来自动的生成可能会触发新的内部状态的输入。此外，AFL是一种基于覆盖率的模糊测试工具。它通过不断生成输入来遍历程序内部的不同的执行路径（内部状态）来触发漏洞[5]。

AFL作为一个开源的程序，不单单在工业界被大范围使用，在学术界，由于它出色的效果和性能，在大量工作中也作为工作的基础，被修改来解决各种各样的实际场景和尝试新的模糊测试方法。但由于它的实现过于耦合，并没有对程序进行模块化，对其修改往往是一件非常困难的事情。为了解决这一问题，我们设计和实现了一种模块化可拓展策略的模糊测试工具。在确保它能够有与AFL不相上下的性能表现的基础上，我们的模糊测试工具对开发者拓展其功能更加友好。模块化的设计可以方便其他开发者以我们的工具为基础，更容易的去实现他们的想法。同时，可以更准确的去对比不同策略的效果。

3 设计概览

与AFL一样，我们的模糊测试工具是基于修改的、基于覆盖率的、灰盒的。该工具主要包括两个部分：程序插桩和动态执行。

3.1 程序插桩与代码覆盖率

程序插桩的目的是让执行的程序能够收集到程序本身内部状态。这些信息被用来指导模糊测试工具如何去产生输入。在此，我们将程序动态执行的路径当成它的内部状态。程序路径由一串分支组成，而分支是基本代码块间的跳转信息。在实现上，路径由一张固定大小的Table表示，Table中每个单元的Key代表某个分支，Value代表这个分支被执行过的次数。我们通过图1的代码来做访问分支的计数，从而代表程序的执行路径。

图1 程序插桩的插入代码：分支计数

插桩通过LLVM Pass[6]来实现。我们使用的是LLVM 4.0版本。插桩作为程序编译过程的最后一个环节，对原先程序代码插入检查分支是否被执行的代码，从而让它可以在动态执行时获取每个输入对应的执行路径，也就是我们所说的内部状态。此外，我们也可以通过Intel Pin或者QEMU来解决没有源代码时的插桩问题。

3.2 动态执行与反馈回路

动态执行部分包括以下几个步骤：

1）从输入样本池中选择一个输入样本。选择哪个输入样本是有输入样本本身的信息或者产生的内部状态所决定。

2）随机修改该输入样本，然后使用该修改后的输入启动被测试程序。该输入会被写到磁盘中，测试程序将调用自身程序中的IO函数读取该输入。

3）获取程序的运行时的内部状态等信息。这些信息被用来判别是否触发异常、是否为一个新的输入样本。如果是一个对应内部状态没出现过的输入，则将该输入放入输入样本池中。此外，这些内部信息还可以用来指导怎么选择输入样本和修改输入样本。

4）重复步骤1）～3）

4 模块化与可拓展策略

根据第3节，我们对模糊测试工具进行模块化。

4.1 程序插桩的模块化

图2为程序插桩的模块化。我们设计和实现了分支计数、污点分析和Fork Server 3个模块。每个模块可以是LLVM的一个Pass，或者是一个可以用来编译时动态链接的动态链接库。其中，分支计数和污点分析为LLVM Pass，Fork Server为动态链接库。污点分析模块用来定位样本输入中的重要部分。Fork Sever模块用来减少被测试程序的启动时间。每个模块基本上由一个代码文件实现，彼此之间不相互依赖。我们可以选择性的开启和关闭某些模块。此外，这些模块的启用顺序可以自由调整。基于这个设计，开发者可以灵活的增减模块，拓展自己想要的功能。

图2 程序插桩的模块化

4.2 动态执行的模块化

图3为动态执行部分的模块化，主要包括4个模块：输入样本池、调度策略、修改策略和执行器。动态执行部分的代码均使用Rust语言编写。Rust语言不但可以确保我们编写的程序安全高效，还提供了包管理、Trait等特性能使我们能更好的去模块化动态执行部分。

图3 动态执行部分的模块化

4.2.1 输入样本池

输入样本池管理已经收集的输入样本。这些样本包含正常的输入样本、可以导致程序崩溃的输入样本、可以导致超时的输入样本。在加入样本池前，每个输入样本都会通过它们相应的内部状态与样本池中一张全局的表进行对比，用来确保它们在样本池中是否为独一无二的。如果是，会把它们的内部状态更新到全局的表中，并将该输入样本加入到样本池中[5]。样本池中输入样本的内容会被存储在磁盘中，其他信息会存储在内存中，包含它的内部状态和文件长度、文件内容在磁盘中的路径等。开发者一般不会对输入样本池模块进行修改。

4.2.2 可拓展的调度策略

怎么从输入样本池中选择合适的样本用来修改是基于修改的模糊测试的一大难点。对模糊测试来说，最好的选择是能够找到一个在修改它之后最有可能找到漏洞或者新的内部状态的输入样本。在现有的实现中，研究人员除了使用轮询调度和随机选择外，还会通过一些启发去选择这些样本，比如根据路径长度、输入样本大小等[7]。在最近的研究中，AFLFast[8]尝试使用马尔可夫模型来调度样本，VUzzer[9]根据路径包含代码块的权重和来选择样本。在此，我们实现了基本的轮询调度和路径最长优先调度。我们的调度策略是模块化可拓展的，开发者可以通过预先暴露的接口（Rust trait）编写自己的调度策略。

4.2.3 可拓展的修改策略

如何去修改选择的输入样本是模糊测试的第二大难点，也是大部分模糊测试研究的工作。对目前的模糊测试工作来说，随机修改占了绝大部分。随机修改包含：随机的增减输入，随机的对某些输入进行数值上的加减、以及取反等。在最近的研究中，越来越多的工作尝试更加智能的去修改这些样本输入。AFL使用基因算法来拼接两个优先选择的样本。BuzzFuzz[10-11]使用污点分析识别样本输入中可能会触发漏洞的部分，并随机修改它们。DART[12]、SYMFUZZ[13]、Driller[14]使用符号执行来对输入样本进行修改。VUzzer和Steelix[15]识别代码中的“Magic Bytes”，并将它们赋值到输入样本中。修改策略和调度策略一样，也是丰富多样的。开发者可能根据自身需求，选择不同的策略。因此，我们对修改策略也是模块化可拓展的。我们实现了基本的随机修改策略、基因算法策略和基于污点分析的修改策略。在此之上，开发者可以选择或者混合使用这些策略，也可以通过预先暴露的接口（Rust trait）实现自己的策略。

4.2.4 执行器与高性能措施

执行器负责调用被测试程序，并将修改后的输入样本输入到被测试程序中。此外，执行器还会与被测试程序进行通讯（IPC）来获取被测试程序的内部状态，并将它们提供给其他模块。跟输入样本池一样，开发者一般不会修改执行器模块。一个好的执行器必须要高效和减少IO。我们通过以下5点来确保执行器高效运行。

1）Rust语言。Rust是一门编译型语言，自身没有垃圾回收等会使得运行速度变慢的运行时。同时，Rust编写的程序能够保证内存安全和线程安全。

2）Fork Server。Fork Server是 AFL 提出的一种技术。它通过在启动一个Server进程与模糊测试工具进行通讯，根据收到的命令来Fork产生子进程作为被测试程序。这样的机制可以大大减少程序被启动时的初始化时间。

3）绑定CPU核心（CPU Binding）。我们的模糊测试工具支持多线程同时工作。当使用多线程时，我们把每个线程绑定到具体一个CPU核心中，从而避免CPU任务调度，并对CPU缓存更加友好。

4）高效的进程间通讯（IPC）。我们使用Shared Memory的方式实现模糊测试工具和被测试程序间的通讯。直接分享内存使得数据的通讯更加高效，没有其他IO延迟。

5）虚拟内存文件系统（TMPFS）。该工具在启动时会自动在内存中划分一块区域作为虚拟内存系统。我们将样本池中的输入样本文件内容，以及一些必须记录在磁盘的信息记录在内存文件系统中，减少IO延迟。

5 结 论

我们调研了现有的模糊测试工具，根据目前模糊测试工具耦合太严重的缺点，提出了一种新的模块化可拓展策略的模糊测试工具。在这个工具为基础，我们可以方便的去根据自己的需求设计实现不同的调度策略和修改策略。这种方式能快速的测试一个实验性的思想是否工作。此外，我们使用Rust语言实现、采用Fork Server等机制保证了我们的模糊测试在其他基础模块的高性能。