在当今众多的软件漏洞发现技术中，模糊技术因其概念简单、部署门槛低以及在发现真实世界软件漏洞方面的大量经验证据而一直备受欢迎。
漏洞的大量经验证据。从高层次上讲，模糊处理是指重复运行程序的过程，生成的输入可能在语法或语义上有问题。语法或语义畸形的程序反复运行的过程。近年来，研究人员和从业人员为改进模糊测试投入了大量不同的精力，但这种激增的工作也使得人们难以对模糊测试形成全面而一致的看法。为了本文提出了一个统一的、通用的模糊模型，并对当前的模糊模型进行了分类。以及当前模糊处理文献的分类法。我们有条不紊地探讨了模型模糊器每个阶段的设计决策。通过调查相关文献以及艺术、科学和工程领域的创新，我们有条不紊地探讨了模型模糊器每个阶段的设计决策，从而使现代模糊器变得更加有效。

介绍

自从20世纪90年代初被引入以来[152]，模糊测试（fuzzing）一直是发现软件安全漏洞最广泛使用的技术之一。总体来看，模糊测试指的是通过生成可能在语法上或语义上不正确的输入，反复运行程序的过程。在实践中，攻击者经常在漏洞利用生成和渗透测试等场景中部署模糊测试[21]，[109]；2016年DARPA网络大挑战（DARPA Cyber Grand Challenge，CGC）中的多个团队也在其网络推理系统（cyber reasoning systems）中使用了模糊测试[37]，[200]，[9]，[93]。受这些活动的推动，防御者也开始试图在攻击者之前使用模糊测试来发现漏洞。例如，Adobe[1]、思科[2]、谷歌[61]，[5]，[15]和微软[38]，[8]等知名厂商都将模糊测试纳入其安全开发实践中。最近，安全审计人员[237]和开源开发者[4]也开始使用模糊测试来评估通用软件包的安全性，并为最终用户提供某些适当形式的安全保证。

模糊测试社区非常活跃。截至本文撰写时，仅在GitHub上就有超过一千个与模糊测试相关的公开代码库[86]。正如我们将展示的，相关文献中也包含大量模糊测试工具（参见图1，第5页），并且越来越多的模糊测试研究出现在主要的安全会议上（例如[225]，[52]，[37]，[176]，[83]，[239]）。此外，博客圈中也充满了许多模糊测试成功的案例，其中一些案例包含了我们认为值得在文献中永久保存的宝贵内容。

然而，研究人员和实践者对模糊测试的大量投入也带来了进展受阻的警告信号。例如，有些模糊测试工具的描述并没有超出其源代码和手册页面的范围。因此，随着时间的推移，模糊测试工具中的设计决策和可能重要的优化调整很容易被忽视。此外，在不同模糊测试工具中使用的术语存在明显的分裂。例如，AFL[231]使用“测试用例最小化”（test case minimization）一词来描述一种减少崩溃输入大小的技术，而同样的技术在funfuzz[187]中被称为“测试用例缩减”（test case reduction）。同时，BFF[49]包含了一种类似术语的技术“崩溃最小化”（crash minimization），但实际上这种技术旨在最小化崩溃输入与原始种子文件之间的差异比特数量，而与减少输入大小无关。这种术语的混乱使得通过已发表的评估结果来比较模糊测试工具变得困难甚至不可能。我们相信，这种分裂会阻碍模糊测试知识的发现与传播，可能在长期内严重阻碍模糊测试研究的进展。

基于以上原因，我们认为现在是整合并提炼模糊测试领域大量进展的最佳时机，其中许多进展是在2007年至2008年间三本关于该主题的专著出版之后[79]，[203]，[205]发生的。

在试图统一该领域时，我们将从§2开始，介绍我们的模糊测试术语以及统一的模糊测试模型。为了忠实于本文的目的，我们选择的术语尽可能反映当前的主流用法，而我们的模型模糊测试器（算法1，第3页）则旨在适应当前模糊测试文献分类中的大量任务（图1，第5页）。通过这一设置，我们将在§3–§7中探索模型模糊测试器的每一个阶段，并在表1（第6页）中详细概述主要模糊测试工具。在每个阶段，我们将回顾相关文献，解释设计选择，讨论重要的权衡，并突显许多出色的工程努力，这些努力帮助使现代模糊测试工具在其任务中变得高效。

系统化、分类和测试程序

术语“fuzz”最早由 Miller 等人在 1990 年提出，用来指代一种“生成一串随机字符供目标程序使用”的程序 [152, 第4页]。从那时起，“fuzz”这一概念以及其衍生的行为——“fuzzing”——已在多种上下文中出现，例如动态符号执行 [90]、基于语法的测试用例生成 [88]、[105]、[213]、权限测试 [24]、[80]、行为测试 [122]、[175]、[224]、复杂性测试 [135]、[222]、内核测试 [216]、[196]、[186]、表现依赖性测试 [121]、功能检测 [227]、鲁棒性评估 [223]、漏洞开发 [111]、GUI 测试 [197]、签名生成 [72] 和渗透测试 [81]、[156]。为了系统化总结大量文献中的 fuzzing 知识，我们首先从现代的 fuzzing 用法中提取出相关术语。

Fuzzing 与 Fuzz 测试

直观来看，fuzzing 是使用“fuzz 输入”运行被测试程序（Program Under Test，简称 PUT）的行为。为了向 Miller 等人致敬，我们将 fuzz 输入定义为一种 PUT 可能未预期的输入，即一种 PUT 可能错误处理并触发未被开发者预料的行为的输入。为了更清晰地表达这一概念，我们定义 fuzzing 如下：

定义 1（Fuzzing）：Fuzzing 是使用来自输入空间（“fuzz 输入空间”）的输入运行 PUT 的行为，其中 fuzz 输入空间超出了 PUT 的预期输入空间。

这里有三个需要说明的地方。第一，尽管 fuzz 输入空间通常包含预期输入空间，但这并非必要——只需 fuzz 输入空间包含至少一个不在预期输入空间中的输入即可。第二，实际操作中 fuzzing 几乎总是会运行多次迭代；因此，若在上述定义中写作“重复执行”也基本是准确的。第三，采样过程并不一定是随机的，如我们将在 §5 中看到的。

Fuzz 测试是一种利用 fuzzing 的软件测试技术。为了与其他测试形式区分开来，并向我们认为其最重要的目的致敬，我们特意将其定义为具有发现与安全相关的漏洞（包括程序崩溃）的特定目标。此外，我们还定义了 fuzzer 和 fuzz campaign，这两者都是 fuzz 测试中的常用术语：

定义 2（Fuzz 测试）：Fuzz 测试是使用 fuzzing 测试 PUT 是否违反安全策略的过程。

定义 3（Fuzzer）：Fuzzer 是一种对 PUT 进行 fuzz 测试的程序。

定义 4（Fuzz Campaign）：Fuzz campaign 是在特定安全策略下，使用 fuzzer 对 PUT 进行的特定执行过程。

通过 fuzz campaign 运行 PUT 的目标是发现违反指定安全策略的漏洞 [26]。例如，早期 fuzzer 使用的安全策略仅检测生成的输入（测试用例）是否导致 PUT 崩溃。然而，fuzz 测试实际上可以用于测试任何从执行中可观察到的安全策略，即 EM-enforceable 策略 [183]。决定执行是否违反安全策略的具体机制被称为漏洞判定器（bug oracle）。

定义 5（漏洞判定器）：漏洞判定器是一种程序（可能是 fuzzer 的一部分），用于确定 PUT 的某次执行是否违反特定的安全策略。

我们简单地将 fuzzer 实现的算法称为其“fuzz 算法”。几乎所有 fuzz 算法都依赖于一些参数，这些参数超出了 PUT 的路径范围。每一种具体的参数设置称为 fuzz 配置：

定义 6（Fuzz 配置）：Fuzz 配置是 fuzz 算法中控制 fuzz 行为的参数值。

这一 fuzz 配置的定义是广泛的。需要注意的是，fuzz 配置中的值类型取决于 fuzz 算法的类型。例如，一个发送随机字节流到 PUT 的 fuzz 算法 [152] 有一个简单的配置空间 {(PUT)}。另一方面，复杂的 fuzzer 包含可接受一组配置并随时间演化这组配置的算法——这包括添加和移除配置。例如，CERT BFF [49] 在 campaign 过程中会动态调整变异率和种子，因此其配置空间为 {(PUT, s1, r1), (PUT, s2, r2), ...}。种子（seed）是一个（通常结构良好的）用于生成测试用例并加以修改的 PUT 输入。fuzzer 通常维护一个种子集合，而一些 fuzzer 会随着 fuzz campaign 的进行演化这个集合。这个集合被称为种子池（seed pool）。最后，fuzzer 能够在每个配置中存储一些数据。例如，基于覆盖的 fuzzer 可能会在每个配置中存储所达到的覆盖范围。

论文选择标准

为了实现明确的研究范围，我们选择了从 2008 年 1 月到 2019 年 2 月 期间，在四大主要安全会议和三大主要软件工程会议的最近论文集中，收录所有关于模糊测试（fuzzing）的论文。按字母顺序排列，前者包括：
(i) ACM 计算机与通信安全会议（ACM Conference on Computer and Communications Security，CCS），
(ii) IEEE 安全与隐私研讨会（IEEE Symposium on Security and Privacy，S&P），
(iii) 网络与分布式系统安全研讨会（Network and Distributed System Security Symposium，NDSS），以及
(iv) USENIX 安全研讨会（USENIX Security Symposium，USEC）；
后者包括：
(i) ACM 软件工程基础国际研讨会（ACM International Symposium on the Foundations of Software Engineering，FSE），
(ii) IEEE/ACM 自动化软件工程国际会议（IEEE/ACM International Conference on Automated Software Engineering，ASE），以及
(iii) 国际软件工程会议（International Conference on Software Engineering，ICSE）。

1 2 3 4 5 6 7 8 9 10 11 12

Input: C, tlimit Output: B // a finite set of bugs B <- ? C <- PREPROCESS(C) while telapsed < tlimit ^ CONTINU E(C) do     conf <- SCHEDUL E(C, telapsed, tlimit)     tcs <- INPUTGEN(conf)     // Obug is embedded in a fuzzer     B′, execinfos <- INPUTEVAL(conf, tcs, Obug)     C <- CONFUPDATE(C, conf, execinfos)     B <- B [ B′ return B

对于出现在其他会议或媒介中的论文，我们根据其相关性自行判断是否纳入。

正如 §2.1 中所提到的，模糊测试与软件测试的区别仅在于模糊测试与安全相关。从理论上讲，专注于安全漏洞并不意味着测试过程会有其他不同，除了缺陷检测机制（bug oracle）的选择。然而，在实践中，使用的技术往往有所不同。在设计测试工具时，通常假定可以访问源代码，并对被测程序（Program Under Test，PUT）有一定的了解。这些假设通常会推动测试工具的发展，使其与模糊测试工具具有不同的特性，而模糊测试工具更可能被 PUT 的开发者以外的人员使用。然而，这两个领域仍然紧密相关。因此，当我们不确定是否将某篇论文归类为“模糊测试”并将其纳入本次研究时，我们遵循一个简单的经验法则：如果论文中出现了“fuzz”一词，我们就将其纳入。

模糊测试算法

我们提出了一个通用的模糊测试算法（算法 1），假设它已在一个模型模糊测试工具中实现。该算法足够通用，可以涵盖现有的模糊测试技术，包括 §2.4 中定义的黑盒、灰盒和白盒模糊测试。算法 1 接收一组模糊配置 C 和一个超时时间 tlimit 作为输入，并输出一组发现的漏洞 B。它由两部分组成：第一部分是 PREPROCESS 函数，在模糊测试活动开始时执行；第二部分是一个循环，包含五个函数：SCHEDULE、INPUTGEN、INPUTEVAL、CONFUPDATE 和 CONTINUE。每次循环执行称为一次模糊测试迭代（fuzz iteration），而每次 INPUTEVAL 对某个测试用例运行 PUT 称为一次模糊测试运行（fuzz run）。需要注意的是，并非所有模糊测试工具都实现了这五个函数。例如，为了模拟 Radamsa [102]，其从不更新模糊配置集，因此 CONFUPDATE 始终返回当前的配置集，不作修改。

PREPROCESS (C) → C

用户向 PREPROCESS 提供一组模糊配置作为输入，函数返回可能被修改的模糊配置集。根据模糊算法的不同，PREPROCESS 可以执行各种操作，例如在 PUT 中插入插桩代码，或者测量种子文件的执行速度。详见 §3。

SCHEDULE (C, telapsed, tlimit) → conf

SCHEDULE 接收当前的模糊配置集 C、当前时间 telapsed 和超时时间 tlimit 作为输入，并选择一个模糊配置用于当前的模糊测试迭代。详见 §4。

INPUTGEN (conf) → tcs

INPUTGEN 接收一个模糊配置 conf 作为输入，并返回一组具体的测试用例 tcs 作为输出。在生成测试用例时，INPUTGEN 使用 conf 中的特定参数。一些模糊测试工具使用 conf 中的种子生成测试用例，而其他工具则可能使用模型或文法作为参数。详见 §5。

INPUTEVAL (conf, tcs, Obug) → B′, execinfos

INPUTEVAL 接收一个模糊配置 conf、一组测试用例 tcs 和一个漏洞检测机制（bug oracle）Obug 作为输入。它对 tcs 中的测试用例运行 PUT，并使用 Obug 检查执行是否违反了安全策略。随后，它输出发现的漏洞集 B′ 以及每次模糊测试运行的相关信息 execinfos，这些信息可能会用于更新模糊配置。我们假设 Obug 嵌入在我们的模型模糊测试工具中。详见 §6。

CONFUPDATE (C, conf, execinfos) → C

CONFUPDATE 接收一组模糊配置 C、当前的模糊配置 conf 和每次模糊测试运行的相关信息 execinfos 作为输入，并可能更新模糊配置集 C。例如，许多灰盒模糊测试工具会根据 execinfos 减少 C 中的模糊配置数量。详见 §7。

CONTINUE (C) → {True, False}

CONTINUE 接收一组模糊配置 C 作为输入，并输出一个布尔值，指示是否应进行新的模糊测试迭代。该函数对于模拟白盒模糊测试工具非常有用，因为白盒模糊测试工具可以在没有更多路径可发现时终止。

模糊测试工具的分类

在本文中，我们根据模糊测试工具（fuzzer）在每次模糊测试运行中观察语义的粒度将其分为三类。这三类分别是黑盒、灰盒和白盒模糊测试工具，定义如下。需要注意，这种分类不同于传统软件测试中的分类，在传统软件测试中，主要只有两大类（黑盒测试和白盒测试）[158]。正如我们将在 §2.4.3 中讨论的，灰盒模糊测试是白盒模糊测试的一种变体，但它只能从每次模糊测试运行中获取部分信息。

黑盒模糊测试工具

“黑盒”一词通常用于软件测试 [158]，[32] 和模糊测试中，表示这些技术无法看到被测程序（PUT，Program Under Test）的内部，仅能观察其输入/输出行为，将其视为一个黑盒。在软件测试中，黑盒测试也被称为基于输入输出的测试（IO-driven testing）或数据驱动测试（data-driven testing）[158]。大多数传统的模糊测试工具 [13]，[103]，[49]，[6]，[50] 都属于这一类别。一些现代模糊测试工具，例如 funfuzz [187] 和 Peach [76]，虽然会利用输入的结构信息生成更有意义的测试用例，但仍保持不检查被测程序的特性。类似的直觉也被用于自适应随机测试（adaptive random testing）[57]。

白盒模糊测试工具

在另一个极端，白盒模糊测试 [90] 通过分析被测程序的内部及其执行时收集的信息来生成测试用例。因此，白盒模糊测试工具能够系统地探索被测程序的状态空间。“白盒模糊测试”一词由 Godefroid 于 2007 年首次引入 [87]，指动态符号执行（DSE，Dynamic Symbolic Execution），这是一种符号执行（symbolic execution）的变体 [39]，[126]，[108]。在动态符号执行中，符号执行与具体执行同时进行，具体的程序状态被用于简化符号约束，例如具体化系统调用。因此，动态符号执行通常被称为“混合符号测试”（concolic testing，即 concrete + symbolic）[191]，[89]。

此外，白盒模糊测试也用于描述那些采用污点分析（taint analysis）的模糊测试工具 [84]。白盒模糊测试的开销通常比黑盒模糊测试高得多。这部分是因为动态符号执行的实现 [90]，[46]，[25] 通常需要使用动态插桩（dynamic instrumentation）和 SMT 求解器 [155]。虽然动态符号执行是一个活跃的研究领域 [90]，[88]，[38]，[172]，[112]，但许多动态符号执行工具并不是白盒模糊测试工具，因为它们的目标并不是发现安全漏洞。因此，本文没有对动态符号执行工具进行全面的综述，而是建议读者参考最近的综述论文 [17]，[185]，以了解动态符号执行在非安全应用中的更多信息。

灰盒模糊测试工具

一些模糊测试工具 [78]，[68]，[205] 采用了一种折中的方法，被称为灰盒模糊测试。一般来说，灰盒模糊测试工具能够获取被测程序及其执行的一些内部信息。与白盒模糊测试不同，灰盒模糊测试不会推理被测程序的完整语义；相反，它们可能会对被测程序进行轻量级的静态分析和/或收集其执行的动态信息，例如代码覆盖率。

灰盒模糊测试工具依赖于近似的、不完美的信息，以便提高速度并能够测试更多的输入。尽管安全专家之间通常存在共识，但黑盒、灰盒和白盒模糊测试之间的界限并不总是清晰的。黑盒模糊测试工具可能会收集模糊测试运行的一些信息，而白盒模糊测试工具通常也会使用一些近似方法。在对本综述中的模糊测试工具进行分类时，特别是在 表 1 中，我们根据最佳判断进行了划分。

灰盒模糊测试工具的一个早期示例是 EFS [68]，它利用每次模糊测试运行中收集的代码覆盖率，通过进化算法生成测试用例。Randoop [166] 也使用了类似的方法，尽管它并不以发现安全漏洞为目标。现代模糊测试工具如 AFL [231] 和 VUzzer [176] 是这一类别的典型代表。

模糊测试工具的谱系与概览

图 1（第 5 页） 按时间顺序展示了我们对现有模糊测试工具的分类。从 Miller 等人 [152] 的开创性工作开始，我们手动选择了那些要么发表在主要会议上，要么获得了超过 100 个 GitHub 星标的流行模糊测试工具，并将它们的关系以图的形式展示出来。黑盒模糊测试工具位于图的左半部分，灰盒和白盒模糊测试工具位于图的右半部分。此外，模糊测试工具根据被测程序的输入类型进一步细分：文件、网络、UI、Web、内核 I/O，或线程（用于并发模糊测试工具）。

表 1（第 6 页） 则详细总结了 图 1 中最著名模糊测试工具所采用的技术。由于篇幅限制，我们不得不省略了一些 图 1 中的模糊测试工具。每个模糊测试工具的总结基于其对我们模型中五个功能的实现，以及一个提供其他细节的杂项部分。我们在下文中描述了每一列所代表的属性。

第一列（反馈收集粒度）表明模糊测试工具是黑盒（⚪）、白盒（#）还是灰盒（H#）。如果一个模糊测试工具有两个阶段且使用了不同类型的反馈收集，则会显示两个圆圈。例如，SymFuzz [52] 在一个预处理阶段运行白盒分析，以优化后续黑盒测试的性能（⚪ + #），而混合模糊测试工具（如 Driller [200]）在白盒和灰盒模糊测试之间交替运行（H# + #）。

第二列显示模糊测试工具的源代码是否公开。第三列表示模糊测试工具是否需要被测程序的源代码才能运行。第四列指出模糊测试工具是否支持内存内模糊测试（参见 §3.1.2）。第五列显示模糊测试工具是否能够推断模型（参见 §5.1.2）。第六列表明模糊测试工具是否在 预处理 阶段执行静态或动态分析。

第七列指示模糊测试工具是否支持处理多个种子并进行调度。变异 列说明模糊测试工具是否通过输入变异生成测试用例。我们用 H# 表示根据执行反馈指导输入变异的模糊测试工具。基于模型 列表示模糊测试工具是否基于模型生成测试用例。基于约束 列则表示模糊测试工具是否执行符号分析以生成测试用例。

污点分析 列表示模糊测试工具是否利用污点分析来指导测试用例的生成过程。在 输入评估 部分的两列中，分别显示模糊测试工具是否通过堆栈哈希或代码覆盖率执行崩溃分析。

配置更新（CONFUPDATE） 部分的第一列表明模糊测试工具是否在更新配置时演化种子池，例如向种子池中添加新种子（参见 §7.1）。第二列显示模糊测试工具是否在线学习输入模型。最后，第三列说明哪些模糊测试工具会从种子池中移除种子（参见 §7.2）。

预处理（PREPROCESS）

一些模糊测试工具会在第一次模糊测试迭代之前修改初始的模糊配置集合。这种预处理通常用于对被测试程序（Program Under Test，PUT）进行插桩（instrumentation），筛选出潜在的冗余配置（即“种子选择” [177]），修剪种子，以及生成驱动程序应用程序。正如将在第5.1.1节（第9页）详细介绍的，PREPROCESS 还可以用于为后续的输入生成（INPUTGEN）准备模型。

插桩（Instrumentation）

与黑盒模糊测试工具不同，灰盒和白盒模糊测试工具可以对被测试程序（PUT）进行插桩，以便在运行输入评估（INPUTEVAL）时收集执行反馈（见第6节），或者在运行时模糊测试内存内容。插桩收集的信息量决定了模糊测试工具的“颜色”（即黑盒、白盒或灰盒）。尽管还有其他方法可以获取被测试程序内部的信息（例如处理器跟踪或系统调用使用情况 [204], [92]），但插桩通常是收集最有价值反馈的方法。

将显著的模糊测试工具的传承关系追溯到 Miller 等人的开创性工作。同一行中的每个节点代表同一年出现的一组模糊测试工具。从 X 到 Y 的实线箭头表示 Y 引用了、参考了或以其他方式使用了 X 的技术。

按照模糊测试工具的插桩粒度和名称分类的概览； 表示描述该工作的论文已发表。黑代表黑盒，灰代表灰盒，白代表白盒，✝️代表基于AFL开发而来

程序插桩可以是静态的，也可以是动态的——前者发生在被测试程序运行之前（PREPROCESS），而后者发生在被测试程序运行时（INPUTEVAL）。为了方便阅读，我们在本节中总结了静态和动态插桩的内容。

静态插桩 通常在编译时对源代码或中间代码进行。由于它发生在运行时之前，通常比动态插桩带来的运行时开销更小。如果被测试程序依赖于一些库，则需要将这些库单独插桩，通常需要使用相同的插桩方式重新编译它们。除了基于源代码的插桩，研究人员还开发了基于二进制的静态插桩（即二进制重写）工具 [238], [132], [77]。

尽管动态插桩的开销高于静态插桩，但它的优势在于可以轻松地对动态链接库进行插桩，因为插桩是在运行时进行的。有几种知名的动态插桩工具，例如 DynInst [173]、DynamoRIO [42]、Pin [144]、Valgrind [163] 和 QEMU [33]。

一个模糊测试工具可以支持多种类型的插桩。例如，AFL 支持通过修改的编译器对源代码进行静态插桩，或借助 QEMU [33] 对二进制文件进行动态插桩。当使用动态插桩时，AFL 可以插桩 (1) 被测试程序本身的可执行代码（这是默认设置），或 (2) 被测试程序和任何外部库的可执行代码（使用 AFL_INST_LIBS 选项）。第二种选项——插桩所有遇到的代码，可以为外部库代码提供覆盖信息，从而提供更完整的覆盖范围。然而，这也会促使 AFL 模糊测试外部库函数中的其他路径。

执行反馈（Execution Feedback）

灰盒模糊测试工具通常通过执行反馈来进化测试用例。AFL 及其衍生工具通过在被测试程序中插桩每个分支指令来计算分支覆盖。然而，它们将分支覆盖信息存储在一个位向量中，这可能导致路径冲突。CollAFL [83] 最近通过引入一种新的路径敏感哈希函数解决了这个问题。同时，LibFuzzer [7] 和 Syzkaller [216] 使用节点覆盖作为它们的执行反馈。而 Honggfuzz [204] 允许用户选择执行反馈的类型。

内存内模糊测试（In-Memory Fuzzing）

在测试大型程序时，有时希望仅模糊测试被测试程序的一部分，而不为每次模糊迭代重新启动一个进程，以最小化执行开销。例如，复杂的（如 GUI）应用程序在接受输入前通常需要几秒钟的处理时间。对这些程序进行模糊测试的一种方法是，在 GUI 初始化后对被测试程序进行快照。然后，在测试新的测试用例时，可以恢复内存快照，再将新的测试用例直接写入内存并执行。同样的直觉也适用于需要大量客户端和服务器交互的网络应用程序的模糊测试。这种技术被称为内存内模糊测试 [104]。

例如，GRR [211], [92] 在加载任何输入字节之前创建快照，这样可以跳过不必要的启动代码。AFL 还使用了一个分叉服务器（fork server）来避免一些进程启动成本。尽管它与内存内模糊测试有相同的动机，但分叉服务器会为每次模糊迭代派生一个新进程（见第6节）。

一些模糊测试工具 [7], [231] 在函数上执行内存内模糊测试，而不在每次迭代后恢复被测试程序的状态。我们将这种技术称为内存内 API 模糊测试。例如，AFL 提供了一个称为持久模式（persistent mode）的选项，在不重启进程的情况下，在循环中反复执行内存内 API 模糊测试。在这种情况下，AFL 会忽略函数在同一执行中被多次调用可能造成的副作用。

尽管高效，内存内 API 模糊测试会带来不可靠的模糊测试结果：通过内存内模糊测试发现的漏洞（或崩溃）可能无法重现，因为 (1) 构造目标函数的有效调用上下文并不总是可行的，以及 (2) 存在无法跨多次函数调用捕获的副作用。需要注意的是，内存内 API 模糊测试的可靠性主要取决于入口函数，而找到这样的函数是一项具有挑战性的任务。

线程调度

竞争条件（Race Condition）相关的错误很难触发，因为它们依赖于非确定性行为，这些行为可能只会偶尔发生。然而，通过显式控制线程调度的方式进行插装（Instrumentation），可以触发不同的非确定性程序行为 [189]、[190]、[169]、[116]、[131]、[47]、[181]。现有研究表明，即使是随机调度线程的方式也能有效发现竞争条件错误 [189]。

种子选择

回顾 §2 的内容，模糊测试工具（Fuzzers）接收一组模糊测试配置，这些配置控制模糊测试算法的行为。然而，模糊测试配置中的某些参数（例如基于变异的模糊测试工具的种子）具有较大的取值范围。例如，假设分析人员正在对一个接受 MP3 文件作为输入的 MP3 播放器进行模糊测试。有效 MP3 文件的数量是无限的，这引出了一个自然的问题：我们应该使用哪些种子进行模糊测试？缩小初始种子集合大小的问题被称为种子选择问题 [177]。

针对种子选择问题，有多种方法和工具可以解决 [177]、[76]。一种常见的方法是找到一个最小化的种子集合（minset），使其最大化覆盖率指标，例如节点覆盖率。举例来说，假设当前的配置集合 C 包含两个种子 s1 和 s2，它们分别覆盖以下地址范围：{s1 → {10, 20}, s2 → {20, 30}}。如果我们有一个第三个种子 s3 → {10, 20, 30}，且其执行速度与 s1 和 s2 相当，那么可以认为选择 s3 进行模糊测试更为合理，因为它以一半的执行时间测试了更多的程序逻辑。这种直觉得到了 Miller 的报告 [153] 的支持，该报告显示，代码覆盖率每增加 1%，发现错误的比例增加了 0.92%。如 §7.2 所述，这一步也可以作为 CONFUPDATE 的一部分，这对可以在整个模糊测试过程中引入新种子的模糊测试工具非常有用。

模糊测试工具在实践中使用多种不同的覆盖率指标。例如，AFL 的最小化种子集合是基于分支覆盖率的，并在每个分支上使用对数计数器。其背后的逻辑是，只有当分支计数的数量级不同的时候，才认为它们是不同的。而 Honggfuzz [204] 基于以下指标计算覆盖率：执行的指令数、执行的分支数以及唯一基本块的数量。这种指标允许模糊测试工具将更长的执行路径纳入最小化种子集合，这有助于发现拒绝服务漏洞或性能问题。

种子修剪

较小的种子通常会消耗更少的内存并提高吞吐量。因此，一些模糊测试工具会在对种子进行模糊测试之前尝试减小种子的大小，这被称为种子修剪。种子修剪可以在主模糊测试循环之前的 PREPROCESS 阶段进行，也可以作为 CONFUPDATE 的一部分。

一个使用种子修剪的典型模糊测试工具是 AFL [231]，它利用其代码覆盖率插装功能，迭代地移除种子的一部分，只要修改后的种子仍然能达到相同的覆盖率即可。同时，Rebert 等人 [177] 报告称，他们的最小化种子集合算法（优先选择较小的种子）相比随机选择种子，发现的独特错误更少。对于模糊测试 Linux 系统调用处理程序的特定场景，MoonShine [167] 扩展了 syzkaller [216]，从而在保持系统调用之间依赖关系的同时减少种子的大小，这些依赖关系是通过静态分析检测到的。

准备驱动应用程序

当直接对目标程序（PUT，Program Under Test）进行模糊测试困难时，准备一个用于模糊测试的驱动程序是有意义的。这个过程在实践中基本是手动完成的，尽管它通常只需要在模糊测试活动的开始阶段完成一次。例如，当目标是一个库时，我们需要准备一个调用该库中函数的驱动程序。同样，内核模糊测试工具可能通过模糊测试用户态应用程序来测试内核 [125]、[165]、[31]。IoTFuzzer [54] 通过让驱动程序与对应的智能手机应用程序通信来针对 IoT 设备进行模糊测试。

调度

在模糊测试中，调度指的是为下一次模糊测试迭代选择一个模糊测试配置。如 §2.1 所述，每个配置的内容取决于模糊测试工具的类型。对于简单的模糊测试工具来说，调度可能非常简单——例如，zzuf [103] 在默认模式下仅允许一个配置，因此无需做出任何决策。但对于更高级的模糊测试工具（如 BFF [49] 和 AFLFast [37]），其成功的一个主要因素是其创新的调度算法。本节将仅讨论黑盒和灰盒模糊测试的调度算法；白盒模糊测试的调度需要一个独特的符号执行器设置，读者可参考其他文献 [38]。

模糊测试配置调度（FCS）问题

调度的目标是分析当前可用的配置信息，选择一个最可能带来最优结果的配置，例如发现最多的独特错误或最大化生成输入集合的覆盖率。从根本上说，每种调度算法都面临着相同的探索与利用冲突——时间可以用来收集每个配置的更准确信息以指导未来的决策（探索），也可以用来模糊测试当前被认为更可能带来有利结果的配置（利用）。Woo 等人 [225] 将这种固有冲突称为模糊测试配置调度（FCS）问题。

在我们的模型模糊测试工具中（算法 1），函数 SCHEDULE 根据 (i) 当前的模糊测试配置集合 C，(ii) 已经过的时间 telapsed，以及 (iii) 总时间预算 tlimit 来选择下一次模糊测试迭代的配置。这个配置随后会被用于下一次模糊测试迭代。需要注意的是，SCHEDULE 仅负责决策，其决策所基于的信息由 PREPROCESS 和 CONFUPDATE 获取，这些过程会将这些知识加入到 C 中。

黑盒 FCS 算法

在黑盒设置中，FCS（Fuzzing Configuration Scheduling，模糊测试配置调度）算法唯一可以利用的信息是某个配置的模糊测试结果——即使用该配置找到的崩溃和漏洞数量，以及在其上花费的时间。Householder 和 Foote [107] 最早研究了如何利用这些信息用于 CERT BFF 黑盒变异模糊测试器 [49]。他们假设，观察到成功率更高（#bugs / #runs）的配置应该被优先选择。实际上，在将 BFF 中的均匀采样调度算法替换后，他们在对 ffmpeg 进行 500 万次运行的实验中，观察到独特崩溃数量增加了 85%，展示了更高级 FCS 算法的潜在优势。

不久之后，Woo 等人 [225] 在多个方面改进了上述想法。首先，他们将黑盒变异模糊测试的数学模型从一系列伯努利试验 [107] 精炼为未知权重的加权优惠券收集问题（WCCP/UW）。前者假设每个配置具有固定的最终成功概率，并随着时间的推移学习该概率；而后者则显式地对该概率的上限进行维护，并随着时间衰减。其次，WCCP/UW 模型自然引导 Woo 等人研究多臂老虎机（MAB）问题的算法，这是应对决策科学中探索与利用冲突的一种流行形式化方法 [34]。通过这种方法，他们设计了可以准确利用尚未被证实衰减的配置的 MAB 算法。第三，他们观察到，在其他条件相同的情况下，更快的配置可以让模糊测试器通过以下方式获益：要么通过该配置收集更多的独特漏洞，要么更快降低其未来成功概率的上限。这启发了他们通过所花费的时间来归一化某个配置的成功概率，从而使更快的配置更具吸引力。第四，他们将 BFF 中的模糊测试运行编排从每次选择固定数量的模糊测试迭代（BFF 的“epoch”概念）改为每次选择固定的时间。通过这一改变，BFF 不再被迫在慢配置上花费更多时间才能重新选择配置。结合以上改进，评估结果 [225] 显示，使用相同时间的情况下，BFF 中发现的独特漏洞数量增加了 1.5 倍。

灰盒 FCS 算法

在灰盒设置中，FCS 算法可以选择使用更丰富的关于每个配置的信息，例如模糊测试某个配置时的覆盖率。AFL [231] 是该类别的先驱，其基于一种进化算法（Evolutionary Algorithm, EA）。直观上，EA 维护一个配置的种群，每个配置都具有某种“适应度”（fitness）值。EA 选择适应性较高的配置，并对其应用诸如变异和重组的遗传变换，以生成后代，这些后代可能随后成为新配置。其假设是，这些生成的配置更有可能是“适应”的。

要理解 EA 背景下的 FCS，需要定义以下内容：(i) 什么使得一个配置具有适应性；(ii) 如何选择配置；(iii) 如何使用选出的配置。简单来说，对于那些执行控制流边缘的配置，AFL 认为包含最快且最小输入的配置是“适应”的（在 AFL 中称为“favorite”）。AFL 维护了一个配置队列，从中选择下一个适应性配置，基本上将该队列视为循环队列。一旦选择了某个配置，AFL 对其进行固定次数的模糊测试。从 FCS 的角度来看，对快速配置的偏好与黑盒设置 [225] 中的行为是一致的。

最近，AFLFast 被 Böhme 等人 [37] 在上述三个方面进行了改进。首先，AFLFast 添加了两个覆盖规则来决定某个输入是否能成为“favorite”：(i) 在执行某个控制流边缘的配置中，AFLFast 偏好被选择次数最少的配置。这会在执行该边缘的配置之间进行轮换，从而增加探索。(ii) 如果在 (i) 中出现平局，AFLFast 偏好执行路径被覆盖次数最少的配置。这会增加对稀有路径的测试，从而可能揭示更多未观察到的行为。其次，AFLFast 放弃了 AFL 中的循环选择，而是基于优先级选择下一个适应性配置。具体来说，一个适应性配置的优先级高于另一个配置，如果它被选择的次数更少，或者在平局时，它执行了一条被覆盖次数较少的路径。与第一项改动的精神一致，这增加了对适应性配置的探索以及对稀有路径的测试。第三，AFLFast 根据一个功率调度策略（power schedule）来确定对选中配置进行模糊测试的次数。AFLFast 中的 FAST 功率调度策略从一个较小的“能量”值开始，以确保初始阶段对配置的探索，并以指数级递增到一定限制，以快速确保足够的利用。此外，它还通过生成的输入数量对能量进行归一化，这些输入执行了相同的路径，从而促进对较少测试的配置的探索。这些改进的总体效果非常显著——在 24 小时的评估中，Böhme 等人发现 AFLFast 发现了 AFL 未能发现的 3 个漏洞，并且在 AFL 和 AFLFast 都能发现的另外 6 个漏洞上，AFLFast 平均快了 7 倍。

AFLGo [36] 通过修改优先级分配进一步扩展了 AFLFast，以便针对特定程序位置。Hawkeye [53] 通过在种子调度和输入生成中利用静态分析，进一步改进了定向模糊测试。FairFuzz [136] 通过为种子和稀有分支的每对组合引入变异掩码，引导测试活动以执行稀有分支。QTEP [218] 使用静态分析推断二进制文件中更可能存在问题的部分，并优先选择覆盖这些部分的配置。

输入生成

由于测试用例的内容直接决定了是否触发漏洞，输入生成技术自然成为模糊测试设计中最具影响力的决策之一。传统上，模糊测试器被划分为基于生成或基于变异的模糊测试器 [203]。基于生成的模糊测试器根据描述被测程序（PUT）期望的输入的给定模型生成测试用例。本文将此类模糊测试器称为基于模型的模糊测试器。而基于变异的模糊测试器通过变异给定的种子输入来生成测试用例。基于变异的模糊测试器通常被视为“无模型”的，因为种子只是示例输入，即使数量很多，也无法完全描述被测程序的预期输入空间。在本节中，我们基于底层测试用例生成机制（INPUTGEN）解释并分类模糊测试器使用的各种输入生成技术。

基于模型（基于生成）的模糊器

基于模型的模糊器根据给定模型生成测试用例。模型生成测试用例。可能接受的输入或执行，如精确描述输入格式的语法输入格式的语法或不太精确的约束条件，如确定文件类型的magic值识别文件类型。

预定义模型

一些模糊测试工具使用可由用户配置的模型。例如，Peach [76]、PROTOS [120] 和 Dharma [3] 接受用户提供的规范作为输入。Autodafé [214]、Sulley [16]、SPIKE [13] 和 SPIKEfile [202] 提供了 API，允许分析人员创建自己的输入模型。Tavor [240] 同样接受用扩展巴科斯-瑙尔范式（EBNF）编写的输入规范，并生成符合相应语法的测试用例。同样，网络协议模糊测试工具如 PROTOS [120]、SNOOZE [29]、KiF [12] 和 T-Fuzz [114] 也接受用户提供的协议规范。内核 API 模糊测试工具 [115]、[216]、[157]、[162]、[221] 以系统调用模板的形式定义输入模型。这些模板通常指定系统调用所需输入的参数数量和类型。在 Koopman 等人的开创性工作 [128] 中，首次提出了在内核模糊测试中使用模型的想法，他们通过一组有限的手工选择的系统调用测试用例比较了操作系统的健壮性。Nautilus [22] 使用基于语法的输入生成进行通用模糊测试，同时利用其语法进行种子修剪（参见 §3.3）。

其他基于模型的模糊测试工具针对特定语言或语法，其语言模型内置于模糊测试工具本身。例如，cross fuzz [232] 和 DOMfuzz [187] 随机生成文档对象模型（DOM）对象。同样，jsfunfuzz [187] 基于其自身的语法模型生成随机但语法正确的 JavaScript 代码。QuickFuzz [94] 在生成测试用例时利用了描述文件格式的现有 Haskell 库。一些网络协议模糊测试工具如 Frankencerts [41]、TLS-Attacker [195]、tlsfuzzer [124] 和 llfuzzer [198] 针对特定的网络协议（如 TLS 和 NFC）设计了相应的模型。Dewey 等人 [69]、[70] 提出了一种通过约束逻辑编程生成不仅语法正确且语义多样的测试用例的方法。LangFuzz [105] 通过解析输入的种子集合生成代码片段，随机组合这些片段并用其突变种子，从而生成测试用例。由于提供了语法，LangFuzz 始终生成语法正确的代码，并已被应用于 JavaScript 和 PHP。BlendFuzz [229] 基于与 LangFuzz 类似的理念，但针对的是 XML 和正则表达式解析器。

推断模型

近年来，与其依赖预定义或用户提供的模型，不如推断模型的方法逐渐受到关注。尽管在自动输入格式和协议逆向工程方面有大量研究发表 [66]、[45]、[141]、[63]、[28]，但只有少数模糊测试工具利用了这些技术。与插桩（参见 §3.1）类似，模型推断可以发生在 预处理阶段（PREPROCESS） 或 配置更新阶段（CONFUPDATE）。

预处理阶段中的模型推断

一些模糊测试工具在预处理阶段推断模型。例如，TestMiner [67] 搜索目标程序（PUT）中可用的数据（如字面值）以预测合适的输入。Skyfire [217] 通过给定一组种子和语法，采用数据驱动的方法推断概率上下文敏感语法，然后用其生成新种子集。与以往工作不同，它专注于生成语义有效的输入。IMF [99] 通过分析系统 API 日志学习内核 API 模型，并生成调用 API 序列的 C 代码。CodeAlchemist [100] 将 JavaScript 代码分解为“代码砖块”，并计算汇编约束，这些约束描述了不同砖块何时可以结合或合并以生成语义有效的测试用例。这些约束通过静态分析和动态分析计算得出。Neural [62] 和 Learn&Fuzz [91] 使用基于神经网络的机器学习技术从给定的测试文件集中学习模型，并从推断的模型生成测试用例。Liu 等人 [142] 提出了类似的方法，但专门针对文本输入。

配置更新阶段中的模型推断

其他模糊测试工具可能在每次模糊测试迭代后更新它们的模型。例如，PULSAR [85] 从一组由程序生成的网络数据包中自动推断网络协议模型。学习到的网络协议随后用于模糊测试程序。PULSAR 在内部构建了一个状态机，并映射哪个消息标记与哪个状态相关联。此信息随后用于生成覆盖状态机更多状态的测试用例。Doupé 等人 [73] 提出了一种通过观察 I/O 行为推断 Web 服务状态机的方法，随后将推断的模型用于扫描 Web 漏洞。Ruiter 等人 [180] 的工作与之类似，但针对的是 TLS，并基于 LearnLib [174] 实现。GLADE [30] 从一组 I/O 样本中合成上下文无关语法，并使用推断的语法模糊测试目标程序（PUT）。最后，go-fuzz [215] 是一个灰盒模糊测试工具，它为添加到种子池中的每个种子构建一个模型。此模型用于从该种子生成新的输入。

编码器模型

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

无模型（基于变异）的模糊测试工具

经典的随机测试 [20]、[98] 在生成满足特定路径条件的测试用例方面效率较低。例如，假设有一个简单的 C 语句：if (input == 42)。如果 input 是一个 32 位整数，随机猜测正确输入值的概率是 1/2³²。当我们考虑结构化输入（如 MP3 文件）时，情况会更糟。随机测试生成一个有效 MP3 文件作为测试用例的可能性极低。结果是 MP3 播放器在解析阶段通常会拒绝随机测试生成的测试用例，而无法到达程序的更深层部分。

这一问题促使人们使用基于种子的输入生成方法以及白盒输入生成方法（参见 §5.3）。大多数无模型模糊测试工具使用种子（即目标程序的输入）来生成测试用例，通过修改种子生成新的输入。种子通常是目标程序支持的类型的结构化输入：文件、网络数据包或一系列用户界面事件。通过仅变异有效文件的一部分，往往可以生成一个大体有效但包含异常值的新测试用例，从而触发目标程序的崩溃。以下描述了常用的种子变异方法。

位翻转（Bit-Flipping）

位翻转是一种常见技术，被许多无模型（modelless）模糊测试工具使用 [231], [204], [103], [6], [102]。一些模糊测试工具简单地翻转固定数量的位，而另一些则随机决定要翻转的位数。为了随机变异种子（seed），某些模糊测试工具使用一个用户可配置的参数，称为变异比率（mutation ratio），它决定了在一次 INPUTGEN 执行中要翻转的位位置的数量。假设某个模糊测试工具希望从一个 N 位种子中随机翻转 K 位，则模糊测试工具的变异比率为 K/N。

SymFuzz [52] 表明，模糊测试的性能对变异比率非常敏感，没有一个统一的比率可以适用于所有被测程序（PUT）。针对如何找到一个合适的变异比率，有多种方法。BFF [49] 和 FOE [50] 对每个种子使用一组按指数比例缩放的变异比率，并为统计上更有效的变异比率分配更多的迭代次数 [107]。SymFuzz [52] 则利用白盒程序分析为每个种子推断出一个合适的变异比率。

算术变异（Arithmetic Mutation）

AFL [231] 和 honggfuzz [204] 包含另一种变异操作，它们将选定的字节序列视为一个整数，并对该值执行简单的算术运算。计算出的新值将替换选定的字节序列。关键的直觉在于通过一个较小的数值来限定变异的影响。例如，AFL 从种子中选择一个 4 字节的值，并将其视为整数 i。然后，它用 i ± r 替换种子中的值，其中 r 是一个随机生成的小整数。r 的范围取决于模糊测试工具，并且通常是用户可配置的。在 AFL 中，默认范围为：0 ≤ r < 35。

基于块的变异（Block-based Mutation）

基于块的变异方法有多种，其中“块”是指种子中的一个字节序列：

1. 在种子的随机位置插入一个随机生成的块 [231], [7]；
2. 从种子中随机删除一个选定的块 [231], [102], [204], [7]；
3. 用随机值替换种子中随机选定的块 [231], [204], [102], [7]；
4. 随机排列一个块序列的顺序 [102], [7]；
5. 通过附加一个随机块来调整种子的大小 [204]；
6. 从一个种子中取出一个随机块，以插入或替换另一个种子的随机块 [231], [7]。

基于字典的变异（Dictionary-based Mutation）

一些模糊测试工具使用一组预定义的、可能具有重要语义意义的值（例如 0 或 -1）以及格式化字符串进行变异。例如，AFL [231]、honggfuzz [204] 和 LibFuzzer [7] 在变异整数时会使用诸如 0、-1 和 1 之类的值。Radamsa [102] 使用 Unicode 字符串，而 GPF [6] 则使用格式化字符（如 %x 和 %s）对字符串进行变异 [55]。

白盒模糊测试工具（White-box Fuzzers）

白盒模糊测试工具也可分为基于模型和无模型两类。例如，传统的动态符号执行 [90], [112], [27], [147], [200] 不需要像基于变异的模糊测试工具那样使用任何模型，但某些符号执行器 [88], [172], [125] 会利用输入模型（如输入语法）来指导符号执行。

尽管许多白盒模糊测试工具（包括 Godefroid 等人的开创性工作 [90]）使用动态符号执行来生成测试用例，但并非所有白盒模糊测试工具都是动态符号执行器。一些模糊测试工具 [219], [52], [145], [182] 利用白盒程序分析来获取被测程序（PUT）接受的输入信息，以将其与黑盒或灰盒模糊测试结合使用。在本节的其余部分，我们将根据测试用例生成算法的底层方法简要总结现有的白盒模糊测试技术。请注意，我们有意省略了动态符号执行器（例如 [89], [191], [60], [46], [209], [51]），除非它们明确称自己为模糊测试工具（如 §2.2 中提到）。

动态符号执行（Dynamic Symbolic Execution）

从高层次来看，经典符号执行 [126], [39], [108] 使用符号值作为输入运行程序，这些符号值代表所有可能的值。程序在执行被测程序（PUT）的过程中，会构建符号表达式，而不是评估具体值。每当遇到条件分支指令时，它会概念性地生成两个符号解释器：一个用于“真”分支，另一个用于“假”分支。在每条路径上，符号解释器都会为执行过程中遇到的每个分支指令构建路径公式（或路径谓词）。如果路径公式是可满足的，则存在一个具体输入可以执行该路径。通过向 SMT 求解器 [155] 查询路径公式的解，可以生成具体输入。

动态符号执行是传统符号执行的一种变体，它同时进行符号执行和具体执行。因此，我们通常将动态符号执行称为混合测试（concolic testing，concrete + symbolic）。其思想是具体执行状态可以帮助降低符号约束的复杂性。关于动态符号执行的学术文献的广泛回顾超出了本文的范围，不过可以在其他资料中找到更全面的处理 [17], [185]。

动态符号执行相比灰盒或黑盒方法速度较慢，因为它需要对被测程序（PUT）的每一条指令进行插桩和分析。为应对高成本，常见策略是缩小其使用范围；例如，让用户指定不感兴趣的代码部分 [210]，或在混合测试与灰盒模糊测试之间交替使用。Driller [200] 和 Cyberdyne [92] 在 DARPA 网络大挑战中展示了这一技术的实用性。QSYM [230] 通过实现一个快速混合执行引擎，改进了灰盒和白盒模糊测试之间的集成。DigFuzz [239] 通过首先估计灰盒模糊测试覆盖每条路径的概率，然后让白盒模糊测试工具专注于灰盒模糊测试认为最具挑战性的路径，优化了灰盒与白盒模糊测试之间的切换。

引导模糊测试

一些模糊测试工具利用静态或动态程序分析技术来提高模糊测试的有效性。这些技术通常涉及两个阶段的模糊测试：(i) 对被测程序（PUT，Program Under Test）进行代价较高的程序分析以获取有用信息，以及 (ii) 利用前期分析的指导生成测试用例。这在表1（第6页）的第六列中有所表示。例如，TaintScope [219] 使用细粒度的污点分析（taint analysis）来识别“热字节”（hot bytes），即那些流入关键系统调用或API调用的输入字节。其他安全研究者也提出了类似的想法 [75], [110]。

Dowser [97] 在编译期间执行静态分析，利用启发式方法找到可能包含漏洞的循环，尤其是那些包含指针解引用的循环。然后，它通过污点分析计算输入字节与候选循环之间的关系。最后，Dowser 使用动态符号执行，仅将关键字节设置为符号化，从而提高了性能。

VUzzer [176] 和 GRT [145] 同时利用静态和动态分析技术，从被测程序中提取控制流和数据流特征，并用这些特征来指导输入生成。

Angora [56] 和 RedQueen [23] 通过先对每个种子运行代价较高的插桩分析，之后利用这些信息生成在轻量插桩下运行的输入，从而降低分析成本。Angora 改进了“热字节”这一概念，通过污点分析将每个路径约束与相应的字节关联起来，然后采用受梯度下降算法启发的搜索方法，指导其变异以解决这些约束。另一方面，RedQueen 通过对所有比较操作进行插桩，尝试检测输入在被测程序中的使用方式，并寻找操作数与给定输入之间的对应关系。一旦找到匹配，就可以用来解决约束。

被测程序变异

模糊测试中的一个实际挑战是绕过校验和验证。例如，当被测程序在解析输入之前计算校验和时，许多测试用例会被拒绝。为了解决这一问题，TaintScope [219] 提出了一种校验和感知的模糊测试技术，该技术通过污点分析识别校验和测试指令，并修改被测程序以绕过校验和验证。一旦发现程序崩溃，它会为输入生成正确的校验和，从而生成可以使未修改的被测程序崩溃的测试用例。

Caballero 等人 [44] 提出了一种称为拼接动态符号执行（stitched dynamic symbolic execution）的技术，可以在存在校验和的情况下生成测试用例。

T-Fuzz [170] 扩展了这一思路，通过灰盒模糊测试高效地穿透各种条件分支。它首先构建了一组非关键检查（NCC，Non-Critical Checks），即可以在不修改程序逻辑的情况下进行变换的分支。当模糊测试不再发现新路径时，它会选择一个NCC进行变换，然后在修改后的被测程序上重新开始模糊测试。最后，当在变换后的程序上发现崩溃时，T-Fuzz 使用符号执行尝试在原始程序上重现崩溃。

输入评估

在生成输入后，模糊测试工具会在被测程序上执行该输入，并决定如何处理生成的执行结果。此过程称为输入评估。尽管执行被测程序的简单性是模糊测试吸引人的原因之一，但与输入评估相关的许多优化和设计决策都会影响模糊测试工具的性能和有效性。本节将探讨这些考虑因素。

漏洞检测器（Bug Oracles）

模糊测试中使用的经典安全策略将每次因致命信号（如段错误）终止的程序执行视为违规行为。这种策略能够检测许多内存漏洞，因为覆盖数据或代码指针的内存漏洞通常会在解引用时导致段错误或程序中止。此外，该策略高效且易于实现，因为操作系统允许模糊测试工具捕获此类异常情况而无需插桩。

然而，传统的崩溃检测策略并不能检测每个被触发的内存漏洞。例如，如果栈缓冲区溢出用有效地址覆盖了栈中的指针，程序可能会以无效结果完成运行，而模糊测试工具将无法检测到这一点。为了解决这个问题，研究人员提出了多种高效的程序转换技术，这些技术可以检测不安全或不希望的程序行为并中止程序。这些技术通常被称为检测器（sanitizers）。

内存与类型安全

内存安全错误可以分为两类：空间错误和时间错误。非正式地说，空间内存错误发生在指针被解引用到其预期对象之外时。例如，缓冲区溢出和下溢是空间内存错误的典型例子。而时间内存错误发生在指针指向的内存不再有效但仍被访问时。例如，释放后使用漏洞（use-after-free） 是一种典型的时间内存错误，其中指针在其指向的内存被释放后仍被使用。

Address Sanitizer（ASan） [192] 是一种快速的内存错误检测工具，在编译时对程序进行插桩。ASan 能够检测空间和时间内存错误，并且平均仅有73%的性能开销，因此是基本崩溃检测的有吸引力的替代方案。ASan 使用影子内存（shadow memory），允许在解引用指针前快速检查每个内存地址的有效性，从而能够检测许多（但不是全部）不安全的内存访问，即使这些访问不会导致原始程序崩溃。

MEDS [101] 通过利用64位平台的大内存空间，在分配的对象之间创建大块不可访问的内存红区（redzones），改进了ASan。这些红区使得被破坏的指针更有可能指向无效内存并导致崩溃。

SoftBound/CETS [159], [160] 是另一种内存错误检测工具，在编译时对程序进行插桩。但与ASan不同，SoftBound/CETS 为每个指针关联边界和时间信息，因此理论上可以检测所有的空间和时间内存错误。然而，正如预期的那样，这种完整性带来了平均116%的性能开销 [160]。

CaVer [133]、TypeSan [96] 和 HexType [113] 在编译期间对程序进行插桩，从而检测C++类型转换中的错误转换（bad-casting）。错误转换发生在对象被转换为不兼容的类型时，例如将基类对象转换为派生类型。CaVer 已证明能够扩展到包含此类漏洞的Web浏览器，并带来了7.6%到64.6%的性能开销。

另一类内存安全保护是控制流完整性（Control Flow Integrity，CFI） [10], [11]，它在运行时检测程序中不可能发生的控制流转移。CFI 可用于检测非法修改程序控制流的测试用例。最近，一个专注于保护CFI子集的项目已经被集成到主流的gcc和clang编译器中 [208]。

未定义行为

像 C 这样的语言包含许多未在语言规范中定义的行为。这些行为由编译器自由处理，可以以各种方式实现。在许多情况下，程序员可能（有意或无意地）编写代码，使其仅在某些编译器实现下是正确的。虽然这看起来并不特别危险，但许多因素可能会影响编译器对未定义行为的实现，包括优化设置、体系结构、编译器本身以及编译器版本。当编译器对未定义行为的处理方式与程序员的预期不一致时，常常会引发漏洞和错误【220】。

Memory Sanitizer (MSan) 是一种工具，它在编译时对程序进行插桩，以检测由 C 和 C++ 中未初始化内存的使用引起的未定义行为【199】。类似于 ASan，MSan 使用影子内存来表示每个位地址是否被初始化。Memory Sanitizer 约有 150% 的性能开销。

Undefined Behavior Sanitizer (UBSan)【71】在编译时修改程序以检测未定义行为。与专注于特定未定义行为来源的其他检测工具不同，UBSan 能检测各种未定义行为，例如使用未对齐的指针、除以零、解引用空指针和整数溢出。

Thread Sanitizer (TSan)【193】是一种编译时的修改工具，用于检测数据竞争（data race），这需要在精确性和性能之间进行权衡。数据竞争发生在两个线程同时访问同一共享内存位置且至少有一个访问为写操作时。这种错误可能导致数据损坏，并因为非确定性而极难复现。

输入验证

测试输入验证漏洞（如 XSS 跨站脚本攻击和 SQL 注入漏洞）是一个具有挑战性的问题，因为这需要理解驱动 Web 浏览器和数据库引擎的复杂解析器的行为。

KameleonFuzz【74】通过使用真实的 Web 浏览器解析测试用例、提取文档对象模型（DOM）树，并将其与手动指定的模式进行比较，来检测成功的 XSS 攻击。

µ4SQLi【18】使用类似的方法来检测 SQL 注入。由于无法可靠地通过 Web 应用程序的响应检测 SQL 注入，µ4SQLi 使用一个数据库代理拦截目标 Web 应用程序与数据库之间的通信，以检测输入是否触发了有害行为。

语义差异

语义错误通常通过一种称为差分测试【148】的技术发现，该技术比较类似（但不完全相同）程序的行为。许多模糊测试工具【41】【171】【59】利用差分测试来识别类似程序之间的差异，而这些差异很可能表明存在错误。

Jung 等人【118】提出了黑盒差分模糊测试，它通过对单个程序的多个输入进行差分测试，来映射从输入到被测程序输出的变异。这些映射被用来识别信息泄露。

执行优化

我们的模型将单个模糊测试迭代视为顺序执行。虽然这种方法的直接实现会在每次模糊测试迭代开始时重新加载被测程序 (PUT)，但这些重复加载过程可能会显著降低效率。为此，现代模糊测试工具提供了跳过这些重复加载过程的功能。

例如，AFL【231】提供了一个 fork-server，允许每次新的模糊测试迭代从一个已初始化的进程中 fork 出来。同样，内存中的模糊测试也是优化执行速度的另一种方式（如 §3.1.2 所述）。无论具体机制如何，加载和初始化被测程序的开销可以被摊销到多个迭代中。

Xu 等人【228】通过设计一种替代 fork() 的新系统调用，进一步降低了每次迭代的成本。

筛选（Triage）

筛选是分析和报告导致策略违规的测试用例的过程。筛选可分为三个步骤：去重、优先级排序和测试用例最小化。

去重

去重是从输出集中删除任何触发相同错误的测试用例的过程。理想情况下，去重会返回一组测试用例，其中每个测试用例都会触发一个独特的错误。

去重是大多数模糊测试工具的重要组成部分，原因如下：

• 实践意义：它避免了重复结果占用硬盘空间和其他资源。
• 可用性考虑：它使用户可以大致了解存在多少不同的错误，以及能够分析每个错误的示例。这对于各类模糊测试工具的用户都很有用。例如，攻击者可能只想寻找那些可能导致可靠利用的“关键”漏洞。

当前实践中主要有三种去重实现：堆栈回溯哈希、基于覆盖的去重和语义感知去重。

堆栈回溯哈希

堆栈回溯哈希【154】是最早且最广泛使用的去重方法之一。该方法通过记录程序崩溃时的堆栈回溯，并根据该回溯内容生成堆栈哈希。例如，如果程序在执行函数 foo 的某一行代码时崩溃，并且调用栈为 main → d → c → b → a → foo（见图 2），那么一个 n = 5 的堆栈回溯哈希实现会将该测试用例与其他堆栈回溯以 d → c → b → a → foo 结尾的崩溃分为一组。

堆栈哈希的实现差异很大，主要体现在：

• 包含的堆栈帧数量：一些实现只使用一个堆栈帧【19】，一些使用三个【154】【225】，

堆栈回溯散列示例

• 一些使用五个【82】【49】，还有一些没有限制【123】。
• 每个堆栈帧包含的信息量：有些实现只对函数名称或地址进行哈希，而其他实现还会对名称、偏移量或行号进行哈希。有些实现【150】【82】会生成两个哈希值：主哈希和次哈希。主哈希较为宽松，可能将不同的崩溃分为一组，因为它仅基于函数名称进行哈希；而次哈希更精确，因为它使用函数名称和行号，并包括无限数量的堆栈帧。

虽然堆栈回溯哈希被广泛使用，但它也存在缺点。堆栈回溯哈希的基本假设是：相似的崩溃由相似的错误引起，反之亦然。但据我们所知，这一假设从未被直接验证过，有理由怀疑其真实性。某些崩溃可能并非发生在导致错误的代码附近。例如，一个导致堆损坏的漏洞可能仅在代码中一个无关部分尝试分配内存时崩溃，而不是在堆溢出发生时崩溃。

基于覆盖的去重

AFL [231] 是一种流行的灰盒模糊测试工具，采用高效的源码插桩技术记录每次运行目标程序（PUT）的边覆盖信息，并测量每条边的大致命中计数。作为一种灰盒模糊测试工具，AFL 主要使用这些覆盖信息来选择新的种子文件。然而，这种机制也带来了一个相当独特的去重方案。
根据其文档的描述，AFL 认为一个崩溃是独特的，当且仅当：
(i) 该崩溃覆盖了之前未见过的边，或者
(ii) 该崩溃未覆盖所有先前崩溃中都存在的某条边。

基于语义的去重

RETracer [65] 通过从每次崩溃中恢复的逆向数据流分析进行崩溃分类。具体而言，RETracer 通过分析崩溃转储（核心转储）来检查哪个指针导致了崩溃，并递归地识别出哪个指令分配了错误的值。最终，它会找到一个具有最大堆栈帧深度的函数，并“归咎”于该函数。这个被归咎的函数可以用来对崩溃进行聚类。
作者展示了他们的技术如何成功地将数百万个 Internet Explorer 的缺陷归并为一个，而堆栈哈希方法则将相同的崩溃分为许多不同的组。

优先级排序与可利用性

优先级排序（也称为模糊测试收敛问题 [58]）是根据严重性和独特性对违规测试用例进行排名或分组的过程。在模糊测试中，这一过程传统上用于发现内存漏洞。在这种背景下，优先级排序通常被称为确定崩溃的可利用性。
可利用性非正式地描述了攻击者能够为测试用例暴露的漏洞编写实际利用程序的可能性。防御者和攻击者都对可利用的漏洞感兴趣：防御者通常会优先修复可利用的漏洞，而攻击者则出于显而易见的原因关注它们。

最早的可利用性排序系统之一是微软的 !exploitable [150]，其名称来源于其提供的 WinDbg 命令 !exploitable。
!exploitable 使用了一些启发式规则与简化的污点分析 [164]、[185] 配对。它按照以下严重性等级对每次崩溃进行分类：
EXPLOITABLE > PROBABLY_EXPLOITABLE > UNKNOWN > NOT_LIKELY_EXPLOITABLE，其中 x > y 表示 x 比 y 更严重。
虽然这些分类没有正式定义，但 !exploitable 非正式地倾向于保守，即更倾向于将某些崩溃报告为“更具可利用性”。例如，如果崩溃执行了一条非法指令，!exploitable 会认为该崩溃是 EXPLOITABLE，因为它假定攻击者能够强制控制程序流。而对于除零崩溃，则被认为是 NOT_LIKELY_EXPLOITABLE。

自 !exploitable 引入以来，又提出了其他类似的基于规则的启发式方法，例如 GDB 的 exploitable 插件 [82] 和 Apple 的 CrashWrangler [19]。然而，这些方法的正确性尚未被系统性研究和评估。

测试用例最小化

测试用例最小化是分类中的另一个重要部分。测试用例最小化是指识别导致违规的测试用例中必要的部分，并在可选情况下，生成一个比原始输入更小、更简单但仍然能引发违规的测试用例。

尽管测试用例最小化与种子修剪（详见 3.3，第 8 页）在概念上相似，因为它们都旨在减少输入的大小，但它们是不同的，因为最小化器可以利用漏洞判定机制（bug oracle）。

一些模糊测试工具使用自己的实现和算法来完成这一任务。例如，BFF [49] 包含了一种针对模糊测试的最小化算法 [106]，该算法试图最小化与原始种子文件不同的位数量。AFL [231] 也包括一个测试用例最小化工具，该工具通过将字节设置为零并缩短测试用例长度来尝试简化测试用例。
Lithium [179] 是一种通用的测试用例最小化工具，通过尝试移除相邻行或字节的“块”并以指数递减的大小进行操作来最小化文件。Lithium 的设计灵感来源于 JavaScript 模糊测试工具（如 jsfunfuzz [187]）生成的复杂测试用例。

还有一些并非专为模糊测试设计的测试用例缩减工具，但同样可以用于模糊测试识别的测试用例。这些工具包括与格式无关的技术，例如 delta debugging [236]，以及针对特定格式的专用技术，例如用于 C/C++ 文件的 C-Reduce [178]。尽管专用技术显然受到待缩减文件类型的限制，但它们的优势在于比通用技术效率更高，因为它们对所尝试简化的语法有更深入的理解。

配置更新

CONFIG_UPDATE 函数是区分黑盒模糊测试与灰盒、白盒模糊测试行为的关键。正如算法 1 所讨论的，CONFIG_UPDATE 函数可以基于当前模糊测试运行期间收集的配置与执行信息来修改配置集（C）。在最简单的形式中，CONFIG_UPDATE 返回未修改的 C 参数。

黑盒模糊测试不会执行 bug 判定机制 Obug 之外的任何程序内省，因此它们通常不会修改配置集 C，因为它们没有收集到任何可以用于修改 C 的信息。

相比之下，灰盒和白盒模糊测试则通过更复杂的 CONFIG_UPDATE 函数实现得以区分，它们可以合并新的模糊测试配置，或者移除可能已被取代的旧配置。CONFIG_UPDATE 使得在一次模糊测试迭代中收集的信息可以用于所有后续的模糊测试迭代。

例如，白盒模糊测试通常为每个生成的新测试用例创建一个新的模糊测试配置，因为它们生成的测试用例数量相对较少，低于黑盒和灰盒模糊测试工具。

演化种子池更新

演化算法（Evolutionary Algorithm, EA）是一种基于启发式的方法，涉及变异、重组和选择等生物进化机制。在模糊测试（fuzzing）的背景下，EA维护一个由有潜力的个体（即种子）组成的种子池，这些种子在模糊测试活动中会随着新个体的发现而不断进化。尽管EA的概念相对简单，但它构成了许多灰盒模糊测试工具的基础 [231], [7], [216]。关于如何选择用于变异的种子以及变异过程本身，已在§4.3和§5中详细说明。

可以说，EA中最重要的一步是将一个新的配置添加到配置集合 C 中，这发生在模糊测试中的 CONFUPDATE 步骤。大多数基于EA的模糊测试工具使用节点或分支覆盖率作为适应度函数：如果一个测试用例发现了新的节点或分支，就会将它添加到种子池中。由于可到达路径的数量可能比种子数量大几个数量级，种子池被设计为所有可到达路径的一个多样化子集，以表示当前对被测程序（PUT）的探索。此外，请注意，不同大小的种子池可能具有相同的覆盖率（如§3.2第7页所述）。

EA模糊测试工具中的常见策略之一是优化适应度函数，以检测更细微和更精确的改进指标。例如，AFL [231] 通过记录分支被触发的次数来优化其适应度函数定义。STADS [35] 受生态学启发，提出了一种统计框架，用于估计如果模糊测试活动继续进行，将会发现多少新配置。另一种常见的策略是测量复杂分支条件被满足的条件比例。例如，LAF-INTEL [130] 将多字节比较拆分为多个分支，从而能够检测新的种子何时通过了中间字节比较。LibFuzzer [7]、Honggfuzz [204]、go-fuzz [215] 和 Steelix [138] 会对所有比较进行插桩，并添加任何在比较中取得进展的测试用例到种子池中。类似的想法也作为clang的独立插桩模块发布 [119]。此外，Steelix [138] 检查哪些输入偏移量会影响比较指令。Angora [170] 通过考虑每个分支调用上下文来改进AFL的适应度标准。

VUzzer [176] 是一种基于EA的模糊测试工具，其适应度函数依赖于自定义程序分析的结果，用于为每个基本块分配权重。具体来说，VUzzer 首先使用内置的程序分析将基本块分类为普通块或错误处理（EH）块。对于普通块，其权重与随机游走在包含该块的控制流图（CFG）中访问该块的概率成反比（此概率由VUzzer定义的转换概率决定）。这种方法鼓励VUzzer优先选择那些被上述随机游走认为稀有的普通块。EH块的权重为负数，其大小为基本块数量与被该配置执行的EH块数量之比。这些负权重用于减少EH块的执行，因为假设遍历EH块表明发现漏洞的可能性较低，因为漏洞通常与未处理的错误相伴。

维护最小集合（Minset）

随着创建新模糊测试配置的能力增强，也带来了生成过多配置的风险。一种常见的缓解策略是维护一个最小集合（minset），即在最大化覆盖率指标的同时，保持最小的测试用例集合。最小集合也在 PREPROCESS 阶段中使用，并在§3.2中有更详细的描述。

一些模糊测试工具使用了一种专门针对配置更新的最小集合维护变体。例如，与完全移除不在最小集合中的配置（如Cyberdyne [92] 所做的）不同，AFL [231] 使用了一种剔除（culling）程序，将最小集合中的配置标记为有利配置。被标记为有利的模糊测试配置在 SCHEDULE 函数中被赋予更高的选择概率。AFL的作者指出：“这种方法在队列循环速度和测试用例多样性之间提供了合理的平衡” [235]。

相关工作

模糊测试领域的文献在2007–2008年间经历了一次早期的繁荣期，当时有三本关于该主题的专业书籍在两年内相继出版 [79], [203], [205]。这些书籍采用了更为实践的方法，介绍了当时可用的不同工具和技术及其在各种目标上的应用。我们注意到，Takanen等人 [205] 已经区分了黑盒、白盒和灰盒模糊测试，尽管没有给出正式定义。最近，[205]在十年后进行了修订。其第二版 [206] 包含了许多更新内容，包括现代工具如AFL [231] 和 ClusterFuzz [61]。

我们知道有两篇与我们的工作同时期的模糊测试综述 [137], [139]。然而，这两篇综述的目标比我们的更聚焦，而我们的目标是提供一个涵盖整个领域的最新发展研究。具体而言，Li等人 [137] 对许多近期的模糊测试进展进行了全面回顾，但他们决定专注于基于覆盖率的模糊测试，而非其他类型。与我们的工作更相似的是，Liang等人 [139] 提出了一个非正式模型来描述各种模糊测试技术。然而，他们的模型不足以涵盖我们在本文中讨论的一些模糊测试方法，例如模型推断（参见§5.1.2）和混合模糊测试（参见§5.3）。

Klees等人 [127] 最近发现，目前还没有一种连贯的方式来评估模糊测试技术，这可能会阻碍我们比较不同模糊测试技术效果的能力。此外，他们还为评估模糊测试算法提供了若干有用的指导方针。我们认为他们的工作与我们是互补的，因为模糊测试算法的评估超出了本文的范围。

总结

正如我们在§1中所述，本文的目标是提炼现代模糊测试文献的一个全面而连贯的视角。为此，我们首先提出了一个通用的模型模糊测试器，以帮助我们解释当前使用的多种模糊测试形式。随后，我们通过图1（第5页）和表1（第6页）展示了一个丰富的模糊测试工具分类法。我们通过讨论设计决策以及展示社区取得的诸多成就，探索了模型模糊测试器的每个阶段。

上传的附件：

• The Art Science and Engineering of Fuzzing.pdf （496.01kb，0次下载）