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

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)},
  publisher = {IEEE Computer Society},
  pages = {89--98},
  doi = {10.1109/ASE.2008.19},
  year = {2008}
}

Acknowledgements

This work was supported by the Natural Sciences and Engineering Research Council of Canada and a University of British Columbia Graduate Fellowship.