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

背景

2013年，John Regehr发表了《如何对ADT实现进行模糊测试》的博客文章，详细讨论了确保数据类型实现可靠性的通用方法，包括代码覆盖率、测试预言和差分测试。文章还提供了一个可运行的红黑树模糊测试器示例。

传统单元测试的局限性

传统单元测试形式如下：

1
2
3

result1 = foo(3, "hello");
result2 = bar(result1, "goodbye")
assert(result2 == DONE);

这种方法存在两个问题：编写测试工作量巨大，且测试覆盖范围有限，难以发现预期使用场景之外的异常情况。

API模糊测试原理

模糊测试不仅可以生成文件或数据包，还能生成API调用序列来测试软件库。一个典型的模糊测试结构如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

foo_result = NULL;
bar_result = NULL;
repeat LENGTH times:
   switch (choice):
      choose_foo:
         foo_result = foo(randomInt(), randomString());
         break;
      choose_bar:
         bar_result = bar(foo_result, randomString());
         break;
      choose_baz:
         baz_result = baz(foo_result, bar_result);
         break;
   checkInvariants();

DeepState的优势

DeepState提供了完整的测试基础设施，包括：

• 自动保存失败测试用例
• 测试用例最小化以便调试
• 回归测试重放功能
• 支持多种测试生成后端（Manticore、angr、libFuzzer、AFL）

转换John的测试器为DeepState测试

主要修改步骤：

1. 移除main函数，替换为命名测试TEST(RBTree, GeneralFuzzer)
2. 使用固定长度的API调用序列（通过#define LENGTH 100控制）
3. 将rand() % NNN调用替换为DeepState数据生成函数
4. 使用DeepState的OneOf构造替换选择API调用的switch语句

安装和使用DeepState

在macOS上的安装步骤：

1
2
3
4
5
6

git clone https://github.com/trailofbits/deepstate
cd deepstate
mkdir build
cd build
cmake ..
sudo make install

启用libFuzzer支持的构建：

1
2

brew install llvm@7
CC=/usr/local/opt/llvm@7/bin/clang CXX=/usr/local/opt/llvm@7/bin/clang++ BUILD_LIBFUZZER=TRUE cmake ..

测试红黑树实现

构建测试套件：

1
2
3

git clone https://github.com/agroce/rb_tree_demo
cd rb_tree_demo
make

使用不同测试方法：

• 简单模糊测试：./ds_rb --fuzz --timeout 60 --output_test_dir tests
• 使用libFuzzer：./ds_rb_lf corpus -use_value_profile=1 -detect_leaks=0 -max_total_time=60

测试用例重放和缩减

重放测试用例：

1
2

./ds_rb --input_test_file file
./ds_rb --input_test_files_dir dir --exit_on_fail

测试用例缩减：

1

deepstate-reduce ./ds_rb test_file.crash minimized.crash

实际漏洞检测演示

通过修改红黑树实现中的一行代码（将x->parent->parent->red=1改为0），演示了DeepState如何快速发现并记录该漏洞，并生成最小化的测试用例。

结论

DeepState将手写的模糊测试器转换为功能完整的测试生成器，支持多种测试生成后端，并提供专业的测试基础设施。在第二部分中将进一步评估测试质量并探讨符号执行的应用。