Shape refinement through explicit heap analysis

D. Beyer, T.A. Henzinger, G. Théoduloz, D. Zufferey, in:, D. Rosenblum, G. Taenzer (Eds.), Springer, 2010, pp. 263–277.

Download
OA 312.15 KB

Conference Paper | Published | English
Author
; ; ;
Editor
;
Department
Series Title
LNCS
Abstract
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.
Publishing Year
Date Published
2010-04-21
Volume
6013
Page
263 - 277
Conference
FASE: Fundamental Approaches To Software Engineering
Conference Location
Paphos, Cyprus
Conference Date
2010-03-20 – 2010-03-28
IST-REx-ID

Cite this

Beyer D, Henzinger TA, Théoduloz G, Zufferey D. Shape refinement through explicit heap analysis. In: Rosenblum D, Taenzer G, eds. Vol 6013. Springer; 2010:263-277. doi:10.1007/978-3-642-12029-9_19
Beyer, D., Henzinger, T. A., Théoduloz, G., & Zufferey, D. (2010). Shape refinement through explicit heap analysis. In D. Rosenblum & G. Taenzer (Eds.) (Vol. 6013, pp. 263–277). Presented at the FASE: Fundamental Approaches To Software Engineering, Paphos, Cyprus: Springer. https://doi.org/10.1007/978-3-642-12029-9_19
Beyer, Dirk, Thomas A Henzinger, Grégory Théoduloz, and Damien Zufferey. “Shape Refinement through Explicit Heap Analysis.” edited by David Rosenblum and Gabriele Taenzer, 6013:263–77. Springer, 2010. https://doi.org/10.1007/978-3-642-12029-9_19.
D. Beyer, T. A. Henzinger, G. Théoduloz, and D. Zufferey, “Shape refinement through explicit heap analysis,” presented at the FASE: Fundamental Approaches To Software Engineering, Paphos, Cyprus, 2010, vol. 6013, pp. 263–277.
Beyer D, Henzinger TA, Théoduloz G, Zufferey D. 2010. Shape refinement through explicit heap analysis. FASE: Fundamental Approaches To Software Engineering, LNCS, vol. 6013. 263–277.
Beyer, Dirk, et al. Shape Refinement through Explicit Heap Analysis. Edited by David Rosenblum and Gabriele Taenzer, vol. 6013, Springer, 2010, pp. 263–77, doi:10.1007/978-3-642-12029-9_19.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:18:13Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar