Journal of Frontiers of Computer Science and Technology ›› 2024, Vol. 18 ›› Issue (4): 947-962.DOI: 10.3778/j.issn.1673-9418.2301018

• Theory·Algorithm • Previous Articles     Next Articles

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

QIAN Zhongsheng, SUN Zhiwang, YU Qingyuan, QIN Langyue, JIANG Peng, WAN Zilong, WANG Yahui   

  1. School of Information Management, Jiangxi University of Finance and Economics, Nanchang 330013, China
  • Online:2024-04-01 Published:2024-04-01

基于路径相似表与个体迁移策略的多路径覆盖测试

钱忠胜,孙志旺,俞情媛,秦朗悦,蒋鹏,万子珑,王亚惠   

  1. 江西财经大学 信息管理学院,南昌 330013

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%,故该方法有效地提高了测试效率。

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