soc logo

"No bird soars too high, if he soars with his own wings."   W. Blake

Automatic Inference of Frame Axioms Using Static Analysis

2008_ASE_RH screenshot

Abstract

Many approaches to software verification are currently semi-automatic: a human must provide key logical insights — e.g., loop invariants, class invariants, and frame axioms that limit the scope of changes that must be analyzed. This paper describes a technique for automatically inferring frame axioms of procedures and loops using static analysis. The technique builds on a pointer analysis that generates limited information about all data structures in the heap. Our technique uses that information to over-approximate a potentially unbounded set of memory locations modified by each procedure/loop; this over-approximation is a candidate frame axiom. We have tested this approach on the buffer-overflow benchmarks from ASE 2007. With manually provided specifications and invariants/axioms, our tool could verify/falsify 226 of the 289 benchmarks. With our automatically inferred frame axioms, the tool could verify/falsify 203 of the 289, demonstrating the effectiveness of our approach.

Citation

Zvonimir Rakamaric, Alan J. Hu.
Automatic Inference of Frame Axioms Using Static Analysis
Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE 2008), 89--98, 2008.

BibTeX

@inproceedings{2008_ASE_RH,
  title = {Automatic Inference of Frame Axioms Using Static Analysis},
  author = {Zvonimir Rakamaric and Alan J. Hu.},
  booktitle = {Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE 2008)},
  editor = {Ahmed Bouajjani and Oded Maler},
  publisher = {IEEE},
  pages = {89--98},
  year = {2008}
}