标签（空格分隔）： Paper
CCS-2017
导向型灰盒模糊测试还可以用于补丁测试和崩溃重现，实现并开源了与模拟退火相结合的导向型灰盒模糊测试工具 AFLGo。将其作为补丁测试工具整合进了 OSS-Fuzz 的工具链中。通过大规模的实验评估证明其效果比基于符号执行的导向型白盒模糊测试和非导向型的灰盒模糊测试工具都要好
导向型 Fuzzer 的典型应用：
- 补丁测试（补丁引入新漏洞、不完整修复）
- 崩溃重现
- 静态分析与报告验证
- 信息流检测（污点分析）
已有的导向型 Fuzzer 大多基于符号执行，定向符号执行（DSE）将可达性问题转换成迭代约束满足问题。虽然基于符号执行的白盒 Fuzzer 可简单进行导向，但定向符号执行的效果是以效率为代价的，符号执行生成一个样本的时间灰盒 Fuzzer 可以生成数量远比这多的样本
与非导向型 Fuzzer 不同，导向型 Fuzzer 将花费大量时间在搜索特定目标位置，而非浪费时间在无关的程序组件中
AFLGo 结合模拟退火算法设计特殊的启发式算法来最小化生成样本到目标的距离
评价的指标一般有两个
- 效率高（efficiency）：相同时间测试目标的频率更高
- 效果好（effectiveness）：发现更多漏洞
导向型灰盒模糊测试优于定向符号执行，AFLGo 比 KATCH 可以多覆盖 13% 的补丁，比 BugRedux 多三倍的崩溃重现
KATCH 对每个目标执行贪婪搜索，容易陷入局部最优导致搜索不完整。由于使用了重型程序分析技术，资源消耗极大且不支持每个字节码。
与非导向型灰盒 Fuzzer 的代表 AFL 相比，AFLGo 要快上数倍，因为 AFLGo 将分析转移到了编译时，这样可以最小化开销
AFL 插桩用于返回代码覆盖度信息，而 AFLGo 插桩用于得到执行样本与目标的距离信息
整体架构如下图所示：
使用 LLVM 工具链中现成的工具：插桩框架 trampoline 实现基于 LLVM 的静态分析，以此得到 Call Graph 和 Control-flow Graph，到目标节点的最短距离使用 Dijkstra 算法计算
在 Call Graph 中计算函数级目标距离，在 Control-flow Graph 中计算基本块级目标距离。使用 Python 的 networkx 包来解析图结构
最后需要对距离进行归一化计算
生成的输入样本的数量为样本的能量，该能量受能量调度表（Power Schedule）控制，此能量和模拟退火的温度不同
AFLfast 证明了在灰盒模糊测试中可以使用马尔科夫链（Markov Chain）有效地进行能量调度，这也为使用马尔科夫蒙特卡罗（MCMC）奠定了基础。值得注意的是模拟退火是一种马尔科夫蒙特卡罗方法，用于在可接受的时间内在非常大的通常是离散的搜索空间中逼近全局最优
温度 T 是模拟退火算法中用于调节更差解接受度的一个参数，它根据冷却表下降。刚开始 T=1 时，模拟退火算法有很高的几率接受更差解；最后到 T=0 时，模拟退火算法退化为传统的梯度下降算法，只接受更优解
冷却表由收敛度控制，需要注意的是能量是对一个样本的局部概念，而温度是对所有样本的全局概念。这里的能量调度表使用的是指数冷却表
能量调度表为更接近目标的样本分配更多的能量，随着时间的推移，温度会下降而能量差会增加
AFL 现有的能量调度表基于执行时间和样本大小，AFLGo 将 AFL 原有的能量调度与退火因子相结合，退火因子和自设计的能量调度表直接相关，以此将两种能量调度进行整合
如前所述，AFLGo 比 KATCH 快的部分在于导向型灰盒模糊测试的效率更高
AFLGo 使用运行时的 signal 检查来报告错误出现，而 KATCH 通过对 LLVM 的中间表示进行符号执行，通过约束求解判断错误存在
OSS-Fuzz 项目针对 47 个开源项目进行持续模糊测试，每天产生超过十万亿的输入样本，五个月的时间发现了超过一千个漏洞，其中有 264 个关键漏洞
KLEE 是最广泛使用的符号执行引擎也是大多数用 C 写成的导向型白盒扫描器的基础
符号执行和模糊测试可互补
灰盒 Fuzzing 可以保证快速探索不同的路径而不陷入“邻居”路径
重型程序分析，提前做可以降低对效率的影响，先把有关的信息都存下，每次都用得上
灰盒模糊测试在漏洞检测上厉害的原因就是效率高