Mopt: Optimized Mutation Scheduling For Fuzzers（2019）

本文主要是介绍Mopt: Optimized Mutation Scheduling For Fuzzers（2019），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

摘要：

背景知识：

1.模糊测试的工作流程包括：

2.突变调度器

3. 变异操作符：

4.从前的突变调度器的局限性

4.模糊器AFL的突变调度选择：

PSO粒子群优化算法：

MOPT主框架：

PSO初始化模块：

Pilot Fuzzing Module：目标是找到效率最高的群

核心 Fuzzing模块

PSO更新模块

Pacemaker Fuzzing Mode：加速PSO的收敛速度

摘要：

近年来已经提出了许多新解决方案，包括改进种子生成，改进种子选择策略，改进测试速度和代码覆盖，以及将其他技术集成到模糊测试中。
然而，较少关注如何突变测试用例以生成新的有效测试用例。

1.提出突变调度策略MOPT，以改进传统的Mutation-based fuzzing 通常遵循特定的分布来选择变异操作符，在寻找通用程序的漏洞时效率不高的现状。

2.mopt寻找操作符最佳概率分布的原理：MOPT使用定制的粒子群优化算法（PSO）来寻找与模糊效果相关的操作符的最佳选择概率分布，并提供一个节拍器模糊模式来加速PSO的收敛速度。

3.作者将MOPT应用到最先进的模糊器AFL、AFLFast和VUzzer上，分别实现了MOPT-AFL、MOPT-AFLFast和MOPT-VUzzer，并在13个真实世界的开源程序上进行了评估。广泛的评估还表明，MOPT在合理性、兼容性和稳定性方面表现良好，同时引入的代价可以忽略不计。

背景知识：

1.模糊测试的工作流程包括：

维护一个测试用例队列，从队列中选择测试用例，对这些测试用例进行变异，使用新产生的测试用例测试目标程序，并根据需要报告漏洞或更新种子队列，本文主要关注变异阶段

2.突变调度器

在模糊测试过程中，它们使用某些突变调度器从预定义的操作符集合中选择操作符，以突变测试用例并生成新的用于模糊测试的测试用例。
突变调度器不是直接产生一个突变操作符，而是产生预定义操作符的概率分布，模糊器将遵循这个分布选择操作符。

3. 变异操作符：

定义了在哪里进行变异（如哪些字节）和如何进行变异（如添加、删除或替换字节）。

4.从前的突变调度器的局限性

它们没有考虑到：

（1）不同操作符的效率存在差异：不同的突变操作符在找到崩溃和路径方面具有不同的效率。

使用均匀分布选择突变操作符的模糊器可能会在不高效的操作符上浪费不必要的计算资源

（2）操作符的效率与目标程序有关：每个操作符的效率都是程序依赖的，并且很难或至少难以静态推断这种依赖关系。但是最优的突变调度器必须根据每个操作符在目标程序上的运行时效率做出决策。

（3）操作符的效率随时间变化：在当前测试用例上表现良好的操作符在极端情况下可能在接下来的测试用例上表现较差。最优的突变调度器依赖于操作符的历史效率来计算选择操作符的最佳概率分布。

4.模糊器AFL的突变调度选择：

（1）AFL采用了三种不同的调度方案，分别在确定性阶段、混沌阶段和拼接阶段使用，以不同的方式选择和变异测试用例，以适应不同阶段的模糊测试需求。

（2）确定性阶段调度器：用于首次选择的种子测试用例，使用6种确定性变异操作符依次处理。

（3）混沌阶段调度器：是AFL的主要变异调度方案，它首先决定在这个阶段生成的新测试用例的数量，然后随机选择一系列变异操作符生成新的测试用例。

（4）拼接阶段调度器：在某些情况下，经过前两个阶段对所有种子处理后，未能发现任何独特的崩溃或路径时使用。这个阶段只使用一个操作符交叉来生成新的测试用例，然后这些新的测试用例会送入混沌阶段调度器，而不是直接测试程序，以生成新的测试用例。

（5）第一阶段的调度器是确定性的且较慢，而最后一个阶段的调度器很少使用。混沌阶段的调度器更为通用，已被许多模糊测试器广泛采用。

PSO粒子群优化算法：

MOPT对每个算子使用一个粒子，并尝试在预定义的概率空间 [xmin,xmax]中探索每个算子的最优位置，其中 0 < xmin < xmax≤ 1。

xnow：一个粒子 (即算子 )在概率空间中的当前位置，表示该算子将被调度程序选择的概率。

MOPT采用多个蜂群「与原始的 PSO有多个粒子探索解空间不同，MOPT定义的群体实际上只在解空间中探索一个候选解 (即概率分布 )，因此可能陷入局部最优。为了避免局部最优， MOPT 采用了多个群体，并对每个群体使用定制的 PSO算法。」在模糊测试期间，在 PSO的每次迭代中执行以下三个额外的任务。

T1:定位每个群中所有粒子的局部最佳位置。在每个蜂群中，在模糊过程中评估一次迭代中每个粒子的局部效率 effnow。对于每个粒子，将历史上效率 effbest最高的位置标记为其局部最佳位置 Lbest。

T2:定位整个群中所有粒子的全局最佳位置。每个

粒子的全局效率 global eff 跨群评估。然后评估粒子的全局效率分布。将每个粒子的 global ef在该分布中的比例用作其全局最佳位置 Gbest。

T3:选择最佳蜂群来引导模糊测试。评估每个群体在一次迭代中的效率 swarmeff（将群体的效率 (swarme ff)定义为该群体贡献的有趣测试用例的数量除以一次迭代期间新测试用例的数量。）

选择 swarmeff最高的群体，并将其在当前迭代中的概率分布应用于进一步的模糊化。然后，在每次迭代结束时， MOPT以与 PSO相似的

方式移动每个群体中的粒子。更具体地说，对于一个粒子 Pj在一个群 Si 中我们更新它的位置如下。

MOPT主框架：

MOPT由四个核心模块组成，PSO 初始化和更新模块，先导模糊和核心模糊模块。

初始化模块执行一次，用于设置 PSO算法的初始参数。其他三个模块形成一个迭代循环，共同工作，连续模糊目标程序。

PSO初始化模块：

MOPT

(1)将每个群中每个粒子的初始位置 xnow设为随机值，并将一个群中所有粒子的和 xnow 归一化为 1;

(2)将每一群中每个粒子的粒子运动位移 vnow设为 0.1;

(3)将每个群中每个粒子的初始低效率 effnow设为 0;

(4)将每个群中每个粒子的初始局部最佳位置 Lbest设为 0.5;

(5)将每个粒子跨群的初始全局最佳位置 Gbest设为 0.5。

Pilot Fuzzing Module：目标是找到效率最高的群

该模块采用多个蜂群来执行模糊测试，其中每个蜂群探索不同的概率分布。该模块按顺序评估每个群体，

并在它生成一个可配置的数量 (表示为 periodpilot )的新测试用例后停止测试群体。对特定群体进行模糊测试的过程

如下。

在模糊化过程中，该模块将测量三个测量值 :

(1)由特定粒子 (即算子 )贡献的有趣测试用例的数量，

(2)特定粒子的调用次数，

(3)通过仪器化目标程序，该群发现的有趣测试用例的数量。

每个粒子 (在当前群中 )的局部效率是第一次测量除以第二次测量。我们可以定位每个粒子的局部最佳位置。

当前群的效率是第三次测量除以测试用例计数 periodpilot。因此，我们可以找到效率最高的群体。

核心 Fuzzing模块

该模块将采用上一个 Pilot Fuzzing Module选择的最佳群，并

利用其概率分布进行模糊测试。它将在生成一个可配置的数量 (表示为 periodcore )的新测试用例 )后停止。

一旦它停止，我们可以测量从 PSO初始化开始到现在，每个粒子所贡献的感兴趣的测试用例的数量，而不管它属于哪个群。然后我们可以计算粒子之间的分布，并定位每个粒子的全局最佳位置。

PSO更新模块

根据飞行员和核心模糊模块提供的信息（得到的局部和全局效率），该模块根

据公式 3和 4更新每个群体中的粒子。

Pacemaker Fuzzing Mode：加速PSO的收敛速度

MOPT应用于基于突变的模糊器是通用的，并且我们意识到 MOPT的性能可以在应用于特定的模糊器 (如AFL)时进一步优化

在前面“模糊器AFL的突变调度选择”里面提到

「1）AFL采用了三种不同的调度方案，分别在确定性阶段、混沌阶段和拼接阶段使用，以不同的方式选择和变异测试用例，以适应不同阶段的模糊测试需求。

（2）确定性阶段调度器：用于首次选择的种子测试用例，使用6种确定性变异操作符依次处理。

（3）混沌阶段调度器：是AFL的主要变异调度方案，它首先决定在这个阶段生成的新测试用例的数量，然后随机选择一系列变异操作符生成新的测试用例。

（4）拼接阶段调度器：在某些情况下，经过前两个阶段对所有种子处理后，未能发现任何独特的崩溃或路径时使用。这个阶段只使用一个操作符交叉来生成新的测试用例，然后这些新的测试用例会送入混沌阶段调度器，而不是直接测试程序，以生成新的测试用例。

（5）第一阶段的调度器是确定性的且较慢，而最后一个阶段的调度器很少使用。混沌阶段的调度器更为通用，已被许多模糊测试器广泛采用。」