Automation of Software Test Data Generation Based on Path Coverage Criteria and Using Coati Optimization Algorithm and Q Learning

Abstract :

The software testing process is very time-consuming and expensive and accounts for almost half of the cost of software production. The main issue in the test data generation process is determining the program's input data in such a way that it meets the specified test criteria. In this research, the structural method has been used to automate the process of generating test data, focusing on the criterion of covering all finite paths. In the structural method, the problem becomes a search problem, and metaheuristic algorithms can be used to solve it. The proposed method is a hybrid algorithm in which the q-learning algorithm is used as a local search method within the structure of the Coati search algorithm. The results of the tests have shown that this method for generating test data is faster than many metaheuristic algorithms and can provide better coverage with fewer evaluations. On average, our proposed algorithm shows about 25-30% improvement in coverage compared to other algorithms, which makes it significantly more effective than other algorithms. This shows that our algorithm achieves superiority over other compared algorithms due to its more efficient and optimal path coverage approach.

References:

[1] P. Ammann and J. Offutt, Introduction to Software Testing, Cambridge University Press, 2016.
[2] F. Lonetti and E. Marchetti, "Emerging software testing technologies," Advances in Computers, Elsevier, vol. 108, pp. 91-143, 2018.
[3] S. Parsa, "Automatic test data generation symbolic and concolic executions," In S. Parsa (ed.), Software Testing Automation: Testability Evaluation, Refactoring, Test Data Generation and Fault Localization, pp. 503-542, Springer, 2023.
[4] G. Zhang, et al.,"FDSE: enhance symbolic execution by fuzzing-based pre-analysis (competition contribution)," in Proc. 27th Int. Conf. on Fundamental Approaches to Software Engineering, pp. 304-308, Luxembourg City, Luxembourg, 6-11 Apr. 2024.

[5] O. Sahin and B. Akay, "Comparisons of metaheuristic algorithms and fitness functions on software test data generation," Applied Soft Computing, vol. 49, pp. 1202-1214, Dec. 2016. [6] M. Harman and P. McMinn, "A theoretical and empirical study of search-based testing: local, global, and hybrid search," IEEE Trans. on Software Engineering, vol. 36, no. 2, pp. 226-247, Mar./Apr. 2009.
[7] M. Dehghani, Z. Montazeri, E. Trojovská, and P. Trojovský, "Coati optimization algorithm: a new bio-inspired metaheuristic algorithm for solving optimization problems," Knowledge-Based Systems, vol. 259, Article ID: pp. 110011, Jan. 2023.
[8] N. Soffair and S. Mannor, \Textit {MinMaxMin} $Q$-Learning, arXiv preprint arXiv:2402.05951, 2024.
[9] N. Khoshniat, A. Jamarani, A. Ahmadzadeh, M. Haghi Kashani, and E. Mahdipour, "Nature-inspired metaheuristic methods in software testing," Soft Computing, vol. 28, no. 2, pp. 1503-1544, 2024.
[10] P. Ashwini, B. Rajani, and B. Vijitha, "An efficient early software reliability prediction using particle swarm optimization (PSO)," In K. Venkata Murali Mohan, M. Suresh Babu (eds). Disruptive Technologies in Computing and Communication Systems, pp. 52-58, CRC Press, 2024.
[11] T. Avdeenko and K. Serdyukov, "Automated test data generation based on a genetic algorithm with maximum code coverage and population diversity," Applied Sciences, vol. 11, no. 10, Article ID: 4673, May-2 2021.
[12] M. Nosrati, H. Haghighi, and M. V. Asl, "Test data generation using genetic programming," Information and Software Technology, vol. 130, Article ID: 106446, 2021.
[13] M. Angelova, K. Atanassov, and T. Pencheva, "Multi-population genetic algorithm quality assessment implementing intuitionistic fuzzy logic," in Proc. Federated Conf. on Computer Science and Information Systems, pp. 365-370, Wroclaw, Poland, 9-12 Sept. 2012.
[14] M. Alshraideh, B. A. Mahafzah, and S. Al-Sharaeh, "A multiple-population genetic algorithm for branch coverage test data generation," Software Quality J., vol. 19, pp. 489-513, 2011.
[15] N. Zhang, B. Wu, and X. Bao, "Automatic generation of test cases based on multi-population genetic algorithm," Int. J. Multimedia Ubiquitous Eng., vol. 10, no. 6, pp. 113-122, 2015.
[16] X. Bao, Z. Xiong, N. Zhang, J. Qian, B. Wu, and W. Zhang, "Path-oriented test cases generation based adaptive genetic algorithm," PloS One, vol. 12, no. 11, Article ID: e0187471, 2017.
[17] A. Damia, M. Esnaashari, and M. Parvizimosaed, "Software testing using an adaptive genetic algorithm," J. of AI and Data Mining, vol. 9, no. 4, pp. 465-474, Oct. 2021.
[18] M. Mann, P. Tomar, and O. P. Sangwan, "Test data generation using optimization algorithm: an empirical evaluation," in Proc. of Soft Computing: Theories and Applications, vol. 2, pp. 679-686, Jaipur, India, 28-30 Dec. 2018.
[19] M. Mann, O. P. Sangwan, P. Tomar, and S. Singh, "Automatic goal-oriented test data generation using a genetic algorithm and simulated annealing," in Proc. 6th Int. Conf.-Cloud System and Big Data Engineering, pp. 83-87, Noida, India, 14-15 Jan. 2016.
[20] X. M. Zhu and X. F. Yang, "Software test data generation automatically based on improved adaptive particle swarm optimizer," in Proc. Int. Conf. on Computational and Information Sciences, pp. 1300-1303, Chengdu, China, 17-19 Dec. 2010.
[21] S. Singla, D. Kumar, H. Rai, and P. Singla, "A hybrid PSO approach to automate test data generation for data flow coverage with dominance concepts," International J. of Advanced Science and Technology, vol. 37, no. 11, pp. 15-26, 2011.
[22] S. Jiang, J. Shi, Y. Zhang, and H. Han, "Automatic test data generation based on reduced adaptive particle swarm optimization algorithm," Neurocomputing, vol. 158, pp. 109-116, Jun. 2015.
[23] H. Sharifipour, M. Shakeri, and H. Haghighi, "Structural test data generation using a memetic ant colony optimization based on evolution strategies," Swarm and Evolutionary Computation, vol. 40, no. 40, pp. 76-91, Jun. 2018.
[24] A. H. Damia and M. M. Esnaashari, "Automated test data generation using a combination of firefly algorithm and asexual reproduction optimization algorithm," International J. of Web Research, vol. 3, no. 1, pp. 19-28, Jun. 2020.
[25] A. Damia, M. Esnaashari, and M. Parvizimosaed, "Automatic web-based software structural testing using an adaptive particle swarm optimization algorithm for test data generation," in Proc. 7th Int. Conf. on Web Research, pp. 282-286, Tehran, Iran, 19-20 May 2021.
[26] O. Al-Masri and W. A. Al-Sorori, "Object-oriented test case generation using teaching learning-based optimization (TLBO) algorithm," IEEE Access, vol. 10, pp. 110879-110888, 2022.
[27] M. Saadtjoo and S. Babamir, "Optimizing cost function in imperialist competitive algorithm for path coverage problem in software testing," J. of AI and Data Mining, vol. 6, no. 2, pp. 375-385, Jul. 2018.
[28] X. Dai, W. Gong, and Q. Gu, "Automated test case generation based on differential evolution with node branch archive," Computers & Industrial Engineering, vol. 156, Article ID: 107290, Jun. 2021.
[29] R. R. Sahoo and M. Ray, "Forest optimization-based test case generation for multiple paths with metamorphic relations," International J. of Applied Metaheuristic Computing, vol. 13, no. 1, pp. 1-18, Jan. 2022.
[30] F. Feyzi and S. Parsa, "Bayes‐TDG: effective test data generation using Bayesian belief network: toward failure‐detection effectiveness and maximum coverage," IET Software, vol. 12, no. 3, pp. 225-235, Jun. 2018.
[31] M. Esnaashari and A. H. Damia, "Automation of software test data generation using genetic algorithm and reinforcement learning," Expert Systems with Applications, vol. 183, Article ID: 115446, Nov. 2021.
[32] M. Malkauthekar, "Analysis of euclidean distance and manhattan distance measure in face recognition," in 3rd Int. Conf. on Computational Intelligence and Information Technology, pp. 503-507, Chennai, India, 27 Jul. 2013.
[33] Y. Duan, et al., "CAPSO: chaos adaptive particle swarm optimization algorithm," IEEE Access, vol. 10, pp. 29393-29405, 2022.
[34] P. Trojovský and M. Dehghani, "Pelican optimization algorithm: a novel nature-inspired algorithm for engineering applications," Sensors, vol. 22, no. 3, Article ID: 855, 2022.
[35] S. H. S. Moosavi and V. K. Bardsiri, "Poor and rich optimization algorithm: a new human-based and multi populations algorithm," Engineering Applications of Artificial Intelligence, vol. 86, pp. 165-181, Nov. 2019.
[36] S. Zhao, T. Zhang, S. Ma, and M. Chen, "Dandelion optimizer: a nature-inspired metaheuristic algorithm for engineering applications," Engineering Applications of Artificial Intelligence, vol. 114, Article ID: 105075, Sept. 2022.
[37] I. Fister, I. Fister Jr, X. S. Yang, and J. Brest, "A comprehensive review of firefly algorithms," Swarm and Evolutionary Computation, vol. 13, pp. 34-46, Dec. 2013.