使用DeepState进行API模糊测试（第二部分）
变异测试介绍
手动引入一个错误（如我们在第一部分中所做）是可以的，我们可以再次尝试，但“轶事的复数并不是数据”。然而，这并不完全正确。如果我们有足够的轶事，我们或许可以称之为数据（“大数据多重轶事”领域预计随时会起飞）。在软件测试中，创建多个“假错误”有一个名称，即变异测试（或变异分析）。变异测试通过自动生成对程序的许多小更改来工作，期望大多数此类更改会使程序不正确。一个测试套件或模糊器如果检测到更多这些更改，则更好。在变异测试的行话中，检测到的变异体被“杀死”。这种措辞对变异体有点苛刻，但在测试中，对错误保持某种铁石心肠是合适的。变异测试曾经是一个学术小众话题，但现在已在主要公司的现实世界情境中使用。
有许多可用的变异测试工具，特别是针对Java。对于C代码的工具通常不太健壮，或更难以使用。我（与NAU和其他大学的同事一起）最近发布了一个工具，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秒；除非你的机器非常慢，否则这有足够的时间编译我们的代码）。
如果我们将包含有效（编译）变异体的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 KILLEDRUNNING 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.78541398048RUNNING 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的详细性会隐藏我们实际的变异结果：
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个额外的变异体，我们会发现每一个都涉及将指针上的相等比较更改为不等比较。例如：
< if ( (y == tree->root) ||> assert (node->right->parent >= node);
如果我们假设断言对原始代码总是成立，那么将==更改为更宽松的>=显然不会失败。
第七个变异体潜伏在注释中。
第八个变异体删除了一个断言。同样，删除一个断言永远不会导致先前通过的测试失败，除非你的断言有问题！
第九个变异体更改了一个红色赋值：
243c243
< x->parent->parent->red=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);> /*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论文。
更多精彩内容 请关注我的个人公众号 公众号（办公AI智能小助手）
公众号二维码
