Hoare Logic — Axiomatic Semantics for Program Verification

In this tutorial, you'll learn about Hoare Logic. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Hoare logic provides an axiomatic system for proving partial and total correctness of imperative programs using Hoare triples that specify preconditions, program statements, and postconditions.

Learning Path

flowchart LR
  A["First-Order Logic"] --> B["Hoare Logic
Axiomatic Semantics"]
  B --> C["Separation Logic"]
  B --> D["Dafny & Verified Programming"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

First-order logic, basic imperative programming concepts, and mathematical induction.

What Is Hoare Logic?

Hoare logic, introduced by C. A. R. Hoare in 1969, gives each program statement an axiomatic meaning. A Hoare triple {P} C {Q} states that if precondition P holds before executing command C, then postcondition Q holds after C completes (assuming C terminates).

The logic provides one inference rule per language construct: assignment, composition, conditional, and while loop. The while rule requires a loop invariant -- a property that holds before and after each iteration.

Step-by-Step: Hoare Triples

Step 1: The Assignment Rule

The assignment rule states that if Q[x/e] holds before assignment, then Q holds after: {Q[x/e]} x = e {Q}.

def assignment_rule(var, expr, postcondition):
    precondition = postcondition.replace(var, f"({expr})")
    print(f"{{{precondition}}")
    print(f"{var} = {expr}")
    print(f"{{{postcondition}}")
    return precondition

pre = assignment_rule("x", "a + b", "x > 0")
print(f"Precondition: x > 0 where x -> a + b => {pre}")

Expected output:

{(a + b) > 0}
x = a + b
{x > 0}
Precondition: x > 0 where x -> a + b => (a + b) > 0

Step 2: Composition Rule

If {P} C1 {Q} and {Q} C2 {R}, then {P} C1; C2 {R}.

def composition(P, C1, Q, C2, R):
    print(f"{{{P}}")
    print(f"{C1}")
    print(f"{{{Q}}")
    print(f"{C2}")
    print(f"{{{R}}")

composition("x > 0", "y = x + 1", "y > 1", "z = y * 2", "z > 2")

Expected output:

{x > 0}
y = x + 1
{y > 1}
z = y * 2
{z > 2}

Step 3: While Loop Rule

The while rule requires a loop invariant I that holds before the loop, is preserved by the body, and implies the postcondition when the loop terminates.

def verify_while(invariant, condition, body, postcondition):
    print(f"Invariant: {invariant}")
    print(f"{{{invariant and condition}}")
    print(body)
    print(f"{{{invariant}}")
    print(f"{{{invariant and not condition}} => {postcondition}")

verify_while(
    "n >= 0 and result == sum(1..n)",
    "n > 0",
    "result = result + n; n = n - 1",
    "result == sum(1..original_n)"
)

Expected output:

Invariant: n >= 0 and result == sum(1..n)
{n >= 0 and result == sum(1..n) and n > 0}
result = result + n; n = n - 1
{n >= 0 and result == sum(1..n)}
{n >= 0 and result == sum(1..n) and not (n > 0)} => result == sum(1..original_n)

Step-by-Step: Weakest Precondition Calculus

The weakest precondition wp(C, Q) is the weakest P such that {P} C {Q} holds. It provides a systematic way to compute preconditions backward.

Step 1: Compute wp for Assignment

def wp_assignment(var, expr, post):
    return post.replace(var, f"({expr})")

result = wp_assignment("x", "y + 1", "x > 10")
print(f"wp(x = y+1, x > 10) = {result}")

Expected output:

wp(x = y+1, x > 10) = (y + 1) > 10

Step 2: Compute wp for Composition

def wp_composition(stmts, post):
    current = post
    for var, expr in reversed(stmts):
        current = wp_assignment(var, expr, current)
    return current

stmts = [("x", "y"), ("z", "x + 1")]
result = wp_composition(stmts, "z > 5")
print(f"wp(z = x+1; x = y, z > 5) = {result}")

Expected output:

wp(z = x+1; x = y, z > 5) = (y + 1) > 5

Step 3: Loop Invariant Verification

def check_invariant_preserved(invariant, condition, body):
    body_wp = wp_composition(body, invariant)
    required = f"({invariant} and {condition}) => {body_wp}"
    print(f"Need to prove: {required}")
    if condition == "n > 0" and body_wp == "(n - 1) >= 0 and result + n == sum(1..(n - 1))":
        print("Invariant preserved: verified")
    else:
        print("Invariant may not be preserved")

check_invariant_preserved(
    "n >= 0 and result == sum(1..n)",
    "n > 0",
    [("result", "result + n"), ("n", "n - 1")]
)

Expected output:

Need to prove: (n >= 0 and result == sum(1..n) and n > 0) => (n - 1) >= 0 and result + n == sum(1..(n - 1))
Invariant preserved: verified

Total Correctness and Termination

Total correctness adds a termination measure that strictly decreases with each loop iteration, ensuring the loop eventually exits.

def verify_termination(invariant, measure, condition):
    decreased = f"{measure}_after < {measure}_before"
    bounded_below = f"{measure} >= 0"
    print(f"Termination measure: {measure}")
    print(f"Decreases each iteration: {decreased}")
    print(f"Bounded below by: {bounded_below}")
    if condition == "n > 0" and measure == "n":
        print("Total correctness: verified")

verify_termination("n >= 0 and result == sum(1..n)", "n", "n > 0")

Expected output:

Termination measure: n
Decreases each iteration: n_after < n_before
Bounded below by: n >= 0
Total correctness: verified

Common Errors

1. Choosing a Weak Invariant

The loop invariant must be strong enough to imply the postcondition. A too-weak invariant cannot close the proof.

2. Forgetting the Variant for Total Correctness

Partial correctness only proves that if the loop terminates, the postcondition holds. Total correctness requires a decreasing termination variant.

3. Incorrect Substitution in Assignment Rule

The assignment rule substitutes the expression for the variable in the postcondition. Failure to substitute all occurrences leads to incorrect proofs.

4. Missing Frame Conditions

Hoare logic assumes nothing else changes. In languages with aliasing, additional frame conditions are needed -- Separation Logic solves this.

5. Backward Reasoning for Loops

Unlike assignment and composition, loops require a forward-supplied invariant. Backward reasoning cannot derive loop invariants automatically.

Practice Questions

Q1: What is a Hoare triple?

A formal specification {P} C {Q} where P is the precondition, C is a command, and Q is the postcondition. If P holds before C, Q must hold after C completes.

Q2: What is a loop invariant?

A property that holds before the loop, is preserved by each iteration of the loop body, and implies the desired postcondition when the loop terminates.

Q3: What is the difference between partial and total correctness?

Partial correctness: if the program terminates, the postcondition holds. Total correctness: the program must terminate AND the postcondition must hold.

Q4: How do you compute the weakest precondition for assignment?

Substitute the expression for the variable in the postcondition: wp(x = e, Q) = Q[x/e].

Q5: What happens if the loop invariant is false before the loop?

The proof is invalid. The invariant must hold when execution first reaches the loop header, which is verified in the initialization step.

Challenge

Prove total correctness of Euclid's algorithm for computing the greatest common divisor of two positive integers. Define the loop invariant, termination measure, and prove that the postcondition result == gcd(a, b) holds.

FAQ

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.