Approach to Multi-path Coverage Testing Based on Path Similarity Table and Individual Migration

doi:10.3778/j.issn.1673-9418.2301018

Abstract

Abstract: The application of genetic algorithm in multi-path coverage testing is a research hotspot. In the process of iteration between the old and new populations, the old population may contain excellent individuals from other sub-populations, which are not fully utilized, resulting in resource waste. At the same time, the number of individuals in the population will be much greater than that of reachable paths, and each individual will go through a reachable path. This causes multiple individuals to pass through the same path, leading to repeated calculation of the similarity between the individual and the target path. Based on this, a multi-path coverage testing method combined with path similarity table and individual migration is proposed to improve testing efficiency. By storing the calculated path similarity value in the path similarity table, the value can be avoided from being calculated repeatedly and the testing time can be reduced. In the evolutionary process, the individual path is compared with other target paths, and if the similarity reaches the threshold, the excellent individual is migrated to the sub-population corresponding to the path, which improves the utilization rate of individuals and reduces the evolutionary generation. Experiments show that, compared with other six classic methods, the proposed method reduces the average generation time on eight programs by up to 44.64%, and the minimum is 2.64%, and the average evolution generation is reduced by up to 35.08%, and the minimum is 6.13%. Therefore, the proposed method effectively improves the test efficiency.

Key words: test case, path similarity table, individual migration, multi-path coverage, multi-population genetic algorithm

摘要： 将遗传算法用于多路径覆盖测试中是个研究热点，在新旧种群迭代过程中，旧种群中可能包含其他子种群的优秀个体，这部分个体未被充分利用，造成资源浪费；同时，种群中的个体数会远大于可达路径数，而每个个体都会经过某一条可达路径，这样会有多个个体经过同一条路径，导致重复计算个体与目标路径的相似度。基于此，提出结合路径相似表与个体迁移的多路径覆盖测试方法以提高测试效率。通过路径相似表存储已计算得到的路径相似度值，避免该值被重复计算，减少测试时间。在进化过程中，将个体路径与其他目标路径进行比较，若相似度达到阈值，则将此优秀个体迁移至该路径对应的子种群中，提高个体利用率并减少进化代数。由实验可知，该方法与其他六种同类经典方法在八个程序上的平均生成时间降低最高达44.64%，最低为2.64%，平均进化代数降低最高达35.08%，最低为6.13%，故该方法有效地提高了测试效率。

关键词: 测试用例, 路径相似表, 个体迁移, 多路径覆盖, 多种群遗传算法

QIAN Zhongsheng, SUN Zhiwang, YU Qingyuan, QIN Langyue, JIANG Peng, WAN Zilong, WANG Yahui. Approach to Multi-path Coverage Testing Based on Path Similarity Table and Individual Migration[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(4): 947-962.

钱忠胜, 孙志旺, 俞情媛, 秦朗悦, 蒋鹏, 万子珑, 王亚惠. 基于路径相似表与个体迁移策略的多路径覆盖测试[J]. 计算机科学与探索, 2024, 18(4): 947-962.

References

[1] LIU S Y, NAKAJIMA S. Automatic test case and test oracle generation based on functional scenarios in formal specifications for conformance testing[J]. IEEE Transactions on Software Engineering, 2022, 48(2): 691-712.
[2] TIUTIN C M, VESCAN A. Test case priortization based on neural networks classification[C]//Proceedings of the 2nd ACM International Workshop on AI and Software Testing/Analysis, Korea, Jul 18, 2022. New York: ACM, 2022: 9-16.
[3] 姚香娟. 复杂软件测试数据进化生成理论及应用[D]. 徐州: 中国矿业大学, 2011.
YAO X J. Theory of evolutionary generation of test data for complex software and applications[D]. Xuzhou: China University of Mining and Technology, 2011.
[4] 廖伟志, 夏小云, 贾小军. 基于蚁群算法的多路径覆盖测试数据生成[J]. 电子学报, 2020, 48(7): 1330-1342.
LIAO W Z, XIA X Y, JIA X J. Test data generation for multiple paths coverage based on ant colony algorithm[J]. Acta Electronica Sinica, 2020, 48(7): 1330-1342.
[5] SHARIFIPOUR H, SHAKERI M, HAGHIGHI H. Structural test data generation using a memetic ant colony optimization based on evolution strategies[J]. Swarm & Evolutionary Computation, 2018, 40(6): 76-91.
[6] LV X W, HUANG S, HUI Z W, et al. Test cases generation for multiple paths based on PSO algorithm with metamorphic relations[J]. IET Software, 2018, 12(4): 306-317.
[7] PANDEY A, BANERJEE S. Test data generation and selection using Levy flight-based firefly algorithm[J]. International Journal of Software Innovation, 2021, 9(2): 18-34.
[8] 高凤娟, 王豫, 司徒凌云, 等. 基于深度学习的混合模糊测试方法[J]. 软件学报, 2021, 32(4): 988-1005.
GAO F J, WANG Y, SITU L Y, et al. Deep learning-based hybrid fuzz testing[J]. Journal of Software, 2021, 32(4): 988-1005.
[9] 姚香娟, 巩敦卫, 李彬. 融入神经网络的路径覆盖测试数据进化生成[J]. 软件学报, 2016, 27(4): 828-838.
YAO X J, GONG D W, LI B. Evolutional test data generation for path coverage by integrating neural network[J]. Journal of Software, 2016, 27(4): 828-838.
[10] JATANA N, SURI B. Particle swarm and genetic algorithm applied to mutation testing for test data generation: a comparative evaluation[J]. Journal of King Saud University-Computer and Information Sciences, 2020, 2(4): 514-521.
[11] SKOCELAS K G, DEVRIES B. Test data generation for recurrent neural network implementations[C]//Proceedings of the 2020 IEEE International Conference on Electro Information Technology, Chicago， Jul 31-Aug 1, 2020. Piscataway: IEEE, 2020: 469-474.
[12] 张岩, 巩敦卫. 基于稀有数据扑捉的路径覆盖测试数据进化生成方法[J]. 计算机学报, 2013, 36(12): 2429-2440.
ZHANG Y, GONG D W. Evolutionary generation of test data for paths coverage based on scarce data capturing[J]. Chinese Journal of Computers, 2013, 36(12): 2429-2440.
[13] 丁蕊, 董红斌, 张岩, 等. 基于关键点路径的快速测试用例自动生成方法[J]. 软件学报, 2016, 27(4): 814-827.
DING R, DONG H B, ZHANG Y, et al. Fast automatic generation method for software testing data based on key-point path[J]. Journal of Software, 2016, 27(4): 814-827.
[14] 夏春艳, 张岩, 宋丽. 基于节点概率的路径覆盖测试数据进化生成[J]. 软件学报, 2016, 27(4): 802-813.
XIA C Y, ZHANG Y, SONG L. Evolutionary generation of test data for paths coverage based on node probability[J]. Journal of Software, 2016, 27(4): 802-813.
[15] PRADHAN D, SHUAI W, ALI S, et al. CBGA-ES+: a cluster-based genetic algorithm with non-dominated elitist selection for supporting multi-objective test optimization[J]. IEEE Transactions on Software Engineering, 2021, 47(1): 86-107.
[16] NOSRATI M, HAGHIGHI H, ASL M V. Test data generation using genetic programming[J]. Information and Software Technology, 2021, 130(4): 106446.
[17] 钱忠胜, 俞情媛, 宋涛, 等. 基于支持向量机回归模型的测试用例生成与重用[J]. 电子学报, 2021, 49(7): 1386-1391.
QIAN Z S, YU Q Y, SONG T, et al. Test case generation and reuse based on support vector machine regression model[J]. Acta Electronica Sinica, 2021, 49(7): 1386-1391.
[18] QIAN Z S, HONG D F, ZHAO C, et al. A strategy for multi-target paths coverage by improving individual information sharing[J]. KSII Transactions on Internet and Information Systems, 2019, 13(11): 5464-5488.
[19] 钱忠胜, 祝洁, 俞情媛, 等. 基于关键点概率与路径相似度的多路径覆盖进化测试策略[J]. 软件学报, 2022, 33(2): 434-454.
QIAN Z S, ZHU J, ZHU Y M, et al. Multi-path coverage strategy combining key point probability and path similarity[J]. Journal of Software, 2022, 33(2): 434-454.
[20] 范书平, 张岩, 马宝英, 等. 基于均衡优化理论的路径覆盖测试数据进化生成[J]. 电子学报, 2020, 48(7): 1303-1310.
FAN S P, ZHANG Y, MA B Y, et al. Evolutionary generation of test data for paths coverage based on balance optimization theory[J]. Acta Electronica Sinica, 2020, 48(7): 1303-1310.
[21] 杜莹, 孙百才, 巩敦卫, 等. 软件测试路径选择优化模型及其进化求解[J]. 软件学报, 2022, 33(9): 3297-3311.
DU Y, SUN B C, GONG D W, et al. Optimization model of path selection for software testing and its evolution-based solution[J]. Journal of Software, 2022, 33(9): 3297-3311.