基于变异粒子群算法的字符串型测试数据生成

doi:10.11896/j.issn.1002-137X.2016.11.049

计算机科学 ›› 2016, Vol. 43 ›› Issue (11): 252-256.doi: 10.11896/j.issn.1002-137X.2016.11.049

基于变异粒子群算法的字符串型测试数据生成

李刚,于磊,孙回回,张兴隆,侯韶凡

解放军信息工程大学郑州450001数学工程与先进计算国家重点实验室郑州450001,解放军信息工程大学郑州450001数学工程与先进计算国家重点实验室郑州450001,解放军信息工程大学郑州450001数学工程与先进计算国家重点实验室郑州450001,解放军信息工程大学郑州450001数学工程与先进计算国家重点实验室郑州450001,解放军信息工程大学郑州450001数学工程与先进计算国家重点实验室郑州450001

出版日期:2018-12-01 发布日期:2018-12-01
基金资助:
本文受国家科学自然基金项目(61402525),郑州市普通科技攻关项目(141PPTGG383)资助

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

摘要： 基于搜索的算法在以路径覆盖为目标的测试数据生成中应用广泛。然而对于字符串型测试数据的生成,现有方法效率不高。为了高效地生成字符串型测试数据,提出了一种基于变异粒子群算法的字符串型测试数据自动生成方法。在随机生成初始种群后,采用粒子群算法使种群在趋近最优个体的过程中实现进化,并以一定的概率对种群中的个体进行变异操作,以避免进化过程陷入局部最优。为了有效地指导种群进化过程,对经典适应度函数中分支距离的计算方法进行改进,使其适用于含有字符串型参数的程序。实验结果表明,该方法具有较高的成功率和稳定性,且能明显提升测试数据生成效率。

关键词: 测试数据生成,字符串型数据,分支距离,变异粒子群算法

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

李刚,于磊,孙回回,张兴隆,侯韶凡. 基于变异粒子群算法的字符串型测试数据生成[J]. 计算机科学, 2016, 43(11): 252-256. https://doi.org/10.11896/j.issn.1002-137X.2016.11.049

LI Gang, YU Lei, SUN Hui-hui, ZHANG Xing-long and HOU Shao-fan. String-type Test Data Generation Based on Mutation Particle Swarm Optimization[J]. Computer Science, 2016, 43(11): 252-256. https://doi.org/10.11896/j.issn.1002-137X.2016.11.049

参考文献

[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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于变异粒子群算法的字符串型测试数据生成

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0