uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Block me if you can!: Context-sensitive parameterized verification
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
2014 (engelsk)Inngår i: Static Analysis: SAS 2014, Springer, 2014, s. 1-17Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
Springer, 2014. s. 1-17
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8723
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-260087DOI: 10.1007/978-3-319-10936-7_1ISI: 000360204700001ISBN: 978-3-319-10935-0 (tryckt)OAI: oai:DiVA.org:uu-260087DiVA, id: diva2:846306
Konferanse
21st International Symposium, SAS 2014, September 11–13, Munich, Germany
Prosjekter
UPMARCTilgjengelig fra: 2014-09-13 Laget: 2015-08-15 Sist oppdatert: 2015-12-16bibliografisk kontrollert
Inngår i avhandling
1. Few is Just Enough!: Small Model Theorem for Parameterized Verification and Shape Analysis
Åpne denne publikasjonen i ny fane eller vindu >>Few is Just Enough!: Small Model Theorem for Parameterized Verification and Shape Analysis
2015 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Uppsala: Acta Universitatis Upsaliensis, 2015. s. 123
Serie
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1302
Emneord
program verification, model checking, parameterized systems, infinite-state systems, reachability, approximation, safety, tree systems, shape analysis, small model properties, view abstraction, monotonic abstraction
HSV kategori
Forskningsprogram
Datavetenskap
Identifikatorer
urn:nbn:se:uu:diva-264171 (URN)978-91-554-9366-0 (ISBN)
Disputas
2015-11-18, ITC 2446, Lägerhyddsvägen 2, Uppsala, 13:00 (engelsk)
Opponent
Veileder
Prosjekter
UPMARC
Tilgjengelig fra: 2015-10-28 Laget: 2015-10-06 Sist oppdatert: 2019-02-25

Open Access i DiVA

fulltext(588 kB)132 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 588 kBChecksum SHA-512
964ee1476ecb2083a384c7c816b4f7542a0f3d8a9a9bf73a0a060a941b284f5a00d62634d515ce406b4483ae6d907df83803cde7a59690d1734fd858a54b56cb
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekst

Personposter BETA

Abdulla, Parosh AzizHaziza, Frédéric

Søk i DiVA

Av forfatter/redaktør
Abdulla, Parosh AzizHaziza, Frédéric
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 132 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 2552 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf