Shape Analysis of Sets

Author Jan Reineke



PDF
Thumbnail PDF

File

OASIcs.TrustworthySW.2006.698.pdf
  • Filesize: 442 kB
  • 19 pages

Document Identifiers

Author Details

Jan Reineke

Cite As Get BibTex

Jan Reineke. Shape Analysis of Sets. In Workshop on Trustworthy Software. Open Access Series in Informatics (OASIcs), Volume 3, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006) https://doi.org/10.4230/OASIcs.TrustworthySW.2006.698

Abstract

Shape Analysis is concerned with determining "shape invariants", i.e. structural properties of the heap, for programs that manipulate pointers and heap-allocated storage. Recently, very precise shape analysis algorithms have been developed that are able to prove the partial correctness of heap-manipulating programs. We explore the use of shape analysis to analyze abstract data types (ADTs). The ADT Set shall serve as an example, as it is widely used and can be found in most of the major data type libraries, like STL, the Java API, or LEDA. We formalize our notion of the ADT Set by algebraic specification. Two prototypical C set implementations are presented, one based on lists, the other on trees. We instantiate a parametric shape analysis framework to generate analyses that are able to prove the compliance of the two implementations to their specification.

Subject Classification

Keywords
  • Shape analysis
  • adt
  • algebraic specification
  • invariants
  • verification
  • set implementations
  • imperative programs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail