User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Verification of Certifying Computations


Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Rizkallah,  Christine
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Alkassar, E., Böhme, S., Mehlhorn, K., & Rizkallah, C. (2011). Verification of Certifying Computations. In G. Gopalakrishnan, & S. Qadeer (Eds.), Computer Aided Verification (pp. 67-82). Berlin: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0010-12BF-E
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 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.