基于蚁群算法的多路径覆盖测试数据生成

doi:10.3969/j.issn.0372-2112.2020.07.011

摘要/Abstract

摘要： 为了提高多路径覆盖测试数据的生成效率，研究了一种基于蚁群算法的多路径覆盖测试数据生成方法.首先给出蚁群算法的一种改进方法，该算法以蚂蚁对生成测试数据的重要性作为蚂蚁状态转移和蚂蚁路径变异的依据，以引导更多蚂蚁穿越小概率节点，提高测试数据生成效率.其次，根据改进的蚁群算法分别提出了基于单信息素表和多信息素表的多路径覆盖测试数据生成方法.在基于多信息素表的方法中，每条目标路径的信息素表均被用于其它路径测试数据的求解，而且蚁群算法运行一次即可求解多条目标路径的覆盖测试数据.最后对所提出方法的有效性和复杂度进行了理论分析.实验结果表明，与其它方法相比，基于多信息素表的测试数据生成方法能够有效地生成多路径覆盖测试数据.

关键词: 测试数据生成, 蚁群算法, 多路径, 路径覆盖, 蚂蚁珍贵度

Abstract: In order to improve the generation efficiency of multipath coverage test data,a novel method is proposed based on ant colony algorithm (ACO).Firstly,an improved ACO is developed.The importance of an ant to generate test data is considered as a factor for ant state transfer and path mutation.As a result,more ants are guided to traverse small probabilities node and the efficiency of test data generation is improved.Secondly,according to the improved ACO,test data generation of multipath coverage based on single pheromone table and multiple pheromone tables are proposed.In a multiple pheromones table based approach,the pheromone table of each target path is also used to generate test data for other target path,and the test data of multiple paths are generated by running ACO only once.Finally,the effectiveness and complexity of the proposed method are analyzed theoretically.Experimental results show that test data generation based on multi-pheromone tables can effectively generate multipath coverage test data compared with other methods.

Key words: test data generation, ant colony algorithm, multiple paths, path coverage, valuableness of ants

中图分类号:

TP301

廖伟志, 夏小云, 贾小军. 基于蚁群算法的多路径覆盖测试数据生成[J]. 电子学报, 2020, 48(7): 1330-1342.

LIAO Wei-zhi, XIA Xiao-yun, JIA Xiao-jun. Test Data Generation for Multiple Paths Coverage Based on Ant Colony Algorithm[J]. Acta Electronica Sinica, 2020, 48(7): 1330-1342.

参考文献

[1] XANTHAKIS S,ELLIS C,SKOURLAS C,et al.Application of genetic algorithms to software testing[A].Proceedings of the Fifth International Conference on Software Engineering and its Applications[C].Toulouse,France:ACM,1992.625-636.
[2] LATIU G I,CRET O A,VACARIU L.Automatic test data generation for software path testing using evolutionary algorithms[A].Proceedings of the Third International Conference on Emerging Intelligent Data and Web Technologies[C].Bucharest,Romania:IEEE,2012.1-8.
[3] SURI B,SINGHAL S.Literature survey of ant colony optimization in software testing[A].Proceedings of CSI Sixth International Conference on Software Engineering[C].Washington DC,USA:IEE,2012.1-7.
[4] HUANG Han,YANG Zhongming,HAO Zhifeng.Automated test case generation based on differential evolution with relationship matrix for iFogSim toolkit[J].IEEE Transactions on Industrial Informatics,2018,14(11):5005-5016.
[5] GOPI P,RAMALINGAM M,MARUTHAPERUMAL A K,et al.Weighted particle swarm optimization algorithm for test data generation[A].International Conference on Computing,Analytics and Security Trends[C].Pune,India:IEEE,2016.35-39.
[6] 傅博.基于蚁群算法的软件测试数据自动生成[J].计算机工程与应用,2007,43(12):97-99. FU Bo.Automated software test data generation based on colony algorithm[J].Computer Engineering and Application,2007,43(12):97-99.(in Chinese)
[7] BIDGOLI A M,HAGHIGHI H,NASAB H Z,SABOURI H.Using swarm intelligence to generate test data for covering prime paths[A].International Federation for Information Processing[C].Rome,Italy:Springer-Verlag,2017.132-147.
[8] LI K,ZHANG Z,LIU W.Automatic test data generation based on ant colony optimization[A].Proceedings of the Fifth International Conference on Natural Computation[C].Washington DC,USA:IEE,2009.216-220.
[9] SRIVASTAVA P R,RAI V K.An ant colony optimization approach to test sequence generation for control flow based software testing[J].Communications in Computer & Information Science,2009,31(12):345-346.
[10] SHARMA B,GIRDHAR I,et al.Software coverage:a testing approach through ant colony optimization[A].Proceedings of the Second International Conference on Swarm[C].Andhra Pradesh,India:Springer-Verlag,2011.618-625.
[11] AYARI K,BOUKTIF S,ANTONIOL G.Automatic mutation test input data via ant colony[A].Proceedings of the Ninth Annual Conference on Genetic and Evolutionary Computation[C].London,UK:ACM,2007.1074-1081.
[12] LI Huizhong,LAM C Peng.Software test data generation using ant colony algorithm[J].International Journal of Computer,Control,Quantum and Information Engineering,2007,1(1):126-129.
[13] SRIVASTAVA P R,BABY Km.Automated software testing using metahurestic technique based on an ant colony optimization[A].International Symposium on Electronic System Design[C].Bhubaneswar,India:IEEE,2010.235-240.
[14] BOUCHACHIA A,MITTERMEIR R,et al.Nature-inspire techniques for conformance testing of object-oriented software[J].Applied Soft Computing,2010,10(3):730-745.
[15] BAUERSFELD S,WAPPLER S.An approach to automatic input sequence generation for GUI testing ant colony optimization[A].Proceedings of the 13 Annual Conference on Genetic and Evolutionary Computation[C].Dublin,Ireland:ACM,2011.251-252.
[16] MAO Chengying,XIAO Lichuan.Adapting ant colony optimization to generate test data for software structural testing[J].Swarm and Evolutionary Computation,2015,20(2):23-26.
[17] SHARIFIPOUR H,SHAKERI M,HAGHIGHI H.Structural test data generation using a memetic ant colony optimization based on evolution strateges[J].Swarm and Evolution Computation,2018,40:76-91.
[18] BUENO P M S,JINO M.Automatic test data generation for program paths using genetic algorithms[J].Software Engineering and Knowledge,2002,12(6):691-709.
[19] WATKINS A,HUFNAGEL E M.Evolutionary test data generation:A comparison of fitness functions[J].Software Particle and Experience,2006,36(1):95-116.
[20] YERESIME S,SANTANU K R.A genetic algorithm based approach for test data generation in basis path testing[J].The International Journal of Soft Computing and Software Engineering,2013,3(3):326-332.
[21] 谢晓园,徐宝文,史亮,聂长海.面向路径覆盖的演化测试用例生成技术[J].软件学报,2009,20(12):3117-3136. XIE Xiao-yuan,XU Bao-wen,SHI Liang,NIE Chang-hai.Genetic test case generation for path-oriented testing[J].Journal of Software,2009,20(12):3117-3136.(in Chinese)
[22] MEI Jia,WANG Sheng-yuan.An improved genetic algorithm for test cases generation oriented paths[J].Chinese Journal of Electronics,2014,23(3):494-498.
[23] 张岩,巩敦卫.基于搜索空间自动缩减的路径覆盖测试数据进化生成[J].电子学报,2012,40(5):1011-1016. ZHANG Yan,GONG Dun-wei.Evolutionary generation of test data for path coverage based on automatic reduction of search space[J].Acta Electronica Sinica,2012,40(5):1011-1016.(in Chinese)
[24] 张岩,巩敦卫.基于稀有数据扑捉的路径覆盖测试数据进化生成方法[J].计算机学报,2013,36(12):2212-2223. ZHANG Yan,GONG Dun-wei.Evolutionary generation of test data for paths coverage based on scarce data capturing[J].Chinese Journal of Computers,2013,36(12):2212-2223.(in Chinese)
[25] 田甜,巩敦卫.消息传递并行程序路径覆盖测试数据生成问题的模型及其进化求解方法[J].计算机学报,2013,36(11):2212-2223. TIAN Tian,GONG Dun-wei.Model of test data generation for path coverage of message-passing parallel programs and its evolution-based solution[J].Chinese Journal of Computers,2013,36(11):2212-2223.(in Chinses)
[26] 巩敦卫,任丽娜.回归测试数据进化生成[J].计算机学报,2014,37(3):489-499. GONG Dun-wei,REN Li-na.Evolutionary generation of regression test data[J].Chinese Journal of Computers,2014,37(3):489-499.(in Chinese)
[27] 夏春艳,张岩,宋丽.基于节点概率的路径覆盖测试数据进化生成[J].软件学报,2016,27(4):802-815. XIA Chun-yan,ZHANG Yan,SONG Li.Evolutionary generation of test data for paths coverage based on node probability[J].Journal of Software,2016,27(4):802-815.(in Chinese)
[28] 李爱国,张艳丽.基于PSO的软件结构测试数据自动生成方法[J].计算机工程,2008,34(6):93-97. LI Aai-guo,ZHANG Yan-li.Automatic generation method of test data for software structure based on PSO[J].Computer Engineering,2008,34(6):93-97.(in Chinese)
[29] NARMADA N,DURGA P M.Automatic test data generation for data flow testing using particle swarm optimization[A].Proceedings of the Third International Conference on Contemporary Computing[C].Noida,India:IEEE,2010.1-12.
[30] 史娇娇,姜淑娟,韩寒,王令赛.自适应粒子群优化算法及其在测试数据生成中的应用[J].电子学报,2013,41(8):1555-1559. SHI Jiao-jiao,JIANG Shu-juan,HAN Han,WANG Ling-sai.Adaptive particle swarm optimization algorithm and its application in test data generation[J].Acta Electronica Sinica,2013,41(8):1555-1559.(in Chinese)
[31] 廖伟志.基于路径自动分割的测试数据生成方法[J].电子学报,2016,44(9):2254-2261. LIAO Wei-zhi.Test data generation based on automatic division of path[J].Acta Electronica Sinica,2016,44(9):2254-2261.(in Chinese)
[32] AHMED M A,HERMADI I.GA-based multiple paths test data generator[J].Computer Operation and Research,2008,35(10):3107-3124.
[33] 巩敦卫,张婉秋.基于自适应分组的大规模路径覆盖测试数据进化生成[J].控制与决策,2011,26(7):979-983. GONG Dun-wei,ZHANG Wan-qiu.Evolutionary generation of test data for many paths coverage based on adaptive grouping[J].Control and Decision,2011,26(7):979-983.(in Chinese)
[34] GONG D W,ZHANG W Q,YAO X J.Evolutionary generation of test data for many paths coverage based on grouping[J].Journal of System and Software,2011,84(12):2222-2233.
[35] MARAGATHAVALLI P,KANMANI S,KIRUBAKAR J S,et al.Automatic program instrumentation in generation of test data using genetic algorithm for multiple paths coverage[A].Proceedings of 2012 International Conference on Advances in Engineering,Science and Management[C].Tamil Nadu,India:IEEE,2012.349-353.
[36] LI A G,ZHANG Y L.Automatic generating all-path test data of a program based on PSO[A].Proceedings of World Congress on Software Engineering[C].Xiamen,China:IEEE,2009.189-193.
[37] 聂鹏,耿技,秦志光.多路径粒子群优化自动测试用例生成算法[J].计算机集成制造系统,2012,18(1):216-223. NIE P,GEN J,QIN Z-G.Multi-path oriented swarm optimization automatic test case generation algorithm[J].Computer Integr Manuf System,2012,18(1):216-223.(in Chinese)
[38] WANG S T,WU H.A novel algorithm for multi-path test data generation[A].Proceedings of the Fourth International Conference on Digital Manufacturing and Automation[C].Qingdao,China:IEEE,2013.58-60.
[39] HAN X,LEI H,WANG Y S.Multiple paths test data generation based on particle swarm optimization[J].IET Software,2017,11(2):41-47.
[40] YAO X,GONG D.Genetic algorithm-based test data generation for multiple paths via individual sharing[J].Computational Intelligence and Neuroscience,2014,2014(3):59-70.
[41] ZHU Ziming,XU Xiong.Improved evolutionary generation of test data for multiple paths in search-based software testing[J].2017 IEEE Congress on Evolutionary Computation[C].Washington DC,USA:IEEE,2017.612-620.
[42] 巩敦卫,张岩.一种新的多路径覆盖测试数据进化生成方法[J].电子学报,2010,38(6):1299-1304. GONG Dun-wei,ZHANG Yan.Novel evolutionary generation approach to test data for multiple paths coverage[J].Acta Electronica Sinica,2010,38(6):1299-1304.(in Chinese)
[43] ZHANG Y,GONG D,YAO X,LU Q.Generating test data covering multiple paths using genetic algorithm incorporating with reducing input domain[A].Proceedings of Chinese Intelligent Systems Conference[C].Mudanjiang,China:Springer-Verlag,2017.739-747.