作者: Hongxu Chen, Yinxing Xue， Yuekang Li, Bihuan Chen, Xiaofei Xie, Xiuheng Wu, Yang Liu
出处：CCS 2018
背景
定向模糊测试就是引导模糊测试朝着目标代码块的方向探索，让已覆盖的代码块越来越接近目标代码块，最终测试目标代码块。那么已覆盖的路径和目标代码块之间的距离衡量是一个需要解决的关键问题。AFLGO通过控制流图、函数调用图来计算一个输入覆盖的路径上所有基本块距离目标基本块的平均距离，作为种子调度的依据。也就是说，为了衡量这样的距离，需要额外的静态分析，因为动态执行我们只能知道覆盖了哪里，并不知道和目标之间的距离。
这个距离计算的静态分析需要具有以下性质：
1. 性能损耗要在一个可接受的范围。
2. 要能够提供必要的信息。
定向模糊测试需要具有以下性质：
1. 给种子设置优先级，尽快地接近目标代码块。
2. 当种子覆盖程序的不同状态的时候要使用不同的变异策略。
Insight
作者分析了定向模糊测试需要具有的四个性质。
对于第一个性质作者只用静态分析计算邻接函数的距离，函数级别的距离和基本块级别的距离用来得到函数之间的亲和度。在fuzzing运行的时候计算基本块trace距离以及已覆盖函数和目标函数之间的相似性。
对于第二个性质，基于CG和CFG分析函数的可达性、指针分析、间接调用等信息。
对于第三个性质，利用上述的基本块trace以及函数亲和度等信息来指导种子调度。
对于第四个性质，提出了一个适应性变异策略。
方法
- 静态分析：给定程序源代码和目标，利用静态分析推导出目标所在的基本块和函数，标记为目标基本块和目标函数。然后利用插桩技术把基本块距离信息插桩到目标程序中，然后输出。这里的基本块距离信息获取步骤如下：
-
构建CG和CFG。
-
基于CG经计算函数级别的距离，也就是计算邻接函数的距离。
- 给定一个callee C N C_N CN，caller可能会通过很多条路径都可以调用到它， Φ ( C N ) = ϕ ⋅ C N + 1 ϕ ⋅ C N \Phi(C_N)=\frac{\phi·C_N+1}{\phi·C_N} Φ(CN)=ϕ⋅CNϕ⋅CN+1,用于表示这种影响，通常 ϕ = 2 \phi =2 ϕ=2。
- caller函数中包含callee的基本块的数量越多调用到callee的执行trace就越多，这个影响表示为 Ψ ( C B ) = ψ ⋅ C B + 1 ψ ⋅ C B \Psi(C_B)=\frac{\psi·C_B+1}{\psi·C_B} Ψ(CB)=ψ⋅CBψ⋅CB+1,通常 ψ = 2 \psi=2 ψ=2。
- 给定caller f 1 f_1 f1，callee f 2 f_2 f2,它们之间的距离为 d f ′ ( f 1 , f 2 ) = Ψ ( f 1 , f 2 ) ⋅ Φ ( f 1 , f 2 ) d'_f(f_1,f_2)=\Psi(f_1,f_2) ·\Phi(f_1,f_2) df′(f1,f2)=Ψ(f1,f2)⋅Φ(f1,f2)。
- 由于目标函数可能有多个，那么一个函数到所有目标函数的平均距离为：
-
基于函数级别的距离计算基本块之间的距离，通过CG和CFG。对于每一个基本块计算它到达目标基本块的距离然后插桩。
-
最后还会给每一个目标位置列出所有能够到达它的函数。
-
- 模糊测试：把插桩好的程序、上述收集的信息、目标位置、初始测试用例给fuzzing。fuzzing输出能够触发程序异常的输入。
-
能量调度：主要由两方面因素决定，基本块trace距离以及已覆盖函数相似度。
- 基本块trace距离计算为：对于种子s执行的trace上的所有基本块计算一个平均的基本块级别的距离。然后进行一个归一化。
- 已覆盖函数相似度（这里不用基本块级别是因为太重量级了），就是种子覆盖的函数里面有多少是能够到达目标位置的。
- 基本块trace距离计算为：对于种子s执行的trace上的所有基本块计算一个平均的基本块级别的距离。然后进行一个归一化。
-
种子调度，考虑到种子的多样性，他这里设置了一定的概率不会给选中的种子分配更多的能量。
-
变异策略：选中一个种子后对于给定的能量对每种变异算子分配使用次数。他把变异分为了粗粒度和细粒度。它的策略就是当种子s能到达目标位置就提高细粒度的变异的占比。
-
种子优先级：提出了一个三级队列，就是根据种子的分数分到不同的级别，从最高级别开始选。覆盖新的分支、和目标种子相似度高、覆盖目标函数的种子优先级会更高。
-
