uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Regular Model Checking for LTL(MSO)
Show others and affiliations
2004 In: Proc. 16th Int. Conf. on Computer Aided Verification, LNCSArticle in journal (Refereed) Published
Place, publisher, year, edition, pages
URN: urn:nbn:se:uu:diva-96978OAI: oai:DiVA.org:uu-96978DiVA: diva2:171733
Available from: 2008-03-28 Created: 2008-03-28Bibliographically approved
In thesis
1. Verifying Absence of ∞ Loops in Parameterized Protocols
Open this publication in new window or tab >>Verifying Absence of ∞ Loops in Parameterized Protocols
2008 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The complex behavior of computer systems offers many challenges for formal verification. The analysis quickly becomes difficult as the number of participating processes increases.

A parameterized system is a family of systems parameterized on a number n, typically representing the number of participating processes. The uniform verification problem — to check whether a property holds for each instance — is an infinite-state problem. The automated analysis of parameterized and infinite-state systems has been the subject of research over the last 15–20 years. Much of the work has focused on safety properties. Progress in verification of liveness properties has been slow, as it is more difficult in general.

In this thesis, we consider verification of parameterized and infinite-state systems, with an emphasis on liveness, in the verification framework called regular model checking (RMC). In RMC, states are represented as words, sets of states as regular expressions, and the transition relation as a regular relation.

We extend the automata-theoretic approach to RMC. We define a specification logic sufficiently strong to specify systems representable using RMC, and linear temporal logic properties of such systems, and provide an automatic translation from a specification into an analyzable model.

We develop acceleration techniques for RMC which allow more uniform and automatic verification than before, with greater power. Using these techniques, we succeed to verify safety and liveness properties of parameterized protocols from the literature.

We present a novel reachability based verification method for verification of liveness, in a general setting. We implement the method for RMC, with promising results.

Finally, we develop a framework for the verification of dynamic networks based on graph transformation, which generalizes the systems representable in RMC. In this framework we verify the latest version of the DYMO routing protocol, currently being considered for standardization by the IETF.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2008. 80 p.
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 419
formal methods, verification, model checking, infinite-state systems, regular model checking, liveness, graph transformation
urn:nbn:se:uu:diva-8605 (URN)978-91-554-7148-4 (ISBN)
Public defence
2008-04-18, 2446, MIC, Polacksbacken, Uppsala, 13:15
Available from: 2008-03-28 Created: 2008-03-28 Last updated: 2011-02-18Bibliographically approved

Open Access in DiVA

No full text

By organisation
Department of Information Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 177 hits
ReferencesLink to record
Permanent link

Direct link