Verification of Sequential Imperative Programs in Isabelle/HOL

Norbert Schirmer



The purpose of this thesis is to create a verification environment for sequential imperative programs. First a general language model is proposed, which is independent of a concrete programming language but expressive enough to cover all common language features: mutually recursive procedures, abrupt termination and exceptions, runtime faults, local and global variables, pointers and heap, expressions with side effects, pointers to procedures, partial application and closures, dynamic method invocation and also unbounded nondeterminism.

For this language a Hoare logic for both partial and total correctness is developed and on top of it a verification condition generator is implemented. The Hoare logic is designed to allow the integration of program analysis or software model checking into the verification.

To demonstrate the continuity to a real programming language a subset of C is embedded into the verification environment.

The whole work is developed in the theorem prover Isabelle. Therefore the correctness is machine-checked and in addition the rich infrastructure of the general purpose theorem prover Isabelle can be employed for the verification of imperative programs.

 Online Copy

Available as PDF-File (1.5MB)

 BibTeX Entry

  author = 	 {Norbert Schirmer},
  title = 	 {Verification of Sequential Imperative Programs in {I}sabelle/{HOL}},
  school = 	 {Technische Universit\"at M\"unchen},
  year = 	 {2006},

Norbert Schirmer
Last modified: Mon Nov 7 15:14:15 CET 2005