基本信息
原文名称 Effective Seed Scheduling for Fuzzing with Graph Centrality Analysis
原文作者 She D, Shah A, Jana S.
原文链接 https://arxiv.org/pdf/2203.12064.pdf
发表期刊 IEEE Symposium on Security and Privacy(S&P),2022
开源代码 https://github.com/Dongdongshe/K-Scheduler
一、 引言
种子调度作为模糊测试中至关重要的一个环节,决定着种子队列的质量与模糊器能量的分配方式,在很大程度上影响着模糊器的性能。现有的种子调度策略利用历史变异信息完成种子调度工作,如AFL及其衍生产物,它们优先选择那些在历史模糊测试中拥有更高覆盖率或命中稀有边的种子。虽然此类基于历史信息的种子调度策略能够给予模糊器有效指导,但是它们忽略了目标程序的底层控制流图结构,无法鉴别种子到达程序未被访问区域的能力。
程序控制流图(CFG)作为程序执行过程中所有基本块执行可能流向的表现,反映着基本块节点之间的相互关系。现有基于控制流引导的灰盒模糊测试所使用的种子调度策略利用当前种子集能够覆盖到的CFG区域内的信息进行种子的筛选与能量分配,并没有充分利用到CFG内无法被覆盖到区域的信息。She D等人敏锐地发现,CFG中能够触发新边的节点位于已被覆盖区域和未被覆盖区域的边界处,而且边界处每个节点的重要性存在差异——有的节点能够比其他节点触发更多的边。显然,我们希望选取那些更有可能触发新边的种子,而这些种子应当覆盖到更多“重要”的边界节点。因此,如果选取一个合适的标准对CFG中的节点进行重要性评估,再综合节点的重要性对种子质量进行评估,那么就可以筛选出队列中更有可能触发新覆盖率的种子,并将更多能量分配给这一部分种子。She D发现这一需求可以被抽象为图的中心性分析问题:节点的中心性用于衡量节点在图中的重要性。下面让我们一起讨论一下She D等人提出的K-Scheduler方法。
二、 背景知识——基于中心性度量的影响分析
网络(图)由节点和连接节点的边组成。在社会网络分析领域,一项基本的任务就是鉴定一群人中那些人比其他人更有影响力,从而帮助我们理解他们在网络中扮演的角色。这一任务使用的分析算法即为网络中心性分析。CFG作为一个有向图,其中每个基本块节点在重要性上也具有一定差异。那么,什么样的节点是重要的呢?
图 1 网络样例
让我们先从最简单的中心性——度中心性(Degree Centrality)开始。如图1所示,该网络包含5个节点和6条边。度中心性认为可以基于一个节点的度测量其中心性,即如果一个节点于其它许多个节点相连,那么该节点可以被认为是重要的。其表达式如公式1所示所示:
根据该公式,可以计算得出节点v1和v5拥有最高的中心性3,v2、v3和v4有相同的中心性2。显然,度中心性认为节点所有邻居的重要性都是相同的。然而,事实并非如此,以v3和v4为例,V4的两个邻居节点都拥有度中心性3,而v3的两个邻居节点中只有一个度中心性为3,v4的重要性因此会略高于v3,因为v4的两个“朋友”具有更高的影响力。
为了考虑到邻居节点对节点中心性的影响,需要用到特征向量中心性(Eigenvector Centrality)。其定义公式如公式2所示。可以看到,特征向量中心性还考虑到了相邻节点的中心性。通过计算可得,v4的特征向量中心性为0.806,略高于v2和v3的0.675。
本文中作者采用的中心性分析算法——KATZ中心性(KATZ Centrality)是特征向量中心性的一个变体,它不仅考虑了直接邻居的中心性,还考虑了网络中通过这些直接邻居连接到所考虑节点的所有其他节点的数量来计算网络中节点的相对影响。KATZ中心性的计算公式如公式3所示:
三、 K-Scheduler工作流程
了解了中心性分析的概念后,让我们继续了解K-Scheduler的工作流程。
框架总览
图 2 K-Scheduler工作流程图
K-Scheduler的总体框架如图2所示,给定程序、种子语料库和目标程序的过程间CFG,K-Scheduler首先修改CFG以生成仅由种子、边界节点和非边界未访问节点组成的边缘分界线图。然后,使用Katz中心性对边缘分界线图进行中心性分析。模糊器优先选择中心性得分最高的种子。当模糊器的突变到达以前未访问的节点时,删除这些新访问的节点,并在更新后的边缘分界线图上重新计算Katz中心性。
四、 实现细节
该小节将基于下方例子进行讲解。
图 3 边缘分解图生成过程
K-Scheduler首先根据target的CFG生成边缘分界线图(Edge Horizon Graph)。生成过程如下所示:首先,根据当前语料库的覆盖范围将CFG中的节点分为已访问和未访问节点,如图3(a),其中灰色节点为已访问节点,白色节点为未访问节点。然后,识别CFG中的边界节点。边界节点位于已访问节点和未访问节点交界处,如图3(a),其中A和B即为边界节点,因为它们是具有已访问父节点的未访问节点。最后,将种子节点插入CFG,并将它们连接到沿着种子执行路径可以触碰到的所有边界节点(即触碰不一定可以访问块,但是经过块的父节点),同时删除已访问节点,如图3(b)。
得到边缘分界线图后,需要根据边缘分界线图计算边界节点的中心性。如背景知识中提到的KATZ中心性度量公式,其矩阵表达形式为:
因此,首先需要确定参数α和β的值。衰减参数α用来衰减来自更远节点的贡献,作者根据实验经验将其设置为0.5。每个节点常数参数β计算方式为:若种子进行了100次变异,其中70次变异后种子可以到达边界节点A的父节点,100次变异后种子可以到达边界节点B的父节点,那么节点A的
图 4 KATZ中心度计算迭代过程
以种子s3(a=15, b=30)为例,如图3(c)所示。一开始,c_{s2}(0)=1。使用公式c(t)=\alpha Ac(t-1)+\beta计算,第一轮迭代:
第二轮迭代:
第三轮迭代:
可以看到,经过三轮迭代后,种子S2比S1具有更高的得分,因此模糊器会优先选取S2进行后续的变异操作。
五、 实验
本章节将主要介绍作者进行的验证K-Scheduler有效性的实验。
5.1 实验设置
由于当前流行的其它种子调度策略通常被集成到AFL或LibFuzzer中,作者将K-Scheduler分别集成到AFL(或基于AFL改进的模糊器)和LibFuzzer中,在底层模糊器相同的情况下比较种子调度策略。这一方法同样可以证明K-Scheduler的通用性。
作者使用谷歌的FuzzBench基准测试,这是一个常用的数据集,用于评估真实程序上的模糊性能。作者从基准测试中选择了12个不同的实际程序,包括密码和数据库程序以及解析器。同时,作者使用基准测试提供的默认种子语料库和配置,以支持公平的比较。
本次实验在4台拥有Intel Xeon E5-2623 CPUs以及Ubuntu 20.0操作系统的计算机上进行。作者在模糊评估中遵循标准操作程序,将每个模糊器绑定到一个CPU。
5.2 RQ1:种子调度对比
对于与基于Libfuzzer的种子调度策略,作者将K-Scheduler与Entropic和Libfuzzer默认种子调度器(Defalult)进行对比,将24小时作为一轮的循行周期,共计运行了10次,并取10次运行结果的算术平均值。该实验结果如表1所示,可以看出,在运行了24小时后,K-Scheduler的特征覆盖率与边覆盖率与Entropic和Libfuzzer默认种子调度器相比都要更高。
表 1 K-Scheduler与Entropic和Libufuzzer默认种子调度
策略对比结果
图 5 K-Scheduler与Entropic和Libufuzzer默认种子调度策略
覆盖信息对比图
对于与基于AFL的种子调度策略,作者将K-Scheduler与RarePath、RareEdges、NewPath、SecurityCov和AFL默认种子调度策略(Default)进行24小时一轮、10次实验,结果如表2所示。
表 2 K-Scheduler与基于AFL的种子调度策略对比结果
图 6 K-Scheduler与基于AFL的种子调度策略边覆盖率对比图
经过统计,K-Scheduler比Entropic增加了25.89%的特征覆盖率,比次之的基于AFL的种子调度器(RarePath)增加了4.21%的边缘覆盖率。
5.3 RQ2:漏洞挖掘
为了检测不一定会导致崩溃的内存损坏错误,作者使用Address和Undefined Behavior santizers编译12个测试目标程序,然后再K-Scheduler、AFL、RarePath、RareEdge和NewPath上进行24小时一轮、共10轮的实验。最终,试验结果表明,K-Scheduler比种子调度策略SecCov(TortoiseFuzz)多发现3个bug。
表 3 漏洞挖掘实验所用目标程序
表 4 K-Scheduler漏洞挖掘结果
5.4 RQ3:运行时开销
运行时开销可以分为两个部分:1)模糊器记录边命中情况并为种子分配能量;2)调用K-Scheduler进行种子调度。为了测量这两部分开销,作者同样以12个目标程序运行AFL和Libfuzzer24小时,共运行10轮。在这一过程中,记录他们的时间开销总时间,同时分别记录在独立进程中计算边缘水平图上的Katz中心性所花费的总时间。详细结果如下图所示,K-Scheduler增加了最多1%的图表分析开销和最多2%的模糊维护开销。
表 5 将K-Scheduler接入ALF和Libfuzzer的运行开销
六、 总结
本文中作者提出了一个简单但是目的清晰的种子调度策略。比起现有种子调度策略,作者将模糊测试中的种子调度问题抽象为图的中心性分析问题,能够充分使用CFG未被覆盖区域内的信息来进行种子调度。
还没有评论,来说两句吧...