Reading Papers - Grey-Box Fuzzing
# State-Aware Grey-Box Fuzzing
# FSE'17 - Steelix
Steelix 在收集代码覆盖信息的同时收集比较进度信息(例如 magicbytes 比较中已经正确匹配了多少个字节),旨在生成能通过 magicbytes comparison 的测试输入。
Taxonomy : mutation-based / coverage-guided / grey-box fuzzing
Tag : state-aware fuzzing / taint-inference
Steelix 利用静态分析过滤掉不感兴趣的比较指令并收集感兴趣的比较指令的信息,随后据此在 binary-level 进行插桩,以在运行时刻生成比较进度信息。
Steelix 的静态分析过程会先对二进制代码进行反汇编,然后基于一系列预设规则来过滤不感兴趣的比较指令,例如:
不考虑单字节比较,因为它们可以直接用 AFL 默认的单字节突变操作匹配到。
不考虑对函数返回值的比较,因为它们可能会使比较操作数和输入之间的联系变得模糊,例如
ret = hash(input_str)
。(但是这也使其不能处理 checksum ?)
Steelix 的插桩会在运行时刻引入较大的性能开销。
# S&P'20 - Ijon
Ijon 是一种人类分析师通过注释来指导 fuzzer 的机制,仅用很少的(通常是一行)注释就能解决 coverage-guided fuzzer 难以解决的挑战。
Taxonomy : mutation-based / coverage-guided / grey-box fuzzing
Tag : state-aware fuzzing / manual annotation
coverage-guided fuzzer 难以探索具有复杂状态机性质的程序。程序状态数据的变化(即状态转移)是由某些代码触发的,而基于覆盖率的方法只能激励探索所有“单独的”状态转移,但无法激励探索这些状态转移的组合,即无法探索特定的代码执行顺序。
Ijon 专注于程序状态空间中无法用代码覆盖率描述的部分。
KEY Idea :人类可以交互地协助和引导 fuzzer 克服许多当前依靠代码覆盖率无法克服的挑战。
人类通常更擅长制定 high-level 的战略计划,而计算机则确保有效地执行战术,因此人类的加入能确保不忽视任何重要的方面。这种方法被称为 human-in-the-loop ,广泛应用于包括程序验证和机器学习在内的各种领域。
Computers are incredibly fast, accurate and stupid; humans are incredibly slow, inaccurate and brilliant; together they are powerful beyond imagination.
行业中许多测试人员已经在 fuzzing 过程中使用 closed feedback loop 的策略:首先运行 fuzzer 一段时间,然后人工分析代码覆盖情况,并据此调整 (tweat and adapt) fuzzing 过程以期能提高覆盖率。
所有“容易”的 BUG 很快就会在 fuzzing 过程中被发现,而那些更“有趣”的 BUG 则是使用当前工具在当前的配置下无法找到的,因此需要进行一些人工调整。
很难自动推断出程序中哪些事物(变量数据、代码)是有趣的(即会影响到状态空间的探索),而人类则通常对此有一定的认知。
实践中无法依靠覆盖率探索的程序 :
感兴趣的状态与代码覆盖无关,而是与变量数据强相关:
while(true) {
ox = x; oy = y;
switch (input[i]) {
case 'w': y --; break;
case 's': y ++; break;
case 'a': x --; break;
case 'd': x ++; break;
}
if (maze[y][x] == '#') { Bug(); }
// If target is blocked, do not advance
if (maze[y][x] != ' ') { x = ox; y = oy; }
}
程序状态涉及的变量中仅有一小部分是有趣的:
- 例如横版通关游戏:人类可以指导 fuzzer 尽可能增加 x 坐标,促使其丢弃较差的中间结果。
被测程序过于复杂,人类难以识别出状态中哪些部分是有趣的,或是可能有趣的子集仍然过大,但是人类可以识别出哪些代码预期会高度影响程序状态。这种情况一般出现在使用高度结构化数据的程序中,此时人类可以修改原程序以建立抽象(将巨大的状态集合抽象为较小的状态集合,并以新创建的变量作为状态转移的标准),例如增加变量以标识成功处理的消息类型的日志,并将其暴露给 fuzzer 的反馈函数:
msg = parse_msg();
switch (msg.type) {
case Hello: eval_hello(msg); break;
case Login: eval_login(msg); break;
case Msg_A: eval_msg_a(msg); break;
}
有一些极其复杂的情况,是依靠符号执行也不能轻易解决的问题,需要找到路径和哈希值的非常具体的组合,而人类可以认识到这是一种一对多的字符串比较,并将复杂的约束拆解为 fuzzer 可解的一系列的简单字符串比较:
- 在整个 binutils 代码库中,出现了超过 500 次类似的情况,并关联了各种不同的字符串。
//shortened version of a hashmap lookup from binutils
entry * bfd_get_section_by_name(table * tbl, char * str) {
entry * lp;
uint32_t hash = bfd_hash_hash(str);
uint32_t i = hash % tbl->size;
//Every hash bucket contains a linked list of strings
for (lp = tbl->table[i]; lp != NULL; lp = lp->next) {
if (lp->hash == hash && strcmp(lp->string, str) == 0)
return lp;
}
return NULL;
}
// used somewhere else
section = bfd_get_section_by_name(abfd, ".bootloader");
if (section != NULL) { ... }
Ijon 注释反馈机制 :
Ijon 基于交互式的 fuzzing 会话:人类不时地检查代码覆盖率,识别 fuzzer 似乎难以覆盖的分支,分析原因,加入注释以期能越过障碍,然后继续执行。成功越过指定障碍的输入会被记录下来。
Ijon 设计了一组能够影响 fuzzer 反馈函数的注释,允许人类用于为 fuzzer 提供 high-level 的指导,包括四种通用原语。
允许人类分析师选择哪些代码区域与当前的探索目标相关:
IJON_DISABLE();
// ...
if (x < 0) {
IJON_ENABLE();
// ...
}
允许直接访问 AFL bitmap 以存储和修改附加值,以将状态值暴露给反馈函数:
// each time accessing x will increase the corresponding AFL bitmap entry.
// this actually tells AFL to think x as part of the coverage.
IJON_INC(x);
while (true) {
ox = x; oy = y;
IJON_SET(hash_int(x, y));
switch (input[i]) {
case 'w': y --; break;
// ...
}
}
msg = parse_msg();
err = handle_msg(msg);
// ...
state_log = (state_log << 8) + command.index;
IJON_SET(state_log);
允许改变覆盖率计算的方法,这会导致相同的 edge coverage 计算出不同的 AFL bitmap coverage ,进而提供了更细粒度的状态探索。
IJON_STATE(has_hello + has_login);
msg = parse_msg();
// ...
允许添加爬山优化(事实上将 fuzzer 变成了一个通用的黑盒爬山优化器),这样如果希望针对特定的目标进行优化,或是可能的状态空间太大而无法彻底探索,人类分析师可以为 fuzzer 提供一个努力的目标:
// x and y are optimized independently (similar to AFL bitmap)
IJON_MAX(player_y, player_x);
# Taint-Based Grey-Box Fuzzing
# NDSS'17 - VUzzer
VUzzer 使用轻量的程序分析技术替代低效的符号执行技术,以期能更好地解决符号执行指导的 fuzzer 未能解决的问题。
Taxonomy : mutation-based / coverage-guided / grey-box fuzzing
Tag : taint-based fuzzing
VUzzer 使用轻量的静态和动态分析获取被测应用程序的控制流和数据流特征:
数据流特征显示了应用程序的输入数据和数据计算指令之间的关联。VUzzer 利用污点分析技术来获取此类信息,包括条件分支和输入的关联以及 magic bytes 。
控制流特征允许 VUzzer 推断执行路径的重要性,并计算不同程序路径的优先级。具体地,VUzzer 将每个函数的 CFG 建模为 马尔可夫模型 (Markov model) ,估算到达函数中每个基本块 的概率 ,然后设定其权重为 。特别地,被识别为 error handling code 的基本块将被赋予负数权重。
VUzzer 的初始化流程如下:
首先在 binary-level 对被测程序进行过程内静态分析,获取
cmp
指令的立即值(这些立即值可能意味着期望输入中的某些字节具有对应的值),并计算每个基本块的权重。使用初始的 input seed 执行被测程序,通过污点分析获取数据流特征,
VUzzer 的主循环流程如下:
使用上一轮生成的输入变异生成新的输入,然后执行被测程序,记录所执行基本块的 trace ,并利用污点分析推断新触及的基本块的结构信息。
将该输入的优先级计算为已执行基本块的权重的加权和,以用于下一轮的变异。
VUzzer 识别 error handling code 的方法:
准备一组预计不会触发任何 error handling 的 valid input seed ,执行并这些输入,并收集它们所执行到的基本块,记收集到的集合为 。
创建一组完全随机的输入,在彻底的随机下,它们很可能在执行过程中触发 error handling 。收集它们所执行到的、但不在 中的基本块,假定它们是 error handling code 。
在 fuzzing 的后续迭代过程中进行 增量分析 (incremental analysis) :记迭代过程中生成的所有输入的集合为 ,记 中输入所执行到的所有基本块的集合为 。对于 ,如果 与 中 以上的输入有关联且 ,则认为 是 error handling code 。
应用程序中的 error handling code 是有限的,因而可以随着迭代轮数的增加而逐渐降低进行增量分析的频率。
VUzzer 只需要被测程序的二进制可执行文件,但假设初始的合法输入是另外可获取或可构造的。
disadvantages of concolic-execution-guided fuzzing :
利用 concolic execution 指导 fuzzing 能避免在被测程序的表面 get stuck ,然而受符号执行的 scalability 限制,仍然很难探索到更深层的路径。此外,尽管符号执行可以均匀地覆盖到每一条分支路径,但它无法向 AFL 传达有关程序路径优先级的关键信息,即无法帮助 AFL 判断哪条路径更有价值。具体地讲:
其一,在借助符号执行通过 magic byte check 之后,AFL 的随机变异策略可能会再次尝试修改输入中的对应字节,浪费算力:
if (buf[5] == 0xd8 && buf[4] == 0xff) {
// some useful code
} else {
exit(-1);
}
其二,在借助符号执行进入难以探索的 nested if 后,由于 else 之后仍然有大量未探索的路径,AFL 简单的 coverage-guided 策略会倾向于继续探索,从而不会优先考虑符号执行针对 nested if 所作的努力,阻碍我们探索那些可能更有价值的区域:
if (...) {
if (...) {
...
}
} else {
...
}
其三,例如对于 error handling code 所处的分支,尽管符号执行能让 AFL 以较高的概率进入另一分支,AFL 仍然会在 error handling code 上浪费算力进一步探索不同的输入,因为这些输入确实覆盖到了新的代码。然而,如果我们考虑探索更有意义和更有趣的路径,重用这些输入不会产生任何好处,并且会阻碍对被测应用程序的进一步探索。
下列代码段具有 magic bytes / markers / error handling / nested conditions ,使 AFL 难以探索:
unsigned char buf[1000];
read(fd, buf, size);
if (buf[1] == 0xEF && buf[0] == 0xED) { // notice the order of cmps (?)
printf("1st magic bytes matched");
} else {
printf("invalid file");
return error_handler(1);
}
if (buf[100] == '%' && buf[101] == '@') {
printf("2nd magic bytes matched");
if (strncmp(&buf[105], "MAZE", 4) == 0) { // nested IF
bug();
} else {
// ...
return 0;
}
} else {
printf("invalid file");
return error_handler(2);
}
// ...
return 0;
而结合符号执行的技术也无法解决全部困难:这能使 AFL 快速通过第一个分支,但仍然会卡在第二个分支(?)。
# ASE'18 - FairFuzz
FairFuzz 特殊处理那些极少被已生成的输入触及到的分支,使后续生成的输入能沿此类分支深入探索,旨在改进 AFL 的代码覆盖率。
ASE'18 - FairFuzz - A Targeted Mutation Strategy for Increasing Greybox Fuzz Testing Coverage
Taxonomy : mutation-based / coverage-guided / grey-box fuzzing
Tag : taint-based fuzzing / taint-inference
KEY Idea :对于那些很少被先前生成的输入触及的条件分支,称为 rare branches ,其后的代码更可能未被充分探索。
KEY Idea :对于那些少量的、已经触及 rare branches 的输入来说,输入中的某一部分对于触及该分支而言是关键的。
一方面,FairFuzz 在 fuzzing 过程中统计每个分支被触及的次数并识别出 rare branches ,并增加触及这些 rare branches 的概率。具体的统计和判断方法略。
另一方面,FairFuzz 在变异前先进行变异实验,即预先尝试对输入中的不同字节进行不同的变异操作,执行并观察是否导致路径偏离目标,并将对应的变异方式标记为不可用。本质上,这是以不同于动态污点分析的、推断的方式来获取污点信息。
FairFuzz 不像其他 fuzzer 那样需要对被测程序进行额外的插桩,而只需要 AFL 提供的常规插桩。
FairFuzz 的方法与其它帮助 AFL 通过 magic bytes check 的方法或 directed fuzzing 的方法是正交的,可以结合运用。
# NDSS'19 - RedQueen
RedQueen 提供了一种轻量的近似方法以取代污点分析或符号执行,以期能更易于扩展到复杂的大型程序上。
NDSS'19 - Redqueen - Fuzzing with Input-to-State Correspondence
Taxonomy : mutation-based / coverage-guided / grey-box fuzzing
Tag : taint-based fuzzing / taint-inference
当 RedQueen 开始测试一个新输入时,会先运行一次程序以提取所有比较指令的信息(包括一些函数调用指令,因为可能涉及字符串比较及其它类似功能)。由于无法区分不同的比较操作(例如小于和等于),RedQueen 直接对比较值进行变异,例如 +1 和 -1 等。
RedQueen 使用变异模式 <pattern -> repl>
来识别输入中将被 repl
替换的部分,这是 RedQueen 能绕开污点分析以识别污点信息的关键。
在实践中,这样的模式可能有大量可应用的候选位置,例如输入 ZZZZZ...ZZZ
和模式 <ZZZZZ -> MAGIC>
。为此,RedQueen 设计了一种随机算法来增加输入中随机字节的数量,这能将候选数减少几个数量级。
对于 checksum ,过往技术都是识别并移除程序中的 checksum 检查,然后对于找到 BUG 的输入,再用符号执行技术修复 checksum 值。RedQueen 沿用同样的想法,但是尝试利用代码补丁的方式来修复 checksum 值:细节略。
# Empirical-Based Grey-Box Fuzzing
# ICSE'22 - HavocMAB
HavocMAB 是对一组 state-of-the-art fuzzer 中实现的 Havoc 策略进行实验后,设计的一种对 Havoc 策略的改进方案。
Taxonomy : mutation-based / coverage-guided / grey-box fuzzing / fuzzing effect measurement
Tag : empirical study
Havoc 是实现于 AFL 的 fuzzing loop 内的一种 mutation 策略,随机 mutator stack 的大小,并随机选取预设的 15 种 unit mutator 和 chunk mutator 之一填入 mutator stack 的每个位置,然后依次执行。通常 fuzzer 会以 sequntial 的形式交替执行 Havoc 策略和主策略,或是以 parallel 的形式同时执行。
实验表明,以 edge coverage 为度量的情况下,Havoc 的作用甚至要超过许多前沿 fuzzer 采用的主策略,并且 pure Havoc 本身就是一个很强大的 fuzzer 。结合了 concolic execution 或 neural network 的 fuzzer 才能与 Havoc 较好地互补。
HavocMAB :在不同程序中 Havoc 的各个参数的最佳取值不同,HavocMAB 利用了这一点,在 fuzzing 过程中为产生新覆盖的 stack size 和 mutator chosen 分配更高的优先级,该策略在 HavocMAB 中具体实现为多臂老虎机算法的形式。
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01