Abstract

Structural testing, also known as white-box testing, requires the generation of input data that ensures coverage of program structures such as statements, branches, and paths. The complexity of software development makes testing extremely challenging and demands novel approaches with significant advancement in the field. Manual testing by contrast, remains time-consuming and costly activity, accounting for almost 50% of software production costs. To address these challenges, several automated techniques have been explored, among which Genetic Algorithms (GAs) have emerged as one of the most widely adopted and studied approaches. GAs are a class of search-based optimization techniques inspired by natural selection, and they are particularly effective in solving complex search problems. However, the use of traditional GAs for structural test data generation suffers from premature convergence and population stagnation. To address these limitations, we introduce the Alterable Genetic Algorithm (AGA), a novel approach in which a single genetic operator is applied per iteration. An adaptive alternation function dynamically selects the most appropriate operator for the current state of search, capitalizing on their respective strengths to guide the search more effectively. This paper investigates the extent to which AGA improves structural test data generation, particularly by achieving high branch coverage with fewer fitness evaluations.

References

• Sultan H Aljahdali, Ahmed S Ghiduk, and Mohammed El- Telbany. The limitations of genetic algorithms in software testing. In ACS/IEEE International Conference on Computer Systems and Applications-AICCSA 2010, pages 1–7. IEEE, 2010.
• Peter Boonstoppel, Cristian Cadar, and Dawson Engler. Rwset: Attacking path explosion in constraint-based test generation. In Tools and Algorithms for the Construction and Analysis of Systems: 14th International Conference, TACAS 2008, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29-April 6, 2008. Proceedings 14, pages 351– 366. Springer, 2008.
• Rajiv Chopra. Software testing: a self-teaching introduction. Mercury Learning and Information, 2018.
• Philippe Collard and Alessio Gaspar. ” royal-road” landscapes for a dual genetic algorithm’. In ECAI, volume 96, page 12th. PITMAN, 1996.
• Mehdi Esnaashari and Amir Hossein Damia. Automation of software test data generation using genetic algorithm and reinforcement learning. Expert Systems with Applications, 183:115446, 2021.
• Marie-Claude Gaudel. Formal methods for software testing. In 2017 International Symposium on Theoretical Aspects of Software Engineering (TASE), pages 1–3. IEEE, 2017.
• Robert Gold. Control flow graphs and code coverage. International Journal of Applied Mathematics and Computer Science, 20(4):739–749, 2010.
• Shifen Han and Li Xiao. An improved adaptive genetic algorithm. In SHS Web of Conferences, volume 140, page 01044. EDP Sciences, 2022.
• Mark Harman. The current state and future of search based software engineering. In Future of Software Engineering (FOSE’07), pages 342–357. IEEE, 2007.
• Mark Harman. Open problems in testability transformation. In 2008 IEEE International Conference on Software Testing Verification and Validation Workshop, pages 196–209. IEEE, 2008.
• Mark Harman and Afshin Mansouri. Search based software engineering: Introduction to the special issue of the ieee transactions on software engineering. IEEE Transactions on Software Engineering, 36(6):737, 2010.
• Mark Harman and Phil McMinn. A theoretical & empirical analysis of evolutionary testing and hill climbing for structural test data generation. In Proceedings of the 2007 international symposium on Software testing and analysis, pages 73–83, 2007.
• Frederick Hayes-Roth. Review of” adaptation in natural and artificial systems by john h. holland”, the u. of michigan press, 1975. ACM SIGART Bulletin, (53):15–15, 1975.
• Weigang He, Jianqi Shi, Ting Su, Zeyu Lu, Li Hao, and Yanhong Huang. Automated test generation for iec 61131-3 st programs via dynamic symbolic execution. Science of Computer Programming, 206:102608, 2021.
• Ren´e Just. On effective and efficient mutation analysis for unit and integration testing. 2016.
• Susan Khor and Peter Grogono. Using a genetic algorithm and formal concept analysis to generate branch coverage test data automatically. In Proceedings. 19th International Conference on Automated Software Engineering, 2004., pages 346–349. IEEE, 2004.
• Stefan Mairhofer, Robert Feldt, and Richard Torkar. Searchbased software testing and test data generation for a dynamic programming language. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, pages 1859–1866, 2011.
• Gerrit Jan Tretmans and Axel Belinfante. Automatic testing with formal methods. Centre for Telematics and Information Technology, University of Twente, 1999.
• Sapna Varshney and Monica Mehrotra. Search based software test data generation for structural testing: a perspective. ACM SIGSOFT Software Engineering Notes, 38(4):1–6, 2013.
• Richard A Watson and Thomas Jansen. A building-block royal road where crossover is provably essential. In Proceedings of the 9th annual conference on Genetic and evolutionary computation, pages 1452–1459, 2007.
• Dalin Zhang, Jianwei Sui, and Yunzhan Gong. Large scale software test data generation based on collective constraint and weighted combination method. Technical Gazette/Tehniˇcki Vjesnik, 24(4), 2017.