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： lcamtuf）写的模糊测试工具：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的次数、相同路径的数量，给低频路径更高的优先级。策略有两个标准：
- s(i)小的优先级高：s(i)表示种子t_i之前从队列 Τ 中选到的次数
- 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博客