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

Alex Groce
2019年1月23日
动态分析、模糊测试、Manticore、符号执行
Alex Groce，北亚利桑那大学信息、计算与网络系统学院副教授

变异测试

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

有许多可用的变异测试工具，尤其是针对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函数内部。

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

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

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

只是更积极地模糊测试

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

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

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

符号执行呢？

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

1
2
3
4


703c703
<   return left_black_cnt + (node->red ? 0 : 1);
---
>   return left_black_cnt / (node->red ? 0 : 1);

1
2
3
4


703c703
<   return left_black_cnt + (node->red ? 0 : 1);
---
>   return left_black_cnt % (node->red ? 0 : 1);

1

703