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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Few is Just Enough!: Small Model Theorem for Parameterized Verification and Shape Analysis
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (APV)
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This doctoral thesis considers the automatic verification of parameterized systems, i.e. systems with an arbitrary number of communicating components, such as mutual exclusion protocols, cache coherence protocols or heap manipulating programs. The components may be organized in various topologies such as words, multisets, rings, or trees.

The task is to show correctness regardless of the size of the system and we consider two methods to prove safety:(i) a backward reachability analysis, using the well-quasi ordered framework and monotonic abstraction, and (ii) a forward analysis which only needs to inspect a small number of components in order to show correctness of the whole system. The latter relies on an abstraction function that views the system from the perspective of a fixed number of components. The abstraction is used during the verification procedure in order to dynamically detect cut-off points beyond which the search of the state-space need not continue.

Our experimentation on a variety of benchmarks demonstrate that the method is highly efficient and that it works well even for classes of systems with undecidable property. It has been, for example, successfully applied to verify a fine-grained model of Szymanski's mutual exclusion protocol. Finally, we applied the methods to solve the complex problem of verifying highly concurrent data-structures, in a challenging setting: We do not a priori bound the number of threads, the size of the data-structure, the domain of the data to store nor do we require the presence of a garbage collector. We successfully verified the concurrent Treiber's stack and Michael & Scott's queue, in the aforementioned setting.

To the best of our knowledge, these verification problems have been considered challenging in the parameterized verification community and could not be carried out automatically by other existing methods.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2015. , 123 p.
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1302
Keyword [en]
program verification, model checking, parameterized systems, infinite-state systems, reachability, approximation, safety, tree systems, shape analysis, small model properties, view abstraction, monotonic abstraction
National Category
Computer Systems
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-264171ISBN: 978-91-554-9366-0 (print)OAI: oai:DiVA.org:uu-264171DiVA: diva2:859328
Public defence
2015-11-18, ITC 2446, Lägerhyddsvägen 2, Uppsala, 13:00 (English)
Opponent
Supervisors
Available from: 2015-10-28 Created: 2015-10-06 Last updated: 2015-12-17
List of papers
1. All for the price of few: (Parameterized verification through view abstraction)
Open this publication in new window or tab >>All for the price of few: (Parameterized verification through view abstraction)
2013 (English)In: Verification, Model Checking, and Abstract Interpretation, Springer Berlin/Heidelberg, 2013, 476-495 p.Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013
Series
Lecture Notes in Computer Science, 7737
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-190003 (URN)10.1007/978-3-642-35873-9_28 (DOI)978-3-642-35872-2 (ISBN)
Conference
VMCAI 2013, January 20-22, Rome, Italy
Projects
UPMARC
Available from: 2013-01-09 Created: 2013-01-07 Last updated: 2015-11-10Bibliographically approved
2. An Integrated Specification and Verification Technique for Highly Concurrent Data Structures
Open this publication in new window or tab >>An Integrated Specification and Verification Technique for Highly Concurrent Data Structures
Show others...
2013 (English)In: Tools and Algorithms for the Construction and Analysis of Systems, 2013Conference paper, Published paper (Refereed)
Abstract [en]

We present a technique for automatically verifying safety properties of concurrent programs, in particular programs which rely on subtle dependen- cies of local states of different threads, such as lock-free implementations of stacks and queues in an environment without garbage collection. Our technique addresses the joint challenges of infinite-state specifications, an unbounded num- ber of threads, and an unbounded heap managed by explicit memory allocation. Our technique builds on the automata-theoretic approach to model checking, in which a specification is given by an automaton that observes the execution of a program and accepts executions that violate the intended specification. We extend this approach by allowing specifications to be given by a class of infinite-state au- tomata. We show how such automata can be used to specify queues, stacks, and other data structures, by extending a data-independence argument. For verifica- tion, we develop a shape analysis, which tracks correlations between pairs of threads, and a novel abstraction to make the analysis practical. We have imple- mented our method and used it to verify programs, some of which have not been verified by any other automatic method before.

Keyword
verification, pointer program, queue, stack, unbounded concurrency, specification, linearizability
National Category
Computer Science
Identifiers
urn:nbn:se:uu:diva-191330 (URN)
Conference
19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 16-24 March, 2013, Rome, ITALY
Projects
UPMARC
Available from: 2013-01-16 Created: 2013-01-10 Last updated: 2015-11-10Bibliographically approved
3. Block me if you can!: Context-sensitive parameterized verification
Open this publication in new window or tab >>Block me if you can!: Context-sensitive parameterized verification
2014 (English)In: Static Analysis: SAS 2014, Springer, 2014, 1-17 p.Conference paper, Published paper (Refereed)
Abstract [en]

We present a method for automatic verification of systems with a parameterized number of communicating processes, such as mutual exclusion protocols or agreement protocols. To that end, we present a powerful abstraction framework that uses an efficient and precise symbolic encoding of (infinite) sets of configurations. In particular, it generalizes downward-closed sets that have successfully been used in earlier approaches to parameterized verification. We show experimentally the efficiency of the method, on various examples, including a fine-grained model of Szymanski’s mutual exclusion protocol, whose correctness, to the best of our knowledge, has not been proven automatically by any other existing methods.

Place, publisher, year, edition, pages
Springer, 2014
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8723
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-260087 (URN)10.1007/978-3-319-10936-7_1 (DOI)000360204700001 ()978-3-319-10935-0 (ISBN)
Conference
21st International Symposium, SAS 2014, September 11–13, Munich, Germany
Projects
UPMARC
Available from: 2014-09-13 Created: 2015-08-15 Last updated: 2015-12-16Bibliographically approved
4. Monotonic abstraction for programs with dynamic memory heaps
Open this publication in new window or tab >>Monotonic abstraction for programs with dynamic memory heaps
Show others...
2008 (English)In: Computer Aided Verification / [ed] Gupta A, Malik S, Berlin: Springer-Verlag , 2008, 341-354 p.Conference paper, Published paper (Refereed)
Abstract [en]

We propose a new approach for automatic verification of programs with dynamic heap manipulation. The method is based on symbolic (backward) reachability analysis using upward-closed sets of heaps w.r.t. an appropriate preorder on graphs. These sets are represented by a finite set of minimal graph patterns corresponding to a set of bad configurations. We define an abstract semantics for the programs which is monotonic w.r.t. the preorder. Moreover, we prove that our analysis always terminates by showing that the preorder is a well-quasi ordering. Our results are presented for the case of programs with 1-next selector. We provide experimental results showing the effectiveness of our approach.

Place, publisher, year, edition, pages
Berlin: Springer-Verlag, 2008
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 5123
National Category
Computer Science
Identifiers
urn:nbn:se:uu:diva-106059 (URN)10.1007/978-3-540-70545-1_33 (DOI)000257539900033 ()
Conference
20th International Conference on Computer Aided Verification Princeton, NJ, JUL 07, 2008
Available from: 2009-06-13 Created: 2009-06-13 Last updated: 2015-11-10Bibliographically approved
5. Parameterized tree systems
Open this publication in new window or tab >>Parameterized tree systems
Show others...
2008 (English)In: Formal Techniques for Networked and Distributed Systems: FORTE 2008 / [ed] Suzuki K, Berlin: Springer-Verlag , 2008, 69-83 p.Conference paper, Published paper (Refereed)
Abstract [en]

Several recent works have considered parameterized verification, i.e. automatic verification of systems consisting of an arbitrary number of finite-state processes organized in a linear array. The aim of this paper is to extend these works by giving a simple and efficient method to prove safety properties for systems with tree-like architectures. A process in the system is a finite-state automaton and a transition is performed jointly by a process and its parent and children processes. The method derives an over-approximation of the induced transition system, which allows the use of finite trees as symbolic representations of infinite sets of configurations. Compared to traditional methods for parameterized verification of systems with tree topologies, our method does not require the manipulation of tree transducers, hence its simplicity and efficiency. We have implemented a prototype which works well on several nontrivial tree-based protocols.

Place, publisher, year, edition, pages
Berlin: Springer-Verlag, 2008
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 5048
National Category
Computer Science
Identifiers
urn:nbn:se:uu:diva-106058 (URN)10.1007/978-3-540-68855-6_5 (DOI)000256666500005 ()978-3-540-68854-9 (ISBN)
Conference
28th International Conference on Formal Techniques for Networked and Distributed Systems Tokyo, JAPAN, JUN 10-13, 2008
Available from: 2009-06-13 Created: 2009-06-13 Last updated: 2015-11-10Bibliographically approved
6. Model checking race-freeness
Open this publication in new window or tab >>Model checking race-freeness
2008 (English)In: SIGARCH Computer Architecture News, ISSN 0163-5964, E-ISSN 1943-5851, Vol. 36, no 5, 72-79 p.Article in journal (Refereed) Published
National Category
Computer Science
Identifiers
urn:nbn:se:uu:diva-142914 (URN)10.1145/1556444.1556454 (DOI)
Available from: 2011-01-17 Created: 2011-01-17 Last updated: 2017-12-11Bibliographically approved
7. Parameterized verification through view abstraction
Open this publication in new window or tab >>Parameterized verification through view abstraction
2016 (English)In: International Journal on Software Tools for Technology Transfer (STTT), ISSN 1433-2779, E-ISSN 1433-2787, Vol. 18, no 5, 495-516 p.Article in journal (Refereed) Published
Abstract [en]

We present a simple and efficient framework for automatic verification of systems with a parametric number of communicating processes. The processes may be organized in various topologies such as words, multisets, rings, or trees. Our method needs to inspect only a small number of processes in order to show correctness of the whole system. It relies on an abstraction function that views the system from the perspective of a fixed number of processes. The abstraction is used during the verification procedure in order to dynamically detect cut-off points beyond which the search of the state space need not continue. We show that the method is complete for a large class of well quasi-ordered systems including Petri nets. Our experimentation on a variety of benchmarks demonstrate that the method is highly efficient and that it works well even for classes of systems with undecidable verification problems. In particular, the method handles the fine-grained and full version of Szymanski's mutual exclusion protocol, whose correctness, to the best of our knowledge, has not been proven automatically by any other existing methods.

Keyword
Parameterized systems; Safety; Small model properties; View abstraction
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-260089 (URN)10.1007/s10009-015-0406-x (DOI)000382011100003 ()
Projects
UPMARC
Available from: 2015-11-23 Created: 2015-08-15 Last updated: 2017-12-04Bibliographically approved

Open Access in DiVA

fulltext(1120 kB)227 downloads
File information
File name FULLTEXT02.pdfFile size 1120 kBChecksum SHA-512
d4cfdd4f3837e3bd2f3a412151e4620904443324cc882a6fff9a9eaa3a6573b7cb29df6dacac7a170692f089392a251f32e80f63e19fdd6e3b8926c623c9fdfc
Type fulltextMimetype application/pdf
Buy this publication >>

Authority records BETA

Haziza, Frédéric

Search in DiVA

By author/editor
Haziza, Frédéric
By organisation
Division of Computer SystemsComputer Systems
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 227 downloads
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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 5870 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf