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.

REFERENCES

• 1: J. S. Dong, P. Hao, J. Sun, and X. Zhang. A Reasoning Method for Timed CSP Based on Constraint Solving. In Proc. of the 8th Inter. Conf. on Formal Engineering Methods (ICFEM 2006), pages 342--359. Springer, 2006.
• 2: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 3: Gerard J. Holzmann, The Model Checker SPIN, IEEE Transactions on Software Engineering, v.23 n.5, p.279-295, May 1997 [doi>10.1109/32.588521]
• 4: Gerard J. Holzmann, The Model Checker SPIN, IEEE Transactions on Software Engineering, v.23 n.5, p.279-295, May 1997 [doi>10.1109/32.588521]
• 5: J. Sun, Y. Liu, and J. S. Dong. A Simulator and Model Checker for Extended CSP. http://www.comp.nus.edu.sg/~liuyang/pat/, 2008.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Model checking

General Terms:
Verification

Keywords:
fairness, model checking, sat solvers, simulation