背景
2013年，John Regehr发表了《如何对ADT实现进行模糊测试》的博文，详细讨论了验证数据结构可靠性的通用方法，包括代码覆盖率、测试预言和差分测试等技术。本文基于该工作，使用DeepState测试框架对其手工编写的红黑树模糊测试工具进行了现代化改造。
传统测试的局限性
传统单元测试模式存在两个根本问题：
- 需要大量手工编写测试用例
- 难以覆盖非预期场景
1
2
3
4
|
// 典型单元测试示例
result1 = foo(3, "hello");
result2 = bar(result1, "goodbye")
assert(result2 == DONE);
|
DeepState解决方案
DeepState提供了类似GoogleTest的测试框架，但增加了以下关键能力：
- 支持多种测试生成后端（libFuzzer/AFL/Manticore等）
- 自动失败测试用例保存与最小化
- 测试序列回放功能
改造后的测试模板：
1
2
3
4
5
|
OneOf(
[&] { /* 插入操作 */ },
[&] { /* 查找操作 */ },
[&] { /* 删除操作 */ }
);
|
关键技术实现
- 测试参数化：
1
|
#define LENGTH 100 // 控制每个测试的API调用次数
|
- 数据生成：
1
2
3
|
int GetValue() {
return DeepState_IntInRange(0, valueRange);
}
|
- 操作选择：
1
2
3
4
|
OneOf(
[&] { RBTreeInsert(tree, ip, vp); },
[&] { RBExactQuery(tree, &key); }
);
|
实战演示
注入Bug测试
修改红黑树着色逻辑后：
1
2
|
- x->parent->parent->red=1;
+ x->parent->parent->red=0;
|
测试执行
1
|
./ds_rb --fuzz --exit_on_fail
|
输出显示在48次操作后发现断言违规：
1
|
Assertion failed: (left_black_cnt == right_black_cnt)
|
测试用例最小化
使用deepstate-reduce工具将测试用例从8KB缩减到50字节：
1
|
deepstate-reduce test.crash minimized.crash
|
最小化后的测试仅需3次重复插入即可触发Bug：
1
2
3
|
TRACE: 0: INSERT:0 0x00000000
TRACE: 1: INSERT:0 0x00000000
TRACE: 2: INSERT:0 0x00000000
|
环境配置
- 安装DeepState：
1
2
3
4
|
git clone https://github.com/trailofbits/deepstate
cd deepstate/build
cmake .. -DBUILD_LIBFUZZER=TRUE
make install
|
- 构建测试目标：
1
2
|
git clone https://github.com/agroce/rb_tree_demo
CC=clang CXX=clang++ make
|
测试执行模式
- 基础模糊测试：
1
|
./ds_rb --fuzz --timeout 60
|
- 使用libFuzzer：
1
|
./ds_rb_lf corpus -max_total_time=60
|
- 测试回放：
1
|
./ds_rb --input_test_file bug.crash
|
（第二部分将探讨测试质量评估方法和符号执行技术的应用）