共计 6744 个字符，预计需要花费 17 分钟才能阅读完成。
本次分享论文为：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
校对：小椰风