Coverage-based Greybox Fuzzing as Markov Chain
30 Aug 2016 | categories notes为什么要做
据AFL的作者、著名黑客Michal Zalewski（lcamtuf）所说，目前大部分的bug都是由模糊测试发现的，而不是symbolic execution等基于程序分析的技术发现的。原因就在于fuzzing速度更快（不需要分析程序，不需要解约束），更具扩展性（路径爆炸的影响很小）。
本文所说的coverage-based greybox fuzzing（CGF）介于whitebox（需要了解程序内部结构，通过程序分析或符号执行得到）和blackbox之间，它通过轻量级的插桩获得输入和程序路径的对应关系，如果发现有新的路径则保留输入作为下次fuzzing的种子，否则扔掉输入。
作者发现CGF的问题在于：大部分的输入执行的都是少数的几条路径（称为high frequency path，高频路径），如大部分生成的输入执行的都是输入合法性检查失败的路径。
做了什么
改进AFL（最流行的CGF）的种子输入的选择策略，以及每个种子fuzz的次数的计算方法，改进后的模糊测试器称为AFLFast。
- 为此，将CGF视为马尔科夫链（Markov chain），假设当前种子输入执行的路径是 i，fuzz之后的路径为 j 的概率为 $p_{ij}$。那么称路径从 i 到路径 j 所要生成的测试用例个数为该种子输入的能量（$E_{ij}=1/p_{ij}$）。而AFL计算出的fuzz次数远高于$E_{ij}$。
- 新的能量分配策略。由于$p_{ij}$的值通常是未知的，所以CGF对能量的分配也通常是经验性的，比如AFL采用的是一个常数（即不论路径频率如何，其种子输入都执行同样的次数）。文章提出了几种分配策略，使得低频路径可以获得更高的能量，并测试了效果。
- 新的种子选择策略。AFL按种子加入队列的顺序选择下一个将要执行的种子输入，文章实现了多种选择策略，使得低频路径对应的种子输入更优先被选择。
- 开源了工具，并交给Darpa CGC的一只参赛队伍Codejitsu使用，该队伍获得了决赛的第二名。
怎么做到的
两个概念：对于路径i，s(i) 为路径对应的种子输入之前被选中的次数；f(i) 为路径被已生成的输入所执行的次数。路径 i 的能量是这两个概念的函数。AFL维护了一个从输入到输入所执行的路径片段的映射，用 cksum 标识。s(i) 以及 f(i) 可以修改AFL在程序执行时动态统计，此外还维护了一个 cksum(i) 到 f(i) 的映射。
AFL的策略
AFL在大部分情况下，每次选择下一个种子输入时都只在标为favorite的输入里挑选。所谓favorite，是指该输入对应执行路径上存在这样的片段，其他所有能执行到它的种子输入都没有该输入执行速度快或输入体积最小。
每个种子输入fuzz的次数由执行时间、路径片段覆盖率和产生新输入所花的时间确定，也就是说和 s(i) 以及 f(i) 无关。如果新产生的输入经历了新的路径片段或者经历相同片段的次数比已有的输入经历的次数多，则认为该新输入是interesting的，并把该输入放入输入队列。
新的策略
对于每个种子输入fuzz的次数，在AFL的计算结果上乘以一个以指数增长的系数，并设定最大值，超过则截断：一种称为截断指数（COE，系数为$2^{s(i)}$）；一种称为FAST（系数为$2^{s(i)}/f(i)$）；一种称为线性策略（系数为$s(i)/f(i)$）；一种为二次策略（QUAD，系数为$s(i)^2/f(i)$）。
对于挑选下一个种子输入的策略，提出两种策略：一种优先考虑 s(i) 最小的执行路径 i 的输入（路径 i 是当前输入执行的路径？）；一种是优先考虑 f(i) 最小的执行路径 i 的输入。在为每个路径片段选择favorite输入时，先用策略1，如果不止一个，再应用策略2；如果还不止一个，则使用AFL的策略。在为当前输入选择下一个favorite输入时，采用同样的流程。
效果如何
用40核并行做实验，每个实验运行6到24小时，测试对象是binutils，拿到了9个CVE。其中，c++filt、nm和onjdump发现了比AFL多得多的crash，时间也只有AFL的1/5，但有几个程序两个工具都没有发现crash。所采用的两项策略，在5个小时的运行之后，显著地比AFL现有策略要好，发现crash的数量远超AFL。
相关工作
一种优化fuzzing的办法是更明智地从一堆输入中挑选种子输入，而AFL并不对初始种子输入做假设，它允许初始输入为空文件。另一种是利用程序分析技术找出输入bit之间的依赖，如图像文件中常用4个字节储存图像尺寸，这四个字节最好一起修改。
Whitebox fuzzing可以分为基于符号执行的、基于污点分析的，以及基于模型的三类。符号执行可以用于计算将执行路径直接导向“危险点”的输入，污点分析用于确定输入的哪些部分需要符号化，基于模型的方法使用了输入模型，用于在部分输入固定的情况下综合（synthesize）出完整的输入。
Whitebox和blackbox/greybox的结合有两种方式：一种叫Hybrid fuzzing，先用符号执行得到能执行到“前沿点”的输入，然后将输入丢给fuzzing进行测试。另一种，如Driller，则先用AFL做测试，当进行不下去时调用符号执行扩大覆盖率。
然后呢
没了。