Model-Based Test Case Generation from Graph Transformation Specifications using Beam Search Algorithm

Software testing is one of the key activities in software development life cycle that plays an important role in software quality. More than half of the software development costs and time are often spent on the test. Obviously, the automation of software testing, especially in generating test cases that is a key activity of this process, will dramatically reduce the costs. Among the prosperous testing techniques is model-based testing that utilizes model checker tools to automatically extract test cases. However, as these tools basically designed for model verification, not for test generation, the researches in the testing context are encountered with some major challenges such as state space explosion problem and duplication of the vast majority of test cases. In this paper, we propose a novel method using Beam-search algorithm for generating tests from systems specified through graph transformation specification. The popopsed approach not only improvs the mentioned challenges, but also generates the test suites with high coverage and low size in a desired time budget. We implemented it in the model checker tool GROOVE. To assess the efficiency of our approach, we compared it with model checker-assisted testing, search-based testing strategies and random testing. The empirical results over some case studies in the domain of service-oriented systems confirm it's superiority in terms of coverage size, test suit size and speed.