MoFuzz：用于测试模型驱动软件工程工具的 Fuzzer 套件

引用

Nguyen H L, Nassar N, Kehrer T, et al. Mofuzz: A fuzzer suite for testing model-driven software engineering tools[C]//2020 35th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2020: 1103-1115.

摘要

模糊测试是一项成熟的技术，旨在通过将自动生成的数据提供给被测程序来发现意外的程序行为（例如错误、安全漏洞等）。但模糊测试在测试模型驱动软件工程工具(MDSE)方面的应用仍然受到限制，因为现有的模糊测试难以提供结构化、类型良好的输入（符合由给定元模型和底层建模框架产生的类型和一致性约束的模型）。通过借鉴模糊测试和自动模型生成的最新研究进展，我们提出了三种不同的模糊 MDSE 工具方法：基于图形语法的模糊器、使用不同模型变异算子集的基于覆盖率的突变模糊器的两种变体。我们对 MDSE 工具的评估表明，我们的方法优于标准模糊器和模型生成器 w.r.t.的模糊测试能力。我们的不同方法在故障发现能力和覆盖被测系统不同方面的能力方面有自己的优势和劣势。这些方法相辅相成，形成了一个用于测试 MDSE 工具的模糊器套件。

引言

模糊测试自动生成大量输入并将它们提供给被测程序，用来发现意外的程序行为并评估程序的可靠性。自模糊测试被提出以来，人们通过 AFL 之类的工具进行模糊测试，因其概念简单且经过验证的有效性而被广泛采用。但是模糊测试在测试模型驱动软件工程(MDSE)工具方面的应用仍然受到限制，因为现有的模糊测试难以提供结构化、类型良好的输入。

在本文中，我们研究了基于 Eclipse 建模框架(EMF)的 MDSE 工具的模糊化，EMF 是 OMG 的基本元对象工具(EMOF)的一个参考实现，它已经成为开源 MDSE 环境和工具链上下文中的一个标准。为了有效地测试基于 EMF 的工具，模糊器必须生成至少符合 EMF 和类型约束的输入模型，而现有的模糊方法都无法满足这一需求。

我们提出了 MoFuzz，一个用于测试 MDSE 工具的模糊器套件，它从两个相互独立发展的研究领域中解决了这一挑战，(i)突变和基于生成器的模糊，(ii)自动模型生成。我们提出三种不同的模糊器来生成模型，作为模糊 MDSE 工具的输入:(i)一个基于图形语法的模糊器，试图尽可能快地覆盖输入领域的不同方面;(ii)建立在 EMF Edit API 之上的一组定制定义的突变;(iii)一组指定为模型转换规则的编辑操作，这些规则是从给定的元模型中生成的。

我们在一组基于 EMF 的真实 MDSE 工具上评估了我们的模糊方法。实验结果表明，所有方法的模糊能力都优于现有的模糊器和自动模型生成器。我们的方法在故障发现能力和覆盖被测系统不同方面的能力方面都有自己的优势和劣势。这些方法相辅相成，形成了一个用于测试 MDSE 工具的模糊器套件.

MoFuzz方法

图 1 给出了 MoFuzz 模糊器套件的总体概述。它以输入域的元模型和待测试的 MDSE 工具作为输入。我们的内部结构建立在 JQF 之上，这是一个针对 Java 的反馈导向模糊测试框架。JQF 执行实时字节码检测来测量代码覆盖率，并使用自定义输入生成器提供的输入反复执行测试中的程序。此外，JQF 提供了各种模糊算法的实现，包括 Zest 算法，它将在我们的评估中作为基线技术。

图 1 MoFuzz 的高层概述

基于生成器的模糊测试

使用基于生成器的模糊方法的目的是尽可能快地生成覆盖输入域不同方面的模型，同时保持高水平的一致性。尽管基于求解器的生成器提供了最强的一致性保证，但现有的工具对于我们模糊化的目的来说效率太低，而且他们无法在短时间内生成大量的模型。为了实现自包含性，在介绍集成到我们的模糊套件 MoFuzz 中的特定配置之前，我们简要回顾一下一般的模型生成过程。

首先遵循基于语法的模型生成方法的模式，EMF 模型生成器将元模型转换为建设性的语言规范，然后可以将其用于模型生成。模型生成分为两个阶段。首先，模型增加阶段在不违反多重性上限的情况下创建模型元素。然后，模型完成阶段通过与模型修复工具 EMF Repair 交互，将中间模型完成为有效的 EMF 模型。

为了实现 MoFuzz 模糊化，我们为模型增加阶段配置两种产生规则:额外节点创建和额外边缘创建。前者创建一个特定类型的 ASG 对象及其来自合适容器的传入包含引用，后者在两个合适的现有对象之间插入一个跨树引用。所有的规则都被包装到一个所谓的独立单元中，该单元以非确定性的方式迭代地执行其中的一个规则。从我们使用基于生成器的模糊器的总体目标出发，规则被设计为原子性的，它们执行基本的更改可以生成模型的所有可能结构。模型可以作为输入，输入到 EMF model Generator 中。这种策略可以有效地生成大型模型。但在 MoFuzz 中，我们选择了一个限制模型大小的设置，以避免在测试中执行 MDSE 工具时出现的可伸缩性问题。

基于突变的模糊测试

在这种方法中，我们建议采用自动故障检测中最广泛使用的技术之一，即覆盖引导的灰盒模糊测试(CGF)。基于一组初始输入，CGF 迭代地对输入应用各种变异以产生新的测试输入。关键思想是只保留那些增加覆盖率的新输入，从而以迭代方式有效地探索程序空间。我们将 CGF 的实现分为两个阶段:生成阶段和突变阶段。在生成阶段，生成随机种子模型，直到实现预配置的目标元模型覆盖率。在突变阶段，从队列中选择一个输入模型，并对其应用一组突变。然而，利用 CGF 的传统模糊器通常对二进制/文本输入进行操作，在位级别上应用突变，这对于实例模型的输入领域不是很有效。因此，我们需要直接在模型级别上操作的突变算子。

我们提供了上述两阶段方法的两个具体实现。一个使用通用 EMF Edit API，另一个基于规则的突变。

对于第一种技术，我们使用不同种类的模型突变来满足两个阶段中每个阶段的不同要求。由于变异算子是基于 EMF Edit API 实现的，我们将这种技术称为 MoFuzz-cgf-emfedit。在生成阶段，EMF 随机实例化器通过利用给定元模型定义的包含层次结构，分两步随机生成 EMF 模型：首先，包含树以深度优先的方式填充随机初始化的对象，直到预先配置达到目标尺寸。其次，基于部分模型中的可用类型创建跨树引用。在突变阶段，基于 EMF Edit API 的突变操作模型中的单个对象，因此不需要通过计算密集型匹配算法找到复杂的图形模式。我们的默认实现在选择一个随机突变应用时，按照以下顺序优先选择突变操作符:(1)添加对象，(2)更改/取消设置属性和替换子树，(3)更改交叉引用，(4)删除对象。

我们的第二个覆盖引导模糊器，在图 1 中称为 MoFuzz-cgf-cpeo，使用从给定元模型派生的基于规则的模型转换作为模型突变。与第一种方法中介绍的自定义突变相比，我们使用这种保持一致性的编辑操作(CPEO)进行模糊测试的主要思考是在更高的一致性级别上合成模型，一般类型的 CPEO 类似于我们定制定义的突变，包括创建、删除、移动和更改模型元素的操作。在生成阶段，只选择节点和边缘创建规则，以便快速达到一定程度的元模型覆盖。在突变阶段，利用各种 CPEO 对反馈循环队列中最有前途的模型进行突变。

实验评估

理想的评估形式将是评估我们的 fuzzer 套件的性能在一个建立的基准上，如谷歌的 FuzzBench。但是这些基准都不包含 1108 个 MDSE 工具作为测试程序，目前还没有用于模糊测试 MDSE 工具的基准。为此，我们选择了一组真实世界的 MDSE 工具作为实验对象。所有工具都是公开可用的，在 Java 和 EMF 的基础上实现: EMF2GraphViz、UMLValidator、UML2Java、UML2OWL、EMFCompare、EcoreUtil。我们可以假设所有项目都达到一定程度的成熟度；它们不太可能包含浅层错误，通过模糊测试将故障查找呈现为一项非平凡的任务。

虽然我们的 fuzzer 套件可以使用任何基于 EMF 的元模型来对通用工具进行模糊测试，但在我们的实验中，我们坚持使用 UML 元模型来实现这个目的，以便在不同的实验对象之间进行更好的比较。

在比较基线的选择上，我们选择 Zest 和 EMF Random Instantiator 作为比较基准的基线，它们代表了结构感知模糊和自动模型生成这两个研究领域的最新工具。

由于 fuzzing 的基本随机性，fuzzer 的性能在多次运行中可能会有所不同。我们对每个受试者进行了 30 次试验，结果以平均值和标准偏差的形式报告。同时采用了一个 1 小时的超时时间，因为初步的测试运行显示，在这个时间之后，几乎所有的测试对象的覆盖率趋于稳定。

实验结果

图 2 绘制了每个项目和技术随时间变化的地图覆盖范围，其中每个图显示了每个时间点 30 个试验的平均地图覆盖范围。总体结果报告在表 1 中，它描述了 1h 超时后的平均最终覆盖率以及标准偏差。结果表明，对于所有基准测试对象，除了 UML2Java，我们提出的一种或多种技术能够显著优于基线方法。相对的，所有方法在 UML2Java 上都可以执行得同样好，与其他方法相比，UML2Java 是一个相当简单的项目。

图 2 平均图覆盖时间(30 次试验，1 小时超时)。

表 1 平均地图覆盖后 1 小时超时 30 次试验

总体而言，AtlanMod 生成器在覆盖范围方面表现最差。Zest 能够有效地引导生成器逐步增加覆盖率，但与我们的技术相比，它仍然存在不足，并且产生的结果也不太稳定。MoFuzz-emf-modelgen 和 MoFuzz-cgf-emfedit 在所有技术中表现最好，MoFuzz-emf-modelgen 通常具有最快和最高的整体图覆盖率。虽然 MoFuzz-cgf-cpeo 在大多数项目上都能够胜过 AtlanMod，但这种改进通常也不足以超过 Zest。一个可能的原因可能是 MoFuzz-cgf-cpeo 的模型生成过程稍慢。 大多数实现 CPEO 的 Henshin 规则包含的图形模式比 MoFuzz-emfmodelgen 使用的规则模式大得多，这导致应用规则时匹配时间更长。

表 2 显示了我们在实验评估过程中遇到的崩溃。如果其中一种方法能够触发崩溃，我们会报告找到崩溃的平均时间以及崩溃暴露的可靠性。 可靠性表明该方法能够至少识别一次崩溃的试验比例。

表 2 找到实验中发现的每次崩溃的平均时间

与基线方法相比， 12 次崩溃中有 11 次，我们的技术(1)与基线一样可靠地触发崩溃，(2)以更高的可靠性触发崩溃，(3)暴露一个其他基线方法都无法找到的崩溃。对于除 EMFCompare-3 之外的所有崩溃，与基线方法相比，至少我们提出的一种技术能够在明显更快的时间内找到崩溃。

总的来说，MoFuzz fuzzer 套件发现了 12 个崩溃，而组合基线只能暴露其中的一个子集（8 个崩溃），如图 3 所示。虽然一些发现的崩溃可能具有相同的异常类型（ClassCastExceptions 和 StackOverflowErrors），我们每个单独的模糊器也能够触发任何其他方法（UML2Java-1、EMFCompare-2 和 EMF2Graphviz-3）都没有覆盖的独特崩溃。

图 3 每种方法发现的崩溃数

结论及未来工作

在本文中，我们介绍了 MoFuzz，这是一个针对模型驱动软件开发 (MDSE) 中的模糊测试工具问题量身定制的模糊器套件。该套件包括一个基于图形语法的模糊器和一个覆盖引导的基于变异的模糊器的两个变体。前者是尝试尽可能快地覆盖输入域的不同方面，而后两者旨在逐步发展输入模型以在被测 MDSE 工具中执行更深的路径。

我们的实验结果有两个。首先，我们可以证明 MoFuzz 套件中的所有模糊器都可以显着优于现有的标准模糊器和模型生成器 w.r.t. 涵盖被测 MDSE 工具及其故障检测功能。这证明了为模糊测试 MDSE 工具而集成这两种技术的好处，这是指导我们工作的主要研究问题。其次，我们的实验结果表明 MoFuzz 中的模糊测试方法确实有自己的优点和缺点。模糊器相互补充，形成了用于测试 MDSE 工具的模糊器套件，有助于建模工具的成熟。

未来的工作可以集中在进一步增强 MoFuzz 算法上。例如，Driller 或 SymFuzz 等混合方法有效地将模糊测试与符号执行结合起来，以发现更深层次的错误。种子生成方法，例如 Skyfire 或 Orthrus 可能能够为 MoFuzz 提供高质量的种子语料库。这些方法的更直接的替代方法是进一步调整我们的实例生成算法，以专注于意外和轻微格式错误的输入的生成。我们还想研究更紧密地集成基于生成器和变异的模糊器的潜在优点。一方面，由于用作我们基于生成器的模糊器的基础的 EMF 模型生成器可以与种子输入模型一起使用，因此它可以与 JQF 框架的反馈循环集成以实现更多覆盖。另一方面，它可用于为两个基于突变的模糊器生成种子输入，这些模糊器目前作为一个两阶段过程工作，创建自己的用于突变的种子输入。此外，我们打算探索 EMF 模型生成器提供的其他生成策略（具有不同配置）的模糊特性，用于生成多样化和庞大的模型。最后，我们打算扩大我们的实验范围，以包括更多的 MDSE 工具处理不同类型的模型，以加强我们实验结果的外部有效性。

致谢

这项工作由德国研究基金会 (DFG) 部分资助，项目“元建模和图形语法：生成建模语言的开发环境”（授权号 HA 2936/4-2 和 TA 294/13-2）和“ ProCI：不完整信息下的流程一致性”（授权号 GR 3634/7-1）。

本文由南京大学软件学院 2021 级硕士曹智豪翻译转述，肖媛审核。

来源：慕测科技