标签（空格分隔）： Paper
CCS-2016
通过实验发现 AFL 大多数测试都使用少量的相同“高频”路径，那么通过策略调整对低频路径执行相同水平的测试就可以探索更多的路径 用马尔科夫链指定在模糊测试中由执行路径i的种子生成执行路径j的样本的概率，每个状态（即种子）都包含一个能量值，它指定种子生成的样本数量 如果能量值和固定分布的密度成反比，并且在每次选择种子时单调递增，会大幅加快基于覆盖度的灰盒模糊测试的效率 据此实现的 AFLFast 可以比 AFL 发现的独特 Crash 至少多一个数量级
符号执行的效果比轻量级的模糊测试要好，但现在大多数都依赖超轻量的 Fuzzer 而非程序分析。符号执行用大量时间来进行程序分析和约束求解，而模糊测试不将时间浪费在程序分析上通过高效选路来达到目标
模糊测试虽然不如符号执行精确，但可扩展性大，它不随着程序体积的变大而时间相应变长。不过符号执行可以解决模糊测试被卡住的问题
基于覆盖度的模糊测试是高度并行的，因为保留的样本代表唯一的内部状态
马尔科夫链是一个随机过程，从一个状态过渡到另一个状态，在任何时候，链只能处于一种状态，所有状态的结合称为链的状态空间 状态之间的转换概率只取决于当前状态，而不是当前状态的路径
概率矩阵指定了转换概率，每项都是非负的，并且每行的总和是1
如果概率矩阵不依赖于时间，则称马尔科夫链是时间均匀的，换句话说，每当链处于状态 i 时，跳转到状态 j 的概率是相同的。如果马尔科夫链是时间均匀的，那么向量π称为马尔科夫链的平稳分布，其满足以下条件
网页的抓取可以模拟为马尔科夫链，页面是状态，链接是转换。像 Google 这样的公司试图为互联网创建重要页面索引编制，开发了一种 PageRank 的算法，为每个页面分配一个重要性分数。正式地说，当重要页面处于高密度区时，PageRank 接近马尔科夫链的平稳分布密度
没有程序分析，灰盒比白盒更高效；有程序内部结构信息，灰盒比黑盒更有效
触发任意控制流边的最小、最快的输入样本会被 AFL 标记为 favorite，AFL 的下一轮样本选择大多忽略了 non-favorite 的样本
AFL 使用执行时间、覆盖度信息、样本创建时间来分配能量
AFL 的 Power Schedule 其实就是为选中的种子分配相同的能量，不管这些种子的执行次数。AFL 的常数分配会出现能量分配超标或者不足的情况，所以 AFLFast 实现了一个指数分配，当种子第一次模糊测试时会被分配非常少的能量，不断被选中的种子，就会成倍的提高其能量值利用其大量产生新样本，以此快速接近发现新路径所需的最小能量值
通常，每个种子大约一分钟会生成 80K 的输入样本。为最初的种子分配大量的能量可以发现更多的“邻居”路径来更多地执行低频路径。一段时间后，随着更多的种子被发现，许多种子频繁执行着高频路径，AFL 为其分配的能量明显过多
AFL 会按照种子添加顺序选择种子，一旦所有的种子都已经参与了 Fuzzing，AFL 会重新选择第一个种子。AFLFast 实现了不同的搜索策略，每轮只选择一次种子
在一轮中，AFLFast 选择那些执行低频路径的、那些更少被选择的早期种子
在能量分配相同的前提下，只看搜索策略，一轮完成时相同的种子会被选中 Fuzzing（策略不同，权值相同）
不使用程序分析而是利用能量分配权值表和搜索策略来提高路径覆盖度
能量分配和搜索策略仅影响 AFL 的效率（单位时间探测的路径数）而不影响 AFL 的有效性（期望探测的路径数），在具有完全相同漏洞的前提下只是速度更快
状态的权值由预定义的 Power Schedule 控制
使用马尔科夫链对执行路径 i 的种子生成执行路径 j 的种子的概率 Pij 进行建模，如果 Fuzzer 集中在马尔科夫链的低密度区域，那么单位时间就会运行更多不同的路径
一旦发现一个从未发现过的路径，就构造一个新的马尔科夫链
对 AFL 的修改只限于搜索策略选择的 ChooseNext 和能量分配权值表 AssignEnergy
二进制插桩沿用 AFL 的 QEMU，AFL 的二进制插桩工具 AFLDynlnst
对于路径i，s(i) 为路径对应的种子输入之前被选中的次数；f(i) 为路径被已生成的输入所执行的次数。路径 i 的能量是这两个参数的函数
每个种子输入fuzz的次数由执行时间、路径片段覆盖率和产生新输入所花的时间确定，也就是说和 s(i) 以及 f(i) 无关。如果新产生的输入经历了新的路径片段或者经历相同片段的次数比已有的输入经历的次数多，则认为该新输入是interesting的，并把该输入放入输入队列
对于每个种子输入fuzz的次数，在AFL的计算结果上乘以一个以指数增长的系数，并设定最大值，超过则截断：一种称为截断指数（COE，系数为2s(i)）；一种称为FAST（系数为2s(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输入时，采用同样的流程。