论文:Seijas P L, Thompson S, Francisco M Á. Model extraction and test generation from JUnit test suites[J]. Software Quality Journal, 2018, 26(4): 1519-1552.

https://ieeexplore.ieee.org/document/7809816

论文摘要

在本文中,我们将介绍如何从遗留单元测试套件中推断系统的状态机模型,以及如何从这些模型生成新的测试。我们方法的新颖之处在于将控制依赖关系和数据依赖关系结合在同一模型中,与此领域的大多数其他工作形成对比。结合这两种依赖性有助于我们构建更具表现力的模型,从而使我们能够进行更智能的测试。我们用我们的实现示例来说明这些技术,James工具旨在将这些技术应用于Java代码和测试。

研究介绍:测试是验证系统最常用的方法,无论是在构建时还是在它们发展时。测试是一个代价高昂的过程,同时也是必然的,仅在测试套件中指定的点探索系统。在本文中,我们将展示如何通过从测试中推断出系统模型来利用现有的单元测试来提供更多的测试价值。我们做出四项具体贡献。

  1. 我们定义了一种新方法,用于从现有测试套件和系统实现中推断出系统的状态机模型。使用数据流和控制流信息的组合推断状态机:现有方法倾向于仅使用其中之一。
  2. 我们将展示如何从该模型自动为被测系统推导出潜在的新测试用例。使用基于QuickCheck属性的测试工具从模型生成新测试,该测试工具练习模型并打印调用序列和后置条件的示例。
  3. 我们提供了一种机制,通过该机制可以自动推断Java系统的近似QuickCheck模型,从而允许从现有测试套件快速开发PBT模型。
  4. 我们提出了一项试点研究,其中我们应用我们的方法为现有工业系统生成新的测试。

我们的工作旨在提取表示目标Web服务的成功和失败行为的模型。模型描述的行为旨在比原始单元测试更通用。这种推广使我们可以通过随机遍历模型来生成新的测试。在此过程中,我们遵循Erlang的早期工作,其中从EUnit测试套件中提取有限状态机模型和属性。

然而,与任何自动化一样,生成模型的某些方面以及因此产生的一些测试可能与系统的预期行为不对应。生成的测试可能需要在添加到测试套件之前进行人工审核,生成的模型可能需要在实际使用之前进行手动更正。然而,一般来说,调整近似模型和测试的成本要低于从头开始编写它们的成本,并且它们可能会探索人工在手动工作时不会考虑的情况。

这里描述的技术已经在一个名为James的工具中实现。James的源代码是可用的;还可以找到更多技术细节。

这里描述的工作和James的实现都是针对Web服务的,因为它们通过查找HTTP请求来识别接口。因此,要求目标系统是Web服务。但是,这里提出的主要思想应该是直接将它们应用于其他类型的API(例如动态库),只要被测系统(SUT)像黑盒一样进行测试并具有清晰的界面。

本文的结构如下:在引入基于属性的测试和相关工作后,我们推动了所采用的方法。然后,我们解释了我们的解决方案的结构,模型生成,测试生成和试验研究。我们也讨论未来的工作。

基于属性的测试

基于属性的测试(PBT)最初是为Haskell [7]开发的,并已转移到一系列其他编程语言中。Quviq QuickCheck (以下简称QuickCheck)支持随机测试Erlang(和C通过外部函数接口)。

程序的属性在一阶逻辑的子集中陈述,嵌入在Erlang语法中。QuickCheck为随机生成的Erlang数据值集合验证这些属性,并在必要时由用户指导定义生成。当发现反例时,QuickCheck尝试以建设性的方式生成更简单,更易理解的反例;这个过程称为收缩。

在测试基于状态的系统时,构建系统的抽象模型以及使用此模型来驱动真实系统的测试是有意义的。抽象状态机可以实现为预定义的QuickCheck行为eqc_fsm的客户端模块。eqc_fsm状态机由一组有限的(“control”)状态和状态数据组成,状态数据由机器的转换修改。这些模型是扩展有限状态机(EFSM)的变体,因此比FSM更具表现力。

相关工作

以前的方法通过关注通常执行命令的顺序来模拟接口的预期用途。这些方法的一个限制是它们通常不会推断如何创建命令所需的参数。在某些情况下,参数的不变量可被推断,然后用于消除有限状态机中的命令歧义。在推断复杂属性或任意半结构化数据时,这种效果是有限的。这些方法具有适用于黑盒接口的优点。但是他们没有利用遗留单元测试提供的依赖性信息。另一方面,显示了与本文中使用的数据相似的数据推断。但是,控制依赖性是直接从数据依赖性推断的,因为示例不用作算法的输入。

此外,本工作中使用的合并算法受以前的常规推理算法的强烈影响,特别是K-tails和QSM。我们使用QSM作为我们以前的测试生成工作的核心算法,但本文介绍的工作与之不同之处在于我们现在将数据依赖性结合在模型上。这种添加使它能够传达被测系统的各个方面,这些方面超出了纯粹的常规推理可以学习的方面。

最近有关软件逆向工程的更多工作使用常规推理,甚至在机器学习的帮助下进行EFSM推理。

解决方案的架构:

如上图所示,我们展示了我们设计和实现的工具的架构。

JVM由C ++中的JVMTI代理检测,该代理检测每个方法入口和方法退出事件,并通过套接字将其报告给Erlang服务器。实际上,方法条目对应于方法调用,方法出口允许我们跟踪方法执行的结果。

此过程会生成一长串方法调用,其中大多数不属于测试本身,而是属于框架(例如Apache Ant库)或JVM本身。Erlang服务器过滤掉大多数不属于测试的调用。我们通过使用Java的反射API检查注释来完成此操作。但是我们在缓存中存储了不包含JUnit测试的类(否则会带来很大的开销)。

此过程还用于区分设置和清理过程以及实际测试主体,因为它们具有不同的注释。

必须跟踪产生在测试中使用的对象的调用,即使它们不是测试本身的一部分,否则James将不知道在生成新测试时如何创建这些对象。

我们的方法存在一些局限性。 James可以跟踪对象,但并非Java中的每个变量都是对象。一些变量具有原始类型(例如:int,char,boolean),JVMTI无法直接跟踪它们。像+或&&这样的运算符也与方法区别对待。

我们当前的实现是通过识别重复值来跟踪基元;但是在处理频繁使用的基元(如false和0)会不准确。

通过使用动态字节码修改分别用对象和函数替换基元和运算符,或者通过使用静态分析来检测原始值的数据流,可以避免这两个问题。但由于James是作为原型而构建的,我们通过手动替换基元来绕过问题。

即使对于普通方法,JVMTI可以检索的信息量取决于代码是否使用调试信息进行编译。 为了获得更有用的系统,我们选择使用提取依赖于JVMTI方法的信息的方法,这些方法也可以处理未使用调试信息编译的Java代码。

一个概念上的限制是,在我们的方法中,只跟踪发出HTTP请求的方法的控制依赖关系。这意味着该模型不会考虑其他方法产生的副作用的后果。将来,这种方法可以扩展到涵盖其他方法。

在之前的研究中已经报告的动态方法的一般问题是由Java程序的工具产生的大量跟踪,这导致针对相对较小的测试套件的分析需要大量的内存并且减慢了进程。如前所述,通过仔细过滤所收集的痕迹可以缓解这个问题。

可以通过确保所有流量通过代理并将代理连接到JVMTI代理来执行识别发出HTTP请求的方法的任务。然而,这种方法需要在每个方法调用的JVMTI代理和代理之间进行上下文更改,这会引入延迟,从而减慢整个过程并增加其复杂性。

相反,我们跟踪产生HTTP请求的Java方法。在我们的例子中,使用的方法是来自类HttpURLConnection的openConnection和setRequestMethod。其他程序可以使用不同的方法,但James可以很容易地调整,以检测它们。

详细示例:在本节中,我们将详细讨论通过在频率服务器示例上运行我们的James工具来应用我们的模型提取方法的结果,这也用于我们在Erlang / EUnit的模型提取的原始工作中。完全提取的机制如下图所示:

频率服务器是一个使用Java编写的Web服务,受到“Erlang编程”一书中的示例的启发。它模拟了一个“频谱管理”系统,允许客户分配和释放频率,同时确保每个频率最多分配一个频率我们已经使用此示例的原始版本来说明将EUnit测试转换为PBT模型的工具。API提供了四个命令:startServer,stopServer,allocateFrequency和deallocateFrequency。上图说明了James工具从一组单元测试中推断出的频率服务器的行为。

测试套件由独立方提供并且可用,所使用的SUT的实现也可在同一链路中访问。通过使用James生成的模型,我们可以生成新的相关测试,以探索原始测试中缺少的可能性。例如,在我们的特定实现中,可以分配的频率数量有限制,但现有单元测试未探讨此限制。

然而,随机测试发生器将随机遍历我们模型的控制流,可以尝试分配足够的频率来实现,因为在分配命令周围有一个控制回路。在某些时候,服务器将返回错误。即使在这种情况下,频率数量的限制也是预期的功能,在一个更大的例子中,它可能是由于一个错误,而不是传统的单元测试揭示出来的。

同时查看控制和数据流,我们可以更好地了解系统的预期功能。例如,如果我们查看如下图中突出显示的图表,我们可以看到可以提取调用allocateFrequency的结果,并在以后调用deallocateFrequency时重用它。对deallocateFrequency的第一次调用应该是有效的。

但是,如果在执行此操作后,我们再次调用deallocateFrequency,如同上图所示,我们将产生一个错误,如deallocateFrequency节点中的粉红色背景所示。我们也可以通过使用整数0作为参数来获得错误结果,而不是使用allocateFrequency的结果(我们知道这是真的,因为在我们的实验中使用的频率服务器的实现开始从10分配频率)。

总结

本文介绍了一组生成模型的技术,这些模型结合了数据和控制流的信息,并使用该模型生成新的测试。这些技术已经通过从James工具的执行中提取的示例进行了测试和说明,并且已经在涉及工业Web服务的试点研究中进行了测试。

我们已经展示了如何从JUnit测试套件中提取控制流和数据流信息,并在James工具中实现了提取,结果可视化和自动测试生成。

对于未来,另一个研究方向是从JUnit测试套件构建模型,而无需系统的实现。未来的工作还可以通过应用现有技术(如主动学习和不变推理)来提高生成模型的准确性和表现力。

致谢

此文由南京大学软件学院2018级硕士李林昱翻译转述。