Verification of Certifying Computations

Eyad Alkassar, Sascha Böhme, Kurt Mehlhorn and Christine Rizkallah

Document: DOI PDF

Abstract: Formal verification of complex algorithms is challenging. Verifying their implementations goes beyond the state of the art of current verification tools and proving their correctness usually involves non-trivial mathematical theorems. Certifying algorithms compute in addition to each output a witness certifying that the output is correct. A checker for such a witness %requires an order of magnitude less size and is usually much simpler than the original algorithm – yet it is all the user has to trust. Verification of checkers is feasible with current tools and leads to computations that can be completely trusted. In this paper we develop a framework to seamlessly verify certifying computations. The automatic verifier VCC is used for checking code correctness, and the interactive theorem prover Isabelle/HOL targets high-level mathematical properties of algorithms. We demonstrate the effectiveness of our approach by applying it to the verification of the algorithmic library LEDA.

Files:

Bibtex entry:

@inproceedings{
   author    = {Eyad Alkassar and Sascha B{\"o}hme and Kurt Mehlhorn
                and Christine Rizkallah},
   title     = {Verification of Certifying Computations},
   booktitle = {Computer Aided Verification},
   editor    = {Ganesh Gopalakrishnan and Shaz Qadeer},
   series    = {Lecture Notes in Computer Science},
   publisher = {Springer},
   volume    = 6806,
   year      = 2011,
   pages     = {67--82},
}