• P-ISSN 0974-6846 E-ISSN 0974-5645

Indian Journal of Science and Technology


Indian Journal of Science and Technology

Year: 2022, Volume: 15, Issue: 41, Pages: 2151-2161

Original Article

Automatic Test Data Generation for Basis Path Testing

Received Date:18 July 2022, Accepted Date:23 September 2022, Published Date:03 November 2022


Objectives: This paper presents a new hybrid ACO-NSA algorithm for the automatic test data generation problem with path coverage as an objective function. Method: In it, at the first instance, test data (detectors) are generated with the ant colony optimization algorithm (ACO), and then the generated data set (detector set) has been refined by a negative selection algorithm (NSA) with Hamming distance. Findings: The algorithm’s performance is tested on several benchmark problems with different data types and variables for metrics average coverage, average generations, average time and success rate, Iteration value 1000 is set for average coverage, average generations, average time and 200 for success rate. The obtained results from the proposed approach are compared with some existing approaches. The results are very efficient with high efficacy, higher path coverage, minimal data redundancy, and less execution time. Applications: This approach can be applied in any type of software development process in software engineering to reduce the testing efforts. Novelty: The approach is based on two distinct methodologies: metaheuristic search and artificial immune search, and its fitness is measured using path coverage as the fitness function. The approach provides 99.5% average path coverage, 2.72% average number of generations in 0.07 ns, and 99.9% success rate, which is significantly better than comparable approaches.

Keywords: Test data generation; Metaheuristic search; Artificial immune search; Ant colony optimization; Negative selection algorithm; Path coverage


  1. Ntafos SC. A comparison of some structural testing strategies. IEEE Transactions on Software Engineering. 1988;14(6):868–874. Available from: https://doi.org/10.1109/32.6165
  2. Garousi V, Mäntylä MV. A systematic literature review of literature reviews in software testing. Information and Software Technology. 2016;80:195–216. Available from: https://doi.org/10.1016/j.infsof.2016.09.002
  3. Dorigo M, Birattari M, Stutzle T. Artificial ants as a computational intelligence technique. IEEE computational intelligence magazine. 2006;1:28–39. Available from: https://doi.org/10.1109/CI-M.2006.248054
  4. Anand S, Burke EK, Chen TY, Clark J, Cohen MB, Grieskamp W, et al. An orchestrated survey of methodologies for automated software test case generation. Journal of Systems and Software. 2013;86(8):1978–2001. Available from: https://doi.org/10.1016/j.jss.2013.02.061
  5. Ghiduk AS. Automatic generation of basis test paths using variable length genetic algorithm. Information Processing Letters. 2014;114(6):304–316. Available from: https://doi.org/10.1016/j.ipl.2014.01.009
  6. Hermadi I, Lokan C, Sarker R. Dynamic stopping criteria for search-based test data generation for path testing. Information and Software Technology. 2014;56(4):395–407. Available from: https://doi.org/10.1016/j.infsof. 2014.01.001
  7. Chen Y, Zhong Y, Shi T, Liu J. Comparison of Two Fitness Functions for GA-Based Path-Oriented Test Data Generation. 2009 Fifth International Conference on Natural Computation. 2009;4:177–181. Available from: https://doi.org/10.1109/ICNC.2009.235
  8. Zhu XMM, Yang XFF. Software Test Data Generation Automatically Based on Improved Adaptive Particle Swarm Optimizer. 2010 International Conference on Computational and Information Sciences. 2010;p. 1300–1303. Available from: https://doi.org/10.1109/ICCIS.2010.321
  9. Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 1996;26(1):29–41.
  10. Socha K, Dorigo M. Ant colony optimization for continuous domains. European Journal of Operational Research. 2008;185(3):1155–1173. Available from: https://doi.org/10.1016/j.ejor.2006.06.046
  11. Mao C, Xiao L, Yu X, Chen J. Adapting ant colony optimization to generate test data for software structural testing. Swarm and Evolutionary Computation. 2015;20:23–36. Available from: https://doi.org/10.1155/2014/392309
  12. Sayyari F, Emadi S. Automated generation of software testing path based on ant colony. 2015 International Congress on Technology, Communication and Knowledge (ICTCK). 2015;p. 435–440. Available from: https://doi.org/10.1109/ICTCK.2015.7582709
  13. Dasgupta D. Advances in artificial immune systems. IEEE computational intelligence magazine. 2006;1:40–49. Available from: https://doi.org/10.1109/CI-M.2006.248056
  14. Liu Z, Li T, Yang J, Yang T. An Improved Negative Selection Algorithm Based on Subspace Density Seeking. IEEE Access. 2017;5:12189–12198. Available from: https://doi.org/10.1109/ACCESS.2017.2723621
  15. Mohi-Aldeen SM, Mohamad R, Deris SR. Application of Negative Selection Algorithm (NSA) for test data generation of path testing. Applied Soft Computing. 2016;49:1118–1128. Available from: https://doi.org/10.1016/j.asoc.2016.09.044
  16. Sharma M, Pathik B. Crow Search Algorithm with Improved Objective Function for Test Case Generation and Optimization. Intelligent Automation & Soft Computing. 2022;32(2):1125–1140. Available from: https://doi.org/10.32604 /iasc.2022.022335
  17. Khan R, Srivastava AK. Automatic software testing framework for all def-use with genetic algorithm. Int J Innov Technol Explor Eng (IJITEE). 2019;8(8):2055–2060.
  18. Ma E, Fu X, Wang X. Scalable Path Search for Automated Test Case Generation. Electronics. 2022;11(5):727. Available from: https://doi.org/10.3390/electronics11050727
  19. Mohi-Aldeen SM, Mohamad R, Deris SR. Optimal path test data generation based on hybrid negative selection algorithm and genetic algorithm. Plos One. 2020;15(11):e0242812.


© 2022 Kumar & Chopra. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Published By Indian Society for Education and Environment (iSee)


Subscribe now for latest articles and news.