【作者】 游亮；

【导师】 卢炎生；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2012， 博士

【摘要】 在软件的开发和维护过程中,为了增强软件的功能和修正软件的错误,需要对软件进行变更。变更完成后,为了验证变更的效果,需要对于软件系统进行回归测试。传统上,回归测试就是重新运行回归测试用例集的测试过程。回归测试是非常昂贵的,回归测试优化技术是一种节省回归测试高昂花费的优化技术。回归测试用例选择技术是最重要的回归测试优化技术。回归测试用例选择技术计算出程序新旧版本之间的变更,选择所有覆盖了变更部分的回归测试用例,计算出回归测试用例选择集。回归测试的过程不再是重新运行回归测试用例集,而是重新运行回归测试用例选择集。通过减少重新运行的回归测试用例的数量来节省回归测试过程的花销。Java虚拟机的兴起、基于构件的开发范式和持续集成的广泛应用对回归测试用例选择技术提出了新的挑战。为了应对这些新挑战,新一代的回归测试用例选择算法必须是基于字节码的、满足增量性质的和支持面向对象特性。基于对完整Java字节码指令集的分析,提出了一种无需Java源代码,直接基于Java字节码构造控制流图的算法。并且基于字节码直接构造的控制流图,提出了一种基于字节码控制流图的回归测试用例选择算法。基于字节码控制流图的回归测试用例选择算法直接分析程序新旧版本的字节码,构造出新旧版本的控制流图。然后对比新旧版本的控制流图,计算出程序的变更。最后,将所有覆盖了程序变更部分的回归测试用例加入回归测试用例选择集。该算法无需源代码,支持完整的Java字节码指令集,特别是支持Java特有的异常特性。Java程序中类型之间的继承关系和使用关系构成了类型之间的依赖关系。基于自动构造和维护的依赖关系,提出了一种Java语言的增量编译算法。相比于完全编译算法,增量编译算法能够最大限度的减少不必要的重新编译过程。进一步,基于Java语言的增量编译算法,提出了一种类层次的回归测试用例选择算法。由于增量编译算法输出的所有重新编译输出的字节码文件集合代表着程序的变更部分。因此,类层次的回归测试用例选择算法只需选择出所有覆盖了程序变更部分的回归测试用例,将其加入回归测试用例选择集。类层次回归测试用例选择算法不仅支持Java面向对象中的继承等特性,而且满足增量性质。算法的时间复杂度不再正比于程序的总规模,而是正比于程序新旧版本之间的变更规模。一般说来,由于程序的总规模很大,变更规模很小。所以具有增量性质的回归测试用例选择算法运算效率高。不管是基于字节码控制流图的回归测试用例选择算法,还是类层次回归测试用例选择算法,都需要计算出程序新旧版本之间基于语法的变更。提出了一种基于语法的变更算法,能够计算Java程序新旧版本字节码之间基于语法的变更。该算法首先将Java程序新旧版本的字节码直接转化为XML数据结构,然后对比新旧版本的XML数据结构,最后计算出基于语法的变更。不同于将源代码简单的看作是文本文件,使用文本行的增加、删除和更新作为程序新旧版本之间变更结果的传统变更算法。基于语法的变更算法没有忽略Java程序的语法信息,基于语法的变更结果适合回归测试用例选择算法的需要。此外,还提出了将基于语法的变更结果进一步分解为原子变更的方法,并且分析了Java语言原子变更的二进制兼容性和源代码兼容性。更多还原

【Abstract】 During the develop phase and maintain phase of the software project, it need change software to enhance the functionality and fix the bugs of the software project. After the programmer finishes the coding works for the new version software, it need run regression testing for validating the diff between the old version and new version software. In general, the regression testing process rerun all test cases in the regression testing suite. But the regression testing is the expensive phase of the software testing, the optimization regression testing techniques can save the total costs of the regression testing.The regression testing selection(RTS) is the most important technique in the optimization regression testing techniques. The regression testing selection technique diffs between the old version and new version software, and selects all test cases into the selected regression testing suite that cover the diff portions of the software. The process of optimization regression testing do not rerun all test cases in the regression testing suite, but only rerun the selected regression testing suite. The optimization regression testing saves the total costs by saving the numbers of rerunning test cases.The booming of the Java virtual machine platform and the rapid rate of adoption of the component-based development and continuous integration set new challenges for the regression testing selection techniques. To tackle these three new challenges, the new regression testing techniques must have bytecode-based, incremental and object-oriented properties.Based on the analysis for the full Java bytecode instructions set, this paper presents a bytecode based algorithm to compute the Control Flow Graph(CFG). The CFG algorithm does not need Java source code and can directly compute CFG from Java bytecode. It also presents a CFG-based regression testing selection algorithm. The CFG-based regression testing selection algorithm directly analyzes the bytecode of the old version and new version of the software, and then compute control flow graphs. It compares the old version and new version control flow graphs of the software and outputs the diff. Finally, it selects all test cases in the regression testing suite that cover the diff portions of the software and outputs the selected regression testing suite. The algorithm supports full Java bytecode instructions set and does not need the source code of the software, especially it supports the exception feature of the Java programming language.The dependency relationship is composed of the inheritance relationship and use relationship in the Java programming language. Based on the automatically created and updated dependency relationship information, this paper presents an incremental compilation algorithm for the Java programming language. Comparing with the batch compilation algorithm, the incremental compilation algorithm can avoid redundant recompilation works to save total compilation costs. Based on the Java incremental compilation algorithm, it presents a class level regression testing selection algorithm. Because the incremental compilation algorithm outputs all recompiled bytecode files that is composed of the class level diff between old version and new version of the software, the class level regression testing selection algorithm only selects all test cases in the regression testing suite that cover the diff portions of the software and output selected regression testing suite. The class level regression testing selection algorithm not only supports the inheritance feature of the object-oriented Java programming language but also have incremental property. The cost of the class level regression testing selection algorithm is proportion with the size of diff portions between old version and new version of the software and is not proportion with the total size of the software. Because the size of diff is much smaller than the total size of the software in general, so the class level regression testing selection algorithm has incremental property and is more efficient that the batch algorithm.The control flow graph based regression testing selection algorithm and class level regression testing algorithm both need syntax based diff between the old version and new version of the software. This paper presents a syntax based diff algorithm that output the difference of the old version and new version in bytecode format. The syntax based diff algorithm converts the old version and new version bytecode into the XML data structure at first, and then compares the old version and new version XML data structures and outputs the syntax based diff. The non syntax based diff algorithm only assumes the Java program to be the simple text files and totally ignores the syntax information of the Java programming language. The non syntax based diff algorithm outputs non syntax diff that is composed of inserted, deleted and changed text lines. But the syntax diff algorithm outputs syntax diff that contains full Java syntax information and fulfills the needs of the regression testing selection algorithms. It also presents the method that decomposes the syntax diff into atomic change set, and also analyzes the differences of the binary compatibility and source compatibility of the atomic change.更多还原