Lazy shape analysis

D. Beyer, T.A. Henzinger, G. Théoduloz, in:, Springer, 2006, pp. 532–546.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ;
Series Title
LNCS
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.
Publishing Year
Date Published
2006-08-08
Volume
4144
Page
532 - 546
Conference
CAV: Computer Aided Verification
IST-REx-ID

Cite this

Beyer D, Henzinger TA, Théoduloz G. Lazy shape analysis. In: Vol 4144. Springer; 2006:532-546. doi:10.1007/11817963_48
Beyer, D., Henzinger, T. A., & Théoduloz, G. (2006). Lazy shape analysis (Vol. 4144, pp. 532–546). Presented at the CAV: Computer Aided Verification, Springer. https://doi.org/10.1007/11817963_48
Beyer, Dirk, Thomas A Henzinger, and Grégory Théoduloz. “Lazy Shape Analysis,” 4144:532–46. Springer, 2006. https://doi.org/10.1007/11817963_48.
D. Beyer, T. A. Henzinger, and G. Théoduloz, “Lazy shape analysis,” presented at the CAV: Computer Aided Verification, 2006, vol. 4144, pp. 532–546.
Beyer D, Henzinger TA, Théoduloz G. 2006. Lazy shape analysis. CAV: Computer Aided Verification, LNCS, vol. 4144. 532–546.
Beyer, Dirk, et al. Lazy Shape Analysis. Vol. 4144, Springer, 2006, pp. 532–46, doi:10.1007/11817963_48.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar