×

zbMATH — the first resource for mathematics

Efficient approximate verification of Promela models via symmetry markers. (English) Zbl 1141.68453
Namjoshi, Kedar S. (ed.) et al., Automated technology for verification and analysis. 5th international symposium, ATVA 2007 Tokyo, Japan, October 22–25, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-75595-1/pbk). Lecture Notes in Computer Science 4762, 300-315 (2007).
Summary: We present a new verification technique for Promela which exploits state-space symmetries induced by scalarset values used in a model. The technique involves efficiently computing a marker for each state encountered during search. We propose a complete verification method which only partially exploits symmetry, and an approximate verification method which fully exploits symmetry. We describe how symmetry markers can be efficiently computed and integrated into the Spin tool, and provide an empirical evaluation of our technique using the Topspin symmetry reduction package, which shows very good performance results and a high degree of precision for the approximate method (i.e. very few non-symmetric states receive the same marker). We also identify a class of models for which the approximate technique is precise.
For the entire collection see [Zbl 1138.68006].

MSC:
68Q60 Specification and verification (program logics, model checking, etc.)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Software:
TopSpin
PDF BibTeX XML Cite
Full Text: DOI