关于模糊测试的一些思考

前言

这篇博客有点特别，它实际上是我在回应 fuzzbench 项目第 654 号议题时发布的一条消息。但坦率地说，我认为它值得写成一篇文章，哪怕内容略显粗糙！

你可以在 fuzzbench 的议题追踪器 #654 找到相关讨论。

社交动态

我现在更定期地在我的 Twitch 上直播了！我开发了用于模糊测试的虚拟机监控程序、变异器、模拟器，并且在直播中做了很多有趣的模糊测试工作。欢迎过来看看！

在 Twitter 上关注我 @gamozolabs，以便在新博客发布时收到通知。我经常会在数据产生和学习过程中发布数据和图表。

正文

今天再次问好！

我想讨论一些我经过更长时间思考后得出的观点，并希望强调它们。

可视化，以及我通常从数据中寻找什么

在可视化方面，我并不太在意默认显示哪些图表，是线性刻度还是对数刻度，是基于时间还是基于测试用例数，但这些都应该可以在默认设置中进行切换。我不是网页开发人员，但拥有交互式图表会非常棒，可以开启或关闭某些线条、缩放以及更改刻度/坐标轴。不过，我认为我们在这点上是一致的。我个人认为默认应该使用对数刻度，并且不明白它有任何不好的地方，除非你只关心看到数据在何处“趋于平缓”。但在那种情况下，对数刻度下同样可见，你只需要对对数刻度有所了解即可。

以下是我在运行和调优模糊测试器时通常会绘制的图表示例。我将微小调整后的模糊测试器与我之前的最佳运行进行并排比较，并在时间域和测试用例数域上绘制两者的数据。为了与当前的做法进行比较，我包含了线性刻度图，但我个人从不使用线性刻度，因为我觉得它在各方面都更差。

通过使用线性刻度，我们无法看到模糊测试器在前约 20 分钟内的任何情况。我们只能看到一条垂直线。而在对数刻度下，我们可以看到更多正在发生的事情。这张图比较的是执行 rand() % 20 轮变异（中等破坏）的模糊测试器与执行 rand() % 5 轮相同变异（低破坏）的模糊测试器。我们可以看到，早期中等破坏具有更好的特性，因为它探索更积极。但实际上存在一个交叉点，这很可能是中等破坏平均破坏程度变得过大，最终“破坏”了之前好的输入，从而显著降低了我们看到好的测试用例的频率。值得注意的是，由于中等破坏是低破坏的超集（即，有机会执行低破坏），两条曲线最终会收敛到完全相同的值。

这张图中有太多让我印象深刻的信息。我看到中等破坏在前约 100 秒内表现良好。在最开始的几秒内有一个很好的领先优势，然后逐渐减弱。这给了我反馈，告诉我应该在何时何地使用这种程度的破坏。

此外，由于我既有测试用例数图又有时间图，我可以看到早期的中等破坏实际上比低破坏表现更好。这再次说明是合理的：破坏越多，你越有可能生成一个更无效的输入，其解析会更浅。但从覆盖率与测试用例数的关系图中，我发现这不是一个长期现象，最终两者的性能似乎趋于一致。需要注意的是，两条线的交叉点在测试用例域和时间域上都有很大差异。这告诉我，即使我只改变了变异器，它也影响了性能，这很可能是因为语料库中平均输入的深度，非常有意思！

分析结论示例

我看到在这种情况下，中等破坏在达到相同覆盖率的时间上给我带来了大约 10 倍的加速，并且在早期也有一些性能优势。我应该采用一种动态破坏模型，根据时间（或者理想情况下，根据我能从目标或统计信息中提取的其他指标）来调整这种破坏量。我看到长期来看，低破坏开始胜出，对于要运行一周的东西，我宁愿运行低破坏。

即使这个程序非常简单，这些图表也可以任意拉伸到不同的时间轴。例如，如果 fuzzbench 设定一个截止时间，比如 1000 秒，我们永远不会知道模糊测试器的这种性能情况。我认为这很可能是许多模糊测试器现在被调优的方向，因为基准测试通常是 12/24/72 小时递增的。模糊测试器在运行更深层时甚至会出现一些额外的波动，很难估计这些交叉是否会发生。

支持基于测试用例数的观点

我个人从绘制在测试用例数而非时间上的图表中获取大部分信息。通过在时间域进行基准测试，你考虑到了模糊测试器的性能。这是基本事实，对于完整产品最终而言确实重要。但这对于开发中的模糊测试器来说并非基本事实。例如，如果我想为 AFL 原型设计一种新的变异策略，我将被迫用 C 语言实现，避免低效的拷贝，避免内存分配等。我实际上必须确保我的变异器性能与现有 AFL 变异器相当或更好，才能使用这样的基准测试。

当你基于测试用例数进行开发时，你可以开始从产生测试用例的质量角度检查模糊测试器的效率。我可以完全用 Python 原型设计一个变异器，看看它是否比标准的 AFL 变异器表现更好。这让我可以走捷径，花 1 天时间尝试一个变异器，而不是花 1 个月时间制作变异器，然后进行复杂的优化使其工作。在开发的早期阶段，我希望开发者能理解使其更快的后果，并且大致了解如果 O(n^3) 的逻辑变为 O(log n)，性能会如何，以及是否可能。

很多时候，第一次尝试会是粗糙的，没有别的原因，就是懒（非贬义）！有时间和地点去打磨和优化一项技术，重要的是能从非常初步的结果中学习到信息。标准反馈机制和变异策略中的大部分性能问题都可以通过一些工程努力解决，并且大多数开发者应该能够评估其策略的最佳情况大 O 复杂度，即使那不是他们初始实现的算法复杂度。

是的，观察覆盖率与测试用例数的关系增加了细微差别，但我认为我们可以处理它。考虑到大多数模糊测试工具，尤其是初始版本，已经非常不优化，对于 AFL/libfuzzer 等在单核性能方面的任何性能差异，我真的不担心。

扩展性

Fuzzbench 中严重缺乏性能扩展性的评估。在我工作过的每一家公司，无论大小，即使是我们进行模糊测试的最简单的目标，我们至少运行约 50-100 个核心。我猜想（我不确定）fuzzbench 是比较单核性能。这很好，这是一个有用的统计数据，我也经常控制这个变量，因为单核、覆盖率/测试用例数通常可以控制扩展性和性能，从而很好地审视模糊测试器的原始逻辑。

然而，在现实中，这些工具的扩展性对于实际使用至关重要。如果 AFL 的单核速度快 20%，考虑到变异策略的相对平等性，这可能会使其在 fuzzbench 上名列前茅。这很好，性能需要工程努力，不应被低估。事实上，我的大部分研究都集中在使模糊测试器变快上，我有多个模糊测试器可以在单台机器上每秒处理数百亿个测试用例。让这些工具扩展需要大量工作，比单核性能要多得多，单核性能通常通过算法修复来解决。

如果 AFL 单核速度快 20%，但受限于 fork() 或 write()，因此只能扩展到 20-30 个核心（我经常看到 AFL 在这个规模上崩溃，对于中等规模的目标是 5-10 个核心）。但像 libfuzzer 这样的东西在内存中管理事务，可以随着你投入的核心数量线性扩展，那么 libfuzzer 将远远超过任何 20% 的单核性能增益。

这些信息很难进行基准测试。嗯，不是难，而是成本高。实际上，我希望看到模糊测试器在单台服务器上扩展到约 16 个核心，以及至少分布在 4 台服务器上的约 128 个核心的基准测试。这些基准测试：A. 测试模糊测试器首先能否扩展，如果不能，这对实际可用性是一个重大打击。B. 测试其能否跨服务器扩展（通常是跨网络）。像 AFL-over-SMB 这样的工具在这里会有很差的扩展性。C. 同一服务器上核心之间的可扩展性属性，以及它们如何通过网络传输。

我发现这些被基准测试的模糊测试器拥有相似的扩展性属性的可能性非常低。由于每个测试用例都大量使用系统调用和阻塞性 IPC（据我回忆，signal()、read()、write()，每个用例大约 3-4 个系统调用），AFL 即使在单台服务器上、甚至在持久模式下也难以扩展。

扩展性也对论文中提出的不可行的模糊测试策略施加了很大压力。我们都见过它们，那些高内省技术，从小程序中提取内存、寄存器、污点状态并承诺有很好的结果。我不反对这些结果，你提取的信息越多，几乎直接与覆盖率/测试用例数的增加相关。但是，最终数据负载变得很难在核心之间共享、在服务器之间排队，甚至难以处理。

测量符号执行

符号执行被多次提及，因为它肯定比传统模糊测试器有更好的覆盖率/测试用例数。但这种细微差别可以通过同时查看覆盖率/测试用例数和覆盖率/时间图来轻松处理。了解算法上什么效果好应该驱动我们的工程努力来解决问题。虽然符号执行可能存在巨大的性能问题，但很可能它的许多部分（例如污点跟踪）可以通过有损算法和数据捕获来近似，更重要的是了解其优势和劣势所在。我对符号执行的许多分析很大程度上引导我走向向量化模拟，它允许进行高度压缩、近似的污点跟踪，同时仍能获得接近原生（甚至更好）的执行速度。

反对单一整体式模糊测试器的理由

了解什么有效对于确定我们的工程时间投入在哪里很重要。考虑到目前模糊测试中的代码质量（通常很差），有很多事情我不希望因为我们当前的方法不支持而排除它们。我非常关心测试用例的复位时间（通常是：fork() 的成本），以及确定性。在一个完全确定性的环境中，配合快速复位，可以使用许多近似策略。尝试近似输入中字节的来源，因为你有一个有趣的分支目标而翻转字节，然后粉碎这些字节可以提供关于这些字节与输入关系的有用信息。有了快速复位和分叉，你甚至可以进行部分模糊测试，在测试用例执行期间多次 fork() 和快照，你可以从解析器的不同点逐步进行模糊测试。这对于可以在每个数据包边界快照的协议尤其有效。

当我们拥有单一整体式的模糊测试器时，这类技术和分析并不真正有效。现有模糊测试器的性能通常相当差（AFL fork() 等），或者不支持部分执行（持久模式、libfuzzer 等）。这导致我们甚至无法研究这些技术。随着我们不断地将新功能添加到现有的模糊测试器中，并将它们视为大块头，我们将越来越远离能够学习模糊测试器的孤立属性并找到应用特定策略的最佳位置。

为什么我不太关心用于基准测试的模糊测试器性能

• 复位速度：AFL 的 fork() 瓶颈对我来说通常在单核上大约每秒 10-20k 次执行，整个系统大约 40-50k，即使是 96C/192T 的系统。这主要是由于卡在内核分配和锁上。启动进程是昂贵的，并且很大程度上超出了我们的控制。AFL 允许测试用例访问本地系统和内核，因此测试用例既不是确定性的，也不是隔离的（在模糊测试具有锁定文件的程序时）。这需要使用另一个抽象层，如 Docker，这给方程增加了更多开销。我用于模糊测试的虚拟机监控程序可以在单核上每秒复位 Windows 虚拟机 100 万次，并随核心数线性扩展，同时保持确定性。为什么这很重要？嗯，我们正在比较的工具甚至远远没有达到 CPU 的能力，它们在内核上遇到了瓶颈。这些都是可以解决的问题，因此，作为一个好点子的消费者而非工具的消费者，我对什么有效感兴趣。我可以自己让它变快。

• 确定性：我们现在使用的大多数模糊测试器都不是确定性的。你不能期望测试用例之间指令级的确定性。这使得使用可能依赖于前一次执行结果与未来执行结果相同的复杂模糊测试策略变得更加困难。这主要是一个工程问题，可以在系统级和应用级目标中解决。

• 变异性能：变异器的性能通常不是它应有的水平。例如，honggfuzz 曾经（现在已经修复，干得漂亮！）在多轮处理期间使用临时分配。在其 mangle_MemSwap 过程中，它复制了要交换的块，执行了 3 次内存拷贝并使用临时分配。这段逻辑本可以使用一次内存拷贝且无需动态分配来实现。这不是对 honggfuzz 的批评，而是对开发如何经常发生的重要说明：早期原型设计、成功，以及很少重新审视可以更改的内容。我在这里想说明什么？嗯，许多模糊测试器中的变异策略可能会引入一些时序特性，而这些特性从根本上并非实现相同行为所必需的。这本身没有问题，但它是额外的噪音，会影响到基于时间的基准测试。这意味着一个好的策略可能被糟糕的实现所拖累，或者仅仅被早期完成的简单实现所拖累。我认为从分析中去除这种噪音是重要的，这样我们可以尝试了解哪些想法有效，然后再进行工程实现。

此外，我不知道有任何不进行原地变异的变异式模糊测试器。这意味着输入中的多次拼接和移除最终必须对剩余部分进行 memcpy()。这是一个非常常见的变异过程。这意味着模糊测试器的速度相对于输入文件大小呈指数级下降。我们几乎看到每个模糊测试器都对输入大小施加了疯狂的限制（如果你给 AFL 的不是一个很小的文件，它会出问题）。

没有什么能阻止我们制作一个基于树的模糊测试器，其中拼接向树中添加一个节点并更新其他节点的元数据。输入可以在准备好被使用时序列化一次，或者更好的是，按需序列化，只提供在测试用例期间实际使用的文件部分。

例如：

初始输入：“foobar”，树是 [指向 “foobar” 的指针，长度 6] 在位置 3 拼接 “baz”：[指向 “foo” 的指针，长度 3][指向 “baz” 的指针，长度 3][指向 “bar” 的指针，长度 3] 程序 read() 3 字节，返回 “foo” 而无需序列化其余部分 程序崩溃，树可以被保存，甚至只保存已读取的部分

在这个过程中，成本是 N 次对一些基本元数据的更新，其中 N 是在该输入上执行的变异次数（通常是 5-10 次）。在一个新的测试用例中，你从一个初始输入开始，位于树的一个节点中，你可以再次根据需要拆分它。几乎不需要执行任何 memcpy() 或分配，因为输入可以在内存中扩展为 “foobarbaz”，但元数据描述 “baz” 应该在 “foo” 和 “bar” 之间。

像这样重构我们进行变异的方式，可能使我们轻松找到 10 倍的变异器性能改进（注意，不是整体模糊测试器性能）。这意味着，我真的不想让变异器的成本成为方程的一部分，因为再次说明，它很可能是懒惰或简单的结果。如果某项策略确实带来了卓越之处，我们很可能可以使其工作得一样快（甚至可能更快），胜过现有的策略。

更不用说，可能了解在先前测试用例中使用了哪些变异，并且你可以潜在地变异这棵树（例如，将拼接从 5 字节改为 8 字节，不改变偏移，只改变变异树中的节点）。这也可以作为一种机制，根据产出动态加权变异策略，同时仍能获得相对于简单实现的性能提升。

性能结论

根据以往与模糊测试器打交道的经验，大部分复位、开销和破坏逻辑的性能甚至可能不在一个数量级内。因此，我更有兴趣弄清楚策略在何时何地有效，因为它们的实现通常不能代表其性能。

但是！ 我认识到将它们视为整个系统的价值。我更偏向于这个问题的硬核工程方面。我对哪些策略有效感兴趣，而不是哪些工具。当然，了解在你没有时间自己调整或重建的情况下，哪些工具效果最好，这也有其价值。话虽如此，我认为扩展性在这里重要得多，因为我不知道有谁真的在做单核模糊测试。这些模糊测试器在扩展规模下的结果很可能与单核截然不同，并且会对一些产生太多信息难以处理的理论构想施加巨大压力。

从数据中重构完整图景

我希望 fuzzbench 提供的数据，也是我会为做到这一点而大大赞赏的，是每次覆盖率增加时原始的、微秒级时间戳的信息。

这意味着，每次覆盖率增加时，生成一条新的 CSV 记录（或其他格式），包括发现时间的时间戳（精确到微秒），以及指示已运行了多少个输入到模糊测试器的测试迭代 ID。这还应包括被发现的块（边）的唯一标识符。

这意味着，在事后，可以重构模糊测试器的整个进度。每条边、它们是哪些边、被发现的时间以及发现它们时的用例 ID，使得我们不仅可以比较原始的“边数量”，还可以比较发现的边之间的差异。令人难以置信的是，这些信息不是基准测试的一部分，因为几乎所有的模糊测试器都可能发现几乎相同的覆盖率，但一个发现较少覆盖率但完全是独特边的模糊测试器会被低估。

这是数据洪流，但由于它不是按时间间隔收集的，所以很快就会变成几乎没有数据。

难题：什么是覆盖率？

这引出了一个非常困难的问题。我们如何比较不同工具之间的覆盖率？我们能否安全地创建一个在所有模糊测试器及其目标之间通用的唯一块标识符。我不知道 fuzzbench 如何解决这个问题（甚至是否解决了）。如果 fuzzbench 依赖于模糊测试器对“边”有大致相同的概念，我会说结果完全无效。具有不同覆盖收集过程、比较信息收集过程的编译器，很容易影响图表。即使是 clang（或其他编译器）中的非确定性因素，也会让我对 afl-clang 二进制文件是否与 libfuzzer-clang 二进制文件具有相同的图形形状感到不安。

如果 fuzzbench 确实解决了这个问题，我很好奇是如何解决的。我预计会通过一个在所有目标之间标准化的覆盖率传递过程。如果是这种情况，他们使用的是相同的二进制文件吗？如果不是，二进制文件是确定性的吗？或者模糊测试器是否可能因为添加了自己的编译器插桩而影响基准测试的覆盖率信息？

此外，如果是这种情况，那么比较以独特方式收集自身覆盖率的模拟器或其他工具就变得更加困难。例如，如果我的模拟器（几乎免费获得覆盖率）为了 fuzzbench 获取数据而必须运行一个插桩的二进制文件，这就不是现实的比较。我的模糊测试器将因覆盖率收集而受到双重惩罚，即使它不需要插桩的二进制文件。

也许有人解决了这个问题，我很好奇解决方案是什么。TL;DR：我们实际上是在比较具有相同图形的相同二进制文件吗？这对于不需要编译时插桩的模糊测试器是否公平？

结束语

期待更多讨论。即使我经常有些固执己见，你也非常乐于接受。我非常尊重这一点。

保持可爱， gamozo