AFL能量调度优化方法研究

范永陈

（四川大学网络空间安全学院，成都 610065）

0 引言

模糊测试技术（fuzzing）是当前最流行的漏洞检测技术。其基本原理是将种子文件进行随机变异，生成大量新的程序输入，然后在目标程序中执行，跟踪目标程序运行状态信息，最后对目标程序崩溃信息进行分析来发现程序漏洞。然而传统的模糊测试技术由于缺乏引导，严重影响了漏洞检测效率。由此诞生了灰盒模糊测试技术（gray-box fuzzing），灰盒模糊测试借助轻量级的程序分析，获取程序运行时信息，借助运行时信息对模糊测试过程进行引导，提升漏洞检测效率。

当前模糊测试技术可以划分为基于生成的模糊测试和基于突变的模糊测试。基于生成的模糊测试通常需要测试人员提供目标程序输入的格式信息或语法知识。模糊测试程序根据输入的格式信息或相关语法自动生成程序输入进行漏洞检测。这种方式使得程序输入能够通过目标程序校验代码，到达目标程序深层代码区域。但这种方式需要人工编写规则来描述程序输入的格式，并且目标程序不同需要的格式描述文件也不相同。因此这种方式适用于结构化的程序输入，如HTML、Java Script 等，代表模糊器有AFLsmart。基于突变的模糊测试则不需要熟悉输入文件的格式。模糊测试工具通过一组预定义的变异规则来生成新的程序输入，代表模糊器有AFL、AFLFast、EcoFuzz等。

本文基于突变的灰盒模糊测试进行研究。该方法认为能够探索到新的执行路径的测试用例具有较高的价值，将其保存到种子队列进行后续测试，不能探索到新的执行路径的测试用例直接丢弃。AFL 为此类模糊器的代表，它在漏洞检测方面取得了非常好的效果。AFL 在进行种子选择后，会立即进行能量调度。能量调度的目的是在模糊过程中为种子分配能量，从而确定种子的变异次数。近年来的研究表明，能量调度对模糊测试系统至关重要，合理的能量分配可以有效地提高新路径的发现速度。如果一个种子的能量被过度分配，会导致其占用过多的测试时间，使得其他种子的测试时间不足。相反，如果种子的能量分配不足，就会不利于新路径的发现和潜在的漏洞检测。

目前AFL 存在能量分配不合理的问题。具体来讲，AFL 的能量分配取决于种子执行时间、位图大小、种子文件的平均大小等因素，没有将种子执行路径与控制流图相结合来考虑种子的能量分配，并且没有考虑种子的突变有效性，导致变异潜力大的种子能量分配不足或者变异潜力小的种子分配过多能量，影响模糊测试效率。

1 背景

由于本文的方法是在AFL 上实现的，因此本节首先介绍覆盖率引导的灰盒模糊测试的通用流程，然后对AFL的相关背景进行介绍。

1.1 覆盖率引导的灰盒模糊测试

覆盖率引导的模糊测试工具测试流程如图1所示。

图1 覆盖率引导的模糊测试工具基本流程

在模糊测试开始之前，需要将目标程序中每一个基本块进行插桩。然后将初始种子集和插桩后的目标程序送入模糊器进行测试。测试开始时，测试工具中只包含初始种子集，模糊测试工具按照种子选择策略进行种子选择。选取种子文件之后，会为选择的种子文件分配相应的能量，即变异的次数。然后种子进行变异生成大量测试用例，将生成的测试用例用于执行目标程序，并且跟踪目标程序的运行状态。根据目标程序的运行状态和测试用例的执行路径，来判断当前输入是否是有趣的测试用例，有趣的测试用例将被加入到种子队列，其它测试用例将被丢弃。当一个种子文件测试完成之后，继续从种子队列中选择下一个种子进行测试。模糊测试工具按照上述流程循环进行测试，直到到达规定的时间或者接收到停止指令。

1.2 AFL介绍

在覆盖率引导的模糊测试工具中，AFL 是最具代表性的一款模糊测试工具。近年来，大量的模糊测试工具都在AFL 的基础上进行改进，如Fairfuzz、FuzzFactory等。AFL 使用了大量的系统底层编程技巧，提高了测试过程的执行效率，并且AFL 使用了边覆盖作为代码覆盖率的度量方式。相较于基本块作为代码覆盖率的度量方式，边覆盖方式能记录更加丰富的程序执行信息，更容易发现目标程序的潜在漏洞。

在模糊测试开始之前，AFL 首先会插桩编译目标程序。插桩是指向目标程序的每一个基本块中插入一段桩代码用于记录相关信息。具体过程如下：

其中cur_block 和pre_block 分别代表当前基本块和前一个基本块的ID。基本块的桩代码中包含一个0-65535 的随机值，表示每个基本块的ID。当测试用例的执行路径从一个基本块跳转另一个基本块时，会将这两个基本块的ID 进行异或得到一个哈希值，这个哈希值就表示这两个基本块之间的边。为了区分两个基本块的执行顺序，AFL 在计算当前边的哈希值时会对前一个基本块的标识值右移一位。vergin_map 是一个64KB 长度的共享内存。它由模糊测试主程序和目标程序共享，模糊测试主程序能够通过共享内存及时获取目标程序执行过程中的相关信息。AFL只需将vergin_map中的信息与测试用例执行路径信息进行比对，就能知道当前测试用例是否有新的边覆盖。如果有新的边覆盖产生则将该测试用例添加到种子队列，如果没有新的边覆盖则将该测试用例丢弃。

2 方法

本文通过变异潜力适应度函数和突变有效性能量回收算法来进行种子的能量分配与回收，提高模糊测试效率。

2.1 变异潜力适应度函数

变异潜力适应度函数用来衡量种子文件变异潜力，本文将根据种子的变异潜力为种子分配能量。根据实验和漏洞挖掘经验，本文总结出两条模糊测试过程中的启发式规则。

（1）启发式规则1。如果一个种子的执行路径上有更多未探索邻边，那么这条路径上的突变更可能会带来新的边覆盖。

（2）启发式规则2。如果一个种子的执行路径上有更多新探索的边，那么这条路径上的突变更可能会带来新的边覆盖。

根据上述启发式规则，定义种子变异潜力适应度函数如公式（1）所示。

其中，表示种子执行路径上所有未探索邻边的和，表示种子执行路径上所有的邻边之和。表示执行路径上发现的新边数量，即执行路径上执行次数为1 的边的数量，表示种子执行路径上总的边数量。

图2表示程序的控制流图，下面使用图中的实例解释基于变异潜力的适应度的计算方法。假设有a1、a2、a3 三个种子，它们的执行路径按照顺序分别为a-g-n-l-j-k-m、a-g-h-i-j-km 和a-b-c-d-k-m。a1 执行路径上新发现的边为g-n、n-l、l-j。a2 执行路径上新发现的边为g-h、h-i、i-j。a3 执行路径上新发现的边为ab、b-c、c-d、d-k。由此，可以得到三个种子的变异潜力的种子适应度。

图2 变异潜力适应度计算

2.2 基于变异潜力适应度的能量分配

将AFL 给种子分配的能量表示为energy（），factor表示基于变异潜力适应度的能量调节因子，取值范围为［1，16］。energy（）表示最终种子获得的能量，其计算方式如公式（2）所示。

2.3 基于突变有效性的能量回收

能量回收算法回收变异效率低下的种子文件的剩余能量，将变异机会分配给队列中其他种子，提高模糊测试效率。

种子突变有效性定义为突变产生的有趣测试用例数除以种子突变产生的测试用例总数，计算方式如公式（4）所示。

由于模糊测试工具在一开始很容易生成有趣的测试用例，但随着时间的推移新路径的发现越来越困难，导致了生成有趣测试用例的难度增加。通过以往的模糊测试经验发现AFL 路径发现速度的倒数基本上随测试时间呈指数增长，所以通过补偿权重compen 对后续测试的种子突变有效性进行补偿。compen 的计算方式如公式（5）所示，取值范围为［1，64］。

其中，表示当前模糊测试的执行时间，单位为分钟，是系数，可以根据不同的应用程序进行设置，本文默认为1。

补偿之后种子突变有效性计算方式如公式（6）所示。

当前测试过程中已经进行模糊测试的种子的平均突变有效性则通过公式（7）进行计算。

基于突变有效性的能量回收方法如算法1所示：

能量回收算法

算法1的执行流程如下。

（1）首先通过calculateEnergy 函数按照公式（2）为种子分配能量energy。

（2）当前种子消耗的能量达到energy 的75%时，通过getAverEffect 函数按照公式（7）计算当前已经进行过测试的种子的平均突变有效性。通过getCurEffect函数按照公式（6）计算当前种子的突变有效性。

（3）如果当前种子的突变有效性大于总体平均突变有效性，即curEffect＞averEffect。表示当前种子有较大的突变价值，需要继续测试。

（4）如果当前种子的突变有效性小于等于总体平均突变有效性，即curEffect≤averEffect。表示当前种子突变价值不足，则直接跳过当前种子，减少不必要的能量消耗。

2.4 系统总体流程

本文模糊测试系统中能量调度优化总体流程如图3所示，整个系统的工作步骤如下。

图3 能量调度优化总体流程

（1）首先根据种子选择策略选取用于测试的种子文件，然后根据选择的种子采集变异潜力适应度函数所需的相关信息，再进行变异潜力适应度计算。

（2）将变异潜力适应度与AFL 原有的能量公式结合，根据公式（2）计算种子能量。

（3）分配能量后，将能量回收算法与能量消耗过程相结合，防止种子在探索具有复杂约束条件的程序分支的过程中产生过多的无效变异，影响测试效率。

（4）若没有收到停止测试指令，则跳转到步骤（1）。

3 实验及分析

本文在AFL 2.52b 的基础上实现了模糊测试工具EnFuzzer，使用EnFuzzer 与AFL 2.52b 进行了对比实验。本实验的运行环境为64 位Ubuntu16.04 操作系统，内存为4 GB，CPU 为AMD Ryzen 5-4600G。每个程序每次运行时间为24 小时，测试结果取5 次测试的平均值。选取了xmllint、cxxfilt、swftophp、objdump、nm-new这5个程序作为实验对象。

针对这5个目标程序，对应的实验结果如表1所示。

表1 实验结果对比及参数信息

实验结果表明，EnFuzzer 在这5个目标程序上的路径发现数量和崩溃发现数量相较于AFL都有一定的提升。其中，对于xmllint 总路径数量提升了32.36%， 独特崩溃数量提升了39.06%；对于cxxfilt 总路径数量提升了19.20%，独特崩溃数量提升了19.75%；对于swftophp 总路径数量提升了15.47%，独特崩溃数量提升了26.60%；对于objdump 总路径数量提升了9.53%，独特崩溃数量提升了6.67%；对于nmnew 总路径数量提升了18.40%，独特崩溃数量提升了66.66%。总体来说，Enfuzzer 能提高灰盒模糊测试的路径发现数量和独特崩溃数量，证明了本文方法的有效性。

4 结语

灰盒模糊测试是当前最为流行的漏洞挖掘方法。针对AFL 模糊测试工具能量分配不合理的问题，本文提出基于变异潜力适应度函数的能量分配策略和基于突变有效性的能量回收算法，并基于该方法实现了EnFuzzer。实验结果表明本文所提方法具有一定的有效性。在下一步的研究中，将考虑与污点分析、符号执行等技术相结合，对模糊测试变异策略进行改进，降低随机变异的盲目性，提升灰盒模糊测试工具的漏洞检测能力。