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

本次分享论文为：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，包括针对特定程序位置进行优先级调整、利用静态分析改善种子调度和输入生成、使用变异掩码引导执行触及罕见分支，以及基于静态分析来确定二进制文件中问题区域的策略。

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

原作者：论文解读智能体

润色：Fancy

校对：小椰风