An empirical comparison of combinatorial testing and search-based testing in the context of automated and autonomous driving systems

Context: More automated and autonomous systems are becoming daily use that implements safety–critical functions, e.g., autonomous driving or mobile robots. Testing such systems people depend on is challenging because some environmental interactions may not be expected during development but occur when those systems are in operation. Deciding when to stop testing or answering how to ensure sufficient testing is challenging and very expensive. Objectives: For generating critical environmental interactions, i.e., critical scenarios, we present and compare two testing solutions focusing on generating critical scenarios utilizing combinatorial and search-based testing, respectively. Methods: For combinatorial testing, we suggest using ontologies that describe the environment of an autonomous or highly automated system. For search-based testing, we rely on genetic algorithms. We experimentally compared the two testing approaches using two implementations of an industrial emergency braking function and random testing as the baseline. Furthermore, we compared the approaches qualitatively using several categories. Results: From the experiments, we see that the combinatorial testing approach can find all different types of faults listed in Table 5 considering a combinatorial strength of 3. This is not the case for search-based and random testing in all experiments. Combinatorial testing comes with the highest combinatorial coverage. However, all approaches can reveal faulty behavior utilizing appropriate environmental models. Conclusion: We present the results of an in-depth comparison of combinatorial and search-based testing. The be as fair as possible, the comparison relied on the same environmental model and other parameters like the number of generated test cases. The results show that combinatorial testing comes with the highest coverage and can find all different kinds of failures summarized in Table 5 providing a certain strength. Meanwhile, search-based testing is also capable of finding different failures depending on the coverage it can reach. Both approaches seem complementary and of use for the application domain of autonomous and automated driving functions.