考研软件工程(考研软件工程专业考哪些科目)




考研软件工程,考研软件工程专业考哪些科目

引用

H. L. Nguyen, N. Nassar, T. Kehrer and L. Grunske, “MoFuzz: A Fuzzer Suite for Testing Model-Driven Software Engineering Tools,” 2020 35th IEEE/ACM International Conference on Automated Software Engineering (ASE), 2020, pp. 1103-1115.

摘要

模糊测试的目的是通过将自动生成的数据输入到被测试的程序中来发现意外的程序行为。然而,使用模糊来测试模型驱动软件工程(MDSE)工具的应用仍然受到限制,因为现有的模糊器难以提供结构化的、良好类型的输入。我们提出了三种不同的模糊 MDSE 工具的方法:一个是基于图语法的模糊器,另外两个是基于覆盖引导的和基于突变的模糊器的两种变体,它们使用不同的模型突变算子集工作。我们对一组真实世界的 MDSE 工具的评估表明,我们的方法可以优于标准模糊器和模型生成器的模糊能力。此外,我们发现,我们的每一种方法在故障发现能力和覆盖被测试系统的不同方面的能力方面都有自己的优缺点。因此,这些方法相互补充,形成了一个用于测试 MDSE 工具的模糊器套件。

1. 引言

模糊测试自动生成大量的输入并将它们输入到被测试程序中,以发现意外的程序行为并评估程序的可靠性。自 Miller 首次提出以来,通过 AFL 这样的工具进行模糊处理,由于其概念上的简单性和被证明的有效性而被广泛采用。各种先进的方法已经被提出通过指导输入生成过程来提高模糊器的性能。通过包含目标输入字符串突变或特定于问题的生成器,已经进行了进一步的改进。

然而,模糊技术在测试模型驱动软件工程(MDSE)工具方面的应用还很有限。这是由于现有的模糊器难以提供结构化的、良好类型的输入,即符合由给定元模型和底层建模框架诱导的类型和一致性约束的模型。

在本文中,我们研究了基于 Eclipse 建模框架(EMF)的 MDSE 工具的模糊化,EMF 是 OMG 的基本元对象工具(EMOF)的参考实现,EMOF 在开源的 MDSE 环境和工具链中已经成为公认的标准。使用 EMF 模型作为输入的工具有一个处理管道,如图 1 所示。解析阶段将模型从某种外部表示转换为内部表示,根据工具的核心功能,内部表示可以很容易地进行处理。通过解析阶段的模型在语法上是有效的,因为它们遵守 EMF 施加的基本一致性约束,并且它们是给定元模型的正确类型。语法上有效的模型可能需要通过验证阶段,检查进一步的语义一致性约束,特别是多重约束或元模型定义的任意格式良好的规则。每个阶段都可能拒绝输入模型,并且工具的核心功能仍未经过测试。因此,为了有效地测试基于 EMF 的工具,模糊器必须生成至少符合 EMF 和类型约束的输入模型,而现有的模糊方法都无法满足这一需求。

图 1:基于 EMF 的 MDSE 工具加工管道

我们提出了 MoFuzz,一个用于测试 MDSE 工具的模糊器套件,通过借鉴两个相互独立发展的研究领域来解决这一挑战,即(i)突变和基于生成器的模糊,(ii)自动化模型生成。前者提供了指导模糊器有效覆盖被测系统的灵感,后者提供了生成有效模型的技术。

我们提出三种不同的模糊器来生成模型,作为模糊 MDSE 工具的输入:(i)一一种基于图形语法的模糊器,它试图尽可能快地覆盖输入域的不同方面,以及两种基于突变的方法,其目的是使用(ii)定义的一组自定义 EMF 编辑 API 的突变,或者(iii)一组指定为模型转换规则的编辑操作,这些规则是从给定的元模型中生成的。虽然已经对使用上下文无关语法的文本输入格式进行了研究,但我们的方法集成了基于实例生成图语法概念的 EMF 模型生成器。我们的基于变异的模糊器在某种意义上受到指导,即有希望的种子输入是通过一个反馈循环来选择的,该反馈循环利用了来自被测系统的覆盖率信息。它们的变异点在于模型突变所保持的一致性水平。

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

2.方法

2.1 综述

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

图 2:MoFuzz 的高层概况

我们提供三种不同的输入生成策略:(i)一种基于图语法的方法,利用最近推出的高效模型生成器,尽可能快地涵盖输入领域的不同方面;以及两种基于突变的方法,目的是通过使用(ii)一组构建在通用 EMF Edit API 之上的自定义突变来增量演进输入,以练习深度路径,或者(iii)一组保持一致性的编辑操作(CPEOs),指定为模型转换规则,使用相关方法和支持工具集从给定的元模型生成。

2.2 基于发生器的模糊方法

使用基于生成器的模糊方法的主要目的是尽可能快地生成覆盖输入域不同方面的模型,同时保持高水平的一致性。尽管基于求解器的生成器提供了最强的一致性保证,但现有工具对于我们模糊化的目的来说效率太低;他们无法在短时间内生成大量的模型。在剩下的模型生成器中,Nassar 最近提出的 EMF 模型生成器代表了一致性和性能之间最有希望的折衷。生成的模型是有效的 EMF 模型,它们具有适当的类型,并且遵循由元模型定义的任意多重性约束的良好格式规则。此外,该工具可以在几分钟内生成大型有效模型。

2.2.1 Mofuzz 的生成策略。为了模糊化,我们将模型增加阶段配置为两种产生规则:额外节点创建和额外边缘创建。前者创建一个特定类型的 ASG 对象及其来自合适容器的传入包含引用,后者在两个合适的现有对象之间插入一个跨树引用。这些规则是针对元模型的每个元类和引用类型派生的,并配备了应用程序条件,以防止引入上限违规并保留 EMF 约束。所有的规则都被包装到一个所谓的独立单元中,该单元以非确定性的方式迭代地执行其中的一个规则。

从我们使用基于生成器的模糊器的总体目标出发,这种策略背后的直觉如下:规则被设计为原子性的,也就是说,它们执行基本的更改,因此可以生成模型的所有可能结构。通过构造,规则覆盖所有元模型类型。因此,他们可以广泛地研究并生成给定元模型的所有可能的有效 EMF 模型。此外,查找规则匹配是非常高效的,因为它需要找到一个小型的图形模式。分类成两种不同类型的规则增加了找到适用规则的可能性。此外,它们的原子设计增加了以任何顺序组合它们的灵活性。最后,该策略从头开始模型生成过程,因此,它独立于给定种子模型的质量,原则上,种子模型可以作为输入输入到 EMF 模型生成器中。这种策略可以有效地生成大型模型。然而,在 MoFuzz 中,我们选择了一个限制模型大小的设置,以避免在测试中执行 MDSE 工具时出现可伸缩性问题。

2.3 基于变异的模糊方法

在这种方法中,我们建议采用在自动故障检测中最广泛使用的技术之一,即覆盖引导灰盒模糊(CGF),到 MDSE 领域。基于一组初始输入,CGF 迭代地对输入应用各种突变以产生新的测试输入。关键的想法是只保留那些增加覆盖率的新输入,从而以迭代的方式有效地探索程序空间。特别地,我们建议将 CGF 的实施分为两个阶段,生成阶段和突变阶段:

在生成阶段,生成随机种子模型,直到实现预配置的目标元模型覆盖率。我们的目标是要有一套不同的种子输入,涵盖被测试项目的不同方面。但是,我们只使用覆盖在测试中的 MDSE 工具的新部件的最新输入来初始化我们的输入队列。这种方法背后的直觉是,第一个输入通常只覆盖可以轻松到达的程序位置。相反,以后仍然能够在这些微不足道的路径之外执行额外覆盖的输入可能更值得保留。

在突变阶段,从队列中选择一个输入模型,并对其应用一组突变。如前所述,如果突变的输入执行新的覆盖率,它也会被添加到队列中,否则它将被丢弃。此过程将重复进行,直到达到超时时间或用户手动中止该过程。然而,利用 CGF 的传统模糊器通常对二进制/文本输入进行操作,因此在比特级别上应用突变,这对于实例模型的输入领域不是很有效。因此,我们需要直接在模型级别上操作的突变操作符。

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

2.3.1 基于通用 EMF Edit API 的自定义突变。对于第一种技术,我们使用不同类型的模型突变来解决两个阶段中每个阶段的不同需求。由于突变操作符是基于 EMF Edit API 实现的,我们将这种技术称为 MoFuzz-cgf-emfedit。

(1)生成阶段:对于生成阶段,我们建立在 NaoMod 团队开发的现有 EMF Random Instantiator 之上,NaoMod 团队以前被称为 AtlanMod。与 Mougenot 的方法类似,EMF 随机实例化器通过利用给定元模型定义的包含层次结构,通过两个步骤随机生成 EMF 模型:首先,包含树以深度优先的方式填充随机初始化的对象,直到达到预配置的目标大小。树遍历可能会在随机点上被修剪,或者达到预先配置的最大深度。结果是一个符合元模型定义的包含层次结构的模型。其次,跨树引用是基于分部模型中的可用类型创建的。这是通过遍历模型中的每个对象并设置存在合适相反对象的交叉引用来完成的。

为了在生成的种子模型中获得实例化模型结构的高度多样性,我们调整了原始的随机选择策略,通过优先化元模型定义的未公开类和引用类型。这在基于语法的模糊器中很常见,这些模糊器操作于派生树,其中先前发现的扩展规则被优先化以实现更高的语法覆盖率。

(2)突变阶段:基于 EMF Edit API 的突变操作于模型中的单个对象,因此不需要通过计算密集的匹配算法来发现复杂的图形模式。简单来说,以下突变已经实现:增加对象,删除对象,改变属性,取消设置属性,改变交叉引用,替换子树。

我们的默认实现在选择一个随机突变应用时,按照以下顺序优先选择突变操作符:(1)添加对象,(2)更改/取消设置属性和替换子树,(3)更改交叉引用,(4)删除对象。

与基于求解器或基于图语法的方法相比,基于 EMF API 的操作更高效,因为它们不需要执行任何昂贵的约束求解或图转换操作。然而,只考虑基本的一致性约束,即一致的包含层次结构和适当的类型;任何进一步的约束都可能被违反。我们可以容忍这种情况,因为使用这种技术,我们更喜欢速度而不是一致性。我们依靠进化算法过滤掉格式太不规范的输入模型,从而不能暴露 MDSE 测试工具的核心功能的新部分。

2.3.2 元模型基于规则的突变。我们的第二个覆盖导向模糊器,在图 2 中被称为 MoFuzz-cgf-cpeo,它使用基于规则的模型转换,这些转换是从给定的元模型中派生出来的,作为模型突变。转换规则生成器最初设计的目的是生成编辑操作的声明性规范,这些操作在可视化模型编辑器中可以作为编辑命令使用。这些编辑操作必须保持标准可视编辑器所强制的一致性级别,标准可视编辑器包括基本类型和 EMF 约束。此外,为了保持模型处于图形显示状态,还强制执行了一组受限制的多重性,特别是下界。与前一节中介绍的自定义突变相比,我们使用这种保持一致性的编辑操作进行模糊化的主要直观感受是在更高的一致性级别上合成模型,因此可以更可靠地通过图 1 所示的模型加载管道。

一般类型的 CPEOs 类似于我们定制定义的突变,包括创建、删除、移动和更改模型元素的操作:

与应用基于 API 的突变策略相反,我们在所有类型的 CPEOs 上选择均匀的概率分布来选择下一个突变。这种选择背后的基本原理是,节点删除和移动不会导致剧烈的变化,就像我们基于 api 的突变一样。这是因为指定 CPEO 的编辑规则是由转换引擎通过检查所谓的悬空条件来应用的,这些条件是由双推出方法对图转换施加的。如果一条规则会导致 ASG 中的悬空引用,悬空条件就会阻止它的应用,这意味着我们不能在 CPEO 指定的单个转换步骤中删除较大的子图。较大的子图只能以逐步删除的方式删除,从包含树的叶节点开始。

3. 实验评估

3.1 研究设计

3.1.1 实验对象。理想的评估形式是在一个已建立的基准上评估我们的模糊器套件的性能,这是传统模糊器的惯例,也是声音实验评估所需要的。然而,这些基准都不包括作为被测程序的 MDSE 工具,而且目前还没有用于模糊测试 MDSE 工具的基准,这是我们在这项工作中的先锋。为此,我们选择了一组真实世界的 MDSE 工具作为实验对象。所有工具都是公开可用的,在 Java 和 EMF 的基础上实现,并提供一个合适的测试驱动程序作为模糊的入口点:EMF2GraphViz、UMLValidator、UMLValidator、UML2OWL、EMFCompare、EcoreUtil。

所选的主题涵盖了各种不同的特定于 MDSE 的任务和应用程序,包括模型到模型和模型到代码的转换、模型验证、模型比较和合并,以及用于实现建模工具的基本库。此外,我们的主题选择包括通用工具和特定于语言的工具,后者基于 UML 元模型的基于 EMF 的实现。我们选择的所有科目都在积极发展中,在 MDSE 社区中大量使用,它们有超过十年的发展历史。因此,我们可以假设所有的研究对象都有一定程度的成熟;它们不太可能包含浅层 bug,通过模糊处理将错误查找变成一项重要的任务。

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

至于算法参数,我们为生成的模型设置最大目标大小为 500。对于基于突变的模糊器,我们将其输入队列的大小限制为最多存储 50 个执行新程序部件的模型。

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

3.1.4 实验次数和重复次数

由于模糊的基本随机性质,模糊器的性能可以在多个运行中变化。为了解释这一点,每个受试者进行了 30 次试验。结果以平均值和标准差报告。此外,还进行了统计检验,以确定观察到的任何差异是否具有统计学意义。

研究中常用的超时时间从几个小时到 1 天不等。在这个评估中,使用了一个 1 小时的超时时间,因为初步的测试运行显示,在这个时间之后,几乎所有的测试对象的地图覆盖(见下文)趋于稳定。

3.2 研究问题

l 问题一(覆盖率):与两种基线方法相比,MoFuzz 在模糊 MDSE 工具时能够提高代码覆盖率吗?

l 问题二(故障探测):与两种基线方法相比,MoFuzz 是否可以在模糊 MDSE 工具时提高故障查找能力?

3.3 实验结果

3.3.1 问题一:覆盖率结果。为了评估覆盖率,我们使用 JQF 框架提供的地图覆盖率度量。由于在模糊测试期间要执行大量的程序,因此计算每次运行的覆盖率应该尽可能地轻量级。

图三:平均地图覆盖时间

图 3 绘制了每个主题和技术随时间变化的地图覆盖范围。总体结果报告在表 1 中。结果表明,对于所有基准测试对象,除了 UML2Java,我们提出的一种或多种技术能够显著优于基线方法。相反,所有方法都可以在 UML2Java 上执行得同样好,与其他方法相比,UML2Java 是一个相当简单的主题。

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

总体来说,MoFuzz-emf-modelgen 和 Mofuz -cgf-emfedit 在所有技术中表现最好,Mofuz-emf-modelgen 通常拥有最快和最高的总体地图覆盖。虽然 MoFuzz-cgf-cpeo 能够在大多数受试者中优于 AtlanMod,但这种改进通常不足以超越 Zest。

3.3.2 问题二:崩溃探测。表 2 展示了我们在实验评估过程中遇到的崩溃。

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

图 4:每种方法发现的崩溃数

总的来说,MoFuzz 模糊器套件发现了 12 个崩溃,而合并的基线只能暴露其中的一个子集(8 个崩溃),如图 4 所示。虽然一些发现的崩溃可能具有相同的异常类型,但我们的每个模糊器也能够触发一个独特的崩溃,这是任何其他方法都没有覆盖到的。

4. 结论和未来工作

在本文中,我们提出了 MoFuzz,一个针对模型驱动软件开发(MDSE)中模糊测试工具问题的模糊测试套件。该套件包括一个基于图形语法的模糊器和两个基于覆盖引导的突变模糊器的变体。

我们的实验结果是双重的。首先,我们可以证明 MoFuzz 套件中的所有模糊器都可以显著优于现有的标准模糊器和模型生成器,以覆盖测试中的 MDSE 工具及其故障检测功能。其次,我们的实验结果表明,MoFuzz 中的模糊方法确实有各自的优点和缺点。因此,模糊器相互补充,形成了一个用于测试 MDSE 工具的模糊器套件,有助于建模工具的成熟。

未来的工作将集中在进一步增强 MoFuzz 算法上。种子生成方法可以为 MoFuzz 提供高质量的种子语料库。这些方法的一个更直接的替代方法是进一步调整我们的实例生成算法,以专注于生成意外的、稍有畸形的输入,忽略所需的引用、设置无效的属性值等。我们还想研究将基于生成器和突变的模糊器更紧密地整合的潜在好处。一方面,由于 EMF 模型生成器(它是我们基于生成器的模糊器的基础)可以与种子输入模型一起工作,因此它可以与 JQF 框架的反馈循环集成,以实现更具有覆盖率指导的行为。另一方面,它可以用来为两个基于突变的模糊器生成种子输入,目前这两个模糊器的工作分为两个阶段创造自己的种子输入用于突变。

此外,我们打算探索 EMF 模型生成器提供的其他生成策略的模糊特性,以生成不同的和巨大的模型。最后,我们打算扩大我们的实验,包括进一步的 MDSE 工具与不同类型的模型,以加强我们的实验结果的外部有效性。

致谢

本文由南京大学软件学院 2021 级硕士曾鹏程翻译转述、肖媛审核。

考研软件工程(考研软件工程专业考哪些科目)

未经允许不得转载:广州考研网 » 考研软件工程(考研软件工程专业考哪些科目)

赞 (0) 打赏

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏