formalmethods.dev

§ 1.4

Model checking

Don't pick test cases. Check all of them.

see also · Bounded model checking · Kripke structures · Coverage as a negative metric

prefixcycle ↺repeats foreverstuvw
a simple path that closes into a loop — the shape every LTL counterexample takes

Every behaviour at once

Model checking asks: does every possible run of the structure satisfy the property? Not a sample — all of them, including the interleaving you never thought to test.

The answer "no" arrives with a counterexample: a concrete run that breaks the property. That counterexample is a failing test, ready for the regression suite.

What it costs

The price is the state explosion: runs grow exponentially with states and nondeterminism, and full checking is PSPACE-complete. In practice you check small abstractions — this lab enumerates lassos (simple prefix + loop) explicitly, right for teaching and models of a few dozen states.

Too big? Bound the search — that is bounded model checking, and where testing takes over.

try it · enumerate every behaviour — lab B →