# 简述

种子调度,即种子选择的顺序,对 fuzzer 的性能影响很大。现有的种子调度策略基于历史变异数据,而没有考虑到 CFG 的结构信息。通过检查 CFG,可以分析出种子变异对 edge coverage 提升的情况,从而帮助进行种子调度。

理想的调度策略应当分析种子变异的所有可达 edge,但计算开销是非常大的。因此,种子调度策略必须进行近似估计。对于这样的近似估计值 A,作者有一些观察:

  1. 如果一个种子到达更多的路径,A 值应该增加
  2. 如果历史变异信息表明某一条边难以到达,或者和当前已访问的边距离远,那么 A 值应当下降
  3. 即便对于大规模的 CFG,计算 A 值也应当是高效的

作者发现 graph influence analysis 中的 centrality(中心性)提供了这三种性质,所以可以用于高效近似计算种子变异带来的访问新边的可能性。

本文对于中心性的三个性质描述:

  1. 从节点出发能到达的边越多,该节点影响力越大;边的序列不考虑顺序
  2. 中心性可以被外部影响,比如根据历史变异记录调整影响力,并且距离该节点越远的节点对该节点影响力的贡献越小
  3. 使用迭代的方法可以在大规模的图上高效计算中心性

本文使用的是 Katz centrality,其提供了这三个性质。

# 资料

Effective Seed Scheduling for Fuzzing with Graph Centrality Analysis
IEEE S&P 2022

关于图中心性的简单介绍,degree centrality 是用节点的度数衡量;closeness centrality 是用某一节点到其他节点的距离衡量(几何意义上);betweenness centrality 是用某一节点在其他节点之间最短通路上出现次数来衡量。

# 背景、意义与思路

Fuzzing 是一种自动化探索程序输入空间,并发现能触发 bug 的输入的测试方法。目前的模糊测试器采用了边缘覆盖率导向的进化策略,来引导测试样例生成阶段,使其能探索到目标程序的不同路径。Fuzzer 周期性地从语料库中选择种子,进行变异,然后将产生新覆盖率的输出添加到语料库中。这些 fuzzer 的性能依赖于种子调度,即选择种子进行变异的顺序。

种子调度的主要挑战是确定语料库中哪些种子在变异时更有可能探索新的路径。Fuzzing 由于输入空间非常大,穷尽探索是不可能的。优先选择有价值的种子可以提高测试效率。

给定程序、种子语料库、目标程序的 CFG,通过将 CFG 转化为 edge horizon graph(包括种子、horizon、non-horizon unvisited nodes)使用

# 概览

# 解决方法

# 实验结果

# 相关工作

# 讨论、总结与展望

# 几个问题

  1. 按什么思路来分享组会?

首先介绍什么是种子调度,其解决了什么问题。然后介绍种子调度存在的问题和挑战,现有解决方法。然后引出本文的 insights,然后介绍作者的思路。然后介绍 overview、method、evaluation、discussion and limitations

  1. 文中所构建的 “节点” 具体是什么?

  2. 如何处理 “更难访问到” 的节点?

  3. 构建矩阵时,节点的规模有多大?

  4. power method 计算影响值时,为什么 α 要选 0.5?没有做更细粒度的绘图证明。以及 β 的为什么采用 1 - 忽略率的方法来计算难易度?为什么降低难以到达的 node 的影响值?

个人水平有限,以上总结仅供参考;欢迎评论区讨论、指正。