使用DeepState进行API模糊测试（第一部分）

本文介绍了如何使用DeepState工具对API进行高效的模糊测试，包括如何将手写测试转换为功能完善的测试生成器，支持多种后端如Manticore和libFuzzer，并通过实际案例展示如何发现和调试红黑树实现中的隐藏错误。

使用DeepState进行API模糊测试（第一部分）

背景

2013年，John Regehr发表了一篇关于“如何对ADT实现进行模糊测试”的博客文章。John详细讨论了确保数据类型实现可靠性的通用问题，包括代码覆盖率、测试预言和差分测试。如果你还没有读过John的文章，我建议你现在就去阅读。它很好地概述了如何为ADT或任何相对自包含的API构建简单的自定义模糊测试器。

通用问题很简单。假设我们有一段软件，提供对象上的一组函数或方法。本文的运行示例是红黑树；然而，AVL树、文件系统、内存存储甚至加密库都可以轻松替换。我们对调用可用函数时会发生什么有一些期望。我们的目标是彻底测试软件，传统的单元测试方法是编写一系列小函数，形式如下：

1
2
3

result1 = foo(3, "hello");
result2 = bar(result1, "goodbye")
assert(result2 == DONE);

也就是说，每个测试的形式是：“做一些事情，然后检查它是否做了正确的事情。”这种方法有两个问题。首先，工作量很大。其次，这项工作的投资回报不如你希望的那么好；每个测试只做一件特定的事情，如果测试的作者没有想到潜在的问题，那么测试就不太可能发现那个问题。这些单元测试不足的原因与AFL和其他模糊测试器在广泛使用的程序中成功发现安全漏洞的原因相同：人类编写许多测试的速度太慢，并且想象疯狂、有害输入的能力有限。模糊测试的随机性使得能够快速产生许多测试，并产生远远超出“预期用途”的测试。

模糊测试通常被认为是生成文件或数据包，但它也可以生成API调用序列来测试软件库。这种模糊测试通常被称为随机或随机化测试，但模糊测试就是模糊测试。与做一件特定事情的单元测试系列不同，模糊测试（也称为基于属性的测试或参数化单元测试）看起来更像：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

foo_result = NULL;
bar_result = NULL;
repeat LENGTH times:
   switch (choice):
      choose_foo:
         foo_result = foo(randomInt(), randomString());
         break;
      choose_bar:
         bar_result = bar(foo_result, randomString());
         break;
      choose_baz:
         baz_result = baz(foo_result, bar_result);
         break;
   checkInvariants();

也就是说，模糊测试器重复选择一个随机函数调用，然后调用所选函数，可能存储结果以供后续函数调用使用。

这种形式的构造良好的测试将包括许多关于系统应如何行为的通用断言，因此模糊测试器更有可能发现函数调用之间的不寻常交互。最明显的此类检查是代码中的任何断言，但还有许多其他可能性。对于数据结构，这将采用repOK函数的形式，确保ADT的内部表示处于一致状态。对于红黑树，这涉及检查节点着色和平衡。对于文件系统，你可能期望在一系列有效的文件系统操作后，chkdsk永远不会发现任何错误。在加密库中（或者JSON解析器，对消息内容有一些限制），你可能想要检查往返属性：message == decode(encode(message, key), key)。在许多情况下，例如ADT和文件系统，你可以使用相同或类似功能的另一个实现，并比较结果。这种差分测试非常强大，因为它让你用相对较少的工作编写非常完整的正确性规范。

John的文章不仅提供了一般建议，还包括了一个可工作的红黑树模糊测试器的链接。该模糊测试器是有效的，并作为一个很好的例子，展示了如何使用基于随机值生成的可靠测试工具来真正锤击API。然而，它也不是一个完全实用的测试工具。它生成输入并测试红黑树，但当模糊测试器发现错误时，它只是打印错误消息并崩溃。你除了“你的代码有错误。这是症状。”之外什么也学不到。修改代码以在测试步骤发生时打印出来稍微改善了情况，但在失败之前可能有数百或数千个步骤。

理想情况下，模糊测试器会自动将失败的测试序列存储在文件中，最小化序列以便于调试，并使得可以在回归测试套件中重放旧的失败测试。编写支持所有这些基础设施的代码并不有趣（尤其是在C/C++中），并显著增加了测试工作所需的工作量。处理更微妙的方面，例如捕获断言违规和硬崩溃，以便在终止之前将测试写入文件系统，也很难正确完成。

AFL和其他通用模糊测试器通常提供这种功能，这使得模糊测试在调试中成为一个更实用的工具。不幸的是，这样的模糊测试器对于测试API并不方便。它们通常生成一个文件或字节缓冲区，并期望被测试的程序将该文件作为输入。将一系列字节转换为红黑树测试可能比编写保存、重放和减少测试的所有机制更容易和更有趣，但这似乎仍然是很多与你的真实任务不直接相关的工作：弄清楚如何描述有效的API调用序列，以及如何检查正确行为。你真正想要的是一个像GoogleTest这样的单元测试框架，但能够改变测试中使用的输入值。有许多好的随机测试工具，包括我自己的TSTL，但很少有复杂的工具针对C/C++，并且据我们所知，没有工具让你使用除工具内置的随机测试器之外的任何测试生成方法。这就是我们想要的：GoogleTest，但能够使用libFuzzer、AFL、HonggFuzz或你想要的任何工具来生成数据。

进入DeepState

DeepState满足了这一需求，甚至更多。（当我们讨论符号执行时，我们会谈到“更多”）。

将John的模糊测试器转换为DeepState测试工具相对容易。这里是“相同模糊测试器”的DeepState版本。DeepState的主要更改，可以在文件deepstate_harness.cpp中找到，是：

  • 移除main并将其替换为命名测试（TEST(RBTree, GeneralFuzzer)）
    • DeepState文件可以包含多个命名测试，尽管只有一个测试也可以。
    • 在每个测试中只创建一个树，而不是有一个外部循环迭代影响单个树的调用。
    • 我们的测试更接近非常通用的单元测试：每个测试做一个有趣API调用序列。
    • DeepState将处理运行多个测试；模糊测试器或符号执行引擎将提供“外部循环”。
  • 将每个API调用序列的长度固定为一个固定值，而不是随机值。
    • 文件顶部的#define LENGTH 100控制我们在每个测试中调用多少个函数。
    • 在每个测试中字节在某种程度上相同的位置对于基于突变的模糊测试器是有帮助的。极长的测试将超出libFuzzer的默认字节长度。
    • 只要它们不消耗太多字节以至于模糊测试器或DeepState达到其限制，或难以找到正确的字节进行突变，较长的测试通常比较短的测试更好。可能有一个长度为5的序列暴露了你的错误，但DeepState的暴力模糊测试器甚至libFuzzer和AFL可能会难以找到它，并更容易产生相同问题的长度为45的版本。另一方面，符号执行将为任何它能处理的长度找到这种稀有序列。
    • 为简单起见，我们在工具中使用#define，但可以将此类测试参数定义为具有默认值的可选命令行参数，以便在测试中具有更大的灵活性。只需使用与DeepState定义其自己的命令行选项相同的工具（参见DeepState.c和DeepState.h）。
  • 用DeepState_Int()、DeepState_Char()和DeepState_IntInRange(…)调用替换各种rand() % NNN调用。
    • DeepState提供调用以生成你想要的大多数基本数据类型，可选地在受限范围内。
    • 你实际上可以只使用rand()而不是进行DeepState调用。如果你包含DeepState并定义了DEEPSTATE_TAKEOVER_RAND，所有rand调用将被转换为适当的DeepState函数。文件easy_deepstate_fuzzer.cpp展示了这是如何工作的，并且是John的模糊测试器的最简单转换。这不理想，因为它不提供任何日志记录来显示测试期间发生的事情。这通常是将现有模糊测试器转换为使用DeepState的最简单方法；John的模糊测试器的更改是最小的：90%的工作只是更改一些包含并移除main。
  • 用DeepState的OneOf构造替换选择要进行的API调用的switch语句。
    • OneOf接受一个C++ lambda列表，并选择一个执行。
    • 此更改不是严格必需的，但使用OneOf简化了代码并允许优化选择和智能测试减少。
    • OneOf的另一个版本接受一个固定大小的数组作为输入，并返回其中的某个值；例如，OneOf(“abcd”)将产生一个字符，a、b、c或d。

还有许多其他外观（例如格式化、变量命名）更改，但模糊测试器的本质在这里 clearly preserved。有了这些更改，模糊测试器几乎像以前一样工作，除了我们不再运行fuzz_rb可执行文件，而是使用DeepState运行我们定义的测试并生成输入值，这些值选择要进行的函数调用、要插入红黑树的值，以及由DeepState_Int、OneOf和其他调用表示的所有其他决策：

 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

int GetValue() {
  if (!restrictValues) {
    return DeepState_Int();
  } else {
    return DeepState_IntInRange(0, valueRange);
  }
}
...
  for (int n = 0; n < LENGTH; n++) {
    OneOf(
      [&] {
        int key = GetValue();
        int* ip = (int*)malloc(sizeof(int));
        *ip = key;
        if (!noDuplicates || !containerFind(*ip)) {
          void* vp = voidP();
          LOG(TRACE) << n << ": INSERT:" << *ip << " " << vp;
          RBTreeInsert(tree, ip, vp);
          containerInsert(*ip, vp);
        } else {
          LOG(TRACE) << n << ": AVOIDING DUPLICATE INSERT:" << *ip;
          free(ip);
        }
      },
      [&] {
        int key = GetValue();
        LOG(TRACE) << n << ": FIND:" << key;
        if ((node = RBExactQuery(tree, &key))) {
          ASSERT(containerFind(key)) << "Expected to find " << key;
        } else {
          ASSERT(!containerFind(key)) << "Expected not to find " << key;
        }
      },
...

安装DeepState

DeepState GitHub存储库提供了更多详细信息和依赖项，但在我的MacBook Pro上，安装很简单：

1
2
3
4
5
6

git clone https://github.com/trailofbits/deepstate
cd deepstate
mkdir build
cd build
cmake ..
sudo make install

构建启用libFuzzer的版本稍微复杂一些：

1
2
3
4
5
6
7

brew install llvm@7
git clone https://github.com/trailofbits/deepstate
cd deepstate
mkdir build
cd build
CC=/usr/local/opt/llvm\@7/bin/clang CXX=/usr/local/opt/llvm\@7/bin/clang++ BUILD_LIBFUZZER=TRUE cmake ..
sudo make install

使用DeepState红黑树模糊测试器

安装DeepState后，构建红黑树模糊测试器也很简单：

1
2
3

git clone https://github.com/agroce/rb_tree_demo
cd rb_tree_demo
make

make命令使用我们能想到的所有清理器（地址、未定义和整数）编译所有内容，以便在模糊测试中捕获更多错误。这有性能损失，但通常是值得的。

如果你在macOS上并使用非Apple clang以获得libFuzzer支持，你需要做类似的事情：

1

CC=/usr/local/opt/llvm\@7/bin/clang CXX=/usr/local/opt/llvm\@7/bin/clang++ make

以便使用正确（例如，homebrew安装的）版本的编译器。

这将给你一些不同的感兴趣的可执行文件。一个，fuzz_rb，只是John的模糊测试器，修改为使用60秒超时而不是固定数量的“元迭代”。ds_rb可执行文件是DeepState可执行文件。你可以使用简单的暴力模糊测试器（行为非常像John的原始模糊测试器）对红黑树进行模糊测试：

1
2

mkdir tests
./ds_rb --fuzz --timeout 60 --output_test_dir tests

如果你想查看更多关于模糊测试器在做什么的信息，你可以使用–min_log_level指定日志级别，以指示你想要查看的消息的最低重要性。min_log_level为0对应于包括所有消息，甚至调试消息；1是来自被测系统的TRACE消息（例如，由上面显示的LOG(TRACE)代码产生的消息）；2是INFO，来自DeepState本身的非关键消息（这是默认值，通常合适）；3是警告，等等，沿着层次结构向上。测试目录在模糊测试终止时应为空，因为repo中的红黑树代码（据我所知）没有错误。如果你将–fuzz_save_passing添加到选项中，你将在目录中得到大量用于通过测试的文件。

最后，我们可以使用libFuzzer生成测试：

1
2

mkdir corpus
./ds_rb_lf corpus -use_value_profile=1 -detect_leaks=0 -max_total_time=60

ds_rb_lf可执行文件是一个正常的libFuzzer可执行文件，具有相同的命令行选项。这将运行libFuzzer 60秒，并将任何有趣的输入（包括测试失败）放入corpus目录。如果有崩溃，它将在当前目录中留下一个crash-文件。你可以通过确定测试使用的最大输入大小来调整它以在某些情况下表现得更好，但这是一个不简单的练习。在我们的情况下，长度为100时，我们的最大大小和4096字节之间的差距不是非常大。

对于更复杂的代码，像libFuzzer或AFL这样的覆盖驱动、基于检测的模糊测试器将比John的模糊测试器或简单DeepState模糊测试器的暴力随机性有效得多。对于像红黑树这样的例子，这可能不那么重要，因为很少有状态可能很难被快速的“哑”模糊测试器达到。但即使在这里，更聪明的模糊测试器也具有产生产生有趣代码覆盖的测试语料库的优势。DeepState让你使用更快的模糊测试器进行快速运行，并使用更聪明的工具进行更深入的测试，几乎不费吹灰之力。

我们可以轻松重放任何DeepState生成的测试（来自libFuzzer或DeepState的模糊测试器）：

1

./ds_rb --input_test_file file

或重放整个测试目录：

1

./ds_rb --input_test_files_dir dir

在重放整个目录时添加–exit_on_fail标志，让你在遇到失败或崩溃测试时立即停止测试。这种方法可以轻松地将使用DeepState发现的失败（或有趣的通过测试，或可能来自libFuzzer的语料库测试）添加到项目的自动回归测试中，包括在CI中。

添加一个错误

这一切都很好，但它不会（或至少不应该）让我们对John的模糊测试器或DeepState有太多信心。即使我们更改Makefile以让我们查看代码覆盖率，也很容易编写一个不实际检查正确行为的模糊测试器——它覆盖所有内容，但除了崩溃之外找不到任何错误。为了看到模糊测试器在行动中（并看到更多DeepState给我们的东西），我们可以添加一个中等微妙的错误。转到red_black_tree.c的第267行，将1改为0。新文件和原始文件的diff应该看起来像：

1
2
3
4

267c267
<   x->parent->parent->red=0;
---
>   x->parent->parent->red=1;

做一个make以用新的、损坏的red_black_tree.c重建所有模糊测试器。

运行John的模糊测试器几乎会立即失败：

1
2
3
4
5
6
7

time ./fuzz_rb
Assertion failed: (left_black_cnt == right_black_cnt), function checkRepHelper, file red_black_tree.c, line 702.
Abort trap: 6

real 0m0.100s
user 0m0.008s
sys 0m0.070s

使用DeepState模糊测试器将产生几乎一样快的结果。（我们将让它使用–min_log_level选项向我们显示测试，并告诉它一找到失败测试就停止。）：

 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

time ./ds_rb --fuzz --min_log_level 1 --exit_on_fail --output_test_dir tests
INFO: Starting fuzzing
WARNING: No seed provided; using 1546625762
WARNING: No test specified, defaulting to last test defined (RBTree_GeneralFuzzer)
TRACE: Running: RBTree_GeneralFuzzer from deepstate_harness.cpp(78)
TRACE: deepstate_harness.cpp(122): 0: DELETE:-747598508
TRACE: deepstate_harness.cpp(190): checkRep...
TRACE: deepstate_harness.cpp(192): RBTreeVerify...
TRACE: deepstate_harness.cpp(122): 1: DELETE:831257296
TRACE: deepstate_harness.cpp(190): checkRep...
TRACE: deepstate_harness.cpp(192): RBTreeVerify...
TRACE: deepstate_harness.cpp(134): 2: PRED:1291220586
TRACE: deepstate_harness.cpp(190): checkRep...
TRACE: deepstate_harness.cpp(192): RBTreeVerify...
TRACE: deepstate_harness.cpp(190): checkRep...
TRACE: deepstate_harness.cpp(192): RBTreeVerify...
TRACE: deepstate_harness.cpp(154): 4: SUCC:-1845067087
TRACE: deepstate_harness.cpp(190): checkRep...
TRACE: deepstate_harness.cpp(192): RBTreeVerify...
TRACE: deepstate_harness.cpp(190): checkRep...
TRACE: deepstate_harness.cpp(192): RBTreeVerify...
TRACE: deepstate_harness.cpp(113): 6: FIND:-427918646
TRACE: deepstate_harness.cpp(190): checkRep...
...
TRACE: deepstate_harness.cpp(192): RBTreeVerify...
TRACE: deepstate_harness.cpp(103): 44: INSERT:-1835066397 0x00000000ffffff9c
TRACE: deepstate_harness.cpp(190): checkRep...
TRACE: deepstate_harness.cpp(192): RBTreeVerify...
TRACE: deepstate_harness.cpp(190): checkRep...
TRACE: deepstate_harness.cpp(192): RBTreeVerify...
TRACE:
comments powered by Disqus
© 2020 - 2025 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次