面向关键字流图的相似程序间测试用例的重用  

Reuse of Test Cases Between Similar Programs Based on Keyword Flow Graph

作　　者：钱忠胜[1] 宋涛 QIAN Zhong-Sheng;SONG Tao(School of Information Management,Jiangxi University of Finance and Economics,Nanchang 330013,China)

机构地区：[1]江西财经大学信息管理学院,江西南昌330013

出　　处：《软件学报》2021年第9期2691-2712,共22页Journal of Software

基　　金：国家自然科学基金(61762041);江西省自然科学基金(20181BAB202009);江西省教育厅科技重点项目(GJJ180250)。

摘　　要：软件测试是软件开发中重要的一环,能有效地提高软件的可靠性和质量.而测试用例的重用可减少软件测试的工作量,提升测试的效率.提出一种面向关键字流图的相似程序间测试用例的重用方法,该方法将程序已经生成的测试数据重用到与之相似的程序中.可见,探究测试用例重用的前期工作是判定程序的相似性.对于程序相似性的判定,给出根据关键字流图相似性比较的方法:首先,将程序代码中的关键字存储在流图所对应的节点中,构建关键字流图;接下来,利用动态规划算法查找待测程序关键字流图的最大公共子图;最后,根据最大公共子图距离算法计算程序的相似度.较高相似程度的程序可用到测试用例重用的方法中.在利用遗传算法生成测试用例时,引用相似程序中适应度较高的测试用例,使种群在进行进化操作过程中不断与这些用例进行交叉,加快用例的生成效率.实验表明:将测试用例重用在相似程序的测试生成中,与传统方法相比,在覆盖率和平均进化代数等方面均有明显优势.Software testing is an important part of software development,which can effectively improve software reliability and its quality.The reuse of test cases can improve the efficiency of testing and reduce the workload of software testing.Therefore,an approach to test case reuse between similar programs based on keyword flow graph is proposed.The method reuses test data generated by programs to their similar programs.Thus,the first step in exploring reuse of test cases is to determine similarities between programs.To determine the similarity of programs,a comparison method of similarity based on keyword flow graph is given.Firstly,the keywords in the program code are stored in the nodes corresponding to the flow graph to construct the keyword flow graph.Then,the maximum common sub-graph of keyword flow graph of the maximum programs tested is searched by using dynamic programming algorithm.Finally,the similarity of the programs is computed according to the common sub-graph distance algorithm.Programs with a high similarity can be used with test case reuse methods.In utilizing genetic algorithm to generate test cases,the test cases with high fitness of similar programs are selected.To speed up the efficiency of test case generation,the population intersects with these test cases continuously in the process of evolution.Experiments show that the reuse of test cases in test generation of similar programs has obvious advantages over traditional methods in terms of coverage and average evolution times.

关 键 词：流图 程序相似性 遗传算法 测试用例重用 最大公共子图 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]