从零开始学习fuzzing之一段代码覆盖之旅

 

之前看到安全客平台有zoemurmure师傅翻译的《从零开始学习fuzzing》系列文章，但是只翻译到了第三篇。这个系列的文章读着感到酣畅淋漓，从最基础的代码开始，让人很容易理解一个模糊测试器的诞生，使人欲罢不能。然后看到英文原版博客有了第四和第五章，遂尝试翻译引入填坑，也算是和大家一起交流，因为还是个大三的本科生，翻译不好之处，还请各位师傅批评指正。

此为本系列的第五章，也是最后一章，完结撒花★,°:.☆(￣▽￣)/$:.°★ 。

 

一、前言

我们已经在本系列前面讨论过代码覆盖的重要性，所以今天我们将尝试理解一些非常基本的底层概念、一些常见的方法、一些工具，并了解一些流行的fuzzing框架能够利用哪些技术。我们将避开一些更深奥的策略，试着专注于所谓的“面包和黄油”，即人们熟悉的主题领域。所以，如果你刚接触fuzzing，刚接触软件测试，这篇博文应该是友好的。我发现这个领域中使用的许多术语都很直观且容易理解，但也存在一些不一样的地方。希望这至少能帮助你做你自己的研究。

我们将尽最大努力不陷入定义的细枝末节，而只会专注于学习东西。我不是计算机科学家，这篇博客的目的只是向您介绍这些概念，以便您了解它们在模糊测试中的作用。本着这种精神，如果您发现任何具有误导性，严重错误的信息，请告诉我。

感谢所有在Twitter上回答问题并一直帮助我的人，比如:@gamozolabs，@domenuk，@is_eqv，@d0c_s4vage和@naehrdine，这只是其中的几个例子:)

 

二、核心定义

我们需要做的第一件事就是弄清楚一些定义。这些定义非常重要，因为我们将在随后的说明/探索中以它们为基础。

2.1 代码覆盖率

代码覆盖率是我们了解我们的模糊测试输入测试到程序代码数量的一个指标。我们不会在这里花太多时间，因为我们已经在以前的文章中讨论过代码覆盖率。代码覆盖率对于模糊测试器非常重要，因为这可以让我跟踪目标程序中我们能够测试覆盖到的范围。我们可以想象一下，如果我们只探索程序空间的一小部分，那么我们的测试可能在综合性方面受到限制。

2.2 基本快

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

“In compiler construction, a basic block is a straight-line code sequence with no branches in except to the entry and no branches out except at the exit.”

在编译器结构中，基本块是一个直线代码序列，入口没有分支，且出口也没有分支。

所以“基本块”是一种线性执行的代码序列，代码执行路径没有机会分支到不同的方向。让我们举个直观的例子。以这个程序为例，它通过命令行获取密码，然后检查它是否满足密码长度要求：

#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()分解成代码块的。如果您查看每个块的内部，您将看到代码执行是单向的，在块内部没有机会走两条或多条不同的路径。代码在路径上执行，而路径上没有分叉。您可以看到，在这个示例中，块通过不同的条件跳转指令从main函数返回值然后继续正常执行流程，或者直接调用exit()退出程序

2.3 边/分支/过渡

“边”是CS（计算机科学）图论中的一个术语，我认为这并不是很直观，我更喜欢用“过渡”或者“分支”来描述它，但是从本质上讲，这是为了描述基本块之间的关系。回顾Ghidra的基本块图，我们可以发现存在一些不同的关系，也就是说，代码执行可以根据多种条件采取多种途径。

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

• 如果参数个数不是2，则通过非条件跳转（JZ）跳转到基本块001006e4
• 如果参数个数是2，则通过条件跳转到基本块00100706

这两种可能性可以称为“边”，所以块01006cf有两条边。你可以想象从模糊测试器的角度来看这是多么重要。如果我们的模糊器只探索其中一个基本块的边，我们就会留下一个未测试的完整分支，所以我们有必要追踪这类信息。

这个概念的全部含义显然比我在这里介绍的要多得多，你可以在维基百科的Control-flow_graph条目上阅读更多内容。

2.4 路径

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

路径一：0x001006cf->0x001006e4

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

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

2.5 仪表化

在本博文中，“仪表化”主要是指我们可以实现可以提供模糊测试器对目标代码的覆盖率提供反馈数据的能力。这可能意味着很多事情。它可以复杂到像完全重构一个没有源代码的已经编译好的二进制程序，也可以简单到只是在每个基本块的入口地址上放置一个断点。

一个重要的结论是我们的这个“仪表化”将引起性能的损失，如果我们的检测工具提供的有效信息比另外一种技术多50%，但是需要消耗的性能却是另一种的1000倍，那么我们就要权衡一下。也许视不同的场景，为了增加50%的数据而付出巨大的性能损失也不是不可以接受的。

2.6 仅有二进制文件

这是一个简单的概念。“仅二进制”指的是我们没有目标程序的源代码。所以我们要处理的就是一个一堆二进制数据。它可以是动态链接的，也可以是静态的。这些类型的目标在某些环境中更为普遍，例如嵌入式目标，MacOS和Windows。尽管在Linux上仍然会存在只有二进制数据的目标，但它们并不常见（因为Linux开源情况比较好）。

尽管“只有二进制”是一个容易理解的概念，但是它对我们的收集代码覆盖率造成的麻烦却是巨大的。许多流行的代码覆盖率统计机制都依赖于源代码，以便可以以某种方式对目标进行编译，从而使其方便收集覆盖率数据。而对于二进制的目标，我们无法按照我们想要的方式编译目标。我们必须按照编译后的目标来处理它。

 

三、通用策略

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

3.1 跟踪基本块

收集代码覆盖率的最简单方法之一是简单地跟踪给定输入达到了多少基本块。你可以想象，我们正在用我们的输入探索一个目标程序，我们想知道已经到达了哪些代码。我们知道，鉴于我们在上面对基本块的定义，如果我们输入一个基本块，我们将执行其中的所有代码。因此，如果我们仅跟踪是否已达到一个基本块，我们至少会知道什么路径我们尚未遍历，我们可以手动对其进行检查。

这种方法不是很复杂，并且在高保真覆盖数据方面提供的很少。但是，它实现起来非常简单，并且可以与各种目标一起使用。没有源代码？在上面添加一些断点。没有时间写编译器代码?在上面添加一些断点。

在性能方面，这项技术很棒。达到新的覆盖率将需要命中一个断点，删除该断点并恢复在检测过程中被覆盖的原始内容，保存到达该断点的输入，然后继续。这些事件实际上在发生时会很慢。但是，随着您在模糊测试活动中的进展，新的触发信息变得越来越稀有。因此，随着时间的流逝，前期成本最终会降低到几乎为零。

我想说，在我有限的经验中，这种统计覆盖率信息的方法通常用于封闭源目标（仅二进制目标），因为此时我们的选择有限，而且这种技术含量低的方法也足够有效。

让我们看看@gamozolabs非常快速的基本块跟踪代码覆盖率工具Mesos。你可以看到，它针对的目标是在Windows上的程序，因为Windows的程度大多是不开源的都是仅提供二进制数据。这个工具的优点在于它的性能。你可以在README中看到他的基准测试结果:

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

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

// 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入口处的断点，并将到达它的输入添加到我们的语料库中。

但是加入我们现在输入的值是220，则会进入到parsing_routine_2，我们进入parsing_routine_2的值将永远都是220了，因为我们删除了这个断点，我们将不会把其它能触发这个断点的值保存到我们的语料库中（例如221）。因此，我们将不会再把其它到达基本块的可能值更新到我们的语料库中，这个影响可能十分重大。假设parsing_routine_1之后会接受整个输入，然后逐字节地读取全部的输入，并在每次迭代时进行某种冗长的解析。也就是说我们前面的输入会对我们后续的程序的具有重大的影响，大的输入与小的输入在行为上有很大的差异。如果我们给程序的第一个输入是1MB呢？我们的模糊测试器将会把保存在语料库中同样能触发基本块但是很大的输入混为一谈，如果我们很不幸，先保存了大输入的状态，而不是保存小输入的状态，这将使得我们使用大输入造成性能损失。

解决此问题的一种方法是只需要定期重新实例化所有断点。假设您已经运行了100亿个模糊测试样例的模糊器，并且在24小时内未发现任何新覆盖，则可以在那时再次插入所有已发现的断点，然后尝试保存以不同的方式可以满足input[0x9] < 220但长度较小且性能更高的输入。确实有上百万种方法可以解决此问题，我相信@gamozolabs之前已在Twitter上解决了这个确切问题，但我找不到该帖子。

总而言之，这是一种非常有效的统计覆盖率的方法，特别是考虑到它可以实现的目标多种多样且实现起来非常简单。

3.2 跟踪边缘和路径

跟踪边缘来统计代码覆盖率也是非常流行的，这也是AFL及其衍生品所采用的策略。在这种方法中，我们不仅关心被命中的基本块，还关心探索基本块之间的关系。

AFL++对于覆盖率统计数据的展示同时引用了基于基本块和基于边缘的隐式计数器。我也不是100%确定，但我相信他们对“路径”的定义与我们上面的一致。我认为他们说“路径”与他们文档中的测试用例相同。

我不会在这里深入解析AFL及其衍生品（实际上AFL和AFL++十分不同）是如何收集和分析覆盖率信息的，原因很简单：这是留给感兴趣的高手们，我对此不是很了解。如果你对更详细的分析感兴趣，请继续阅读他们的文档，并尽情享受他们。

为了跟踪边缘信息，AFL使用了一个元组来保存有关系的基本块地址。因此，在我们的示例程序中，如果我们因为没有提供正确数量的命令行参数而从块0x001006cf转到块0x001006e4，那么这个元组(0x001006cf, 0x001006e4)将被添加到AFL++中用于跟踪边缘路径信息的元组映射中。因此，让我们跟踪一下在程序中遍历整个路径时要注册的元组：

0x001006cf -> 0x00100706 -> 0x00100722

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

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

这类覆盖数据远比仅仅跟踪到达的基本块复杂得多；而且，获得这种级别的细节也不是那么简单。

在通常的情况下，AFL通过在编译目标时通过插桩来获取这些数据。如果你拥有源代码，你可以使用AFL编译的目标代码，AFL将在其中嵌入一些汇编代码。这真是太漂亮了。但它需要访问源代码，而这并不总是可能的。

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

我不明白这里所有的细微差别，但是关于这个主题的一个很棒的博文是:@abiondo’s post explaining an optimization they made to AFL QEMU mode in 2018。在一个简短的总结中(希望不是太不准确)，QEMU将预先计算找出的直接跳转一系列的基本块并将他们编译为一个完整的块，以加快处理速度。以这个示例为例：

ADD RAX, 0x8
JMP LAB_0x00100738

在这里，我们有一个硬编码的目的地址。我们知道从我们当前跳转到目标LAB_0x00100738的相对地址（current_addr - LAB_0x00100738），于是在模拟器中我们可以直接通过硬编码替换掉LAB_0x00100738，而不是每次执行都要重新计算（只有最初的一个计算相对偏移量）。这将允许模拟器以本机执行的方式进行，而不必回到我所说的“模拟模式”，即在每次执行跳转到它之前必须计算地址。这在QEMU中称为“基本块链”。好吧，你可以想象一下，如果发生这种情况，那块本地执行的代码(实际上是两个块)对AFL来说是完全不透明的，因为它不知道这两个块被包含，所以它不能记录所取的边缘。因此，作为一种解决方案，AFL将对QEMU进行修改，使其不再进行这种操作，并保持每个区块隔离，以便能够跟踪边缘。这意味着在每个块的末尾，无论是否直接跳转，QEMU都会回到“模拟模式”，这将导致性能损失。

不过，一定要读读@abiondo的博文，它的信息量要大得多。

如果你想知道什么是间接跳转，那么它应该是只在执行时才知道跳转位置，就像一个示例中所示的那样:

ADD RAX, 0x8
JMP RAX

使用QEMU收集覆盖率数据的唯一问题是，与纯粹的本地执行相比，它的速度相对较慢。这种损失显然是值得的，因为我们获得的数据量非常大，而且有时只有二进制数据时我们没有其他选择。

3.3 比较覆盖率/细粒度比较

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

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%的比较信息，因为我们0xdeadbebe== 0xdeadbeef匹配了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模式，你可以利用他们所谓的“la -intel仪器”，这里有两处说明文档：

https://github.com/AFLplusplus/AFLplusplus/blob/3b799c09cd68bb68b26784261f1fbaa3e737c747/instrumentation/README.laf-intel.md
https://lafintel.wordpress.com/

来自laf-intel的博客文章，我们可以看到他们的示例看起来非常类似于我们已经经历过的具有源代码的思想实验：

if (input == 0xabad1dea) {
  /* terribly buggy code */
} else {
  /* secure code */
}

此代码段已“优化”为几个较小的比较，而模糊测试器可以通过以下比较来衡量其进度：

if (input >> 24 == 0xab){
  if ((input & 0xff0000) >> 16 == 0xad) {
    if ((input & 0xff00) >> 8 == 0x1d) {
      if ((input & 0xff) == 0xea) {
        /* terrible code */
        goto end;
      }
    }
  }
}

/* good code */

end:

当人们选择指定某些环境变量并利用afl-clang-fast其编译目标时，可以发出这种优化过的代码。

这非常聪明，可以消除繁琐的工作。

但是，当我们无法访问源代码并且纯二进制目标可能充满大量比较时，我们该怎么办？

幸运的是，也有针对此问题的开源解决方案。让我们看看@ifsecure和一个名为“ TinyInst ”的人。由于我从未使用过该工具，因此无法深入了解该工具的工作原理，但是它README具有很丰富的介绍，十分具有可读性！

正如我们所看到的，它的目标是MacOS和Windows目标，这与其只检测二进制目标的目的相一致。TinyInst通过调试器对选择例程进行插桩以更改执行权限，从而使我们得到覆盖率信息，具体的方法是使对执行插装代码的任何执行（由于保留了这些权限而无法读取或写入）都会导致错误，然后由TinyInst调试器处理该错误，在此代码执行重定向到重写的检测例程/模块。因此，TinyInst阻止了原始模块的所有执行，并将所有执行重定向到插入到程序中的重写模块。您会看到它有多么强大，因为它可以以与laf-intel方法非常相似的方式（而且是对于已编译的目标）将大型比较分解为小得多的比较。看一下这个很酷的gif，它显示了@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跟踪数据。在他们的自述文件中包含的图表非常酷，你可以看到它比其他硬件来源的覆盖引导模糊工具要快得多，同时也收集了最高保真度的覆盖数据，他们称之为“全边缘覆盖”。直接从CPU获得覆盖率数据似乎是理想的，哈哈。因此，对于他们来说，能够设计一个库，让我们获得完美的覆盖率，并且不需要源代码，这似乎是一个巨大的成就。我个人目前还没有足够的工程能力来处理这种类型，但总有一天会的。许多流行的模糊器都可以立即使用Intel-PT，诸如AFL ++，honggfuzz和WinAFL之类的模糊器。

还有许多其他这样的程序，但它们不在本博文的讨论范围之内。

 

五、结论

在这篇文章里，我们介绍了一些在构建基本块中经常使用的术语，一些用于获取有意义的覆盖率数据的非常常见的基本策略，以及一些用于提取数据的工具（在某些情况下，什么模糊测试框架使用什么工具）。应该提到的是，流行的模糊测试框架（如AFL ++和honggfuzz）经过了很长时间的研究，以使它们的框架尽可能地灵活，并可以在广泛的目标范围内工作。它们通常会给我们带来极大的方便，采用最适合情况的覆盖范围数据提取方法。希望这篇文章对你开始理解与代码覆盖有关的一些问题有所帮助。