MOpt: Optimized Mutation Scheduling for Fuzzers
一．论文介绍及研究背景
1.1论文信息
论文题目：MOpt: Optimized Mutation Scheduling for Fuzzers
作者：Chenyang Lyu, Zhejiang University;
Shouling Ji, Zhejiang University & Alibaba-Zhejiang University Joint Research Institute of Frontier Technologies;
Chao Zhang, BNRist & INSC, Tsinghua University;
Yuwei Li, Zhejiang University;
Wei-Han Lee, IBM Research;
Yu Song, Zhejiang University;
Raheem Beyah, Georgia Institute of Technology
论文链接https://www.usenix.org/conference/usenixsecurity19/presentation/lyu
这篇论文被列入了《纽约时报》的议事录第 28 届 USENIX 安全研讨会。
时间地点：2019 年 8 月 14 日至 16 日·美国加利福尼亚州圣克拉拉
1.2 论文内容
本文提出了一种新的突变调度方案 MOPT，使基于突变的模糊器能够更有效地发现漏洞。MOPT 利用自定义粒子群优化(PSO)算法来寻找算子在引信有效性方面的最优选择概率分布，并提供起搏器引信模式来加速 PSO 的收敛速度。解决了现有的模糊器通常遵循特定的分布来选择突变算子，寻找一般程序的漏洞方面效率低下的问题。
1.3 研究背景
1.3.1基于突变的 Fuzzing
基于突变的模糊处理善于发现漏洞，而不利用目标程序的先验知识。 相反，它通过以某些方式变异一些格式良好的种子测试用例来生成新的测试用例。
基于突变的引信一般工作流程如下：
（1）维护种子测试用例队列，可以在运行时更新；
（2）按一定顺序从队列中选择一些种子；
（3）以各种方式变异种子；
（4）用新生成的测试用例测试目标程序，并报告漏洞或在必要时更新种子队列；
（5）最后再回到步骤(2）。
本文主要研究突变阶段（即步骤(3)）
1.3.2 变异算子
基于突变的模糊子可以以无限多的方式变异种子。 考虑到性能和可用性，在实践中，这些模糊器，包括 AFL 及其后代，通常预先定义一组突变算子，并选择其中一些在运行时突变种子。 这些突变运算符描述了在哪里突变（例如，哪个字节)和如何突变(例如，添加、删除或替换字节）。
1.3.3突变计划
在 AFL 的三个阶段中使用的三种突变调度方案，如下图：
- 确定性阶段调度器： AFL 对首次选择变异的种子测试用例应用确定性调度方案。 该调度器按顺序使用 6 种确定性类型的突变算子，并将它们逐一应用于种子测试用例。
- havoc 阶段调度器：在大破坏阶段采用 AFL 的主要突变调度方案。
AFL 首先决定数字，表示为 Rt 在这个阶段生成新的测试用例。 每次AFL 选择一系列遵循均匀分布的 Ro 突变算子，并将它们应用于种子上生成一个测试用例。破坏阶段结束后，Rt 新的测试用例已经产生。
3. 拼接阶段调度器： 在一些罕见的情况下，AFL 工作通过上述两个阶段的所有种子，但未能发现任何独特的崩溃或路径在一轮。 然后 AFL 将进入特殊的拼接阶段，在这个阶段，AFL 只使用一个操作符交叉来生成新的测试用例。 这些新的测试用例将被输入到破坏阶段调度程序，而不是正在测试的程序，以生成新的测试用例。
1.3.4变异效率
不同的突变算子的工作方式截然不同。一个直观的假设是，它们在不同的目标程序上有不同的效率。测量了 12 个突变算子在确定性阶段产生测试用例。 结果如图所示：
在确定性阶段，突变算子的顺序和选择的时间是固定的。下图显示了顺序和操作符在引信 avconv 期间被 AFL 选择的时间，指示引信花费的时间。
二．MOPT 概述
2.1设计思路
突变调度器旨在为给定的运行时上下文选择下一个最优突变算子，该算子可以找到更有趣的测试用例。 我们将这个问题简化为寻找突变算子的最优概率分布，然后调度器在测试目标程序时选择下一个算子。 寻找所有突变算子的最优概率分布是具有挑战性的。相反，我们可以首先让每个算子探索自己的最优概率。 然后，基于这些最优概率，我们可以得到突变算子的全局最优概率分布。
2.2粒子群优化(PSO)
粒子群算法是由 Eberhart 和 Kennedy 提出的，旨在寻找问题的最优解。
它采用多个粒子迭代搜索解空间，其中一个位置是候选解。
在每次迭代中，每个粒子被移动到一个新的位置 xnow，基于（1）它的惯性(即，先前的运动 now )，（2）位移到它的局部最佳位置 Lest，到目前为止这个粒子已经发现，（3）位移到全球最佳位置 Gest， 到目前为止所有粒子已经发现。 具体地，粒子 P 的运动计算如下：
每个粒子都向 Lest 和 Gest 移动，并且可能继续移动到更好的位置。通过向 Gest 移动，多个粒子可以同步工作，避免陷入局部最优。 因此，群将被引导到最优解。 此外，PSO 易于实现，计算量小，是优化突变调度的一个很好的方法。
2.3设计细节
MOPT 旨在找到最优的概率分布。首先探索每个算子的最优概率，然后构造最优概率分布。
2.3.1粒子
每个算子都使用一个粒子，并试图在预定义的概率空间[x]中为每个算子探索一个最佳位置 m在Xmax，粒子（即算子）在概率空间中的当前位置，即 Xnow，表 示调度程序将选择该算子的概率。 由于概率的性质，一次迭代中所有粒子概率的和都应该归一化为 1。
2.3.2当地最佳位置最佳
对于给定的粒子，Lest 是粒子的位置，其中相应的运算符产生测试用例（给定相同数量的调用）。 为了进行这种比较，对于每个粒子（即算子），我们测量了它的局部效率，即这个算子贡献的测试用例的数量除以这个算子在一次迭代中的调用次数。 我们把最大的 effnow 表示为 effbest。 因此，Lest 是操作者在历史上获得有效的位置。
2.3.3全球最佳位置
测量了到目前为止在所有群中每个操作符贡献的测试用例的数量，并将其用作粒子的全局效率 globaleff。 然后计算所有粒子的全局效率分布。 对于每个算子（即粒子），它的全局最佳位置 Gbest 被定义为它的 globaleff 在这个分布中的比例。 通过这种分布，效率较高的粒子（即算子）可以获得更高的概率被选择。
2.3.4群
MOPT 使用多个群，并将定制的 PSO 算法应用于每个群。在引信期间，执行以下三项额外任务
在 PSO 的每次迭代中。
• 找到每个群体中所有粒子的局部最佳位置。
• T2：定位所有粒子在群中的最佳位置。每个粒子的全局效率全局 eFF 是跨群评估的。 然后对粒子的全局效率分布进行了评价。
• 选择最好的蜂群来引导引信。在一次迭代中对每个群的效率进行了评估。 选择具有最高 swarmef 的群，并将其在当前迭代中的概率分布应用于进一步的模糊化，然后，在每次迭代结束时，MOPT 以类似于 PSO 的方式移 动每个群中的粒子。
三．执行MOPT
3.1主要框架
3.2具体框架
3.2.1 PSO 初始化模块
（1）将每个粒子在每个群中的初始位置 Xnow 设置为一个随机值，并将 x 的和归一化在一个群中的所有粒子中；
（2）将每个粒子在每个群中的粒子运动 VNow的位移设置为 0.1；
（3）将每个粒子在每个群中的初始局部效率 efnow 设置为 0；
（4）设置初始局部最佳位置 每个群中的每个粒子到 0.5；
（5）将每个粒子跨群的初始全局最佳位置 Gest 设置为 0.5。注意，初始化模块只在 fuzzer 开始运行时执行一次。
3.2.2 先导模糊模块
该模块使用多个群集执行模糊，其中每个群集探索不同的概率分布。 该模块按顺序计算每个群，并在生成新测试用例的可配置数量（表示为周期导航）后停止测试一个群。 用特定的蜂群进行引信的过程如下。 在引信过程中，该模块将测量三个测量：（1) 特定粒子(即算子)贡献的有趣测试用例的数量；
(2)特定粒子的调用数量；
(3）通过对目标程序进行仪器化，测量该群体发现的测试用例的数量。
每个粒子的局部效率（在电流群中）是第一次测量除以第二次测量。因此，我们可以定位每个粒子的局部最佳位置。电流群的效率是第三次测量除以测试用例计数周期。 因此，我们可以找到最有效的群体。
3.2.3核心模糊模块
该模块将采用最佳群，并利用其概率分布进行引信。它将在生成新测试用例的可配置数字后停止。一旦它停止，我们可以测量每个粒子贡献的测试用例的数量，而不管它属于哪个群，从 PSO 初始化开始到现在，我们可以计算粒子之间的分布，并定位每个粒子的全局最佳位置。
3.2.4PSO 更新模块
该模块按照方程更新每个群中的粒子，更新每个粒子后，我们将进入 PSO 更新的下一次迭代。因此，我们可以接近一个最优群（即算子的概率分布），使用它来指导核心引信模块，并帮助提高引信效率。
四．实验
4.1实验环境
我们论文中使用的 AFL 版本是 2.52b。我们将 MOPT 应用于 AFL 的 破 坏 阶 段 ， 并 实 现 MOPT-AFL-tmp 和 MOPT-AFL-ever 的原型，其中-tmp 和-ever 表示上一节中讨论的相应的起搏器模糊模式。 在 C 中实现 MOPT 的核心功能平台。
所有实验都运行在一个虚拟机上，该虚拟机配置了1 个 CPU 核心 2.40GHz、E5-2640、V4、4.5GB RAM 和 64 位 Ubuntu16.04LTS 的操作系统。