Synthesis of Circular Compositional Program Proofs via Abduction

Boyang Li, Isil Dillig, Thomas Dillig, Kenneth L. McMillan, Mooly Sagiv

Abstract

This paper presents a technique for synthesizing circular compositional proofs of program correctness. Our technique uses abductive inference to decompose the proof into small lemmas, which are represented as small program fragments annotated with pre and post-conditions. Different tools are used to discharge each different lemma, combining the strengths of different verifiers. Furthermore, each lemma concerns the correctness of small syntactic fragments of the program, addressing scalability concerns. We have implemented this technique and used it combine four different verification tools. Our experiments show that our technique can be successfully used to verify applications that cannot be verified by any individual technique.
BibTeX
@inproceedings{li2013synthesis,
  author = {Boyang Li and Isil Dillig and Thomas Dillig and Kenneth L. McMillan and Mooly Sagiv},
  title = {{Synthesis of Circular Compositional Program Proofs via Abduction}},
  booktitle = {TACAS},
  year = {2013},
  doi = {10.1007/978-3-642-36742-7\_26},
}

Loading related content...

Figure