A Hybrid Meta-heuristic Approach to Cope with State Space Explosion in Model Checking Technique for Deadlock Freeness

Abstract

Model checking is an automatic technique for software verification through which all reachable states are generated from an initial state to finding errors and desirable patterns. In the model checking approach, the behavior and structure of system should be modeled. Graph transformation system is a graphical formal modeling language to specify and model the system. However, modeling of large systems with the graph transformation system suffers from the state space explosion problem which usually requires huge amounts of computational resources. In this paper, we propose a hybrid meta-heuristic approach to deal with this searching problem in the graph transformation system because meta-heuristic algorithms are efficient solutions to traverse the graph of large systems. Our approach, using Artificial Bee Colony and Simulated Annealing, replaces a full state space generation, only by producing part of it checking the safety, and finding errors (e.g., deadlock). The experimental results show that our proposed approach is more efficient and accurate compared to other approaches.

Keywords

• software verification
• model checking
• state space explosion
• meta-heuristic approaches
• graph transformation system