前置知识#
Fuzzing 的方法是通过大量生成 input，来找出被测程序的错误的方法。
Fuzzing 的关键点之一在于 input 生成方法，其二在于 input 的排序方法，其三在于软件内部信息的获取和应用。
如果 input 完全是自己构建的，那么这种方法称之为 generational fuzzing
如果 input 是通过原始种子略微修改后得到的，那么这种 fuzzing 为 Mutational fuzzing。
如果 Mutator 可以经过一定的程序信息的引导，那么这叫做 GrayBox Fuzzing，比如覆盖率引导的模糊测试
如果 Seed 经过 Power Schedule 的精力分配，随后 Mutator 根据 Seed 的精力大小排序，那么这种方法称之为 Boosted GrayBox Fuzzing
grey-box fuzzing 是什么#
白盒是很大程度上利用了源码进行约束求解、程序分析等操作
黑盒是一点源码的信息都没有获取
而灰盒是局部获取了程序的信息，常见的就是获取程序的执行覆盖率，最常见的手段是二进制插桩（编译时在每个跳转分支后面插入自定义的记录代码）。比如 AFL 就是灰盒 fuzzer。
DGF（directed grey-box fuzzing）是什么#
为什么会有 DGF#
大多数的灰盒模糊测试都是使用种子的覆盖率进行引导的，在有限的时间内覆盖尽可能多的路径。这么做的主要原因是因为代码的覆盖率和 bug 的覆盖率是呈正相关的，当一个模糊测试工具能够覆盖更多的代码的时候往往能找到更多的 bug。
但是，并不能将程序中所有的代码同等或者说等权重的对待，因为模糊测试工具覆盖的绝大多数代码都是不包含 bug 的。而且在实际的应用过程中，想要覆盖完整的代码分布，是十分困难的或者说是完全不可能的。
为了克服这种问题，就提出了导向型模糊测试。
和传统的灰盒 fuzzing 有什么区别#
和传统的灰盒模糊测试相比：
1. 目标不同：传统的灰盒模糊测试为了提高代码覆盖率，而 DGF 更倾向于测试指定代码块的 bug
2. 技术不同：DGF 一般需要数据流和控制流图来计算种子和目标代码段的距离
DGF 最终要解决的问题#
利用种子和目标 target 之间的距离，作为适应度函数来帮助种子进行选择。
将距离目标位置更近的种子，更多的变异机会，来引导灰盒模糊测试到达目标位置。
整个导向型灰盒模糊测试将之前的可达性问题转换成了一个优化问题。
也就是优化生成的种子和目标位置之间的距离。
在了解导向型灰盒模糊测试的整个过程之后，能够发现，整个问题的关键就是如何定义种子和目标位置之间的距离，来进行优化。
Background#
DGF 当前主要基于两个关键机制：
1.DGF 可以支持由无向灰盒 fuzzing 中的覆盖率引导来进化测试用例
2.DGF 通过 CFG（控制流图）中的执行节点和目标节点的距离来衡量每个测试用例的优先级，并排序，从而为 fuzzer 提供到达目标程序点的指导
当前有两个 DFG 的扩展性问题：
1. 传统的覆盖反馈不总是能提供找到目标程序点（可以说是存在 crash 的程序段）的有意义的指导
2. 当程序具有复杂的控制结构时，现存的种子距离算法表现不佳
关于覆盖率引导，有时候会因为程序庞大，导致覆盖率引导的方向和目标程序点背离，Beacon 最先尝试解决该问题，并使用一个最弱先决条件来判断是否会到达目标程序点，但是这个方法在程序有复杂循环时不起效
当程序较大时，执行节点链的长度会很长，会包含很多和目标程序点语义不相关的节点，WindRanger 是第一个使用偏差基本块（DBBs）来解决偏差问题，但是在循环结构中不是一个好的形式
Motivation#
简单来看就是一段 C 语言的数组越界错误，用户可以输入任意大小的整数作为索引，而一个易受攻击的函数没有验证输入的索引
到达这个易受攻击的函数的路径只有一条，但是从 main 出发经过这条路径的同时，中途会有很多分岔路径，会大大分散测试用例的能量分配，导致误导
同时对比 AFLGo 的种子距离计算和 WindRanger 的种子距离计算，得出的结果相同，即当涉及复杂的环路结构时，基于 DBB 的距离度量同样会误导
Solution#
Selective coverage instrumentation#
为了到达程序 P 的指定代码点 t，在 t 处 backward 地构造了 Def-Use Graph，来收集所有依赖语句，并使用 Thin Slicing
关于 Thin Slicing：将指针解引用了（去除指针带来的多余变量），可以减小切片（理解为数据依赖的一个 backward 的数据流图）的大小，从而为定向 fuzzing 提供更有效率的指导
为什么要用 DUG 呢，因为 DUG 可以自动忽略掉很多不相关的节点，即留下来的只有有数据依赖关系的节点；同时，即使对应的 CFG 有循环，DUG 也不会有循环（只要没有循环数据依赖性）
Semantic relevance scoring#
从目标节点到 DUG 上最远的距离记为 1，其后所有节点到目标节点的最短距离每接近一个节点就加 1，这样执行节点路径的分数总和为语义相关分数
达到效果：种子执行了更多的节点，或更接近目标程序点的节点，则综合分数更高（如 3c 图所示）
Exp#
使用 AFL、AFLGo、Beacon、WindRanger、DAFL 五个 fuzzer，分别对 Beacon paper 中的 41 个漏洞进行了 fuzz，指标是 TTE（Time-to-Exposure），即 fuzz 一个漏洞 24 小时，得到第一个 crash 的耗时
但是不知道为什么图里没有 Beacon
结果是 DFL 最少也能平均比其他几个 fuzzer 快 1.93 倍
之后还做了消融实验：
Thin slicing 能够使得平均快 2.01 倍
Selective coverage instrumentation 能够使得平均快 1.73 倍（对比 AFL）
Semantic relevance scoring 能够使得平均快 1.39 倍（对比 AFL）
这两个 technique 合起来能够达到 1.93 倍（对比 AFL）
Discussion#
讨论了 DAFL 对于多目标的支持，即在执行节点链路上有多个目标程序点，取到他们的平均距离为相关分数
还讨论了支持其他语言比如 C/C++、Go 等语言的问题
总结#
由于现有的 DGF distance 计算存在误导的问题，用 DUG 取代 CFG，利用数据流信息取代了控制流信息，使得那些无关的节点不存在了，从而不会误导 fuzzer 的定向
使用 thin slicing 剪枝，DUG 会变得更精简，提高 fuzzer 效率
参考链接#
Fuzzing 技术总结（Brief Surveys on Fuzz Testing）
https://zhuanlan.zhihu.com/p/43432370
Directed Greybox Fuzzing 相关内容整理
https://zhuanlan.zhihu.com/p/415316061
Hawkeye：定向灰盒模糊测试技术
https://zhuanlan.zhihu.com/p/130767857
给你的模糊测试开开窍 —— 定向灰盒模糊测试（Directed Greybox Fuzzing）综述
https://www.cnblogs.com/welkinchan/p/17685797.html
【学习笔记】Fuzzing 学习笔记 3—— 灰盒 Fuzzing
https://superlova.github.io/2020/08/20/%E3%80%90%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%E3%80%91Fuzzing%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B03%E2%80%94%E2%80%94%E7%81%B0%E7%9B%92Fuzzing