City Research Online

Abstract

Effective test case generation is crucial for ensuring software correctness, whereas generating high-coverage test suites efficiently remains a challenge. Graph transformations provide a formal way to specify and analyse software systems by modeling system operations as transformation rules and constructing a state-based representation of system behavior. Model-based testing (MBT) often uses model checking over this representation to discover execution paths that satisfy certain test requirements. However, such approaches suffer from severe scalability issues due to the rapid growth of the state space and the high computational cost of exhaustive exploration. While optimization-based approaches mitigate these issues by exploring a reduced portion of the state space, they still struggle to scale effectively. MBT approaches using graph transformation faces the same scalability and often face additional challenges due to the richer structural complexity of graph-based models. However, apart from the behavioral information derived from state transitions, graph transformation systems also encode explicit structural relationships between states and transformation rules. These structural characteristics can be used to define and evaluate test objectives. To exploit this, we propose a novel approach 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 optimize 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 minimizing 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 on well-known case studies demonstrate that our approach achieves higher coverage with reduced computational cost compared to state-of-the-art techniques.

Publication Type:	Article
Additional Information:	This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher Keywords:	Model checking-based testing, Test suite generation, Graph transformation systems, Deep reinforcement learning, Neural network
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments:	School of Science & Technology School of Science & Technology > Department of Computer Science
SWORD Depositor:	Symplectic Administrator

Export

Downloads