前言
本文根据英文原文“EMS: History-Driven Mutation for Coverage-based Fuzzing.”整理撰写。原文发表在The Network and Distributed System Security Symposium. 2022. 作者是Chenyang Lyu, Shouling Ji, Xuhong Zhang, Hong Liang, Binbin Zhao, Kangjie Lu, Raheem Beyah。本文较原文有所删减，详细内容可参考原文。
01 背景介绍
基于变异的模糊测试在软件测试领域得到了广泛应用。它通过随机选择变异算子对种子文件进行变异来不断生成新的测试用例，并将生成的测试样例作为输入执行目标程序，从而实现自动化的漏洞挖掘。
近年来，科研人员提出了多种模糊测试的改进方案。从能量分配和种子调度的角度，EcoFuzz借助定制化的多臂赌博机模型实现了自适应能量调度机制，在有限的执行次数内实现了路径覆盖率的最大化，TortoiseFuzz则从函数级、代码结构级、基本块级三个维度对种子触发内存操作数进行评估，实现了更细粒度、更多层次的种子调度分配机制。从提高复杂路径约束求解能力的角度，QSYM、Angora、GREYONE等工具则利用符号执行、污点分析、梯度下降等技术来缓解魔数、校验和等传统变异难以突破的分支覆盖问题。从工具实现和优化角度，CollAFL、UnTracer则以获取反馈信息的插桩模块入手，避免了哈希碰撞和无效插桩引起的性能降低，提高了路径探索和漏洞检测的效率。
虽然现有的模糊测试工具种类丰富、各具特色，但并没有考虑到历史数据对后续模糊测试的贡献问题，缺乏对高效变异策略的提取和复用机制。一方面，同一程序的不同执行路径可能包含相同的函数调用或相似的路径约束，测试过程中积累的触发特定分支行为的变异策略对其他路径的探索亦有助益；另一方面，随着开源社区的蓬勃发展，开源代码框架和库的使用在程序开发中屡见不鲜，比如，近十分之一的IoT 固件镜像都使用相同的开源库 BusyBox。因此，相似的代码逻辑在不同程序中经常重复使用，这为跨程序的高效变异策略复用提供了可能。由此观之，模糊测试历史中包含着丰富的高效变异策略，如果能够学习并充分利用这些策略，势必可以显著提高模糊测试的性能。为了验证上述观察的可靠性，我们对多个目标程序进行了立即数和共享代码两项案例分析。
1.立即数分析
程序cmp指令中的立即数与路径约束密切相关，直接控制着程序的分支行为。因此，我们对pdfimages、objdump、nasm三个目标程序的汇编代码进行了分析，研究了汇编指令中cmp指令立即数种类及其使用次数情况，实验结果如表1.1所示。
表 1.1: 汇编指令cmp中包含的立即数种类及其使用次数统计表
由表可知，立即数往往多次影响程序的控制流和数据流行为。比如，在objdump中，重复出现的立即数数量是单次出现立即数数量的1.36倍，而且重复出现的立即数使用总数也明显高于单次出现的立即数。
我们进一步统计分析了程序间相同立即数使用占比，即相同立即数使用次数除以各自所有立即数的使用次数。由于不同程序中存在很多例如0，1等通用的立即数，我们统计了含通用立即数和不含通用立即数两种情况下的统计结果，如图1.1所示。其中，通用立即数的判定以模糊测试工具预设的“interesting value”为标准。
图 1.1: 相同立即数的使用次数百分比统计图
由图可知，程序间相同立即数使用比例很高。其中，pdfimages和nasm中相同立即数的使用次数占pdfimages总使用次数比例高达82.9%。如果将通用立即数计入实验结果，则所有分析中相同立即数的使用比例均达79.9%以上。
2. 共享代码分析
同一供应商提供的不同程序之间存在共享代码，相同的高效变异策略可以触发它们相似的分支行为。因此，我们使用MOPT对xpdf-4.02和binutils-2.28中的pdfimages、pdftotext、pdfinfo、objdump、addr2line和objcopy六个程序进行了长达5小时的测试，统计分析了各程序触发的执行路径中包含的基本块和共享基本块的数量，实验结果如图1.2所示。
由图可知，同一厂商不同程序的共享基本块所占比例很高。例如，在pdfimages和 pdftotext的共享基本块共计7128个，比例高达85.05%和86.00%。共享基本块的重复使用为不同程序的模糊测试历史积累高效变异策略、求解相同路径约束提供了可能。
图 1.2: 共享基本块数量统计图
基于上述分析可知，许多高效变异策略可以从同一程序和不同程序的模糊测试实验数据中归纳提取。然而，现有的模糊测试工具并没有考虑到历史数据的利用问题，如何实现程序间和程序内历史数据的高效复用有待探索。
02
历史数据驱动的模糊测试变异框架EMS
为了实现程序间和程序内模糊测试历史中高效变异策略的学习和复用，我们提出了概率字节定向模型（PBOM），并基于此设计了历史数据驱动的模糊测试变异框架EMS，实现框架如图2.1所示。
图 2.1: EMS实现框架图
EMS旨在利用历史数据中的高效变异策略，根据给定来自种子文件的输入字节值，选择对应的有效策略来实施变异，改变输入字节值生成新的测试样例，从而提高模糊测试工具的路径和崩溃探索能力。整体上，EMS由Inter-PBOM初始化、PBOM算子构建、变异算子分析和数据收集、Intra-PBOM更新四个模块组成，构造了Inter－和Intra-PBOM来实现程序内和程序间的历史数据收集和复用，新增了PBOM算子来实现高效变异策略的应用。同时，EMS利用变异算子分析和数据收集模块来持续地收集测试过程中新积累的历史记录，并基于此定期调用Intra-PBOM更新模块进行模型更新。
1.Inter-PBOM初始化模块
为了实现程序间高效变异策略的复用，EMS在模糊测试启动开始时使用Inter-PBOM初始化模块，读取高效变异操作集合，将输入字节值与有效输出变异策略配对，并对其分配合适的选择概率。具体地，EMS读取程序间高效变异操作集合，分析变异操作类型、变异前字节值与变异后字节值，将变异操作类型与变异前的字节值作为输入值，变异后的字节值作为输出值，训练Inter-PBOM概率模型。
2.PBOM算子构建模块
EMS通过Inter-和Intra-PBOM模型分别实现了程序间和程序内高效变异策略的学习，然后调用PBOM算子使得积累的策略发挥作用。EMS将积累的高效变异策略新增为PBOM算子，将种子文件的输入字节值与变异类型作为输入，基于概率选择对应的输出字节值，并使用输出字节值对种子文件实施变异操作。
3.变异算子分析和数据收集模块
在变异种子文件过程中，EMS记录了每个变异操作的原始字节值、变异类型、变异后字节值、变异位置等信息。如果实施变异操作后，新生成的测试样例触发了目标程序的新执行路径或异常崩溃行为，EMS将其纳入到高效变异策略中，实现变异算子分析和数据收集的功能。
4. Intra-PBOM更新模块
在 Intra-PBOM更新模块，EMS根据变异算子分析和数据收集模块得到的试验内高效变异操作集合，对Intra-PBOM模型进行训练更新，增加新的变异策略并调整各高效变异策略的选择概率，从而实现模糊测试过程中概率模型自适应的实时优化，提高测试过程中高效变异策略的利用率。
（本文只选取原文中部分章节，更多精彩内容敬请期待后续出版的《网络安全研究进展》）
作者简介
梁红，浙江大学21级在读博士生，主要研究方向为模糊测试，研究成果发表在NDSS和ISSTA。
