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},
}