Test Case Generation from Graph Transformation Systems Using Deep Reinforcement Learning

Graph transformations can be used to specify and analyse software systems by modelling operations as rules and generating the labelled transition system (LTS) as a representation of system behaviour. Model-based testing (MBT) often uses model checking over LTS to discover paths that satisfy certain test requirements. Significant challenges include the size of the state space and the complexity of model checking. Meta-heuristic search-based approaches try to cope with this problem by exploring only a small portion of the LTS to produce paths that cover maximal test objectives. Despite acceptable results in small case studies, these approaches also do not scale well.MBT approaches using graph transformation face the same limitations as LTS-based MBT in general, exacerbated by the more complex nature of graph-based LTS. However, apart from the behavioural information of the LTS, here we are able to use the graph structure of states and rules to define and evaluate test objectives. This enables a new method based on deep reinforcement learning to generate test suites for systems specified through graph transformations.We use the reward/penalty mechanism of reinforcement learning to optimise the selection of moves within the state space, enabling the generation of test cases based on prior decisions. Our goal is to achieve greater coverage of test objectives while minimising the size of the test cases. The method has been implemented in GROOVE, an open-source toolset for designing and model checking graph transformation systems. Experimental results in well-known case studies demonstrate that our approach generates test cases with improved coverage scores while reducing the cost of testing compared to existing works.