阅读笔记——《RapidFuzz: Accelerating fuzzing via Generative Adversarial Networks》

• 【参考文献】Ye A, Wang L, Zhao L, et al. Rapidfuzz: Accelerating fuzzing via generative adversarial networks[J]. Neurocomputing, 2021, 460: 195-204.
• 【注】本文仅为作者个人学习笔记，如有冒犯，请联系作者删除。

---

目录

摘要

一、介绍

二、相关工作

三、RapidFuzz

1、数据预处理

2、带有梯度惩罚的Wasserstein GAN (WGAN-GP、Wassertein Generative Adversarial Networks with Gradient Penalty) 

3、变异基因检测算法 (Mutation gene detection algorithm)

四、评估

1、评估指标

1.1、Mapsize

1.2、Code coverage

1.3、Favored rate

1.4、t-SNE

五、总结

---

摘要

• 本文实现了一个基于生成对抗网络 (GAN)的模糊器——RapidFuzz，来生成测试用例。它可以在相对较短的时间内精确捕获数据的结构特征。
  • 【注】生成对抗网络 (GAN)是一种深度学习模型，其核心思想是通过训练两个神经网络，一个生成器 (Generator)和一个判别器 (Discriminator)，彼此对抗地学习。生成器尝试生成与真实数据相似的数据，而判别器尝试区分真实数据和生成器生成的数据。
• RapidFuzz提供的种子具有相似但不同的数值分布，使用GAN来生成种子也加速了突变的过程。
• 本文实验证明，RapidFuzz在测试速度、覆盖范围和map大小方面都显著强于AFL。

---

一、介绍

• 模糊测试是通过生成大量测试输入，并发送到目标程序中运行来检测意外的行为和bug。
• 根据测试用例的构建，模糊测试技术可以分为两类：
  • 基于生成
    • 基于生成的模糊器旨在基于程序输入的语法生成高度结构化的测试用例。然而，由于特定语法的构建主要是手动完成的，所以基于生成的模糊测试技术效率并不高。
  • 基于变异
    • 基于变异的模糊器通过改变现有的测试用例来生成新的测试用例，即对初始种子进行变异。而基于变异的方法几乎不需要了解程序的输入结构，这对于许多应用程序来说更具可扩展性。
    • 通常，在程序输入存在丰富的结构信息。程序需要检查输入的语法格式，并阻止异常输入。由于基于突变的模糊技术几乎是随机改变现有的测试用例来进行变异，因此变异的空间相当大，特别是对于高度结构化的程序输入（例如，PDF、PNG、TIFF）。
    • 因此，对于高度结构化的数据，基于变异的模糊器生成能够通过语法检查并探索程序深层路径的测试用例是低效的。
• 为了解决生成高度结构化程序输入的挑战，研究人员提出了多种基于学习的技术。
  • Learn&Fuzz训练一个递归神经网络 (RNN)来自动学习语法结构。
  • FasterFuzzing使用学习模型来增强数据，可以看作是弥补输入样本数量不足的另一种增强策略。
  • GanFuzz展示了GAN在生成高度结构化输入方面的能力，但只关注了工业协议。
  • 这些技术在生成高度结构化的程序输入方面显示了它们的有效性。但这些训练模型是先前在大量现有样本上构建的。对于诸如专有协议之类的未知程序输入，它们可能会失去优势。此外，如何探索变异空间或加快生成高度结构化输入的速度尚未得到研究。
• 为了解决这些问题，本文提出了另一种数据收集方法，并应用一种更高级的学习模型来更快地学习特定的结构。
• 本文提出了RapidFuzz，该方法实现了基于Wasserstein-Generative Adversarial Networks with Gradient Penalty（WGAN-GP）的先进生成模型。
  • 首先，RapidFuzz解决了各种数据格式的问题，展示了基于GAN的模糊测试处理复杂数据的强大可扩展性。
  • 其次，与基于RNN的方法不同，RapidFuzz直接学习种子样本的数值分布。将这一特征与本文的缝合算法结合起来，RapidFuzz可以加速像AFL和FairFuzz这样的最新模糊测试器，并提高代码覆盖率。
  • 经过实验证明，经过RapidFuzz充分变异后，测试用例仍然保持聚类，但分布范围扩大了。
• 本文贡献总结如下：
  • 第一个基于GAN的模糊测试方法，注重覆盖率、速度和高度结构化的格式。
  • 通过结合变异基因检测算法和先进的学习模型WGAN-GP，生成的测试用例的分布得到了扩展。
  • RapidFuzz可以处理未知的高度结构化数据，无需准备训练数据。
  • 在9个程序上进行实验，涉及6种高度结构化的格式，结果表明其强大的可扩展性。

---

二、相关工作

• 基于突变的模糊测试通过利用修改从现有数据创建测试用例。最基本的突变策略是随机性。
  • AFL 使用一个优先级队列来收集每个测试用例的程序覆盖率，以指导变异过程。它将遗传算法与翻转、替换或其他变异操作结合起来创建测试用例。
  • BuzzFuzz 和 TaintScope 利用动态污点跟踪自动定位影响库调用处值的输入区域。
  • AFLFast 的变异策略使用了马尔可夫链建模，给予触发低频路径的测试用例更多的概率。
  • AFLGo 使用控制流图来优化种子变异。
  • VUzzer 利用基于数据流和控制流的种子变异策略，通过轻量级静态分析和动态分析提取程序特征。
  • FairFuzz 设计了一种机制来发现AFL中的低频路径。
  • EcoFuzz 利用基于奖励概率的系统来触发潜在路径。
  • 上述这些方法，为了实现完美的软件测试，旨在尽可能多地探索程序状态。主要挑战在于，爆炸式探索空间的方法，其计算能力和时间相对有限。即，稍微有引导的或没有引导的模糊测试方法不能很好地处理特定的结构。
• 最近，使用深度学习方法的基于生成的模糊测试正迅速崭露头角。
  • Learn&Fuzz 训练了一个循环神经网络 (RNN)来获取 pdf.obj 文件的语法结构。与传统的基于语法的模型相比，这个想法在代码覆盖率方面具有一定的优势。RNN 在文本处理领域是有效且广泛使用的。但使用 RNN 在速度方面似乎并没有太多优势。
  • FasterFuzzing 首次提出用 GAN 替代 RNN。GAN 通过学习收集样本的统计分布来直接生成新样本。由 GAN 生成的测试用例类似于真实测试用例，但仍然略有不同。这种微小的差异遵循收集数据的分布。尽管 FasterFuzzing 中实现了基于 GAN 的模型，但实验中使用的测试用例规模仍然太小以至于没有太多意义。用于证明其有效性的可靠实验数据仍然不足。
  • Ganfuzz 提出了一个使用工业协议作为主要测试输入的框架。Ganfuzz 利用 RNN 作为 GAN 的生成器部分，并提高了代码覆盖率。然而，Ganfuzz 仍受限于 RNN 和独特的数据结构。
  • MoWF 是基于白盒模糊测试，使用文件格式输入模型来检查数据的完整性约束。Skyfire 利用上下文无关文法，解决了高度结构化输入的问题，通过实现抽象语法树 (ASTs)对现有样本进行建模，然后学习包含语法特征和语义规则的概率上下文敏感文法 (PCSG)。
  • Learn&Fuzz 训练了一个基于字符级别的循环神经网络 (CHAR-RNN)，该网络学习了以 PDF 为数据集的语法，以生成高度结构化的文件。Learn&Fuzz 是一种基于语法的方法，利用深度学习技术。Learn&Fuzz 利用 RNN 关注生成语法本身。然而，学习特定的良好形式的结构与模糊测试的探索性质相冲突，这限制了Learn&Fuzz的性能。
• 
• 将RapidFuzz与目前最先进的方法进行比较，如表1中，AFL、AFLFast、AFLGo和VUzzer都是基于变异的方法，不能很好地处理高度结构化的数据。MoWF、GoWF和SkyFire是基于语法的生成模糊测试。它们可以处理部分高度结构化的数据，但由于基于语法的模型的限制，它们没有足够的可扩充性来实现各种类型的格式。Learn&Fuzz、FasterFuzzing、Smartfuzz和Smartseed是基于机器学习的生成方法。后三者并不关注高度结构化数据的速度和效率。Learn&Fuzz发现了学习系统与模糊本质之间的冲突。因此，基于上述问题的启发式思想是通过利用缝纫算法将输入生成与输入突变联系起来。
• RapidFuzz将基于学习的系统附加在主模糊器上，增加了触发程序中隐藏在更深层次信息的种子变异速度。

---

三、RapidFuzz

• 本文提出了RapidFuzz，利用GAN加快突变速度的方法。使得可以跳过部分无意义的突变，减少对高结构化数据进行模糊测试消耗过多计算资源的问题。
• 

1、数据预处理

• 本文将数据预处理分为：数据收集和数据转换。
• 这两个过程说明了如何获取充分的数据来训练模型。数据收集解决了训练集的数据源的问题；数据转换解决了GAN如何处理结构化数据的问题。此外，数据转换可以扩展到多个程序。
• 数据收集：
  • 训练集的质量直接影响了RapidFuzz的性能。如图1所示，为了获得高质量的合成测试用例，训练集需要利用一组包含正确结构信息的种子文件。
  • RapidFuzz将初始种子文件输入到AFL中，经过五个小时的时间生成了成千上万个变异的种子文件。这些种子文件不仅保留了原始结构，还包含变异信息。
• 数据转换：
  • 对于不同类型的高度结构化数据，有必要进行统一处理。因为GAN对输入数据格式有特定的要求，所以需要将训练集统一为GAN能够处理的相同格式。此外，还需要确保GAN的输出可以还原为其原始文件格式。
  • 在本文的方法中，首先将输入作为二进制流读取，然后通过Base64编码，将二进制流转换为数字矩阵。由于各种文件格式的大小不同，有必要选择一种编码方法来表示所有文件格式。
  • 整个数据预处理过程包括如下步骤，如图2所示：
    • 用二进制流读取输入。
    • 使用Base64对二进制流进行编码。
    • 将编码的代码转换为Base64数字。
    • 将数字序列转换为108*108的矩阵。
    • 
  • Base64共有65个代码，包括52个字母、10个数字、'+'、'/'和'='。Base64每次读取一个3字节的二进制序列，并将其转换为四个对应的6位序列。使用 '=' 字符填充多余的空间，以确保编码数据的长度是4的倍数。根据实验文件的不同大小，我们选择了108*108的矩阵来确保其能力。这种转换方法确保了RapidFuzz的兼容性。

2、带有梯度惩罚的Wasserstein GAN (WGAN-GP、Wassertein Generative Adversarial Networks with Gradient Penalty) 

• 本文最大的亮点之一是将生成对抗网络 (GAN)作为生成模型（生成测试用例）的一部分。
• GAN以生成图像而闻名，通过生成器和判别器的对抗学习，可以生成与真实图像相似但不相同的新图像。类似于生成图像，RapidFuzz生成的测试用例也不需要完全的规范，即为对测试用例的变异。并且RapidFuzz利用一个108*108的矩阵进行数据预处理，从而使得GAN能够处理各种数据格式。
• GAN由两个独立的网络组成，一个生成器和一个判别器。原始GAN的目标函数，如公式(1)所示，表示判别器认为它是真实样本还是生成样本的概率。在GAN的训练过程中，判别器希望最大化这个目标函数。这种架构确实能够生成类似的概率分布矩阵，最后使用类似KL散度的损失函数来评估效果。
  • 
  • 其中，G和D分别表示GAN中的生成器和判别器。符号 x∼p(x) 表示真实数据分布，即生成器G希望从中学习的数据分布。符号 z∼p(z) 表示先验输入噪声，它打断了生成器 G 的学习过程。该方程展示了生成器G和判别器D之间的动态平衡。生成器的目标是获得与真实数据分布距离最小的生成数据。
• 在引入 WGAN-GP 之前，Wasserstein GAN (WGAN)从Wasserstein距离的角度改进了GAN模型。它改善了原始GAN在训练不稳定性方面的问题。Wasserstein距离如公式(2)所示。Wasserstein距离描述了从一个分布到另一个分布的最小代价。与JS散度和KL散度性能不佳的情况不同，Wasserstein距离可以通过相对平滑的度量稳定训练过程。
  • 
  • 其中，W(Pr, Pg)代表真实数据分布Pr和生成数据分布Pg之间的Wasserstein距离。WGAN的引入明显缓解了训练不稳定性的问题。
  • 但WGAN引入的权重裁剪方法仍然会导致意外的行为。为了应对优化问题，WGAN-GP提出了一种更为先进的方法，遵循1-Lipschitz连续性，可以看作是在损失函数中的梯度惩罚。因此，相较于其他GAN模型，WGAN-GP能够更稳定、更有效地学习原始数据集上的概率分布。

3、变异基因检测算法 (Mutation gene detection algorithm)

• 变异基因检测算法被用作将突变注入到原始种子池的缝合算法。在这个算法中，敏感变异点主要用于检测那些AFL可能会对测试用例进行修改的字节。具体而言，AFL提供了关于测试用例的一些信息，例如测试用例的ID (id)、源 (src)、操作 (op)等，"op flip1, pos 7552" 表示对测试用例的第7552个字节上进行了1位翻转操作。
• 第7552个字节就可被视为一个突变点。通过统计AFL生成的所有种子文件中某个字节的变异频率，如果某个字节的变异频率很高，就将其标记为敏感变异点。这个过程的目的是找到那些在变异时可能对测试用例产生重要影响的字节。
• RapidFuzz通过对从AFL获取的训练集样本中敏感变异点（即热点）的频率进行排名。利用半随机方法确保高频变异点出现在由GAN生成的样本中，这些样本将与原始由AFL生成的样本结合在一起。这有助于保留原始测试用例的一些特征，同时引入新的变异。低频变异点通过一个随机函数确定。这个步骤的目的是引入一些随机性，使得低频变异点以较低的概率出现在继承的总变异点中，但仍然存在。这表明从父代中仍然可以获得基因遗传。
• 与非结构化数据不同，高度结构化的数据更具挑战性，更难以进行变异操作。通过采用这种变异基因检测算法，测试用例可以吸收那些更有价值且更有可能发生变异的点。
• 此外，AFL还难以对那些能够通过高度结构化数据的解析器的测试用例进行变异。通过对模糊测试中生成的测试用例进行统计分析，我们提取了那些具有高概率的突变点，以引导两侧测试用例之间的合并。伪代码如下：
  • 
• 我们收集了由AFL提供的变异数据集。然后，统计了突变点的频率，其中高频字节表示该字节不容易受到格式解析器的影响，并且有更高的变异概率。
• 首先，将所有的变异点按降序排列。对于较少的那一半的变异点，我们生成一个随机数k，服从U(0, 1)。如果随机数大于给定的阈值，那么该字节被标记为敏感变异点。这种方法不仅将高频变异点定义为敏感变异点，而且低频变异点也有一定的概率成为敏感变异点。
• 总的来说，对于GAN生成的每个样本，从变异点数据集中随机选择一定比例的敏感变异点，将源文件的值缝合到生成的样本中，从而增加了生成样本的变异概率。

---

四、评估

• 本文我们对9个不同的开源程序进行了实验，涉及6种高度结构化的数据，包括png、tiff、xml、elf、pdf和jpeg，如表2所示。对于每种格式，我们选择了2~3个程序来验证我们方法的有效性。

• 

• 这6种格式包括各种功能。例如，Tiff2pdf是一个将tiff文件转换为pdf文件的程序。该程序包含一个用于解析tiff文件的解析器，使其难以进行模糊测试。Tiffdump用于提取tiff文件中的目录信息。
• 本文提供了两个实验场景来讨论该方法的有效性，具体如下：
  • 场景1：
    • 首先，运行AFL5小时，以收集训练集。然后，将生成的种子注入AFL，并持续运行24小时，作为对照组。
    • 其次，将AFL生成的种子输入到RapidFuzz中进行进一步的变异，以生成300个新的种子。
    • 最后，将这300个新种子注入AFL，并持续运行24小时，作为实验组。
  • 场景2：
    • 模糊测试过程和训练过程同时进行。在AFL和FairFuzz运行6小时后，获得GAN的训练集。
    • 在训练完成后，将合并的测试用例并行注入到AFL（或其他模糊器）中。整个实验的时间限制被设定为24小时。
• 【注】GAN模型是可重复使用的，所以在长时间的测试过程中，训练的时间消耗是可以忽略不计的。
• 此外，与传统的模糊测试方法不同，基于深度学习的系统的训练过程主要依赖于GPU的计算资源，这为不中断CPU的情况下，提高模糊器性能提供了机会。
• 在场景2中，我们将初始种子的数量限制为一个，因为由Rapidfuzz生成的测试用例是在模糊测试进行中添加的。一个初始覆盖相对较低的单个初始种子可以更好地展示算法的效果。
• 软件实验配置设置如下：python3.6.2，Anaconda3，Keras2.1.6，tensorflow-gpu1.8.0，numpy1.14.0。
• 硬件配置包括：Intel i7-8700 K CPU，32G内存，和TITAN X显卡，12G内存。

1、评估指标

• 

1.1、Mapsize

• Mapsize是AFL中覆盖率的计算方法。AFL分配了一块大小为 65KB 的数组sharemem[]来存储分支的执行情况。每个数组元素包含一个元组，用于存储执行路径的位图。对于执行路径A->B->C->D->E，它在数组中以[AB]、[BC]、[CD]、[DE]的形式保存。当AFL获取到一个新的测试用例时，AFL会检查其执行时的跟踪路径，并将其与已有路径进行比较。
• 例如，存在两个跟踪路径A->B->C->D->E和A->B->C->A->E。第二个路径比对第一个路径有新的路径产生，分别是[CA]和[AE]。如果存在像A->B->C->E这样的新路径，它将不会被考虑，因为没有出现新的元组。AFL设计了这种结构以避免路径爆炸问题，并提供了一种全面的方法来评估程序中的模糊测试质量。
• 图3和表3展示了RapidFuzz的性能。所有实验都在24小时内进行，RapidFuzz在大多数目标程序的覆盖率和速度方面都表现出与AFL的明显差异。RapidFuzz在大多数情况下实现了更高的Mapsize，这意味着RapidFuzz发现的路径比AFL多，除了pngfix。并且，RapidFuzz在cjpeg、Tiff2pdf和Strip中分别检测到了10、3和3个崩溃，而AFL只发现了3、0和2个。
  • 

1.2、Code coverage

• 

• 代码覆盖率 (Code coverage)通常指的是由模糊测试输入触发的程序代码。本文从三个不同的方面提供覆盖率指标，包括函数覆盖、基本块覆盖和分支覆盖。如图4所示。
  • 基本块是一组指令，其中所有指令都按顺序执行且仅执行一次。基本块只有一个入口和一个出口，即基本块中的所有指令执行完毕后才会跳转到其他基本块。
  • 函数是程序中的一块代码，被设计用于完成不同的任务。函数覆盖是基本覆盖之一。
  • 分支是两个连续执行的基本块，可以将其视为由两个基本块及其连线组成的结构。分支覆盖表示程序中基本块之间的执行情况。
• 本文收集的代码覆盖是通过angr和Qemu获得的。其中，angr是一个先进的符号执行框架。符号执行是一种将程序转化为控制流图以找出漏洞的方法。angr实现了多种符号执行和静态分析方法，以实现更好的性能。Qemu是AFL中提供的一种模式，用于模拟程序执行。
• RapidFuzz调用angr接口获取被测试程序的控制流图和分支信息。然后，调用Qemu获取追踪信息。
  • 分支覆盖是从追踪信息的分支信息和angr提供的总分支信息中计算得出的。
  • 基本块覆盖是通过Qemu提供的每个测试用例的基本块数量和angr提供的分支中的总基本块数量计算得出的。
  • 函数覆盖是通过Qemu提供的函数入口与angr提供的控制流图中的函数入口之比计算得出的。
  • 具体的计算公式如下：
  • 
• 与AFL相比，RapidFuzz提高了代码覆盖率。对于Tiff2pdf和Tiffdump，提高的比例甚至超过了20%，如表4所示。一方面，根据提高的百分比，RapidFuzz成功地优化了AFL的变异过程。另一方面，RapidFuzz确实加速了整个模糊测试过程，这可以从图3中观察到。在大多数测试的程序中，RapidFuzz在分支覆盖、基本块覆盖和函数覆盖上都具有优势，即利用GAN进行变异提高了测试用例的质量，从而进一步提高了模糊测试的代码覆盖率。
• 
• 在场景2中，我们将本文的方法与Fairfuzz进行了两方面的比较：
  • 将基于AFL的RapidFuzz版本与FairFuzz进行了比较；
  • 在FairFuzz的基础上实施了RapidFuzz，以结合两种方法的优势，以展示RapidFuzz的可移植性。
• 结果发现在大多数情况下，RapidFuzz比Fairfuzz表现更好，并且这种优势会随着测试时间的增加而增加。此外，我们发现RapidFuzz + AFL的组合在cjpeg方面表现并没有更好。原因可能是深度学习模型的质量高度依赖于训练集，即程序在AFL运行6小时后收集的样本。但我们观察到，在AFL运行3小时后直到测试结束，mapsize不再发生改变。在这种情况下，就很难实现提升了。

1.3、Favored rate

• AFL有自己的方法来选择有意义的测试用例。首先找到能够覆盖最多分支的测试用例，然后根据其大小和执行时间来选择最佳的测试用例。公式如下：
  • 
• 从表5可以看出，对于不同的测试程序，RapidFuzz生成的近300个测试用例中，都有一部分被AFL吸收到最优的测试用例集中。Tiff2pdf的吸收比例高达21%，这也对应了Tiff2pdf的代码覆盖率最为出色。这些选定的测试用例是触发非重复路径的样本，表明了模糊测试工具接受测试用例的程度。根据表5，经过变异基因检测算法重新组合后，GAN生成的测试用例可以提高AFL模糊效率。
• 

1.4、t-SNE

• T-distributed Stochastic Neighbor Embedding (t-SNE)是一种非线性降维的机器学习方法。t-SNE的核心思想是寻找高维空间到低维空间的映射，从而使得高维数据可视化。可视化的数据可以以一种可理解的方式反映数据之间的差异。
• 在RapidFuzz中，t-SNE展示了合并的测试用例的分布情况。测试用例的分布分别通过t-SNE进行可视化，如图5所示。很容易看出，AFL测试用例的分布比RapidFuzz测试用例更为集中。这表示在高维空间中，AFL生成的测试用例变异速度比RapidFuzz慢。由RapidFuzz生成的测试用例和AFL的测试用例都位于中心，但RapidFuzz比AFL显示出更为广泛的分布。这表明RapidFuzz可以生成比AFL更有意义的测试用例，从而发现被测试程序的深层状态。
• 

---

五、总结

• 本文提出了一种名为RapidFuzz的创新方法。关键是利用深度学习技术和缝合算法加速原始模糊测试工具中的变异速度，并且实现比AFL更高的覆盖率。
• 实验结果显示，对于大多数选定的程序，Mapsize提高了约20%，这意味着RapidFuzz可以极大地提高模糊测试工具的覆盖范围。此外，t-SNE表明了变异速度显著提高，但在大多数情况下仍然遵循分布。
• 本文提出了一种基于深度学习生成模型的测试用例生成方法。测试用例生成的质量高度依赖于训练集。在未来的工作中，我们将继续研究如何自动获取高质量的训练集。
• 总的来说，RapidFuzz采用了一种合理的方法，将基于生成的模糊测试和基于变异的模糊测试结合起来，并极大提高了模糊测试效率。