【翻译】Designing New Operating Primitives to Improve Fuzzing Performance

WenXu SanidhyaKashyap ChangwooMin† TaesooKim Georgia Institute of Technology Virginia Tech†

摘要

模糊测试是一种通过重复注入变化输入到被测程序中来发现bug的测试技术。它因众所周知的实用性而非常受欢迎。当前对模糊测试的研究主要在于产生更容易触发漏洞的输入。

在这篇论文中，我们使用了另一种方式来提高模糊测试的效率，这种方式能减少每个循环的执行时间。以最先进的AFL为重点，在120核并行fuzz时，由于文件系统的竞争和fork()系统调用的可扩展性（scalability），是慢了24倍的。对其他fuzzer而言，因为它们设计模式相似，所以瓶颈是共通的。为了提升fuzz的效率，我们特地设计并实现了三个新的操作原语，来解决这些瓶颈，并在多核的机器上实现可扩展的性能。我们的实验表明，在120核的情况下，测试Google的模糊测试套件，AFL每秒执行的总数量能从6.1提高到28.9x，libfuzzer能从1.1提升至735.7x。另外，在30核（这在数据中心是较为普遍的配置）的情况下，操作原语还提高了AFL的覆盖率7.7倍。原语可以很容易地应用于任何的基本性能改进，直接受益于大规模的模糊测试和基于云的模糊测试服务。

一、介绍

攻击者利用漏洞来发起恶意攻击，以最大限度地控制用户服务。为了防止这些恶意的攻击，各金融组织和社区，在使用流行的软件和系统内核的时候，都要花费很大的努力去发现和修复他们产品中的bug，而在学术和实际中，其中一种发现bug的方法就是模糊测试（fuzz）。fuzz是一种软件测试技术，工作原理是将随机输入灌入被测试的程序。和其他发现bug的技术相比，模糊测试一个主要的优势是它能保证，只需要很少的人工操作和软件相关的前置知识，就能达到很高的覆盖率。例如，最先进的覆盖率导向型fuzzer AFL已经在开源软件中发现了超过一千的漏洞，甚至谷歌浏览器的安全也很依赖于它的模糊测试基础设施ClusterFuzz。

模糊测试是一种随机测试技术，需要巨大的计算资源。 例如，ClusterFuzz是一个分布式基础设施，由数百个虚拟机组成，处理50万个测试样例。最近谷歌为了让开源软件更加安全发布的也是由ClusterFuzz提供的OSSFuzz，平均每天会进行十万亿次的测试，在五个月以内已经发现了超过一千个bug。 除了谷歌之外，微软还提出了Project Springfield，该项目为开发人员提供了基于云的fuzz服务，以在他们的软件里发现bug，这清晰地表明了大规模的fuzz越来越应用广泛了。

对于复杂的软件堆栈和操作系统来说，fuzzer的性能是很重要的。换句话说，一个更好的fuzzer在目标程序中应该能更快地击中更多的bug。为了应对这一问题，有两个被广泛研究的方向：1）产生更能触发漏洞的输入（即使触及bug所需的时间更短）；2）缩短每个循环的运行时间（即在给定的时间里能达到更大的覆盖率）。

在之前的研究主要是在关注第一个方向。特别地，覆盖率驱动的fuzzers 通过目标程序的运行时覆盖率来评估一个测试用例，然后尝试去生成可能覆盖未触及分支的测试用例。更先进的技术还包括一种进化样本的技术，一个统计模型如Markovchain，或与符号执行相结合。但是，缩短每次模糊测试的执行时间也带来了巨大的好处， 这种方法在给定的fuzz策略下减少了发现新bug的时间。现在的fuzzer会用数天、数周甚至数月的时间来fuzz公开软件，以发现其中可被利用的漏洞，来应对它的内部复杂性并提高安全性。 因此对fuzzer性能的一个微小改进是能造成很大影响的，同时可以fuzzer节约巨大的运行成本。

一个关键的性能问题是，当前的fuzzer在多核框架（现已真实可用）的商业操作系统上并不具有可扩展性。（例如，2-4个socket + 16-64个物理内核这样的）。如图2所示，模糊性的可用性令人惊讶地差。 大多数CPU周期都因为底层的内容被浪费了，这降低了不超过30个CPU内核的fuzz的可扩展性。 这在概念上是反直觉的，因为每个测试样例都是无争用地独立运行的。

我们发现一些先进的fuzzer都有相似的结构（即启动并监控目标应用、创建和读取测试用例、并在不停循环的fuzz过程中可选择地在测试样例和fuzzer实例间同步）。为了完成这些步骤，这些fuzzer在fuzz目标程序中广泛依赖于众多的操作系统源于，这就是它们具有相似的特性和扩展性瓶颈的根源。

首先，在AFL之类先进的fuzzer的每个fuzz迭代中，会为当前的运行使用fork()来克隆目标程序。但是，这一行为在多核上同时生成进程是不可扩展的。fork()是被设计用来重复一些正在运行的进程的。在fuzzing的上下文中，大部分重复的fork()操作是有着相同的效果的，因为目标程序从未改变。

其次，模糊实例在每一轮的fuzz中，会密集地通过创建，写入和读取小的测试与文件系统进行交互。 这些操作导致了文件系统大量元数据的更新，这在多核上的并行fuzz方面是不可扩展的。

最后，如AFL、Libfuzzer等现有的fuzzer，在并行fuzz的时候，在每个fuzz实例之间共享测试用例。每个fuzz实例周期性地扫描其他fuzzer的输出目录来发现新的测试用例，然后重复执行这个测试用例来看它是否interesting。目录枚举操作和执行目标程序操作数，在更多fuzzer和更长时间fuzzing的情况下呈非线性增长，导致了第三个瓶颈。

在这篇论文中，我们为fuzzers提出了三个操作原语来达到在多核机器上fuzz性能的目的。这三个操作原语是针对fuzz提出的，它们旨在解决上述的三个性能上的瓶颈。

特别地，我们提出了：

1）snapshot()，一个新的系统调用，它能用有效而可扩展的方式克隆目的程序。

2）双文件系统服务，它在fuzzer对测试样例进行操作的时候，使用基于内存的文件系统（如tmpfs）来提高可扩展性等性能，同时使用磁盘文件系统（如ext4）来确保容量和持久性。

3）共享内存日志，它能帮助fuzzer在一种可扩展的、协同合作的方式共享测试用例的执行数据。

在这篇论文中，我们做出了以下贡献：

我们确定并分析了遏制大规模fuzz效率的一些突出的性能瓶颈，这些瓶颈源自于现有的操作原语仅用于一般用途。

我们设计并实现了三个新的模糊测试特定的操作原语，可以提升fuzzer在多核机器上的可扩展性等性能。

我们在AFL和libfuzzer上应用和测试了我们提出的操作原语——AFL在30核、60核和120核的机器上，每秒的执行次数提升了7.7/25.9和28.9倍。同时，libfuzzer在30,60,120核的机器上速率分别提高了170.5、134.9和735.7倍。

§2里描述了操作原语在fuzz中扮演的角色，以及它们成为了关键瓶颈的原因。新操作原语的设计在§3中提出，而在§4中描述了新操作原语是怎么帮助多核机器上运行的fuzzer的。§5提及了相关的实现细节，以及所提出的操作原语的评估会在§6中进行阐述。§7里说明了相关的工作，§9是相关的论文。

二、背景和动机

在这一环节中，我们首先描述了现代的fuzzer是怎么工作的（2.1），并解释了这些fuzzer所依赖的操作原语是怎样和为什么成为严重的可扩展性瓶颈的。

2.1 fuzz说明

模糊测试是一种用来在应用中发现bug的被广泛使用的软件测试技术。 它通过给目标程序灌入随机变化的输入，然后监控目标的反常行为（如崩溃、竞争、挂起或断言失败）来测试软件。

触发反常行为的输入会被认为是潜在的bug。为了更快地发现bug，已经有很多的技术被用来用更好的策略来更明智地变异输入，以更有效地探索程序的状态。

特别地，常见的fuzzer，如AFL和libfuzzer，利用过去的代码覆盖率来决定当前的变化输入是否interesting，并将其用作下次执行的反馈。

为了获得代码覆盖率，如果有源码的话，fuzzer需要插桩；如果是binary的话，fuzzer则需要一个系统仿真层如QEMU。

总的来说，一个fuzzer由一个种子输入集合（也被称为样本）开始，运行目标程序，然后通过之前执行的反馈（如覆盖率或crash）变异输入。

这整个过程称为一个fuzz循环，一个fuzzer可以一直进行这样的循环直到达到某个饱和点（在绝大多数的情况下都是无限期的）。

准确的来说，一轮fuzz循环包括如下步骤：

1）将优先级最高的测试样例（或输入）从磁盘加载到内存缓冲区。

2）通过随机修改某些字节来变异缓冲区输入，或在输入末尾增加随机的字节。

3）将最新生成的输入灌入目标进程，并监视它的运行时状态。

4）如果这个测试样例是interesting的，则将它作为连续运行的更深层的变化的新的测试样例保存到磁盘上，以供进一步运行中更深入的进化（如探测新的分支等）。

5）重复1），开始新一轮的fuzz

当多个fuzzer实例并行运行时，每个fuzz实例会有一个额外的同步阶段，来交换有用的测试样例。

在执行了某个数目的fuzz循环后，每个fuzzer会定期地检查其他fuzzer是否生成了新的测试样例，并重新执行部分的它们，来决定它对fuzzer自身来讲是否interesting——即覆盖到了fuzzer之前没有覆盖过的执行路径和基础块。这些interesting的样例会被保存到fuzzer私人的样本目录中。

2.2 AFL的设计

图1：AFL的大致设计。1.读入/同步 将输出文件夹中的测试用例读入缓冲区，变异缓冲区产生新的输入，并将其灌入测试进程。2.目标程序fork一个子进程来运行，它的执行路径会被记录在跟踪位图里。3.目标程序等待子进程来终止并返回它的退出状态。4.如果通过共享的跟踪位图（shared tracing bitmap）发现它覆盖了新的路径，就将该测试用例记录在输出目录中。5.重复这一fuzz进程。6.在多核系统里，每个AFL实例是独立运行的。

AFL是一个先进的fuzzer，它在不平凡的、真实世界中的软件里发现了许多的关键安全问题。我们现在着重于诠释AFL的结构框架，和它的性能、多核系统上可拓展性相关的设计理念。我们在图1中阐释了它的整体设计和工作流程。

变异输入（1）。AFL使用一种发展的基于覆盖率的变异技术来为在目标程序中发现新的路径生成测试用例。在AFL中，一个给定输入在目标程序中的执行路径表示为一个分支序列（如 覆盖位图）。为了追踪一个分支是否被触及，AFL在编译时对目标程序的每个条件分支和函数入口进行插桩。

发动目标程序（2）。传统的模糊器调用fork（）后跟execve（）来启动目标程序的实例。这个过程出现在每一轮的fuzzer中，以将新的输入灌给目标程序。它不仅消耗了时间，而且是一个不可扩展的操作。之前的研究表明，大多数的执行仅仅能执行到较浅部分的代码（如无效输入格式导致的等），这导致了输入样例的频繁执行。因此，fork()和execve()占据了fuzz的成本。为了降低这个成本，AFL引入了fork server，和Android中的Zygote进程类似，它消除了繁重的execve()系统调用。在实例化目标程序后，fork server等待AFL实例通过管道传来的起始信号。收到请求后，它用fork()克隆已经加载好的程序，然后子进程使用为当前loop生成的给定输入从入口点（即 main）继续执行目的程序的原始代码。父进程（fork sever）等待子进程的终止，并告知AFL进程，如果测试输入是interesting的话就将它保存。

记录结果（3，4）。fork server还会初始化一块共享内存（也被称作追踪位图），用于AFL实例和目标程序。实例记录了在执行过程中的所有覆盖信息，并把它写到共享的追踪位图中，追踪位图总结了之前运行时的分支覆盖。

并行fuzz（6）。AFL还支持并行模糊测试，以完全利用多核机器上的功能，和加快fuzz进程。在这种情况下，每个AFL实例在没有显式争用的情况下独立地运行（即令人尴尬地平行）。从AFL的设计上来看，fuzz操作应该随着核数的增加进行线性扩展。另外，为了防止对文件系统访问的显式争用，每个AFL实例在它用于测试用例的私有工作目录下工作。在每轮fuzz的最后，AFL实例扫描其它fuzz的输出文件夹来学习他们的测试用例，称为同步阶段。每个协作的邻居fuzzer都各自地保留着一个测试用例标识，该标识符指示它已检查的最后一个测试用例。它找出所有标识符大于保留标识符的测试用例，并以此重新执行这些用例。如果一个样例覆盖到了一条该fuzzer实例之前没有发现过的新路径，则这个测试用例会被拷贝到它自身目录来进行更深入的变异。

2.3 扩展fuzz的冒险

在一轮fuzz的过程中，fuzzer利用众多的操作系统原语，如fork()，和文件操作，就如2.1和2.2所说的那样。不幸的是，当扩展fuzzer到多个实例并行运行的时候，这些原语开始成为主要的瓶颈，导致了比单个fuzz实例更加糟糕的端对端性能。我们现在给出在fuzz进程的每个环节中的潜在系统瓶颈的更加深入的细节。

克隆目标进程。每个模糊测试的执行都需要一个新鲜的目标进程的实例来测试生成的输入。大部分的现有fuzzer使用fork()系统调用来快速地克隆目标进程，即，在每一轮的fuzz过程中，父进程都会拷贝一个新的目的进程，该进程是在相同进程状态下开始的（如虚拟内存空间、文件、套接字和权限等）

瓶颈：在性能层面，fork()系统调用有两个问题。首先，操作系统重复执行fork（）中一些冗余的操作，这些操作是没有用的，且对在fuzz循环时执行目标程序也是不必要的。其次，由于各种争用（如自旋锁）和标准要求（例如，PID应在POSIX中以增量顺序分配），因此使用fork（）系统调用并发产生的进程是不可扩展的。这些原语都要用到一个一般用途的fork（），但它显著地阻止了fuzz的可扩展性。例如，fork（）需要在内存页面上进行相应的动态映射，这是当前Linux内核中已知的可扩展性瓶颈。而且fork（）强调全局内存分配器用于分配新任务所需的各种元数据，需要设置安全性和审计信息，并且必须将任务添加到调度程序队列，这些都是已知的、在增加核数的情况下不可扩展的。 因此，上述的操作中，没有一个对fuzz而言是必要的。

创建变异的测试样例。每个复制的进程都用一个新鲜的、不同的变异测试样例来运行，以发现新的路径和崩溃。为了支持各种各样的应用，现存的fuzzer把测试样例存储为一个标准的文件，然后将它灌入目标程序，要么作为命令行参数输入，要么是标准输入。在每轮fuzz的最后，fuzzer把interesting的样例存储在磁盘上，并在之后用它来为下一次的运行生成变异的测试样例。存储在磁盘上的测试样例的数目单调增长，直到fuzzer停止，因为每个被保存的测试样例会在之后的fuzz循环中被再次进化。因此，最常见的做法是“保存的测试样例越小越好”（如，在AFL里，1kb大小是理想的），因为这减小了文件IO和变异搜索空间，使得典型的测试用例只保留几百个字节。每次运行的时候，fuzzer都会通过与文件系统进行大量交互来管理层测试用例。

瓶颈。fuzzer依赖的典型文件系统操作，亦即在每轮fuzz循环中对小文件的打开/创建（为了生成变异的测试用例）、写入（写入interesting的测试样例）和读入（为了加载测试样例），特别是在并行fuzz的时候。两个FxMark里的基准可以用来解释fuzzer的可扩展性细节：MWCL（即在私有目录下创建文件）和DWOL（即在私有目录下写入小文件）。更特别的是，创建和写入小文件的进程大量地修改文件系统的元数据（如，为创建文件分配的索引节点和用于文件写入的磁盘块），而元数据是文件系统实现的关键部分，是不可扩展的。

同步测试样例。并行测试时，每个fuzzer可以通过与其他fuzzer在同步阶段共享有用的测试用例来加快对搜索空间的探索。在这一阶段，每个fuzzer会通过重复迭代他们的测试用例目录来检查其他fuzzer的测试用例。例如,一个AFL实例的测试样例的文件名是以一个记录了序列号的前缀开始的，以此来作为它的标识，这指示了测试用例创建的先后，序列号更大则是更迟生成的测试样例。在同步的时候，每个AFL实例扫描它邻居fuzzer的目录，并通过这个前缀来决定是否同步过。然后它重复执行所获得的测试用例，来获得它的追踪位图，并判断该测试用例是否有用。

瓶颈。在同步阶段的目录扫描由于以下原因是不具有可扩展性的：首先，发现新的、未同步的测试用例的目录枚举操作，随着fuzzer数目的增长，是呈非线性增长的，这导致了同步阶段的耗时更长。举个例子，每个fuzzer需要O(f*t)，f是fuzzer的数目，t是目录下测试用例的数目。其次，目录枚举操作严重地干扰了新测试用例的创建，因为目录的读（目录枚举）写（创建文件）操作是不能同时进行的。

图2：AFL用于libjpeg binary时的多核扩展性。图2（a）显示了fuzz操作执行数（即测试新变异的测试样例）和同步操作执行数（即测试其他fuzzer那获得的测试样例）。图2（b）分解了fuzz和同步操作的执行时间。尽管fuzzer间没有任何的依赖，是一种令人尴尬的并行工作负载方式，AFL的可扩展性确实出乎意料地差。AFL的执行次数在15核的时候达到饱和，30核时开始下降，在120核的时候彻底崩溃。扩展性塌陷将近24倍的原因如下：1）AFL同步阶段的固有设计限制（2x）；2）fork()系统调用的开销(6x)；3）文件系统打开关闭小文件的开销（2x）

2.4 AFL的可扩展性

为了测试这些瓶颈的影响，我们在各种核数（从1到120）的情况下用AFL fuzz 了libjep库和JPEG 解压器（详情看§6）。我们使用AFL提供的输入样本（即种子输入）。图2描绘了fuzz libjpeg库的执行次数，表明AFK的可扩展性是令人惊讶地差的。执行次数在15核时达到饱和，并在120核近乎崩塌。考虑到标准的服务器的数据中心是32或64核、2或4socket的机器，当前先进的fuzzer是不能充分利用服务器的。这种糟糕的可扩展性是违反直觉的，因为模糊测试是一种令人尴尬的并行工作负载，fuzzer彼此间没有任何依赖性。图2（b）中的性能分解表明，在核数增加的情况下，变异和fuzz新用例的实际时间减少，而增加的时间被用于同步环节。一个很重要的点是，所有从其他fuzzer中同步的测试用例其实已经被运行过了，并且考虑到整个目的程序的探索流程的话，重复运行它们是毫无意义的。另外，图2（a）表明了从45核开始，操作系统内核成为了最主要的可扩展瓶颈，每个fuzzer实例首先会受到文件系统的影响，然后不可扩展的fork()系统调用也会产生一共24倍的开销，导致了前面所述的操作系统和fuzzer设计缺陷固有的可扩展性瓶颈。

总结。fuzzer看起来并行时是令人尴尬的，但fuzzer自身和操作系统的设计以不同寻常的方式引入了一些特性和可扩展性瓶颈，这需要在下层中进行性能工程以充分利用硬件的全部潜力。

三、操作原语

我们现在开始展现我们三个用于fuzzer可扩展性的操作原语：一个新的snapshot（）系统调用来代替笨重的fork（）系统调用(§3.1)，用于优化小文件操作的文件系统服务(§3.2)，和一个用于提高同步效率和可扩展性的共享内存测试用例日志(§3.3)。

3.1 Snapshot系统调用

如我们在§2.3所说的，fuzzer依赖fork（）系统调用来获得目标程序的快照，从而能容易地捕捉到它的崩溃。但是，一般的fork（）对fuzz来说是过于笨重的：它包含了大量的不必要的特性，如为了互换而创建的子进程物理页面的反向映射等，这是linux中众所周知的特性瓶颈。然而，通过将fuzzer视为OS中的一等公民，可以减轻或完全避免这些已知的争用，而不会损害在模糊测试中执行目标处理的正确性。

图3：通过snapshot（）系统调用简化快照的使用。一个进程（如AFL里的fork server）从利用sigsetjmp()系统调用来存储用户上下文开始，然后等待“go”信号去开始它的执行（1）。一旦它得到这个信号，它就准备执行（例如设置命令行参数等）并创造一个快照（2），然后开始运行main函数（3）。如果进程因任何原因（如exit（），segfault等）终止，在（2）里注册的一个回调函数callback()就会被调用。它可以用于任何目的（例如记录追踪的比特等）。通过恢复快照（4），内核将存储器和OS资源（例如，文件和套接字描述符）恢复到其原始状态(2)。最后，使用siglongjmp（）将程序执行恢复为初始位置1。

我们提出了一个新的系统调用，snapshot（），它是一个轻量级的，用来fuzz的可扩展的fork（）系统调用替代品。图3阐述了一个简单的如何使用snapshot（）系统调用的例子。snapshot（）为进程创建一个快照（如他的内存；文件、套接字描述符之类的操作系统资源）。在这之后，进程可以继续运行。在请求时，snapshot（）将进程的状态恢复为快照状态。它的原型如下：

1 int snapshot(unsigned long cmd, unsigned long callback, 
2 			   struct iovec *shared_addr)

cmd可以是用于快照的BEG_SNAPSHOT，或用于还原的END_SNAPSHOT。在BEG_SNAPSHOT里，用户可以注册回调函数，回调和共享地址范围向量，以及操作系统应该保持不变的共享内存地址。

例如，在模糊测试的情况下，shared_addr可指示在模糊器实例和目标进程之间的共享跟踪位图（检查§2.2在AFL中实际使用）。

当一个快照处理器发出命令时，它会调用已注册的回调函数。目前，我们不支持嵌套快照。 snapshot（）比fork（）更轻量级，更具可扩展性。它甚至比pthread_create（）具有更好的性能，因为它不需要分配和释放线程堆栈，这是pthread_create（）所需要的。在fork（）和pthread_create（）中不必要的操作最终会导致代价昂贵的TLB shutdowns，调度程序调用，内存分配，审计和安全相关的修改等（见图8）。

该节中剩余的部分，我们将会着重于fuzz的背景下介绍snapshot（）的相关细节。我们将完整的的fuzz流程分成三部分，并诠释snapshot（）是怎样和内核、测试进程在不同的阶段协同合作的。

3.1.1 fuzz之前：过程快照

我们假设要处理的这个fuzzer是使用AFL的fork sever的。更特别的是，我们在最开始加载目标程序。这个程序被序言prologue插桩，它会一直等待一个从fuzzer实例传过来的信号。一旦fuzzer实例的请求到达，应用就会执行fork()操作。然后，子进程运行它的main函数，同时它的父进程等待子进程的终止。

在我们的设计里，在fuzz运行之前，目标程序首先需要保存用户空间执行上下文ctx，或更特别地，用sigsetjmp()保存所有的当前寄存器的值和信号掩码。然后它进入一个循环，并继续等待来自fuzzer实例的新的模糊测试请求。 在收到请求时，进程snapshot（）保留其内核上下文（BEG_SNAPSHOT）并注册一个回调函数：callback（）。这个用户回调函数充当了每轮fuzz的结语，我们将在后面更详细地描述（第3.1.3节）。

在使用BEG_SNAPSHOT命令参数的情况下，内核会对它的数据结构进行操作，数据结构如下：

•虚拟内存区域（VMA）。snapshot（）重复进程的虚拟内存区域（即vmas），并临时存储每个vma的开始和结束地址。

•Page。snapshot（）维护一组可写的vma的页面，因为目标应用程序可能会修改这些可写页面，当应用程序终止时，内核应该恢复到原始状态。

为了跟踪这些可写页面并保持其原始内存状态，我们使用写时复制（CoW）技术。 我们通过更新相应的页表入口（PTE）和刷新TLB来将可写页面的权限更改为只读，以保持一致性。因此，这些页面上的任意写入都会导致页面错误，页面错误处理程序会捕获并处理该页面错误。 我们的方法包括了一个优化：我们不更改内核尚未分配物理页面所映射的可写虚拟地址的权限，因为这些页面上的内存访问将始终导致页面错误。

•BRK。 进程的brk定义了其数据段的结尾，这在Linux中表明了它的堆区域的有效范围。 因此它影响了在程序执行过程中堆分配的结果。 snapshot（）保存当前进程的brk值。

•文件描述符。 在快照进程结束时，内核关闭在快照后开启的文件描述符，但会把文件描述符的状态还原到快照前的状态。snapshot（）通过检查文件描述符表和bitmap（即open_fds）来保存开启的文件描述符。

除了修改这些数据结构外，snapshot（）还保留了已注册的回调函数。当快照进程在fuzz运行过程中终止（例如，调用exit（））时），snapshot（）可以安全地将控制流重定向到用户空间中的callback（）函数。

3.1.2fuzzing过程中：要求页面复制。

目标进程在从snpashot（）返回后要使用运行时的参数和环境变量从它真实的main函数那里继续运行。像§3.1.1里提到的，对每个可写的页面来说，由于我们把页面的权限改成了只可读，在目的进程的运行过程中，每一次的内存写入操作（在该页范围内）都会引起页面错误。在我们的页错误处理器中，我们首先会检查错误地址是否在快照页面里。如果在的话，就复制这一被修改的页数据，并连接到对应的拥有另外的写权限的PTE中。对于这一没被分配的、没有对应物理页面的页而言，我们只是分配了一个新的页面并且更新了对应的、拥有额外的写权限的PTE而已。最后，我们通过刷新TLB来保持一致性。

3.1.3模糊测试后：快照恢复。

在结束快照进程之前，我们会调用注册了的回调函数callback()。在正常的（即从main（）函数返回）终止情况下，它首先将退出状态（在该情况下是0）告知它控制fuzzer实例的父进程。为了处理这个状态，我们修改了sys_exit_group的入口函数并检查进程是否被快照。如果是，它会在用户空间里调用callback()。另一方面，如果目的进程在运行时超时或崩溃，它会返回相应的信号，如SIGSEGV或SIGALARM，这些信号量在默认情况下会终止受害进程。为了告知父进程异常状态并避免重建目的进程，我们插桩的prologue会在非常开始的地方为所有关键的信号注册一个特殊的处理器，这个处理器用相对应的退出状态（如segmentation fault对应139）调用callback()。

在调用回调函数后，进程用END_SNAPSHOT执行snapshot()来回到原始的快照状态。然后回归进程将保存了的用户空间上下文ctx用siglongjmp()归还，这把它指向了等待下一轮fuzz开始的状态。我们将这snapshot()中具体的过程用END_SNAPSHOT命令描述，它执行了以下四个步骤：

•恢复复制的页面。snapshot（）恢复被修改了的页面的母本，它同时会将被分配了的物理内存空间重新分配，恢复对应的PTE，并刷新对应的TLB入口。

•调整内存布局。snapshot再次重复给目的进程的VMAs并反映社所有新的被映射了的虚拟内存空间地址。

•恢复brk。进程brk的值会影响堆的分配，它会被恢复到保存的brk值。

•关闭打开的文件描述符。通过将当前文件描述符比特位图与过去fuzz运行之前的进行比较，snapshot（）确定打开文件的描述符和关闭它们。

与forfork（）相比，snapshot（）在复制许多内核数据结构（例如，文件描述符，内存描述符，信号和命名空间）方面节约了大量的时间。此外，它还避免了建立一个安全审计数据结构的副本，和给快照进程分配一个新的栈。因此，snapshot（）不会着重于内核内存的分配和cgroup模块。此外，snapshot（）还去除了调度的成本，即调度器从进程队列中执行增加、移除新的或推出了的进程时的操作的成本，从而消除了运行队列中的争用以及重新安排的中断。总之，snapshot（）在fuzz中扮演着和fork（）一样的角色，但它却更加轻盈和具有扩展性。

3.2 双文件系统服务

如我们在§2.3所说的，变异测试用例实际上涉及到小文件的操作，包括创建、写入、读取等，这在一些现存的文件系统是不具有可扩展性的，根本原因因文件系统而异，如在实现过程中的日志、锁的争用，或更严重的，在普通的虚拟文件系统VFS层面（如块分配器）。

我们介绍的第二个操作原语，双文件系统服务，就是用来为模糊测试提供高效且可扩展的稳健操作的。我们的关键思想是：无论是fuzz实例，还是测试实例，都不需要那么强大的同步模型，除非测试实例需要将序列化的突变状态持久储存。 在意外故障时（例如电源故障或系统崩溃），预计会出现一定程度的测试用例丢失，但是fuzzer始终可以在可接受的时间段内重现它们。新的文件系统为文件系统提供了两个等级的分层：一个内存文件系统（如tmpfs），在fuzzer实例和目标进程表现间进行无缝连接；一个磁盘文件系统（如ext4），用于存储和维护崩溃、输入和变异状态的容量和持久性。

我们的双文件系统服务为每个fuzzer创建一个单独的内存文件系统实例作为它的私有工作目录。这种方法完全避免了在同一个文件夹下同时访问测试用例的争用。此外，它还向fuzzer提供了一种错觉，即只有内存文件系统可以用，这使fuzzer在内存文件系统中创建和读取测试用例。为了在提供超过内存和持久性的容量的同时给出这样的错觉，我们的测试用例冲洗器，即文件系统的核心组成部分，定期检查内存使用是否超过预定义的阈值。如果是，则将内存文件系统中的测试用例移动到磁盘文件系统。这些测试用例文件将会被替换成指向磁盘上相应副本的符号链接。我们总是选择最旧的文件。因为之前生成的测试用例更有可能有更低的覆盖率， 且不太可能被fuzzer重新读取以进行编译。阈值和磁盘上要移动的旧测试样例的比例可以在启动文件系统守护进程的时候配置。

我们的方法使测试用例在移动到磁盘文件系统使是不可持久保存的，但是，在fuzz的背景下，这是没问题的。相比起依赖于单一的磁盘文件系统，它有两个不同的地方：1）我们会在系统崩溃的时候失去内存文件系统的文件；2）在文件被移动了，但是它的符号链接还没有创建这一很小的时间段中，fuzzer是不能看到这个文件的。但是，这些测试样例在fuzz中问题不大，它们没有影响fuzzing的正确性，只是让fuzzer重新生成或重新测试这些测试样例。

图4：一种在fuzzer间高效地共享测试用例信息（如文件名、跟踪比特位图等）的共享内存测试用例日志的插图。通过分享测试用例的信息，fuzzer可以判断其他fuzzer创建的测试用例有没有用，而不需要再次执行或者枚举目录。概念上而言，一个测试用例日志是一个大小固定的循环日志，它支持push（）和pop（）操作。不同于传统的循环日志，一旦所有fuzzer都进行了pop（）操作，该元素就会被从日志中移除。

3.3 共享内存中的测试用例日志

fuzzer在并行时，每个fuzzer在同步阶段利用到了别的fuzzer生成的测试用例。但是，跟之前提到过的一样，当前fuzzer的设计需要花费很大开销在用于发现新用例的目录枚举和用于得到追踪信息的再次执行上。因此，随着fuzz实例的增多，同步产生了很多不必要的测试用例再次执行，这增加了操作系统内核的开销。

我们引入了一个共享内存测试样例日志，来用于fuzz间无需任何开销的协作。这个测试用例日志是一个大小固定的、在内存里的循环日志（如图4），它能帮助fuzzer有效地管理和共享生成的测试用例。每个日志被master fuzzer实例所创建和控制，同时，任何其他的fuzzer实例都可以作为slave访问这些测试样例。每个日志元素存储着测试用例的信息，包括文件名、大小、哈希值和追踪比特位图。和传统的循环队列一样，我们的测试用例日志要维护好头指针。只有master可以在头指针那 push一个新的元素到日志里。但和传统的循环队列不同的是，任何slave在连接到日志的情况下都可以执行pop操作，来得到一个最旧的元素。每个slave保持它本地的TAIL。当它执行POP操作的时候，TAIL指向的元素就出列。一旦所有的slave都pop了最老的那个元素，全局的TAIL就会向前移动一位。为了扩展性，测试用例日志是没有锁的。此外，即使进程无限期运行，我们固定大小的设定也保证了内存使用的限制。

为了让fuzzer的开发人员在实践中利用测试用例日志，我们设计了表1中列出的几个接口。

create_log(int id, size_t tc_size) 为调用该接口的fuzzer实例用id创建共享内存测试用例日志，tc_size是测试用例元数据的大小

attach_log(int id) 和属于id对应的fuzzer实例的测试用例日志连接

push_testcase(int id, testcase_t *tc) 将最新生成的测试样例tc push进属于id对应的fuzzer实例的测试用例日志

pop_testcase(int id, testcase_t *tc) 从属于id对应的fuzzer实例的测试用例日志中得到一个corpus并交给tc

flush_log(int id) 从属于id对应的fuzzer实例的测试用例日志中暴力冲洗掉所有旧了的测试样例

close_log(int id) 销毁属于id对应的fuzzer实例的测试用例日志

每个fuzzer实例在最开始的时候创建自己的测试用例日志(create_log())。它还需要连接到其他fuzzer的测试样例来共享样本(attach_log())。在fuzz的时候，如果测试样例很有趣的话，fuzzer就会每轮fuzz结束之后把它的执行信息push到日志里(push_testcase()) ；在同步的时候，fuzzer从它的邻居那里pop出一个测试样例，来检查测试样例是否有用。需要注意的是，每个fuzzer始终从日志中获取第一个测试用例，它在避免了昂贵的目录枚举的同时，是没有进行检查的。 更重要的是，由于每个生成的测试样例的追踪比特位图（即，AFL中的trace_bits，和libfuzzer中的__sancov_trace_pc_guard_8bit_counters）是被直接访问的，因此不需要重新执行。当fuzz结束的时候，log会被fuzzer销毁（close_log()) ）。

四、 改进最先进的fuzzer

我们宣布，遵循§2中列出来的五个步骤的fuzzer，都能从我们的五个操作原语中获益。表2总结了上述措施对近几年来的已知的开源的10种fuzzer的适用性。

表2：根据十种fuzzer的设计和实现，表中显示了三个操作原语对它们的增益情况。

在这个环节，我们首先在§4.1中解释了我们的三个操作原语是如何普遍提高fuzzer性能的。在这些被选择的fuzzer中，AFL和libfuzzer是两个具有代表性的、被广泛应用的、成功发现过数多bug的fuzzer。它们也是很多后续研究和fuzzing项目的基础。因此，我们通过将上述原语应用到AFL和libfuzzer中，实现了基于Linux x86_64平台的两种工作原型，我们在4.2和4.3里介绍了相关的技术细节。

4.1 概述

4.1.1 快照系统调用。

首先，snapshot()系统调用可以作为AFL fork server中fork()的完美替代（详情请看§4.2.1）

现存的很多fuzzer如 Choronzon, VUzzer, IFuzzer, jsfunfuzz 和zzuf通过执行fork（）和execve（）（即python里的subprocess.Popen() ）来启动目的进程。这两个操作的结合是不可扩展的，并在fuzzing进程的时间消耗中占了很大的比例。为了让这些fuzzer应用snapshot（）系统调用，我们可以用连接到fuzzer的prologue对目标进程进行插桩，并设置还原点，而回调函数甚至不需要目的进程的资源。因此，fuzzer可以用和AFL相同的方式来利用snapshot（）系统调用。

libfuzzer为每个目的进程创建运行的线程。它的in-process模式避免了fork（）带来的竞争。因此，snapshot（）系统调用对它无用。

4.1.2 双文件系统

在多数情况下，每个fuzzer实例总是需要在文件系统里一个特殊的目录下创建和读取测试用例，而这在磁盘文件系统下，多进程的操作是不可扩展的。因此，所有fuzzer都可以从我们的双文件系统服务中获益。因为大多数情况下fuzz进程的工作目录都是可配置的，因此把该文件系统服务应用到它们上也是非常直接的一件事。libfuzzer在一个进程中有多个fuzzer实例，因此，给每个实例配置一个特殊的目录需要额外的修改（看4.3节）。

还有一种特殊情况，zzuf在启动目标进程之前并没有生成输入。它拦截文件和网络操作并使用给定种子的复制品直接改变进程的输入。因此，我们的双文件系统服务在默认情况下对zzuf没有多大益处。

4.1.3 共享内存测试用例日志

AFL、LibFuzzer和Choronzon等反馈驱动的fuzz通过所有正在运行的实例之间共享测试用例来支持并行模糊测试。每个fuzzer实例周期性的检查其他fuzzer生成的测试用例并将interssting的用例保存。同步阶段的性能瓶颈主要来源于目录枚举和测试用例的重复执行（§2.3所述），这可以通过使用共享内存解决。

一些发达的fuzzer如VUzzer和IFuzzer等本身是不支持协同fuzzing的，它们并没有同步这一阶段。通过应用我们的共享内存日志，这些fuzzer可以在多核的机器上没有征用地支持真正的多进程工作。

更多的常见fuzzer，如zzuf、jsfunfuzz等，是不通过什么度量或反馈来变异他们的测试用例的。只有一个测试用例触发了异常（如内存错误、超时、断言失败）等，它才会被认为是interesting的。对这些fuzzer来说，测试用例的在线共享并没那么有效，因为它们生成样本的大小是有限制的。

衍生Driller和AFLFast是两种近年来推荐的两种基于AFL的fuzzer。Driller使用符号执行扩展AFL，而AFLFast优化了测试用例的调度算法。它不会修改AFL的控制部分，因此我们的操作原语也能像应用在AFL上一样应用于它们。同理，Honggfuzz源于libfuzzer，所以操作原语也能以同样的方式用在Honggfuzz上。

4.2 扩展AFL

我们的三种操作原语都能增益AFL，解决它的性能瓶颈。

4.2.1快照服务

应用快照服务是很直接明了的，并不需要太多的工程上的努力。我们在main（）函数入口之前插桩了一个新的snapshot来替代掉原来的那个。 snapshot首先会执行sigsetjmp（）来保存用户空间的执行上下文，包括当前寄存器的值和全局的信号量掩码。然后，跟fork server一样，它等待AFL实例的开始信号。 一旦snapshot收到请求，它就会使用BEG_SNAPSHOT命令参数执行snapshot（），这个命令是回调函数cleanup（）的地址，该回调函数同时也被插桩到了目的应用进程中。同时，基地址和追踪比特位图也会通过shared_addr传入内核。被内存更新的比特位图在fuzz的过程中是不应该被重置的，因为它要用来判断测试用例是否interesting。 快照服务会直接使用运行时的参数和环境变量调用main（）函数。如果快照进程普通地在main（）函数中退出了，被插桩了的cleanup（）函数会被执行，以告知AFL实例退出状态，然后使用END_SNAPSHOT 调用snapshot（）来返回快照状态。

4.2.2 消除文件系统争用

AFL不用进行任何修改就可以应用我们的双文件系统。第一层是内存文件系统，保存了每个AFL实例的私有目录，AFL只会在读取和保存测试用例的时候和它进行交互。第二层是磁盘文件系统，它对正在运行的fuzzer是透明的。双文件系统守护进程周期性地，在内存使用没有超过阈值的情况下，把第一层文件系统中最旧的、和所有造成崩溃或挂起状态的测试用例移动到第二层中。另外，如果正在运行的AFL实例终止的话，所有生成的测试样例最后都会被保存到磁盘文件系统。

4.2.3 提高同步效率

我们现在来介绍我们怎么用我们的第三个操作原语来节约AFL在同步阶段枚举目录和重复执行测试用例浪费的时间。 在初始化的时候，每个AFL实例都会注册了一个测试用例日志，它在所有fuzzer中时共享的。我们的前提是我们已经知道了正在运行的fuzzer实例的数目，这个假设在多核并行模糊测试的实际应用中，是非常合理的，如数据库、实时操作系统等也满足这个前提。当一个新的interesting的测试用例被添加到日志（即add_to_queue()），它的文件路径、文件名和完整的追踪比特位图（默认情况下即65536比特的trace_bits）会作为一个元素存放到被共享的日志队列。 在同步阶段，一个特殊的AFL实例会从其他fuzzer的共享测试用例日之中pop出一个没被同步的元素，然后它就可以直接通过追踪比特位图来判断它是否interesting。之后，在每个同步阶段的最后，AFL实例会清除掉已经被每个其它fuzzer获取的测试用例。需要注意的是，AFL会尝试去缩减已经保存的测试用，这意味着测试用力的大小值在fuzz的过程中是会缩小的。这导致了存储在测试用例日志中的size值可能是过时的。但是，AFL测试用例实例总是会把它从其他fuzzer中同步到的测试用例复制到它的输出目录中，因此，我们依赖最后一次write()操作的返回值来决定最新的测试用例的size值。

4.3 扩展libfuzzer

在fuzz的时候，libfuzzer追踪代码的可达性，该代码可以使用种子corpus（输入的测试用例）或基于生成的corpus（变异的测试用例） 的变异结果来执行。 至于代码覆盖，Libfuzzer用的是LLVM的SanitizerCoverage，它能捕获各种于内存相关的错误并跟踪内存访问。更深入地来讲，每个libfuzzer都会各自维护一个跟踪程序位图（trace program bitmap），在每次运行后进行更新。此外，它还维护一个本地内存中的哈希表，用于存储libfuzzer认为有趣的测试用例。哈希表的key是它运行的interesting corpus的SHA1值，它也保存在磁盘上，以便其他libfuzzer可以用于进一步推进进度。特别的是，每个libfuzzer会定期扫描共享语料库目录，来获取哈希表中没有其SHA1值的任何测试用例。目前，在默认情况下，一秒会进行这样的同步一次。

启动目标程序 libfuzzer通过调用一个包含开发人员想要测试的目标代码的入口来工作。 调用libfuzzer的时候，它首先会创建一个本地日志文件，该日志文件记录了coverage、测试用例的输出和应用的变异策略，以及当前同步状态的信息。 在创建日志之后，libfuzzer会在语料库目录（如果有）中读取corpus，并将所有样本添加到它的哈希表中，然后开始挨个进行变异。 libfuzzer首先会重置检测位图（instrumentation bitmap），然后就将生成的测试输入和它的大小灌入被测函数。 如果覆盖率增加，libfuzzer会先将新输入的SHA1插入哈希表中，然后将输入保存到磁盘上的共享语料库目录中。

并行模糊测试 为了从共享目录中获取新的测试用例，libfuzzer先遍历目录，并且只读取那些 时间大于进行目录读取操作的时间的文件 在读取新的输入用例后，libfuzzer计算SHA1值并判断哈希表里面有没有，没有的话就执行。 之后，如果libfuzzer发现它是有趣的输入，就会将其保存在自己的语料库中，然后再进入编译阶段。

瓶颈 libfuzzer的设计存在两个问题，可以通过双文件系统和共享内存日志系统解决： 1）对不同的fuzz实例来说，通过文件系统进行同步是不明智的，因为他们在自己的内存中拥有了生成的语料库的副本，这些副本可以很简单地在它们之间共享。 2）此外，libfuzzer的同步阶段会收到文件系统开销的影响，因为它会读取和写入同一个不可扩展的共享语料库目录，这对fuzzer这样的应用程序来讲不是必须的。 我们能用我们接下来提出的更改，来通过增加核的数量，提升libfuzzer。

4.3.1高效的协作同步

libfuzzer已经能让libfuzzer从其他fuzz那里获取新的测试用例，来协同fuzz，因为他们的所有corpus都会被写入特定的共享语料库。我们使用共享内存测试样本日志来暴露测试样本、它的覆盖率位图（coverage bitmap）、和它的SHA1。另外，每个libfuzzer会维护一个本地的表，其中列出了从其他fuzz的日志中pop出来的测试样本的数目。因此，在完成了一轮同步之后，libfuzzer在它的locate table中增加了它从其他fuzzer的样本中读取的新的样本的数量。此外，现在的libfuzzer不会重复执行复制的corpus，因为它可以直接更新覆盖比特位图，而该位图是所有fuzz共享的。

4.3.2删除文件系统争用

libfuzzer的当前设计仍然存在写入interesting corpus时的竞争问题。 此外，在fuzz的过程中，它还会在fuzzing的目录下为每一个fuzzer中维护一个log。不幸的是，这两种设计都是不可扩展的。linux在创建新文件的时候保持目录锁定。为了解决这个问题，双重文件系统在每个fuzzer的内存文件系统上创建一个本地目录，来写入interesting corpus数据和它的日志。

五、实现

5.1 操作基元

我们开发了一个库，它包括了六个共享内存日志的接口（create_log(int id,size_t tc_size)，attach_log(int id)，push_testcase(int id, testcase_t *tc)，pop_testcase(int id, testcase_t *tc)，flush_log(int id)，close_log(int id)），大概100行代码。特别地，日志是作为linux中/dev/shm的共享内存接口实现的。

我们还实现了一个新的函数来代替旧的同步。它李用共享内存测试样例日志来连接库、调用相关接口。每个独立的AFL实例都有它的log，路径、大小和覆盖信息。它还保留其他fuzzer的用例的恒基。

5.2 应用

在libfuzzer的每个线程中，我们都有一个内存共享队列，它们单独地被自己的fuzzer更新，并且还有一个列表来保持记录有多少的样本数据从邻居fuzzer那里读入。我们在libfuzzer里增加了200行代码来实现这个想法。

六、测试

AFL

libfuzzer

（左）AFL + 共享内存日志 （右）AFL+snapshot（）

文件系统对优化AFL的影响