【论文精读】| 综述：模糊测试的艺术、科学和工程（下）

在综述《模糊测试：艺术、科学与工程（上）》中，着重探讨了模糊测试的分类及其工作流程中的预处理和调度算法。本篇文章将重点介绍测试用例的生成策略、测试与评估方法、测试过程中的分流策略，以及反馈迭代机制，带领大家深入了解更多关于模糊测试的内容。

测试用例生成策略

生成测试用例是模糊测试过程中一个关键环节，它直接决定了测试的有效性以及是否能够成功发现缺陷。模糊测试工具主要分为两类：基于生成和基于变异。

1.基于生成的模糊测试工具

基于生成的模糊测试工具采用详尽模型创建测试用例，这些模型准确描述了应用程序期望的输入格式。描述可能涵盖输入格式的精确语法，或定义文件类型的特定标识符等更模糊的约束条件。

此类工具模拟目标应用的输入结构以生成测试数据，尤其适用于对结构化数据（例如网络协议或文件格式）的测试。此方法在维持格式或协议规范的基础上变异数据，探寻潜在缺陷。

例如，测试音频播放器如何处理 MP3 文件时，基于模型的测试生成符合 MP3 格式规范的数据，并在某些字段引入异常或非标准值，以检测播放器的错误处理能力和安全性。

基于生成的模糊测试的一大挑战是确保模型的准确与全面。模型需要精确地描述输入结构以产生有效的测试用例，同时广泛涵盖各种输入变量，这需要对目标应用的输入格式有深入的了解和分析。

其主要方法分为三类：预定义模型、自动推断模型以及编码器模型。

1）预定义模型

众多模糊测试工具，如 Peach、PROTOS 和 Dharma，依靠用户定义的预设模型工作。这些工具允许用户根据编写的规范来定制输入模型。同时，Autodafé、Sulley 和 SPIKE 等其他工具提供 API，支持用户根据需求自定义输入模型。例如，Tavor 允许使用扩展的巴科斯-诺尔范式（EBNF）编写规范，以生成遵循特定语法的测试用例。在网络协议测试方面，如 PROTOS 和 SNOOZE 这样的工具，要求用户提供详细的协议规范。进行内核 API 测试时，通常需要依据系统调用模板来定义输入模型。工具如 Nautilus 采用基于语法的方法来生成测试用例，并通过对种子数据的优化修剪，以提升测试效率。

2）自动推断模型

近期，自动推断模型的使用在模糊测试工具中变得越发普遍，诸如 TestMiner、Skyfire、IMF、CodeAlchemist、Neural 及 Learn&Fuzz 等工具，通过在预处理和反馈更新阶段对输入模型进行分析、学习和推断，减轻了对预设模型的依赖并提升了测试用例生成的自动化水平。

● 在预处理阶段进行的模型推断：工具在模糊测试启动前，通过分析目标程序或其相关数据来推断输入模型。例如，TestMiner 通过分析被测程序数据来预测适当的输入；Skyfire 采用数据驱动策略，从特定种子和语法中推导出概率性上下文敏感语法；IMF 分析系统 API 日志以掌握核心 API 模型；CodeAlchemist 解析 JavaScript 代码为模块，并定义模块间的组合约束；Neural 与 Learn&Fuzz 利用基于神经网络的方法从测试数据中学习模型。

● 测试过程中通过反馈更新进行的模型推断：工具利用测试迭代后生成的数据更新和优化输入模型，促使测试过程动态调整，实现精细化探索。例如，PULSAR 根据捕获的网络数据包推测网络协议模型；Doupé等研究人员观察 I/O 行为以推断 Web 服务状态机；Ruiter 等研究人员则专注于 TLS 的相关工作；GLADE 通过分析 I/O 样本合成上下文无关文法；go-fuzz 为加入种子池的每个种子构建模型。

3）编码器模型

模糊测试经常被应用于检测解码器程序，这类程序用于解析各种特定文件格式。这些文件格式的编码器程序，实际上可被视为文件格式的隐式模型。MutaGen 是一款独特的模糊测试工具，它通过利用这些编码器程序内的隐式模型生成新的测试用例。不同于大部分基于变异的模糊测试工具仅变异测试用例，MutaGen 直接变异编码器程序本身。具体操作是，MutaGen 计算编码器程序的动态程序切片并执行之，以此为手段，通过轻微调整程序切片来改变编码器的行为，进而生成包含小缺陷的测试用例。

2.基于变异的模糊测试工具

基于变异的模糊测试法是一个在处理需结构化输入的软件测试中特别高效的方法。通过对已知良质的输入（即种子）做出小范围且受控的修改，它能够产生新的测试用例，目的是发现软件潜在的错误或漏洞。

挑战在于变异种子：对结构良好的输入，例如 MP3 文件，随机生成一个满足软件特定路径条件的有效测试用例非常难。以一个简单的条件判断为例，if (input == 42)，如果 input 是一个 32 位整数，那么随机猜到正确的 input 值的机率只有 1/2^32。因此，通过采用种子文件和变异策略，基于变异的模糊测试能有效提升产生有效测试用例的几率。

基于变异的模糊测试工具通常使用以下几种变异策略：

1.比特翻转：随机选择种子文件的一个或多个比特位并翻转。这个简单但有效的方法能模拟数据传输错误或损坏。

2.字节替换：随机或选择性地替换种子文件中的字节，这些替换的值可以是随机产生的，或来自特定测试集合。

3.块变异：在种子文件中插入、删除或替换数据块，既可以是随机生成的，也可以是源自文件其他部分的数据块。

4.魔术值替换：用一系列预定义的“魔术值”替换文件中特定的数据，这些魔术值常是导致软件异常处理的特定数字或字符串。

5.格式化字符串：在种子输入中加入格式化字符串，试图触发格式化字符串的漏洞。

6.模糊增量：对数值做微小增加或减少，试图引发边界条件的错误。

3.基于白盒的模糊测试工具

白盒模糊测试，作为一种有效的软件测试策略，依赖于对程序内部结构信息的深入了解来产生测试用例。这类测试工具根据其所采用的技术，主要分为两大类：基于生成的工具与基于变异的工具。在白盒模糊测试领域，有三种先进技术特别值得注意：动态符号执行、引导模糊测试以及对待测程序的变异技术。

1）动态符号执行（Concolic Testing）

动态符号执行，亦称具体与符号测试（concolic testing），融合了传统符号执行与具体执行的优势。此技术采用符号值运行程序，并为遇到的每个条件分支建立路径公式，然后利用 SMT 求解器来检查这些路径公式的满足情况，以产生具体的输入值。动态符号执行的主要优点是它能降低符号约束的复杂度并提升路径覆盖率。由于需对程序指令进行细致分析，其执行速度较慢。为提高效率，常用策略包括缩小分析范围及结合灰盒模糊测试技术。Driller、Cyberdyne 和 QSYM 等工具展现了动态符号执行在实践中的应用，优化了灰盒与白盒模糊测试的结合，提升了测试的效率及成果。

2）引导模糊测试

引导模糊测试结合了程序分析技术（无论是静态还是动态）与模糊测试，以增强测试用例的生成效能。此方法先对程序进行分析，捕获关键信息，然后基于这些信息生成更有针对性的测试用例。

● TaintScope 通过细粒度污点分析识别影响关键系统调用的输入字节（热字节），以生成更有效的测试用例。

● Dowser 结合静态分析和污点分析寻找可能的错误循环，并确定输入字节与这些循环的关系，最后利用动态符号执行以提升性能。

● VUzzer 和 GRT 通过静态与动态分析技术提取程序的控制流和数据流特征，引导测试用例生成。

● Angora 和 RedQueen 分析种子执行情况来降低分析成本，Angora 关联路径约束与输入字节，并采用梯度下降法优化变异策略，RedQueen 则通过插装比较操作来检测输入使用方式，以解决约束。

3）待测程序变异与校验绕过

模糊测试面对的一大挑战是如何有效绕过待测程序内置的校验和验证机制，这些机制通常在输入数据被实际处理前执行，导致某些测试用例由于不满足特定条件而被提前排除，限制了模糊测试探索程序潜在漏洞的范围。以下三种先进技术通过对待测程序进行智能变异，有效绕过内置检查机制，提升测试用例生成效率和发现潜在漏洞的能力。

● 校验和感知模糊测试：TaintScope 引入了一种新颖的“校验和感知模糊测试”解决方案。利用污点分析技术，精准识别执行校验和计算的代码指令，并修改这些指令以绕过校验和验证，使得修改后的测试用例亦能被程序接受处理。若程序崩溃，它能生成与正确输入校验和匹配的测试用例，为未修改的程序生成有效数据。

● 拼接动态符号执行：Caballero 等提出了“拼接动态符号执行”技术，特别适合处理包含校验和验证的场景，通过动态符号执行技术生成能绕过校验和验证的测试用例，提升模糊测试的有效性及覆盖范围。

● TFuzz 的非关键检查（NCC）方法：TFuzz 在灰盒模糊测试领域扩展了这一思路，首先标识所谓的非关键检查（NCC）分支，即那些可以修改而不影响程序主逻辑的条件分支。当发现新路径停滞时，TFuzz 会修改一个 NCC 并重新进行模糊测试。如果修改后的程序版本发现崩溃，TFuzz 尝试通过符号执行技术在原程序上复现崩溃，以验证其有效性。

测试与评估

在模糊测试过程中，首步是创建一批测试用例，然后由模糊测试器执行这些用例并对其结果进行评价，此步骤被称为输入评估。虽然模糊测试的一大优点在于它能够以简单直接的方式执行待测程序（PUT），但进行输入评估阶段的优化和设计选择对于增强测试工具的效率和效果具有至关重要的作用。

1.Bug Oracle 机制

糊测试采用的一种核心安全策略是把程序由于致命信号（如段错误）引起的意外终止看作违规行为。这种方法有效地识别出各类内存漏洞，这些漏洞通常会引发段错误或导致程序非正常终止。此策略的主要优点在于其高效率和简易实施——无需对操作系统进行特殊配置就能捕捉这类异常。

但是，这个传统的崩溃侦测策略无法捕捉到所有种类的内存漏洞。例如，在堆栈缓冲区溢出导致堆栈上的指针被替换为另一个合法内存地址的情况下，程序可能会正常终止，即使输出结果不正确，模糊测试在这种情况下可能识别不出问题。为解决这个问题，研究者们开发了多种高效的程序转换技术，这些技术可以检测到不安全或异常的程序行为，并相应地终止程序。这些技术通常称为“sanitizers”。

1）内存错误侦测工具

内存错误侦测工具主要针对两大类安全问题：空间错误与时间错误。空间错误包括缓冲区溢出或下溢，发生于指针解引用越过其目标对象边界的情形。时间错误发生在对象销毁后，指针还尝试访问那个内存位置，如使用已释放的内存。典型的内存错误侦测工具包括：

● 地址检查器（ASan）：一个编译时插桩工具，能快速侦测空间与时间错误，通常会导致约 73%的运行时间开销增加。ASan 通过阴影内存技术，在内存被解引用前检验其有效性，有效地识别不安全内存访问。MEDS 通过创建“红区”增强了 ASan，这些不可访问区域提升了程序崩溃的可能性，从而改进了错误侦测。

● SoftBound/CETS：不同于 ASan，这个工具在编译时追踪指针的边界和生命周期信息，能理论上侦测所有空间和时间错误，但带来了约 116%的运行时间开销。

● CaVer、TypeSan 与 HexType：专注于侦测 C++中的不当类型转换，比如错误地把基类对象转换为派生类对象。

2）未定义行为侦测工具

在 C 语言等编程语言中，许多未定义行为的具体实施可能因编译器而异。程序员的代码可能仅在某一编译器上有效，看似无害，实则编译器的实现方式可能由多种因素影响，包括优化设置、系统架构和编译器版本。编译器实现与程序员预期不一致时，可能引发漏洞。典型的未定义行为侦测工具包括：

● 内存检查器（MSan）：专门侦测 C 和 C++中使用未初始化内存导致的未定义行为。MSan 利用阴影内存追踪每个位的初始化状态，但导致约 150%的性能开销。

● 未定义行为检查器（UBSan）：通过编译时修改程序侦测多种未定义行为，如使用不对齐指针、零除法、解引用空指针和整数溢出等。

● 线程检查器（TSan）：侦测数据竞争的工具，通过编译时修改程序，在精确性与性能间取得平衡。数据竞争一般发生于两线程并发访问同一内存位置且至少一线程执行写操作，可能导致数据损坏且难以复现。

3）Web 漏洞侦测工具

● KameleonFuzz：专门侦测跨站脚本（XSS）攻击的工具，通过解析真实 Web 浏览器中的测试用例、提取 DOM 树，并与 XSS 攻击模式比较，来识别成功的 XSS 攻击。

● µ4SQLi：采用类似技术侦测 SQL 注入。鉴于难以从 Web 应用响应中可靠侦测 SQL 注入，它通过数据库代理拦截 Web 应用与数据库间通信，检查输入是否触发有害行为。

4）语义差异侦测工具

差分测试在模糊测试中扮演发现语义错误的关键角色，通过比较行为相似但不完全相同的程序揭露潜在错误。多种模糊测试工具通过差分测试识别程序间行为差异，这些差异通常标示着错误。Jung 等提出了针对单个程序的黑盒差分模糊测试技术，通过分析不同输入处理及相应输出的变异，有效侦测信息泄露等问题。

2.测试优化策略

在本分析模型中，我们假定模糊测试的各轮迭代顺序执行。通常做法是，每启动一个新的迭代周期，就需要重新加载待测试程序（PUT）。然而，通过执行一些优化措施，可以大幅减少重复加载的需求。比如，AFL 通过引进 fork-server 机制，使得可以从一个进程的已初始化状态开始，为每一轮新的模糊测试创建一个分支（fork）。同样，实施基于内存的模糊测试也可以显著加快测试执行速度。不管采用何种优化策略，重复的加载及初始化待测试程序的开销都能在多轮迭代中被有效地分摊。徐等人通过设计一种新的系统调用来取代传统的 fork()调用，从而进一步减少了每轮迭代的成本。

测试过程中的分流策略

在测试流程中，分流策略关键地参与到分析和上报违反预定策略的测试用例中，涵盖三个主要环节：去除重复的测试用例、对测试用例进行优先级排序、以及最小化测试用例。

1.测试用例去重

去重在模糊测试过程中发挥着至关重要的作用，其目标是剔除那些触发同一错误的重复测试用例，从而形成一个能揭示独特错误的测试用例集合。这一步骤不仅有利于节约磁盘空间和资源，而且帮助用户更加轻松地识别和分析不同的错误类型，特别是对于那些仅对可能导致可靠利用的严重漏洞感兴趣的攻击者而言，这一点尤为重要。

目前广泛采用的去重技术有三种：

1）基于栈回溯哈希去重：这种方法通过捕获崩溃时的调用栈回溯和分配栈哈希来实现去重，其实现细节可能包括不同的栈帧数量和信息量。为了提升效率，某些实现会产生一个主要哈希和一个更精确的次级哈希。

2）基于覆盖率去重：工具如 AFL 通过源代码插桩来记录测试用例发现的新路径或者未覆盖的已知崩溃路径，把这类崩溃当作独一无二处理。

3）基于语义感知去重：RETracer 利用逆向数据流分析技术从崩溃事件中提取语义信息以进行分群，分析崩溃转储来审查导致崩溃的指针，识别出触发错误的具体指令，目标是识别并将崩溃归类到负责的最高级别函数。

2.优先级设置与漏洞可利用性分析

在模糊测试过程中进行的优先级排序，亦称为“驯服问题”，主要是基于测试用例展示的漏洞的严重性及其独特性进行排序或归类。这一点在寻找内存漏洞时格外重要，漏洞的可利用性决定了攻击者是否能够制定出有效的利用代码来利用这些漏洞。因此，防御方通常优先修补那些可被利用的漏洞，而这些漏洞同样是攻击者极其关注的焦点。

微软的!exploitable 系统引领了结合启发式算法与污点分析对崩溃可利用性进行评估的趋势。自从!exploitable 面世以后，随之而来的是其他基于规则的启发式系统，比如 GDB 的可利用性插件以及苹果的 CrashWrangler。尽管如此，这些系统的准确度还没有经过系统性的研究与评估来验证。

3.测试用例最小化过程

测试用例最小化是模糊测试分流过程中的关键步骤，其主要目标是识别并减简能够触发错误的测试用例，从而创造出能触发相同错误的更小且更精简的原始测试用例版本。虽然它在减小输入规模的目的与种子修剪相仿，但测试用例最小化更侧重于根据错误指示进行最小化处理。

各种模糊测试工具实施了不同的实现方式和算法以进行测试用例最小化。如，BFF 利用了一个为模糊测试特制的最小化算法，目的是尽量减少与原始种子文件之间的差异。AFL 也提供了测试用例最小化功能，通过将字节置零和缩减测试用例的长度来实现测试用例的简化。进一步，Lithium 是一种通用的测试用例最小化工具，旨在通过指数级减小尺寸，移除测试用例中的连续行或字节“块”，非常适合处理由脚本模糊测试生成的复杂测试用例。

除了专为模糊测试设计的工具之外，还存在适用于模糊测试发现的测试用例的通用缩减工具，如适用于多种格式的格式无关技术 delta 调试，及针对特定格式的专用技术，例如 CReduce 是专门用于 C/C++文件的。虽然这些专用技术在处理文件类型上受限，但由于它们能够理解目标语法，通常比通用技术更高效。

反馈迭代机制

反馈机制在区分黑盒、灰盒与白盒模糊测试工具的行为上扮演了关键角色。这种能力确保在模糊测试的一个迭代周期中收集到的信息，能够被后续所有迭代所利用。举例来说，与黑盒和灰盒模糊测试工具相比，白盒模糊测试工具通常会针对每个新生成的测试用例创建新的模糊配置，原因是它们生成的测试用例数量相对较少，但信息收集与反馈利用的过程更加精细和深入。

1.种子池的进化更新策略

模糊测试中的进化算法（EA）通过持续维护和更新一个充满潜力的种子集合，即种子池，对模糊测试的发展起到了至关重要的作用。虽然 EA 的概念相对直接，但它构成了众多灰盒模糊测试工具的核心。

在基于 EA 的模糊测试中，节点或分支覆盖率常被用作评估适应度的函数。新发现的节点或分支会导致相应的测试用例被添加到种子池中。考虑到可达路径的数量远远超过种子的数量，种子池旨在作为一个代表所有可达路径的多样化集合，映射出被测程序的探索状态。值得一提的是，不同大小的种子池可能实现相同的覆盖率。

EA 模糊测试工具通常采用优化适应度函数的方法，以便捕捉更细致的改进指标。例如，AFL 通过追踪分支的访问频率来精细化适应度函数。STADS 引入了生态统计框架，以预测持续模糊测试可能揭示的新配置数量。其他策略包括测量复杂分支条件满足程度的比例，如 LAF-INTEL 将多字节比较分解成多个分支，以便观察新种子在中间字节比较中的表现。LibFuzzer、Honggfuzz、go-fuzz 及 Steelix 通过插桩所有比较操作，将有助于推动比较进展的测试用例加入种子池。Steelix 还额外分析了影响比较指令的输入位置。Angora 通过分析每个分支的调用上下文来优化 AFL 的适应度评价标准。

作为一个基于 EA 的工具，VUzzer 的适应度函数基于专门的程序分析来确定每个基本块的权重，首先对基本块进行分类，区分为常规块或错误处理块，并按基本块访问概率的反比分配权重，鼓励对那些较少访问的块给予优先考虑。

这些种子池的进化更新策略提升了模糊测试工具的效率和有效性，使其能够更精准地识别和探索潜在的漏洞路径。

2.维护最优测试用例集

在模糊测试中，随着测试配置生成能力的提升，面临的一个挑战是避免生成过多的测试配置。为此，采用了一种策略，即维持所谓的“最小集合”，这意味着尽可能保持一个小型的测试用例集合以达到最大的覆盖范围。这个最小集合的思想不仅在模糊测试的执行阶段有所应用，而且在预处理阶段也同样采纳。

特定的模糊测试工具采取了方法来优化更新过程中的最小集合。以 AFL 为例，它实施了一种修剪流程，将属于最小集合的测试配置标记为优选项。因此，这些被视为有益的测试配置将有更高的机会被选中执行。AFL 的开发者指出，这种策略有效地平衡了测试队列的循环速度与测试案例的多样性。

通过这种方法，能够在保持测试的深度和广度的同时，有效地控制测试用例的数量，提升模糊测试的效率与成效。这一最小集合维护策略有助于聚焦于那些可能揭示潜在漏洞的关键测试用例，从而优化测试结果。

总结

本文旨在提供一个有关模糊测试技术的全面观察。尽管先前的诸多研究已经探讨了模糊测试的各个特定方面，但这些研究通常聚焦于有限的领域。相比之下，本文目标在于对模糊测试领域的现有文献进行全方位梳理，涵盖模糊测试技术的最新动态，分析不同模糊测试技术以及它们在多样化应用背景下的测试表现。

原作者：论文解读智能体

润色：Fancy

校对：小椰风