formalmethods.dev

§ 1.5

Bounded model checking

Exhaustive within a budget — the honest middle between proving and testing.

see also · Model checking · Specification-based test generation

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

Search, but only so deep

BMC asks a weaker question on purpose: does any run of length ≤ k violate the property? Translate bounded runs into a SAT/SMT query and let a solver hunt for the bad ones only — that scales far past explicit enumeration.

The verdict means exactly what testers already live with: no counterexample within depth k — what a campaign covering the first k steps can claim, and no more.

Sound, never complete

Raising k alone can never yield a proof — a deeper counterexample may hide below the bound. So the answer is always: violation found, or unknown. Honest tools say unknown out loud.

Special case: a finite structure means every violation is a lasso. At depth = number of states, this lab's holds is genuinely exhaustive; below that, it labels itself incomplete.

try it · bound the depth — lab B →