前言

DeepState是一个框架，它为C和c++开发人员提供了一个公共接口，用于各种符号执行和模糊引擎。用户可以使用类似于Google Test的API编写一个测试工具，然后使用多个后端执行它，而不必了解底层引擎的复杂性。它支持编写单元测试和API序列测试，以及自动测试生成。

使用DeepState，我们就可以编写一个红黑树(red-black tree)模糊器。之后只需付出较少的努力，就可以将其变成一个功能更加全面的测试生成器。 尽管DeepState模糊器不需要很多的编码工作，但它支持回归测试(regressiontest)的重放，以减少用于调试的测试用例的大小，以及多个数据生成后端，包括Manticore，angr，libFuzzer和AFL。使用符号执行，我们甚至发现了原始模糊忽略的人为引入的漏洞。

在此，我保证你阅读完本文后，可以完全在自己的API中进行一次高质量的自动化测试。

背景信息

2013年，犹他州大学计算机系的John Regehr撰写了一篇关于“如何实现ADT的模糊测试”的博客。John详细地讨论了一些一般性问题，比如代码覆盖率、测试代码和差异测试。如果你尚未阅读John的文章，那么我建议你现在就阅读。

一般性的模糊测试很简单，只需要有一个测试软件，利用John的方法就可以在测试对象上提供一组函数或方法。我们在这篇文章中的运行示例是一个红黑树，不过，AVL树、文件系统、内存存储，甚至密码库都可以达到类似的测试目的。由于我们的目标是对软件进行彻底的测试，而传统的单元测试方法则是编写一系列看起来像以下这样的小函数。

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

也就是说，每个测试都会按着这样的步骤来进行：“先运行一些测试内容，然后检查它是否和预期的是一样的。”这种方法有两个问题。首先，工作量很大。其次，这项工作的测试效果并不像你想象的那样好，每个测试都只针对一个测试内容，如果测试的人没有提前把潜在的问题考虑进去，那么测试过程也就会忽略这些问题。

而在模糊测试中，用随机坏数据（也称做 fuzz）攻击一个程序，然后等着观察哪里遭到了破坏。模糊测试的技巧在于，它是不符合逻辑的：自动模糊测试不去猜测哪个数据会导致破坏（就像人工测试员那样），而是将尽可能多的杂乱数据投入程序中。由这个测试验证过的失败模式通常对程序员来说是个彻底的震撼，因为任何按逻辑思考的人都不会想到这种失败。模糊测试是一项简单的技术，但它却能揭示出程序中的重要漏洞。它能够验证出现实世界中的错误模式并在您的软件发货前对潜在的应当被堵塞的攻击渠道进行提示。

模糊测试通常被认为会生成文件或数据包，但它也可以生成测试软件库的API调用序列。

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();

也就是说，fuzzer先反复选择要调用的随机函数，然后调用所选择的函数，测试期间可能会存储结果，以便在以后的函数调用中使用。

John的帖子不仅提供一般性建议，还包含了红黑树的工作模糊器的链接。这个模糊器是有效的，它是一个很好的例子，说明了如何使用基于随机值生成的可靠测试工具来真正测试API。但是，它也不是一个完全实用的测试工具。它虽然会生成输入，并测试红黑树，但当模糊器发现漏洞时，它只会打印一个漏洞信息随即便崩溃。你没有学到任何东西，除了“你的代码有一个漏洞”这样的信息外，我们再也得不到任何有价值的信息。

理想情况下，模糊器会自动将失败的测试序列存储在一个文件中，最小化这些序列以简化调试，并且可以在回归套件中重放过去的失败测试。编写支持所有这些基础设施的代码很是枯燥(尤其是在C/ c++中)，而且会显著增加测试工作所需的工作量。另外处理类似捕获断言违规和硬崩溃的现象，以便在终止之前将测试编写到文件系统，也很难做到。

AFL和其他常用的模糊器通常会提供这种功能，这使得模糊测试成为一种更实用的调试工具。不幸的是，这种模糊测试器并不便于测试API。它们通常会生成一个文件或字节缓冲区，并期望被测试的程序将该文件作为输入。将一系列字节转换为红黑树测试可能比重新编写更有趣，但工作量也很大。你真正想要的是一个像GoogleTest这样的单元测试框架，但它能够改变测试中使用的输入值。有很多很好的随机测试工具，包括TSTL，但很少有复杂的工具以C / C ++为目标，而且据我所知，没有一个工具允许你使用除了工具内置的随机测试器之外的任何测试生成方法。这就是我们想要的GoogleTest，它能够使用libFuzzer，AFL，HonggFuzz或生成数据。

DeepState

DeepState满足了我以上提到的所有测试要求，甚至更多。将John的模糊器转换为DeepState测试工具相对容易，可以在文件deepstate_harness.cpp中找到DeepState的主要更改项，总共5项：

1.删除main并用一个已经命名的test (test (RBTree, GeneralFuzzer))替换它；

1.1DeepState文件可以包含多个名为test的测试，但是只有一个测试是可以用的；

2.只需在每个测试中创建一个树，而不是使用一个外部循环来迭代每次影响单个树的调用：

2.1与模糊测试循环不同，我的测试更接近于非常一般化的单元测试，即每个测试都会执行一个有趣的API调用序列；

2.2DeepState将处理运行多个测试，模糊或符号执行引擎将提供“外部循环”；

3.将每个API调用序列的长度固定为固定值，而不是随机值。

3.1文件顶部的#define LENGTH 100控制我们在每个测试中调用的函数数量；

3.2在每次测试中，字节都在相同的位置，这对基于突变的模糊器很有帮助。注意：极长的测试将超出libFuzzer的默认字节长度。

3.3只要它们不消耗那么多字节使得模糊器或DeepState达到它们的极限，或者找不到要变异的正确字节，更长的测试通常比更短的测试更好。可能有一个长度为5的序列暴露了你的漏洞，但是DeepState的暴力模糊器甚至libFuzzer和AFL可能很难找到它，并且更容易生成相同问题的长度为45的版本。另一方面，符号执行可以找到任意长度的罕见序列。

3.4为简单起见，我在我的工具中使用了#define，但是也可以将这些测试参数定义为带有默认值的可选命令行参数，以便在测试中获得更大的灵活性。只需使用与DeepState相同的工具来定义自己的命令行选项（请参阅DeepState.c和DeepState.h）。

4用DeepState_Int()、DeepState_Char()和DeepState_IntInRange(…)调用替换各种rand() % NNN调用。

4.1 DeepState提供调用来生成你想要的大多数基本数据类型，可以选择在受限制的范围内生成。

4.2实际上你可以使用rand()代替DeepState调用，如果你的调用包含DeepState并已定义DEEPSTATE_TAKEOVER_RAND，则所有rand调用都将转换为适当的DeepState函数。 easy_deepstate_fuzzer.cpp文件显示了它的工作原理，但它并不理想，因为它不提供任何记录来显示测试期间发生的情况。这通常是将现有模糊器转换为使用DeepState的最简单方法。注意：John的模糊器的变化很小，90%的工作只是更改了一些include和删除main。

5. 用DeepState的OneOf结构替换选择要进行API调用的switch语句：

5.1 OneOf获取C ++ lambda的列表，并选择一个执行；

5.2此更改并不是必须的，但使用OneOf可简化代码并允许优化选择和减少智能测试工作量；

5.3另一个版本的OneOf接受一个固定大小的数组作为输入，并返回一些值，例如，OneOf（“abcd”）将产生一个字符a，b，c或d。

除此之外，还有许多其他的修饰性（例如格式化，变量命名）更改，但底线就是确保模糊器的本质属性不被破坏。通过这些更改，模糊器除了不运行fuzz_rb可执行文件，几乎和以前一样。我将使用DeepState运行我们定义的测试并生成输入值，选择要进行的函数调用，什么值插入在红黑树，以及由DeepState_Int，OneOf和其他调用表示的所有其他决策：

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上，安装很简单。

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

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

brew install [email protected]
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

AFL也可用于为DeepState生成输入，但大多数情况下，原始速度（由于不需要分叉），比较分解和值配置文件似乎为libFuzzer提供了这种API测试的优势。有关在DeepState中使用AFL和其他基于文件的模糊器的更多信息，请参阅DeepState文件。

使用DeepState红黑树模糊器

安装DeepState后，构建红黑树模糊器的过程也就很简单了。

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

make命令使用了我们能想到的所有杀毒软件(address、undefined和integer)编译所有内容，以便在模糊处理中捕获更多漏洞。虽然这样做会降低运行性能，但却很有价值。

如果你使用macOS并使用非Apple clang来获得libFuzzer支持，那么你需要做以下的事情。

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

这样，你就能使用到正确的编译器版本，例如，homebrew-installed。

这将为你提供一些不同的可执行程序，一个是fuzz_rb，它只是John使用的模糊器，使用时长只有60秒，ds_rb可执行文件是DeepState可执行文件。你可以用一个简单的BF算法模糊器来模糊红黑树。

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

如果要查看有关fuzzer正在执行的操作的更多信息，可以使用–log_level指定日志级别，以明确要查看的信息的重要性。 log_level为0，则代表包括所有信息，甚至包括调试信息，log_level为1时，代表的是来自被测系统的TRACE信息（例如，由上面显示的LOG（TRACE）代码产生的信息）。log_level为2时，代表的是来自DeepState本身的INFO，非关键信息（这是默认的，通常是合适的）， log_level为3时，代表的是警告信息，依此类推。在模糊测试结束时，测试目录应为空，因为repo中的红黑树代码是没有漏洞的。如果将–fuzz_save_passing添加到选项中，你将在目录中得到大量用于传递测试的文件。

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

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

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

对于更复杂的代码，像libFuzzer或AFL这样的基于覆盖的且基于工具的模糊器将比John的模糊器或简单的DeepState模糊器的随机性更强。对于像红黑树这样的例子，这可能没有那么重要。随机性更强的模糊器也具有产生测试语料库的优势，这些测试可以产生有趣的代码覆盖。 DeepState允许你使用更快的模糊器进行快速运行，并使用更智能的工具进行更深入的测试。

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

./ds_rb --input_test_file file

或者重放整个测试目录：

./ds_rb --input_test_files_dir dir

在重放整个目录时添加–exit_on_fail标志，可让你在遇到失败或崩溃测试时立即停止测试。这种方法可以很容易的用于将DeepState中发现的失败添加到自动回归测试中。

认为的添加一个漏洞

虽然一切都很顺利，但它没有让我对John的模糊或DeepState充满信心。即使我们更改了Makefile来查看代码覆盖率，也很容易编写一个不检查正确行为的模糊器。也就是说模糊测试涵盖了所有内容，除了出现崩溃之外没有发现任何漏洞。要查看正在运行的模糊器，以及DeepState提供给我们的更多信息，我可以主动添加一个漏洞。转到red_black_tree.c的第267行，将1改为0。新文件和原始文件的差异应该如下所示:

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

使用新的red_black_tree.c重建所有模糊器后，运行John的模糊器会立即引发崩溃。

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模糊器可以快速生成模糊结果：

time ./ds_rb --fuzz --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: deepstate_harness.cpp(154): 46: SUCC:-244966140
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(103): 48: INSERT:1679127713 0x00000000ffffffa4
TRACE: deepstate_harness.cpp(190): checkRep...
Assertion failed: (left_black_cnt == right_black_cnt), function checkRepHelper, file red_black_tree.c, line 702.
ERROR: Crashed: RBTree_GeneralFuzzer
INFO: Saved test case to file `tests/6de8b2ffd42af6878875833c0cbfa9ea09617285.crash`
...
real 0m0.148s
user 0m0.011s
sys 0m0.131s

为了方便本文的阐述，我做了一些精简，上面的代码只是详细输出的一部分。DeepState保与John的模糊器的最大区别在于，它保存了一个测试用例。当然，保存的测试用例的名称会有所不同，因为每个已保存的测试都会生成唯一名称。重放测试如下所示：

./ds_rb --input_test_file tests/6de8b2ffd42af6878875833c0cbfa9ea09617285.crash

而且我会再次看到整个过程细节，如上所述，这一长串看似任意的操作并不是最有帮助的测试。此时，DeepState可以帮助我们找到有用的信息。

deepstate-reduce ./ds_rb tests/6de8b2ffd42af6878875833c0cbfa9ea09617285.crash minimized.crash
ORIGINAL TEST HAS 8192 BYTES
LAST BYTE READ IS 509
SHRINKING TO IGNORE UNREAD BYTES
ONEOF REMOVAL REDUCED TEST TO 502 BYTES
ONEOF REMOVAL REDUCED TEST TO 494 BYTES
...
ONEOF REMOVAL REDUCED TEST TO 18 BYTES
ONEOF REMOVAL REDUCED TEST TO 2 BYTES
BYTE RANGE REMOVAL REDUCED TEST TO 1 BYTES
BYTE REDUCTION: BYTE 0 FROM 168 TO 0
NO (MORE) REDUCTIONS FOUND
PADDING TEST WITH 49 ZEROS
 
WRITING REDUCED TEST WITH 50 BYTES TO minimized.crash

同样，我省略了减少测试的一些冗长过程，新的测试结果更容易理解。

./ds_rb --input_test_file minimized.crash
WARNING: No test specified, defaulting to last test defined (RBTree_GeneralFuzzer)
TRACE: Initialized test input buffer with data from `minimized.crash`
TRACE: Running: RBTree_GeneralFuzzer from deepstate_harness.cpp(78)
TRACE: deepstate_harness.cpp(103): 0: INSERT:0 0x0000000000000000
TRACE: deepstate_harness.cpp(190): checkRep...
TRACE: deepstate_harness.cpp(192): RBTreeVerify...
TRACE: deepstate_harness.cpp(103): 1: INSERT:0 0x0000000000000000
TRACE: deepstate_harness.cpp(190): checkRep...
TRACE: deepstate_harness.cpp(192): RBTreeVerify...
TRACE: deepstate_harness.cpp(103): 2: INSERT:0 0x0000000000000000
TRACE: deepstate_harness.cpp(190): checkRep...
Assertion failed: (left_black_cnt == right_black_cnt), function checkRepHelper, file red_black_tree.c, line 702.
ERROR: Crashed: RBTree_GeneralFuzzer

我们只需要在树中插入三个相同的值就可以发现其中存在的漏洞，在继续操作之前，请记得修复red_black_tree.c！

你可以点此链接，观看整个过程。

在第2部分中，我将对测试的结果进行评估，看看DeepState测试是否与John的模糊测试一样有效？看看这两种方法在查找某些潜在的漏洞方面是否同样有效?符号执行是否也有同样的效果呢?敬请关注。