Fuzz Testing¶

Introduction¶

Fuzz的目的是驱动系统执行进入期望的状态。

Evolution¶

基因算法¶

基因算法是一种模拟自然选择的算法。将初始随机种子输入到种子池，通过选择和变异得到种子，以这个种子作为测试用例，执行程序，得到结果，根据结果判断是否是好的种子，如果是，加入到种子池，否则丢弃。

Coverage¶

如果fuzzer生成了一个能够扩大代码覆盖率的测试用例，那么这个测试用例就是好的种子。

覆盖分为Block Coverage(基本块覆盖)、Branch Coverage(分支覆盖)、Return Coverage(返回覆盖)、Path Coverage(路径覆盖)等。

如果我们可以获得一组覆盖程序控制流图（CFG）中每条可行路径的输入集，那么这个程序就被认为是饱和测试的。

路径覆盖是最全面的覆盖，但在实际中很难实现。在实践中，我们更多是采取分支覆盖，因为它在有效性和可行性之间取得了良好的平衡。

Loops: Trouble Maker for Branch Coverage¶

循环会影响分支覆盖的测试，应当使用Bounded Loop Unrolling技术。把循环变成一个一定次数的顺序执行的代码块。

Concolic execution: forced path exploration¶

Narrow-range constraints¶

对于一些约束很窄的情况，使用随机的输入很难找到满足约束的输入。但从另一方面，如果我们知道约束的范围，我们可以使用符号执行来找到满足约束的输入。

让fuzz完成大部分的状态空间探索，然后使用符号推理引擎来解决剩下的约束。

Fuzz 测试工具¶

AFL (American Fuzzy Lop)¶

AFL 是最经典的覆盖率引导模糊测试工具，由 Michal Zalewski 开发。

flowchart TD
    A["种子队列"] --> B["选择种子"]
    B --> C["变异输入"]
    C --> D["执行目标程序（插桩）"]
    D --> E{"新覆盖率？"}
    E -->|是| F["加入种子队列"]
    E -->|否| G["丢弃"]
    F --> A
    G --> A

LibFuzzer¶

LibFuzzer 是 LLVM 项目内置的进程内模糊测试引擎。

1
2
3
4
5
6
7
8

// LLVMFuzzerTestOneInput 是 LibFuzzer 的入口函数
// data: 模糊器生成的输入数据
// size: 输入数据的长度
extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
    // 调用被测函数
    MyFunction(data, size);
    return 0;  // 返回值必须为 0
}

Honggfuzz¶

Honggfuzz 是 Google 开发的另一个覆盖率引导模糊测试工具，支持 硬件辅助覆盖率收集。

覆盖率引导原理详解¶

覆盖率引导是现代 fuzzer 的核心思想。其基本假设是：能够触发新代码路径的输入更有可能发现 bug。

变异策略详解¶

变异策略是 fuzzer 生成新测试用例的核心。好的变异策略应该在 探索性 和 利用性 之间取得平衡。

实际案例¶

Fuzz 测试最佳实践¶