Software Testing

Expert path · lesson 19 of 21

ExpertTest design5 min readPublished November 12, 2026

Formal methods and model checking for testers

Testing samples behaviour; formal methods reason about all of it, within a model. Here's what model checking, specification languages like TLA+ and proof-based verification can do, what they can't, and why testers are well placed to use them.

On this page

Key takeaways

  • Formal methods use precise, mathematical specifications. Model checkers explore every reachable state of a model within given bounds; provers establish properties for all inputs.
  • They excel where testing struggles: concurrency, distributed protocols, rare interleavings and security-critical cores. Counterexamples come as exact step-by-step traces.
  • They verify against a specification and assumptions, not reality. Testing remains essential, for spec errors, unverified parts, the environment and the gap between model and code.

Where this picks up

You've seen that testing is a sampling problem and that some failures in distributed systems need rare interleavings. Formal methods attack exactly that weakness: instead of sampling, they reason about all behaviours of a precisely described system.

The spectrum

LevelExamplesEffortWhat you get
LightweightStrong type systems, contracts, static analysersLowWhole classes of errors ruled out automatically
Specification + model checkingTLA+ with the TLC model checker, Alloy, SPINMediumExhaustive exploration of a design, within bounds; counterexample traces
Code-level model checking and symbolic executionBounded model checkers such as CBMC; symbolic execution tools such as KLEEMedium–highPaths through real code explored systematically; bugs with concrete inputs
ProofInteractive provers such as Isabelle and Coq/Rocq; verified systems like the seL4 microkernel and the CompCert C compilerHighMathematical guarantees for all inputs, relative to the specification

Model checking in a nutshell

You describe a system as states and transitions, in a specification language, along with properties:

  • Safety properties: something bad never happens. "Two nodes are never both leader."
  • Liveness properties: something good eventually happens. "Every request is eventually answered."

The model checker explores all reachable states, within configured bounds such as 3 nodes, 2 failures and 4 messages in flight, and either confirms the properties hold in all of them or produces a counterexample: the exact sequence of steps that leads to a violation.

A tiny TLA+ fragment for a bank transfer system might state:

TotalMoney  == balance["A"] + balance["B"]
Invariant   == TotalMoney = 100 /\ \A acc \in Accounts : balance[acc] >= 0

TLC then checks every interleaving of concurrent transfers, including failures, against that invariant.

Real-world example · Amazon Web Services, 2015A 35-step bug found before it reached customers

In "How Amazon Web Services Uses Formal Methods" (Communications of the ACM, 2015), Chris Newcombe and colleagues described how AWS engineers had used the specification language TLA+ on complex distributed systems since 2011, including parts of S3, DynamoDB and EBS.

For DynamoDB, the model checker found a subtle bug that could lose data if a particular sequence of failures and recovery steps interleaved with other processing. The shortest trace that showed it had 35 high-level steps. The design had already been through extensive testing and careful review, which hadn't revealed it.

The authors reported that formal specification also improved understanding of the designs, and gave engineers confidence to make aggressive optimisations.

Lesson: for distributed designs, some bugs need long, specific sequences of events. Exhaustive exploration of a model finds them; sampling them by testing is very unlikely.

What "verified" does and doesn't mean

Formal guarantees are always relative:

  • To the specification: if the specification misses a requirement, or states the wrong one, the proof is of the wrong thing.
  • To the bounds: model checking with 3 nodes doesn't prove 5 nodes are safe, though most protocol bugs show up at small sizes.
  • To the model–code gap: a verified design can be implemented incorrectly.
  • To the assumptions: about hardware, compilers, operating systems and inputs.

Where testers fit

You don't need to be a mathematician to benefit:

  1. Write properties. Testers already think in invariants and "what must never happen". These are exactly what specifications need.
  2. Review specifications like requirements: ambiguous, missing or wrong properties are the main risk.
  3. Turn counterexamples into tests. A model-checker trace is a precise, reproducible scenario; replay it against the real system.
  4. Test the gap. Use model-based testing or conformance tests to check the implementation matches the verified design.
  5. Start lightweight. Stronger types, contracts and static analysis give formal-style guarantees with little effort.

When it's worth it

  • Yes: consensus and replication protocols, payment and ledger logic, concurrency primitives, security-critical parsers, safety-critical control, anything where a rare bug is catastrophic.
  • Probably not: UI flows, simple CRUD, fast-changing prototypes. Testing and good design give better value there.

Do

Model-check the design of a new replication or locking protocol before implementing it, then replay every counterexample as a regression test against the code.

Don't

Treat "formally verified" as "no testing needed". Specifications, bounds, unverified components and the environment still need testing.

Check yourself

A team model-checked their leader-election design with 3 nodes and found no violations. A manager concludes 'leader election is proven correct'. What would you point out?

Show answer

The result holds for the model and within its bounds: 3 nodes, and the failures and timings modelled. It doesn't cover larger clusters, behaviours the specification left out, or implementation differences from the design. Suggest checking larger bounds where feasible, reviewing the specification's assumptions and testing the implementation's conformance, with fault injection and the counterexample scenarios.