一种基于改进遗传算法的路径测试用例生成方法

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

Abstract

Abstract: Using genetic algorithms to solve the problem of generating test cases for path coverage is a hot topic in software testing automation.In view of the problems in traditional standard genetic methods,such as premature convergence and slow search efficiency,this paper designed adaptive crossover operator and mutation operator,thus enhancing the global optimal capability of genetic algorithm.Meanwhile,a new fitness function was introduced to evaluate individuals based on dynamic generation algorithm framework,which combines approach level and branch distance and takes the nesting degree of branches into consideration to compute the fitness values of test data.The experimental results confirm that the proposed improved method is more efficient in generating test cases for path coverage compared with the traditional method.

Key words: Fitness function, Genetic algorithm, Software testing, Test cases generation

CLC Number:

TP311

BAO Xiao-an, XIONG Zi-jian, ZHANG Wei, WU Biao, ZHANG Na. Approach for Path-oriented Test Cases Generation Based on Improved Genetic Algorithm[J].Computer Science, 2018, 45(8): 174-178.

References

[1]SAGARNA R,LOZANO J A.Scatter search in software tes-ting,comparison and collaboration with estimation of distribution algorithms[J].European Journal of Operational Research,2006,169(2):392-412.
[2]FRASER G,ARCURI A.EvoSuite at the SBST 2015 Tool Competition[C]∥IEEE/ACM,International Workshop on Search-Based Software Testing.IEEE,2015:25-27.
[3]GALLER S J,AICHERNIG B K.Survey on test data generation tools[J].International Journal on Software Tools for Technology Transfer,2014,16(6):727-751.
[4]XUE Y Z,CHEN W,WANG Y J,et al.An automated approach for structural test data generation based on Messy GA[J].Journal of Software,2006,17(8):1688-1697.(in Chinese)薛云志,陈伟,王永吉,等.一种基于Messy GA的结构测试数据自动生成方法[J].软件学报,2006,17(8):1688-1697.
[5]AWEDIKIAN Z,AYARI K,ANTONIOL G.MC/DC automatic test input data generation[C]∥Genetic and Evolutionary Computation Conference(GECCO 2009).2009:1657-1664.
[6]MAHAJAN M,PORWAL R.Applying genetic algorithm to increase the efficiency of a data flow-based test data generation approach[J].Acm Sigsoft Software Engineering Notes,2012,37(5):1-5.
[7]GIRGIS M R,GHIDUK A S,ABDELKAWY E H.AutomaticGeneration of Data Flow Test Paths using a Genetic Algorithm[J].International Journal of Computer Applications,2014,89(12):29-36.
[8]GONG D W,ZHANG Y.Novel evolutionary generation ap-proach to test data for multiple paths coverage[J].Acta Electronica Sinica,2010,38(6):1299-1304.(in Chinese)巩敦卫,张岩.一种新的多路径覆盖测试数据进化生成方法[J].电子学报,2010,38(6):1299-1304.
[9]XIE X Y,XU B W,SHI L,et al.Genetic test case generation for path-oriented testing[J].Journal of Software,2009,20(12):3117-3136.(in Chinese)谢晓园,徐宝文,史亮,等.面向路径覆盖的演化测试用例生成技术[J].软件学报,2009,20(12):3117-3136.
[10]RAJKUMARI M R,GEETHA B G.Automatic test data gene-ration using genetic algorithm and program dependence graph[J].Journal of Computer Applications,2012,48(7):586-605.
[11]ALSHRAIDEH M A,MAHAFZAH B A,SALMAN H S E,et al.Using Genetic Algorithm as Test Data Generator for Stored PL/SQL Program Units[J].Journal of Software Engineering & Applications,2015,6(2):65-73.
[12]RAUF A,JAFFAR A,SHAHID A A.Fully automated gui testing and coverage analysis using genetic algorithms[J].International Journal of Innovative Computing Information & Control Ijicic,2011,7(6):3281-3294.
[13]SHI J J,JIANG S J.Automatic test data generation tool of dynamic variable parameters based on genetic algorithm[J].Computer Science,2012,39(5):124-127.(in Chinese)史娇娇,姜淑娟.基于遗传算法的动态可变参数的测试数据自动生成工具[J].计算机科学,2012,39(5):124-127.
[14]TRACEY N,CLARK J,MANDER K,et al.An AutomatedFramework for Structural Test-Data Generation[C]∥IEEE International Conference on Automated Software Engineering,1998.IEEE,1998:285-288.
[15]NIRPAL P B,KALE K V.Using Genetic Algorithm for Automated Efficient Software Test Case Generation for Path Testing[J].International Journal of Advanced Networking & Applications,2011,2(6):911-915.
[16]MCMINN P.Evolutionary Search for Test Data in the Presence of State Behaviour[J].University of Sheffield,2005,16(12):41-46.
[17]PACHAURI A,SRIVASTAVA G.Automated test data generation for branch testing using genetic algorithm:An improved approach using branch ordering,memory and elitism[J].Journal of Systems & Software,2013,86(5):1191-1208.
[18]DO H,ELBAUM S,ROTHERMEL G.Supporting ControlledExperimentation with Testing Techniques:An Infrastructure and its Potential Impact[J].Empirical Software Engineering,2005,10(4):405-435.
[19]ALETI A,GRUNSKE L.Test data generation with a Kalman filter-based adaptive genetic algorithm[J].Journal of Systems & Software,2015,103(C):343-352.
[20]SCHAFFER J D,CARUANA R A,ESHELMAN L J,et al.A study of control parameters affecting online performance of genetic algorithms for function optimization[C]∥International Conference on Genetic Algorithms,George Mason University,Fairfax,Virginia,USA.DBLP,1989:51-60.

Related Articles 15

[1]	YANG Hao-xiong, GAO Jing, SHAO En-lu. Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery [J]. Computer Science, 2022, 49(6A): 191-198.
[2]	SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[3]	WU Shan-jie, WANG Xin. Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks [J]. Computer Science, 2021, 48(7): 308-315.
[4]	ZHENG Zeng-qian, WANG Kun, ZHAO Tao, JIANG Wei, MENG Li-min. Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster [J]. Computer Science, 2021, 48(6): 261-267.
[5]	WANG Jin-heng, SHAN Zhi-long, TAN Han-song, WANG Yu-lin. Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network [J]. Computer Science, 2021, 48(6): 338-342.
[6]	ZUO Jian-kai, WU Jie-hong, CHEN Jia-tong, LIU Ze-yuan, LI Zhong-zhi. Study on Heterogeneous UAV Formation Defense and Evaluation Strategy [J]. Computer Science, 2021, 48(2): 55-63.
[7]	WEN Jin, ZHANG Xing-yu, SHA Chao-feng, LIU Yan-jun. Test Suite Reduction via Submodular Function Maximization [J]. Computer Science, 2021, 48(12): 75-84.
[8]	TENG Jun-yuan, GAO Meng, ZHENG Xiao-meng, JIANG Yun-song. Noise Tolerable Feature Selection Method for Software Defect Prediction [J]. Computer Science, 2021, 48(12): 131-139.
[9]	GAO Shuai, XIA Liang-bin, SHENG Liang, DU Hong-liang, YUAN Yuan, HAN He-tong. Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm [J]. Computer Science, 2021, 48(11A): 166-169.
[10]	YAO Ze-wei, LIU Jia-wen, HU Jun-qin, CHEN Xing. PSO-GA Based Approach to Multi-edge Load Balancing [J]. Computer Science, 2021, 48(11A): 456-463.
[11]	SUN Chang-ai, ZHANG Shou-feng, ZHU Wei-zhong. Mutation Based Fault Localization Technique for BPEL Programs [J]. Computer Science, 2021, 48(1): 301-307.
[12]	GAO Ji-xu, WANG Jun. Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm [J]. Computer Science, 2021, 48(1): 72-80.
[13]	JI Shun-hui, ZHANG Peng-cheng. Test Case Generation Approach for Data Flow Based on Dominance Relations [J]. Computer Science, 2020, 47(9): 40-46.
[14]	DONG Ming-gang, HUANG Yu-yang, JING Chao. K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection [J]. Computer Science, 2020, 47(8): 178-184.
[15]	LIANG Zheng-you, HE Jing-lin, SUN Yu. Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition [J]. Computer Science, 2020, 47(8): 227-232.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Approach for Path-oriented Test Cases Generation Based on Improved Genetic Algorithm

PDF (PC)