License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-7284
URL: http://drops.dagstuhl.de/opus/volltexte/2006/728/

Beyer, Dirk ; Henzinger, Thomas A. ; Théoduloz, Grégory

Lazy Shape Analysis

pdf-format:
Dokument 1.pdf (366 KB)


Abstract

Many software model checkers are based on predicate abstraction. If the verification goal depends on pointer structures, the approach does not work well, because it is difficult to find adequate predicate abstractions for the heap. In contrast, shape analysis, which uses graph-based heap abstractions, can provide a compact representation of recursive data structures. We integrate shape analysis into the software model checker BLAST. Because shape analysis is expensive, we do not apply it globally. Instead, we ensure that, like predicates, shape graphs are computed and stored locally, only where necessary for proving the verification goal. To achieve this, we extend lazy abstraction refinement, which so far has been used only for predicate abstractions, to three-valued logical structures. This approach does not only increase the precision of model checking, but it also increases the efficiency of shape analysis. We implemented the technique by extending BLAST with calls to TVLA.

BibTeX - Entry

@InProceedings{beyer_et_al:DSP:2006:728,
  author =	{Dirk Beyer and Thomas A. Henzinger and Gr{\'e}gory Th{\'e}oduloz},
  title =	{Lazy Shape Analysis},
  booktitle =	{Software Verification: Infinite-State Model Checking and Static Program Analysis},
  year =	{2006},
  editor =	{Parosh Aziz Abdulla and Ahmed Bouajjani and Markus M{\"u}ller-Olm },
  number =	{06081},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/728},
  annote =	{Keywords: Software model checking, Shape analysis, Counterexample-guided abstraction refinement, Interpolation, Predicate abstraction}
}

Keywords: Software model checking, Shape analysis, Counterexample-guided abstraction refinement, Interpolation, Predicate abstraction
Seminar: 06081 - Software Verification: Infinite-State Model Checking and Static Program Analysis
Issue date: 2006
Date of publication: 09.11.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI