An analyzer for extended compositional process algebras

Abstract

System simulation and verification become more demanding as complexity grows. PAT is developed as an interactive system to support composing, simulating and reasoning of process algebra with various extensions like fairness events, global variables and parameterized processes. PAT provides user friendly interfaces to support system modeling and simulation. Furthermore, it embeds two complementing model checking techniques catering for different systems and properties, namely, an explicit on-the-fly model checker which is designed to verify event-based fairness constraints efficiently and a bounded model checker based on state-of-the-art SAT solvers. The model checkers are capable of proving reachability, deadlock-freeness and the full set of Linear Temporal Logic (LTL) properties. Compared to other model checkers, PAT has two key advantages. Firstly, it supports an intuitive annotation of fairness constraints so that it handles large number of fairness constraints efficiently. Secondly, the compositional encoding of system models as SAT problems allows us to handle compositional process algebra effectively. The experimental results show that PAT is capable of verifying systems with large number of states and outperforms the state-of-the-art model checkers in some cases. © May 10-18, 2008.