Page 67 - 《软件学报》2021年第9期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(9):2691−2712 [doi: 10.13328/j.cnki.jos.005984] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

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

钱忠胜, 宋 涛

(江西财经大学 信息管理学院,江西 南昌 330013)
通讯作者: 钱忠胜, E-mail: changesme@163.com

摘 要: 软件测试是软件开发中重要的一环,能有效地提高软件的可靠性和质量.而测试用例的重用可减少软件
测试的工作量,提升测试的效率.提出一种面向关键字流图的相似程序间测试用例的重用方法,该方法将程序已经生
成的测试数据重用到与之相似的程序中.可见,探究测试用例重用的前期工作是判定程序的相似性.对于程序相似性
的判定,给出根据关键字流图相似性比较的方法:首先,将程序代码中的关键字存储在流图所对应的节点中,构建关
键字流图;接下来,利用动态规划算法查找待测程序关键字流图的最大公共子图;最后,根据最大公共子图距离算法
计算程序的相似度.较高相似程度的程序可用到测试用例重用的方法中.在利用遗传算法生成测试用例时,引用相似
程序中适应度较高的测试用例,使种群在进行进化操作过程中不断与这些用例进行交叉,加快用例的生成效率.实验
表明:将测试用例重用在相似程序的测试生成中,与传统方法相比,在覆盖率和平均进化代数等方面均有明显优势.
关键词: 关键字流图;程序相似性;遗传算法;测试用例重用;最大公共子图
中图法分类号: TP311

中文引用格式: 钱忠胜,宋涛.面向关键字流图的相似程序间测试用例的重用.软件学报,2021,32(9):2691−2712. http://www.
jos.org.cn/1000-9825/5984.htm
英文引用格式: Qian ZS, Song T. Reuse of test cases between similar programs based on keyword flow graph. Ruan Jian Xue
Bao/Journal of Software, 2021,32(9):2691−2712 (in Chinese). http://www.jos.org.cn/1000-9825/5984.htm

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

QIAN Zhong-Sheng, SONG Tao
(School of Information Management, Jiangxi University of Finance and Economics, Nanchang 330013, China)
Abstract: 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.
Key words: keyword flow graph; program similarity; genetic algorithm; test case reuse; maximum common sub-graph

∗ 基金项目: 国家自然科学基金(61762041); 江西省自然科学基金(20181BAB202009); 江西省教育厅科技重点项目(GJJ180250)
Foundation item: National Natural Science Foundation of China (61762041); Jiangxi Provincial Natural Science Foundation of
China (20181BAB202009); Key Project of Science and Technology of Jiangxi Provincial Department of Education of China (GJJ180250)
收稿时间: 2019-01-03; 修改时间: 2019-07-09, 2019-10-28; 采用时间: 2019-12-02