Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 37 ยท Applications in CS

Hoare Logic and Program Verification

Prove programs correct with Hoare triples, loop invariants and weakest preconditions, and build a small verification-condition checker for an imperative mini-language in Python.

Testing shows that a program works on the inputs you tried. Program verification aims higher: prove it works on all inputs. The classic tool is Hoare logic (C. A. R. Hoare, 1969), a small formal system whose formulas are statements about programs. It applies the ideas of this chapter, a formal system with axioms and rules (formal systems), to code.

Hoare triples

A Hoare triple C {Q} says: if the precondition P holds before command C runs, and C terminates, then the postcondition Q holds afterwards. This is partial correctness; adding "and C does terminate" gives total correctness. P and Q are logical formulas about program variables, for instance {x โ‰ฅ 0} y := x + 1 {y > 0}.

The inference rules, one for each construct:

  • Assignment: {Q[e/x]} x := e {Q}. The precondition is Q with every x replaced by e. Example: {x + 1 > 0} y := x + 1 {y > 0} after renaming.
  • Sequence: from Cโ‚ {R} and Cโ‚‚ {Q} infer Cโ‚; Cโ‚‚ {Q}.
  • Conditional: from {P โˆง b} Cโ‚ {Q} and {P โˆง ยฌb} Cโ‚‚ {Q} infer if b then Cโ‚ else Cโ‚‚ {Q}.
  • Consequence: you may strengthen a precondition or weaken a postcondition.
  • While: from {I โˆง b} C {I} infer while b do C {I โˆง ยฌb}. Here I is the loop invariant.

A beginner mistake is to run the assignment rule forwards. It runs backwards: you start from the postcondition you want and compute the precondition.

Python Checking triples by testing on a grid of states

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Weakest preconditions

Dijkstra defined wp(C, Q): the weakest (most general) condition that guarantees Q after C. Then C {Q} is valid exactly when P โ‡’ wp(C, Q). The wp rules are mechanical, so a computer can generate them:

  • wp(x := e, Q) = Q[e/x]
  • wp(Cโ‚; Cโ‚‚, Q) = wp(Cโ‚, wp(Cโ‚‚, Q))
  • wp(if b then Cโ‚ else Cโ‚‚, Q) = (b โ‡’ wp(Cโ‚, Q)) โˆง (ยฌb โ‡’ wp(Cโ‚‚, Q))
  • For while, a loop invariant I supplies the proof obligations: I โˆง ยฌb โ‡’ Q and I โˆง b โ‡’ wp(body, I).

Deriving invariants is the hard creative step. Everything else is routine, which is why tools such as Dafny, Why3 and Frama-C ask you for invariants and discharge the remaining formulas with an SMT solver (an extension of the SAT solvers you met).

Verifying a loop

Initialization The invariant holds on entry
Preservation Each iteration keeps it true
Exit Invariant + loop ends gives Q
Termination A variant decreases to a bound

Partial correctness needs the first three; total correctness adds the last.

1 / 2

A small verification-condition checker

The checker below represents programs as tuples and predicates as Python functions over a state dict. wp pushes a postcondition backwards through the program. For while, it checks the two invariant obligations over a finite grid of states (a tool like Dafny proves them for all states).

Python wp for a mini language, applied to a summation loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The weak invariant fails because it does not tell the postcondition anything once the loop exits. A good invariant is inductive (preserved by the body) and strong enough to imply Q at exit.

Runtime assertions and design by contract

Even without a prover you can use the ideas. Add assert statements for the precondition, the invariant at the top of each loop iteration, and the postcondition. They check the contract on every run, find the first violation and document intent.

Python Invariant assertions inside a real loop (binary search)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Verification proves the program against its specification, not against what you meant. A wrong specification gives a proof of the wrong thing. Verified systems like seL4 and CompCert owe their value to careful, reviewed specifications.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the Hoare triple {P} C {Q} claim (partial correctness)?

    Partial correctness says Q holds on termination when the run started in a state satisfying P.
  2. 2. Which is the assignment axiom?

    Work backwards: the precondition is the postcondition with x replaced by e.
  3. 3. A good loop invariant must be

    The three conditions: initialization, preservation and usefulness at exit.
  4. 4. What is wp(C, Q)?

    Dijkstra's weakest precondition is the most general condition that ensures Q after C runs.

Summary

  • A Hoare triple C {Q} relates a precondition, a command and a postcondition; rules exist for assignment, sequence, conditional, consequence and while.
  • Weakest preconditions turn verification into logic: C {Q} holds iff P โ‡’ wp(C, Q).
  • Loops need an inductive invariant that holds at entry, is preserved, and implies the postcondition at exit.
  • Asserts make the same ideas executable; proving them for all inputs needs automated provers.

Next: Relational Algebra, Sets and SQL