Automated Test Case Generation as a Many-Objective Optimisation Problem with Dynamic Selection of the Targets

Abstract

The test case generation is intrinsically a multi-objective problem, since the goal is covering multiple test targets (e.g., branches). Existing search-based approaches either consider one target at a time or aggregate all targets into a single fitness function (whole-suite approach). Multi and many-objective optimisation algorithms (MOAs) have never been applied to this problem, because existing algorithms do not scale to the number of coverage objectives that are typically found in real-world software. In addition, the final goal for MOAs is to find alternative trade-off solutions in the objective space, while in test generation the interesting solutions are only those test cases covering one or more uncovered targets. In this paper, we present Dynamic Many-Objective Sorting Algorithm (DynaMOSA), a novel many-objective solver specifically designed to address the test case generation problem in the context of coverage testing. DynaMOSA extends our previous many-objective technique Many-Objective Sorting Algorithm (MOSA) with dynamic selection of the coverage targets based on the control dependency hierarchy. Such extension makes the approach more effective and efficient in case of limited search budget. We carried out an empirical study on 346 Java classes using three coverage criteria (i.e., statement, branch, and strong mutation coverage) to assess the performance of DynaMOSA with respect to the whole-suite approach (WS), its archive-based variant (WSA) and MOSA. The results show that DynaMOSA outperforms WSA in 28 percent of the classes for branch coverage (+8 percent more coverage on average) and in 27 percent of the classes for mutation coverage (+11 percent more killed mutants on average). It outperforms WS in 51 percent of the classes for statement coverage, leading to +11 percent more coverage on average. Moreover, DynaMOSA outperforms its predecessor MOSA for all the three coverage criteria in 19 percent of the classes with +8 percent more code coverage on average.