Teaching Formal Methods: Practice and Experience

BCS London Office, UK, 15 December 2006

AUTHORS

Ralph-Johan Back

ABSTRACT

There are a few standard approaches to constructing verified programs. The original approach, by Floyd, Naur and Hoare, assumes that the program code is given, together with an informal description of what the program is supposed to do.

Program verification amounts to expressing the requirements as precise pre- and postconditions, finding the appropriate loop invariants, constructing the verification conditions and proving them correct. This is known as a posteriori verification.

Dijkstra popularized an alternative approach, correct-by-construction, where we also start by formulating precise pre- and postconditions. Program code and loop invariants are then derived at the same time, hand in hand, and verification conditions are proved as they arise.

The third possibility, invariant based programming (Reynolds, van Emden, Back, see [1]), moves the construction of program code to an even later stage. Pre- and postconditions are formulated first, as in the other approaches. The next step is then to formulate the loop invariants, before any code is written.

The code is constructed last, as transitions between the different situations (precondition, postcondition, loop invariants) that can occur during program execution.

The verification conditions corresponding to these transitions are verified as they arise.

PAPER FORMATS

PDF Version of this Paper (41kb)