Marc Brockschmidt, Sebastiaan J. C. Joosten, René Thiemann, Akihisa Yamada
Proceedings of the 26th International Confluence on Automated Deduction, Lecture Notes in Computer Science 10395, pp. 454-471, 2017.
pdf 
doi:10.1007/978-3-319-63046-5_28
Springer International Publishing AG
Abstract
Modern program analyzers translate imperative programs to an intermediate formal language like integer transition systems (ITSs), and then analyze properties of ITSs. Because of the high complexity of the task, a number of incorrect proofs are revealed annually in the Software Verification Competitions.
In this paper, we establish the trustworthiness of termination and safety proofs for ITSs. To this end we extend our Isabelle/HOL formalization IsaFoR by formalizing several verification techniques for ITSs, such as invariant checking, ranking functions, etc. Consequently the extracted certifier CeTA can now (in)validate safety and termination proofs for ITSs. We also adapted the program analyzers T2 and AProVE to produce machine-readable proof certificates, and as a result, most termination proofs generated by these tools on a standard benchmark set are now certified.
BibTex
@inproceedings{MBSJRTAY-CADE17, author = {Marc Brockschmidt and Sebastiaan J. C. Joosten and Ren{\'{e}} Thiemann and Akihisa Yamada}, editor = {Leonardo de Moura}, title = {Certifying Safety and Termination Proofs for Integer Transition Systems}, booktitle = {Proceedings of the 26th International Conference on Automated Deduction (CADE 2017)}, series = {Lecture Notes in Computer Science}, volume = {10395}, pages = {454--471}, publisher = {Springer}, year = {2017}, doi = {http://dx.doi.org/10.1007/978-3-319-63046-5_28},}