模糊测试的艺术、科学和工程综述

本次分享论文为：The Art, Science, and Engineering of Fuzzing: A Survey (模糊测试的艺术、科学和工程：一项调查)

基本信息

原文作者: Valentin J.M. Manes, HyungSeok Han, Choongwoo Han, Sang Kil Cha, Manuel Egele, Edward J. Schwartz, and Maverick Woo

作者单位: 韩国KAIST网络安全研究中心, Naver公司，波士顿大学，卡内基梅隆大学

关键词: Software Security, Automated Software Testing, Fuzzing (软件安全，自动化软件测试，模糊测试)

原文链接： https://arxiv.org/abs/1812.00140v4

开源代码：不涉及

论文速读

论文简介：本研究深入调查了模糊测试领域，旨在创建一份全面的路线图，对模糊测试中存在的问题及其解决策略进行系统性的梳理和分析，以帮助初学者和资深开发者深入理解模糊测试技术。

论文背景: 在计算机系统的安全领域内，软件安全问题不容忽视。模糊测试作为一种有效的技术，已经被证明是检测程序安全漏洞的关键方法之一。

过去的方案：虽然模糊测试在挖掘安全漏洞方面极为有效，但该领域仍面临诸多挑战，如稀疏的缺陷空间、对有效输入空间的严格要求以及自动化处理多样化目标的困难。

研究动机：本文的目标是探索和弥补模糊测试领域中的知识空缺，通过全面回顾和分析该领域面临的挑战及其潜在的解决策略，明确未来研究的方向。同时为初学者提供模糊测试的基本知识和现有的解决方法，并且向有经验的开发人员介绍三个主要的研究领域，鼓励他们通过深入探索至少其中一个领域，以促成技术上的重大突破。

引言

自20世纪90年代初引入以来，模糊测试已发展成为一项关键技术，用于发现软件安全漏洞。这种方法是通过向程序输入可能包含语法或语义错误的数据来不断执行的过程。实际应用中，攻击者常用模糊测试生成攻击代码和进行渗透测试。以2016年的DARPA网络大挑战（CGC）为例，参赛团队也利用模糊测试增强了他们的网络推理系统。这促使防御方采用模糊测试，以期望能在攻击者之前发现漏洞。Adobe、Cisco、Google和Microsoft等著名公司已将模糊测试整合入他们的安全开发流程。近年来，安全审计人员和开源开发者也开始使用模糊测试来评估商业软件包的安全性，从而为终端用户提供了一定的安全保障。

模糊测试的社区极为活跃，持续扩展。GitHub目前托管了超过一千个相关的开源项目。研究文献不仅记录了大量模糊测试工具的开发，而且在主要安全会议上，相关研究的数量也在持续增加。互联网上充满了关于模糊测试成功案例的博客，其中一些案例被视为值得长期保存的学术资料。

本文通过提出模糊测试的统一模型和对现有文献的分类，旨在提供一个全面且一致的视角来审视模糊测试领域。并且本文深入讨论了模糊测试的设计决策、创新点、相关文献调查以及所面临的重要权衡问题，同时指出了术语的多样性和比较不同工具的挑战。为推动该领域的研究进展，文章强调了整合和精炼模糊测试技术的重要性。总的来说，本文全面总结了模糊测试在软件安全和测试领域的基本概念、技术手段以及发展趋势。

研究范围

本次研究全面审视了2008年1月至2019年2月间，在模糊测试领域内，主要学术会议上发布的所有相关文献。这包括四个在安全领域具有显著声誉的会议和三个在软件工程领域具有重要影响的会议，具体如下：

• 安全领域会议：

a.ACM计算机与通信安全会议（CCS）

b.IEEE安全与隐私研讨会（S&P）

c.网络与分布式系统安全研讨会（NDSS）

d.USENIX安全研讨会（USEC）

• 软件工程领域会议：

a.ACM软件工程基础国际研讨会（FSE）

b.IEEE/ACM自动化软件工程国际会议（ASE）

c.国际软件工程会议（ICSE）

选定这些会议的理由是它们在各自的领域内享有极高的声誉和广泛的影响。此外，本研究还考虑了其他一些被认为与模糊测试高度相关的出版物，以此扩展研究的覆盖范围。为了聚焦模糊测试的主要议题，本研究设定了一个明确的准则：包含“Fuzzing”一词的文献都被纳入考量。这种做法使得研究不仅集中于模糊测试这一核心技术，同时也广泛梳理了该领域的文献，保证了研究的全面性和深入性。

图一：模糊测试相关总结

表一：模糊测试相关总结

模糊测试

一、模糊测试分类

模糊测试根据测试者对被测软件内部结构的了解程度和访问权限的不同，可分为黑盒、白盒和灰盒模糊测试。

• 黑盒模糊测试：这是最基础的测试形式，其中测试者几乎不了解软件的内部工作原理。测试完全基于对软件外在行为的观察，无需访问源代码。通过向软件输入异常或随机数据，测试者观察软件反应，以识别潜在漏洞。该方法简单、直接，能够迅速对软件进行广泛测试，但可能无法探测到更深层的复杂安全问题。

• 白盒模糊测试：与黑盒测试相反，测试者可以完全访问软件的内部逻辑和源代码。通过应用程序分析技术，如静态代码分析和动态执行跟踪，白盒测试能够系统地深入探测软件行为。这种方法能够识别由特定代码路径触发的漏洞，提供更高的测试覆盖率和深入的安全评估，但要求测试者具有较高的专业知识和较大的资源投入。

• 灰盒模糊测试：结合了黑盒和白盒测试的优势，测试者对软件的内部信息有限了解，无需完全的代码访问权限。灰盒测试依赖于对部分代码结构的知识，如通过程序插桩收集运行时的反馈信息，来指导测试用例的生成。这种方法既保持了黑盒测试的灵活性和快速性，又通过有限的内部视角提升了测试的效率和有效性。

二、模糊测试工作流程

在实际应用中，模糊测试的工作流程如下：

1. 预处理：

在开始模糊测试流程之前，许多模糊测试工具需要执行一系列预处理步骤。这些步骤主要涉及对目标程序的插桩，目的是去除潜在的冗余配置，优化种子集，并创建能有效触发应用程序的测试样例。此外，预处理阶段还包括为接下来的输入生成（即输入生成阶段）做好准备，建立必要的模型。

1.1 程序插桩：

程序插桩分为静态和动态两种类型。静态插桩在程序运行前的预处理阶段进行，通常作用于源代码或中间代码，并在编译时完成。这种方式的优势在于，因为处理是在运行前完成的，所以运行时的开销相对较低。如果程序依赖库文件，这些库也需进行插桩，通常是通过使用相同技术重新编译实现的。除了源代码，也有针对二进制代码的静态插桩工具。

相比之下，动态插桩虽然运行时开销更大，但它可以在程序运行时方便地对动态链接库进行插桩。当前，有多种著名的动态插桩工具，如DynInst、DynamoRIO、Pin、Valgrind和QEMU。

模糊测试工具可能支持一种或多种插桩技术。比如，AFL既可以在源代码级别通过修改编译器实现静态插桩，也可以利用QEMU在二进制级别进行动态插桩。在采用动态插桩时，AFL提供两种选项：一是默认情况下只对目标程序的可执行代码进行插桩；二是通过启用AFL_INST_LIBS选项，对目标程序及其所有外部库代码进行插桩。虽然后者能增加代码的覆盖范围，但也可能扩大AFL对外部库函数的测试范围。

1) 执行反馈

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

2) 内存中模糊测试

在测试大型程序时，为了降低执行成本，有时只针对程序的特定部分执行模糊测试，避免在每次模糊测试迭代中重新启动进程。例如，对于那些处理输入可能需要几秒钟的复杂应用程序（如GUI程序），一种有效的方法是在GUI初始化完成后为被测试程序创建一个内存快照。在执行新的测试用例之前，先从这个快照恢复内存状态。这种方法同样适用于需要频繁客户端-服务器交互的网络应用，被称为内存中模糊测试。例如，GRR模糊测试工具会在加载任何输入前创建一个快照，以省略不必要的启动步骤。而AFL通过引入名为fork server的技术，来减少每次模糊测试迭代的进程启动成本，虽然这与内存中模糊测试有着相似的目的，但fork server为每个测试迭代创建一个新的进程。

有的模糊测试工具（如AFL）在每次迭代后不会重置被测试程序的状态，而是持续对内存中的特定函数进行模糊测试，这被称为内存中API模糊测试。例如，AFL的“持久模式”允许在不重启进程的情况下，在一个循环中持续执行API模糊测试。在此模式下，AFL不考虑函数在同一执行过程中被多次调用可能产生的副作用。

虽然内存中API模糊测试效率较高，但测试结果的可靠性可能受到影响，因为内存中发现的错误（或崩溃）可能难以复现，原因包括：构建目标函数的有效调用上下文并非总是可行，以及跨多次函数调用可能累积的未捕获副作用。内存中API模糊测试的成功很大程度上依赖于选择合适的入口点函数，而找到合适的函数是一大挑战。

3) 线程调度和条件竞争漏洞

条件竞争漏洞的触发通常很困难，主要是因为它们依赖于偶尔发生的非确定性行为。不过，通过对程序进行插桩以及显式地控制线程调度，研究者可以引发多种非确定性的程序行为，这有助于检测到这类漏洞。研究已经显示，采用随机线程调度的方法同样可以有效地揭露条件竞争漏洞。

1.2 种子选择：

在模糊测试过程中，调控模糊算法的行为通过设置一系列配置参数来实现是一种常见做法。特别地，在基于变异的模糊测试中，所使用的种子文件有广泛的选择范围。例如，在对一个接收MP3文件的MP3播放器进行模糊测试时，从无限的有效MP3文件中选择合适的种子文件变成了一个挑战，这就是所谓的种子选择问题。

为了解决这个问题，研究人员开发了多种方法和工具。一个常用的策略是寻找能最大化特定覆盖度量（如节点覆盖率）的最小化种子集合，这个过程被称为计算minset。例如，如果一个配置集合C包括了种子文件s1和s2，它们覆盖了不同的程序地址。如果第三个种子文件s3能够覆盖s1和s2的所有地址，并且执行效率相当，那么仅使用s3进行测试将是更理想的选择，因为它能在更短的时间内测试更多的程序逻辑。这一理论得到了米勒研究的支持，该研究表明，代码覆盖率每提高1%，漏洞发现率就会增加0.92%。此外，这种策略还可以作为测试过程中的一个反馈更新机制，特别适合于那些可以持续添加新种子的模糊测试工具。

在实际应用中，模糊测试工具采用了多种覆盖度量标准。例如，AFL根据分支覆盖率来定义minset，并使用对数计数器来区分不同的分支。而Honggfuzz则通过执行指令数、分支数和独立基本块数来衡量覆盖率，这使得测试器可以将执行时间较长的路径考虑进minset，有助于发现服务拒绝或性能相关的问题。

1.3 种子裁剪：

种子文件的大小对模糊测试的效率有直接影响，其中较小的种子文件能显著降低内存消耗并提高测试的吞吐量。因此，减小种子文件大小的过程，即种子修剪，成为了模糊测试准备阶段的一个重要环节。这个过程可以在模糊测试的预处理阶段、测试循环开始之前，或作为测试过程中的配置更新环节进行。

AFL是一个著名的模糊测试工具，它应用种子修剪技术，通过迭代使用与代码覆盖率相关的工具来修剪种子，确保修剪后的种子保持了相同的覆盖范围。Rebert等研究者的成果进一步证实了种子修剪的有效性，他们发现使用最小尺寸算法选出的小种子，相比随机选取的种子，能更有效地降低唯一错误的发生率。特别是在针对Linux系统调用处理程序的模糊测试中，MoonShine工具对syzkaller进行了扩展，实现了在保持静态分析识别出的调用依赖性的同时减少种子文件的大小。

1.4 驱动程序：

在直接对目标应用进行模糊测试遇到障碍时，开发专用的驱动程序成为了一个行之有效的策略。这种方法一般在模糊测试的初期阶段手动执行，并且通常仅需完成一次。例如，针对库文件的模糊测试需要一个专门设计的驱动程序来调用库中的函数。同理，为了测试内核，内核模糊测试工具可能通过模糊测试特定的用户级应用程序来间接实现。IoTFuzzer便是使用此策略的一个例证，它通过让驱动程序与相应的智能手机应用通信，实现对物联网设备的模糊测试。

2.调度算法

在模糊测试的领域内，调度是一个决定下一轮模糊测试迭代将采用哪些配置的过程，这些配置的具体内容取决于使用的模糊测试工具。简单的模糊测试工具，比如zzuf，在默认模式下仅使用一个配置，几乎不涉及调度选择。而更复杂的模糊测试工具，如BFF和AFLFast，其成功在很大程度上归功于它们采用的创新调度算法。本文着重讨论针对黑盒和灰盒模糊测试的调度算法；对于涉及更复杂配置的白盒模糊测试调度，可以参阅专门的文献进行深入了解。

调度问题的定义：调度策略旨在利用现有配置信息选择最有可能产生优秀结果的配置，这可能是指发现更多的独特漏洞或达到更全面的输入集合覆盖。每个调度策略都需要在探索（获取更多信息以指导将来的决策）和利用（集中使用当前最有效的配置进行测试）之间寻找一个平衡点。Woo及其团队将这种平衡的追求称为模糊配置调度问题（Fuzz Configuration Scheduling, FCS）。

2.1 黑盒模糊测试的调度算法优化

优化黑盒模糊测试侧重于分析测试结果，如发现的崩溃和错误数量，及测试耗时。Householder和Foote首次在CERT BFF的黑盒变异模糊测试中研究了使用这类数据进行调度的方法。他们提出了一种基于高成功率（错误数与运行次数的比例）配置的优先选择策略。通过实证研究，他们发现将BFF中的均匀采样策略替换为先进的调度算法，使得在对ffmpeg进行的500万次测试中独特崩溃数增加了85%，证明了高级调度算法的有效性。

Woo及其团队进一步发展和优化了这一方法。他们首先把黑盒变异模糊测试的数学模型从Bernoulli试验序列改为带未知权重的加权优惠券收集问题（WCCP/UW），允许在成功概率下降时仍保持概率的上限，而非假设每个配置有固定的成功率。接着，他们采用多臂老虎机（MAB）问题算法——一种流行的决策科学方法，用于平衡探索与利用——设计出更精细处理未见概率下降配置的MAB算法。他们还发现，与其他因素相比，运行速度更快的配置能更快地发现独特错误或降低成功概率的上限，因此对成功概率按时间消耗进行了归一化，偏好速度更快的配置。最终，他们将BFF的选择策略从固定模糊迭代次数调整为固定时间量，避免在低效配置上浪费过多时间。这些优化的结合，使得在相同的测试时间内，发现的独特错误数量提高了1.5倍，标志着与现有BFF实施相比的显著改进。

2.2 灰盒模糊测试的调度算法优化

灰盒模糊测试通过利用包括代码覆盖率在内的丰富信息来优化调度。在这一领域，AFL通过进化算法（EA）来领先。EA维护着一个配置种群及其适应度值，并通过基因操作如变异和重组来产生可能更优适的后代配置。

EA框架的调度算法核心包括三个主要方面：(i) 确定配置的适应度，(ii) 配置选择方法，(iii) 选中配置的应用方式。AFL认为那些涉及控制流边缘、且输入既快速又小的配置是最适合的（称为“favorite”），并在配置队列中循环选用这些适应配置进行模糊处理，偏好于快速配置的策略并不局限于灰盒环境。

Böhme等研究者对AFL进行了重大改进，创造了AFLFast。AFLFast引入了两个新标准来确定“favorite”路径：偏好选择被遍历次数较少的控制流边缘（以增强探索）和在条件相同的情况下选择执行次数较少的路径（以探索更罕见的路径）。此外，AFLFast通过优先级来改进配置选择机制，优先选择选择次数少或路径执行次数少的配置。AFLFast还采用了一种功率调度策略，显著提升了模糊处理的效率，在24小时的测试中找到了AFL未发现的错误，并在其他错误发现上实现了7倍的速度提升。

AFLGo、Hawkeye、FairFuzz和QTEP分别在特定方面进一步扩展和优化了AFLFast，包括针对特定程序位置进行优先级调整、利用静态分析改善种子调度和输入生成、使用变异掩码引导执行触及罕见分支，以及基于静态分析来确定二进制文件中问题区域的策略。

关于模糊测试测试用例生成策略、测试与评估、测试过程中的分流策略和反馈迭代机制将在[论文精读] 综述：模糊测试的艺术、科学和工程（下）中为大家解析，敬请期待，欢迎关注！

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

测试用例生成策略

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

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

校对：小椰风

声明：本文来自安全极客，版权归作者所有。文章内容仅代表作者独立观点，不代表安全内参立场，转载目的在于传递更多信息。如有侵权，请联系 anquanneican@163.com。