Formal Methods Lab

№ 001

A field guide & workbench for specification-based testing

Formal methods,
for people who ship tests.

Write one temporal-logic sentence — G (request -> F response) — and it becomes your test oracle: checked exhaustively against a model, attacked by a fuzzer, replayable as a regression test, and served to your AI agents over MCP.

§ 01 · field guide

The concepts, said plainly.

Formal methods is not a rival to testing — it is testing, done with the safety rail of precision. Ten short chapters: what each idea is, why a tester should care, and where it shows up in the workbench below.

§ 1.1

Specification as the test oracle

Before you can test a system, you must decide what counts as a failure.

see also · Linear temporal logic · Model checking · Property-based testing & falsification

The oracle problem

A test needs two things: an input, and a way to tell pass from fail. The second one — the oracle — is where testing gets expensive: someone has to know the expected behaviour for every case, and that knowledge lives in tickets, heads, and tribal memory, where it rots.

A formal specification replaces all of that with one precise sentence. G (request -> F response) says: always, if a request happens, then eventually a response follows — for every possible execution, not just the three you thought to try. One line becomes an oracle for infinitely many tests.

From property to test verdict

Once the property is machine-checkable, the test loop inverts. You no longer assert on examples you wrote by hand; you generate executions and ask the specification whether each one passes. This lab does that three ways: exhaustively (model checking), randomly (property-based testing), and after the fact (runtime verification on logs).

  • G p — safety: p holds in every reachable state, nothing bad ever happens.
  • F p — liveness: p eventually happens, something good occurs.
  • p U q — precedence: p holds until q takes over, and q really does occur.
  • G (request -> F response) — the classic request/response contract.

§ 1.2

Kripke structures

The machine you *intend* to build, written down so a machine can read it.

see also · Model checking · Bounded model checking

States, labels, transitions

A Kripke structure is a directed graph with three decorations: a set of *atomic propositions (`ready`, `coin`, `error`…), a finite set of states each labelled with the propositions true there, and a set of initial states*. Transitions say which state may follow which.

That is deliberately less than real code says. No variables, no clocks, no byte order — only what matters for the property. Modelling is abstraction, and abstraction is the whole game: strip away everything irrelevant, keep exactly enough to state what correct means.

Nondeterminism is a feature

In this model, a state with two outgoing transitions does not choose between them — the environment does. Checking the structure means checking every resolution of those choices, which is precisely what makes the verdict strong: an input, a scheduler, a network adversary is covered before it exists.

Dead ends (states with no outgoing transitions) are treated as stuttering forever — the system has frozen. That single modelling decision is what lets liveness properties catch infinite hangs.

§ 1.3

Linear temporal logic

A tiny language for talking about time, and the backbone of this lab.

see also · Specification as the test oracle · Runtime verification · Model checking

The grammar

LTL adds four temporal operators on top of ordinary propositional logic. Formulas are evaluated *along a run* of the system, one state at a time, from the first state onward.

  • X p — next: p holds in the state that follows.
  • F p — finally: p holds somewhere later on (<>).
  • G p — globally: p holds at every step ([]).
  • p U q — until: p holds until q occurs, which it eventually does.
  • Weak until p W q drops the eventual obligation; q R p is its dual (release).

Two semantics, one grammar

Over an *infinite* run (the textbook reading), G and F quantify over an endless future. Model checking uses this: a counterexample is a run that loops forever while breaking the property.

Over a *finite trace — a test case, a log — the same formula means something subtly different: `F p` only promises `p` within the observed trace*, and X p is false at the last state. That reading is called LTLf and it is the right one for runtime verification and for checking concrete test executions.

This lab is bilingual on purpose: the playground checks models with infinite semantics, the fuzzer and the check_ltl MCP tool check finite traces. When you compare results across them, remember which language you are speaking.

§ 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

Every behaviour at once

Model checking takes a finite structure and a temporal property, then answers: does every possible run of the structure satisfy the property? Not a sample — all of them, including the runs that need a specific interleaving, a retry at the worst moment, or a race you never thought to write a test for.

The superpower for testing people: the answer "no" arrives with a *counterexample — a concrete run, state by state, that breaks the property. That counterexample is* a failing test case, ready to be replayed as a regression test.

What it costs

The price is the *state explosion problem: the number of runs grows exponentially with states and nondeterminism, so full model checking is PSPACE-complete in the model size. In practice you check abstractions* of real systems — and this lab's checker enumerates lassos (simple prefix + loop) explicitly, which is perfect for teaching and for models of a few dozen states.

When the model is too big, you bound the search — which is exactly where testing takes over. See bounded model checking and property-based testing.

§ 1.5

Bounded model checking

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

see also · Model checking · Specification-based test generation

Search, but only so deep

Bounded model checking (BMC) asks a weaker question on purpose: does any run of length ≤ k violate the property? Fix a depth bound, translate runs of that depth into a SAT/SMT query, and let a solver look for a violation. It scales far past explicit enumeration, because the solver only hunts for the bad runs, never enumerates the good ones.

The verdict has a precise meaning that testers already live with: *no counterexample within depth k*. That is exactly what a test campaign with 100% coverage of the first k steps can claim — and no more.

Sound, but never complete

BMC can never return a proof by increasing k alone (a deeper counterexample may hide below the bound), so the result is always: violation found, or unknown. The honest move — in academic tools and in this lab — is to say "unknown" out loud rather than dress it up as a pass.

Unbounded depth is a special case: when the structure is finite, every violation is witnessed by a run shaped like a *lasso* — a simple prefix that enters a loop. This lab's checker enumerates lassos explicitly; at depth = number of states its "holds" verdict is genuinely exhaustive, and below that depth it labels itself incomplete.

§ 1.6

Property-based testing & falsification

Let the machine try to break your spec. Then let it explain itself.

see also · Runtime verification · Specification as the test oracle · Coverage as a negative metric

Random executions, one property

Property-based testing replaces hand-written cases with a generator plus a predicate. The generator produces inputs at random; the predicate says what must hold for every one of them. Run the pair a few thousand times and you have tested cases no human would have typed — the empty trace, the all-at-once trace, the pathological interleaving.

In this lab the generated artefacts are *traces of atomic propositions*, and the predicate is an LTL formula evaluated under finite-trace semantics. The fuzzer invents runs; the formula votes; a violation is a bug-shaped counterexample.

Shrinking: counterexamples that explain

A raw failing case is usually noise — 12 random steps when 2 would do. *Shrinking is a delta-debugging loop: repeatedly try deleting a step, or an atom from a step, and keep the deletion whenever the smaller trace still* violates. What survives is a minimal, readable reproduction.

Passing a property-based campaign proves nothing — you sampled the input space and stayed lucky. But falsification has a testing superpower that beats example-based tests on both sides: it finds failures you never imagined, and it shrinks them until they teach you something.

  • Seeds make runs reproducible: same seed, same failures — record it in your bug report.
  • Coverage-guided fuzzers (the industrial version) bend generation toward unexplored paths.
  • A property that survives 10⁵ random traces is evidence, not proof. Evidence is still useful.

§ 1.7

Coverage as a negative metric

Coverage tells you what you didn't test. It can't tell you what you did.

see also · Specification-based test generation · Model checking

Measured honesty

Coverage answers one narrow question with perfect precision: which parts of the model did my tests never reach? In this lab the parts are *states and transitions* of the Kripke structure; run your traces and the report lists every one you missed. If a transition is uncovered, no test ever exercised it — that is a fact, not a judgement.

The trap is reading coverage backwards. 100% transition coverage means every edge fired at least once — not that every behaviour was tested (behaviours are infinite), nor that the property was checked against the edge. Coverage is a checklist of remaining work, never a certificate of correctness.

Spec coverage vs code coverage

In model-based testing there is a second axis: requirement coverage — does every clause of the specification have at least one test that would fail if the clause were broken? One requirement, one traceability link. If a property can be violated by runs your model can produce, make sure a test actually drives the model there — or let the model checker drive it for you (its counterexamples are pre-loaded failing tests).

§ 1.8

Runtime verification

Check the property against what actually ran — in CI, in production.

see also · Linear temporal logic · Property-based testing & falsification

From logs to verdicts

Runtime verification compiles an LTL formula into a *monitor: a small state machine that consumes a running system's events (a test, a request log, a CI run) and flags a violation the moment one becomes inevitable. It is the finite-trace dialect: `F response` promises the response within the log*, X speaks about the next observed event.

Where model checking reasons about all possible runs, runtime verification reasons about the one run that happened. Cheap, no model needed, and directly deployable: end-to-end tests become executable statements of the spec, and intermittent flaky failures get a formal sentence to be judged by, not a screenshot.

A CI-native oracle

The sweet spot for testers: write the property once as G (request -> F response), then reuse it everywhere — as a monitor in CI, as the fuzzer's predicate, and as the model checker's target. One spec, three execution modes, no drift between what you test and what you meant.

§ 1.9

Specification-based test generation

The spec already knows which tests you need. Let it write them.

see also · Model checking · Coverage as a negative metric

Tests from a model

Given a Kripke structure, a test case is just a finite path through it — a story the system can live. Specification-based test generation turns the model into a test oracle *and* a test suite: enumerate runs, keep the ones that reach interesting states or break interesting properties, and export them as concrete, replayable cases.

Model checking contributes the best cases for free: every counterexample is a test that provably fails against the intended behaviour. Coverage analysis contributes the rest — it tells you exactly which runs you still owe a test.

Why this beats example-based testing

Hand-written tests encode yesterday's understanding: they check the bugs you already made. Generated tests encode the specification: they check the obligations you have standing, whether or not you ever thought about them. The catch is honest bookkeeping — the tests are only as good as the model, so the model must stay small, reviewed, and in the repo next to the code.

§ 1.10

Beyond checking: proving

SAT solvers, SMT, and proof assistants — when exhaustive still isn't enough.

see also · Bounded model checking · Model checking

The wider toolbox

Model checking finite structures is the friendliest corner of formal methods. When systems grow unbounded state (data structures, counters, time), the toolbox extends: *SAT/SMT solvers power bounded checking over infinite data domains; theorem provers (Coq, Lean, Isabelle, Agda) prove all instances at once, with humans steering; abstraction & refinement* prove properties of infinite systems via conservative over-approximations.

For testing teams the practical bridge is: keep the model, and let a solver search it. Counterexamples from a solver-level search scale to models far beyond explicit enumeration — same workflow, sharper tools.

The honest spectrum

Every verification technique lands somewhere on a spectrum of confidence vs cost: example tests (cheap, weak), random falsification (cheap, broader), bounded checking (medium, exhaustive within a bound), full model checking (exhaustive, needs abstraction), proof assistants (total, expensive). The craft of specification-based testing is picking the strongest tool you can still afford — and labelling the answer with what it actually proves.

§ 02 · workbench

Now break something.

Four instruments, one engine, running live in your browser — the same code that answers /api/mcp. Verdicts are labelled with exactly what they prove: holds, violated, or incomplete. Never a dressed-up maybe.

A

Trace checker

A property and a run, judged position by position. The truth table is the whole proof: every subformula, every step, nothing hidden.

satisfies

finite-trace (LTLf) semantics · 3 states

the run · edit me
0
1
2

Click a chip to flip an atom in that state. Every edit re-evaluates the property immediately — no run button, the table is the test.

truth table · every subformula, every position
posrequestresponseF responserequest -> F responseG (request -> F response)
0TFTTT
1TFTTT
2FTTTT

Read the last column for the verdict at each position; the columns to its left explain it. This is the same table check_ltl returns over MCP.

B

Model checker

Every behaviour of a Kripke structure at once — and when one breaks the property, you get the run that broke it: a ready-made failing test.

The checker enumerates every lasso — a simple path that enters a loop — and evaluates the property on each, infinite semantics. Dead ends are read as “stuttering forever”, which is how liveness catches hangs.

Empty depth = check every behaviour of the model. A bound is bounded model checking: violations found are real, and “incomplete” is reported honestly.

holds

3 states · depth 3 · 1 lassos checked · 0.2 ms

Holds, exhaustively. Every possible run of the model was checked (depth = 3 = all 3 states, no truncation). The property is proven for this model — which is exactly as strong as the model is faithful.

C

Fuzzer

Random executions against your spec, shrunk to the smallest reproduction. Absence of failure is reported as evidence, never as proof.

D

Coverage meter

What did your tests never touch? Coverage is the negative metric: it proves gaps, not correctness. The honest checklist at the bottom of every campaign.

Coverage answers one question with total honesty: which states and transitions did no test ever reach? It cannot certify the ones that were reached — that is what the checker above is for.

§ 03 · for agents

The same lab, over MCP.

Everything above is callable by your AI agents at a single endpoint — stateless JSON-RPC 2.0, no sessions, no ceremony. Point an MCP client at /api/mcp and the field guide itself becomes a tool.

endpoint

POST /api/mcp

JSON-RPC 2.0 over Streamable HTTP, stateless: every request stands alone, no session handshake required. The five tools are the same engine the workbench above runs — a verdict you read here and a verdict your agent reads over MCP can never disagree.

  • —protocol 2025-06-18; notifications get 202 Accepted
  • —batches (JSON arrays) are answered with arrays
  • —results carry structuredContent for agents and pretty JSON for humans
curl -s https://formalmethods.dev/api/mcp \
  -H 'content-type: application/json' \
  -d '{"jsonrpc":"2.0","id":1,"method":"initialize"}'

# → {"jsonrpc":"2.0","id":1,"result":{
#     "protocolVersion":"2025-06-18",
#     "capabilities":{"tools":{"listChanged":false}},
#     "serverInfo":{"name":"formalmethods-mcp", ...}}}
curl -s https://formalmethods.dev/api/mcp \
  -H 'content-type: application/json' \
  -d '{"jsonrpc":"2.0","id":2,"method":"tools/call",
       "params":{"name":"check_ltl",
                 "arguments":{"formula":"G (request -> F response)",
                              "trace":[["request"],["timeout"],["timeout"]]}}}'

# → result.structuredContent.satisfies === false  (a failing test, machine-read)

the toolbox · five tools

method: tools/list

  1. a. check_ltl

    Check an LTL property on a finite trace

    args: formula, trace

    Evaluate an LTL formula over a finite trace (a test case / log) under finite-trace (LTLf) semantics. Returns the verdict plus a truth table of every subformula at every position, which makes counterexamples easy to read. Supported syntax: atoms (identifiers), true, false, !, &&, ||, ->, <->, X (next), G (globally), F (finally), U (until), W (weak until), R (release).

  2. b. model_check

    Model check an LTL property on a Kripke structure

    args: formula, model

    Check an LTL property against a Kripke structure (states + transitions + labels) under infinite-run semantics. Enumerates every lasso (simple prefix + cycle) up to a depth bound. Returns verdict 'violated' (with counterexample lassos), 'holds' (exhaustive: full depth reached without truncation), or 'incomplete' (depth bound or path budget was reached). Dead-end states are treated as stuttering forever.

  3. c. falsify_property

    Falsify an LTL property with random traces

    args: formula, atoms

    Property-based testing for LTL: generate random finite traces over the given atoms, check the property under LTLf semantics, and when a violation is found, shrink it (drop positions, then atoms) to a minimal readable counterexample. Deterministic given a seed.

  4. d. analyze_coverage

    Measure state/transition coverage of traces

    args: model, traces

    Given a Kripke structure and a set of test traces (sequences of state ids), report state and transition coverage: what was reached, what is missing, and the percentages. A negative metric: it proves absence of testing, never presence of correctness.

  5. e. explain_concept

    Explain a formal-methods concept

    args: —

    Explain formal-methods-for-testing concepts (specification, LTL, Kripke structures, model checking, bounded model checking, property-based testing, coverage, runtime verification, test generation, proving). Call with no concept for a one-line index of available topics.

Honesty is a protocol feature. No tool ever claims more than it checked: bounded results say incomplete, random campaigns say not falsified, and only an exhaustive enumeration is allowed to say holds. Your agents will quote these verbatim — they have been designed so they can.