Whole test suite generation from graph transformation specifications using ant colony optimization

Model-based testing is an automated process to generate tests from behavioral models of a system under test. Model checking is a verification technique to prove/falsify properties through exploring a state system’s space. In the literature, model-based testing often uses model checking to generate execution paths as test cases. However, due to state space explosion, exploring the whole state space may not be possible. Recently, methods based on meta-heuristics have been proposed to cope with this challenge, including evolutionary approaches. In these methods, a tolerable portion of the state space is explored heuristically, optimizing the generated paths to cover the test objectives. Generally, these methods result in large test suites that are hard to evaluate manually and less useful in practice. In this paper, a novel method based on the ant colony optimization is proposed for systems specified through graph transformations. Our approach generates and evaluates the test suite as a whole, aiming to cover test objectives along test paths as soon as possible. This is the first method specifically designed for model-based whole test suite generation, offering a fresh perspective on optimizing test coverage in complex systems. The method is implemented in GROOVE, an open-source toolset for designing and model checking graph transformation systems. Experimental results on well-known case studies show that we generate smaller test suites with better coverage while the speed of convergence is significantly improved.