Correct-by-Construction Design — Refinement and Event-B

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

Correct-by-Construction design builds software from a formal specification through stepwise refinement, ensuring each development step preserves correctness by mathematical construction.

Learning Path

flowchart LR
  A["TLA+"] --> B["Correct-by-Construction
Refinement & Event-B"]
  B --> C["Industrial Formal Verification"]
  B --> D["Theorem Proving"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Set theory, first-order logic, and basic understanding of Model Checking or Theorem Proving.

What Is Correct-by-Construction?

Correct-by-Construction (CbC) starts with a high-level formal specification of what the system should do. Through stepwise refinement, you add implementation details one step at a time, proving each refinement preserves the original specification.

At each level, you verify invariant preservation: every operation maintains the system invariants.

Step-by-Step: Event-B Model

Step 1: Define the Context

CONTEXT BankCtx
SETS ACCOUNT
CONSTANTS max_balance
AXIOMS
    max_balance : INTEGER
    max_balance > 0
END

Step 2: Define the Machine

MACHINE BankMachine
SEES BankCtx
VARIABLES balance
INVARIANTS
    balance : ACCOUNT -> INTEGER
    !a . a : ACCOUNT => balance(a) >= 0
    !a . a : ACCOUNT => balance(a) <= max_balance
EVENTS
    Initialisation
    begin
        balance := {a |-> 0 | a : ACCOUNT}
    end

    Deposit =
    any a, amount where
        a : ACCOUNT
        amount : INTEGER
        amount > 0
        balance(a) + amount <= max_balance
    then
        balance(a) := balance(a) + amount
    end
END

Step 3: Python Simulation

class BankAccount:
    def __init__(self, max_bal=10000):
        self.balances = {}
        self.max_balance = max_bal

    def create_account(self, account_id):
        self.balances[account_id] = 0
        assert self.invariant()

    def deposit(self, account_id, amount):
        # Precondition
        assert amount > 0
        assert self.balances[account_id] + amount <= self.max_balance
        # Operation
        self.balances[account_id] += amount
        # Postcondition + invariant
        assert self.invariant()

    def invariant(self):
        for b in self.balances.values():
            if b < 0 or b > self.max_balance:
                return False
        return True

bank = BankAccount()
bank.create_account("a1")
bank.deposit("a1", 500)
print(f"Invariant holds: {bank.invariant()}")
print(f"Balance: {bank.balances['a1']}")

Expected output:

Invariant holds: True
Balance: 500

Step-by-Step: Refinement

Step 1: Abstract Model

Start with a simple specification:

ABSTRACT
VARIABLES x
INVARIANT x : INTEGER & x >= 0
EVENTS
    Init: x := 0
    Inc: x := x + 1

Step 2: First Refinement

Add a bound:

REFINEMENT FirstRef
VARIABLES x, limit
INVARIANT limit : INTEGER & limit > 0 & x <= limit
EVENTS
    Init: x := 0 || limit := 100
    Inc: when x < limit then x := x + 1 end

Step 3: Second Refinement (Implementation)

class CounterRefined:
    def __init__(self):
        self.x = 0
        self.limit = 100

    def increment(self):
        # Guard: x < limit
        if self.x < self.limit:
            self.x += 1
            return True
        return False

    def check_invariant(self):
        return 0 <= self.x <= self.limit

c = CounterRefined()
for _ in range(150):
    result = c.increment()
    assert c.check_invariant()
print(f"Final x: {c.x}, reached limit: {c.x == c.limit}")

Expected output:

Final x: 100, reached limit: True

Common Errors

1. Refinement Not Preserving Invariants

Each refinement must preserve all invariants from previous levels. A new operation may violate an existing invariant if not carefully guarded.

2. Missing Guard Conditions

Operations must include guards that prevent execution in states where invariants would be violated. Missing guards lead to invariant breaches.

3. Over-Refinement

Adding too many details in one refinement step makes proof obligations difficult. Each refinement should add one or two details.

4. Gluing Invariant Weakness

The gluing invariant connecting abstract and concrete states must be strong enough to prove that concrete behavior matches abstract behavior.

5. Deadlocking Refinements

A refinement that introduces guards may prevent operations from being enabled. All abstract behaviors must have corresponding enabled concrete behaviors.

Practice Questions

Q1: What is stepwise refinement?

A development method starting from an abstract specification and adding implementation details through provably correct steps.

Q2: What is Event-B?

A formal method for system-level modeling and refinement, with tool support via the Rodin platform.

Q3: What is a gluing invariant?

An invariant relating abstract and concrete variables, ensuring that concrete states correspond to valid abstract states.

Q4: What proof obligations does refinement generate?

Invariant preservation, guard strengthening, Deadlock freedom, and simulation between abstract and concrete events.

Q5: How does Correct-by-Construction differ from post-hoc verification?

CbC proves correctness during development. Post-hoc verification proves correctness of already-written code, which is typically harder.

Challenge

Design a simple traffic light controller using Correct-by-Construction. Start with an abstract model: the light cycles between red, green, and yellow. Refine to include timing constraints (minimum red duration, minimum green duration). Prove each refinement step.

FAQ

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