Key takeaways
- Real systems need extended state machines (variables, guards), hierarchical and parallel states and time. Flat diagrams either explode in size or hide the important behaviour.
- Coverage criteria form a ladder: all states → all transitions → transition pairs (1-switch) and longer sequences → sneak paths (invalid events in every state) → conformance methods such as the W-method that also detect wrong target states.
- The most dangerous transitions are often in error, recovery and restart paths, with events arriving at awkward moments. Test them deliberately.
Where this picks up
State transition testing covers states, events, state tables and the valid/invalid distinction. This article is about systems where that simple model breaks down: protocols, devices, distributed workflows and anything that must recover from failure.
Richer models
Extended state machines
Add variables and guards: "Locked if failedAttempts ≥ 3", "Shipped only if all items are packed". Now the state isn't just the box you're in; it's the box plus the variables. Test guards with boundary values (2, 3 and 4 failed attempts), and test the variable updates on each transition.
Hierarchical and parallel states (statecharts)
David Harel's statecharts (1987) let a state contain sub-states, and let independent regions run in parallel: a media player can be Playing / Paused while, in parallel, Online / Offline. Hierarchy keeps models small. But it introduces new questions:
- Which sub-state do you return to after leaving a parent state? Statecharts use history states for this. Test both "first entry" and "re-entry".
- When an event is handled by both a sub-state and its parent, which wins?
- Can events in one parallel region break invariants in the other?
Time
Timeouts, retries and scheduled transitions ("expire after 15 minutes") are transitions too. Test them at, just before and just after the timeout, using controllable clocks in tests rather than real waiting.
A ladder of coverage criteria
| Criterion | Requires | Typically finds |
|---|---|---|
| All states | Visit every state | Unreachable or crashing states |
| All transitions (0-switch) | Fire every valid transition | Missing or wrong single transitions |
| Transition pairs (1-switch) and N-switch | Every sequence of 2 (or N+1) consecutive transitions | Faults depending on history: "pay, cancel, pay again" |
| Sneak paths / all events in all states | Every event attempted in every state | Missing guards; actions that should be refused |
| Round-trip paths | Every path from a state back to itself or to a final state | Faults in loops and cycles |
| Conformance methods (e.g., W-method) | Transition coverage plus sequences that identify the resulting state | Transitions that go to the wrong state while outputs look right |
Why identifying states matters
Many state faults don't produce a visible wrong output immediately. The system simply ends up in the wrong state, and misbehaves later. Conformance-testing methods from protocol engineering, such as Tsun Chow's W-method (1978), add distinguishing sequences after each transition: short event sequences whose outputs differ depending on the state, proving the system arrived where it should.
In practical terms: after each transition, check the state, through the API, a query or a short probe sequence, not just the output of the transition itself.
State explosion and how to manage it
A system with 10 independent two-state components has 1,024 combined states. Techniques that keep it manageable:
- Model per concern (order lifecycle, payment state, shipment state) and test their interactions separately.
- Abstract variables into partitions (balance: negative / zero / positive).
- Use generators: model-based and stateful property-based tests explore long random paths.
- Prioritise by risk: full sneak-path coverage on money and safety states, transition coverage elsewhere.
Error, recovery and restart states
Systems spend little time in recovery, and tests spend even less. But recovery is where:
- events arrive while the system is half-restarted;
- persisted state on disk disagrees with in-memory state;
- neighbours react to the recovering component's messages.
On 15 January 1990, one of AT&T's 4ESS long-distance switches in New York had a minor hardware problem and went through its normal fault-recovery routine. When it came back, it sent messages to neighbouring switches.
A software change installed in all of these switches in December contained a flaw. When a switch received such messages at a particular moment in its own processing, it would fault and enter recovery too, and then send the same kind of messages to its neighbours. The failure cascaded across the network.
For about nine hours, much of AT&T's long-distance network was severely disrupted, and tens of millions of calls couldn't be completed. Engineers found the fault in the recent update and corrected it.
Lesson: the faulty behaviour lived in a recovery path, triggered by an event arriving in a specific state and timing. Transition coverage of normal operation wouldn't find it. Testing events-during-recovery, sequences and timing would.
Testing recovery paths deliberately
- Model the error states explicitly: Recovering, Degraded, ReadOnly, Restarting. Don't leave them as "exceptions".
- Inject events in every error state: new requests, duplicate messages, messages from neighbours, a second failure.
- Restart at every state, including mid-transition, and check persisted vs in-memory state afterwards.
- Control time to hit timeouts and retries exactly.
- Test interactions between instances: what happens to peers while one recovers?
Do
After each transition in a test, assert the resulting state through an independent check, not just the response of the action that caused it.
Don't
Stop at "every transition fired once on the happy path". It misses history-dependent, timing-dependent and recovery-path faults, the expensive ones.
Check yourself
A subscription system has states Trial, Active, PastDue and Cancelled. Payment webhooks can arrive late or twice. Which advanced state tests would you add?
Show answer
For example: sneak paths, such as a "payment succeeded" event in Cancelled or a second identical event in Active; 1-switch sequences, such as PastDue → Active → PastDue in quick succession; late events, such as a payment for an old invoice arriving after cancellation; timing, such as a retry at the exact grace-period boundary; and after each step, an independent check of the resulting state and billing records.
