模糊测试的乐趣

调试技术日臻完善。

Stefan Nagy，由 Peter Alvaro 引言

实践研究汇集了数字图书馆（世界上最大的计算机科学研究文库）的资源以及会员的专业知识。“实践研究”专栏的共同目标是在学术界人士及其在业界的同行之间分享阅读计算机科学研究的乐趣和实用性。

在本期“实践研究”中，我们邀请了犹他大学卡勒特计算学院的助理教授 Stefan Nagy 提供帮助。我们想感谢 John Regehr（他之前曾为 RfP 撰稿）的引荐。

Stefan 将带领我们回顾软件模糊测试的最新研究，即通过生成新颖或意外的输入来系统地测试程序。他讨论的第一篇论文通过属性测试技术推断出的“可能的程序不变式”的语义概念，扩展了覆盖引导模糊测试（根据程序语法衡量测试进度）的最新技术。第二篇论文探讨了将关于某些错误类别（例如，释放后使用错误）的特定领域知识编码到测试用例生成中。他的最后一个选择带我们深入探讨，随机生成完整的 C 程序，并使用差异分析来比较优化和未优化执行的跟踪，以便在编译器本身中查找错误。

我从阅读这些论文中学到了很多，希望您也能如此。

—Peter Alvaro

实践研究：模糊测试的乐趣

Stefan Nagy

模糊测试（fuzz-testing 的简写）或许是历史上最成功的自动化软件错误和漏洞发现技术。模糊测试的核心工作流程很简单：（1）生成大量测试用例；（2）在目标程序上运行每个用例并观察发生了什么；然后（3）按观察到的执行行为（例如，崩溃、代码覆盖率、超时等）对测试用例进行分组，保留那些表现出某种“有趣”行为的用例（尽管“有趣”在这里的含义完全取决于您）。

在过去的几十年中，模糊测试经历了显著的演变：从最初的粗糙、蛮力测试策略发展成为当今最复杂且至关重要的技术之一，用于大规模发现关键安全漏洞。尽管到目前为止，已经有无数篇令人惊叹的模糊测试论文——而且每年都有越来越多的论文发表——但本期“实践研究”着眼于过去两年中三篇特别创新和鼓舞人心的论文。

超越仅覆盖率的模糊测试

Andrea Fioraldi、Daniele Cono D'Elia 和 Davide Balzarotti。“使用可能的程序不变式作为模糊测试器的反馈。” 第 30 届 Usenix 安全研讨会论文集，2021。

https://www.usenix.org/conference/usenixsecurity21/presentation/fioraldi

当今大多数实际应用中的模糊测试都采用最大化代码覆盖率的反馈策略：仅保存覆盖先前未见目标代码的输入并对其进行变异，理想情况下是为了创建新的增加覆盖率的输入。您可以将其想象成赛马，目标是从以前的获胜者中培育出未来几代的获胜者——增加覆盖率的输入。然而，由于覆盖引导模糊测试器只关注扩大其代码覆盖率的范围，它们通常会错过隐藏在已覆盖代码中的许多错误。

为了克服仅覆盖率模糊测试的探索限制，这篇 2021 年 Usenix 论文使用属性测试的语义不变式来增强模糊测试：一组关于程序变量预期状态的“规则”。例如，以下断言语句

assert(x < 5)

要求变量 x 小于 5；如果违反此不变式，程序将发出信号，表明此变量已进入异常状态。然而，自动挖掘不变式通常会带来大量的误报和噪声。天真地跟踪每个可能的不变式既会用过多的反馈压倒模糊测试器，又会因每个不变式的工具开销而降低其吞吐量。

为了缓解这种情况，作者重放了先前生成的模糊测试输入——这是利用通常丢弃的模糊测试数据的好方法——并引入了一组启发式方法来修剪不可能违反、冗余和其他错误的不变式。然后，这些最终的不变式都配备了一个检查，以向模糊测试器发出任何违规信号。

通过结合不变式和覆盖率反馈，作者的方法帮助模糊测试器比仅代码覆盖率发现更多的程序状态——在仅覆盖率模糊测试的基础上，以可忽略不计的 8% 开销揭示了多出 34-56% 的错误。

由于仅覆盖率的模糊测试遗漏了如此多的错误，因此不变式引导的模糊测试很可能很快成为 AFL++ 和 libFuzzer 等流行模糊测试框架中的一流模式。尽管作者的实现仅支持源代码可用的目标，但二进制提升、翻译和重写方面的进步让我充满希望，不变式引导的模糊测试技术将很快扩展到更难模糊的闭源软件和系统。

针对特定漏洞定制模糊测试

Manh-Dung Nguyen、Sébastien Bardin、Richard Bonichon、Roland Groz 和 Matthieu Lemerre。《用于释放后使用漏洞的二进制级定向模糊测试》。第 23 届国际攻击、入侵和防御研究研讨会 (RAID 2020)。 https://www.usenix.org/conference/raid2020/presentation/nguyen

模糊测试器设计中的一个主要挑战是平衡错误查找速度和广度。尽管覆盖引导的模糊测试可以快速暴露缓冲区溢出等唾手可得的错误，但其最大化覆盖率的搜索在触发需要复杂程序状态（例如，时间内存安全违规）的错误时无效。先前改进通用错误发现的尝试探索了更细粒度的代码覆盖率级别（例如，n-gram 控制流边），但由于其更高的工具开销和覆盖率簿记成本，通常会降低模糊测试速度。因此，提高软件安全性不仅需要强大的通用模糊测试器，还需要专门针对某些漏洞类别的模糊测试器。

这篇 RAID 2020 论文介绍了一种针对释放后使用漏洞的定向模糊测试技术——释放后使用漏洞是一类危险的时间内存安全错误，当程序尝试访问先前释放的内存区域时会发生。通用模糊测试器通常难以合成触发释放后使用错误所需的一系列程序事件：（1）分配；（2）释放；以及（3）访问。为了克服这个问题，作者设计了一种定向模糊测试策略，按顺序命中这些函数调用——有效地结合了时间意识来引导模糊测试探索这些漏洞。

毫不奇怪，作者的方法在释放后使用漏洞方面取得了巨大成功：与现有的时间无关的定向模糊测试器相比，查找已知的释放后使用错误的速度快了两倍，同时还在 Perl 和 MuPDF 等经过良好模糊测试的程序中发现了 11 个新的释放后使用错误。

尽管作者的原型以二进制可执行文件为目标，但序列定向模糊测试很容易扩展到源代码可用的模糊测试目标，以及其他时间错误（例如双重释放）。我预计，通过结合通用方法和针对错误的定制方法，将有更多机会改进模糊测试。

将模糊测试应用于其他问题

Giuseppe Antonio Di Luna、Davide Italiano、Luca Massarelli、Sebastian Österlund、Cristiano Giuffrida 和 Leonardo Querzoni。《谁在调试调试器？揭示优化二进制文件中的调试信息错误》。第 26 届国际编程语言和操作系统体系结构支持会议 (ASPLOS 2021) 论文集。

https://dl.acm.org/doi/10.1145/3445814.3446695

许多部署后质量保证任务依赖于调试信息（例如，DWARF）：编译器发出的可执行代码到其更高级别源代码表示（例如，变量、类型、指令等）的映射。调试信息中的差异（缺失或不相关的工件）通常是由开发工具链中的细微错误引起的，并因编译器激进的优化而加剧。防止开发人员因处理不当的调试信息而误入歧途需要有效的自动化方法来发现现代开发工具链中的这些隐藏错误。

这篇 ASPLOS 2021 论文介绍了一个基于差异分析的调试信息模糊测试框架：随机生成 C 程序，并比较其优化和未优化版本的调试跟踪以查找差异。对于他们的差异分析，作者形式化了一组跟踪不变式，规定优化的二进制文件在执行期间的任何时候都应与其未优化版本的调试跟踪中存在的调试信息（例如，变量、函数和源代码行）保持一致性。

在此之后，作者对引起差异的测试用例进行分类，以确定错误发生的位置——要么在编译器发出调试信息时，要么在调试器解析和解释调试信息时。作者将其自动化模糊测试技术应用于各种广泛使用的软件开发工具链。

总的来说，作者的差异模糊测试方法展示了令人印象深刻的有效性：在 LLVM、GNU 和 Rust 编译器/调试器工具链中发现了 34 个调试信息错误——其中十几个报告的问题已被确认为已修复。由于验证调试信息的正确性仍然是模糊测试的一个相当新的应用，我预计未来的模糊测试器将改进本文中的技术，以更加严格地审查开发工具链。此外，我乐观地认为，差异模糊测试的力量将为其他重要的错误类别、软件和系统产生有用的策略。

祝您模糊测试愉快！

Peter Alvaro 是加州大学圣克鲁兹分校的计算机科学副教授，在那里他领导 Disorderly Labs 研究小组 (disorderlylabs.github.io)。他的研究重点是使用以数据为中心的语言和分析技术来构建和推理数据密集型分布式系统，以使其可扩展、可预测，并且能够可靠地应对大规模分布中固有的故障和不确定性。他在加州大学伯克利分校获得博士学位，师从 Joseph M. Hellerstein。他是国家科学基金会职业奖、Facebook 研究奖、Usenix ATC 2020 最佳演示奖、SIGMOD 2021 杰出 PC 奖和 UCSC 卓越教学奖的获得者。

Stefan Nagy (https://www.cs.utah.edu/~snagy/) 是犹他大学卡勒特计算学院的助理教授。他于 2022 年在弗吉尼亚理工大学获得计算机科学博士学位，并于 2016 年在伊利诺伊大学厄巴纳-香槟分校获得计算机科学学士学位。他在软件和系统安全领域的研究广泛旨在为计算中不透明和其他具有挑战性的领域实现高效且有效的质量保证。

最初发表于《Queue》第 20 卷，第 6 期——
在数字图书馆中评论本文

更多相关文章

Alpha Lam - 使用远程缓存服务于 Bazel
远程缓存服务是一项新的发展，可以显著节省运行构建和测试的时间。它对于大型代码库和任何规模的开发团队特别有用。Bazel 是一个积极开发的开源构建和测试系统，旨在提高软件开发的生产力。它有越来越多的优化措施来提高日常开发任务的性能。