Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-19T04:19:21.848Z Has data issue: false hasContentIssue false

Generalization strategies for the verification of infinite state systems

Published online by Cambridge University Press:  25 January 2012

FABIO FIORAVANTI
Affiliation:
Dipartimento di Scienze, Università ‘G. D'Annunzio’, Viale Pindaro 42, I-65127 Pescara, Italy (e-mail: fioravanti@sci.unich.it)
ALBERTO PETTOROSSI
Affiliation:
Dipartimento di Informatica, Sistemi e Produzione, Università di Roma Tor Vergata, Via del Politecnico 1, I-00133 Roma, Italy (e-mail: pettorossi@disp.uniroma2.it)
MAURIZIO PROIETTI
Affiliation:
CNR-IASI, Viale Manzoni 30, I-00185 Roma, Italy (e-mail: maurizio.proietti@iasi.cnr.it)
VALERIO SENNI
Affiliation:
LORIA-INRIA, 615, rue du Jardin Botanique BP 101, 54602 Villers-les-Nancy Cedex, France, & Dipartimento di Informatica, Sistemi e Produzione, Università di Roma Tor Vergata, Via del Politecnico 1, I-00133 Roma, Italy (e-mail: valerio.senni@loria.fr, senni@disp.uniroma2.it)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We present a method for the automated verification of temporal properties of infinite state systems. Our verification method is based on the specialization of constraint logic programs (CLP) and works in two phases: (1) in the first phase, a CLP specification of an infinite state system is specialized with respect to the initial state of the system and the temporal property to be verified, and (2) in the second phase, the specialized program is evaluated by using a bottom-up strategy. The effectiveness of the method strongly depends on the generalization strategy which is applied during the program specialization phase. We consider several generalization strategies obtained by combining techniques already known in the field of program analysis and program transformation, and we also introduce some new strategies. Then, through many verification experiments, we evaluate the effectiveness of the generalization strategies we have considered. Finally, we compare the implementation of our specialization-based verification method to other constraint-based model checking tools. The experimental results show that our method is competitive with the methods used by those other tools.

Information

Type
Regular Papers
Copyright
Copyright © Cambridge University Press 2012