Coverage-based greybox fuzzing as markov chain

00 — Begin

和老五聊的比较久,最终还是答应他努力把自己平时的一些总结发在九零
不是不愿意发,而是感觉自己太菜,但是九零刚使用新论坛,内容欠缺,我也只能凑个数

本篇论文名为《Coverage-based greybox fuzzing as markov chain》,有三位作者:

Marcel Böhme
Computer Science, National University of Singapore, Singapore, Singapore Singapore 117417 (e-mail: [email protected])

Van-Thuan Pham
Computer Science, National University of Singapore, Singapore, Singapore Singapore (e-mail: [email protected])

Abhik Roychoudhury
Computer Science, National University of Singapore, Singapore, Singapore Singapore 117417 (e-mail: [email protected])

论文主要讨论的是系统安全测试中的Fuzzing技术
改进了著名前谷歌安全研究员 Michał Zalewski(ID: lcamt​​uf)写的模糊测试工具:AFL

01 – Why

目前绝大多数的Bug是由fuzzing Test发现的,Symbolic Execution仅占了小部分,因为fuzzing的速度更快,不需要进行程序内部逻辑分析,不需要进行相关的条件约束,而且对于受路径爆炸的影响来说更小。目前Fuzzing的挑战是,在一次模糊测试中,如果对一张有效的图片来进行fuzzing,那么执行fuzz后的图片,有90%的可能性执行拒绝无效图片文件的路径π,然后再fuzzing一张无效的图片文件,那么有99.999%的概率执行相同路径π。这样的路径π可以称作高频路径。简单来说,即许多fuzz会执行高频路径,导致大多数的模糊操作的路径是相同的,因此AFL-FAST提出了几种使模糊测试系统偏向低频路径的策略,以便在相同的模糊测试量下探索更多的路径。

02 - What

将AFL进行了改进,改进后的测试工具称为AFLFast

GitHub地址:

03 – How

AFL采用的方法就是找一些testcase,去触发漏洞或者提高代码的覆盖率,这里的部分的testcase也可以叫做seed(种子),这些种子通过循环不断去挑选好的种子,然后把好的种子留下来去进行下一轮测试,把种子编译好后,再进行测试,留下更好的种子,直到达到理想效果。

注: testcase不同于seed,优秀的对发现新coverage有利的testcase才能成为seed;大部分testcase都是被抛弃的

AFLFast在这里做的就是优化挑选种子的方法。通过查阅文献了解知道,AFL会经过每轮迭代挑选好的种子,然后把好的种子选出来一部分再进行变异杂交操作。

但需要注意,这里“好种子”不一定只有一个,可能几十,可能上百,如果第一轮迭代选第一个,第N轮迭代选择第N个,差别可能很大,所以种子的顺序非常关键,AFLFast做的工作是评估了这N个种子中,哪个种子被选了多少次,因为有的种子被选择的次数很大(高频路径),有的可能就一次(低频路径),AFLFast这时候会优先选择被选次数较小的种子,因为被选择次数多的种子被充分测试了,剩余价值就没有这个被选次数较少的价值高。

总的来说,由于AFL去执行高频路径,花费了大量时间,因此AFLFast改进了AFL的种子输入的选择策略和每个种子fuzz的次数的计算方法,从技术上讲,AFLFast修改了种子性能得分(calculate_score)的计算,该种子被标记为favorite(update_bitmap_score),并且接下来从循环队列(main)中选择了哪个种子。

AFLFast的具体做法如下所述。

搜索策略

即确定下一个所要选择的种子,这个决策依赖于种子之前被fuzz的次数、相同路径的数量,给低频路径更高的优先级。策略有两个标准:

  1. s(i)小的优先级高:s(i)表示种子t_i之前从队列 Τ 中选到的次数
  2. f(i)小的优先级高:f(i)表示执行路径 I 的生成输入的能量

能量分配策略

AFLFast将CGF视为马尔科夫链,假设当前种子输入执行的路径是 i ,fuzz之后的路径为 j 的概率为 P_{ij} 那么称路径从 i 到路径 j 所要生成的测试用例个数为该种子输入的能量( E_{ij}=1/P_{ij} )。

这里的 P_{ij} 通常是未知的,所以CGF对能量的分配也通常是经验性的,AFL采用的是一个常数,AFLFast则采用了几种新的分配策略:
首先AFLFast为Power Schedule定义了一个函数:

p(i)=\mathbb{E}[X_{ij}]

这里的 p(i) 是关于 s(i)f(i) 的函数,其中 p(i) 是指种子 t_i 之前从队列 Τ 中选到的次数, f(i) 表示执行路径 i 的生成输入的能量。 f(i)/n 是CGF产生输入的概率的最大似然估计量。于是就有了以下几种power shcedules

Exploitation-based constant schedule (EXPLOIT) : p(i)=α(i) ,其中 α(i) 是算法中assignEnergy的实现,AFL根据所执行的时间、块转换覆盖率以及 t_i 的构造时间来计算 α(i)

Exploration-based constant schedule (EXPLORE): p(i)= α(i)/β ,其中 α(i)/β 保持fuzz对t_i质量的原始判断 α(i)β>1 是一个常数

Cut-Off Exponential (COE): \begin{cases}0 , f(i)>μ\\min(\frac{α(i)}{β}·2^{s(i)},M),其他情况\\\end{cases} ,其中 α(i) 保持模糊的原始判断, β>1 是一个常数, s(i) 值较低,μ是执行已发现路径的模糊平均数,且 \frac{∑_{iϵS^+}f(i) )}{| S^{+}|}S^+ 是发现的路径集合,直观的说, f(i)>μ 为高频路径,即使从模糊其他种子接收大量模糊,也被视为低优先级,直到它们再次低于平均值才模糊。常数M提供了每次模糊迭代生成的输入数量的上限。

Exponential schedule (FAST) : min(\frac{α(i)}{β}·\frac{2^{s(i)}}{f(i)},M) ,当 f(i)>μ 时,Power Schedule不会使 t_i 模糊,而是使 t_i 和执行路径 i 的模糊 f(i) 的量成反比,分母中的 f(i) 利用过去没有收到大量模糊的 t_i ,因此更可能位于低频区域,这样, s(i) 的指数增长允许越来越多的能量用于低频路径。(个人理解就是输入队列中选择 t_i 的输入次数越多,执行路径 i 就越少,所以放在指数上, t_i 选的越多,就赋予低频路径越多的能量值,让其多变异。)

Linear schedule (LINEAR): min(\frac{α(i)}{β}·\frac{{s(i)}}{f(i)},M)

Quadratic schedule (QUAD): min(\frac{α(i)}{β}·\frac{{s(i)^2}}{f(i)},M)

对于每个种子输入fuzz的次数,在AFL原有计算结果的基础上,再乘以一个以指数增长的系数,然后设定一个最大值,如果超过了这个最大值,进行截断:

  • 指数截断(COE)
  • 快速截断(FAST)
  • 线性规划(LINE)
  • 二次规划(QUAD)

通过上述的策略,AFLFast智能地控制种子产生的模糊量,从而使搜索转向低频运行的路径,转向可能隐藏漏洞的路径。

04 – Code(具体代码如何改进的)

通过比对AFL(V2.32b)和AFLFast的源文件,发现以下文件进行了改动:

主目录下:

  • afl-analyze.c (3处不同)
  • afl-as.c (3处不同)
  • afl-cmin (4处不同)
  • afl-fuzz.c (104处不同)
  • afl-gcc.c (3处不同)
  • afl-plot (1处不同)
  • afl-showamp.c (14处不同)
  • afl-tmin.c (17处不同)
  • afl-whatsup (1处不同)
  • config.h (6处不同)
  • Makefile (2处不同)
  • types.h (1处不同)

dictionaries目录下:

  • json.dict (新增)

experimental/crash_triage目录下:

  • triage_crashes.sh (2处不同)

experimental/distributed_fuzzing目录下:

  • sync_script.sh (1处不同)

libdislocator目录下:

  • libdislocator.so.c (6处不同)

libtokencap目录下:

  • libtokencap.so.c (2处不同)

llvm_mode目录下:

  • afl-clang-fast.c (6处不同)
  • afl-llvm-pass.so.cc (5处不同)
  • afl-llvm-rt.o.c (9处不同)

经过进一步对比,发现主要是afl-fuzz.c进行了较大的改动,其他文件根据afl-fuzz.c的改动而略微改动。在afl-fuzz.c文件中,改动如图1:


图1

从图一可以看出,AFLFast建立了一个新的能量分配模块,其中FAST代表文章中的快速截断、COE代表指数截断、EXPLORE代表Exploration-based constant schedule、LIN代表线性规划、QUAD代表二次规划、EXPLOIT代表Exploitation-based constant schedule。

此外,还给模糊迭代次数专门创建变量为fuzz_level,不发生溢出的模糊次数创建变量为n_fuzz,如图2。


图2

在图3中,可以看到代码主要改变了下一个种子输入的策略,给了两种策略:一种优先考虑 s(i)最小的执行路径 i 的输入,一种是优先考虑 f(i) 最小的执行路径 i 的输入。


图3

在为每个路径片段选择“favorite”输入时,先用s(i)策略,如果不止一个,再用f(i)策略;如果还有,则使用AFL的策略。

在为当前的输入选择下一个“favorite”输入时,采用同样的流程

在图4中,可以看到AFLFast新增了更新高频路径的判断。


图4

图5也是一处比较大的变动,但是读了注释后也不是很明白是用来干什么用的(论文对应的地方没找到)。


图5

如图6、7、8,这里是文件最大的改动了,是能量分配的具体实现:


图6


图7


图8

05 – Result

  • 在GNU binutils中发现了9个CVE
  • AFLFAST暴露6个CVE的速度是AFL的14倍
  • 开源了AFLFast

06 - Reference

GitHub - mirrorer/afl: american fuzzy lop (copy of the source code for easy access)
https://www.jianshu.com/p/4bd82c28e267
https://bbs.pediy.com/thread-249912.htm
Coverage-based Greybox Fuzzing as Markov Chain · cgnail's weblog
Coverage-based Greybox Fuzzing as Markov Chain-CSDN博客

Coverage-based greybox fuzzing as markov chain.pdf (1.4 MB)
原论文下载

源码插桩来说AFL确实是目前工程中会重点考虑的选项,但是在很多实际情况下的工程中测试人员是只有二进制的,AFL原生提供了qemu的方式去fuzz二进制,但是效率太低,不知道楼主有没有往二进制插桩的方向去考虑改进一下?

对的,目前研究的方向主要还是Coverage,CollAFL研究的是消除碰撞问题(bitmap),AFLGO也是种子策略选择,针对二进制插桩方向的研究我还没开始看,目前刚刚起步,只是去了解以前研究了哪些内容,感谢师傅指出的方向,我记录到笔记上去了