Skip to content

Model Checker and Static Analyzer

Static verification audit (tool) — instantiates Specification-to-Execution Lowering

Verifies that a model or program satisfies stated properties and pre/post-conditions by analysing its reachable states, returning a counterexample when it doesn't — proof over a bounded domain, not evidence from sample runs.

A Model Checker and Static Analyzer establishes that a lowering satisfies stated properties not by running it on examples but by analyzing its space of possible behaviors. Given a model or program and a set of properties — invariants, pre/post-conditions, "this bad state is never reached" — it explores the reachable states exhaustively (or up to a bounded depth) and returns either a guarantee that the property holds across that space or a counterexample: a concrete trace that violates it. Its defining difference from every test-based sibling is the kind of evidence it produces. A test says "correct on the inputs we tried"; a model checker says "correct on all behaviors within the modeled domain" — a far stronger claim, but one that holds only inside the assumptions and bounds it was given, which is why stating that domain of validity is inseparable from the result.

Example

A team lowering a control law into embedded C must guarantee an array index into a sensor buffer can never go out of bounds, for inputs within stated ranges. Instead of testing sample inputs, they run a static analyzer and a bounded model checker over the routine: the analyzer tracks the possible range of each variable through the code, and the checker explores reachable states up to a bounded loop depth, discharging the obligation "index stays within [0, N)."

It finds a trace no hand-picked test had hit: when a sensor returns its maximum value and a mode flag is set, an intermediate computation overflows and the index wraps negative. Once the bug is fixed, the guarantee is stated with its scope attached: "no out-of-bounds access for inputs within the declared ranges, up to loop depth k." Outside that domain of validity, the checker stays silent — and honest about staying silent. The counterexample trace, not a pile of passing runs, is what makes the flaw undeniable.

How it works

  • Analyze the state space, don't sample it. Properties are checked against the model's reachable behaviors — exhaustively or to a bounded depth — rather than against representative inputs.
  • Discharge obligations, return counterexamples. Each property, invariant, or pre/post pair is a proof obligation; the tool either discharges it or produces a concrete violating trace, its most useful output.
  • Scope every guarantee. Results hold only under the stated assumptions, abstractions, and bounds; the domain of validity is part of the verdict, not a footnote.
  • Verify contracts, not just crashes. Beyond safety properties, it checks declared pre/post-conditions and invariants — the correctness contract of the lowered code.

Tuning parameters

  • Exhaustive vs. bounded — full state-space coverage versus checking to a fixed depth. Exhaustive proof is strongest but often infeasible; bounded checking scales but only guarantees up to its bound.
  • Abstraction level — how much the model simplifies the real system. Coarser abstractions make verification tractable but widen the gap between "the model is safe" and "the code is safe."
  • Property strength — how much is specified to verify, from "no crash" up to full functional correctness. More properties mean stronger guarantees but more specification effort and more false alarms to triage.
  • Soundness vs. completeness stance — whether the analyzer may report false positives (sound, no missed bugs) or false negatives (fewer false alarms, some bugs missed). This dial sets whether you trust a clean result or a clean conscience.
  • Domain-of-validity breadth — how wide the assumed input/environment envelope is. A narrow domain is easier to verify but guarantees less; widening it strengthens the claim at rising cost.

When it helps, and when it misleads

Its strength is delivering the strongest assurance any lowering can carry short of a full proof — a guarantee over all behaviors in the modeled domain, and, when a property fails, a counterexample worth more than a hundred passing tests because it shows the flaw. For safety- and security-critical lowerings, this is the difference between "we didn't find a bug" and "no bug of this class exists here."

Its two failures are famous. State-space explosion means the reachable space can grow beyond what any tool can explore, forcing abstraction or bounding — and both weaken the claim.[1] And the guarantee covers the model, not necessarily the running system: if the abstraction omits something real, or the code later drifts from the verified model, "verified" becomes false comfort. The misuse is quoting a bounded or abstracted result as if it were unconditional — "proven correct," full stop, with the domain of validity quietly dropped. The discipline is to state the assumptions and bounds with every guarantee, keep the verified model synchronized with the shipped code, and pair formal results with testing over the region the model abstracts away.

How it implements the components

Model Checker and Static Analyzer fills the components that carry a verified, domain-scoped guarantee:

  • domain_of_validity_statement — the assumptions, abstractions, and bounds under which the guarantee holds; inseparable from the verdict, because the claim is meaningless without them.
  • proof_and_test_obligation_set — the properties, invariants, and safety conditions it discharges (or refutes with a counterexample); the obligations verification is responsible for.
  • precondition_postcondition_pair — the declared pre/post-conditions of the lowered code, verified across the state space rather than merely tested at examples.

It produces no runnable artifact and no golden outputs — it consumes a model or program and returns a verdict — so the emitted code (executable_realization — a Compiler Intermediate-Representation Lowering Pipeline) and the recorded-behavior oracle (reference_model_or_oracle — a Regression Test Suite) belong to other siblings.

Notes

The guarantee is only as good as the fidelity between the verified model and the running system. When the model is abstracted or the code is later changed, a past "verified" can quietly stop applying — which is why formal verification is paired with a Differential Equivalence Test or Regression Test Suite over exactly the behaviors the model abstracts away.

References

[1] State-space explosion — the number of reachable states grows combinatorially with a system's variables and concurrency, so exhaustive model checking becomes intractable for large systems. Abstraction and bounded model checking are the standard responses, each trading some strength of guarantee for feasibility. ↩