关于测试用例缩减的一切：你不知道但应该问的问题
想象一下，在几乎不需要人工干预的情况下，减少测试软件所需的代码量和时间，同时提高测试效果并使调试任务更容易。这听起来好得令人难以置信，但我们将解释测试用例缩减如何实现所有这些（甚至更多）。
了解缩减的工作原理有助于故障排除，并更容易找出高效的工作流程和优化测试的最佳工具。我们将解释为什么测试用例缩减是安全工程师特别需要理解的重要主题，并看看DeepState的最先进缩减器。
测试用例缩减对人类的意义
测试用例缩减最常见的目的是将一个复杂的失败测试用例（针对已确认的错误）转换为更容易理解的版本，以便简化调试。但您也可能希望忽略低优先级的错误！拥有这些错误的简化版本有助于快速识别未来相同不重要问题的重复提交。对于未确认的错误，缩减测试用例可能更为关键，因为在简化之前，您通常无法判断错误是否是重复的（甚至是否是错误）。您可能会发现问题出在您的规范、测试生成工具或操作系统上。
如果没有一个可以轻松理解并简洁描述的缩减测试用例，很难说您有一个错误。您可能有证据表明软件系统行为异常，但当测试用例足够复杂时，“一个错误”可能是一个可疑的概念。一个复杂的测试用例几乎类似于一个数学证明，只显示具有某种属性的整数必须存在；如果您想做一些需要实际数字的事情，您的证明需要是建设性的。
假设您有一个非常大的、随机生成的HTML文件，会导致Chrome崩溃。您可能发现了一个重要的错误；或者您只是做了一些导致Chrome以预期方式耗尽内存的事情。如果您的唯一结论是“当我在Chrome中加载这个巨大文件时，它停止运行”，您实际上并不了解多少。在这种情况下，您可能希望应用测试用例缩减器，而不是花时间查看核心文件并附加调试器。如果它将文件缩减到单页HTML，或者更好的是，缩减到像单个SELECT标签这样小的东西，您就有了理解正在发生什么的捷径。
测试用例缩减在网络安全中有直接应用，特别是当模糊器用于从随机输入生成的崩溃中构建漏洞利用时。输入越简单，构建漏洞利用或意识到错误无法被利用就越容易。AFL和libFuzzer提供内置的有限测试用例缩减，但有时您需要更多。现代测试用例缩减工具可以简化这种分析，如果您想生成复杂的API调用序列以在TLS、SQLite或LevelDB等库中找到漏洞，它们可能是必不可少的。这个概念也扩展到模糊测试智能合约，这就是为什么Trail of Bits的智能合约模糊器Echidna包含一个测试用例缩减器。
测试用例缩减对机器的意义
测试用例缩减不仅仅使测试更容易人类阅读；它对核心网络安全任务如模糊测试、符号执行和错误分类非常有用。缩减器可以：
- 减少执行时间：这在为大型复杂程序运行巨大回归套件时非常重要。用单个SELECT标签测试Chrome比用多GB文件测试更高效。在慢速执行环境（如Android模拟器）中尤其有帮助。
- 提高基于变异的模糊器的性能：当模糊器使用现有测试生成新测试用例时，如果测试用例不包含大量不相关的垃圾，它们有更高的机会探索有趣的路径。这就是为什么AFL和libFuzzer喜欢只对每个覆盖元素使用最小和最快运行的输入进行模糊测试。
- 更容易解决符号执行约束：如果涉及较少无趣的执行，生成的约束更容易解决。更多细节可以在Zhang等人的论文中找到。
- 避免不稳定测试：有时通过、有时失败的测试，在不更改测试代码的情况下，被称为“不稳定测试”，它们是谷歌规模测试软件中最关键的问题之一。测试用例缩减是最近提出的自动修复一些不稳定测试算法的核心部分。
- 去重模糊测试错误：当测试用例被缩减时，自动“模糊器驯服”——在由模糊器产生的大量大多重复的测试用例中找到实际错误集——更有效。如果移除不相关的部分，相同错误的测试用例更相似。
- 提高故障定位工具性能：故障定位的一个核心问题是失败测试用例执行大量非故障代码。当失败的测试运行较少的非错误代码时，找出坏代码隐藏的位置更容易。缩减测试用例减少了执行的非故障代码量，并使故障定位算法更容易。
- 帮助未来验证测试：在某些情况下，缩减的测试用例可能比原始测试更有效地在未来软件版本中找到错误；缩减的测试可能对当前代码的过拟合较少。
- 从现有测试创建新测试。
- 使软件适应资源较少的环境：缩减器也可以将程序作为输入，这成为最近提出的自动使程序适应可用资源较少环境的方法的核心。
- 提供模糊测试的替代方法：最后，正如John Regehr指出的，“缩减器是模糊器。”测试用例缩减可能用于帮助发现软件系统中以前未知的错误，尽管目前尚不清楚这种新的模糊测试方法到底有多有效。
如果您想搜索关于测试用例缩减的文献，它也被称为最小化、收缩，最初是delta-debugging。所有这些名称都指同一个过程：取一个执行X的程序输入A，并产生一个更小的输入B，也执行X。
使用测试用例缩减器
让我们看看测试用例缩减的实际操作。启动DeepState docker镜像，并安装testfs存储库，这是一个用于用户模式ext3-like文件系统的DeepState harness。
1
2
3
4
|
> git clone https://github.com/agroce/testfs.git
> cd testfs
> cmake .
> make
|
我们的DeepState harness允许我们在操作中间模拟设备重置，并检查由中断文件系统调用引起的问题。它检查重置后文件系统是否仍然可以挂载。为了生成显示这并不总是成立的测试用例，我们可以只使用DeepState的内置模糊器：
1
2
|
> mkdir failure
> ./Tests --fuzz --output_test_dir failure --exit_on_fail --seed 10
|
DeepState将报告一个问题，并将结果测试用例保存在具有唯一文件名ID和.fail扩展名的文件中。让我们看看产生文件系统损坏的序列。为简洁起见，我们只显示下面的实际测试步骤。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
> ./Tests --input_test_file failure/dbb393e55c77bac878ab06a02a022370e33761cb.fail
TRACE: Tests.cpp(115): STEP 0: tfs_lsr(sb);
TRACE: Tests.cpp(140): STEP 1: tfs_stat(sb, ".a.BBA");
TRACE: Tests.cpp(146): STEP 2: tfs_cat(sb, "/aAb.BaAb");
TRACE: Tests.cpp(140): STEP 3: tfs_stat(sb, ");
TRACE: Tests.cpp(115): STEP 4: tfs_lsr(sb);
TRACE: Tests.cpp(103): STEP 5: tfs_rmdir(sb, "BB");
TRACE: Tests.cpp(146): STEP 6: tfs_cat(sb, "b");
TRACE: Tests.cpp(110): STEP 7: tfs_ls(sb);
TRACE: Tests.cpp(95): STEP 8: tfs_mkdir(sb, "A");
TRACE: Tests.cpp(146): STEP 9: tfs_cat(sb, "a./b");
TRACE: Tests.cpp(103): STEP 10: tfs_rmdir(sb, "AaBbBB.A.");
TRACE: Tests.cpp(130): STEP 11: tfs_write(sb, "BA/BB/", "yx");
TRACE: Tests.cpp(140): STEP 12: tfs_stat(sb, "bba");
TRACE: Tests.cpp(155): STEP 13: set_reset_countdown(4);
TRACE: Tests.cpp(140): STEP 14: tfs_stat(sb, "/A");
TRACE: Tests.cpp(121): STEP 15: tfs_create(sb, "bA");
|
此输出显示了达到super.c第252行断言违规所需的16个步骤，当我们在重置后尝试重新挂载文件系统时。但是所有这些步骤都是必要的吗？我们真的需要cat文件"a./b"才能发生这种情况吗？我们将使用DeepState的缩减器来找出答案。
1
|
> deepstate-reduce ./Tests failure/dbb393e55c77bac878ab06a02a022370e33761cb.fail failure/shrink.fail
|
您将看到类似以下的输出：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
Original test has 8192 bytes
Applied 75 range conversions
Last byte read: 307
Shrinking to ignore unread bytes
Writing reduced test with 308 bytes to failure/shrink.fail
================================================================================
Iteration #1 0.18 secs / 2 execs / 0.0% reduction
Structured deletion reduced test to 304 bytes
Writing reduced test with 304 bytes to failure/shrink.fail
0.36 secs / 3 execs / 1.3% reduction
================================================================================
Structured deletion reduced test to 272 bytes
Writing reduced test with 272 bytes to failure/shrink.fail
0.5 secs / 4 execs / 11.69% reduction
================================================================================
Structured deletion reduced test to 228 bytes
Writing reduced test with 228 bytes to failure/shrink.fail
0.6 secs / 5 execs / 25.97% reduction
…
1-byte chunk removal: PASS FINISHED IN 0.24 SECONDS, RUN: 1.45 secs / 57 execs / 95.78% reduction
4-byte chunk removal: PASS FINISHED IN 0.08 SECONDS, RUN: 1.53 secs / 70 execs / 95.78% reduction
8-byte chunk removal: PASS FINISHED IN 0.08 SECONDS, RUN: 1.61 secs / 83 execs / 95.78% reduction
1-byte reduce and delete: PASS FINISHED IN 0.02 SECONDS, RUN: 1.62 secs / 86 execs / 95.78% reduction
4-byte reduce and delete: PASS FINISHED IN 0.01 SECONDS, RUN: 1.64 secs / 88 execs / 95.78% reduction
8-byte reduce and delete: PASS FINISHED IN 0.01 SECONDS, RUN: 1.64 secs / 89 execs / 95.78% reduction
Byte range removal: PASS FINISHED IN 0.31 SECONDS, RUN: 1.96 secs / 141 execs / 95.78% reduction
Structured swap: PASS FINISHED IN 0.01 SECONDS, RUN: 1.96 secs / 142 execs / 95.78% reduction
Byte reduce: PASS FINISHED IN 0.1 SECONDS, RUN: 2.06 secs / 159 execs / 95.78% reduction
================================================================================
Iteration #2 2.06 secs / 159 execs / 95.78% reduction
Structured deletion: PASS FINISHED IN 0.01 SECONDS, RUN: 2.08 secs / 161 execs / 95.78% reduction
Structured edge deletion: PASS FINISHED IN 0.01 SECONDS, RUN: 2.09 secs / 163 execs / 95.78% reduction
================================================================================
Completed 2 iterations: 2.09 secs / 163 execs / 95.78% reduction
Padding test with 23 zeroes
Writing reduced test with 36 bytes to failure/shrink.fail
|
几秒钟后，我们可以运行新的、更小的测试用例：
1
2
3
4
5
6
7
|
> ./Tests --input_test_file failure/shrink.fail
TRACE: Tests.cpp(155): STEP 0: set_reset_countdown(4);
TRACE: Tests.cpp(121): STEP 1: tfs_create(sb, "aaaaa");
CRITICAL: /home/user/testfs/super.c(252): Assertion (testfs_inode_get_type(in) == I_FILE) || (testfs_inode_get_type(in) == I_DIR) failed in function int testfs_checkfs(struct super_block *, struct bitmap *, struct bitmap *, int)
ERROR: Failed: TestFs_FilesDirs
ERROR: Test case failure/shrink.fail failed
|
为了在重置中断下“破坏”testfs，我们只需要在创建文件"aaaaa"时第四次写入块时导致重置。使用调试器或日志语句来理解这种行为显然比使用原始测试用例更愉快。
对于这个错误，我们只需要给deepstate-reduce：
- DeepState harness可执行文件（./Tests），
- 要缩减的测试用例（dbb393e55c77bac878ab06a02a022370e33761cb.fail），以及
- 要生成的新缩减测试用例（failure/shrink.fail）。
但有时我们需要提供更多信息。例如，如果我们只要求缩减的测试失败，测试用例可能在缩减过程中“改变错误”。缩减器可以接受一个额外的要求，形式为必须出现在输出中的字符串或正则表达式，或所需的退出代码。
关于代码覆盖率的缩减
缩减器也可以在