Genetic Algorithms have been successfully applied to the generation of unit tests for classes, and are well suited to create complex objects through sequences of method calls. However, because the neighborhood in the search space for method sequences is huge, even supposedly simple optimizations on primitive variables (e. g. , numbers and strings) can be ineffective or unsuccessful. To overcome this problem, we extend the global search applied in the EvoSuite test generation tool with local search on the individual statements of method sequences. In contrast to previous work on local search, we also consider complex data types including strings and arrays. Arigorous experimental methodology has been applied to properly evaluate these new local search operators. In our experiments on a set of open source classes of different kinds (e. g. , numerical applications and text processing), the resulting test data generation technique increased branch coverage by up to 32% on average over the normal Genetic Algorithm. A common scenario in software testing is therefore that test data are generated, and a tester manually adds test oracles. As this is a difficult task, it is important to produce small yet representative test sets, and this representativeness is typically measured using code coverage. There is, however, a fundamental problem with the common approach of targeting one coverage goal at a time: Coverage goals are not independent, not equally difficult, and sometimes infeasible the result of test generation is therefore dependent on the order of coverage goals and how many of them are feasible. To overcome this problem, we propose a novel paradigm in which whole test suites are evolved with the aim of covering all coverage goals at the same time while keeping the total size as small as possible. This approach has several advantages, as for example, its effectiveness is not affected by the number of infeasible targets in the code. We have implemented this novel approach in the EVOSUITE tool, and compared it to the common approach of addressing one goal at a time. Evaluated on open source libraries and an industrial case study for a total of 1,741 classes we show that EVOSUITE achieved up to 188 times the branch coverage of a traditional approach targeting single branches, with up to 62 percent smaller test suites.

1. M. Alshraideh and L. Bottaci. Search- based software test data generation for string datausingprogram-specificsearch operators. Software Testing, Verification, and Reliability, 16(3):175–203, 2006.
2. A. Arcuri. Theoretical analysis of local search in software testing. In Symposium on Stochastic Algorithms, Foundations and Applications (SAGA), pages 156–168, 2009.
3. A. Arcuri and L. Briand. A hitchhiker's guide to statistical tests for assessing randomized algorithms in software engineering. Software Testing, Verification and Reliability (STVR), 2012. (to appear).
4. A. Arcuri and G. Fraser. On parameter tuning in search based software engineering. In International Symposium on Search Based Software Engineering (SSBSE), pages 33–47, 2011.
5. A. Arcuri and X. Yao. A memetic algorithm for test data generation of object- oriented software. In IEEE Congress on Evolutionary Computation (CEC), pages 2048–2055, 2007.
6. L. Baresi, P. L. Lanzi, and M. Miraz. Testful: an evolutionary test approach for java. In IEEE Int. Conference on Software Testing, Verification and Validation (ICST), pages 185–194, 2010.
7. R. Ferguson and B. Korel. The chaining approach for software test data generation. ACM Transactions on Software Engineering and Methodology, 5(1):63–86, 1996.
8. G. Fraser and A. Arcuri. The seed is strong: Seeding strategies in search-based software testing. In IEEE Int. Conference on SoftwareTesting,Verificationand Validation (ICST), pages 121–130, 2012.
9. G. Fraser and A. Arcuri. Sound empirical evidence in software testing. In ACM/IEEE International Conference on Software Engineering (ICSE), pages 178–188, 2012.
10. G. Fraser and A. Arcuri. Whole test suite generation. IEEE Transactions on Software Engineering, 39(2):276–291, 2013.
11. A. Arcuri and X. Yao, "Search Based Software Testing of Object- Oriented Containers," Information Sciences, vol. 178, no. 15, pp. 3075-3095, 2008.
12. A. Baars, M. Harman, Y. Hassoun, K. Lakhotia, P. McMinn, P. Tonella, and T. Vos, "Symbolic Search-Based Testing," Proc. IEEE/ACM 26th Int'l Conf. Automated Software Eng. , 2011.
13. L. Baresi, P. L. Lanzi, and M. Miraz, "Testful: An Evolutionary Test Approach for Java Proc IEEE Int'l Conf. Software Testing Verfication and Validation, pp. 185-194, 2010.
14. B. Baudry, F. Fleurey, J. -M. Je´ze´quel, and Y. Le Traon, "Automatic Test Cases Optimization: A Bacteriologic Algorithm," IEEE Software, vol. 22, no. 2, pp. 76-82, Mar. /Apr. 2005.
15. C. Csallner and Y. Smaragdakis, "JCrasher: An Automatic Robustness Tester for Java," Software Practice and Experience, vol. 34, pp. 1025-1050, 2004.
16. W. Feller, An Introduction to Probability Theory and Its Applications, vol. 1, third ed. Wiley, 1968.
17. G. Fraser and A. Arcuri, "Evolutionary Generation of Whole Test Suites," Proc. 11th Int'l Conf. Quality Software, pp. 31-40, 2011.
18. G. Fraser and A. Arcuri, "Evosuite: Automatic Test Suite Generation for Object- Oriented Software," Proc. 19th ACM SIGSOFT Symp. and the 13th European Conf. Foundations of Software Eng. , 2011.
19. G. Fraser and A. Arcuri, "It Is Not the Length That Matters, It Is How You Control it," Proc. Fourth IEEE Int'l Conf. Software Testing, Verification and Validation, pp. 150-159, 2011.
20. G. Fraser and A. Zeller, "Exploiting Common Object Usage in Test Case Generation," Proc. Fourth IEEE Int'l Conf. Software Testing, Verification and Validation, pp. 80-89, 2011.

Search-based Software Engineering Length Branch Coverage Genetic Algorithm Infeasible Goal Collateral Coverage