0x00 前言

论文题目：模糊测试：艺术、科学和工程

这篇论文是模糊测试领域的一篇具有代表性的综述性工作，系统总结了模糊测试技术的发展历程、关键组成部分、工程挑战以及未来研究趋势。

模糊测试作为当前最有效的软件漏洞发现技术之一，因其简单的概念、低部署门槛及大量实际漏洞发现案例而备受青睐。然而，近年来模糊测试研究爆发式增长，也带来了术语不统一、缺乏统一理论模型等问题，阻碍了知识传播与工具的持续演进。

论文的主要贡献包括：

  • 统一模糊测试模型：提出涵盖输入生成、调度、执行监控、崩溃检测等关键步骤的通用模型，帮助厘清模糊测试整体流程和构成。
  • 模糊测试术语标准化：梳理并规范社区中诸如测试用例缩减（test case reduction）、最小化（minimization）等模糊测试相关术语的使用差异，推动统一理解。
  • 文献分类图谱：对大量模糊测试相关研究工作进行了系统分类，涵盖基于变异的灰盒模糊测试、白盒符号执行辅助模糊测试、智能输入生成等多个方向。

0x01 简介

自 20 世纪 90 年代初推出以来，模糊测试（以下简称 Fuzzing）一直是发现软件安全漏洞的最广泛部署的技术之一。在较高的层次上，Fuzzing 指的是使用生成的输入重复运行程序的过程，这些输入可能在语法或语义上有缺陷。在实践中，攻击者通常会在诸如漏洞利用生成和渗透测试等场景中部署 Fuzzing；在如今的 Fuzzing 热潮下，安全研究人员开始研究 Fuzzing，试图在攻击者之前发现程序所存在的漏洞。 例如，Adobe、Cisco、Google 和 Microsoft 等知名厂商都采用 Fuzzing 作为他们安全开发实践的一部分。

由于 Fuzzing 社区非常活跃，有非常多的关于 Fuzzing 研究，于是也随之诞生出了以下问题：

  • 一些模糊测试工具的描述仅限于其源代码或手册页，缺乏系统化文档；这使得其设计决策和关键实现细节容易随时间被遗忘或忽视；
  • 同时，模糊测试领域在术语使用上出现了明显的碎片化，这加剧了理解与传播的困难。

比如 AFL 使用 “test case minimization” 来表示将崩溃样本的大小缩小的技术；而在 funfuzz 中，这一技术则被称为 “test case reduction”；BFF 中还有一个叫 “crash minimization” 的技术，听起来相似，但其目标其实是最小化崩溃样本与原始输入之间的比特差异，而不是样本本身的大小。

这类术语不一致的问题会导致 Fuzzing 知识难以发展和传递，长期来看可能严重阻碍该领域的研究发展。

于是论文针对以上问题做了以下工作：

  • 提出一个统一的模糊测试模型；
  • 提出一套统一的模糊测试术语体系；
  • 对模糊测试相关研究做系统分类。

0x02 系统化、分类与测试程序

术语 “fuzz” 最初是由 Miller 等人在 1990 年创造的，用来指代一种生成随机字符并将其输入目标程序的程序。从那时起，fuzz 的概念以及行为 fuzzing 出现在各种各样的语境中，包括动态符号执行、基于语法的测试用例生成、权限测试、行为测试、表示依赖性测试、功能检测、鲁棒性评估、漏洞利用开发、GUI 测试、签名生成和渗透测试。

2.1 Fuzzing & Fuzz Testing

直观地说，模糊测试是使用 “模糊输入” 运行被测程序（PUT，Program Under Test）的动作。为了纪念 Miller 等人，我们认为模糊输入是 PUT 可能没有预料到的输入，即 PUT 可能不正确的处理输入，并触发 PUT 开发人员意想不到的行为。根据这个，我们将术思想语定义如下：

  • Fuzzing：Fuzzing 是指使用来自一个模糊输入空间中的输入来执行被测程序（PUT）这个模糊输入空间超出了 PUT 所预期的输入空间。
  • Fuzz Testing：模糊测试技术是使用 Fuzzing 方式来测试被测程序是否违反某项安全策略。
  • Fuzzer：Fuzzer（模糊测试器）是一个程序，其作用是对被测程序执行 Fuzz Testing。
  • Fuzz Campaign：Fuzz Campaign（模糊测试任务）是指 Fuzzer 在某个被测程序上，基于特定的安全策略执行的一次具体测试流程。
  • Bug Oracle：Bug Oracle（漏洞判定器）是一个程序（可能是 Fuzzer 的一部分），其职责是判断 PUT 的一次执行是否违反了指定的安全策略。
  • Fuzz Configuration：Fuzz Configuration（模糊测试配置）是 Fuzz 算法的参数集合，这些参数用于控制 Fuzz 的具体行为，每组参数设置就是一个 Fuzz 配置。一个 Fuzz 配置通常写成一个元组，模糊配置中值的类型取决于模糊算法的类型。

模糊测试与软件测试的区别只在于它与安全性相关。尽管瞄准安全 bug 并不意味着除了理论上使用 bug oracle 之外，测试过程中有什么不同，但是在实践中使用的技术常常是不同的。在设计测试工具时，我们通常假设存在源代码和关于 PUT 的知识。这类假设会推动测试工具的发展走向与 fuzzer 不同的路径。尽管如此，模糊测试和传统软件测试这两个领域仍然密不可分、紧密交织。因此，当我们难以凭主观判断区分某项工作是否属于 “fuzz testing” 时，我们采用一个简单的经验法则：是否存在某种自动化机制，反复向 PUT 提供生成的输入，并监控其运行行为以发现异常？

2.2 模糊测试算法

本文提出了一种用于 Fuzzing 的通用算法，它被设想为在一个 “模型模糊器（model fuzzer）” 中实现。该算法具有足够的通用性，能够兼容当前存在的各种模糊测试技术。

算法接受以下输入：

  • 一组 Fuzzing 配置C。
  • 一个超时时间tlimit。

输出一组发现的 bug b。

它由两部分组成：

  1. Preprocess函数：在 Fuzzing 开始时执行。
  2. 主循环部分：Schedule（调度）、InputGen（输入生成）、InputEval（输入评估）、ConfUpdate（配置更新）、Continue（判断是否继续）。

主循环的每一次执行称为一次模糊迭代（fuzz iteration），而对单个测试用例执行InputEval被称为一次模糊执行（fuzz run）。

需要注意的是：某些 fuzzer 并不会实现所有这五个函数。例如，为了对 Radamsa 建模，我们定义的配置更新函数ConfUpdate仅返回当前配置C，即不对配置进行任何更新。

函数名输入输出功能说明
Preprocess(C)模糊配置集合C（可能修改的）模糊配置集合C初始化阶段：插桩 PUT、测量种子性能等
Schedule(C, telapsed, tlimit)配置集合C、已用时间telapsed、总时限tlimit当前选中的配置conf选择当前轮次要使用的配置，影响测试优先级
InputGen(conf)配置 conf生成的测试用例集合tcs根据配置（如种子、语法）生成测试数据
InputEval(conf, tcs, Obug)配置conf、测试用例tcs、bug oracle Obug发现的 bug 集合B′、执行信息execinfos运行测试用例，收集覆盖率、崩溃等反馈
ConfUpdate(C, conf, execinfos)原始配置集合C、当前配置conf、执行反馈execinfos更新后的配置集合C更新配置集合，保留有效项、移除冗余项
Continue(C)当前配置集合C布尔值（是否继续）决定是否进入下一轮迭代（如路径已穷尽则停止）

2.3 Fuzzers 分类

本文中根据 fuzzer 在每次执行 fuzz run 中观察到的语义粒度，将 fuzzer 分为三类：黑盒（block-box）、灰盒（grey-box）和白盒（white-box） fuzzer。需要注意的是，这与传统的软件测试不同，传统的软件测试只有黑盒测试和白盒测试两大类。灰盒模糊测试是白盒模糊测试的一种变体，它只能从每次模糊执行中获得部分信息。

图 1 展示了本文按时间顺序对现有模糊测试器的分类。它从 Miller 等人的开创性工作开始，选取了在主要会议上出现或 GitHub 上星标超过 100 的流行 fuzzer，并用图示展示它们之间的关系。图中左半部分是黑盒模糊测试器，右半部分是灰盒和白盒 fuzzer。

表 1 详细总结了在主要会议上出现的主流 fuzzer 所使用的技术。表中将每个 fuzzer 都映射到本文提出的模型中的五个函数，还有一个杂栏部分给出了 fuzzer 的额外细节。

  • 第一列（插桩粒度）：表示 fuzzer 基于静态或动态分析从 PUT 获取的信息量。若 fuzzer 包含两个阶段且使用不同类型的插桩，则会出现两个圆圈。例如，SymFuzz 在预处理阶段运行白盒分析以提取信息，随后执行黑盒测试；Driller 则在白盒和灰盒模糊测试间交替进行。
  • 第二列：显示是否公开了源代码。
  • 第三列：表明模糊测试器是否需要源代码才能运行。
  • 第四列：指出是否支持内存内模糊测试。
  • 第五列：表明是否能够推断模型。
  • 第六列：显示是否在预处理阶段执行静态或动态分析。
  • 第七列：指示是否支持多种种子管理和调度。
  • 变异栏：说明是否进行输入变异生成测试用例，带 “✓” 表示变异过程受到执行反馈引导。
  • 基于模型栏：显示是否基于模型生成测试用例。
  • 基于约束栏：表示是否执行符号分析以生成测试用例。
  • 污点分析栏：表示是否利用污点分析指导测试用例生成。
  • 输入评估部分有两列，显示模糊测试器是否利用堆栈哈希或代码覆盖率进行崩溃分拣。
  • 配置更新部分有三列，分别表示是否在ConfUpdate过程中扩充种子池（例如添加有趣种子）、是否在线学习模型，以及是否从种子池中移除种子。
图 1：追溯重要模糊测试器谱系至Miller等人的开创性工作。图中同一行的每个节点代表同一年出现的一组模糊测试器。实线箭头从X指向Y表示Y引用、参考或以其他方式使用了X的技术。★ 表示对应工作的论文已被发表。

2.3.1 Black-box Fuzzer

术语 “black-box” 通常用于在软件测试和模糊测试中，用于表示 PUT 视其为一个黑盒系统。在软件测试中，黑盒测试也被称为基于输入输出驱动或数据驱动的测试，即测试过程中不依赖程序内部实现，而进阶基于输入与观察到的输出进行判断。大多数传统的 fuzzer 都属于这一类。一些现代的 fuzzer 例如 funfuzz 和 Peach，虽然保持不检查 PUT 内部的特性，但会考虑输入的结构信息，以生成更有意义的测试用例。类似的思路也用于自适应随机测试。

2.3.2 White-box Fuzzer

白盒模糊测试通过分析 PUT 的内部结构及其执行时行为信息来生成测试用例，因此能够更系统地探索 PUT 的状态空间。“白盒模糊测试” 这一术语由 Godefroid 于2007年提出，指的是动态符号执行（DSE），它是符号执行的一种变体，其核心思想是在执行过程中同时进行具体执行与符合执行。其中具体的程序状态用于简化符号约束条件。由于其结合了具体执行和符合执行的特性，DSE 常被称为 “混合测试”（concolic testing）。此外，白盒模糊测试的范畴还包括使用污点分析（taint analysis）的 fuzzer，这些工具能够追踪输入对程序状态的映像，从而指导更有效的测试用例生成。白盒模糊测试的开销通常远高于黑盒模糊测试，这一方面是由于其通常依赖于动态插桩技术收集执行信息，另一方面则是因为其内部使用了 SMT 求解来处理复杂的路径约束条件，计算资源消耗显著。

2.3.3 Grey-box Fuzzer

一些安全专家提出了一种折中方案，称为灰盒模糊测试。灰盒模糊测试器通常可以访问 PUT 部分内部信息及其执行过程中的动态行为信息。相比白盒模糊测试器，灰盒模糊测试器不追求对程序语义的完整理解，而是通过轻量级静态分析和动态执行信息（如代码覆盖率）来辅助测试用例生成。灰盒模糊测试器利用信息近似的方法，以便测试更多输入。虽然安全专家通常对黑盒、灰盒和白盒模糊测试的区别达成一定共识，但界限并非绝对清晰。黑盒模糊测试器有时也会收集部分信息，白盒模糊测试器也常常需要做某种程度的近似处理。

灰盒模糊测试器的早期实例包括 EFS，它利用每次模糊运行收集的代码覆盖率，通过进化算法生成测试用例。Randoop 也采用了类似方法，但其目标并非安全漏洞。

现代灰盒模糊测试器的代表包括：

  • AFL：利用轻量插桩收集路径覆盖率，以指导输入变异。
  • VUzzer：结合程序静态信息与运行时反馈，采用基于语义的灰盒 fuzz 测试，进一步提升路径探索能力。
表1：按仪器颗粒度和名称排序的模糊器概述，分别表示黑盒、灰盒和白盒。

0x03 预处理

一些模糊测试器会在第一次模糊测试迭代之前，修改初始的模糊配置集合。这种预处理操作通常用于：

  • **插桩目标程序；
  • 剔除潜在的冗余配置（即所谓的“种子选择”）；
  • 以及裁剪种子（trim seeds）。

简而言之，预处理阶段的目的是在模糊测试正式开始前，对初始输入集进行优化和准备，以提高后续测试的效率和效果。

3.1 插桩

与黑盒 fuzzer 不同，灰盒和白盒 fuzzer 通常可以对 PUT 进行插桩，以在 InputEval 阶段执行 fuzz run 时收集执行反馈，或者在运行时 fuzz 内存内容。虽然还有其他方式可以获取 PUT 的内部信息（例如处理器跟踪和系统调用监控），但插桩通常是获取最有价值反馈的方式，因此几乎完全决定了 fuzzer 的 “颜色”。

程序插桩可以是静态的或动态的：前者在 PUT 运行之前完成，而后者则在 PUT 运行时进行。由于静态插桩在运行前运行，因此通常比动态插桩带来更低的运行时开销。

静态插桩通常在编译时进行，可以作用于源代码或中间代码。如果 PUT 依赖某些库，这些库也必须单独插桩，通常需要使用相同的插桩方法重新编译。除了基于源代码的插桩外，研究人员还开发了基于二进制的静态插桩工具（即二进制重写）。

相比之下，尽管动态插桩的运行时开销高于静态插桩，但它的优势在于可以轻松地对动态链接的库进行插桩，因为其插桩发生在程序运行时。常见的动态插桩工具有：DynInst、DynamoRIO、Pin、Valgrind 和 QEMU。通常，动态插桩在运行时发生，这意味着它对应于我们模型中的 InputEval 阶段。

某些 fuzzer 支持多种插桩方式。例如，AFL 在源代码级别支持静态插桩（通过修改过的编译器），在二进制级别则支持动态插桩（借助 QEMU）。在使用动态插桩时，AFL 可以选择以下两种策略：

  1. 插桩 PUT 本身的可执行代码（默认）；
  2. 插桩 PUT 及其所有外部库中的可执行代码（通过设置AFL_INST_LIBS选项）。

第二种方式，即插桩所有被执行到的代码，可以收集包括外部库在内的更全面的覆盖率信息。但相应地，也意味着 AFL 会测试等多来自外部库函数的执行路径。

3.1.1 执行反馈

灰盒 fuzzer 通常使用执行反馈（Execution Feedback）作为输入，用于引导测试用例的演化。AFL 及其衍生工具通过在 PUT 中的每个分支指令上进行插桩来计算分支覆盖率（branch coverage）。然而，这类工具将分支覆盖信息存储在一个位向量（bit vector）中，这可能会导致路径冲突（path collisions），即不同的路径被映射到相同的位，降低反馈精度。

为了解决这一问题，CollAFL 引入了一种新的路径敏感型哈希函数（path-sensitive hash function），用以提升路径区分能力，从而更准确地记录覆盖信息。

与此同时，LibFuzzer 和 Syzkaller 使用的是节点覆盖率（node coverage）作为执行反馈，即记录哪些基本块被执行过，而不是具体的分支。

另一个工具 Honggfuzz 则提供了更多的灵活性，它允许用户自行选择所使用的执行反馈类型，以适应不同目标程序和测试策略的需求。

3.1.2 In-Memory Fuzzing

在测试大型程序时，为了最小化每轮模糊测试迭代的执行开销，有时希望只对 PUT 的一部分进行测试，而不是每次都重新启动进程。例如，复杂的程序（如 GUI 应用）通常在接受输入前需要几秒钟的初始化处理。

一种测试这类程序的方法是：在 GUI 初始化完成后对 PUT 创建内存快照（snapshot），随后每轮测试新的输入时，只需恢复该内存快照，再将新的测试用例直接写入内存并执行。这一策略也适用于网络程序测试，尤其是客户端与服务端之间存在大量交互的场景。这种技术被称为内存中模糊测试（in-memory fuzzing） 。

例如，GRR 会在载入输入字节之前创建内存快照，从而跳过不必要的启动代码。AFL 则使用一种称为 fork server 的机制来避免部分进程启动的开销。尽管 fork server 与 in-memory fuzzing 有着相同的动机，但它每次 fuzz 迭代仍然会 fork 一个新的进程。

有些 fuzzer 会在不恢复 PUT 状态的情况下对某个函数直接执行内存内模糊测试，这种技术被称为内存内 API 模糊测试（in-memory API fuzzing）。例如，AFL 提供了一种名为持久模式（persistent mode）的选项，它可以在一个循环中反复对某个函数进行模糊测试，而不重新启动进程。在这种模式下，AFL 忽略了函数在同一执行中被多次调用可能产生的副作用。

尽管这种方式非常高效，但它存在不可靠的风险：即内存中发现的 bug 或崩溃可能无法在正常环境中复现，原因包括：

  1. 无法构造有效的调用上下文：不是所有目标函数都能被正确、完整地调用；
  2. 存在跨多次调用无法捕捉的副作用。

需要注意的是，内存内 API 模糊测试的可靠性（soundness）主要依赖于入口函数的选择，而找到一个合适的入口函数本身就是一项挑战。

3.1.3 线程调度

条件竞争漏洞很难触发，因为它们依赖于不确定的行为，这种行为可能只会很少发生。然而，插桩也可以通过显式控制线程的调度方式来触发不同的非确定性程序行为。现有的工作已经表明，即使是随机调度线程也可以有效地发现条件竞争漏洞。

3.2 种子选择

正如第 2 节所述，fuzzer 接收一组模糊测试配置（fuzz configurations）作为输入，这些配置直接影响模糊测试算法的行为。其中，一些参数（如基于变异的模糊测试中的种子）具有非常大的取值空间，这就引出了一个问题：应该选择哪些种子用于模糊测试？

以 MP3 播放器为例，该程序接收 MP3 文件作为输入。由于合法的 MP3 文件数量是无限的，那么我们该选择哪些种子？这个问题被称为种子选择问题（seed selection problem）。

针对该问题，有多种方法和工具被提出。一种常见的方法是：构建一组最小种子集合（minset），以最大化某种覆盖率指标（如节点覆盖率）。这个过程被称为计算最小种子集合（computing a minset）。

举个例子，假设当前的配置集合 CC 包含两个种子：

  • s₁ → {10, 20}
  • s₂ → {20, 30}

现在引入一个新的种子：

  • s₃ → {10, 20, 30}

并且 s₃ 的执行效率与 s₁ 和 s₂ 相当。直观来看，使用 s₃ 替代 s₁ 和 s₂ 是合理的，因为它以更低的成本覆盖了更多的执行路径。这种做法得到了 Miller 的报告的支持：代码覆盖率每提升1%，发现的 Bug 数量就增加约0.92%。这一步也可以作为ConfUpdate的一部分。

在实际应用中，不同的 fuzzer 使用了多种不同的覆盖率指标构造 minset。例如：

  • AFL 的 minset 是基于分支覆盖率（branch coverage）构造，并在每个分支上使用对数计数器。该设计的核心思想是：仅当两个路径在分支执行次数上存在数量级差异时，才认为它们是不同的路径。
  • Honggfuzz 采用的是基于执行指令数量、执行的分支数量，以及唯一基本块数量的覆盖率度量。这种度量方式允许模糊测试器将执行路径较长的测试用例加入 minset，有助于发现拒绝服务（DoS）漏洞或性能问题。

3.3 种子裁剪

较小的种子通常会占用更少的内存，并带来更高的吞吐量。因此，一些 fuzzer 在模糊测试前会尝试缩减种子大小，这一过程被称为种子裁剪（seed trimming）。

种子裁剪可以在主模糊测试循环开始前执行，属于 Preprocess，也可以作为 ConfUpdate 的一部分。

一个使用种子裁剪的典型 fuzzer 是 AFL，它借助代码覆盖插桩机制进行迭代式裁剪：只要对种子进行修改（删除部分内容）后仍然保持相同的覆盖率，AFL 就会保留该修改，从而生成更小的种子。

与此同时，Rebert 等人提出了一种名为 size minset 的算法，该算法优先选择较小的种子，用以组成最小种子集。然而，他们的实验结果表明，与随机选择种子相比，使用该算法发现的独特漏洞数量反而更少。

换言之，尽管种子裁剪在提升效率方面有效，但过度优化种子大小可能影响漏洞发现的多样性。因此，在实际应用中需要在种子 “精简” 和“多样性” 之间做权衡。

3.4 编写驱动程序

当直接对 PUT 进行测试较为困难时，为其编写一个用于模糊测试的驱动程序（通常称为Harness）是常见的做法。这个过程在实际应用中通常是人工完成的，尽管它只需要编写一次（现如今以及有了很多自动化生成驱动的项目）。

例如：

  • 当目标是一个库函数（library）时，我们需要编写一个驱动程序来调用该库中的函数，使其能够接受模糊测试输入。
  • 类似地，内核模糊测试器有时会模糊测试用户态程序，以间接触发内核行为并进行测试。

有些研究利用驱动程序中的信息来辅助模糊测试：

  • MutaGen 利用驱动程序中包含的 PUT 相关知识来生成测试用例。具体来说，它对驱动程序本身进行变异，使用动态程序切片（dynamic program slicing）技术来产生测试输入。
  • IoTFuzzer 针对 IoT 设备进行模糊测试，它的做法是将对应的智能手机应用程序作为驱动程序，从而间接对设备进行测试。

综上，驱动程序的准备工作虽然初始成本较高，但对于无法直接测试的目标来说，是模糊测试的关键前置步骤。

0x04 调度

在模糊测试中，调度（scheduling）指的是为下一次 fuzz run 选择一个 fuzz configuration。正如第 2.1 节中所说的，每个配置的具体内容取决于 fuzzer 的类型。

对于简单的 fuzzer，调度过程可能非常直接。比如，zzuf 在默认模式下仅允许一个配置（即指定的 PUT 和其它默认参数），因此在调度时不需要做任何决策。

但对于更高级的模糊测试器，如 BFF 和 AFLFast，其成功的重要因素之一正是它们所采用的创新调度算法（scheduling algorithms）。

本节将仅讨论黑盒和灰盒模糊测试中的调度算法；而白盒模糊测试中的调度涉及复杂的符号执行机制，因此不在本节范围之内。

简而言之，调度是模糊测试中一个核心的问题，尤其是在面对大量种子、输入路径或配置选项时，它决定了下一个 “值得尝试” 的目标，对漏洞发现效率有重要影响。

4.1 FCS 问题

调度的目标是分析当前可用的关于配置的信息，并选择一个最有可能带来最优结果的模糊测试配置。例如，目标可能是：

  • 发现尽可能多的独特漏洞；
  • 最大化当前生成输入所能达到的程序覆盖率。

从本质上讲，每一个调度算法都面临一个经典问题：探索 vs 利用（exploration vs. exploitation）冲突。

  • 探索（explore）：将时间花在了解不同配置的行为，以获取更准确的信息，从而在未来做出更好的决策；
  • 利用（exploit）：优先选择当前看来最 “有希望” 产出漏洞或提高覆盖率的配置，尽快获得实际结果。

Woo 等人将这个固有冲突称为模糊测试配置调度问题（Fuzz Configuration Scheduling，FCS）。

在模型模糊测试器（Model Fuzzer）中，Schedule函数通过以下因素选择下一次要执行的配置：

  1. 当前的模糊测试配置集合C；
  2. 当前已用时间t elapsed；
  3. 总时间预算t limit。

该配置将被用于下一次模糊测试运行。需要注意的是，Schedule仅负责做出选择决策。而支持该决策所需的信息，则通过Preprocess和 ConfUpdate函数来更新配置集合C获得。

换句话说，调度算法基于动态更新的状态信息进行决策，其本质在于权衡试探新的路径（探索） 与深入已有路径（利用） 的收益。

4.2 黑盒 FCS 算法

在黑盒环境下，FCS 算法唯一可用的信息是配置的模糊测试结果——即通过该配置发现的崩溃数何漏洞数，以及在该配置上花费的时间。

Householder 和 Foote 是最早研究如何在 CERT BFF 黑盒变异模糊器中如何利用这些信息。他们提出：一个配置如果在过去运行中具有更高的成功率（bugs / runs）应该更优先考虑。实际上，在将 BFF 中原本采用的均匀采样调度算法替换之后，他们在对 ffmpeg 进行的 500 万次测试运行中观察到 85% 的独特崩溃（unique crashes）数量提升，这表明更先进的 FCS 算法具有显著的潜力。

不久之后，Woo 等人在多个方面改进了上述思想：

  1. 改进的数学建模：他们将黑盒变异模糊测试从中的伯努利试验序列模型，转变为未知权重的加权集邮员问题（Weighted Coupon Collector’s Problem with Unknown Weights，WCCP/UW）。

    • 前者假设每个配置都有一个固定的最终成功概率，并在测试过程中逐步学习；
    • 后者则显式维护该概率的一个上界，并考虑其随时间的衰减。

  2. 引入多臂老虎机（MAB）算法：WCCP/UW 模型自然引导他们研究多臂老虎机（Multi-Armed Bandit）问题中的算法——这是决策科学中广泛用于解决探索与利用冲突的一个经典框架。基于此，他们设计了 MAB 算法，能够有效利用那些成功率尚未明显衰减的配置。

  3. 引入“单位时间成功率”：他们还观察到，在其他条件相同的情况下，一个模糊测试运行速度更快的配置，要么可以更快收集更多独特漏洞，要么可以更快地降低其未来成功率的上界。这一观察促使他们将配置的成功率按时间进行归一化处理，从而使运行更快的配置更具吸引力。

  4. 调整调度机制：最后，他们将 BFF 中原本按“每次调度固定运行次数（BFF 中称为 epoch）”的方式，替换为“每次调度固定运行时间”。 这一改变意味着：BFF 不再被迫在某个运行缓慢的配置上花费过多时间，可以更灵活地重新选择配置。

通过结合上述策略，Woo 等人在实验中展示：在相同时间预算下，找到的唯一漏洞数量提高了 1.5 倍，相较于原始 BFF 实现具有显著改进。

4.3 灰盒 FCS 算法

在灰盒环境中，FCS 算法可以选择使用更丰富的信息来描述每个配置，例如：该配置在进行模糊测试过程中所达到的路径覆盖率。AFL 是该类别中的先驱，其核心基于进化算法（Evolutionary Algorithm, EA）。直观地说，进化算法会维护一个配置种群（population），每个配置都有一定的 “适应度”（fitness）值。算法会选择适应度高的配置，对其进行遗传变换，如变异（mutation）和重组（recombination）等遗传操作来生成后代配置，这些后代可能成为新的测试配置。基本假设是：这样的新配置更可能具有高适应度。

要理解 FCS 在 EA 框架中的运作机制，我们需要定义：

  1. 什么样的配置才是“适应的”；
  2. 如何选择这些配置；
  3. 如何使用选中的配置。

从较高层次的抽象来看，AFL 在多个同时探索某个控制流边（control-flow edge）的配置中，会优先选择运行最快、输入最小的那个作为“favorite”（喜爱）。AFL 维护一个配置队列，基本上是以循环队列的方式来选取下一个适应的配置。选中配置后，AFL 对其进行模糊测试，测试次数基本固定。

从 FCS 的视角来看，AFL 对运行速度快的配置的偏好，与中黑盒设置的做法是一致的。

最近，Böhme 等人提出的 AFLFast 在上述三个方面对 AFL 进行了改进：

  • 适应度判定标准改进：

    1. 对于某个控制流边，AFLFast 优先选择 “被选择次数最少” 的配置。这使得多个配置在该边上轮流被探索，从而增强了探索性；
    2. 如果出现并列，AFLFast 进一步选择 “执行了最少次数的路径” 的配置。这增强了对 “稀有路径”（rare paths）的覆盖，有助于发现更多未观察到的行为。

  • 调度策略改进：

    • 与 AFL 的轮转调度（round-robin）不同，AFLFast 根据优先级（priority）来选择下一个适应配置。
    • 优先级由以下决定：
      • 被选中次数越少 → 优先级越高；
      • 如果相同，则执行的路径越稀有 → 优先级越高。
    • 这种策略在本质上也是为了提升对 “适应配置” 的探索能力和稀有路径的测试频率。

  • 能量分配（power schedule）改进：

    • AFLFast 对选中的配置执行变次数的模糊测试，次数由其 “FAST 能量分配策略” 决定：
      • 初期给予配置较小的 “能量”，鼓励广泛探索；
      • 随后指数级地增加，快速提升对潜力配置的利用。
    • 此外，还会根据产生的执行相同路径的输入数量对能量进行归一化处理，从而鼓励对 “较少模糊测试过的路径” 进行更多探索。

这些改进带来了显著效果：在一项 24 小时的实验中，Böhme 等人发现 AFLFast 发现了 3 个 AFL 无法发现的漏洞，并且在另外 6 个 AFL 和 AFLFast 都能发现的漏洞中，AFLFast 的发现速度平均快了 7 倍。

此外，AFLGo 在 AFLFast 的基础上进一步改进了优先级分配机制，使其能够定向到特定的程序位置。而 QTEP 则利用静态分析来推断程序二进制中可能更 “易出错” 的部分，并优先对这些部分进行覆盖。

0x05 输入生成

由于测试用例的内容直接决定了是否会触发漏洞，因此输入生成技术自然成为 fuzzer 设计中最具影响力的决策之一。传统上，fuzzer 通常被划分为生成式（generation-based）和变异式（mutation-based）。

  • 生成式 fuzzer 根据给定的模型生成测试用例，该模型描述了 PUT 所期望的输入格式。本文将此类 fuzzer 称为基于模型的模糊器（model-based fuzzers）。

  • 变异式模糊 fuzzer 则通过对已有的种子输入（seed input）进行变异来生成测试用例。变异式 fuzzer 通常被认为是无模型的（model-less），因为种子只是示例输入，即使种子数量很多，也无法完整覆盖被测程序所期望的输入空间。

在本节中，我们将基于测试用例生成机制（InputGen）来解释并分类模糊测试器中使用的各种输入生成技术。

5.1 基于模型的 Fuzzer

基于模型的 fuzzer会根据给定的模型生成测试用例，该模型描述了 PUT 可能接受的输入或执行方式。例如：

  • 精确描述输入格式的语法规则（grammar）
  • 较不精确的约束条件，例如用于标识文件类型的魔数（magic）。

5.1.1 预定义模型

一些 fuzzer 使用用户可用配置的模型。例如：

  • Peach、PROTOS 和 Dharma 接收用户提供的输入规范；
  • Autodafé 、Sulley 、SPIKE 和 SPIKEfile 提供 API，使分析人员可以构建自己的输入模型；
  • Tavor 接收使用扩展巴科斯-诺尔范式（EBNF）编写的输入规范，并根据对应语法生成测试用例。

类似地，一些网络协议模糊器，如 PROTOS、SNOOZE、KiF 和 T-Fuzz，也接收用户提供的协议规范。

针对内核 API 的 fuzzer 通常以系统调用模板的形式定义输入模型。这些模板一般会指定一个系统调用所期望的参数数量与类型。将模型用于内核模糊测试的想法最早由 Koopman 等人提出，他们的开创性工作比较了不同操作系统在面对一组手动挑选的系统调用测试用例时的健壮性。

还有一些基于模型的模糊器专门面向特定的编程语言或语法，这些模糊器将该语言的模型内置在自身中：

  • cross_fuzz 和 DOMfuzz 会随机生成文档对象模型（DOM）对象；
  • jsfunfuzz 基于自身内置的语法模型，生成随机但语法正确的 JavaScript 代码；
  • QuickFuzz 利用 Haskell 中已有的描述文件格式的库来生成测试用例；
  • 一些网络协议模糊器（如 Frankencerts、TLS-Attacker、tlsfuzzer 和 llfuzzer）专为特定网络协议（如 TLS 和 NFC）设计了协议模型；
  • Dewey 等人提出了一种方法，使用约束逻辑编程（Constraint Logic Programming）生成不仅语法正确，而且语义上具有多样性的测试用例；
  • LangFuzz 会解析一组种子输入，提取出代码片段，并通过随机组合这些片段以及用它们变异原始种子来生成测试用例。由于提供了语法模型，LangFuzz 始终生成语法正确的代码。它被应用于 JavaScript 和 PHP；
  • BlendFuzz 基于与 LangFuzz 相似的思路，但目标是 XML 和 正则表达式解析器。

5.1.2 推断模型

相比依赖预定义逻辑或用户提供的模型，自动推断模型（Inferred Model）的研究近年来逐渐受到关注。尽管关于输入格式和协议的自动逆向工程已有大量研究成果，但目前仅有少数 fuzzer 将这些技术应用于实际测试中。模型推断通常可以分为两个阶段进行：预处理阶段或配置更新阶段。

预处理阶段中的模型推断

一些模糊测试器在启动模糊测试前，先对目标程序进行分析以推断输入模型：

  • TestMiner ：利用程序代码中的信息来挖掘并预测适合的输入。
  • Skyfire ：基于数据驱动方法，从已有语法和输入样本中生成一组语义上有效的新种子。与以往方法不同，Skyfire 的目标是生成“语义正确”的新种子集合。
  • IMF ：通过分析系统 API 日志，学习内核 API 的使用模型，并根据推断结果生成调用这些 API 的 C 语言代码。
  • Neural 和 Learn&Fuzz ：使用神经网络为基础的机器学习方法，从给定的测试文件集中学习输入模型，并基于该模型生成新的测试用例。
  • Liu ：提出了一个类似的方法，但专注于文本输入的建模。

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

另一些模糊测试器会在每轮测试中持续更新输入模型：

  • PULSAR ：从程序产生的一组网络数据包中自动推断出网络协议模型。它内部构建状态机，并识别哪些消息标记（token）与状态相关联，然后利用这些信息生成新的测试用例，以探索更多状态。
  • Doupé 等人：通过观察 Web 服务的输入输出行为，推断出其状态机，并据此检测 Web 漏洞。
  • Ruiter 等人：与上述方法类似，针对的是 TLS 协议，其实现基于 LearnLib。
  • GLADE：从一组输入/输出样本中合成上下文无关文法（CFG），并利用该文法对目标程序进行模糊测试。

5.2 基于变异的 Fuzzer

传统的随机测试方法在生成满足特定路径条件的测试用例方面效率较低。例如，考虑一个简单的 C 语句：if (input == 42)。如果 input是一个 32 位整数，那么随机猜中正确输入值的概率是 1/2³²。这个问题在处理结构良好的输入（如 MP3 文件）时会变得更加严重。随机测试几乎不可能在合理时间内生成一个有效的 MP3 文件作为测试用例。

因此，MP3 播放器大多会在解析阶段就拒绝这些随机生成的测试用例，从而无法触达程序的更深层逻辑。

这个问题促使研究者采用基于种子的输入生成方法以及白盒测试方法。大多数无模型模糊测试器会使用一个“种子”（即输入到被测试程序 PUT 的初始输入）来通过变异生成测试用例。种子通常是由被测程序所支持的、结构良好的输入，如文件、网络数据包或一系列用户界面事件。

通过只变异一个有效文件的一部分，往往可以生成一个 “基本有效但包含异常值” 的新测试用例，从而可能触发被测程序的崩溃。种子的变异方法多种多样，以下将介绍几种常见的变异方式。

5.2.1 字节翻转

比特翻转是许多基于变异的 fuzzer 常用的一种技术。一些 fuzzer 简单地翻转固定数量的比特，而另一些则随机决定翻转的比特数量。为了随机变异种子，一些 fuzzer 使用一个可由用户配置的参数，称为 “变异比例”（mutation ratio），它决定了每次输入生成操作中要翻转的比特位数量。假设一个 fuzzer 希望从一个 N 位的种子中随机翻转 K 位，那么变异比例就是 K/N。

SymFuzz 等研究表明，模糊测试性能对变异比例非常敏感，且不存在一个对所有 PUT 都有效的最优比例。有若干种方法可以找到一个好的变异比例。BFF 和 FOE 使用指数缩放的一组变异比例对每个种子进行测试，并为那些在统计上更有效的比例分配更多的迭代次数。SymFuzz 借助白盒程序分析来推断一个合适的变异比例。但需要注意的是，该方法只考虑推断一个全局最优的变异比例。事实上，同时使用多个变异比例可能比使用单一最优比例更有效，而这仍是一个尚未解决的研究问题。

5.2.2 算数变异

AFL 和 honggfuzz 包含一种将选定字节序列视为整数并对其进行简单算术运算的变异操作。计算后的值会用于替换原始字节序列。其核心思想是用一个小数值范围来控制变异的影响。例如，AFL 从种子中选取一个 4 字节值，将其视为整数 i，然后用i ± r替换该值，其中r是一个随机生成的小整数。r 的范围因模糊器而异，通常是用户可配置的。在 AFL 中，默认范围是 0 ≤ r < 35。

5.2.3 基于块的变异

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

  1. 在种子的随机位置插入一个随机生成的块；
  2. 从种子中随机删除一个块；
  3. 用随机值替换一个随机选定的块；
  4. 随机打乱一组块的顺序；
  5. 通过附加一个随机块来调整种子的大小；
  6. 从一个种子中提取一个随机块，并用于插入或替换另一个种子中的随机块。

5.2.4 基于字典的变异

一些模糊器使用一组预定义的、有潜在语义意义的值（如 0 或 -1）以及格式字符串进行变异。例如，AFL 、honggfuzz 和 LibFuzzer 在变异整数时会使用像 0、-1 和 1 这样的值。Radamsa 使用 Unicode 字符串，而 GPF 使用格式化字符（如%x和%s）来变异字符串。

5.3 白盒 Fuzzer

白盒模糊测试器也可以分为基于模型或无模型两类。例如，传统的动态符号执行与基于变异的模糊测试一样，不需要任何模型；但一些符号执行器则使用输入模型（如输入语法）来指导符号执行过程。

尽管许多白盒模糊器，包括 Godefroid 等人提出的开创性工作，都使用动态符号执行来生成测试用例，但并非所有白盒模糊器都是动态符号执行器。一些模糊器利用白盒程序分析技术获取有关 PUT（被测程序）可接受输入的信息，然后与黑盒或灰盒模糊测试结合使用。

在本小节的其余部分，我们将基于其底层的测试用例生成算法，对现有的白盒模糊测试技术进行简要总结。请注意，除非某些动态符号执行器明确自称为“模糊器”，否则我们故意不将它们归入模糊器的范畴。

5.3.1 动态符号执行

从高层次来看，传统的符号执行使用符号值作为程序输入，这些符号值表示所有可能的取值。在执行过程中，它不会对输入进行具体求值，而是建立符号表达式。每当遇到条件分支指令时，程序就会在概念上分叉为两个符号解释器：一个探索分支为真的路径，另一个探索分支为假的路径。

对于每一条路径，符号解释器会构建一个路径公式（path formula 或 path predicate），用于记录执行过程中所遇到的每一个分支条件。若某一条路径的路径公式是可满足的（satisfiable），即存在某个具体输入可以触发该路径，那么可以通过查询 SMT 求解器来生成满足该路径公式的具体输入。

动态符号执行是传统符号执行的一个变体，它同时进行符号执行与具体执行（concrete execution）。其思想是，具体执行状态有助于降低符号约束的复杂性。

5.3.2 引导模糊测试

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

  1. 通过代价较高的程序分析获取有关 PUT 的有用信息；
  2. 利用这些信息指导测试用例的生成。

这类方法在表 1（第 9 页）的第六列中有标注。

例如，TaintScope [201] 使用细粒度污点分析来找到“热点字节”（hot bytes），即会流向关键系统调用或 API 调用的输入字节。类似的想法也被其他安全研究者提出过。

Dowser [91] 在编译期间执行静态分析，以基于启发式规则识别可能包含漏洞的循环，尤其是那些包含指针解引用的循环。然后，利用污点分析来计算输入字节与候选循环之间的关系。最后，Dowser 执行动态符号执行，但仅将关键字节视为符号值，以此提升性能。

VUzzer [164] 和 GRT [132] 结合使用静态与动态分析技术，从 PUT 中提取控制流和数据流特征，并使用这些特征来指导输入生成。

Angora [50] 对“热点字节”思想进行了改进，它使用污点分析将每个路径约束与对应的输入字节关联起来，然后执行类似梯度下降算法的搜索策略，引导变异过程去满足这些路径约束。

5.3.3 PUT 变异

模糊测试中的一个实际挑战是绕过校验和验证（checksum validation）。例如，当被测程序在解析输入前会对其计算校验和，模糊器生成的大多数测试用例会因此被拒绝。

为应对此挑战，TaintScope [201] 提出了感知校验和的模糊测试技术。该方法通过污点分析识别校验和验证指令，并修改 PUT 来绕过校验逻辑。当模糊测试发现一个程序崩溃点时，它会对该输入生成正确的校验和，从而构造出能够触发崩溃的有效测试用例，适用于未修改的 PUT。

Caballero 提出了称为拼接式动态符号执行（stitched dynamic symbolic execution）的技术，用于在存在校验和的情况下生成测试用例。

T-Fuzz 将这一思想扩展到使用灰盒模糊测试突破各种条件分支。它首先建立一组非关键性检查（NCC，Non-Critical Checks），这些是可以转换而不改变程序逻辑的分支条件。当模糊测试停止发现新路径时，T-Fuzz 会选择一个 NCC，进行变换，并重新开始模糊测试。

最终，当在修改后的程序中发现崩溃时，T-Fuzz 会使用符号执行在原始程序中还原该崩溃点。

0x06 输入评估

在输入被生成后，模糊测试器会执行该输入，并决定如何处理它。由于模糊测试的主要目标是发现安全策略的违规行为，因此模糊测试器必须能够检测执行过程中是否违反了安全策略。该策略的具体实现被称为 Bug 预言机（bug oracle，记为 Obug）（参见第2.1节）。被预言机标记的输入通常会在分诊（triage）后写入磁盘。如算法1所示，预言机会在每次生成输入后被调用，因此预言机必须高效地判断输入是否违反了安全策略。

回顾第3节，一些模糊测试器在每次输入执行时还会收集额外信息以改进模糊过程。Preprocess 和 InputEval 在许多模糊测试器中是紧密耦合的，因为经过 instrument 的被测程序（PUT）在执行时会输出额外的信息。

6.1 执行优化

在我们的模型中，每一次模糊测试迭代被认为是按顺序执行的。如果采用最直接的实现方式，每次迭代都需重新加载待测程序（PUT, Program Under Test），这将带来大量重复的启动开销。

为加快这种重复加载的过程，现代模糊测试器提供了多种优化机制：

  • AFL 使用了 forkserver 技术： 每次模糊迭代通过从一个已初始化的父进程 fork 新进程来避免重复加载，从而显著加快迭代速度。
  • 内存中模糊测试（In-memory fuzzing）：通过将待测程序完全加载到内存中并直接在内存中执行，有效避免磁盘 I/O 和初始化开销。

无论采用哪种机制，其核心目的都是将加载与初始化 PUT 的开销在多次迭代中摊销，从而提升整体模糊测试效率。

此外，Xu 等人 进一步通过设计一个替代 fork() 的新系统调用，进一步降低每轮迭代的开销。

我们的模型将每次模糊测试迭代视为顺序执行。最直接的实现方式是，每次迭代都从头加载被测程序（PUT）。但这种重复加载过程开销巨大，因此现代模糊器引入了优化机制，跳过重复加载步骤。例如：

6.2 Bug Oracles

模糊测试中最常用的安全策略是假设：凡是以致命信号终止的程序执行都视为违反策略。这类策略能够发现大量内存相关漏洞，因为非法内存访问往往会导致段错误（segfault）或中止。其优势是实现简单、效率高，操作系统能够在无额外 instrument 的情况下捕捉到异常行为。

但该策略并不能检测所有已触发的内存漏洞。例如，若栈缓冲区溢出覆盖了一个指针但该值是合法地址，程序可能不会崩溃，而是产生错误输出，模糊器将无法察觉。为缓解这一问题，研究者提出了一些高效的程序转换工具来检测不安全行为并使程序中止，这些工具通常被称为 sanitizers（检测器）。

  • 内存与类型安全
    • 空间错误（spatial errors）：当指针被访问到超出其合法范围的区域时发生（如缓冲区溢出、下溢）。
    • 时间错误（temporal errors）：当指针在失效后仍被访问时发生（如 use-after-free）。
    • 时间错误（temporal errors）：当指针在失效后仍被访问时发生（如 use-after-free）。
    • MEDS：基于 64 位虚拟地址空间，改进 ASan，通过引入 redzones 进一步提升检测能力。
    • SoftBound/CETS：通过为每个指针关联边界和时间信息，可理论上检测所有空间与时间错误，但开销较高（116%）。
    • CaVer、TypeSan、HexType：在编译期插桩以检测 C++ 中的不安全类型转换（bad casting），比如将基类对象错误地转换为派生类对象。CaVer 可扩展至浏览器应用，性能开销 7.6%–64.6%。
    • CFI（Control Flow Integrity，控制流完整性）：检测运行时的非法控制流转移，部分实现已集成进主流 gcc 和 clang 编译器。
  • 未定义行为
    • C 语言包含大量未定义行为，其处理方式取决于编译器实现、优化级别、体系结构等，这可能导致漏洞。
    • MSan（Memory Sanitizer）：在编译期插桩，检测未初始化内存的使用，平均性能开销约 150%。
    • UBSan（Undefined Behavior Sanitizer）：检测多种未定义行为，如空指针解引用、除零、整数溢出等。
    • TSan（Thread Sanitizer）：检测多线程程序中的数据竞争，精度与性能之间有所权衡。
  • 输入验证
    • Web 安全漏洞（如 XSS、SQL 注入）较难检测，因为需要理解复杂的解析器。
    • KameleonFuzz [68]：通过浏览器解析输入，分析 DOM 树并匹配特定模式以检测 XSS。
    • μ4SQLi：使用数据库代理拦截应用与数据库的通信，检测 SQL 注入。
  • 语义差异检测
    • μ4SQLi：使用数据库代理拦截应用与数据库的通信，检测 SQL 注入。
    • Jung 等人提出黑盒差分模糊测试，通过观察输出差异来检测信息泄露。

6.3 分类

分类（Triage） 是对触发违规的测试用例进行分析和报告的过程，可分为三个步骤：

  1. 去重（Deduplication）
  2. 优先级排序与可利用性评估（Prioritization & Exploitability）
  3. 测试用例最小化（Test Case Minimization）

6.3.1 去重

去重是指删除触发相同漏洞的重复测试用例，最终 ideally 保留的集合中每个测试用例对应一个独立漏洞。去重的意义：

  • 避免浪费存储和资源。
  • 帮助使用者快速了解漏洞数量及类型。
  • 攻击者或防御者可以聚焦在“高价值”的漏洞。

常见去重方式：

  • 堆栈回溯哈希（Stack Backtrace Hashing）
    • 最常用方法之一，通过记录崩溃时的调用栈并生成哈希来分组。
    • 实现差异：使用的栈帧数量（1、3、5、无限），包含信息的多少（函数名、地址、行号等）。
    • 局限：某些漏洞（如堆溢出）可能在不同位置才触发崩溃，导致误分类。
  • 基于覆盖率的去重（Coverage-based Deduplication）
    • 由 AFL 引入：如果崩溃执行覆盖了新的边缘，或者遗漏了之前崩溃覆盖过的边缘，则认为是新的崩溃。
  • 语义感知去重（Semantics-aware Deduplication）
    • RETracer ：通过反向数据流分析找出导致错误指针的源头，并将其归因于特定函数，从而实现更精确的聚类。

6.3.2 优先级和可利用性评估

也称 fuzzer 驯服问题（taming problem）。目的是根据漏洞严重性与独特性对测试用例排序。

  • 可利用性（Exploitability）：描述漏洞是否可能被实际利用。
  • Microsoft 的 !exploitable [137]：基于启发式与简化污点分析，将漏洞分为：
    • EXPLOITABLE
    • PROBABLY_EXPLOITABLE
    • UNKNOWN
    • NOT_LIKELY_EXPLOITABLE
  • 类似工具还有：GDB 的 exploitable 插件 [76]，Apple 的 CrashWrangler。

6.3.3 测试用例最小化

目标：找出触发违规所必需的输入部分，并生成一个更小、更简洁但仍能触发漏洞的测试用例。

  • BFF [45]：包含专门为模糊测试设计的最小化算法。
  • AFL [211]：通过逐步将字节置零、缩短输入长度来简化用例。
  • Lithium [167]：通用最小化工具，通过逐步删除相邻数据块来缩减文件。
  • 其他测试用例缩减器：如 Delta Debugging [216]，以及针对特定格式的工具（如 C-Reduce [166] 针对 C/C++ 源码）。特定格式的工具虽然适用范围有限，但由于理解语法，效率更高。

0x07 配置更新

ConfUpdate 函数在区分 黑盒、灰盒 与 白盒模糊测试器的行为上扮演了关键角色。正如算法 1 所示，ConfUpdate 可以根据当前模糊测试过程中收集的配置信息和执行信息，修改配置集 C。黑盒模糊测试器不会执行除调用漏洞预言机 O bug 之外的任何程序内省，因此它们通常保持 C不变，因为它们没有收集到能够支持修改配置集合的信息。

然而，灰盒和白盒模糊测试器的主要区别就在于它们更复杂的 ConfUpdate 实现，这使得它们能够引入新的模糊配置，或移除已经过时的旧配置。ConfUpdate使得一次迭代中收集到的信息能够传递到未来的所有迭代中。例如，白盒模糊测试器中的路径选择启发式通常会为每一个新生成的测试用例创建一个新的模糊配置。

相比之下，灰盒与白盒模糊测试器的 ConfUpdate 实现更为复杂：

  • 它们可以 添加新的模糊配置（例如基于覆盖率路径），或
  • 移除已经被覆盖或无效的旧配置。

ConfUpdate 的功能使得一次迭代中收集的信息能够传递到后续所有迭代中使用。

例如，白盒模糊测试器中常见的路径选择启发式方法会针对每一个新生成的测试用例创建一个新的模糊测试配置，从而实现更系统性的路径探索。

7.1 进化种子池更新

进化算法(EA)是一种基于启发式的方法，涉及生物进化机制，如突变、重组和选择。虽然EA看起来非常简单，但它构成了许多灰盒模糊器的基础。他们维持一个种子库，这是EA在模糊活动中进化的人口。选择要突变的种子的过程和突变本身分别在§4.3和§5中有详细说明。

可以说，EA 最重要的步骤是向配置集C中添加一个新配置，这对应于模糊测试的confuupdate步骤。大多数fuzzers通常使用节点或分支覆盖作为适应度函数:如果测试用例发现了新的节点或分支，则将其添加到种子池中。AFL更进一步，考虑了一个分支被占用的次数。安哥拉通过考虑每个分支的调用上下文，改进了AFL的适应度标准。除了进化种子库的代码覆盖率外，Steelix 还检查了哪些输入偏移会影响PUT比较指令的进度。

VUzzer 只有在发现一个新的非错误处理基本块时才会在C语言中添加一个配置。他们的见解是在程序分析中投入时间，以获得特定于应用程序的知识，从而提高EA的有效性。具体来说，VUzzer定义了每个基本块的权值，配置的适应度是配置的对数的加权和在每个行是的基本块上的频率。VUzzer 具有内置的程序分析功能，可将基本块分为正常块和错误处理块（EH）。根据经验，他们的假设是，遍历EH块表明漏洞的可能性较低，因为错误可能是由于未处理的错误而发生的。对于一个正常的块，它的权重与根据VUzzer定义的转移概率在包含该块的CFG上随机行走访问它的概率成反比。对于EH区块，其权重为负，是基本区块数量与该配置所运行的EH区块数量之间的比例。实际上，这使得VUzzer更倾向于执行正常块的配置，而上述随机漫步认为正常块是罕见的。

7.2 维护最小集合

具备创建新模糊测试配置的能力同时也带来了一个风险：可能会生成过多的配置。
为缓解这一风险，一个常见的策略是维护一个 最小集（minset），即在 覆盖率指标最大化 的前提下，保留最少量的测试用例集合。

最小集的构建也常在预处理（Preprocess）阶段执行。

有些模糊测试器在更新配置时，会使用针对性更强的最小集变种策略。例如：

  • Cyberdyne 直接移除不在最小集中的配置；
  • 而 AFL 则采用“剔除策略（culling procedure）”，将属于最小集的配置标记为“优选（favorable）”。

被标记为“优选”的模糊配置在调度函数（Schedule）中被赋予显著更高的选中概率。 AFL 的作者指出，这种机制“在队列轮换速度和测试用例多样性之间提供了合理的平衡”。

0x08 总结

本文的提炼出了现代模糊测试文献的全面而连贯的观点。首先提出了一个通用模型模糊测试器，以方便解释当前使用的多种形式的模糊测试。然后，使用图 1 和表 1 说明了模糊测试器的丰富分类。通过讨论设计决策以及展示整个社区的许多成就来探索模型模糊测试的每个阶段。