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

Alex Groce
2019年1月22日
动态分析, 模糊测试, Manticore, 符号执行

Alex Groce，北亚利桑那大学信息、计算与网络系统学院副教授

使用 DeepState，我们只需极少的努力就将一个手写的红黑树模糊测试工具转变为功能更全面的测试生成器。尽管无需额外编码工作，DeepState 模糊测试器支持回归测试的重放、调试时测试用例的简化，以及多种数据生成后端（包括 Manticore、angr、libFuzzer 和 AFL）。通过符号执行，我们甚至发现了原始模糊测试器遗漏的人工注入漏洞。阅读本文后，您应能开始将高性能自动化测试生成应用于自己的 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。

还有许多其他外观（如格式化、变量命名）更改，但模糊测试器的本质显然在此保留。通过这些更改，模糊测试器几乎像以前一样工作，只是我们不运行 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 命令使用我们能想到的所有清理程序（address、undefined 和 integer）编译所有内容，以便在模糊测试中捕获更多错误。这有性能损失，但通常值得。

如果您在 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 是来自 DeepState 本身的 INFO、非关键消息（这是默认值，通常合适）；3 是警告，依此类推向上。测试目录在模糊测试终止时应为空，因为仓库中的红黑树代码（据我所知）没有错误。如果您将 –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。新文件与原始文件的差异应如下所示：

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

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): check