融合种间热度的灰盒模糊测试方法

任家祥，宋礼鹏，朱宇辉

(1. 中北大学 大数据学院，山西 太原 030051； 2. 山东大学(威海) 机电与信息工程学院，山东 威海 264209)

0 引 言

近年来，与日俱增的软件漏洞严重威胁着网络空间安全，如何有效检测出未知的软件漏洞是网络安全中的一大重要挑战[1]. 基于模糊测试的动态漏洞检测技术通过生成大量的测试输入可以发现程序中的各种缺陷，已成为当前研究热点[2].

Barton Miller于1990年首次提出模糊测试的概念，通过生成随机数据测试Unix程序的有效性[3]. 依据对程序的分析程度和源码依赖程度，可将模糊测试分为黑盒、白盒和灰盒[4]. 黑盒模糊测试不需要了解目标程序的内部状态，仅通过随机变异初始种子测试目标程序，虽易于部署但难以发现程序的深层漏洞. 白盒模糊测试需要从目标程序获得信息并且使用这些信息指导测试用例的生成，例如，基于LLVM的符号执行引擎KLEE[5]将符号执行应用在模糊测试中，通过约束求解条件值来增加代码覆盖率，可以一定程度上弥补传统黑盒模糊测试的不足，但是符号执行往往会因为路径爆炸问题和约束求解能力的不足，导致在程序分析阶段耗费大量时间. 灰盒模糊测试介于黑盒测试和白盒测试之间，其降低了白盒模糊测试的工程成本和复杂性，同时保留了一定程度的智能，得到了学术界和工业界的广泛关注. 在灰盒测试中常用代码插桩来获得目标程序在运行时的代码覆盖率，另一种在灰盒模糊中使用的技术是污点分析[6]，其扩展了用于追踪污点数据流的代码插桩. 灰盒模糊测试的代表AFL[7](American Fuzzy Lop)通过轻量级的编译时插桩或QEMU模式，实现对程序运行时的覆盖率信息的收集，通过覆盖信息引导模糊测试的过程. 但是，由于AFL在为种子分配能量的过程中存在一定的盲目性，限制了其代码覆盖率.

覆盖率导向的灰盒模糊测试在测试目标程序的过程中，通过能量调控算法决定在变异阶段由该种子生成的测试用例数量，由于该算法为种子分配能量时未考虑该种子所执行路径的稀有程度，导致始终存在一些路径与其他路径相比被执行的次数较少，即路径覆盖不均衡. 该问题一定程度上限制了灰盒模糊测试的路径覆盖率，因此，本文从路径覆盖不均衡问题入手，改进AFL的种子能量调控算法，从而提高其路径覆盖率. 本文用种子的热度描述与该种子执行相同路径的测试用例的数量，并将种子输入队列划分为多个温度区域. 通过计算该种子所在温度区域与高温区域和低温区域的距离，确定该种子的种间热度，即种子所执行路径的相对稀有程度. 根据种间热度为其分配能量，通过能量调控为稀有路径传递更多的能量. 选取5个真实Linux程序和LAVA-M数据集[8]作为测试集，进行本文方法和AFL以及先进灰盒模糊测试方法AFLFast[9]、FairFuzz[10]、MOPT-AFL[11]的对比实验，从路径覆盖均衡程度、路径覆盖率和漏洞检测能力三方面进行对比分析. 实验结果显示，在测试集中该方法的路径覆盖更为均衡，24 h内发现的路径总数较之AFL提高28.34%，较之3个先进模糊测试工具平均提高20.25%.

1 相关工作

灰盒模糊测试不依赖于目标程序的源代码，只使用轻量级的工具来获得一些程序运行时的信息，而没有进行复杂的程序分析，弥补了黑盒测试和白盒测试的缺陷[12]. 基于覆盖率导向的灰盒模糊测试使用插桩技术获取程序覆盖信息，其中，AFL通过静态插桩收集分支覆盖率，与libfuzzer[13]使用基本块覆盖率记录相比，可以获取更为完整的程序控制流信息，从而更好地反映目标程序状态. AFL结合插桩获得的覆盖率信息，使用遗传算法自动发现干净、有趣的测试用例，这些测试用例可用来触发目标二进制文件中的新的内部状态. AFL虽然已在现实世界程序中发现了大量的软件漏洞，但其内部算法对程序反馈信息分析利用不足，导致AFL代码覆盖率低，难以发现深层漏洞. 因此，大量研究者为提高AFL代码覆盖率对其进行优化，优化的方向主要集中在种子选择策略、种子变异策略以及能量调控策略.

Böhme[9]等针对稀有路径问题提出了AFLFast，使用马尔可夫链模型对AFL建模，发现AFL变异生成了大量执行某些高频程序路径的测试用例，将大量的计算资源浪费在高频路径上，各路径练习次数不均衡的现象导致AFL的代码覆盖率不足. AFLFast首先修改了AFL的种子选择策略，使得其倾向于选择之前被选中次数少并且执行了稀有路径的种子； 然后提出了多种能量调控策略，其核心思想在于减少分配给执行高频路径的种子的计算资源. AFLFast虽在一定程度上解决了稀有路径的问题，但根据其能量调控策略，路径的稀有程度对其获得的能量影响比重较小. 并且对于稀有路径判断标准为均值，当路径的执行次数超过均值后，即为非稀有路径，显然该指标不能有效描述路径的稀有程度. EcoFuzz[14]的思路类似于AFLFast，将AFL的能量调控问题建模为“开发VS探索”问题，并使用多臂老虎机模型对能量调控策略进行优化，种子的能量取决于其在每次迭代中是否发现了崩溃，模糊测试器倾向于为已知错误生成更多的崩溃输入.

FairFuzz[10]通过修改变异策略解决稀有分支造成的覆盖率低的问题，自动识别被执行较少的程序分支，并提出了一种新的变异掩码算法，在该算法中变异偏向于产生命中给定稀有分支的输入. FairFuzz使用动态增长的分支命中计数来判断稀有分支，虽在一定程度上避免了单一固定值造成的局限性，但其本质上仍为多个固定值，当分支的执行次数超过最大阈值后，仍会归为非稀有分支，从而导致路径被执行次数不均衡. MOPT-AFL针对模糊测试中根据固定概率分布选择变异算子所造成的漏洞检测能力低的问题[11]，使用启发式算法改进变异策略，具体使用粒子群算法寻找变异算子的全局最优分布和局部最优分布，从而动态调节模糊测试过程中选择变异算子的概率，其寻找最优分布中未加入种子执行路径的稀有程度指标，因此各路径被执行次数仍有可能不均衡.

部分研究者为提高灰盒模糊测试的漏洞挖掘能力，在模糊测试的静态分析阶段和动态执行阶段加入更多的程序分析技术. Vuzzer[15]为最大化覆盖范围并探索更深入的路径，在静态分析阶段为每个基本块分配权重，该权重由基本块的深度信息决定，并通过污点分析的方法解决魔术字节问题. Angora[16]为在不使用符号执行的前提下有效地解决路径约束，引入了几种关键技术：可伸缩的字节级污点追踪，上下文相关的分支计数，基于梯度下降的搜索. Vuzzer和Angora为灰盒模糊测试引入了复杂的程序分析技术，带来了额外的计算开销，一定程度上影响了动态执行部分的运行时间，并且增加了部署的难度.

本文发现AFL在测试目标程序一段时间后，当绝大多数路径均已被执行了一定次数时，通过比较种子之间所执行路径的稀有程度更能反映种子的优劣，因此，本文提出了种间热度指标，该指标可准确识别出执行了稀有路径的种子，然后融合种间热度指标改进了AFL的能量调控算法，为种间热度低的种子分配更高的能量，生成更多执行稀有路径的测试用例，从而提高灰盒模糊测试的路径覆盖率和漏洞检测能力.

2 融合种间热度的灰盒模糊测试

本文基于AFL2.52b开发了灰盒模糊测试工具HeatFuzz，为说明本文方法，给出以下定义：

定义1：对于种子t，其能量为由该种子变异生成的测试用例数量[9].

定义2：对于种子t，其热度为与该种子执行相同路径的测试用例数量，记为h(t).

HeatFuzz为识别出执行了稀有路径的种子，在AFL的基础上加入了热度优先序列建立模块和种间热度计算模块； 其次设计了一种融合种间热度的能量调控算法，该算法借鉴热传导现象的思想，为热度低的种子分配更多的能量. HeatFuzz的主要工作流程见图 1，具体描述如下：

1) 将用户提供的初始测试用例添加到队列中；

2) 从队列中选择下一个种子(输入文件)；

3) 尝试将种子修剪到不改变程序行为测试的最小大小；

4) 建立种子热度优先序列；

5) 计算当前种子的种间热度；

6) 根据种间热度为种子动态分配能量；

7) 使用各种模糊策略反复地对种子进行变异，变异时间由所分配能量决定；

8) 如果生成的任何测试用例导致检测记录的新状态转换，则在种子队列中添加该突变文件作为新种子；

9) 转到第二步.

其中第二步的选种策略决定从队列中选择出哪一个种子进行变异. 本文选种策略倾向于选择执行速度快、体积小并且自身热度低的种子. 本节后续将详细介绍热度优先序列的建立，种间热度的计算以及融合种间热度的能量调控算法实现.

2.1 热度优先序列

在灰盒模糊测试初始阶段需要提供一个初始种子集，随着模糊测试的进行，种子输入队列Q中将陆续加入触发新的程序行为的种子，对于执行同一条路径的种子，队列仅保存其中适应度最高的种子.模糊测试的每一轮迭代过程中，从种子输入队列Q中根据选种策略选择待模糊的输入文件，Q中包括n个种子，随着模糊测试的不断进行，n将持续增大.将Q记为Q={t1,t2,…,tn}.

根据Q中每个种子的热度h(ti)对其进行排序，得到热度优先序列S={t1,t2,…,tn}.其中，t1为序列中热度最高的种子，tn为序列中热度最低的种子.

得到种子热度优先序列S后，可知种子ti+1与ti-1的热度与ti的热度大小较为接近，因此，可将ti临近的种子视为位于同一温度区域.将S等分为m个子序列，每个子序列中有n/m个种子，即子序列的长度为n/m，记为β.因此，序列S=S1+…+Sm，其中，S1={t1,…,tβ},…,Sm={tn-β+1,…,tn}.

子序列Sk的热度H(Sk)为Sk中种子热度的平均值，即

(1)

种子热度优先序列S的平均热度H(S)为

(2)

完成热度优先序列建立后，便可根据种子热度及种子所在子序列的热度，计算出种间热度.

2.2 种间热度计算

由于模糊测试的过程中不断产生新的测试用例，种子热度优先序列S的总能量以及各子序列的热度均在不断上升.如果根据某一具体的值来划分热度高与热度低的种子，在长时间的模糊测试后该策略将失去意义.因此，本文提出了一种随着模糊测试的进行不断动态适应变化的指标，即种间热度.

在2.1节中得到了种子热度优先序列S并将其划分为m个子序列，种子热度优先序列S的子序列S1为热度最高的子序列，Sm为热度最低的子序列.通过计算序列之间的欧式距离来分析热度差异.

对于子序列Sk中的种子(1

(3)

计算Sk与Sm的欧式距离ρkm.

(4)

当ρ1k>ρkm时，说明Sk与S1的距离大于Sk与Sm的距离，低温区域的热度与Sk的热度较为接近，则Sk为相对低温区域.由此可知，Sk中的种子的热度较低，即执行了相对稀有路径.同理，当ρ1k<ρkm时，则Sk为相对高温区域，Sk中的种子热度较高，即执行了相对高频路径.

根据热传导的性质，热量传递的结果是使系统各部分热度达到平均，本文期望通过算法干预使得稀有路径的热度逐渐接近路径的平均热度.因此，还需计算Sk中的种子的热度与S平均热度的比值Rk，进一步完善种间热度计算，计算公式为

(5)

当Rk>1时，Sk的平均热度低于全局平均热度； 当Rk<1时，Sk的平均热度高于全局平均热度.通过计算Rk可快速确定Sk的热度与全局热度的关系.

2.3 融合种间热度的能量调控算法

AFL的能量调控算法通过计算测试用例的执行速度、位图大小、测试用例的产生时间等因素为输入文件进行打分，返回一个能量值，决定由该种子生成的测试用例数量[17]，希望使执行时间短、代码覆盖高、新发现的、执行路径深度深的种子拥有更多变异的时间. 该算法实质上为贪心算法，往往不能做出最优的全局选择. 因此，本文期望对AFL的能量调控算法进行改进，对不同热度的种子分配不同的能量，来影响每一轮模糊测试中被测试用例执行过的程序路径的能量，从而提高模糊测试的路径覆盖率.

本文的能量调控算法借鉴了热传导现象的思想，自然界中有温差存在的地方，热量会自发地由高温区域向低温区域传递[18]. 随着模糊测试的进行，系统的整体能量不断上升，并且无法降低路径的能量，只能通过降低或增加分配给执行该路径的种子的能量，使得各路径的能量趋于均衡. 因此，本文期望为种间热度更低的种子分配更多的能量，分配的能量与热度差成正比. 对于使用选种策略选中的待分配能量的种子t′，算法1详细说明了其能量调控算法.

算法1 融合种间热度的能量调控算法

输入：种子t′

种子队列Q

子序列数m

输出：种子能量p

1.n=Length(Q)

2.S=SortQby heat//根据种子热度排序

3. forifrom 1 tondo

4. ifsi.heat==t′.heat then

5.k=i

6. end if

7. end for

8.k=k/(n/m)//确定种子所属的子序列

9.ρ1k=EuclideanDist (S1,Sk)

10.ρkm=EuclideanDist (Sk,Sm)

11.Rk=Avg(S.heat) / Avg(Sk.heat)

12.a=OriginalEnergy(t′)//原始能量

13. ifρ1k>ρkmthen

14.p=a*ρ1k*2Rk

15. else ifρ1k<ρkmthen

16.p=a/ρkm* 2(-1/Rk)

17. end if

18.p=Min(p,M)//能量最大为M

在算法1中，给定待计算能量的种子t′，种子输入队列Q，热度优先序列子序列数为m.该算法分为两部分，第一部分进行种间热度计算(1～11行)，首先建立热度优先序列(1～2行)，遍历S确定种子t′在序列S中所处的位置(3～7行)，向上取整除以子序列的长度n/m，确定t′所属的子序列Sk(第8行)，计算出Sk与热度最高和最低的子序列的欧式距离(9～10行)，然后计算Sk与序列S平均热度的比值Rk(11行).通过计算种间热度，可准确识别出执行了相对稀有路径的种子.第二部分计算为t′分配的能量(12-18行)，t′的原始能量大小为a，由AFL的原始能量调控策略给出(12行).如果种子t′所在子序列与热度最高子序列的欧式距离较大，则其位于相对低温区域，应增加为t′分配的能量，将原始能量a根据Rk呈指数放大，然后乘以Sk与高温区域的欧式距离(13行～14行)； 反之，t′位于相对高温区域，应减小为t′分配的能量，将原始能量根据平均温度比值呈指数缩小，然后除以Sk与低温区域的欧式距离(15行～16行).最后将t′分配的能量上限限制为M.

算法1通过比较序列之间的欧式距离确定t′的相对热度，充分考虑了种子间的热度差异，避免了固定值判断指标的单一性，准确判断出t′所执行路径的相对稀有程度.将原始能量呈指数增长或减小，确保了种子能量的快速增长与收敛，使各路径被执行次数趋于均衡，有效优化了灰盒模糊测试的路径发现能力.该算法的时间复杂度由种子队列Q的长度n决定，其中，时间复杂度最高的操作为建立热度优先序列部分，可表示为O(nlogn)，计算欧式距离部分时间复杂度为O(n/m)，计算平均温度比值Rk部分复杂度为O(n).由此可知该能量调控算法的时间复杂度为O(nlogn)，并未在AFL中加入复杂的计算过程，保留了其轻量级的特点.

3 实验评估

3.1 实验设计

为评估本文方法在覆盖率导向的灰盒模糊测试中的有效性，应用本文方法在AFL与MOPT-AFL的基础上进一步开发出HeatFuzz与MOPT-heat. 选取AFL以及当前先进的灰盒模糊测试方法AFLFast、FairFuzz、MOPT-AFL作为本实验对照.

测试环境为Ubuntu 18.04LTS 64位操作系统，处理器型号为Intel(R) Xeon(R) Platinum 8269CY CPU @ 2.50 GHz处理器，在单核心上运行模糊测试工具，内存为8 GB.

本文选取LAVA-M数据集和五个真实Linux应用程序作为测试集，LAVA-M数据集由base64、md5sum、uniq、who这4个应用程序组成，每个程序中被注入了多个漏洞，该数据集常用于评估模糊测试工具的性能. 5个真实Linux应用程序为binutils-2.36中的objdump、readelf，libtiff-4.0.9中的tiff2rgba和tiff2pdf，libxml2-2.9.2中的xmllint. 为了保证实验结果的普遍性，测试集选取的目标程序处理的文件格式包括纯文本类型、二进制程序、TIFF图片、PDF文件以及XML文件，5个真实Linux应用程序的详细说明见表 1.

表 1 目标程序配置Tab.1 The configuration of target programs

实验中，首先分析模糊测试方法的路径覆盖均衡性的对比，然后重点对比6个模糊测试工具的路径覆盖率和路径发现速率，最后在LAVA-M数据集上对比漏洞发现能力.

3.2 路径覆盖均衡性分析

为比较不同模糊测试方法的路径覆盖均衡程度，本文通过覆盖率反馈信息记录模糊测试中目标程序各路径被测试用例执行的次数，并计算总体标准差. 通过计算程序路径总体标准差可以反映出当某一模糊测试工具测试目标程序时，该程序中各路径被执行的次数与路径平均执行次数之间的偏差，总体标准差越小则路径覆盖越均衡.

模糊测试工具在目标程序中各路径被执行次数的集合L为总体，该目标程序已发现的路径总数为n，第i条路径记为li, 则该模糊测试工具测试目标程序中各路径被执行次数的总体标准差σ为

(6)

使用相同的初始种子集，6个模糊测试工具在测试集中的9个目标程序中分别运行1 h，比较每个模糊测试工具在不同目标程序上已发现的各条路径被测试用例执行次数的总体标准差，计算结果舍去小数，详见表 2.

表 2 程序路径总体标准差Tab.2 Program paths population standard deviation

由表 2 中数据可见，HeatFuzz在9个应用程序上的总体标准差均小于AFL、AFLFast和FairFuzz，可见HeatFuzz对目标程序覆盖更为均衡. 另外，MOPT-heat在9个应用程序上的总体标准差均小于MOPT-AFL. 由此可知，本文方法通过种间热度识别出执行稀有路径的种子，并动态计算为其分配的能量，使得各路径被执行次数更接近平均值，从而使得各路径覆盖更为均衡.

3.3 路径覆盖分析

通过分析程序路径覆盖数，可以判断模糊测试工具是否对目标程序进行了充分的测试. 使用AFL、AFLFast、FairFuzz、HeatFuzz、MOPT-AFL和MOPT-heat分别在9个应用程序中运行24 h, 路径覆盖数详见表 3.

由表 3 中数据可见，在9个应用程序中，HeatFuzz在其中8个应用程序中发现的路径数多于AFL，路径覆盖较之AFL平均提升22.34%，在5个真实应用程序中平均提升32%，在测试集中发现的路径总数比AFL多28.24%，由此可见，HeatFuzz通过解决路径覆盖不均衡的问题，稳定提升了AFL的路径覆盖率.

较之与HeatFuzz优化方向类似的先进模糊测试工具AFLFast与FairFuzz，发现路径总数分别提升27.39%与13.78%，说明HeatFuzz的路径发现能力优于这二者. 较之MOPT-AFL,MOPT-heat在8个应用程序中发现了更多的路径，路径覆盖数平均提升17.64%，总路径数多19.58%，在5个真实Linux程序中平均提升 28.04%. 综上，本文方法对于3个先进灰盒模糊测试方法的路径覆盖总数平均提高20.25%. 因此，融合种间热度的能量调控算法可有效提高覆盖率导向的灰盒模糊测试的路径覆盖率.

表 3 路径覆盖数分析Tab.3 Path coverage analysis

3.4 路径发现效率分析

对于灰盒模糊测试来说，路径发现效率与漏洞发现效率成正比[19]，分析路径发现效率可有效衡量模糊测试工具的漏洞检测能力. 24 h内，在 9个应用程序中6个模糊测试工具的路径发现效率对比详见图 2.

图 2 路径发现效率分析

首先，分析本文方法与AFL、AFLFast、FairFuzz的对比实验结果，由图 2(a)～图 2(i)可见，HeatFuzz在除tiff2pdf之外的8个应用程序上的路径发现效率明显优于FairFuzz，在除md5sum之外的8个应用程序上的路径发现效率明显优于AFL. 由图 2(e)～图 2(i)可见，在5个真实Linux程序中，AFL、AFLFast与HeatFuzz在前 5 h 内发现的路径数量均保持着稳定的增长，这是因为在模糊测试初期有着大量待发现的路径； 而HeatFuzz在不牺牲前期快速发现大量路径能力的前提下，随着时间的增长，最终发现的路径数均多于AFL与AFLFast. AFLFast在readelf中与HeatFuzz路径发现效率相近，但是在objdump与tiff2pdf中，HeatFuzz更为快速且稳定地测试了目标程序. 因此，本文提出的种间热度指标可更准确地描述出种子所执行路径的稀有程度，融合种间热度的能量调控算法有效提高了灰盒模糊测试路径发现效率.

然后，分析本文方法和MOPT-AFL的对比实验结果. 由图 2(a)～图 2(d)可见，在LAVA-M数据集上由于目标程序路径总数较少，MOPT-AFL和MOPT-heat的路径发现效率相近，发现的路径数接近上限. 由图2(e)～图 2(i) 可见，较之MOPT-AFL，MOPT-heat在5个真实Linux中路径发现效率明显优于MOPT-AFL，说明即使在其他优化方向的模糊测试工具中应用本文方法，同样可以有效提高其路径发现效率，因此本文方法具有一定的普适性.

3.5 漏洞检测能力分析

比较模糊测试工具优劣的最终指标是其漏洞检测能力，一个好的模糊测试工具应该快速地检测出目标程序中的漏洞[20]. 为证明本文方法对于灰盒模糊测试漏洞挖掘能力的提高，6个模糊测试工具使用相同的初始种子集，在LAVA-M数据集上各运行6 h，比较发现的漏洞数量，结果详见表 4.

表 4 漏洞检测能力分析Tab.4 Vulnerability detection capability analysis

由表 4 可见，HeatFuzz较之AFL、AFLFast和FairFuzz，在base64、uniq和who程序中均发现了更多的漏洞. 其中，AFL仅在base64中发现了漏洞，AFLFast和FairFuzz仅在base64中发现的漏洞数量与HeatFuzz接近，并且MOPT-heat较之MOPT-AFL在uniq和md5sum中发现了更多的漏洞. 因此，本文方法可用于解决灰盒模糊测试路径覆盖不均衡的问题，具有更高的路径覆盖率，可以生成更多执行漏洞所在区域的测试用例，更有可能触发程序漏洞，从而有效提高了灰盒模糊测试的漏洞挖掘能力.

4 结 论

为解决灰盒模糊测试中路径被执行次数不均衡的问题，首先提出了种间热度指标来识别执行稀有路径的种子，然后提出了一种能量调控算法使得各路径被执行次数趋于均衡，并基于AFL2.52b与MOPT-AFL进一步开发出了HeatFuzz和MOPT-heat. 实验结果表明，本文方法路径覆盖更为均衡，有效提高了灰盒模糊测试的路径覆盖率和漏洞检测能力，具有实际应用价值.

未来的研究工作中将进一步提高灰盒模糊测试在复杂路径约束下的路径覆盖率，引入更多的程序分析技术，比如上下文语义分析和污点分析技术. 另外，将完善并扩展种子序列模型，在该模型上进行不同种子间的差异度分析.