Building a pushbutton RESOLVE verifier Progress

Authors: Murali Sitaraman Bruce Adcock Jeremy Avigad Derek Bronish Paolo Bucci David Frazier Harvey M Friedman Heather Harton Wayne Heym Jason Kirschenbaum Joan Krone Hampton Smith Bruce W Weide

Publish Date: 2010/04/14

Volume: 23, Issue: 5, Pages: 607-626

PDF Link

Abstract

A central objective of the verifying compiler grand challenge is to develop a pushbutton verifier that generates proofs of correctness in a syntaxdriven fashion similar to the way an ordinary compiler generates machine code The software developer’s role is then to provide suitable specifications and annotated code but otherwise to have no direct involvement in the verification step However the general mathematical developments and results upon which software correctness is based may be established through a separate formal proof process in which proofs might be mechanically checked but not necessarily automatically generated While many ideas that could conceivably form the basis for software verification have been known “in principle” for decades and several tools to support an aspect of verification have been devised practical fully automated verification of full software behavior remains a grand challenge This paper explains how RESOLVE takes a step towards addressing this challenge by integrating foundational and practical elements of software engineering programming languages and mathematical logic into a coherent framework Current versions of the RESOLVE verifier generate verification conditions VCs for the correctness of componentbased software in a modular fashion—one component at a time The VCs are currently verified using automated capabilities of the Isabelle proof assistant the SMT solver Z3 a minimalist rewrite prover and some specialized decision procedures Initial experiments with the tools and further analytic considerations show both the progress that has been made and the challenges that remain

Keywords: