Test Suite Generation with Memetic Algorithms and Dynamic Symbolic Execution

Genetic Algorithms have been successfully applied to generate 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 (i.e., Memetic Algorithms, MA) on primitive values contained in method sequences. In contrast to previous work on local search, we also consider string datatypes as primitives, and furthermore study search on path constraints in terms of Dynamic Symbolic Execution (DSE) to address this problem. A rigorous experimental methodology has been applied to properly evaluate the combination of MA with DSE. In our experiments on a set of open source classes of different kinds (e.g., numerical applications and text processing), the resulting MA+DSE technique increased branch coverage by 8% on average over the normal Genetic Algorithm.