模糊测试器AFL种子变异策略优化研究

张琦 马莺姿

摘  要：AFL作为模糊测试领域最具有代表性的工具，使用至今已发现大量软件的内存漏洞。实验表明，AFL超过60%的变异操作不会产生任何新路径，这些变异都是无效的变异。文章对AFL种子变异策略进行分析，研究并提出了一种变异策略的优化算法。该算法通过在确定性变异阶段记录种子文件的有效字节数组，在随机性变异阶段判断要变异的字节是否为有效字节来进行选择性的变异。根据所提出的算法对AFL进行了优化，实验验证了该种子变异优化算法的有效性。

关键词：模糊测试;AFL;种子变异策略;错误检测

中图分类号：TP391;TP311        文献标识码：A文章编号：2096-4706（2021）24-0142-04

Abstract： As the most representative tool in the field of Fuzzing， AFL has found a large number of software memory vulnerabilities so far. Experiment results show that more than 60% of AFLs mutations will not find any new paths， and these mutations are invalid. The paper analyzes the AFL seed mutation strategy， studies and proposes an optimization algorithm for the mutation strategy. The algorithm performs selective mutation by recording the effective byte array of the seed file in the deterministic mutation stage， and judging whether the bytes to be mutated are valid bytes in the random mutation stage. According to the proposed algorithm， AFL is optimized， and the experiment verifies the effectiveness of the seed mutation optimization algorithm.

Keywords： Fuzzing; AFL; seed mutation strategy; error detection

0  引  言

随着社会不断发展，信息化给人类的衣、食、住、行等各个方面带来了极大的便利。计算机软件给社会带来便利的同時，也潜藏着一些安全问题。OpenSSL[1]本身是一个进行安全通信、可以保障通信保密性和可靠性的应用程序，然而，在2014年，OpenSSL被爆出“心脏滴血”重大漏洞，攻击者可以通过这一漏洞，获取应用程序源码、用户的网络访问请求和用户的cookie信息，甚至可以获取到用户的电子邮件、银行卡账号密码等，带来了无法估量的损失。为了保证软件的可靠性和信息的安全性，越来越多的技术关注于检测软件系统的内存安全性。

AFL[2-4]模糊测试器基本思想是将种子测试用例作为被测程序的输入，检测程序的执行过程并按照种子变异策略生成新的测试用例喂给被测程序，最终报告异常行为。其中种子变异策略是模糊测试器的关键核心，测试用例的生成质量，决定了模糊测试器的执行效率。实验表明，AFL在进行种子变异的时候，超过60%的变异操作不会产生任何新路径，这些变异都是无效的变异，提高种子变异的有效性是提升模糊测试效率的关键。

1  理论知识

1.1  AFL工作流程

AFL由前Google安全研究员lcamtuf开发的一款基于代码覆盖率的模糊测试工具，它通过记录输入的测试文件的代码覆盖率，从而调整输入样本以提高覆盖率。目标源程序经过插桩编译后生成插桩二进制文件，将初始种子文件输入到模糊器进行变异喂给插桩后的目标程序，挖掘程序中的漏洞。如图1所示，算法流程总结如下[5]：

（1）将用户提供的初始测试种子文件加载到输入队列中。

（2）从输入队列获取下一个测试文件。

（3）尝试将测试用例精简到最小尺寸，并且不改变程序的测试行为。

（4）使用一些传统模糊算法不断地变异文件。

（5）如果新产生的变异导致了新的状态转换，将变异的输出插入到队列中。

（6）重复步骤2。

1.2  AFL变异策略

AFL变异阶段最重要的任务就是对种子文件进行变异。AFL维护了一个输入队列，每次从输入队列中取出一个文件，对其进行大量变异，经过变异后的文件喂给目标程序执行，观察执行过程中是否引起程序崩溃、发现新路径等结果。对于发现新路径的文件会返回输入队列继续进行变异并一直持续下去。

AFL的变异策略主要包括确定性变异和随机变异[6]。其中确定性变异策略主要包括比特翻转、算术运算、特殊值替换和字典值，具体类型如下：

bitflip，按位翻转，1变为0，0变为1。这一阶段还会按照不同的长度和步长进行多种不同的翻转，每次翻转1/2/4/8/16/32 bit，依次进行。

arithmetic，整数加/减算术运算。跟bitflip类似，arithmetic根据目标大小的不同，也分为了多个子阶段，依次对8/16/32 bit进行加减运算。

interest，把一些特殊内容替换到原文件中。同样每次对8/16/32 bit进行替换。所谓的特殊内容是AFL预设的一些比较特殊的数，比如可能造成溢出的数。

dictionary，把自动生成或用户提供的字典值替换或插入到原测试用例中。

而随机变异策略主要包括havoc大破坏和文件拼接：

havoc，对文件进行大量的破坏，此阶段会对原文件进行大量随机变异。包括随机翻转、加减、替换和删除等操作。

splice，此阶段会将两个文件拼接起来得到一个新的文件，并对这个新文件继续执行havoc变异。

具体地，AFL在种子文件队列中随机选取一个，与当前的种子文件对比。如果两者差别不大，就再重新随机选一个;否则就随机选取位置进行拼接，产生新的文件。在这里，AFL还会过滤掉拼接文件未发生变化的情况。

2  种子变异优化算法

在AFL对种子文件进行变异的时候，除了确定性变异阶段，还伴随着随机变异阶段，通常，大量新路径都是在随机变异阶段发现的。但是由于随机havoc阶段的变异盲目随机，会导致大量无效的测试用例的生成，影响模糊测试效率[7]。因此，对havoc阶段变异策略的优化是本文的研究重点。

一般来说，二进制输入的种子文件通常具有一定的格式，分为“元数据”和“数据”两部分。比如可执行链接格式ELF对象文件，通常分为ELF头部，用来描述整个文件的组织，包括魔数、版本、类别、系统架构、程序头起点等信息。程序头部表提供系统创建进程映像的信息。节区头部表则描述了节区的名称，节区大小等信息。而节区部分则包含链接视图的数据、指令、符号表和重定位信息等。而段类似与节区，包含程序的代码段和数据段相关信息[8]。

为了减少随机变异阶段盲目的变异，提高模糊测试效率，本文提出一种思想来对随机变异阶段进行改进。其主要思想是：在对种子文件进行变异的时候，对其每个字节进行记录，如果该字节的变化（包括其中某些bit的翻转，字节的加减运算，字节的替换等）会引起新的路径变化，则将该字节标记为有效字节，如果该字节的变化不会引发新路径，则该字节是无效字节。那么在随机变异阶段，可以判断出对无效字节的变异往往不会有太大的效果。因此，通过在随机变异阶段判断字节是否为有效来决定是否对该字节进行变异，可以有效地提高种子文件的变异效率。

针对种子文件中不同字节对程序执行路径的影响，可以把执行相同路径的连续字节划分为同一输入域，对同一输入域中某些字节的变异可能不会导致目标程序执行路径的变化，比如分别改变某一输入域中的第一个字节和第二个字节时，程序的执行路径可能都会发生变化，但是这两种变异后新的执行路径可能为同一条，这种情况就不能同时把这两个字节都标识为有效字节。

如图2所示，图中属于同一个输入域的相邻字节被框在一起。当第0个字节发生变化时，目标程序没有产生新的执行路径，则将该字节标记为无效，即标记为0。而当第2个字节发生变化时，AFL检测到目标程序产生了新的执行路径，则将其对应的字节标记为1，代表着该字节是一个有效字节。需要注意，对应同一块输入域，比如图中的第2到5个字节属于同一个输入域，当分别单独对第2、3、4、5个字节进行变异后，相比于原来的种子文件，目标程序都产生了新的执行路径，但是我们还需要判断产生的新执行路径是否为同一条，因为同一块输入域的中字节的变化产生的路径往往是相同的。对于这种情况，需要做如下简单的判断：如果改变了某一字节引起了新的路径变化，并且该路径与改变其前一个字节引发的路径不同，才将这个字节标记为有效字节。

当对种子文件的所有字节都进行单独变异后，我们就可以根据变异结果对所有字节进行标识。随后在对种子文件进行havoc随机变异阶段，AFL会随机选取种子文件中的某些位置，对该位置的字節进行某些变异操作，充满了随机性。改进后的种子变异策略在havoc阶段首先根据标识结果对要进行变异的字节判断是否为有效字节，如果是有效字节，则进行该次变异，否则跳过该字节，减少变异次数和目标程序的执行次数。

3  对AFL的改进

根据上述的优化思路，需要对AFL的代码进行改进。首先，在AFL的种子变异的方法中定义一个长度等于输入种子文件字节长度的unsigned char类型数组shadow_map用来标识种子文件对应字节是否为有效字节。shadow_map[i]为1表示测试用例的第i个字节为有效字节。为了给shadow_map赋值，我们需要单独遍历种子文件的每个字节并对其进行变异，来判断该字节是否会产生新的执行路径。

这里采用的方法是利用确定性变异阶段的字节翻转变异策略，即bitflip 8/8。该阶段是依次对每个字节进行翻转，判断是否会产生新的路径。同时，为了避免输入域产生相同路径的影响，我们还需要判断前一个字节的变化和当前字节的变化是否会导致同一新路径。

AFL中使用trace_bits字节数组记录分支信息的执行次数，我们使用哈希函数计算trace_bits的哈希值，通过比较种子文件变异前后的哈希值来比较执行路径是否发生了变化。在测试用例的数据结构中存储该用例未进行变异之前的trace_bits的哈希值exec_cksum，使用临时变量记录前一个字节trace_bits的哈希值pre_cksum。在对当前字节进行改变后的用例执行完目标程序后，计算当前trace_bits的哈希值cksum，当cksum不等于exec_cksum且cksum不等于pre_cksum时，我们将当前字节对应的shadow_map标识为1。

当执行完flipbit 8/8阶段后，整个测试用例的所有字节对应的shadow_map标识完成。在随后的havoc随机变异阶段，先判断要变异的字节是否为有效字节，来减少无效测试用例的生成。具体改进后的变异算法如表1改进后的种子变异策略所示。

4  实验与分析

使用AFL模糊测试器对程序进行模糊测试的命令为：

afl-fuzz -i in/ -o out/ -- /path/to/fuzz_app [option]

其中in为输入的种子文件夹，out为输出文件夹，包括了崩溃信息、种子队列信息等，-- 后指定要进行模糊测试的程序。常用的afl-fuzz命令如表2所示。

由于本文对AFL变异策略的优化针对的是二进制文件中的每一个字节进行有效性记录，在随机变异阶段对字节进行改变时首先判断该字节的有效性，对于无效字节则不进行变异，从而提高变异的效率。因此，该部分的实验针对的程序输入为二进制文件，我们对Mibench中几个输入为音频和图片的测试用例进行测试。由于模糊测试的随机性影响较大，因此本次实验对每一个测试用例分别使用原始的AFL模糊测试器和改进后的AFL各进行三次实验，每次实验进行一小时，然后取平均值，具体的测试结果如表3所示。

其中total paths表示总的执行路径，uniq crashes为找到的不同漏洞的个数。由于初始种子文件的大小对AFL的影响较大，因此表格中不同的测试用例的结果差异较大。比如对于ghostscript来说，由于种子文件所占字节较多，在对初始种子进行确定性变异阶段执行的过程较久，而优化前后的AFL测试器对确定性变异阶段没有影响，而随机变异阶段在较大种子测试用例中所占的比重较轻，因此相较于其他的测试软件，优化后的AFL相比于原始AFL所执行到的路径提升较小。而对于大多数的测试软件，改进后的AFL模糊测试器所能执行到的路径可以提升10%至20%以上。同样从测试结果中可以看出，使用改进后变异策略的AFL对同一测试用例进行同样时间的模糊测试，往往能够发生更多的崩溃。

5  结  论

本文介绍了AFL对种子文件进行模糊测试的相关变异策略，分析了随机变异阶段的缺陷，针对随机变异阶段的有效测试用例生成效率低的问题，提出了相应的解决方案：即在确定性变异阶段通过记录每个字节对变异的有效性，指导后续随机变异，以提高AFL测试用例的生成效率。在未来的工作中，我们会继续研究其他形式输入的模糊测试项目，比如字符串文本输入，提高该类型的种子变异效率。

参考文献：

[1] VIEGA J， MESSIER M， CHANDRA P. Network security with openSSL：cryptography for secure communications [M].[S.I.]：OReilly Media，2002.

[2] CORDY J R. The TXL source transformation language [J].Science of Computer Programming，2006，61（3）：190-210.

[3] BHARDWAJ M，BAWA S. Fuzz testing in stack-based buffer overflow [EB/OL].[2021-11-01].https：//link.springer.com/chapter/10.1007/978-981-13-0341-8_3.

[4] LIANG J，WANG M Z，CHEN Y L，et al. Fuzz testing in practice：Obstacles and solutions [C]//2018 IEEE 25th International Conference on Software Analysis，Evolution and Reengineering（SANER）.Campobasso：IEEE，2018：562-566.

[5] 任澤众，郑晗，张嘉元，等.模糊测试技术综述 [J].计算机研究与发展，2021，58（5）：944-963.

[6] 李明磊，陆余良，黄晖，等.模糊测试变异算子调度优化模型 [J].小型微型计算机系统，2021，42（10）：2190-2195.

[7] WANG H J，XIE X F，LI Y，et al. Typestate-guided fuzzer for discovering use-after-free vulnerabilities [C]//2020 IEEE/ACM 42nd International Conference on Software Engineering（ICSE）.Seoul：IEEE，2020：999-1010.

[8] YOU W，WANG X Q，MA S Q，et al. Profuzzer：On-the-fly input type probing for better zero-day vulnerability discovery [C]//2019 IEEE Symposium on Security and Privacy（SP）.San Francisco：IEEE，2019：769-786.

作者简介：张琦（1992—），男，汉族，江苏连云港人，硕士生导师，硕士研究生，研究方向：软件工程、软件运行时验证;马莺姿（1996—），女，汉族，山东淄博人，硕士研究生在读，研究方向：软件工程、软件验证。