Shape Refinement through Explicit Heap Analysis

Shape analysis is a promising technique to prove program properties about recursive data structures. The challenge is to automatically determine the data-structure type, and to supply the shape analysis with the necessary information about the data structure. We present a stepwise approach to the selection of instrumentation predicates for a TVLA-based shape analysis, which takes us a step closer towards the fully automatic verification of data structures. The approach uses two techniques to guide the refinement of shape abstractions: (1) during program exploration, an explicit heap analysis collects sample instances of the heap structures, which are used to identify the data structures that are manipulated by the program; and (2) during abstraction refinement along an infeasible error path, we consider different possible heap abstractions and choose the coarsest one that eliminates the infeasible path. We have implemented this combined approach for automatic shape refinement as an extension of the software model checker BLAST. Example programs from a data-structure library that manipulate doubly-linked lists and trees were successfully verified by our tool.

Rosenblum, D.S.
Taentzer, G.
Published in:
Proceedings of the 13th Internation Conference on Fundamental Approaches to Software Engineering (FASE 2010, Paphos, Cyprus, March 22-26), 263-277
Presented at:
13th Internation Conference on Fundamental Approaches to Software Engineering (FASE), Paphos, Cyprus, March 22-26, 2010

 Record created 2010-02-01, last modified 2018-03-17

External link:
Download fulltext
Rate this document:

Rate this document:
(Not yet reviewed)