模糊测试中的基于图中心性分析的种子调度策略｜技术解析

种子调度作为模糊测试中至关重要的一个环节，决定着种子队列的质量与模糊器能量的分配方式，在很大程度上影响着模糊器的性能。现有的种子调度策略利用历史变异信息完成种子调度工作，如AFL及其衍生产物，它们优先选择那些在历史模糊测试中拥有更高覆盖率或命中稀有边的种子。虽然此类基于历史信息的种子调度策略能够给予模糊器有效指导，但是它们忽略了目标程序的底层控制流图结构，无法鉴别种子到达程序未被访问区域的能力。

程序控制流图（CFG）作为程序执行过程中所有基本块执行可能流向的表现，反映着基本块节点之间的相互关系。现有基于控制流引导的灰盒模糊测试所使用的种子调度策略利用当前种子集能够覆盖到的CFG区域内的信息进行种子的筛选与能量分配，并没有充分利用到CFG内无法被覆盖到区域的信息。She D等人敏锐地发现，CFG中能够触发新边的节点位于已被覆盖区域和未被覆盖区域的边界处，而且边界处每个节点的重要性存在差异——有的节点能够比其他节点触发更多的边。显然，我们希望选取那些更有可能触发新边的种子，而这些种子应当覆盖到更多“重要”的边界节点。因此，如果选取一个合适的标准对CFG中的节点进行重要性评估，再综合节点的重要性对种子质量进行评估，那么就可以筛选出队列中更有可能触发新覆盖率的种子，并将更多能量分配给这一部分种子。She D发现这一需求可以被抽象为图的中心性分析问题：节点的中心性用于衡量节点在图中的重要性。下面让我们一起讨论一下She D等人提出的K-Scheduler方法。

网络（图）由节点和连接节点的边组成。在社会网络分析领域，一项基本的任务就是鉴定一群人中那些人比其他人更有影响力，从而帮助我们理解他们在网络中扮演的角色。这一任务使用的分析算法即为网络中心性分析。CFG作为一个有向图，其中每个基本块节点在重要性上也具有一定差异。那么，什么样的节点是重要的呢？

让我们先从最简单的中心性——度中心性（Degree Centrality）开始。如图1所示，该网络包含5个节点和6条边。度中心性认为可以基于一个节点的度测量其中心性，即如果一个节点于其它许多个节点相连，那么该节点可以被认为是重要的。其表达式如公式1所示所示：

本文中作者采用的中心性分析算法——KATZ中心性（KATZ Centrality）是特征向量中心性的一个变体，它不仅考虑了直接邻居的中心性，还考虑了网络中通过这些直接邻居连接到所考虑节点的所有其他节点的数量来计算网络中节点的相对影响。KATZ中心性的计算公式如公式3所示：

了解了中心性分析的概念后，让我们继续了解K-Scheduler的工作流程。

K-Scheduler的总体框架如图2所示，给定程序、种子语料库和目标程序的过程间CFG，K-Scheduler首先修改CFG以生成仅由种子、边界节点和非边界未访问节点组成的边缘分界线图。然后，使用Katz中心性对边缘分界线图进行中心性分析。模糊器优先选择中心性得分最高的种子。当模糊器的突变到达以前未访问的节点时，删除这些新访问的节点，并在更新后的边缘分界线图上重新计算Katz中心性。

该小节将基于下方例子进行讲解。

K-Scheduler首先根据target的CFG生成边缘分界线图（Edge Horizon Graph）。生成过程如下所示：首先，根据当前语料库的覆盖范围将CFG中的节点分为已访问和未访问节点，如图3(a)，其中灰色节点为已访问节点，白色节点为未访问节点。然后，识别CFG中的边界节点。边界节点位于已访问节点和未访问节点交界处，如图3(a)，其中A和B即为边界节点，因为它们是具有已访问父节点的未访问节点。最后，将种子节点插入CFG，并将它们连接到沿着种子执行路径可以触碰到的所有边界节点（即触碰不一定可以访问块，但是经过块的父节点），同时删除已访问节点，如图3(b)。

得到边缘分界线图后，需要根据边缘分界线图计算边界节点的中心性。如背景知识中提到的KATZ中心性度量公式，其矩阵表达形式为：

以种子s3(a=15, b=30)为例，如图3(c)所示。一开始，c_{s2}(0)=1。使用公式c(t)=alpha Ac(t-1)+beta计算，第一轮迭代：

第二轮迭代：

第三轮迭代：

可以看到，经过三轮迭代后，种子S2比S1具有更高的得分，因此模糊器会优先选取S2进行后续的变异操作。

本章节将主要介绍作者进行的验证K-Scheduler有效性的实验。

对于与基于Libfuzzer的种子调度策略，作者将K-Scheduler与Entropic和Libfuzzer默认种子调度器（Defalult）进行对比，将24小时作为一轮的循行周期，共计运行了10次，并取10次运行结果的算术平均值。该实验结果如表1所示，可以看出，在运行了24小时后，K-Scheduler的特征覆盖率与边覆盖率与Entropic和Libfuzzer默认种子调度器相比都要更高。

对于与基于AFL的种子调度策略，作者将K-Scheduler与RarePath、RareEdges、NewPath、SecurityCov和AFL默认种子调度策略（Default）进行24小时一轮、10次实验，结果如表2所示。

经过统计，K-Scheduler比Entropic增加了25.89%的特征覆盖率，比次之的基于AFL的种子调度器(RarePath)增加了4.21%的边缘覆盖率。

为了检测不一定会导致崩溃的内存损坏错误，作者使用Address和Undefined Behavior santizers编译12个测试目标程序，然后再K-Scheduler、AFL、RarePath、RareEdge和NewPath上进行24小时一轮、共10轮的实验。最终，试验结果表明，K-Scheduler比种子调度策略SecCov（TortoiseFuzz）多发现3个bug。

运行时开销可以分为两个部分：1）模糊器记录边命中情况并为种子分配能量；2）调用K-Scheduler进行种子调度。为了测量这两部分开销，作者同样以12个目标程序运行AFL和Libfuzzer24小时，共运行10轮。在这一过程中，记录他们的时间开销总时间，同时分别记录在独立进程中计算边缘水平图上的Katz中心性所花费的总时间。详细结果如下图所示，K-Scheduler增加了最多1%的图表分析开销和最多2%的模糊维护开销。

本文中作者提出了一个简单但是目的清晰的种子调度策略。比起现有种子调度策略，作者将模糊测试中的种子调度问题抽象为图的中心性分析问题，能够充分使用CFG未被覆盖区域内的信息来进行种子调度。