Skip to content

Property-Based State-Sequence Testing

Automated testing method — instantiates Conjunctive Path Assurance

Generates thousands of random operation sequences, checks a safety invariant after every step, and shrinks any violation to the minimal history that breaks it.

Hand-written tests only cover the sequences someone thought of. Property-Based State-Sequence Testing covers the ones nobody did. Instead of fixed cases, it generates random but valid sequences of operations against the system, asserts a safety invariant that must hold throughout, and — when a sequence violates it — automatically shrinks the failing run to a minimal reproducer. Its defining strength is finding order-dependent conjunctions: the bad interleaving in which each operation is individually fine but their particular ordering completes a route to the hazard. Where combinatorial testing covers static combinations of values, this method explores histories — and where model checking proves absence exhaustively, this samples enormously and cheaply, trading proof for reach into real, running systems.

Example

A distributed payments ledger must satisfy a hard invariant: no account ever goes negative, and total money is conserved. The tester generates random sequences of transfer, refund, hold, and release across accounts under simulated concurrency, running tens of thousands of histories. A rare interleaving trips it — a retry landing between a hold and its release while a concurrent refund posts, double-counting a credit and breaking conservation. The raw failing sequence is 400 operations long; the shrinker reduces it to a three-operation minimal reproducer that still violates the invariant. That tiny, replayable history is the payoff — a precise recipe for the order-dependent conjunction, small enough to debug in minutes.

How it works

Define a generator that emits only valid operation sequences — respecting each operation's precondition so the histories are realizable — and an invariant the system must never violate. Run many random sequences, checking the invariant after each step. On a violation, shrink: repeatedly remove or simplify operations while the failure persists, converging on the smallest history that still breaks the property. What distinguishes it from its siblings is this pairing of generation from a specification with automatic minimization: it reaches interleavings a human would never enumerate, then hands back the irreducible core of the one that failed.

Tuning parameters

  • Generator distribution — how sequences are weighted; biasing toward rare or suspicious operations finds order-dependent conjunctions faster than uniform generation.
  • Sequence length — longer histories reach conjunctions that need more setup, but cost time and complicate shrinking.
  • Invariant strength — how much the property asserts; a stronger invariant catches subtler violations but risks false alarms on benign intermediate states.
  • Shrinking strategy — how aggressively failures are minimized; good shrinking is what turns a 400-step trace into an actionable three-step one.
  • Seed and reproducibility — recording the random seed so a rare failure can be replayed exactly; without it, a flaky violation is lost the moment it scrolls past.

When it helps, and when it misleads

Its strength is discovering the order-dependent conjunction no one thought to test and returning a minimal, replayable reproducer — at a cost that scales to real systems where exhaustive verification cannot reach.[1]

Its honest limit is that sampling cannot prove a conjunction impossible: not finding a violation is not the same as its absence, so a green run is evidence, never a certificate. And it is only as sharp as its invariant and generator — a weak invariant lets a broken system pass, and a generator that can't produce the dangerous operation will never trigger the fault. The classic misuse is treating a passing run as proof of safety. The discipline is to strengthen the invariant to the actual hazard, bias the generator toward the suspicious, and reach for Model Checking and Reachability Analysis where a real proof of absence is required.

How it implements the components

  • edge_activation_predicate — the generator must respect each operation's precondition — the predicate under which that transition is enabled — to emit valid sequences; the method encodes those predicates as generation guards.
  • model_evidence_and_version_trace — every shrunk counterexample, kept with its seed, is a reproducible evidence record; retained as a regression corpus, it is re-run against each later version of the model to prove the conjunction stays fixed.

It does not guarantee coverage of every combination — that promise is t-Wise Combinatorial Interaction Testing — nor prove the absence of any route, which is Model Checking and Reachability Analysis.

Notes

Property-based testing and model checking are natural partners on the same hazard: this method finds violations cheaply and at scale but can never prove there are none; model checking proves absence but pays dearly for it and only over a model. The productive order is usually to shake out bugs with property-based testing first, then certify the cleaned-up design with model checking where the stakes demand a proof.

References

[1] Property-based testing originated with QuickCheck, which introduced both random generation from a specification and shrinking — automatically reducing a failing case to a minimal counterexample. Shrinking is what makes a rare, tangled failure debuggable rather than merely observed. ↩