变异测试
变异测试（Mutation Testing）（有时也叫做“变异分析”）是一种在细节方面改进程序源代码的软件测试方法。这些所谓的变异，是基于良好定义的变异操作，这些操作或者是模拟典型应用错误（例如：使用错误的操作符或者变量名字），或者是强制产生有效地测试（例如使得每个表达式都等于0）。目的是帮助测试者发现有效的测试，或者定位测试数据的弱点，或者是在执行中很少（或从不）使用的代码的弱点。
在上一篇文章中，我已经手动引入了一个漏洞，就是方便进行变异测试。目前有许多可用于变异测试的工具，其中大部分是用Java编写的。一般而言，用C代码编写的工具都不太稳定，或很不好用。为此，我和其他同事还专门编写了一个工具，即universalmutator，这是一个纯粹基于正则表达式指定的代码行重写来生成变异的工具，允许多种语言的变异，包括C和C ++以及Swift，Solidity，Rust等许多以前没有变异测试工具的其他语言。我将在本文中使用universalmutator来查看模糊器在检测人工红黑树漏洞方面的表现。除了常规检测之外，universalmutator的一个优点是它可以产生许多新的变异对象，包括那些经常等同但有时会产生微妙的行为差异的变异对象。也就是说，这些微妙的变异对象很可能就是某个难以被检测到的漏洞。另外，目前大多数变异系统都不支持这些变异对象。
安装universalmutator并生成一些变异对象很容易：
pip install universalmutator mkdir mutants mutate red_black_tree.c --mutantDir mutants |
这将产生大量的变异对象，其中大多数不会编译（universalmutator不会解析C代码，所以毫不奇怪它的许多变异对象都不是有效的C），我可以通过对变异对象运行“变异分析”来解析变异对象。
| analyze_mutants red_black_tree.c "make clean; make" --mutantDir mutants |
这将生成两个文件：killed.txt，包含没有经过编译的变异对象，以及notkilled.txt，包含实际编译的1120个变异对象。为了查看变异某个对象是否被禁用，分析工具只是确定引号中的命令是返回非零退出代码还是超时即可。默认超时为30秒，除非你的设备运行速度很慢，否则30秒最够用了。
如果我将包含有效（编译）变异对象的notkilled.txt文件复制到另一个文件，我就可以进行一些真正的变异测试：
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 |
输出内容如下所示：
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的冗长输出会干扰实际的变异结果的输出，为了加快测试速度，我要将环境变量LIBFUZZER_EXIT_ON_FAIL设置为TRUE，并将输出管道设置为/dev/null。
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 |
该工具会生成2602个变异对象，但实际编译的只有1120个。通过60秒的测试预算来分析这些变异对象，我可以更好的了解模糊测试的质量。DeepState的BF(Brute-Force)算法模糊器禁用了其中的797个变异对象（71.16％），而John的原始模糊器则禁用了822（73.39％）个变异对象。接着，再花60秒模糊那些没有被这些模糊器禁用的变异体，我发现它们还是不会被禁用。libFuzzer的性能竟然和DeepState惊人地相似，60秒内禁用797个变异体。这说明，变异对象是一样的。
可见，DeepState的模糊器在前期的模糊效果不如John的模糊器。这并不奇怪，因为在模糊测试中，速度是王道。因为DeepState正在解析字节流，为了保存崩溃而分叉，并生成大量的、用户控制的日志记录，因此它不可能像John的模糊器一样快速的生成和执行测试。
而libFuzzer的速度甚至更慢，除了DeepState模糊器提供的所有服务（(除了崩溃分岔，崩溃分岔由libFuzzer自己处理）之外，libFuzzer还确定代码覆盖率，并为每个测试计算值概要文件，并执行基于这些输入质量评估的未来测试所需的计算。
这就是John的模糊器禁用25个变异对象的原因，那DeepState就完全不禁用这些变异对象吗？不完全是。如果我检查另外25个变异对象，就会发现每个变异对象都涉及到将指针上的等式比较变成不等式。例如:
< if ( (y == tree->root) || --- > if ( (y <= tree->root) || |
DeepState模糊器没有找到这些变异对象，因为它在fork中运行每个测试。另外，因为大多数分配都在fork中，代码没有分配足够的时间来使用足够的地址空间来对这些特定的检查进行测试。从理论上讲，libFuzzer不应该出现这种情况，它运行时没有分叉。当然，如果我们给缓慢而稳定的libFuzzer 5分钟而不是60秒，它也会捕捉到所有这些变异对象。再多的模糊处理也不能帮助DeepState模糊器，在这种情况下，这个漏洞就显得非常奇怪，而且不太容易被忽略。问题不在于模糊器的速度，也不在于测试的质量，而是不同的模糊测试环境在我实际运行的测试中产生细微差别。
要解决这个问题，就只有在DeepState中添加了一个选项，使采用BF(Brute-Force)算法的模糊器以非分叉模式运行：–no_fork。不幸的是，这不是一个完整的解决方案。虽然我现在可以检测到这些漏洞，但我无法为它们生成一个好的保存测试用例，因为失败取决于已发出的所有malloc，以及某些指针的确切地址。然而，事实证明–no_fork有一个更重要的好处：它大大加快了mac OS上的模糊测试和测试重放速度。不过我在示例中省略了它，因为它使分析失败原因变得复杂，但你应该将其用于mac OS上的大多数模糊测试和测试重放。
现在，我可以确切的说，对于大多数模糊测试的意图和目的，DeepState与John的模糊器一样强大，且DeepState易于实现，并且更便于调试和回归测试。
变异对象的检测
以上我成功的解决了不同模糊器上所禁用的那些变异对象之间的差异，接下来，我就来说一说那些剩下的没有被禁用的变异对象。
使用任何一种模糊器进行五分钟的模糊测试，都没有禁用剩下的变异对象。它们在测试中是否显示漏洞？目前，有多种方法可以检测等效的变异对象（实际上不会改变程序语义的变异对象，因此不可能被禁用），例如比较优化编译器生成的二进制文件。为了本文的讲解方便，我将只检查298个未被禁用的变异对象的随机样本，以确定至少大多数未被禁用的变异对象都是无意义的。
第一个变异对象更改注释中的<=，我们不可能禁用它。比较编译后的二进制文件就可以证明这一点。
第二个变异对象修改了InorderTreePrint函数中的代码，模糊器会明确选择不测试该对象。通过比较二进制文件无法检测到这一变异，如果我的模糊器从未覆盖过这段代码，则它不能很好地检测代码中的漏洞。
第三个变异对象在RBTreeCreate函数中将赋值更改为第44行的temp->key，因此赋值为1而不是0。如果我按照代码的建议并查看标头文件中关于root和nil的注释，我可以看到它们被用作标记。也许root和nil中的确切数据值无关紧要，因为我只通过指针比较来检测它们。
第四个变异对象删除在第35行的赋值newTree-> PrintKey = PrintFunc，再说一遍，因为我从来没有打印过树，所以这是检测不到的。
第五个变异对象在评论中，第六个变异对象更改断言中的指针比较。
686c686 < assert (node->right->parent == node); --- > assert (node->right->parent >= node); |
如果假设我对原始代码始终保持断言，那么将==更改为更宽松的>=显然也是可以的。
第七个变异对象在评论中，第八个变异对象删除了一个断言。同样，删除断言是不会导致先前传递的测试发生失败，除非断言出现问题！
第九个变异对象改变了一个红色赋值：
243c243 < x->parent->parent->red=1; --- > x->parent->parent->red=-1; |
因为我没有检查红色字段的确切值，而是使用它进行分支(因此所有非零值都是相同的)，所以这样做没有问题。
第十个变异对象再次位于InorderTreePrint函数中。
此时，如果我真的要把这个红黑树作为关键代码，我可能会进行如下操作：
1. 创建一个工具(比如一个10行Python脚本)来删除注释、InorderTreePrint函数内部的所有变体，或者直接删除断言。
2.编译所有变异对象并比较二进制文件和原始文件，以删除明显的等效变异对象和冗余变异对象。这一步可能有点耗时，由于编译时生成的时间戳，编译器并不总是生成等效的二进制文件，这就是我在上面的讨论中跳过它的原因。
3.仔细检查剩余的变异对象（大概200个左右），以确保我没有遗漏任何东西。
（1）制作一个测试生成器；
（2）应用变异测试；
（3）观察实际剩余的变异对象，并使用它们改进我们的测试，这个过程可以被认为是一个变异驱动的测试过程。对于非常关键的小段代码，这可能是构建有效的模糊机制的非常有效的方法。它曾帮助过Paul E. McKenney发现了Linux内核RCU模块中真正漏洞。
优化模糊测试过
除了进行变异对象的模糊测试外，你还可以模糊代码。如果我真的将红黑树作为关键代码测试，需要的时间可能会超过五分钟。
哪个模糊器最适合模糊代码呢？虽然我很难确定，但合理的方法是首先使用libFuzzer生成一个大型的测试语料库，从而在未变异的红黑树上实现高覆盖率。然后，我可以尝试对每个变异对象进行更长时间的模糊测试，使用测试语料库来确保我不会花费大部分时间在“学习”红黑树API上。
在原始代码上生成语料库一小时后，我从该语料库开始运行libFuzzer，运行时间为十分钟。以这种方式生成的测试可以在这里找到，这会禁用多少个额外的变异对象？在我的3％样本中，这个数量会少于30个。如上所述，通过删除注释变异、打印函数变异和删除断言，一个简单的脚本可以将需要分析的有意义的、未禁用的变异的数量减少到174个。事实上，这种更具侵略性(也更耗时)的模糊处理会在一分钟内禁用John的模糊器并在五分钟内禁用libFuzzer。即使是长达一小时的libFuzzer运行一小时的语料库也只会禁用另外三个变异对象，而这些变异对象并不是很有意义。禁用了一个free调用，内存泄漏会最终禁用libFuzzer。
符号执行
注意：符号执行这部分目前在Mac系统上不起作用，除非你知道足够的交叉编译知识，并且可以使用二进制分析工具。我是在Docker中的Linux上运行符号执行的。
DeepState还支持符号执行，根据某些定义，符号执行只是另一种模糊测试（白盒模糊测试）。不幸的是，目前无论是Manticore还是angr(我擅长的两个二进制分析引擎)都无法扩展到搜索深度为100完整的红黑树或文件系统示例。这并不奇怪，因为工具正在尝试生成代码中所有可能的路径!然而，仅仅将深度降低到一个更合理的数字也是不够的。即使在深度为3时，也可能出现求解器超时错误。所以，我使用了symex.cpp，它执行更简单的插入或删除模式，且连续执行三次。
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 --log_level 1 |
结果将是覆盖代码中所有路径的测试，保存在out目录中。这可能需要相当长的时间才能运行，因为每条路径可能需要一两分钟才能生成。如果deepstate-manticore太慢，请尝试deepstate-angr。不同的代码适合不同的符号执行引擎。
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％）更差。然而，其中五个被禁用的变异对象是未被我的任何模糊器禁用的变异对象，即使是放在libFuzzer中运行十分钟。
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_cnt = checkRepHelper (node->left, t);*/ |
这些漏洞都在checkRep代码本身中，甚至不是符号执行的目标。虽然这些漏洞不涉及实际的红黑树漏洞，但这也间接表明我的模糊器可以允许将细微的漏洞引入红黑树的工具中以检查其自身的有效性。在实际的操作环境中，这些可能是严重的漏洞，并且在基于模糊的测试中肯定显示出一个漏洞。为了了解检测这些漏洞的难度，我尝试在每个变异对象上使用libFuzzer，我用一小时的语料库作为模糊测试的对象，再对每个变异对象进行一次模糊测试。它仍然无法检测到这些变异对象。
虽然使用符号执行生成测试需要更多的计算能力，并且可能需要更多的人力，但是结果的非常彻底（如果范围有限）测试可以检测即使是攻击性模糊测试可能会错过的漏洞。学习使用DeepState会使测试中混合模糊和符号执行变得容易。即使你需要一个用于符号执行工作的新工具，它也可以与大多数基于模糊的测试共享代码。DeepState的最终目标是使用不依赖于底层引擎的高级策略来提高API序列测试的符号执行的可伸缩性。
有关如何使用符号执行的更多信息，请参阅DeepState报告。
代码覆盖率
我没有在我的模糊测试中查看代码覆盖率，原因很简单，如果我愿意使用变异测试，并检查所有未被禁用的变异对象，那么查看代码覆盖率就没有意义了。其实，libFuzzer和符号执行引擎的目标是最大限度地提高覆盖率，但就我本文的目的而言，变异对象才是重点。毕竟，如果我不覆盖变异的代码，就很难禁用它。当然，在模糊器利用开发的早期阶段，测试代码覆盖率是非常有用的。这是因为变异测试是非常昂贵的，而你只是想知道你是否已经完成了大部分代码。但是对于专业的测试，不仅需要测试代码覆盖率，还必须测试它的功能。事实上，目前，关于代码覆盖有用性的大多数科学证据都依赖于变异测试。
总结
相关文章：使用DeepState对API进行模糊测试（上）http://www.51testing.com/html/29/n-4458029.html
上文内容不用于商业目的，如涉及知识产权问题，请权利人联系博为峰小编(021-64471599-8017)，我们将立即处理。
