基于多样性原理的面向对象程序测试中蜕变关系生成与复用技术研究

Metamorphic testing has attracted great attention since it can effectively alleviate the Oracle (i.e., excepted output results) problem in software testing. Although this method is a good way to avoid the Oracle problem, it also leads to the difficulty in the construction of metamorphic relations. Guided by the principle of diversity, this project attempts to explore the techniques on the automated generation and reuse of metamorphic relations for Object-Oriented programs metamorphic testing. For the complex data types such as objects in method (or function) parameters, the set of mutation rules for the corresponding input data is defined firstly, and then the metamorphic relation generation algorithm based on dynamic detection of invariants will be proposed. In the system-level testing, the research emphasizes the metamorphic relation generation in the case of nonequivalent object states. The intelligent searching and frequent pattern mining techniques will be used to build the metamorphic relations in the form of the pair of method invocation sequences. With regard to metamorphic relation reuse, a recommendation algorithm based on collaborative filtering will be presented for suggesting the cross-program metamorphic relations. In the above solution, the similarity between two program modules is measured by means of topic model. In addition, in order to keep the diversity of selected metamorphic relations for testing the evolved programs, the prioritization problem of metamorphic relations and its solution about multi-objective optimization are both proposed. In a word, the above researches will enrich the methods for metamorphic testing and expand its application fields.

蜕变测试因能有效地减轻软件测试中的Oracle(预期输出结果)问题而引起广泛关注。虽然该方法巧妙地规避了人工指定Oracle的麻烦，但也引出了蜕变关系的构造难题。本项目试图在多样性原理的指导下，探索面向对象程序蜕变测试中蜕变关系的自动生成与复用技术。针对方法参数包含对象型等复杂数据类型，设计对应的输入数据变异规则集，进而提出基于不变式动态检测的蜕变关系生成算法。针对系统级别的测试，重点探讨在对象状态非等价关系情形下的蜕变关系生成问题，拟在智能搜索、频繁模式挖掘等技术的支持下构造形如“方法调用序列对”的蜕变关系。在蜕变关系的复用方面，拟基于语义主题模型计算程序模块之间的功能或特征相似性，进而给出跨程序条件下蜕变关系的协同过滤推荐算法。此外，还通过蜕变关系优先级的多目标建模与求解，实现在程序演化背景下的蜕变关系最大差异化复用。总之，上述研究将有助于进一步丰富蜕变测试的方法体系、拓展其应用领域。

面向对象程序设计范式因具有良好的封装、继承与多态特性而被广泛采用，目前面向对象程序已经成为工程计算、电子商务、人工智能等领域的主流软件形态。然而，这类程序的控制逻辑更加复杂、数据格式更为多样，因此它们的测试数据与测试预言生成问题变得特别困难。本项目以Java和Python语言实现的面向对象程序作为研究对象，重点探讨了该类程序蜕变测试中的三个核心问题。. 在项目研究过程中，以“多样性”(diversity)作为基本准则来设计蜕变关系或测试数据的生成算法。以智能商务领域的推荐系统为例，研究蜕变关系生成方法，深入分析矩阵作为输入的数据处理系统的特点，提出了交换、倍乘、增量、取反和重复等五个方面的蜕变关系生成启发式规则。同时，针对以字符串类型作为输入参数的面向对象程序，设计了一种基于等价方法操作序列检测的蜕变关系生成方法。. 在蜕变测试初始输入数据生成方面，充分利用KD-tree能够显著降低候选点最近邻查询代价的优点，通过平衡该查询的准确性与代价，设计了三种基于距离的适应性随机测试(ART)改进算法。另外，综合基于随机划分的ART(RP-ART)和迭代划分测试(IPT)这两种方法的优点提出了一种基于柔性划分的ART方法。. 在蜕变关系复用方面，分别对方法头部、方法体代码以及注释语句开展词法、语义分析，基于深度学习模型解析出关于方法级别程序的特征向量模型。在此基础上，运用基于协同过滤模型的推荐技术来构建面向方法级程序代码的蜕变关系复用算法。进一步地，针对部分程序没有注释信息的特点，探索了基于代码注释信息自动生成的蜕变关系推荐方法。. 本项目针对数据分析与处理、商务智能领域的面向对象程序，围绕蜕变测试中的蜕变关系生成、测试数据生成、蜕变关系推荐三个方面开展了深入研究。相较于当前的一些代表性方法，所提出的蜕变关系或测试数据生成算法展示了明显的先进性与高效的计算效率。