最近在学习 fuzz，写一篇文章来梳理一下相关芝士

目前只做了一个框架，具体的技术细节之后再填补进来

[1] 原理

[1-1] 什么是 fuzz?

fuzzer 是实施 fuzz 这一操作的工具，它将一系列测试样本 (testcase) 输送给 PUT(Program Under Test)，用以检测 PUT 在大量测试样本下功能是否可以正常运行。所以通俗来说，fuzz 技术就是生成一堆 testcases，然后让 PUT 去执行这些 testcases。

但我们也知道，程序的输入集合可以是无穷大的（程序可以有任意的输入），但能触发 bugs 的输入集合的大小却远小于程序的输入集合，我们称这种现象为 sparse defects space。如果算力也是无穷、计算速度可以忽略不计的话，我们当然可以遍历输入空间来“大海捞针”，但事实是我们并不能这样做。因此，我们需要找到最优的 testcases，这些 cases 可以在最短时间内找到最多的 bugs。

那么，我们如何找到这样的 cases 呢？我们得先搞明白什么样的 testcases 是最优的。

[1-2] 什么样的 testcases 是“最优”的？

在 fuzz 领域中，研究者将 testcases 的度量指标称为 fitness。如果 fitness 好，就说明这个 testcases 是好的，它代表的 seed 也是好的。

常见的 fitness 主要是 bugs 和 coverage。bugs 的思想很朴素，就是如果你这个 testcases 找到了 bugs，就说明这类 testcases 是好样的。不过这种方式还是太片面了，因为 defects space 是 sparse 的，能找到这种 bugs 的 testcases 并不代表它能找到其他 bugs。所以研究者们又提出了 coverage 这个 fitness。

[1-2-1] Coverage

常见的 coverage 有很多：code coverage, instruction coverage, edge coverage, basic block coverage and etc. 最常见的还是 code coverage 和 edge coverage。

code coverage 多应用于源代码，比如我们可以检测这个 testcases 经过的行覆盖率(line)、分支覆盖率(branch)、函数覆盖率(function)以及语句覆盖率(statement)，这些 coverage 的测量可以帮助 fuzzer 理解这个 testcases 是否充分覆盖了代码逻辑。而 edge coverage 主要基于代码的控制流图(CFG)。

种类虽然多，但不用死记硬背，最重要的还是把握这种思想，用 coverage 作为 testcases 的评价标准。

[1-3] 如何找最优的 testcases?

我们已经确定了什么样的 testcase 是最优的，接下来就是去寻找这样的用例了。

最朴素的想法是，我们随机构造一堆输入作为 testcases 输入给 PUT，然后检测每个 testcases 的 fitness。但前文说过的 sparse defects space 使得这种方法十分低效，因此我们需要找到更有效的方式。

我们都知道，某种程序肯定主要用来处理固定格式的输入，比如 PDF parser 处理 PDF 文件、正则引擎处理正则表达式、DOM 处理器处理 DOM 格式的输入...那么我们可以根据测试对象的不同，保证输入格式几乎完全符合对象的要求（如果要 fuzz 错误格式我们也可以调整），以此来大幅度缩减 fuzzer 要搜索的 testcases 空间。那么，有些读者朋友可能就要问了：主播主播，如何做到你说的这一点呢？很简单的兄弟，你继续往下看就知道了。

[1-3-1] 构建 initial seed pool

首先，我们需要构建一个 seed pool(也有人叫它 seed set)，保证我们的 testcases 是围绕 PUT 去生成的，至少不会卡在程序对格式的 validation。

生成 seed pool 主要有三种方式： 第一，程序的开发者都会给程序提供 benchmark，我们可以直接把 benchmark 作为 initial seed pool。 第二，对于那些常见的文件格式，我们可以通过 crawler 来获得网上现有的文件，以此初始化种子池。 第三，可以使用别人做过的 POC Sample，这些也是极好的输入用例。

但是我们知道这些都是已经被 PUT 处理过的 testcases 了，只有这些肯定是不够的，我们需要新的 testcases，该怎样生成呢？

[1-3-2] 生成新的 testcases

根据 testcases 生成方式的不同，研究者们把 fuzzer 分为两类：Generation-based fuzzer 和 Mutation-based fuzzer。

我还没有搞明白 generation 和 mutation 有什么本质上的区别，因为感觉都是基于初始 seed 和某种规则变幻而来的。可能是由于 mutation 是在 seed 的基础上做一些操作，而 generation 是直接基于 seed 的格式生成一些内容？

这一部分先打上一个问号，我先大概讲述一下 mutation-based fuzzer 的原理。

[1-3-2-1] Mutation-based Fuzzer

在讲 mutation-based fuzzer 之前，我们先来说一下遗传算法(Evaluation Algorithm, EA)。

遗传算法的逻辑大概是这样的：假设我们有一个种群(population)，里面有许多个体(individual)。根据适者生存的法则，对环境适应度较好(higher fitness)的个体会生存下来(higher energy)，而不能适应环境的个体则会被淘汰(low energy)。生存下来的个体会产生后代，后代保持着与祖先类似的基因，但是由于基因变异(Mutation)，后代的部分基因会不同于祖先，这种基因的多样性一定程度上保证了对新环境(new fitness feedback)的适应性。

换到 fuzzer 中，EA 的逻辑是这样的：假设我们有一个总祖先为 seed0 的种群(population)，里面有许多由 seed 生成的 testcases(individual)。根据适者生存的法则，具有较高 code coverage 的 testcases 会生存下来(给这个 testcases 或者它对应的 seed 赋予更多的 energy，energy之后在细讲，这里理解个大概意思就行)。energy 未耗尽的 seed 或者 testcases 会继续变异产生新的 testcase，这样的逻辑一定程度上保证里 fuzzer 趋于选择具有更高 code coverage 的 testcases。

那么，如何变异呢？对于程序来说，它的输入无非就是一堆字节，我们要做的事情只有两件：①确定变异哪些字节(WHERE) ②如何变异这些字节(HOW)

WHERE TO MUTATE. 最朴素的思想还是随机挑一些字节来变异。但目前的研究主要使用程序分析技术来选择要变异的字节：比如我们可以通过污点分析技术来判断哪些字节影响了某个 branch 的控制变量，或者是通过符号执行来求解出"为到达某个状态所需要的 fixed 字节"。当然，最近几年基于机器学习的方法也不断涌现，成为了一个新的小方向。

HOW TO MUTATE. 最朴素的思想是随机替换。当然我们也可以用常见的边界案例(edge cases)来替换这些要 mutate 的字节，比如 -1, MAX_INT 这种。此外，对现有输入做一些算术运算也是可以的。还有一种方法是把所有 testcases 按照所需格式打碎成片(fragments)，然后把这些碎片随机拼凑起来，这种方法大概率能满足程序对格式的 validation，code coverage 相对较高。

[1-3-2-2] Generation-based Fuzzer

我对 generation-based fuzzer 不甚了解，因此就不在这里讲述了。目前我遇到的 fuzzer 还都是基于变异的，基于生成的 fuzzer 可能比较有针对性吧。

[1-3-3] 赋能

前文 EA 算法逻辑有提到，如果一个 testcase 有较高的 fitness，那就说明它有更高的变异价值，所以我们就可以让这个 testcase/seed 活得更久一些，也就是给它更多的 energy。

举例来讲，我们可以为每个 testcase 维护一个 energy 变量，fuzzer 每执行一秒它就减一，或者每执行一条指令它就减一；而当这个 testcase 触发了 bugs，或者是有较高的 coverage，我们就可以适当的增加 energy，从而保证它能在 fuzzer 中活得更久。如果在某一次执行当中这个 testcase 耗尽了 energy，负责管理 testcase 的 population 就可以删除这个 testcase 的相关信息了。

[1-4] Fuzzer 精简架构

至此，我们已经了解了如何构建 seed pool，以及如何通过遗传算法在一次次执行中选出最优的 testcases，接下来我们可以宏观地了解一个 fuzzer 的架构是怎样的：不同人有不同的理解，我认为 fuzzer 可以分为三部分：generator, executor 和 detector.大体流程如下：

seed pool -(seeds)-> Generator -(testcase)-> Executor -(states)-> Detector -(fitness)-> Generator

Generator 负责 testcase 的生成。可以理解为 EA 的 fuzz 实现。包含如何初始化 seed pool，如何根据 fitness 反馈进行下一步的 mutation, crossover 和 selection。

Executor 负责反复执行 testcase 并记录执行过程中的状态(比如 coverage or consumption)。

Detector 主要负责监控 executor 的状态，并判断某一状态是否异常，进而找到 bugs，并及时反馈 fitness。举个最简单的例子，对于那些能引发 crashes 的漏洞，detector 只需要监控 OS 是否抛出 exception，如果抛出异常那就说明当前的 testcase 是能触发 bugs 的，此时 detector 就会反馈给 user 这样的 testcase 能触发 这种 bugs。同时，detector 还会意识到这个 testcase 和 seed 是好的，因此会让 generator 给这个 testcase/seed 赋予更高的 energy。

[1-5] 优化

现在，我们已经了解了 fuzzer 的基本架构，接下来看看 fuzzer 当前面临着什么样的困难和挑战：

首先，fuzzer 的资源消耗过多。由于每个 testcase 都需要执行程序，程序执行一次所需要的时间越长，fuzzer 所需的时间等资源就越多。

接下来我将根据 fuzzer 的架构，从前向后开始讲述如何优化：

[1-5-1] 最小化 seed pool

由于在初始阶段，每个 seed 都会被分配近似的 energy，如果 seed pool 因为冗余而过大肯定会导致大量不必要的资源开销。因此，如何在保证检测效果不变的情况下尽可能地缩小 seed pool，是非常经典的问题。而这一问题被研究者们用数学建模出来，提出了 MSCP 问题。相关算法的细节我仍未了解，此处不具体展开。

[1-5-2] Predict Energy

给每个 seed 赋予的初始 energy 应该是多少？一个 testcase 的 fitness 对应的 energy 应该是多少？这样的问题可以通过 Markov Chain, WCCP 和 ILP 问题来建模解决。

[1-5-3] SnapShot

每次从 0 开始启动程序肯定会带来大量不必要的开销。如果我们可以从程序的某一状态开始，布置好程序所需的环境，即可大量减少程序启动带来的开销。

[1-5-4] Triage

minimize payload / deduplicate / exploitable / understandability

[1-6] 应用场景

Black-Box

Grey-Box

White-Box

[2] AFL plus plus 使用

OS: Windows11 24H2 - WSL2 ubuntu2204 CPU: 12th Gen Intel(R) Core(TM) i5-12500H 2.50 GHz

docker 和 本地编译都可以见github readme，用 docker 就能安装

分给 WSL 的 8MB 大概编译了 1h 左右

[2-1] 有源码 demo 运行

参考官方 tutorial 、focus7的博客 、跳跳糖的博客 、ba1100n的博客

[2-1-1] 获取目标源文件并编译

我们可以编写一个有问题的程序 simple_crash.cpp

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
// simple_crash.cpp
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

int main() {
   string str;
   cout << "enter input string: ";
   getline(cin, str);
   cout << str << endl << str [0] << endl;

    if(str[0] == 0 || str[str.length() - 1] == 0) {
        abort();
    }
    else {
        int count = 0;
        char prev_num = 'x';
        while (count != str.length() - 1) {
            char c = str[count];
            if(c >= 48 && c <= 57) {
                if(c == prev_num + 1) {
                    abort();
                }
                prev_num = c;
            } 
            count++;
        }
    }
    return 0;
}

编写编译这个 cpp 文件的 CMakeLists.txt

1
2
project(simple_crash)
add_executable(simple_crash simple_crash.cpp)

接着编译文件

1
2
3
4
5
mkdir build
cd build
cmake ..
make
cd ..

[2-1-2] 初始化 seed pool

然后初始化 seed pool, 即 

1
2
3
4
mkdir input
cd input
for i in {0..4}; do dd if=/dev/urandom of=seed_$i bs=64 count=10; done
cd ..

然后使用afl-fuzz -i input -o output -- ./build/simple_crash启动 fuzz 即可

[2-2] 分析 crashes

可以遍历 output/default/crashes 里的文件来查看导致 crashes 的输入，通过 gdb 等调试文件可以看到在哪里出现了问题。

[0xFE] 参考文献

[1] V. J. M. Manès et al., "The Art, Science, and Engineering of Fuzzing: A Survey," in IEEE Transactions on Software Engineering, vol. 47, no. 11, pp. 2312-2331, 1 Nov. 2021, doi: 10.1109/TSE.2019.2946563.

[2] Xiaogang Zhu, Sheng Wen, Seyit Camtepe, and Yang Xiang. 2022. Fuzzing: A Survey for Roadmap. ACM Comput. Surv. 54, 11s, Article 230 (January 2022), 36 pages. https://doi.org/10.1145/3512345

[3] Li, J., Zhao, B. & Zhang, C. Fuzzing: a survey. Cybersecur 1, 6 (2018). https://doi.org/10.1186/s42400-018-0002-y