An Isabelle/HOL formalization of AProVE’s termination method for LLVM IR
Max Haslbeck, Rene Thiemann10th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2021), pp. 238 – 249, 2021.
Abstract
AProVE is a powerful termination prover for various programming languages, including a termination analysis method for imperative programs specified in the LLVM intermediate representation (IR). The method internally works in three steps: first, it transforms LLVM IR code into a symbolic execution graph; second, the graph is translated into an integer transition system; finally, termination of the transition system is proved by the back end of AProVE. Since AProVE is unverified software, our aim is to increase its reliability by certifying the generated proofs. To this end, we require formal semantics of all program representations, i.e., for LLVM IR, for symbolic execution graphs and for integer transition systems. As the latter is already available, we define the former ones. We note that our semantics for LLVM IR use arithmetic with unbounded integers. We further verify the first and the second step of AProVE’s termination method, including verified algorithms to check concrete proofs. Since the third step can already be certified, we obtain a complete formally verified method for certifying AProVE’s termination proofs of LLVM IR programs. The whole formalization has been done in Isabelle/HOL and our certifier is available as a Haskell program via code generation.
BibTeX
@inproceedings{10.1145/3437992.3439935, author = {Haslbeck, Max W. and Thiemann, Ren\'{e}}, title = {An Isabelle/HOL Formalization of AProVE’s Termination Method for LLVM IR}, year = {2021}, isbn = {9781450382991}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3437992.3439935}, doi = {10.1145/3437992.3439935}, pages = {238–249}, numpages = {12}, keywords = {static program analysis, Isabelle/HOL, termination analysis, formal verification}, location = {Virtual, Denmark}, series = {CPP 2021} }