Computer Science ›› 2016, Vol. 43 ›› Issue (11): 252-256, 279.doi: 10.11896/j.issn.1002-137X.2016.11.049

Previous Articles     Next Articles

String-type Test Data Generation Based on Mutation Particle Swarm Optimization

LI Gang, YU Lei, SUN Hui-hui, ZHANG Xing-long and HOU Shao-fan   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Search-based algorithm is widely used in test data generation for path coverage.However,current methods are not efficient enough dealing with string-type test data.In order to generate string-type test data efficiently,a novel approach based on mutation particle swarm algorithm (MPSO) was presented.In this approach,once a swarm is randomly generated,PSO is used to evolve the swarm by drawing the whole swarm towards the optimal particle,and mutation operation is carried out with certain probability to avoid falling into local optimal.For the sake of providing effective guidance for the search process,this paper improved the classical fitness function by modifying the calculation of branch distance to make it applicable for string-type test data.The experimental results show that our proposed method not only has high success rate and stability,but also can improve the efficiency of test data generation.

Key words: Test data generation,String-type test data,Branch distance,MPSO

[1] 朱鸿,金凌紫.软件质量保障与测试[M].北京:科学出版社,1997
[2] Lyu M R,Rangarajan S,Moorsel A P.Optimal Allocation ofTest Resources for Software Reliability Growth Modeling in Software Development[J].IEEE Transactions on Reliability,2002,51(2):183-192
[3] Offutt A J,Jin Z Y,Pan J.The Dynamic Domain Reduction Approach to Test Data Generation[J].Software Practice and Experience,1999,29(2):167-193
[4] Phil M.Search-based Software Test Data Generation:A Survey[J].Software Testing,Verification and Reliability,2004,14(2):105-156
[5] Jensen C S,Prasad M R,Moller A.Automated Testing withTargeted Event Sequence Generation[C]∥Proceedings of the 2013 International Symposium on Software Testing and Analysis.Lugano,Switzerland,ACM,2013:66-77
[6] Roberto B,Matthieu C,Roberta G,et al.Symbolic Path-Oriented Test Data Generation for Floating-Point Programs[C]∥Proceedings of the 6th International Conference on Software Testing,Verification and Validation.Luemberg,IEEE,2013:1-10
[7] Wang Xiao-yin,Zhang Ling-ming,Philip T.Experience Report-How is Dynamic Symbolic Execution Different from Manual Testing[C]∥Proceedings of the 2015 International Symposium on Software Testing and Analysis.Baltimore.USA,ACM,2015:199-210
[8] Yi Min-jie.The Research of Path-Oriented Test Data GenerationBased on a Mixed Ant Colony System Algorithm and Genetic Algorithm[C]∥Procee-dings of the 8th International Conference on Wireless Communications,Networking,and Mobile Computing (WiCOM).Shanghai,China,IEEE,2012:1-4
[9] Boussaa M,Barais O,Sunye G,et al.A Novelty Search-based Test Data Generator for Object-oriented Programs[C]∥Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation.Madrid,Spain,ACM,2015:1359-1360
[10] Yatoh K,Sakamoto K,Ishikawa F,et al.Feedback-ControlledRandom Test Generation[C]∥Proceedings of the 2015 International Symposium on Software Testing and Analysis.Baltimore,USA,ACM,2015:316-326
[11] Khan S A,Nadeem A.Automated Test Data Generation forCoupling Based Integration Testing of Object Oriented Programs Using Particle Swarm Optimization (PSO)[C]∥Procee-dings of the 7th International Conference on Genetic and Evo-lutionary Computing.Prague,Czech Republic,Springer,2013:115-124
[12] Ahmed M A,Hermadi I.GA-based Multiple Paths Test DataGenerator[J].Computers & Operations Research,2008,35(10):3107-3124
[13] Jiang S J,Yi D D,Ju X L,et al.An Approach for Test Data Generation Using Program Slicing and Particle Swarm Optimization[J].Neural Computing and Applications,2014,25(7/8):2047-2055
[14] Pritanka C,Inderveer C,Ajay R.A Novel Strategy for Automa-tic Test Data Generation Using Soft Computing Technique[J].Frontiers of Computer Science,2015,9(3):346-363
[15] Fraser G,Arcuri A.Whole Test Suite Generation[J].IEEETransactions on Software Engineering,2013,39(2):276-291
[16] Fraser G,Arcuri A.EvoSuite:Automatic Test Suite Generation for Objected-Oriented Software[C]∥Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering.Szeged,Hungray,2011:416-419
[17] Arcuri A,Fraser G.On Parameter Tuning in Search Based Software Engineering[C]∥Proceedings of the 3rd International Symposium on Search Based Software Engineering(SSBSE).Szeged,Hungary,2011:33-47
[18] Fraser G,Arcuri A.The Seed is Strong-Seeding Strategies inSearch-Based Software Testing[C]∥Proceedings of the 5th International Conference on Software Testing,Verification and Validation(ICST).Montreal,Canada,2012:121-130
[19] Mohammad A,Leonardo B.Search-based Software Test DataGeneration for String Data Using Program-Specific Search Ope-rators[J].Software Testing Verification and Reliability,2006,16(3):175-203
[20] Zhao R L.Searc-Based Automatic Path Test Generation forCharacter String Data [J].Journal of Computer-Aided Design & Computer Graphics,2008,20(5):671-677(in Chinese) 赵瑞莲.基于搜索的面向路径字符串测试数据自动生成方法[J].计算机辅助设计与图形学学报,2008,20(5):671-677
[21] Phil M,Muzammil S,Mark S.Search-Based Test Input Generation for String Data Types Using the Results of Web Queries[C]∥Proceedings of the 5th International Conference on Software Testing,Verification & Validation.Washington DC,USA,IEEE,2012:141-150
[22] Zhang X D.Automatic String Test Data Generation Based on Tabu Search [D].Beijing:Beijing University of Chemical Technology,2013(in Chinese) 张晓迪.基于禁忌搜索的字符串型测试数据自动生成[D].北京:北京化工大学,2013
[23] Kim S H,Kim K,Cho H G.A New String Search Tree withMultiple Alignment[C]∥Proceedings of the 12th International Conference on Computer and Information Technology.Chengdu,China,2012:456-463
[24] Sheeva A,Phil M,Mark S.Evolving Readable String Test In-puts Using a Natural Language Model to Reduce Human Oracle Cost[C]∥Proceedings of the 6th International Conference on Software Testing,Verification and Validation.Luembourg,2013:352-361
[25] Mao C Y,Yu X X,Xue Y Z.Algorithm Design and Empirical Analysis for Particle Swarm Optimization-Based Test Data Geneartion [J].Journal of Computer Research and Development,2014,51(4):824-837(in Chinese) 毛澄映,喻新欣,薛云志.基于粒子群优化的测试数据生成及其实证分析[J].计算机研究与发展,2014,51(4):824-837
[26] Whitley D.The GENITOR Algorithm and Selective Pressure:Why Rank Based Allocation of Reproductive Trials is Best[C]∥Proceedings of the 3rd International Conference on Genetic Algorithms,Fairfax,VA.San Francisco,USA,Morgan Kaufmann,1989:116-121
[27] Huang J C.Program Instrumentation and Software Testing[J].Computer Journal,1978,11(4):25-32
[28] Gonzalo N.A Guided Tour to Approximate String Matching[J].ACM Computing Surveys,2001,33(1):31-88

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .