模糊测试如穴居人第五篇：面向初学者的代码覆盖率之旅

引言

我们已在本系列前文中讨论过代码覆盖率的重要性，今天我们将尝试理解一些非常基础的核心概念、常见方法、相关工具，并了解一些流行模糊测试框架能够利用的技术。我们将避开一些更晦涩的策略，专注于被称为“面包与黄油”的成熟主题领域。如果您是模糊测试或软件测试的新手，这篇博文应该会很友好。我发现这个领域使用的很多术语都很直观且易于理解，但也有一些例外。希望这至少能帮助您开始自己的研究。

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

感谢所有在Twitter上慷慨回答问题并帮助我的人，比如：@gamozolabs、@domenuk、@is_eqv、@d0c_s4vage和@naehrdine等等 :)

核心定义

我们需要做的第一件事是澄清一些定义。这些定义很重要，因为我们将在后续的解释/探索中以此为基础。

代码覆盖率

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

基础块

首先来看维基百科的定义：

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

因此，“基础块”是一个线性执行的代码序列，代码执行路径没有机会分支到不同的方向。让我们举一个视觉例子。以下是一个虚拟程序，通过命令行获取密码，然后检查其是否符合密码长度要求：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <stdio.h>
#include <stdlib.h>

int length_check(char* password)
{
    long i = 0;
    while (password[i] != '\0')
    {
        i++;
    }

    if (i < 8 || i > 20)
    {
        return 0;
    }

    return 1;
}

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        printf("usage: ./passcheck <password>\n");
        printf("usage: ./passcheck mysecretpassword2021\n");
        exit(-1);
    }

    int result = length_check(argv[1]);

    if (!result)
    {
        printf("password does not meet length requirements\n");
        exit(-1);
    }

    else
    {
        printf("password meets length requirements\n");
    }
}

在Ghidra中编译和分析后，我们可以看到main()的以下图形视图：

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

边缘/分支/转换

“边缘”是CS/图论中那些我认为不是超级直观的术语之一，我更喜欢“转换”或“分支”，但本质上这是为了捕捉基础块之间的关系。回顾我们来自Ghidra的基础块图，我们可以看到存在几种不同的关系，也就是说，根据一些条件，代码执行可以采取多种路径。

基础块001006cf与两个不同的块有关系：001006e4和00100706。因此，001006cf内部的代码执行可以根据条件到达与其有关系的两个块中的任何一个。在我们的例子中，该条件是JZ操作，取决于命令行参数的数量是否为2：

• 如果参数数量不是2，我们通过不采取条件跳转（JZ）有机地分支到块001006e4
• 如果参数数量是2，我们通过采取条件跳转分支到块00100706

这两种可能性可以被称为“边缘”，因此块01006cf有两个边缘。您可以想象从模糊测试的角度来看这可能是多么重要。如果我们的模糊测试器只探索一个基础块的一个边缘，我们就会留下整个分支未经测试，因此跟踪这类信息对我们有利。

这个概念显然比我在这里透露的要多，您可以在维基百科的Control-flow_graph条目中阅读更多信息。

路径

“路径”只是我们的程序执行遍历的基础块列表。查看我们的示例程序，有几种不同的路径，如下所示，用橙色、绿色和红色线表示。

路径一：0x001006cf -> 0x001006e4 路径二：0x001006cf -> 0x00100706 -> 0x00100738 路径三：0x001006cf -> 0x00100706 -> 0x0000722

插桩

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

插桩的一个重要方面是要记住您的插桩所带来的性能损失。如果您的插桩提供的数据比一种技术多50%，但性能低1000倍，您必须考虑权衡。多出50%的数据可能非常值得巨大的性能损失，这取决于具体情况。

仅二进制

这是一个简单的概念，“仅二进制”指的是我们没有源代码的目标。因此，我们只能处理一个二进制blob。它可以是动态链接的或静态的。这类目标在某些环境中更为普遍，想想嵌入式目标、MacOS和Windows。不过，Linux上也有仅二进制的目标，只是不太常见。

尽管“仅二进制”很容易理解，但对收集代码覆盖率数据的影响是深远的。许多流行的代码覆盖率机制依赖于拥有源代码，以便可以以某种方式编译目标，使其易于收集覆盖率数据，对于仅二进制目标，我们没有按照我们想要的方式编译目标的奢侈。我们必须按原样处理已编译的目标。

常见策略

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

跟踪基础块

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

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

在性能方面，这种技术很棒。命中新覆盖率将需要命中一个断点，移除断点并恢复在插桩期间被覆盖的原始内容，保存到达断点的输入，然后继续。这些事件在实际发生时会很慢；然而，随着模糊测试活动的进行，新覆盖率变得越来越罕见。因此，有一个前期成本，随着时间的推移最终会降低到接近零。

根据我的有限经验，我会说这种类型的覆盖率通常用于闭源目标（仅二进制），我们的选择有限，而这种低技术方法足够有效。

1
2
3
4

Registered    1000000 breakpoints in   0.162230 seconds |  6164072.8 / second
Applied       1000000 breakpoints in   0.321347 seconds |  3111897.0 / second
Cleared       1000000 breakpoints in   0.067024 seconds | 14920028.6 / second
Hit            100000 breakpoints in  10.066440 seconds |     9934.0 / second

要记住的一件事是，如果您使用这种方式收集覆盖率数据，您可能会限制自己只使用第一个到达基础块的输入。比如说，我们有以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// input here is an unsigned char buff
if (input[0x9] < 220)
{
    parsing_routine_1(input);
}

else
{
    parsing_routine_2(input);
}

如果我们到达此代码的第一个输入的input[0x9]值为200，那么我们将进入parsing_routine_1块入口。我们将移除在parsing_routine_1入口处的断点，并将到达它的输入添加到我们的语料库中。但是既然我们已经用一个值为200的输入到达了我们的块，我们某种程度上就与那个值绑定了，因为我们再也不会用任何其他也会到达它的值命中这个断点。因此，我们永远不会保存一个以不同方式“解决”这个基础块的输入到语料库中。这可能很重要。假设parsing_routine_1然后获取整个输入，并在输入的整个长度上逐字节读取，并在每次迭代中进行某种冗长的解析。再假设没有后续例程是高度有状态的，其中大输入的行为与小输入截然不同。如果我们给程序的第一个解决这个块的输入是1MB大小怎么办？我们的模糊测试器某种程度上就与我们保存在语料库中的大输入绑定了，我们有点不幸，较短的输入没有首先解决这个块，这可能会损害性能。

克服这个问题的一种方法是定期重新实例化所有断点。假设您已经运行模糊测试器100亿个测试用例，并且24小时内没有发现任何新覆盖率，您可以在那时再次插入所有已发现的断点，并尝试以不同的方式解决块，可能保存一个更小、性能更高的输入，该输入以input[0x9] = 20解决了块。实际上，有无数种方法可以解决这个问题。我相信@gamozolabs之前在Twitter上解决过这个确切的问题，但我没能找到那篇帖子。

总而言之，这是一种非常有效的覆盖率方法，特别是考虑到它适用于各种目标并且实现起来非常简单。

跟踪边缘和路径

跟踪边缘非常流行，因为这是AFL及其子代采用的策略。这种方法我们不仅关心哪些基础块被命中，还关心基础块之间正在探索哪些关系。

AFL++统计输出引用了路径和边缘以及隐含的“计数器”。我不是100%确定，但我相信他们的“路径”定义与我们的上述定义一致。我认为在他们的文档中，“路径”与测试用例相同。

我不会在这里深入分析AFL及其子代（实际上AFL++与AFL有很大不同）如何收集和分析覆盖率，原因很简单：这是给大脑发达的人准备的，我不太理解。如果您对更详细的分析感兴趣，请前往他们的文档并尽情阅读。

为了跟踪边缘，AFL使用涉及关系的块地址的元组。因此，在我们的示例程序中，如果我们因为未提供正确数量的命令行参数而从块0x001006cf转到块0x001006e4，这个元组(0x001006cf , 0x001006e4)将被添加到AFL++用于跟踪唯一路径的覆盖率映射中。因此，让我们跟踪如果遍历程序中的整个路径我们将注册的元组：

0x001006cf -> 0x00100706 -> 0x00100722

如果我们采取上述路径，我们可以制定两个覆盖率数据元组：(0x001006cf, 0x00100706)和(0x00100706, 0x00100722)。这些可以在AFL的覆盖率数据中查找，以查看这些关系是否曾被探索过。

AFL不仅跟踪这些关系，还跟踪频率。例如，它知道每个特定边缘被到达和探索的频率。

这种覆盖率数据比仅仅跟踪到达的基础块要复杂得多；然而，获得这种细节水平也远非那么简单。

在最常见的情况下，AFL通过使用目标的编译时插桩来获取这些数据。您可以使用AFL编译器编译您拥有源代码的目标，该编译器将发出带有嵌入目标的插桩的已编译代码。这非常巧妙。但它需要访问源代码，这并不总是可能的。

AFL也有针对仅二进制目标的答案，并利用强大的QEMU模拟器来收集类似详细的覆盖率数据。模拟器相对自由地访问这类数据，因为它们必须获取目标指令并要么解释它们（这意味着模拟它们的执行），要么JIT（即时）将块编译成本地代码并本地执行它们。在这里的QEMU案例中，块被JIT成本地代码并存储在缓存中，以便后续执行可以轻松再次使用。因此，当QEMU遇到一个基础块时，它可以检查该块是否已被编译，并相应采取行动。AFL利用这个过程来跟踪正在执行的块，并获得与编译时插桩收集的数据非常相似的数据。

我不理解这里的所有细微差别，但关于这个主题的一篇很棒的博文是：@abiondo的帖子解释了他们在2018年对AFL QEMU模式进行的优化。在一个非常简短（希望不是太不准确）的总结中，QEMU会预计算所谓的直接跳转，并将这些块编译成一个块（通过保持在本地编译的块中执行）作为一种加速方式。以这个玩具例子为例：

1
2

ADD RAX, 0x8
JMP LAB_0x00100738

这里我们有一个可预计算的目的地用于我们的跳转。我们知道从当前地址到LAB_0x00100738的相对偏移（当前地址 - LAB_0x00100738的绝对值），因此在模拟器中，我们可以直接进行跳转并将目的地替换为LAB_0x00100738的编译块，并且每次执行时都不需要计算（只有初始计算相对偏移的一次）。这将允许模拟器继续进行本地执行，而无需回到我称之为“模拟模式”的状态，即每次执行时都必须计算地址然后再跳转到它。这在QEMU中被称为“块链”。好吧，您可以想象，如果发生这种情况，那个巨大的本地执行代码块（实际上是两个块）对AFL是完全不透明的，因为它不知道包含两个块，因此无法记录所采取的边缘。因此，作为一种解决方法，AFL会修补QEMU不再进行这种块链，并保持每个块隔离，以便可以跟踪边缘。这将意味着在每个块的末尾，无论是直接跳转与否，QEMU都会回到那种“模拟模式”，这将带来性能损失。

一定要阅读@abiondo的博文，它信息量更大。

如果您想知道间接跳转会是什么，它会是跳转位置仅在执行时才知道的东西，在玩具例子中可能看起来像这样：

1
2

ADD RAX, 0x8
JMP RAX

使用QEMU收集覆盖率数据的唯一问题是，与纯本地执行相比，它相对较慢。这种减速显然是值得的，因为您获得的数据量是巨大的，而且有时对于仅二进制目标没有其他替代方案。

比较覆盖率/比较粉碎

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

1

CMP		dword ptr [RBP + local_1c], 0x2

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

但就模糊测试而言，问题在于这个比较是相当二进制的。它要么设置零标志，要么不设置，没有细微差别。我们无法判断我们离通过比较、设置零标志有多近。

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

在高层次上，比较覆盖率将这种比较分解成块，以便可以以比二进制通过/失败更细的粒度跟踪比较的进度。因此，使用比较覆盖率，这个比较可能会被重写如下：

之前： 0xdeadbebe == 0xdeadbeef 吗？

之后： 0xde == 0xde 吗？如果是，记录我们匹配了第一个字节，并且 0xad == 0xad 吗？如果是，记录我们匹配了第二个字节，并且 0xbe == 0xbe 吗？如果是，记录我们匹配了第三个字节，并且 0xbe == 0xef 吗？如果是，记录我们完全匹配了两个操作数。

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

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

1101 1110 1010 1101 1011 1110 1110 1111 对比 1101 1110 1010 1101 1011 1110 1011 1110

这可以分解为32个独立的比较，而不是我们的4个，给我们甚至更高的保真度和进度跟踪（可能以实践中的性能为代价）。

这里我们取了一个4字节比较，并将其分解为4个独立的单字节比较。这也被称为“比较粉碎”。在精神上，它与比较覆盖率非常相似。都是关于将大比较分解成更小的块，以便可以以更高的保真度跟踪进度。

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

您可以想象一个场景，程序在分支到一个需要探索的复杂例程之前检查一个大的值。仅凭基本覆盖率通过这些检查是极其困难的，并且需要大量的人工交互。人们可以检查IDA中显示已到达块的彩色图，并尝试手动找出阻止模糊测试器到达未到达块的原因，并确定一个大的32字节比较失败了。然后，人们可以通过字典或其他方式调整他们的模糊测试器以应对这种比较，但这个过程都是非常手动的。

有一些非常有趣/高度技术性的方法可以对有源代码的目标和仅二进制目标做这种事情！

AFL++具有一个LLVM模式，您可以使用他们称之为“laf-intel插桩”的东西，这里描述，最初在这里写过。直接从laf-intel的博文中，我们可以看到他们的例子看起来与我们已经进行的思想实验极其相似，他们有