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

变异测试

手动引入一个错误（如我们在第一部分中所做）是可以的，我们可以再试一次，但“轶事的复数不是数据”。然而，这并不完全正确。如果我们有足够的轶事，我们或许可以称之为数据（“大数据多重轶事”领域随时都会起飞）。在软件测试中，创建多个“虚假错误”有一个名称，即变异测试（或变异分析）。变异测试通过自动生成对程序的许多小更改来工作，期望大多数此类更改会使程序不正确。测试套件或模糊器如果检测到更多这些更改，则更好。在变异测试的行话中，检测到的变异体被“杀死”。这种措辞对变异体有点苛刻，但在测试中，对错误保持一定的冷酷是必要的。变异测试曾经是一个学术小众话题，但现在已在主要公司的现实世界情境中使用。

有许多可用的变异测试工具，尤其是针对Java。对于C代码的工具通常不太健壮，或更难以使用。我（与NAU和其他大学的同事一起）最近发布了一个工具，universalmutator，它使用正则表达式允许对许多语言进行变异，包括C和C++（更不用说Swift、Solidity、Rust以及许多其他以前没有变异测试工具的语言）。我们将使用universalmutator来查看我们的模糊器在检测人工红黑树错误方面的表现如何。除了通用性之外，universalmutator的一个优点是它产生大量变异体，包括那些通常等效但有时在行为上产生细微区别的变异体——即难以检测的错误——这是大多数变异系统不支持的。对于高风险软件，这值得付出额外努力来分析和检查变异体。

安装universalmutator并生成一些变异体很容易：

1
2
3

pip install universalmutator
mkdir mutants
mutate red_black_tree.c --mutantDir mutants

这将生成大量变异体，其中大多数不会编译（universalmutator不解析或“知道”C，所以许多变异体不是有效的C并不奇怪）。我们可以通过对变异体运行“变异分析”来发现编译的变异体，以“它编译吗？”作为我们的“测试”：

1

analyze_mutants red_black_tree.c "make clean; make" --mutantDir mutants

这将产生两个文件：killed.txt，包含不编译的变异体，和notkilled.txt，包含实际编译的1120个变异体。要查看变异体是否被杀死，分析工具只需确定引号中的命令是否返回非零退出代码或超时（默认超时为30秒；除非你的机器非常慢，这有足够的时间编译我们的代码）。

如果我们将包含有效（编译）变异体的notkilled.txt文件复制到另一个文件，那么我们可以进行一些真正的变异测试：

1
2

cp notkilled.txt compile.txt
analyze_mutants red_black_tree.c "make clean; make fuzz_rb; ./fuzz_rb" --mutantDir mutants --verbose --timeout 120 --fromFile compile.txt

输出将如下所示：

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

ANALYZING red_black_tree.c
COMMAND: ** ['make clean; make fuzz_rb; ./fuzz_rb'] **
#1: [0.0s 0.0% DONE]
  mutants/red_black_tree.mutant.2132.c NOT KILLED
  RUNNING SCORE: 0.0
...
Assertion failed: (left_black_cnt == right_black_cnt), function checkRepHelper, file red_black_tree.c, line 702.
/bin/sh: line 1: 30015 Abort trap: 6           ./fuzz_rb
#2: [62.23s 0.09% DONE]
  mutants/red_black_tree.mutant.1628.c KILLED IN 1.78541398048
  RUNNING SCORE: 0.5
...

类似的命令将在DeepState模糊器和libFuzzer上运行变异测试。只需将make fuzz_rb; ./fuzz_rb更改为make ds_rb; ./ds_rb --fuzz --timeout 60 --exit_on_fail以使用内置的DeepState模糊器。对于libFuzzer，为了加速，我们将设置环境变量LIBFUZZER_EXIT_ON_FAIL为TRUE，并将输出管道到/dev/null，因为libFuzzer的详细性将隐藏我们的实际变异结果：

1
2

export LIBFUZZER_EXIT_ON_FAIL=TRUE
analyze_mutants red_black_tree.c "make clean; make ds_rb_lf; ./ds_rb_lf -use_value_profile=1 -detect_leaks=0 -max_total_time=60 >& /dev/null" --mutantDir mutants --verbose --timeout 120 --fromFile compile.txt

该工具生成2,602个变异体，但只有1,120个实际编译。以60秒的测试预算分析这些变异体，我们可以更好地了解我们模糊工作的质量。DeepState暴力模糊器杀死797个这些变异体（71.16%）。John的原始模糊器杀死822个（73.39%）。将这些模糊器未杀死的变异体再模糊60秒不会杀死任何额外的变异体。libFuzzer的性能惊人地相似：60秒的libFuzzer（从空语料库开始）杀死797个变异体，与DeepState的暴力模糊器完全相同——事实上是相同的变异体。

“天下没有免费的午餐”（或者有吗？）

DeepState的本机模糊器在给定时间内似乎不如John的“原始”模糊器有效。这不应该令人惊讶：在模糊测试中，速度是王道。因为DeepState正在解析字节流，分叉以保存崩溃，并产生广泛的、用户控制的日志记录（以及其他事情），它不可能像John的裸骨模糊器那样快速生成和执行测试。

libFuzzer甚至更慢；除了DeepState模糊器提供的所有服务（除了为崩溃分叉，由libFuzzer本身处理）之外，libFuzzer还确定代码覆盖率并为每个测试计算值配置文件，并执行基于这些输入质量评估的未来测试所需的计算。

这就是John的模糊器杀死25个DeepState没有杀死的变异体的原因吗？嗯，不完全。如果我们检查这25个额外的变异体，我们发现每一个都涉及将指针上的相等比较更改为不等比较。例如：

1
2
3

<   if ( (y == tree->root) ||
---
>   if ( (y <= tree->root) ||

DeepState模糊器没有找到这些，因为它在分叉中运行每个测试。代码没有分配足够的时间来使用足够的地址空间来对这些特定检查造成问题，因为大多数分配都在分叉中！理论上，这对于不运行分叉的libFuzzer不应该成立。而且，果然，如果我们给慢而稳的libFuzzer五分钟而不是60秒，它也会捕获所有这些变异体。无论多少额外的模糊测试都无法帮助DeepState模糊器。在这种情况下，错误足够奇怪和不太可能，我们或许可以忽略它。问题不是我们模糊器的速度或质量（确切地说），而是不同的模糊测试环境在我们实际运行的测试中产生了细微的差异。

在我们看到这个问题之后，我们向DeepState添加了一个选项，使暴力模糊器（或测试重放）在非分叉模式下运行：--no_fork。不幸的是，这不是一个完整的解决方案。虽然我们现在可以检测这些错误，但我们无法为它们生成一个好的保存测试用例，因为失败取决于所有已发出的malloc以及某些指针的确切地址。然而，事实证明--no_fork有一个更重要的好处：它显著加快了mac OS上的模糊测试和测试重放——通常数量级。虽然我们在示例中省略了它，因为它使分析失败原因复杂化，但你可能应该在mac OS上的大多数模糊测试和测试重放中使用它。

我们可以有把握地说，对于大多数目的，DeepState与John的“原始”模糊器一样强大，易于实现，并且在调试和回归测试方面更方便。

检查变异体

这处理了我们模糊器性能的差异。但是剩下的变异体呢？它们都没有被我们任何模糊器的五分钟模糊测试杀死。它们显示了我们测试中的漏洞吗？有各种方法可以检测等效变异体（实际上不改变程序语义的变异体，因此不可能被杀死），例如通过比较优化编译器生成的二进制文件。出于我们的目的，我们将仅检查298个未杀死变异体的随机样本，以确认至少大多数未杀死变异体真正无趣。

第一个变异体更改了注释中的<=。我们无法杀死这个。比较编译的二进制文件会证明这一点。

第二个变异体修改了InorderTreePrint函数中的代码，John的模糊器（因此我们的）明确选择不测试。这无法通过比较二进制文件检测，但这是常识。如果我们的模糊器从不覆盖一段代码，故意地，它不能很好地检测该代码中的错误。

第三个变异体更改了RBTreeCreate函数第44行对temp->key的赋值，因此它分配1而不是0。这更有趣。需要一些思考来说服自己这无关紧要。如果我们遵循代码的建议并查看头文件中root和nil的注释，我们可以看到这些被用作哨兵。也许root和nil中的确切数据值无关紧要，因为我们只会通过指针比较检测它们？果然，情况如此。

第四个变异体删除了第35行的赋值newTree->PrintKey= PrintFunc;。再次，由于我们从不打印树，这无法检测。

第五个变异体在注释内部。

第六个变异体更改了断言中的指针比较。

1
2
3
4

686c686
<     assert (node->right->parent == node);
---
>     assert (node->right->parent >= node);

如果我们假设断言对原始代码总是成立，那么将==更改为更宽松的>=显然不会失败。

第七个变异体潜伏在注释中。

第八个变异体删除了一个断言。再次，删除一个断言永远不会导致先前通过的测试失败，除非你的断言有问题！

第九个变异体更改了一个红色赋值：

1
2
3
4

243c243
<       x->parent->parent->red=1;
---
>       x->parent->parent->red=-1;

由于我们不检查red字段的确切值，而是用它来分支（所以所有非零值都相同），这没问题。

第十个变异体再次在InorderTreePrint函数内部。

此时，如果我们真的将这个红黑树作为关键代码进行测试，我们可能会：

1. 制作一个工具（如10行Python脚本，不是任何重量级的！）来丢弃所有在注释内部、在InorderTreePrint函数内部或删除断言的变异体。
2. 编译所有变异体，并与原始文件相互比较二进制文件，以丢弃明显的等效变异体和冗余变异体。这一步可能有点烦人。编译器并不总是产生等效的二进制文件，由于编译时生成的时间戳，这就是为什么我们在上面的讨论中跳过了它。
3. 仔细检查剩余的变异体（可能200个左右），以确保我们没有遗漏任何东西。找到“那没问题”的变异体类别通常使这个过程比听起来容易得多（如“断言移除总是没问题”）。

（1）制作测试生成器然后（2）应用变异测试和（3）实际查看存活的变异体并使用它们改进我们测试的过程可以被认为是一个证伪驱动的测试过程。对于高度关键的小段代码，这可以是构建有效模糊测试方案的非常有效的方法。它帮助Paul E. McKenney发现了Linux内核RCU模块中的真实错误。

只是更多模糊测试

或者，在转向变异调查之前，你可以只是更积极地对代码进行模糊测试。我们的变异样本表明不会有太多 outstanding 错误，但也许有几个。五分钟并不是那么极端的模糊测试方案。人们期望运行AFL数天。如果我们真的将红黑树作为关键代码进行测试，我们可能不会在五分钟后放弃。

哪个模糊器最适合这个？很难确定，但一个合理的方法是首先使用libFuzzer生成一个大的测试语料库来播种模糊测试，实现对未变异红黑树的高覆盖率。然后，我们可以尝试对每个变异体进行更长的模糊测试运行，使用种子确保我们不会花费大部分时间只是“学习”红黑树API。

在原始代码上生成语料库一小时后，我们运行libFuzzer，从该语料库开始，运行十分钟。我们以这种方式生成的测试可以在这里找到。这杀死了多少额外的变异体？根据我们3%的样本，我们已经可以猜到它将少于30。一个简单的脚本，如上所述，通过移除注释变异、打印函数变异和断言移除，将有趣、未杀死的、要分析的变异体数量减少到174。事实上，这种更积极（且耗时）的模糊测试杀死的额外变异体为零，超过John的模糊器在一分钟内和libFuzzer在五分钟内已经杀死的那些。即使是一小时的libFuzzer运行与一小时的语料库也只杀死三个额外的变异体，而这些并不是很有趣。一个新的杀死移除一个free调用，内存泄漏最终杀死libFuzzer；另外两个杀死只是更多的指针比较。这是确凿的证据表明我们剩余的变异体（假设我们还没有检查它们 all）是无害的吗？我们将看到。

符号执行呢？

[注意：这部分目前在Mac系统上不起作用，除非你知道足够进行交叉编译，并可以使二进制分析工具与之配合工作。我在docker内的Linux上运行了它。]

DeepState还支持符号执行，根据某些定义，这只是另一种模糊测试（白盒模糊测试）。不幸的是，目前，Manticore和angr（我们支持的两个二进制分析引擎）都无法扩展到完整的红黑树或文件系统示例，搜索深度类似100。这并不真的令人惊讶，考虑到工具试图生成代码的所有可能路径！然而，简单地将深度降低到更合理的数字也是不够的。即使在深度三，你也可能得到求解器超时错误。相反，我们使用symex.cpp，它执行更简单的插入/删除模式，与参考进行比较，连续三次。

1
2
3

clang -c red_black_tree.c container.c stack.c misc.c
clang++ -o symex symex.cpp -ldeepstate red_black_tree.o stack.o misc.o container.o -static -Wl,--allow-multiple-definition,--no-export-dynamic
deepstate-manticore ./symex --min_log_level 1

结果将是覆盖代码所有路径的测试，保存在out目录中。这可能需要相当长的时间来运行，因为每个路径可能需要一两分钟生成，并且有相当多的路径。如果deepstate-manticore太慢，尝试deepstate-angr（反之亦然）。不同的代码最适合不同的符号执行引擎。（这是DeepState的目的之一——使寻找好的后端变得容易。）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

INFO:deepstate.mcore:Running 1 tests across 1 workers
TRACE:deepstate:Running RBTree_TinySymex from symex.cpp(65)
TRACE:deepstate:symex.cpp(80): 0: INSERT:0 0x0000000000000000
TRACE:deepstate:symex.cpp(85): 0: DELETE:0
TRACE:deepstate:symex.cpp(80): 1: INSERT:0 0x0000000000000000
TRACE:deepstate:symex.cpp(85): 1: DELETE:0
TRACE:deepstate:symex.cpp(80): 2: INSERT:0 0x0000000000000000
TRACE:deepstate:symex.cpp(85): 2: DELETE:-2147483648
TRACE:deepstate:Passed: RBTree_TinySymex
TRACE:deepstate:Input: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ...
TRACE:deepstate:Saved test case in file out/symex.cpp/RBTree_TinySymex/89b9a0aba0287935fa5055d8cb402b37.pass
TRACE:deepstate:Running RBTree_TinySymex from symex.cpp(65)
TRACE:deepstate:symex.cpp(80): 0: INSERT:0 0x0000000000000000
TRACE:deepstate:symex.cpp(85): 0: DELETE:0
TRACE:deepstate:symex.cpp(80): 1: INSERT:0 0x0000000000000000
TRACE:deepstate:symex.cpp(85): 1: DELETE:0
TRACE:deepstate:symex.cpp(80): 2: INSERT:0 0x0000000000000000
TRACE:deepstate:symex.cpp(85): 2: DELETE:0
TRACE:deepstate:Passed: RBTree_TinySymex
...

我们可以使用如前所述的变异分析来查看583个生成的测试表现如何。因为我们只是重放测试，而不是执行符号执行，我们现在可以添加回为了加速符号执行而移除的checkRep和RBTreeVerify检查，通过使用-DREPLAY编译symex.cpp，并使用我们所有的清理器编译所有内容。生成的测试，可以在不到一秒内运行（在正确的red_black_tree.c上），杀死428个变异体（38.21%）。这比模糊测试低得多，并且比libFuzzer一小时语料库杀死的797个（71.16%）更差，后者具有类似的<1s运行时间。然而，这个总结隐藏了更有趣的东西：五个被杀死的变异体是我们的任何模糊器都没有杀死的，即使在良好播种的十分钟libFuzzer运行中：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

703c703
<   return left_black_cnt + (node->red ? 0 : 1);
---
>   return left_black_cnt / (node->red ? 0 : 1);
703c703
<   return left_black_cnt + (node->red ? 0 : 1);
---
>   return left_black_cnt % (node->red ? 0 : 1);
703c703
<   return left_black_cnt + (node->red ? 0 : 1);
---
>   /*return left_black_cnt + (node->red ? 0 : 1);*/
701c701
<   right_black_cnt = checkRepHelper (node->right, t);
---
>   /*right_black_cnt = checkRepHelper (node->right, t);*/
700c700
<   left_black_cnt = checkRepHelper (node->left, t);
---
>   /*left_black