利用函数影响力的相似程序间测试用例重用与生成

doi:10.12263/DZXB.20210953

摘要/Abstract

摘要：

在回归测试过程中，用例重用是一项很重要的工作，其充分利用软件升级变更前的已有资源，提高测试的效率.从已有研究来看，回归测试的研究大部分侧重于用例优化方面，少部分提到利用程序升级变更前后的相似性来重用测试用例以提高用例生成效率.针对回归测试用例重用问题，提出一种重用变更前相似程序的测试信息，并通过设计的适应度函数为变更后程序进化生成新用例的方法.该方法利用构建的函数调用图进行程序相似部分的检测，并根据函数影响力设计适应度函数来调整个体的适应度值，保留适应度值高的优秀个体；再通过重用变更前相似部分的用例，以及进化生成的变更后的部分用例，来构成回归测试中新程序的用例.实验结果表明，在目标路径覆盖率上，对于中小规模和大规模工业程序，本文方法比经典方法分别可提高8%和17%.

关键词: 测试用例, 程序相似性, 函数影响力, 关键函数, 回归测试

Abstract:

In the process of regression testing, the reuse of test cases is a critical activity. It makes full use of the resources before updating the software to improve the efficiency of software testing. According to the existing results, most of them on regression testing focus on the test case prioritization, and a few mention the use of similarity before and after the programs upgrade changes to reuse test cases to improve the efficiency of test case generation. Aiming at the test case reuse in regression testing, this paper proposes an approach to reuse test data of similar programs before the change, and employs the fitness function designed to evolve to generate new test cases for the program after the change. It utilizes the function call graph constructed to detect similar parts of the programs. And according to the function influence, the fitness function is designed to adjust the fitness value of the individual, and excellent individuals with high fitness value are retained. Then, it reuses the test cases of the similar part before the change and the part of the test cases generated in the evolutionary process after the change, to form the test cases of the new program in the regression test. The experimental results show that, compared to the classical methods, the target path coverage rate of the proposed method is increased by 8% and 17% for small- and medium-sized, and large-sized industrial programs, respectively.

Key words: test case, program similarity, function influence, key function, regression test

中图分类号:

TP311

钱忠胜, 宋佳, 俞情媛, 成轶伟, 孙志旺. 利用函数影响力的相似程序间测试用例重用与生成[J]. 电子学报, 2022, 50(7): 1696-1707.

QIAN Zhong-sheng, SONG Jia, YU Qing-yuan, CHENG Yi-wei, SUN Zhi-wang. Test Case Reuse and Generation Between Similar Programs Based on Function Influence[J]. Acta Electronica Sinica, 2022, 50(7): 1696-1707.

图/表 12

参考文献 18

1	DI NUCCID, PANICHELLAA, ZAIDMANA, et al. A test case prioritization genetic algorithm guided by the hypervolume indicator[J]. IEEE Transactions on Software Engineering, 2020, 46(6): 674-696.
2	PEIHan-yu, YINBei-bei, XIEMin, et al. Dynamic random testing with test case clustering and distance-based parameter adjustment[J/OL]. Information and Software Technology, 2021, 131: 106470. .
3	NAIRA, ROYA, MEINKEK. funcGNN: A graph neural network approach to program similarity[C]//ESEM'20: Proceedings of the 14th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement(ESEM). New York, USA: ACM, 2020: 1-11.
4	李玫, 高庆, 马森, 等. 面向代码相似性检测的相似哈希改进方法[J]. 软件学报, 2021, 32(7): 2242-2259.
	LIMei, GAOQing, MASen, et al. Enhanced simhash algorithm for code similarity detection[J]. Journal of Software, 2021, 32(7): 2242-2259. (in Chinese)
5	刘芳, 李戈, 胡星, 等. 基于深度学习的程序理解研究进展[J].计算机研究与发展, 2019, 56(8): 1605-1620.
	LIUFang, LIGe, HUXing, et al. Program comprehension based on deep learning[J]. Journal of Computer Research and Development, 2019, 56(8): 1605-1620. (in Chinese)
6	ZHANGB, SHANC, HUSSAINM, et al. Software crucial functions ranking and detection in dynamic execution sequence patterns[J]. International Journal of Software Engineering and Knowledge Engineering, 2020, 30(5): 695-719.
7	夏春艳, 张岩, 万里, 等. 基于否定选择遗传算法的路径覆盖测试数据生成[J]. 电子学报, 2019, 47(12): 2630-2638.
	XIAChun-yan, ZHANGYan, WANLi, et al. Test data generation of path coverage based on negative selection genetic algorithm[J]. Acta Electronica Sinica, 2019, 47(12): 2630-2638. (in Chinese)
8	王曙燕, 王瑞, 孙家泽. 基于改进细菌觅食算法的测试用例生成方法[J]. 计算机应用, 2019, 39(3): 845-850.
	WANGShu-yan, WANGRui, SUNJia-ze. Test case generation method based on improved bacterial foraging optimization algorithm[J]. Journal of Computer Applications, 2019, 39(3): 845-850. (in Chinese)
9	夏春艳, 张岩, 宋丽. 基于节点概率的路径覆盖测试数据进化生成[J]. 软件学报, 2016, 27(4): 802-813.
	XIAChun-yan, ZHANGYan, SONGLi. Evolutionary generation of test data for paths coverage based on node probability[J]. Journal of Software, 2016, 27(4): 802-813. (in Chinese)
10	姚香娟, 巩敦卫, 李彬. 融入神经网络的路径覆盖测试数据进化生成[J]. 软件学报, 2016, 27(4): 828-838.
	YAOXiang-juan, GONGDun-wei, LIBin. Evolutional test data generation for path coverage by integrating neural network[J]. Journal of Software, 2016, 27(4): 828-838. (in Chinese)
11	ZHAOG, HUANGJ. DeepSim: Deep learning code functional similarity[C]//ESEC/FSE 2018: Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. New York, USA: ACM, 2018: 141-151.
12	LIUB C, HUOW, ZHANGC, et al. αDiff: cross-version binary code similarity detection with DNN[C]//ASE 2018: Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering.New York, USA: ACM, 2018: 667-678.
13	汪洁, 王长青. 子图相似性的恶意程序检测方法[J]. 软件学报, 2020, 31(11): 3436-3447.
	WANGJie, WANGChang-qing. Malware detection method based on subgraph similarity[J]. Journal of Software, 2020, 31(11): 3436-3447. (in Chinese)
14	MUY M, GAOX X, SHENM E. Research of reuse technology of test case based on function calling path[J]. Chinese Journal of Electronics, 2018, 27(4): 768-775.
15	钱忠胜, 俞情媛, 宋涛, 等. 基于支持向量机回归模型的测试用例生成与重用[J]. 电子学报, 2021,49(7): 1386-1391.
	QIANZhong-sheng, YUQing-yuan, SONGTao, et al. Test case generation and reuse based on support vector machine regression model[J]. Acta Electronica Sinica, 2021, 49(7): 1386-1391. (in Chinese)
16	廖伟志, 夏小云, 贾小军. 基于蚁群算法的多路径覆盖测试数据生成[J]. 电子学报, 2020, 48 (7): 1330-1342.
	LIAOWei-zhi, XIAXiao-yun, JIAXiao-jun. Test data generation for multiple paths coverage based on ant colony algorithm [J]. Acta Electronica Sinica, 2020, 48 (7): 1330-1342. (in Chinese)
17	范书平, 张岩, 马宝英, 等. 基于均衡优化理论的路径覆盖测试数据进化生成[J]. 电子学报, 2020,48(7): 1303-1310.
	FANShu-ping, ZHANGYan, MABao-ying, et al. Evolutionary generation of test data for paths coverage based on balance optimization theory[J]. Acta Electronica Sinica, 2020,48(7): 1303-1310. (in Chinese)
18	BAJAJA, SANGWANO P. A survey on regression testing using nature-inspired approaches[C]//Proceedings of the 2018 4th International Conference on Computing Communication and Automation(ICCCA). Greater Noida, India: IEEE, 2018: 1-5.

程序编号	待测程序名称	函数个数	代码行数	目标路径数	主要变更类型	变更率
PG1	三角形判别算法	3	70	40	增加	21.4%
PG2	时间差算法	4	53	21	删除	18.9%
PG3	24点算法	8	278	76	修改	19.4%
PG4	九宫格算法	4	170	37	修改	15.8%

程序编号	待测程序名称	函数个数	代码行数	目标路径数	主要变更类型	变更率
PG1	三角形判别算法	3	70	40	增加	21.4%
PG2	时间差算法	4	53	21	删除	18.9%
PG3	24点算法	8	278	76	修改	19.4%
PG4	九宫格算法	4	170	37	修改	15.8%

程序编号		PG1	PG2	PG3	PG4
随机法	平均进化代数	124.3	87.2	156.5	200.0
	测试用例数量	1 036	867	3 531	4 835
	覆盖率/%	100	100	100	75
传统遗传法	平均进化代数	83.6	56.3	146.1	200.0
	测试用例数量	671	925	3 872	2 761
	覆盖率/%	100	100	100	92
本文方法	平均进化代数	49.0	49.4	14.7	99.3
	测试用例数量	472	573	265	1 273
	覆盖率/%	100	100	100	100

程序编号		PG1	PG2	PG3	PG4
随机法	平均进化代数	124.3	87.2	156.5	200.0
	测试用例数量	1 036	867	3 531	4 835
	覆盖率/%	100	100	100	75
传统遗传法	平均进化代数	83.6	56.3	146.1	200.0
	测试用例数量	671	925	3 872	2 761
	覆盖率/%	100	100	100	92
本文方法	平均进化代数	49.0	49.4	14.7	99.3
	测试用例数量	472	573	265	1 273
	覆盖率/%	100	100	100	100

程序编号	待测程序名称	函数个数	函数代码数	目标路径数	主要变更类型	变更率
PG5	Replace	3	98	10	修改	13.2%
PG6	Space	3	195	15	删除	26.1%
PG7	Gzip	2	239	47	增加	22.8%
PG8	Sed_Part	2	367	125	修改	17.3%
PG9	Flex_Part	2	1 103	233	修改	29.3%