Article Preview
TopIntroduction
Search-Based Software Engineering (SBSE) seeks to reformulate Software Engineering (SE) problems as search-based optimisation problems. It has been applied to a wide variety of SE areas, including requirements engineering, project planning and cost estimation, automated maintenance, service-oriented software engineering, compiler optimisation and quality assessment (Harman, 2007). Most of the overall literature (an estimated 59%) in the SBSE area is, however, concerned with Software Testing (ST) related applications, with structural test data generation being the most studied sub-topic (Harman, Mansouri, & Zhang, 2009).
The application of Evolutionary Algorithms (EAs) to test data generation or selection is often referred to as Evolutionary Testing (ET) (Tonella, 2004b; Wappler & Wegener, 2006b) or Search-Based Test Data Generation (SBTDG) (McMinn, 2004). ET consists of exploring the space of test programs by using metaheuristic techniques that direct the search towards the potentially most promising areas of the input space (Bertolino, 2007); its foremost objective is usually that of searching for a set of test programs that satisfies a predefined test criterion.
EAs have already been applied, with significant success, to the search for test data; the first application of heuristic optimisation techniques to test data generation was presented in 1992 (Xanthakis, Ellis, Skourlas, Gall, & K. Karapoulios, 1992). However, research has been mainly geared towards generating test data for procedural software, and traditional methods – despite their effectiveness and efficiency – cannot be applied without adaptation to Object-Oriented (OO) systems.
The application of search-based strategies to unit testing of OO programs is, in fact, fairly recent – the first approach was presented in 2004 (Tonella, 2004b) – and is yet to be investigated comprehensively (Harman, Hassoun, Lakhotia, McMinn, & Wegener, 2007). Interesting review articles on the topic of SBSE, and Search-Based Software Testing (SBST) in particular, include: (McMinn, 2004; Mantere & Alander, 2005; Xiao, El-Attar, Reformat & Miller, 2007; Afzal, Torkar, & Feldt, 2009; Ali, Briand, Hemmati, & Panesar-Walawege, 2009; Harman et al., 2009; Harman & McMinn, 2010; Maragathavalli, 2011; McMinn, 2011; Harman, Mansouri, & Zhang, 2012; Varshney & Mehrotra, 2013; Anand et al., 2013). McMinn surveys the use of metaheuristic search techniques for the automatic generation of test data (McMinn, 2004); because the work on SBST had, thus far (2004), been largely restricted to programs of a procedural nature, these are the main subject of this review. In (Mantere & Alander, 2005), a review of the application of Genetic Algorithm (GA)-based optimisation methods to ST is presented; the authors stress out that all the researchers in this area report good (or, at least, encouraging) results regarding their use. Xiao et al. reported the experimental results regarding the effectiveness of five different optimisation techniques over five different C/C++ programs (Xiao et al., 2007). The results show that the GA-based approach outperformed the remaining techniques – e.g., Simulated Annealing (SA), Genetic Simulated Annealing (GSA), Simulated Annealing with Advanced Adaptive Neighborhood (SA/ANN) and Random Testing – achieving the best overall performance.