The Art, Science, and Engineering of Fuzzing: A Survey

瞿铸枫

Abstract

在当今可用的许多软件漏洞发现技术中，模糊测试由于其概念简单性，较低的部署障碍以及在发现实际软件漏洞中的大量经验证据而一直非常受欢迎。从较高的层次上讲，模糊是指重复运行程序的过程，生成的输入可能在语法上或语义上是错误的。近年来，尽管研究人员和从业人员都付出了巨大的努力来改善fuzzing，但工作量的激增也使得fuzzing工作难以获得的全面一致的看法。为了帮助维护和增加众多模糊测试文献的连贯性，本文介绍了一种统一的通用模糊测试模型以及当前模糊测试文献的分类法。

1 Introduction

fuzz的社区非常活跃。在撰写本文时，仅GitHub就托管了上千个与模糊测试有关的repository。文献中也包含大量的模糊测试，并且越来越多的模糊测试研究出现在主要的安全会议上。此外，博客圈也包含许多模糊测试的成功案例。

研究人员和从业人员都在进行模糊测试。随着时间的推移，很容易失去对设计决策的跟踪以及对这些模糊器的潜在重要调整。例如，尽管AFL使用术语“测试用例最小化”来指代减少崩溃输入的大小的技术，但同一技术在funfuzz中称为“测试用例减少”。BFF包含了一种听起来类似的技术，称为“崩溃最小化”，但该技术实际上是试图使崩溃输入和原始种子文件之间的位数减少到最小，与减少输入尺寸无关。这使得很难使用发布的评估结果来比较模糊测试。本文认为，这种碎片化使得难以发现和传播模糊知识，从长远来看，这可能严重阻碍模糊研究的进展。

2 SYSTEMIZATION, TAXONOMY, AND TEST PROGRAMS系统化，分类法和测试程序

2.1 Fuzzing & Fuzz Testing

直观上，模糊测试是使用“fuzz input”运行被测程序（Program under test,PUT）的操作。本文认为fuzz input是PUT可能非预期的输入，即PUT可能处理不当并触发PUT开发人员意想不到的行为的输入。

定义1（模糊测试）模糊测试是使用从输入空间（“fuzz input space”）采样的输入执行PUT，该输入空间延伸出了PUT的预期输入空间。

3 remarks:

尽管模糊输入空间包含预期输入空间很常见，但这不是必须的，只要存在输入包含于模糊输入空间而不包含于预期输入空间就能满足要求。
在实践中，fuzzing几乎肯定会运行许多迭代；因此，在上面写“重复执行”在很大程度上仍然是正确的。
抽样过程不一定是随机的。

Fuzz Testing是利用fuzzing的一种软件测试技术。本文认为它的特定目标是查找与安全相关的错误，其中包括程序崩溃。本文还定义了fuzzer和fuzz campaign，这两个都是模糊测试中的常用术语：

定义2（Fuzz Testing）使用Fuzzing来测试PUT是否违反安全策略。

定义3（Fuzzer） fuzzer是一种在PUT上执行fuzz testing的程序。

定义4（Fuzz Campaign） Fuzz Campaign是在具有特定安全策略的PUT上特定执行fuzzer。

通过fuzzing campaign运行PUT的目标是发现违反指定安全策略的错误。例如，早期的模糊测试人员采用的安全策略仅测试生成的输入（测试用例）是否使PUT崩溃。但是，模糊测试实际上可以用来测试执行过程中可观察到的任何安全策略，即EM-enforceable可执行。决定执行是否违反安全策略的特定机制称为bug oracle。

定义5（bug Oracle） bug oracle是一个程序，可能作为fuzzer的一部分，它确定给定的PUT执行是否违反了特定的安全策略。

本文将fuzzer实现的算法简称为“fuzz algorithm”。几乎所有的模糊算法都依赖于PUT以外的某些参数。参数的每个具体设置是fuzz configuration：

定义6（fuzz configuration）模糊算法的模糊配置包括控制模糊算法的参数值。

模糊配置的定义旨在广泛。请注意，模糊配置中的值类型取决于模糊算法的类型。例如，将随机字节流发送到PUT 的模糊算法具有简单的配置空间{(PUT)}。另一方面，复杂的模糊器所包含的算法会接受一组配置，并随着时间的推移而不断发展，其中包括添加和删除配置。例如，CERT BFF在运动过程中会同时改变突变率和种子，因此其配置空间为${(PUT,s_1,r_1),(PUT,s_2,r_2),\cdots}$。

seed是PUT的（通常结构良好的）输入，用于通过修改它来生成测试用例。fuzzer通常维护一个seed集合，一些fuzzer会随着fuzz campaign的进行而进化该集合。此集合称为种子池。最后，fuzzer能够在每个配置中存储一些数据。例如，覆盖引导模糊器可以在每个配置中存储所获得的覆盖。

2.2 Paper Selection Criteria 论文选择标准

为了达到一个明确的范围，本文选择在2008年1月至2019年2月的4次主要安全会议和3次主要软件工程会议的最后会议记录中包括所有关于fuzzing的出版物。

主要安全会议包括

计算机和通信安全（CCS）ACM会议
安全和隐私（S&P）IEEE研讨会
网络和分布式系统安全研讨会（NDSS）
USENIX安全研讨会（USEC）

主要软件工程会议包括

ACM软件工程基础国际研讨会（FSE）
IEEE/ACM自动化软件工程国际会议（ASE）
软件工程国际会议（ICSE）

对于出现在其他场所或媒体中的作品，本文根据对其相关性的判断将其包括在内。

fuzz testing只区别于软件测试，因为fuzz testing与安全相关。

这种假设通常会促使测试工具的开发与fuzzer的开发具有不同的特性，fuzzer更可能被PUT开发人员以外的其他方使用。尽管如此，这两个领域仍然密切相关。因此在本次调查中，当不确定是否将出版物归类为与“fuzz testing”相关时，本文遵循一个简单的经验法则：如果出版物中出现了fuzz一词，本文就将其包括在内。

2.3 Fuzz Testing Algorithm

本文提出了一个通用的模糊测试算法，Algorithm 1，本文认为它已经在模型模糊器中实现了。它的通用性足以适应现有的模糊技术，包括第2.4节中定义的黑盒、灰盒和白盒模糊技术。

算法1以一组模糊配置和一个超时时间限制作为输入，输出一组发现的错误B。它由两部分组成。第一部分是预处理功能，在模糊活动开始时执行。第二部分是循环中的一系列函数：SCHEDULE、INPUTGEN、INPUTEVAL、CONFUPDATE和CONTINUE。这个循环的每次执行都称为fuzz iteration，每次INPUTEVAL执行测试用例上的PUT都称为 fuzz run。注意，有些fuzzer没有实现所有五个函数。例如，对于从不更新模糊配置集的Radamsa模型，CONFUPDATE始终返回当前配置集不变。

$PREPROCESS(\mathbb{C})\rightarrow\mathbb{C}$

用户向PREPROCESS提供一组fuzz configuration作为输入，并返回一组可能修改的fuzz configuration。根据模糊算法，PREPROCESS可以执行多种操作，例如向PUT插入检测代码，或者测量种子文件的执行速度。

$SCHEDULE(\mathbb{C},t_{elapsed},t_{limit})\rightarrow conf$

SCHEDULE接收当前的一组模糊配置，经过的当前时间和一个超时$t_{limit}$作为输入，并选择一个模糊配置以用于当前的模糊迭代。

$INPUTGEN(conf)\rightarrow tcs$

INPUTGEN将模糊配置作为输入，并返回一组具体的测试用例tcs作为输出。生成测试用例时，INPUTGEN使用conf中的特定参数。有些模糊器使用conf中的种子来生成测试用例，而另一些fuzzer则使用模型或语法作为参数。

$INPUTEVAL(conf,tcs,O_{bug})\rightarrow \mathbb{B}’,execinfos$

INPUTEVAL将模糊配置conf，一组测试用例tcs和一个bug oracle $O_{bug}$作为输入。它在tcs上执行PUT，并使用oracle $O_{bug}$错误检查执行是否违反了安全策略。然后，它输出找到的错误集$\mathbb{B}’$和有关每个模糊运行execinfos的信息，这些信息可用于更新模糊配置。本文假设$O_{bug}$嵌入在本文的模型模糊器中。

$CONFUPDATE(\mathbb{C},conf,execinfos)\rightarrow \mathbb{C}$

CONFUPDATE将一组模糊配置$\mathbb{C}$，当前配置conf和有关每个模糊的信息运行execinfos作为输入。它可能会更新模糊配置$\mathbb{C}$的集合。例如，许多灰盒模糊器会基于execinfos减少$\mathbb{C}$中模糊配置的数量。

$CONTINUE(\mathbb{C})\rightarrow {True,False}$

CONTINUE接受一组模糊配置$\mathbb{C}$作为输入，并输出一个布尔值，指示是否应该进行新的模糊迭代。此功能对于建模白盒fuzzer非常有用，当没有更多路径可发现时，该fuzzer可以终止。

2.4 Taxonomy of Fuzzers

本文根据fuzzer在每次模糊运行中观察到的语义的粒度将fuzzer分为三类:

black-box fuzzer
grey-box fuzzer
white-box fuzzer

这种分类不同于传统的软件测试，传统的软件测试只有两个主要类别（黑盒和白盒测试）。灰盒模糊测试是白盒模糊测试的一种变体，只能从每次模糊测试运行中获取部分信息。

2.4.1 Black-box fuzzer

“black-box”一词通常用于软件测试和fuzzing中，它们表示看不到PUT内部的技术，这些技术只能观察PUT的输入/输出行为，它是一个黑盒。在软件测试中，黑盒测试也称为IO驱动或数据驱动测试。大多数传统的fuzzer都属于此类。一些现代的模糊测试工具，例如funfuzz和Peach，也考虑到有关输入的结构信息，以生成更有意义的测试用例，同时保持不检查PUT的特性。在自适应随机测试中也使用了类似的直觉。

2.4.2 White-box fuzzer

白盒模糊测试通过分析PUT内部和执行PUT时收集的信息来生成测试用例。因此，白盒模糊测试能够系统地探索PUT的状态空间。白盒模糊测试一词是Godefroid在2007年提出的，指动态符号执行（DSE），它是符号执行的一种变体。在DSE中，符号执行和具体执行同时进行，其中具体的程序状态用于简化符号约束，例如具体化系统调用。因此，DSE通常被称为concolic测试（concrete+symbolic）。另外，白盒模糊测试也被用来描述采用污点分析的模糊测试。白盒模糊测试的开销通常比黑盒模糊测试的开销高得多。部分原因是DSE的实现通常采用动态插桩和SMT solving(satisfiability modulo theories，可满足性模理论)。虽然DSE是活跃的研究领域，但许多DSE并不是白盒测试工具，因为它们的目的不是发现安全漏洞。因此，本文没有提供有关DSE的全面调查，本文为读者提供了有关非安全应用程序DSE的更多信息的近期调查论文。

2.4.3 Grey-box fuzzer

一些fuzzer采取了middle ground approach，称为灰盒模糊测试。通常，灰盒模糊器可以获取PUT和/或其执行内部的一些信息。与白盒模糊测试器不同，灰盒模糊测试器不会考虑PUT的全部语义；相反，他们可以在PUT上执行轻量级静态分析和/或收集有关其执行的动态信息，例如代码覆盖率。灰盒模糊测试器依赖于近似的不完美信息，以提高速度并能够测试更多输入。尽管安全专家之间通常会达成共识，但是黑盒，灰盒和白盒模糊测试之间的区别并不总是很清楚。黑盒模糊器可能会收集一些有关模糊运行的信息，而白盒模糊器通常会使用一些近似值。本次调查中，特别是在表1中对模糊测试进行分类时，本文使用了最佳判断。

灰盒模糊器的早期示例是EFS，它使用从每次模糊运行收集的代码覆盖率来通过进化算法生成测试用例。 Randoop也使用了类似的方法，尽管它没有针对安全漏洞。诸如AFL和VUzzer之类的现代模糊器就是此类产品的典范。

2.5 Fuzzer Genealogy and Overview 族谱和概述

图1给出了本文按时间顺序对现有模糊器的分类。从Miller等人的开创性工作开始。本文手动选择了流行的模糊测试器，它们出现在大型会议上或获得了100多个GitHub star，并以图表的形式显示了它们的关系。黑盒模糊器在图的左半部分，灰盒模糊器在图的右半部分。此外，根据PUT使用的输入类型将模糊器进行细分：文件，网络，UI，Web，内核I / O或线程（对于并发模糊器）。

表1详细介绍了图1中最著名的模糊器使用的技术。每个模糊器都基于其对模型模糊器的五个函数的实现进行了总结，并在其他部分提供了有关模糊器的其他详细信息。本文在下面的每一列中描述了属性。第一列（反馈收集粒度）指示模糊器是黑盒，白盒还是灰盒。当模糊器具有使用不同类型的反馈收集的两个阶段时，将出现两个圈。

3 PREPROCESS

一些模糊器会在第一次模糊迭代之前修改初始的模糊配置集。这种预处理通常用于检测PUT，清除潜在的冗余配置（即”种子选择”），修剪种子并生成驱动程序。PREPROCESS也可以用于为将来的输入生成（INPUTGEN）准备模型。

3.1 Instrumentation 插桩

与黑盒模糊器不同，灰盒和白盒模糊器都可以通过INPUTEVAL执行模糊执行来检测PUT来收集执行反馈，或者在运行时对内存内容进行模糊处理。收集的信息量定义了模糊器的颜色（即黑盒，白盒或灰盒）。尽管还有其他方法可以获取有关PUT内部的信息（例如，处理器跟踪或系统调用使用情况），但插桩通常是收集最有价值的反馈的方法。

程序插桩可以是静态的，也可以是动态的-前者发生在PUT运行之前（PREPROCESS），而后者发生在PUT运行期间（INPUTEVAL）。

通常在编译时对源代码或中间代码执行静态插桩。由于它发生在运行时之前，因此与动态插桩相比，它通常带来更少的运行时开销。如果PUT有依赖库，则必须分别对这些库进行插桩，通常是使用相同的插桩程序重新编译它们。除了基于源码的插桩之外，研究人员还开发了二进制级别的静态插桩工具（即二进制重写）。

尽管动态插桩的开销比静态插桩高，但动态插桩的优点是可以轻松插桩动态链接库，因为插桩是在运行时执行的。有几种著名的动态插桩工具，例如DynInst，DynamoRIO，Pin，Valgrind和QEMU。

3.1.1 Execution Feedback

灰盒模糊测试器通常将执行反馈作为输入来演变测试用例。 AFL及其衍生作品通过检测PUT中的每个分支指令来计算分支覆盖范围。但是，它们将分支覆盖信息存储在位向量中，这可能导致路径冲突。CollAFL最近通过引入新的路径敏感哈希函数解决了这个问题。同时，LibFuzzer和Syzkaller使用节点覆盖率作为执行反馈。Honggfuzz允许用户选择要使用的执行反馈。

3.1.2 In-Memory Fuzzing

测试大型程序时，有时希望只fuzz一部分PUT，而不必为每个模糊迭代重新生成进程，以最大程度地减少执行开销。例如，复杂（例如GUI）应用程序在接受输入之前通常需要几秒钟的处理。 fuzzing处理此类程序的一种方法是在GUI初始化后拍摄PUT的快照。为了fuzz一个新的测试用例，可以先恢复内存快照，然后再将新的测试用例直接写入内存并执行它。相同的直觉适用于涉及客户端和服务器之间大量交互的模糊网络应用程序。这种技术称为内存fuzz。例如，GRR在加载任何输入字节之前创建快照。这样，它可以跳过不必要的启动代码。 AFL还采用了fork server来避免某些流程启动成本。尽管fork server具有与内存模糊测试相同的动机，但是fork server需要为每个fuzz迭代分叉一个新进程。

3.1.3 Thread Scheduling

条件竞争通常很难触发，因为它们依赖于不确定性行为，这种行为很少发生。但是，通过显式控制线程的调度方式，插桩也可以用于触发不同的不确定性程序行为。现有工作表明，即使随机调度线程也可以有效地发现竞争条件错误。

3.2 Seed Selection

fuzzer收到了一组模糊配置，用于控制模糊算法的行为。不幸的是，模糊配置的某些参数（例如基于突变的模糊器的种子）具有较大的值域。例如，假设分析人员对接受MP3文件作为输入的MP3播放器进行模糊测试。有效的MP3文件数量不胜枚举，这引起了一个自然的问题：应该使用哪种种子进行模糊测试？减小初始种子库大小的问题被称为种子选择问题。

一种常见的解决方法是找到最小的种子集，以最大化覆盖率度量，例如节点覆盖率，此过程称为计算最小集。

在实践中，模糊测试使用各种不同的覆盖率指标。例如，AFL的最小集基于分支覆盖率，每个分支上都有一个对数计数器。该决定的基本原理是仅在分支数量的数量级不同时才允许将它们视为不同。 Honggfuzz根据已执行指令，已执行分支和唯一基本块的数量来计算覆盖率。此度量标准允许模糊测试器将更长的执行时间添加到最小集，这有助于发现拒绝服务漏洞或性能问题。

3.3 Seed Trimming

较小的种子可能会消耗较少的内存并需要更高的吞吐量。因此，一些fuzzer试图在对种子进行fuzz之前减小种子的大小，这称为种子修剪。种子修剪可以在PREPROCESS中的主模糊循环之前进行，也可以作为CONFUPDATE的一部分进行。使用种子修剪的一个著名的模糊器是AFL，只要修改后的种子达到相同的覆盖率，它就会使用其代码覆盖率工具来迭代地删除一部分种子。

3.4 Preparing a Driver Application

当难以直接对PUT进行模糊测试时，准备驱动程序进行模糊测试是很有意义的。实际上，此过程在很大程度上是手动的，尽管在模糊测试开始时仅执行一次。例如，当fuzzing的目标是一个库时，我们需要准备一个调用该库中函数的驱动程序。类似地，内核模糊测试人员可能会对用户区应用程序进行模糊测试，以测试内核。IoTFuzzer通过让驱动程序与相应的智能手机应用程序通信来定位IoT设备。

4 SCHEDULING

在模糊测试中，调度意味着为下一个模糊迭代选择一个模糊配置。每种配置的内容取决于模糊器的类型。对于简单的模糊器，调度可以很简单。但是对于BFF和AFLFast等更高级的模糊测试器而言，其成功的主要因素在于其创新的调度算法。本节将讨论仅适用于黑盒和灰盒模糊测试的调度算法。白盒模糊测试中的调度需要符号执行者所特有的复杂设置，本文中不做讨论。

4.1 The Fuzz Configuration Scheduling (FCS) Problem

调度的目的是分析有关配置的当前可用信息，并选择可能导致最有利结果的信息，例如，查找最多数量的独特错误，或最大化一组生成的输入所获得的覆盖范围。从根本上讲，每种调度算法都面临着相同的exploration vs. exploitation冲突-可以花时间在每个配置上收集更准确的信息以告知将来的决策（探索），或在模糊当前认为会导致更有利结果的配置（开发）上花费时间。 Woo等称这种内在冲突为模糊配置计划（FCS）问题。

4.2 Black-box FCS Algorithms

在黑盒设置中，FCS算法可以使用的唯一信息是配置的模糊结果-所发现的崩溃和错误的数量以及到目前为止所花费的时间。Householder和Foote是第一个研究如何在CERT BFF黑盒突变模糊器中利用这些信息的人。他们假设应该选择具有较高观察到的成功率的配置（#bugs / #runs）。确实，在BFF中替换了统一采样调度算法后，他们发现在ffmpeg运行500万次后，独特的崩溃次数增加了85％，这表明了更高级的FCS算法的潜在益处。

4.3 Grey-box FCS Algorithms

在灰盒设置中，FCS算法可以选择使用有关每个配置的更丰富的信息集，例如，在模糊配置时获得的覆盖范围。 AFL是该类别的先驱，它基于进化算法（EA）。从直觉上讲，EA维护着一系列配置，每个配置都具有“合适性”的某个值。 EA选择合适的配置并将其应用于遗传转化，例如突变和重组以产生后代，这些后代可能随后成为新的配置。假设是这些产生的配置更可能适合。

5 INPUT GENERATION

由于测试用例的内容直接控制是否触发错误，因此用于生成输入的技术自然是模糊测试中最有影响力的设计决策之一。传统上，模糊器分为基于生成或基于突变的模糊器。基于生成的模糊器基于描述PUT期望输入的给定模型来生成测试用例。本文将此类模糊器称为基于模型的模糊器。另一方面，基于变异的模糊器通过变异给定的种子输入来产生测试用例。基于变异的模糊器通常被认为是无模型的，因为种子只是示例输入，即使大量，它们也不能完全描述PUT的预期输入空间。本节将基于基础测试用例生成（INPUTGEN）机制，对模糊测试器使用的各种输入生成技术进行解释和分类。

5.1 Model-based (Generation-based) Fuzzers

基于模型的模糊器基于描述给定PUT可以接受的输入或执行的给定模型来生成测试用例，例如精确描述输入格式的语法或不那么精确的约束（例如标识文件类型的魔术值）。

5.1.1 Predefined Model

一些模糊器使用可由用户配置的模型。这些模板通常指定系统调用期望作为输入的参数的数量和类型。在内核模糊中使用模型的想法起源于Koopman等人的开创性工作，他们将OS的健壮性与一组有限的手动选择的用于系统调用的测试用例进行了比较。Nautilus将基于语法的输入生成用于通用的模糊测试，并且还将其语法用于种子修剪。

5.1.2 Inferred Model推断模型

最近，推断模型而不是依赖于预定义的或用户提供的模型越来越受人们的关注。尽管有大量关于自动输入格式和协议逆向工程的研究已发表，但只有少数模糊测试者利用了这些技术。与检测相似，模型推断可以发生在PREPROCESS或CONFUPDATE中。

5.1.3 Encoder Model

模糊测试通常用于测试解析某种文件格式的解码器程序。许多文件格式都有相应的编码器程序，可以将其视为文件格式的隐式模型。 MutaGen [123]是一个独特的模糊器，它利用编码器程序中包含的隐式模型来生成新的测试用例。 MutaGen利用变异来生成测试用例，但是与大多数基于变异的模糊测试器（Fuzzer）会改变现有的测试用例不同，MutaGen会变异编码器程序。具体来说，为了产生一个新的测试用例，MutaGen将计算编码器程序的动态程序切片并运行它。基本思想是，程序片将略微改变编码器程序的行为，以使其生成略有格式错误的测试用例。

5.2 Model-less (Mutation-based) Fuzzers

经典随机测试在生成满足特定路径条件的测试用例时效率不高。假设有一个简单的C语句：if(input==42)。如果输入是32位整数，则随机猜测正确的输入值的概率为1/2^32。当我们考虑结构良好的输入（例如MP3文件）时，情况会变得更糟。随机测试不太可能在合理的时间内生成有效的MP3文件作为测试用例。结果，MP3播放器将在解析程序的较深部分之前，在解析阶段从随机测试中拒绝生成的测试用例。

这个问题促使人们使用基于种子的输入生成以及白盒输入生成。大多数无模型的模糊测试者都使用种子作为PUT的输入，以便通过修改种子来生成测试用例。种子通常是PUT支持的类型良好的结构化输入：文件，网络数据包或UI事件序列。通过仅对有效文件的一小部分进行变异，通常就可以生成一个新的测试用例，该用例大部分是有效的，但也包含异常值以触发PUT崩溃。我们使用了多种方法来变异种子。在下面描述常见的内容。

5.2.1 Bit-Flipping

bit-flipping是许多无模型模糊器使用的一种常见技术。一些模糊器仅翻转固定数量的位，而其他一些模糊器则随机确定要翻转的位数。为了随机地对种子进行突变，某些模糊测试器使用了一个用户可配置的参数，称为突变率，该参数确定了一次INPUTGEN执行时要翻转的位的数量。假设模糊器想要从给定的N位种子中提取K个随机位。在这种情况下，模糊器的突变率为K/N。

5.2.2 Arithmetic Mutation算术变异

AFL和honggfuzz包含另一种变异操作，它们将选定的字节序列视为整数，并对该值执行简单的算术运算。然后，计算出的值将用于替换选定的字节序列。关键的直觉是将突变的影响限制在很小的范围内。例如，AFL从种子中选择一个4字节的值，并将该值视为整数i。然后用$i\pm r$替换种子中的值，其中r是随机生成的小整数。r的范围取决于模糊器，并且通常是用户可配置的。在AFL中，默认范围是：$o\leq r\lt 35$。

5.2.3 Block-based Mutation

有几种基于块的变异方法，其中块的定义是种子的字节序列

将随机生成的块插入种子的随机位置；
从种子中删除随机选择的块；
将随机选择的块替换为随机值；
随机排列一系列块的顺序；
通过添加随机块来调整种子的大小；
从种子中取出一个随机块，以插入/替换另一个种子的随机块。

5.2.4 Dictionary-based Mutation

一些模糊器使用一组具有潜在语义权重（例如0或-1）的预定值，并格式化字符串以进行突变。例如，当对整数进行突变时，AFL，honggfuzz和LibFuzzer使用诸如0，-1和1之类的值。 Radamsa使用Unicode字符串，而GPF使用格式化字符（例如％x和％s）来使字符串变异。

5.3 White-box Fuzzers

白盒模糊测试器也可以分为基于模型的模糊测试器或基于模型的模糊测试器。例如，传统的动态符号执行不需要基于突变的模糊测试中的任何模型，而某些符号执行器利用输入模型（例如输入语法）来指导符号执行器。

并非所有的白盒测试器都是动态符号执行器。一些模糊器利用白盒程序分析来查找有关PUT接受的输入的信息，以便将其用于黑盒或灰盒模糊测试。本节的其余部分将根据现有的白盒测试模糊技术对其底层的测试用例算法进行简要总结。

5.3.1 Dynamic Symbolic Execution

在较高的级别上，经典的符号执行运行以符号值作为输入的程序，该程序代表所有可能的值。执行PUT时，它会构建符号表达式，而不是评估具体值。每当到达条件分支指令时，它在概念上都会派生两个符号解释器，一个用于True分支，另一个用于False分支。对于每个路径，符号解释器都会为执行期间遇到的每个分支指令建立一个路径公式（或路径谓词）。如果存在执行所需路径的具体输入，则路径公式是可以满足的。可以通过查询SMT求解器来生成路径输入的具体输入。动态符号执行是传统符号执行的一种变体，其中符号执行和具体执行同时运行。因此，我们通常将动态符号执行称为condicolic（concrete+symbolic）测试。这个想法是，具体的执行状态可以帮助减少符号约束的复杂性。除了将动态符号执行应用于模糊测试之外，对动态符号执行的学术文献进行的全面审查不在本文的讨论范围之内。但是，可以在其他来源中找到对动态符号执行的更广泛的处理。

5.3.2 Guided Fuzzing

一些模糊器利用静态或动态程序分析技术来增强模糊效果。这些技术通常包括两个阶段的模糊测试：

进行昂贵的程序分析以获取有关PUT的有用信息，
在先前分析的指导下生成测试用例。

Angora和RedQueen通过使用昂贵的仪器首先运行每个种子，并使用此信息生成输入，并使用较轻的仪器运行，从而降低了分析成本。 Angora通过使用污点分析将每个路径约束与相应的字节相关联，改进了“热字节”的概念。然后，它执行由梯度下降算法启发的搜索，以指导其变异解决这些约束。另一方面，RedQueen尝试通过检测所有比较并查找其操作数与给定输入之间的对应关系，来检测PUT中如何使用输入。一旦找到匹配项，就可以用来解决约束。

5.3.3 PUT Mutation

模糊测试的实际挑战之一是绕过校验和验证。例如，当PUT在解析输入之前计算输入的校验和时，许多测试用例将被PUT拒绝。为了应对这一挑战，TaintScope提出了一种可识别校验和的模糊测试技术，该技术可通过污点分析来识别校验和测试指令，并修补PUT以绕过校验和验证。一旦发现程序崩溃，他们就会为输入生成正确的校验和，从而生成使未修改的PUT崩溃的测试用例。 Caballero等提出了一种称为缝合动态符号执行的技术，该技术可以在存在校验和的情况下生成测试用例。

6 INPUT EVALUATION

生成输入后，模糊器将用该输入执行PUT，并决定如何处理结果。此过程称为输入评估。尽管执行PUT的简单性是吸引人的原因之一，但仍有许多与输入评估有关的优化和设计决策会影响模糊器的性能和有效性，我们将在本节中探讨这些注意事项。

6.1 Bug Oracles

模糊测试所使用的规范安全策略将被fatal signal（例如segmentation fault）终止的每个程序执行视为违规。此策略检测许多内存漏洞，因为使用无效值覆盖数据或代码指针的内存漏洞通常会导致分段错误或在取消引用时中止。另外，该策略高效且易于实施，因为操作系统允许此类异常情况被模糊器捕获，而无需任何工具。

但是，检测崩溃的传统策略不会检测到触发的每个内存漏洞。例如，如果堆栈缓冲区溢出用有效的内存地址覆盖了堆栈上的指针，则程序可能会运行到程序完成并产生无效的结果，而不是崩溃，并且模糊测试器不会检测到该错误。为了减轻这种情况，研究人员提出了各种有效的程序转换，以检测不安全或有害的程序行为并中止程序。这些通常称为sanitizer。

6.2 Execution Optimizations

本文的模型认为单个的模糊迭代要顺序执行。尽管这种方法的直接实现会在每次模糊迭代的开始就启动一个新过程时都简单地加载PUT，但是可以大大减少重复的加载过程。为此，现代的模糊器提供了跳过这些重复加载过程的功能。例如，AFL提供了一个fork服务器，它允许每个新的模糊迭代从已初始化的进程派生。同样，内存模糊测试是优化执行速度的另一种方法。无论采用哪种精确的机制，都将在许多迭代中分摊加载和初始化PUT的开销。

6.3 Triage分类

分类是分析和报告导致违反策略的测试用例的过程。分类可以分为三个步骤：重复数据删除，优先级划分和测试用例最小化。

6.3.1 Deduplication重复数据删除

重复数据删除是从输出集中删除所有触发与另一个测试用例相同的错误的测试用例的过程。理想情况下，重复数据删除将返回一组测试用例，其中的每一个都会触发一个唯一的错误。

6.3.2 Prioritization and Exploitability

优先级，也就是模糊测试的taming问题，是根据测试样例的严重性和唯一性对其进行排序或分组的过程。传统上，模糊检测一直用于发现内存漏洞，在这种情况下，优先级划分称为确定崩溃的可利用性。可利用性非正式地描述了攻击者能够针对测试用例暴露的漏洞编写实用漏洞的可能性。防御者和攻击者都对可利用的bug感兴趣。防御者通常先修复可利用的漏洞，然后再修复不可利用的漏洞，攻击者出于明显的原因对可利用的漏洞感兴趣。

最早的可利用性排名系统之一是Microsoft的!exploitable，它的名称来自其提供的!exploitable WinDbg命令名称。可探索者采用了几种启发式方法，并结合了简化的污点分析。它按照以下严重性等级对每个崩溃进行分类：EXPLOITABLE>PROBABLY_EXPLOITABLE>UNKNOWN>NOT_LIKELY_EXPLOITABLE，其中x>y表示x比y更严重。尽管没有对这些分类进行正式定义，但!exploitable在非正式上是为了保守起见，并在报告某些东西比其更可利用时出错。例如，!exploitable基于攻击者能够劫持控制流的假设，得出结论，如果执行了一条非法指令，则崩溃是可解释的。另一方面，除以零崩溃被认为是NOT_LIKELY_EXPLOITABLE。

自从引入!exploitable以来，已经提出了其他类似的基于规则的启发式系统，包括适用于GDB的可利用插件和Apple的CrashWrangler。但是，它们的正确性尚未得到系统的研究和评估。

6.3.3 Test case minimization

分类的另一个重要部分是测试用例的最小化。测试用例最小化是识别违反测试用例中触发违规所必需的部分，并有选择地生成比原始示例小和简单但仍会引起违规的测试用例的过程。尽管测试用例的最小化和种子修整在概念上相似，它们旨在减小输入的大小，但它们却是截然不同的，因为最小化器可以利用bug oracle。

7 CONFIGURATION UPDATING

CONFUPDATE函数在区分黑盒fuzzer和灰盒和白盒fuzzer的行为方面起着至关重要的作用。 CONFUPDATE函数可以基于当前模糊测试运行期间收集的配置和执行信息来修改配置集($\mathbb{C}$)。 CONFUPDATE以最简单的形式返回未修改的C参数。黑盒fuzzer除了评估bug oracle O~bug~之外不会执行任何程序自省，因此它们通常不修改C，因为它们没有收集到任何允许其修改的信息。

7.1 Evolutionary Seed Pool Update

进化算法（EA）是一种基于启发式的方法，涉及诸如突变，重组和选择等生物进化机制。在模糊测试的背景下，EA维护着有前途的个体（即种子）的种子库，该种子库随着新的个体被发现而在模糊测试过程中不断发展。尽管EA的概念相对简单，但它构成了许多灰盒模糊器的基础。

可以说，EA的最重要步骤是在配置C的集合中添加一个新配置，该配置在模糊化的CONFUPDATE步骤中发生。大多数基于EA的模糊器将节点或分支覆盖率用作功能功能：如果测试用例发现了新的节点或分支，则将其添加到种子池中。由于可到达路径的数量可以比种子数量大几个数量级，因此种子池意在成为所有可到达路径的不同子选择，以表示当前对PUT的探索。还要注意，不同大小的种子库可以具有相同的覆盖范围。

EA模糊器的一种常见策略是优化适应度函数，以便它可以检测到更细微和细粒度的改进指标。例如，AFL通过记录进行分支的次数来完善其功能函数定义。

另一个常见的策略是评估复杂分支条件时满足的条件比例。LibFuzzer，Honggfuzz，go-fuzz和Steelix会执行所有比较，并将所有在比较中取得进展的测试用例添加到种子库中。

7.2 Maintaining a Minset维护最小集合

具有创建新的模糊配置的能力会带来创建过多配置的风险。减轻此风险的常用策略是维护最小化测试用例集合，以使覆盖率指标最大化。

一些模糊测试器使用维护minset的变体来专门配置更新。举一个例子，没有完全消除不在最小集中的配置，而是使用剔除程序将最小集配置标记为有利。通过SCHEDULE函数，有利的模糊配置被选择进行模糊检测的机会要高得多。 AFL的作者指出”这在队列循环速度和测试用例多样性之间提供了合理的平衡”。