Certifying Safety and Termination Proofs for Integer Transition Systems

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.


AModern 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.


  PDF |    doi:10.1007/978-3-319-63046-5_28 |  © Springer International Publishing AG


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 = {},
Nach oben scrollen