变异测试介绍

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

有许多可用的变异测试工具，尤其是针对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模块中的真实错误。

只是更多模糊测试

或者，在转向变异体调查之前，你可以只是更积极地对代码进行模糊测试。我们的变异体样本表明不会有太多突出的错误，但也许有几个。五分钟并不是一个极端的模糊测试方案。人们期望运行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
2
3
4

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

1
2
3
4

701c701
<   right_black_cnt = checkRepHelper (node->right, t);
---
>   /*right_black_cnt = checkRepHelper (node->right, t);*/

1
2
3
4

700c700
<   left_black_cnt = checkRepHelper (node->left, t);
---
>   /*left_black_cnt = checkRepHelper (node->left, t);*/

这些错误都在checkRep代码本身中，甚至不是符号执行的目标。虽然这些错误不涉及实际的红黑树行为故障，但它们表明我们的模糊器可能允许将细微的缺陷引入红黑树检查自身有效性的工具中。在正确的上下文中，这些可能是严重的故障，并且肯定显示了基于模糊器的测试中的差距。为了了解检测这些故障的难度，我们尝试在每个变异体上使用libFuzzer，使用我们的一小时语料库作为种子，每个变异体额外进行一小时的模糊测试。它仍然无法检测到这些变异体中的任何一个。

虽然使用符号执行生成测试需要更多的计算能力，也许还需要更多的人力，但产生的非常彻底（如果范围有限）的测试可以检测到即使积极的模糊测试也可能遗漏的错误。这样的测试肯定是API回归测试套件的一个强大补充。学习使用DeepState使在你的测试中混合模糊测试和符号执行变得容易。即使你需要为符号执行工作一个新的harness，它看起来也可以与你的大多数基于模糊测试的测试共享代码。DeepState的一个主要长期目标是使用不依赖于底层引擎的高级策略来提高符号执行对于API序列测试的可扩展性，因此你可以更频繁地使用相同的harness。

有关如何使用符号执行的更多信息，请参见DeepState repo。

代码覆盖率呢？

我们在模糊测试中甚至没有查看代码覆盖率。原因很简单：如果我们愿意付出努力应用变异测试，并检查所有存活的变异体，那么查看代码覆盖率就没有太多额外的好处。在底层，libFuzzer和符号执行引擎旨在最大化覆盖率，但出于我们的目的，变异体甚至更好。毕竟，如果我们不覆盖变异代码，我们很难杀死它。当然，覆盖率在模糊器harness开发的早期阶段非常有用，其中变异测试昂贵，而你真的只想知道你是否甚至命中了大部分代码。但对于密集测试，当你有时间去做时，变异测试要彻底得多。你不仅必须覆盖代码，还必须测试它的作用。事实上，目前，大多数关于代码覆盖率有用性的科学证据依赖于变异测试的更大有用性。

进一步阅读

有关使用DeepState测试API的更复杂示例，请参见TestFs示例，它测试一个用户级、ext3-like文件系统，或比较Google的leveldb和Facebook的rocksdb行为的差分测试器。有关DeepState的更多详细信息，请参见我们的NDSS 2018 Binary Analysis Research Workshop论文。

如果你喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News