介绍

我们之前已经在这一系列文章中讨论过代码覆盖率的重要性，所以今天我们将尝试理解一些非常基本的底层概念，一些常见的方法，一些工具，还会看看一些流行的模糊测试框架能够利用的技术。我们将避开一些更深奥的策略，而专注于所谓的“基础知识”，即那些常见的话题。所以，如果你是模糊测试的新手或者软件测试的新手，这篇博客应该对你比较友好。我发现这个领域中使用的许多术语是直观且易于理解的，但也有一些例外。希望本文能帮助你起步，开始你自己的研究。

我们会尽量不陷入定义的细枝末节，而是专注于学习知识。我不是计算机科学家，这篇博客的目的只是向你介绍这些概念，以便你能理解它们在模糊测试中的实用性。本着这种精神，如果你发现任何误导性或严重错误的信息，请告诉我。

感谢那些在Twitter上慷慨解答问题并帮助我的人，比如：@gamozolabs、@domenuk、@is_eqv、@d0c_s4vage 和 @naehrdine，仅举几例。

核心定义

我们首先需要处理一些定义。这些定义很重要，因为我们将在后续的解释和探索中建立在它们的基础上。

代码覆盖率

代码覆盖率是任何能让你了解测试、输入等覆盖了程序代码多少的指标。我们不会花太多时间在这里讨论，因为我们在之前的文章中已经讨论过代码覆盖率。代码覆盖率对模糊测试非常重要，因为它可以让你跟踪目标程序中你能够覆盖的表面积。你可以想象，如果你只探索了程序空间的一小部分，你的测试可能在全面性上会有所限制。

基本块

让我们先看看维基百科的定义：

“在编译器构造中，基本块是一个直线代码序列，除了入口之外没有分支进入，除了出口之外没有分支出去。”

所以“基本块”是一个线性执行的代码序列，在这里代码执行路径没有机会分支到不同的方向。让我们用一个可视化的例子来说明。假设有以下这个简单的程序，它通过命令行获取一个密码，然后检查它是否符合密码长度要求：

一旦我们将其编译并在Ghidra中进行分析，我们可以看到main()的以下图形视图：

“块”（Blocks）是那些直观的术语之一，我们可以看到图形视图自动将main()分解为多个代码块。如果你查看每个块的内部，你会发现代码执行是单向的，块内部没有机会走两条或更多不同的路径。代码执行就像在轨道上行驶的火车，而轨道上没有分岔。你可以看到在这个例子中，块通过条件跳转（JZ, JNZ）、main函数返回以及调用exit函数来终止。

边/分支/转换

“边”（Edge）是计算机科学/图论中的术语之一，我认为它并不特别直观，我更喜欢用“转换”（Transition）或“分支”（Branch），但本质上它是用来描述基本块之间的关系的。回看我们在Ghidra中的基本块图，我们可以看到存在几种不同的关系，也就是说，根据一些条件，代码执行可以采取多条路径。

基本块001006cf与两个不同的块有关系：001006e4和00100706。所以代码执行在001006cf中时，可以根据条件到达其关联的两个块中的任意一个。在我们的例子中，这个条件是JZ操作，即判断命令行参数的数量是否为2：

• 如果参数数量不是2，我们通过不进行条件跳转（JZ）自然地分支到块001006e4。
• 如果参数数量是2，我们通过进行条件跳转分支到块00100706。

这两种可能性可以称为“边”（Edges），所以块01006cf有两个边。你可以想象，从模糊测试的角度来看，这可能有多重要。如果我们的模糊测试器只探索了某个基本块的一条边，那就意味着我们遗漏了整个分支未进行测试，因此我们有必要跟踪这类信息。

显然，这个概念比我在这里提到的要复杂得多，你可以在Wikipedia上阅读更多关于控制流图（Control-flow graph）的内容。

路径

“路径”（Path）只是我们程序执行遍历的基本块列表。看着我们的示例程序，有几个不同的路径，如下图中的橙色、绿色和红色线条所示。

路径一：0x001006cf -> 0x001006e4

路径二：0x001006cf -> 0x00100706 -> 0x00100738

路径三：0x001006cf -> 0x00100706 -> 0x0000722

插桩

在这篇博客中，“插桩”指的是为模糊测试目标提供代码覆盖率反馈数据的过程。这可能意味着很多事情。它可以像完全重写我们没有源代码的已编译二进制文件那样复杂，也可以像在每个基本块入口地址上放置一个断点那样简单。

关于插桩，需要记住的一个重要方面是插桩所带来的性能损失。如果你的插桩技术可以提供比另一种技术多50%有用信息，但后者的性能却高出1000倍，那么你就必须考虑权衡。多50%的数据可能非常值得这种巨大的性能损失，这取决于具体情况。

仅有二进制文件

这是一个简单的概念，“仅有二进制文件”是指我们没有源代码的目标。所以我们只能操作一个二进制文件。它可以是动态链接的或静态链接的。这类目标在某些环境中更为普遍，比如嵌入式目标、MacOS 和 Windows。不过，在 Linux 上也依然存在仅有二进制文件的目标，只是相对较少。

即使“仅有二进制文件”这个概念容易理解，但它对获取代码覆盖率数据的影响却是深远的。许多流行的代码覆盖率机制依赖于拥有源代码，这样可以以一种有利于收集覆盖率数据的方式编译目标。而对于仅有二进制文件的目标，我们无法按照自己的意愿编译目标，只能处理已经编译好的目标。

常见策略

在本节中，我们将开始探讨模糊测试工具用于收集代码覆盖率数据的常见策略。

跟踪基本块

收集代码覆盖率最简单的方法之一就是简单地跟踪给定输入到达的基本块数量。你可以想象我们正在用输入探索一个目标程序，我们想知道哪些代码已经被覆盖。根据我们上面关于基本块的定义，如果我们进入一个基本块，我们将执行其中的所有代码，因此，如果我们只跟踪某个基本块是否已被触及，至少我们可以知道哪些路径尚未被覆盖，并且可以手动检查它们。

这种方法并不复杂，在提供高保真覆盖率数据方面的能力较弱；然而，它实现起来极其简单，并且适用于各种目标。没有源代码？在上面加一些断点。没时间写编译器代码？在上面加一些断点。

从性能角度来看，这种技术非常棒。获得新的覆盖率意味着触发一个断点，移除断点并恢复在插桩过程中被覆盖的原始内容，保存触发断点的输入，然后继续执行。这些事件在发生时实际上是慢的；然而，随着模糊测试的进行，新的覆盖率变得越来越罕见。因此，这种方法在前期成本较高，但随着时间的推移最终会降至接近零。

据我有限的经验来看，这种类型的覆盖率通常用于闭源目标（二进制文件），因为我们选择有限，而这种低技术的方法已足够有效。

让我们快速看看 @gamozolabs 的一个非常简单的基本块跟踪覆盖工具叫做 Mesos。你可以看到它主要用于 Windows 上的目标，因为大多数目标是仅有二进制文件的。这个工具的巧妙之处在于它的性能。你可以在README中看到他的基准测试结果：

需要注意的一点是，如果你使用这种方式收集覆盖率数据，你可能会将自己限制在第一个到达基本块的输入上。比如说，我们有以下代码：

假设我们第一次输入以一个值为200的input[0x9]到达了这段代码，那么我们将进入parsing_routine_1块的入口。我们会在parsing_routine_1的入口处移除断点，并将触及该块的输入添加到我们的测试集（corpus）中。但是，由于我们已经用值为200的输入达到了这个块，因此我们永远不会再用其他可能到达这个块的值触发这个断点。所以我们永远不会保存一个“以不同方式解决”这个基本块的输入到测试集中。这可能是非常重要的。假设parsing_routine_1接着会读取整个输入，并在输入的每一个字节上执行某种长时间的解析操作。而且假设没有后续的例程是高度有状态的，即大输入与小输入在行为上有显著差异。如果我们给程序的第一个解决这个块的输入是1MB大小的，那么我们的模糊测试器就与我们在测试集中保存的大输入“捆绑”在一起了，而我们也许是因为不幸地没有首先用较小的输入解决这个块，这可能会影响性能。

解决这个问题的一种方法是定期重新设置所有的断点。比如说，你的模糊测试器已经运行了100亿个测试案例，并且在24小时内没有发现任何新的覆盖率，此时你可以重新插入所有已经发现的断点，并尝试用不同的方式解决这些基本块，也许可以保存一个更小、更高效的输入来解决这个块，比如用input[0x9] = 20。实际上，有一百万种不同的方法可以解决这个问题。我相信 @gamozolabs 之前在Twitter上讨论过这个问题，但我没能找到那条推文。

总的来说，这是一个非常有效的覆盖方法，特别是考虑到它适用于多种目标并且实现起来也很简单。

跟踪边和路径

跟踪边非常流行，因为这是AFL及其衍生工具采用的策略。这种方法不仅关注哪些基本块被触及，还关注基本块之间探索了哪些关系。

AFL++ 的统计输出中提到了路径（paths）和边（edges），并且隐含提到了“计数器”（counters）。我不是百分之百确定，但我相信他们对“路径”的定义与我们上面提到的定义是一致的。我认为他们在文档中表示“路径”与测试用例（testcase）相同。

我不会在这里深入分析 AFL 及其衍生工具（实际上 AFL++ 和 AFL 已经有很大不同）是如何收集和分析覆盖率的，原因很简单：这是为高智商人群准备的，我对此了解不多。如果你对更详细的分析感兴趣，可以查看他们的文档，尽情学习。

为了跟踪边，AFL 使用了涉及关系的基本块地址元组。因此在我们的示例程序中，如果我们因为没有提供正确数量的命令行参数而从块 0x001006cf 转到块 0x001006e4，那么这个元组 (0x001006cf, 0x001006e4) 就会被添加到 AFL++ 用于跟踪独特路径的覆盖率图中。让我们跟踪一下在程序中遍历整个路径时会记录哪些元组：

0x001006cf -> 0x00100706 -> 0x00100722

如果我们走上面的路径，我们可以形成两个覆盖率数据元组：(0x001006cf, 0x00100706) 和 (0x00100706, 0x00100722)。这些元组可以在 AFL 的覆盖数据中查找，以确定这些关系是否已经被探索过。

AFL 不仅跟踪这些关系，还跟踪它们的频率。例如，它可以知道每个特定边被触及和探索的频率。

这种覆盖数据比仅仅跟踪到达的基本块要复杂得多；然而，获取这种细节的过程也远不像前者那么简单。

在最常见的情况下，AFL 通过在目标上使用编译时插桩来获取这些数据。你可以使用 AFL 编译器编译你的目标（前提是你有源代码），编译器会生成包含插桩代码的目标编译代码。这非常巧妙，但需要访问源代码，而这并不总是可能的。

AFL 对于仅有二进制文件的目标也有解决方案，它利用了强大的 QEMU 模拟器来收集类似的详细覆盖数据。模拟器可以相对自由地访问这类数据，因为它们需要处理目标指令，要么解释它们（即模拟其执行），要么即时编译（JIT）这些块为本地代码并以本地方式执行。在这里使用的 QEMU 中，块被即时编译为本地代码并存储在缓存中，以便后续执行能轻松重复使用。因此，当 QEMU 遇到一个基本块时，它可以检查该块是否已经被编译，并根据情况采取相应的行动。AFL 利用这个过程来跟踪哪些块正在被执行，并获取与编译时插桩类似的数据。

我并不完全理解其中的细微差别，但有一篇很棒的博客文章可以阅读：@abiondo 在2018年撰写的关于他们对 AFL QEMU 模式进行优化的帖子。简短地总结（希望不会太不准确），QEMU 会预计算所谓的直接跳转，并将这些块基本编译为一个单一块（通过保持执行在本地编译的块中）作为一种加速方式。以这个简单的例子为例：

在这个例子中，我们有一个可以预计算的跳转目标。我们知道从当前地址到LAB_0x00100738的相对偏移量（current_addr - LAB_0x00100738的绝对值），所以在模拟器中，我们可以直接执行这个跳转，并将目标替换为LAB_0x00100738的已编译块，这样在每次执行时就不需要进行计算（只需在初次计算相对偏移量时计算一次）。这将允许模拟器以本地执行的方式继续运行，而不必回到我称之为“模拟模式”的状态中，在每次执行时都需要计算跳转地址。这在QEMU中称为“块链化”（block-chaining）。你可以想象，如果发生这种情况，那么通过本地执行的那块巨大的代码（实际上是两个块）对于AFL来说是完全不透明的，因为AFL并不知道其中包含了两个块，因此无法记录所采取的边。因此，作为一种变通方法，AFL会修补QEMU，使其不再进行这种块链化，并保持每个块的独立性，以便可以跟踪边。这意味着在每个块结束时，无论是直接跳转还是其他，QEMU都会回到“模拟模式”，这会带来性能损失。

不过，务必阅读 @abiondo 的博客文章，它要详细得多，也更具信息性。

如果你想知道什么是间接跳转，它指的是只有在执行时才知道跳转位置的情况，在一个简单的示例中可能会像这样：

唯一的问题是，使用QEMU来收集覆盖率数据的速度相对较慢，与纯本地执行相比有一定的性能损失。当然，这种性能下降是值得的，因为你获得的数据量非常大，而且在仅有二进制文件的目标上有时没有其他替代方案。

比较覆盖率/比较分解

与仅仅跟踪输入或测试在程序的基本块/边中的进展不同，比较覆盖率旨在了解我们的测试在程序中的比较操作中取得了多少进展。比较可以通过不同的方式进行，但我们的示例密码程序中已经存在一个常见的例子。在001006cf块中，我们有一个CMP操作：

CMP dword ptr [RBP + local_1c], 0x2

dword是一个4字节（32位）值，这个操作将我们程序中的argc值与0x2进行比较，以检查提供了多少命令行参数。因此，我们的两个比较操作数分别是堆栈上RBP + local_1c偏移位置的值和0x2。如果这两个操作数相等，零标志（Zero Flag）将被设置，我们可以利用JZ条件跳转在程序中进行相应的操作。

但是，和模糊测试相关的问题是，这种比较是二元的。它要么设置零标志，要么不设置，没有任何细微差别。我们无法知道我们在通过比较时有多接近，无法知道设置零标志的可能性有多大。

举个例子，假设我们不是用0x2进行比较，而是用0xdeadbeef。在这种情况下，如果我们提交了0xdeadbebe作为另一个操作数，我们会比提交0x0更接近满足JZ条件。

从高层次上看，比较覆盖率将这种比较分解成多个部分，以便能够比二元的通过/失败（PASS/FAIL）更细致地跟踪比较的进展。因此，使用比较覆盖率，这个比较可能会被重写如下：

之前：

0xdeadbebe == 0xdeadbeef ?

之后：

0xde == 0xde ? 如果是，记录我们匹配了第一个字节，然后再比较

0xad == 0xad ? 如果是，记录我们匹配了第二个字节，然后再比较

0xbe == 0xbe ? 如果是，记录我们匹配了第三个字节，然后再比较

0xbe == 0xef ? 如果是，记录我们完全匹配了这两个操作数。

在我们重写后的例子中，我们不再得到二元的通过/失败，而是看到我们在比较中取得了75%的进展，匹配了4个字节中的3个。现在我们知道可以保存这个输入并进一步变异它，希望通过正确的变异通过最后一个字节的比较。

我们也不必将每个比较仅分解到字节级别，我们还可以在比特级别上比较两个操作数。例如，我们也可以将它们如下进行比较：

1101 1110 1010 1101 1011 1110 1110 1111 vs

1101 1110 1010 1101 1011 1110 1011 1110

这可以分解成32个独立的比较，而不是4个，给予我们更多的保真度和进展跟踪（尽管在实践中可能会牺牲性能）。

这里我们将4字节的比较分解成4个独立的单字节比较。这也被称为“比较分解”（Compare Shattering）。从本质上讲，它与比较覆盖率非常相似。其核心思想是将大的比较分解成更小的部分，以便能以更高的保真度跟踪进展。

一些模糊测试器会将所有比较操作数，比如这个例子中的0xdeadbeef，添加到一种“魔术值字典”中，模糊测试器会随机将其插入输入中，希望将来能通过比较。

你可以想象一个场景：程序在分支到一个需要探索的复杂例程之前检查一个大值。仅靠基本覆盖率很难通过这些检查，这通常需要大量人为干预。有人可能会在IDA中查看显示已到达块的彩色图形，试图手动找出是什么阻止了模糊测试器到达未到达的块，并确定32字节的大比较失败了。然后可以通过字典或其他方式调整模糊测试器以考虑这种比较，但整个过程非常手动。

对于具有源代码和仅有二进制文件的目标，实际上有一些非常有趣且高度技术化的方法来做到这一点！

AFL++ 提供了一种LLVM模式，你可以利用他们称之为“laf-intel插桩”的技术，这里有相关描述，最初的文章在这里。直接引用laf-intel的博客文章，我们可以看到他们的例子与我们刚刚讨论的思想实验非常相似，他们有这样的源代码：

这段代码片段被“去优化”成多个较小的比较，模糊测试器可以通过这些比较来衡量其进展。

这种去优化的代码可以在指定某些环境变量并使用 afl-clang-fast 编译目标时产生。

这非常巧妙，可以极大地减少模糊测试中的手动工作量。

但如果我们无法访问源代码，并且我们的仅有二进制文件的目标可能充满了大量的比较操作，我们该怎么办呢？

幸运的是，针对这个问题也有开源解决方案。让我们来看一个名为“TinyInst”的工具，由 @ifsecure 和他的团队开发。我无法深入解析这个工具的技术细节，因为我从未使用过它，但README文件描述得很详细！

正如我们所见，TinyInst 针对的是 MacOS 和 Windows 目标，符合其为仅有二进制文件的目标插桩的目的。TinyInst 通过调试器插桩选择的例程来获取覆盖率数据，改变执行权限，使得对我们插桩代码的任何执行访问（而不是读取或写入，因为这些权限保持不变）都会导致故障，然后由 TinyInst 调试器处理，在此过程中，代码执行被重定向到重新编写的插桩例程/模块。因此，TinyInst 阻止了原始模块的所有执行，而是将所有执行重定向到插入到程序中的重写模块。你可以看到这有多强大，因为它可以将大规模的比较分解成更小的比较，方式非常类似于 laf-intel 方法，但针对的是已经编译的目标。看看这个由 @ifsecure 分享的展示比较覆盖率实际操作的酷炫动图：[https://twitter.com/ifsecure/status/1298341219614031873?s=20] 你可以看到他有一个程序检查一个8字节的值，而他的模糊测试器逐步通过它，直到解决了这个比较。

还有一些其他工具理论上与 TinyInst 的工作方式类似，也值得一看，它们也在 README 中提到，比如：DynamoRIO 和 PIN。

还应该提到的是，即使在 QEMU 模式下，AFL++ 也能够进行比较覆盖率跟踪。

额外内容：使用硬件获取覆盖率数据

这基本上概述了我们感兴趣的数据类型、原因以及如何提取它们。还有一种提取数据的方法没有提到，但对仅有二进制文件的目标特别有帮助，那就是利用实际硬件获取覆盖率数据。

虽然这不算是一种“策略”，但它使上述策略的执行成为可能，因此值得一提。我们不会深入讨论这个话题。如今，CPU内置了各种旨在实现高保真性能分析的实用工具。这些实用工具也可以被用来为我们提供覆盖率数据。

Intel-PT 是新款 Intel CPU 提供的一种实用工具，它允许你提取有关你正在运行的软件的信息，比如控制流。每个硬件线程都可以存储关于其正在执行的应用程序的数据。使用处理器跟踪的最大问题在于解码收集到的跟踪数据一直以来都非常缓慢且麻烦。然而，最近 @is_eqv 和 @ms_s3c 成功创建了一个名为 libxdc 的高性能库，它可以高效地解码 Intel-PT 跟踪数据。他们的 README 中包含的图表非常酷，你可以看到它比其他硬件来源的覆盖引导模糊测试工具快得多，同时收集到最高保真度的覆盖数据，他们称之为“完整边覆盖”（Full Edge Coverage）。直接从 CPU 获取覆盖率数据似乎是理想的选择，哈哈。因此，他们能够设计出一个基本上能给你完美覆盖率的库，而且不需要源代码，这似乎是一个巨大的成就。我个人目前没有处理这种覆盖率的工程能力，但某一天我会有。许多流行的模糊测试器可以直接利用 Intel-PT，例如：AFL++、honggfuzz 和 WinAFL。

还有许多其他类似的实用工具，但它们超出了本介绍性博客文章的范围。

结论

在这篇文章中，我们讨论了一些在这个领域中使用的基础术语、一些用于获取有意义覆盖率数据的非常常见的基本策略，以及一些用于提取这些数据的工具（在某些情况下，哪些模糊测试框架使用了哪些工具）。需要提到的是，像 AFL++ 和 honggfuzz 这样的流行模糊测试框架在尽可能灵活地设计它们的框架以适应广泛的目标方面付出了很大努力。它们通常给予你大量的灵活性，使你能够采用最适合你情况的覆盖率数据提取方法。希望这能在一定程度上帮助你理解与模糊测试相关的代码覆盖率问题。

译者言

本文使用chatGPT-4o翻译而成，如有错误之处，请斧正
原文链接：https://h0mbre.github.io/Fuzzing-Like-A-Caveman-5/