Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
An Integrated Specification and Verification Technique for Highly Concurrent Data Structures
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. (Algorithmic Program Verification)
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. (Algorithmic Program Verification)
Brno University. (Automated Analysis and Verification Research Group - VeriFIT)
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
Visa övriga samt affilieringar
2013 (Engelska)Ingår i: Tools and Algorithms for the Construction and Analysis of Systems, 2013Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
2013.
Nyckelord [en]
verification, pointer program, queue, stack, unbounded concurrency, specification, linearizability
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:uu:diva-191330OAI: oai:DiVA.org:uu-191330DiVA: diva2:585343
Konferens
19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 16-24 March, 2013, Rome, ITALY
Projekt
UPMARC
Tillgänglig från: 2013-01-16 Skapad: 2013-01-10 Senast uppdaterad: 2015-11-10Bibliografiskt granskad
Ingår i avhandling
1. Few is Just Enough!: Small Model Theorem for Parameterized Verification and Shape Analysis
Öppna denna publikation i ny flik eller fönster >>Few is Just Enough!: Small Model Theorem for Parameterized Verification and Shape Analysis
2015 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Uppsala: Acta Universitatis Upsaliensis, 2015. 123 s.
Serie
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1302
Nyckelord
program verification, model checking, parameterized systems, infinite-state systems, reachability, approximation, safety, tree systems, shape analysis, small model properties, view abstraction, monotonic abstraction
Nationell ämneskategori
Datorsystem
Forskningsämne
Datavetenskap
Identifikatorer
urn:nbn:se:uu:diva-264171 (URN)978-91-554-9366-0 (ISBN)
Disputation
2015-11-18, ITC 2446, Lägerhyddsvägen 2, Uppsala, 13:00 (Engelska)
Opponent
Handledare
Tillgänglig från: 2015-10-28 Skapad: 2015-10-06 Senast uppdaterad: 2015-12-17

Open Access i DiVA

tacas2013(353 kB)416 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 353 kBChecksumma SHA-512
fc32f5e415624c6ddbf1f52c200a4ca42c4b8cc7ad80d37ff9735142b6f852c3fda7075ee726bd2e99da785f1b98e4fb505bde814e73ef240e5ab83baa599bee
Typ fulltextMimetyp application/pdf

Personposter BETA

Abdulla, Parosh AzizHaziza, FrédéricJonsson, Bengt

Sök vidare i DiVA

Av författaren/redaktören
Abdulla, Parosh AzizHaziza, FrédéricJonsson, Bengt
Av organisationen
Datorteknik
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 416 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 712 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf