Protocol State Machines and Replay

Keyboard shortcuts

×

?

Open this guide

Alt + B

Show or hide the lesson list

Alt + O

Show or fold the lesson outline

Alt + N

Open or close notes

Alt + H

Toggle semantic colours

Alt + D

Toggle page brightness

Alt + C

Toggle code brightness

← →

Move through a focused code trace

Home End

First or final step in a focused trace

Escape

Close this guide or an open panel

Reader shortcuts pause while you type in a text field.

Cheatsheet for Lesson 9.5Key ideas, reference and questions

A one-page summary of “Protocol State Machines and Replay” you can keep beside your notes. Plain Markdown.

Lesson 9.5 — Protocol State Machines and Replay: cheatsheet

• Remember: Valid bytes can still request a transition that makes no sense in the current session.
• Also useful: Think of the log as receipts and the session state as the current balance. Replay rebuilds the balance from those receipts.

Key terms

• Goodbye: A Greeting with any version other than 1 is refused by its own arm with UnsupportedVersion, and Goodbye is accepted in every state, including Closed itself.
• incoming: The modular test asks a different question — how far forward is incoming from current, counting the wrap?

Formulas and patterns

• Disconnected -> Connected -> Greeted -> InLobby -> InMatch -> Closed

Review

• Q: A chat frame parses correctly but arrives before the protocol greeting. What should the session parser do? A: Reject it as an illegal transition for the current state
• Q: Why keep a raw capture log unchanged and rebuild the session state from it by replay? A: A fixed rule can replay the same frames, so changes in its behavior show up

Download cheatsheet (.md)

Download cheatsheet (.md)

A packet parser is only the first layer

Parsing one message tells you what its bytes mean. A protocol also defines when that message is legal.

TL;DR: Valid bytes can still request a transition that makes no sense in the current session.

A local Wesnoth test client might move through:

Disconnected -> Connected -> Greeted -> InLobby -> InMatch -> Closed

A chat message before the greeting may be invalid even when its length and UTF-8 text parse perfectly. That makes protocol reversing a state-machine problem as well as a byte-parsing problem.

Replay processes the saved frames in order. A record changes the modeled session only after both its bytes and its transition have passed validation:

If any stage fails, the record and old state remain available for diagnosis; the replay never needs to invent a replacement state.

A message log and a session state are different things

The capture is an ordered log of the frames that crossed the connection. The session state is a model produced by applying their messages in order:

initial state + message 1 + message 2 + ... -> current modeled state

For a five-frame capture of one short session, starting from Connected:

frame 0Greeting v1

frame 1LobbyJoined

frame 2Chat

frame 3MatchStarted

frame 4Goodbye

→ Greeted

→ InLobby

stays InLobby

→ InMatch

→ Closed

The boxes are the log; the labels under them are the state after each frame is applied. The log never stores a state, so a corrected rule can rebuild every state from the same five frames.

Keep the raw log immutable and rebuild the model from it. If a parser or transition rule changes, you can replay the same log and see exactly which frame now produces a different result. Editing the stored “current state” by hand loses that history.

Alternative: Think of the log as receipts and the session state as the current balance. Replay rebuilds the balance from those receipts.

Not every message is an event that happened exactly once: a snapshot can repeat a whole state, and a retransmitted request may appear twice. Store direction, sequence identifiers, and timing with each frame; without them, duplicate bytes cannot be told apart from duplicate actions. The real-time section below defines those message kinds and identifiers.

Model states and messages separately

Receiving a well-formed Chat message is different from being ready to accept it. A connection begins in Connected, reaches a lobby only after greeting and room messages, and can then accept chat. These enums keep the connection state and the parsed message as separate facts:

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum SessionState {
    Connected,
    Greeted,
    InLobby,
    InMatch,
    Closed,
}

#[derive(Clone, Debug, Eq, PartialEq)]
enum Message {
    Greeting { version: u16 },
    LobbyJoined { room: String },
    MatchStarted { scenario: String },
    Chat { text: String },
    Goodbye,
}

#[derive(Debug)]
enum ProtocolError {
    IllegalTransition { state: SessionState, message: &'static str },
    UnsupportedVersion(u16),
    EmptyName,
}

The parser creates Message values. The session machine decides whether each value makes sense now.

A valid Chat arrives while ConnectedThe bytes parse into a Chat, but this state only accepts a greeting, so the gate refuses it and the state stays Connected.

ParserSession state

1. 1

   Data Chat { text: "hello" }

   Step 1: Parser to Session state

   Parsing already succeeded: the bytes are a well-formed Chat. The parser says what the message is, not whether it is allowed now.

2. 2

   Alone (Connected, Chat): no accepting arm

   Step 2: Session state (alone)

   The session machine pairs the current state with the message. Nothing in the match lets a Chat through before the lobby is reached.

3. 3

   Control Err(IllegalTransition)

   Step 3: Session state to Parser

   The caller gets an error naming the state and the message. The session is still Connected and nothing was delivered.

The bytes parse into a Chat, but this state only accepts a greeting, so the gate refuses it and the state stays Connected.

The same Chat arrives while InLobbyIdentical bytes, identical parsed value. The current state is the only difference, and this state accepts a Chat without moving.

ParserSession state

1. 1

   Data Chat { text: "hello" }

   Step 1: Parser to Session state

   The same parsed message as before. Nothing about the bytes changed.

2. 2

   Alone (InLobby, Chat): accepted

   Step 2: Session state (alone)

   This state has an arm for a Chat, so the pairing is legal. The message is allowed because of where the session is.

3. 3

   Reply Ok(()) · state stays InLobby

   Step 3: Session state to Parser

   A chat line does not move the session anywhere. It stays InLobby until a message that triggers a transition arrives.

Identical bytes, identical parsed value. The current state is the only difference, and this state accepts a Chat without moving.

Make transitions explicit

Now pair the current state with one parsed message. A version-1 greeting moves Connected to Greeted; an unsupported version returns a precise error; a chat message in the lobby leaves the state unchanged. The match below makes every accepted transition visible in one place:

fn apply(state: &mut SessionState, message: &Message) -> Result<(), ProtocolError> {
    match (*state, message) {
        (SessionState::Connected, Message::Greeting { version: 1 }) => {
            *state = SessionState::Greeted;
            Ok(())
        }
        (SessionState::Connected, Message::Greeting { version }) => {
            Err(ProtocolError::UnsupportedVersion(*version))
        }
        (SessionState::Greeted, Message::LobbyJoined { room }) if !room.is_empty() => {
            *state = SessionState::InLobby;
            Ok(())
        }
        (SessionState::InLobby, Message::MatchStarted { scenario })
            if !scenario.is_empty() =>
        {
            *state = SessionState::InMatch;
            Ok(())
        }
        (SessionState::InLobby | SessionState::InMatch, Message::Chat { .. }) => Ok(()),
        (_, Message::Goodbye) => {
            *state = SessionState::Closed;
            Ok(())
        }
        (state, message) => Err(ProtocolError::IllegalTransition {
            state,
            message: match message {
                Message::Greeting { .. } => "greeting",
                Message::LobbyJoined { .. } => "lobby_joined",
                Message::MatchStarted { .. } => "match_started",
                Message::Chat { .. } => "chat",
                Message::Goodbye => "goodbye",
            },
        }),
    }
}

Drawn as a diagram, apply is this state machine:

Each arrow is one arm of the match. A message with no arrow out of the current state, such as Chat while Greeted, falls through to the last arm and returns IllegalTransition. A Greeting with any version other than 1 is refused by its own arm with UnsupportedVersion, and Goodbye is accepted in every state, including Closed itself.

This is longer than a chain of if statements, but every state and message variant has an explicit case. Adding a variant makes an exhaustive match stop compiling until you decide how to handle it.

Unchanged bytes can be invalid in a new session phase. This step-by-step trace needs JavaScript. Here is the code and where the run ends.

state = Connected
read the next recorded event
check which events are allowed in this state
update state for an accepted transition
deliver Chat only from InLobby
report the stopping phase

Result: Closed, 1 delivered chat event(s), sequence accepted. Replaying bytes does not recreate their original session context.

Final values: order = normal; event = Goodbye; state = Closed; delivered = 1; accepted = true.

Read every step of the lesson’s example

1. Step 1, line 1. Start with the selected inputs and follow how the next operation changes the state.

   order = normal.

2. Step 2, line 2. Read Greeting while Connected.

   order = normal; event = Greeting; state = Connected.

3. Step 3, line 4. Accept the event and retain its resulting phase.

   order = normal; event = Greeting; state = Greeted; delivered = 0.

4. Step 4, line 2. Read Join while Greeted.

   order = normal; event = Join; state = Greeted; delivered = 0.

5. Step 5, line 4. Accept the event and retain its resulting phase.

   order = normal; event = Join; state = InLobby; delivered = 0.

6. Step 6, line 2. Read Chat while InLobby.

   order = normal; event = Chat; state = InLobby; delivered = 0.

7. Step 7, line 4. Accept the event and retain its resulting phase.

   order = normal; event = Chat; state = InLobby; delivered = 1.

8. Step 8, line 2. Read Match while InLobby.

   order = normal; event = Match; state = InLobby; delivered = 1.

9. Step 9, line 4. Accept the event and retain its resulting phase.

   order = normal; event = Match; state = InMatch; delivered = 1.

10. Step 10, line 2. Read Goodbye while InMatch.

    order = normal; event = Goodbye; state = InMatch; delivered = 1.

11. Step 11, line 4. Accept the event and retain its resulting phase.

    order = normal; event = Goodbye; state = Closed; delivered = 1.

12. Step 12, line 6. Result: Closed, 1 delivered chat event(s), sequence accepted. Replaying bytes does not recreate their original session context.

    order = normal; event = Goodbye; state = Closed; delivered = 1; accepted = true.

Watch it happenReplay five frames into a session state

Five unchanged frames are Greeting v1, LobbyJoined, Chat, MatchStarted and Goodbye. A separate state marker moves from Connected to Greeted, InLobby, InMatch and Closed. The Chat frame is delivered without moving the state marker out of InLobby.

Read the steps

1. Keep the five captured frames unchanged. The replay starts in Connected; the state marker is separate from the log.
2. Frame 0: version 1 is supported, so Connected becomes Greeted.
3. Frame 1: the lobby message is legal after the greeting. Move from Greeted to InLobby.
4. Frame 2: chat is legal in the lobby. Deliver the chat, but keep the session in InLobby. A message need not change the state.
5. Frame 3: the match-start message is legal in the lobby. Move from InLobby to InMatch.
6. Frame 4: Goodbye closes the session. The state moves to Closed while every original frame remains in the log.
7. The result is a model built from the log. Changing a rule means replaying these same five frames, rather than editing a stored state by hand.

The log records messages. Applying legal messages produces state; chat can be accepted without a state transition.

Store captures as direction plus bytes

Do not save only the decoded text. A replay fixture should preserve:

• client-to-server or server-to-client direction;
• time relative to the previous frame;
• exact frame bytes;
• the game and protocol version;
• the experiment that produced the capture.

#[derive(Clone, Debug)]
struct CapturedFrame {
    after_ms: u32,
    from_server: bool,
    bytes: Vec<u8>,
}

Redact account names or chat content before committing fixtures. A local test capture should contain only invented data.

Replay without a network

Replay takes recorded frames and the parser used for this protocol version. It starts from Connected, validates each frame’s size and delay, parses its bytes, and applies the resulting message to the session state. The returned state is the result of those messages under the current transition function; the error names the frame where interpretation stopped:

use anyhow::Context;

fn replay(
    frames: &[CapturedFrame],
    mut parse: impl FnMut(&[u8]) -> anyhow::Result<Message>,
) -> anyhow::Result<SessionState> {
    let mut state = SessionState::Connected;

    for (index, frame) in frames.iter().enumerate() {
        anyhow::ensure!(frame.bytes.len() <= 64 * 1024, "frame {index} is too large");
        anyhow::ensure!(frame.after_ms <= 30_000, "frame {index} has an absurd delay");

        let message = parse(&frame.bytes)
            .with_context(|| format!("could not parse frame {index}"))?;
        apply(&mut state, &message)
            .map_err(|error| anyhow::anyhow!("frame {index}: {error:?}"))?;
    }

    Ok(state)
}

The test does not sleep for after_ms. It validates timing metadata deterministically. A separate integration test can use a virtual clock to exercise timeouts.

Deterministic replay requires controlling every input that affects a transition: message order, clock readings, random choices, configuration, and initial state. If the same fixture sometimes reaches different states, one of those inputs is still hidden. Pass it into the model instead of reading a real clock or global setting from inside apply.

For example, imagine a lobby rule that closes a connection if no greeting arrives within five seconds. The same captured Greeting should be accepted at 4,900 ms and rejected at 5,100 ms when a test supplies those times to a virtual clock. Reading the wall clock inside apply would make the result depend on how fast the test machine runs, so that timeout test needs a clock-aware version of the model rather than the small replay above.

Mutate one fact at a time

Useful negative replays include:

• truncate one length prefix;
• make a length larger than the available payload;
• send chat before greeting;
• repeat a one-time greeting;
• remove the final frame;
• insert an unknown message type;
• exceed the maximum accepted text length.

The expected outcome is a precise error at a precise frame, never an out-of-bounds read or an infinite wait. Replaying Greeting twice, for example, stops at frame 1 with an IllegalTransition error for state Greeted, because the state machine has no Greeting arrow out of Greeted.

Narration: A single changed field lets a rejected replay identify one failed assumption instead of several competing explanations.

A length larger than the available payload has to fail before any message is decoded:

000

100

200

309

443

544

645

7??

8??

9??

10??

11??

12??

length field: 9

3 payload bytes present

6 bytes the frame claims but does not have

The big-endian length 00 00 00 09 promises 9 payload bytes, but only 3 follow, so 9 − 3 = 6 are missing. A parser that trusted the length would read 6 bytes past the end of the frame; a checked slice turns that into an error for this frame instead.

For messages that may be retried, test idempotence explicitly. Applying the same acknowledgment twice should either preserve the same state or return a clear duplicate error; it should not create a second match, grant a reward twice, or move backward in the session.

Lesson 9.1’s purchase retry showed the server side: it remembers each request identifier and returns the earlier result, or rejects the repeat as a duplicate. In a replay, that identifier is what makes “same request” testable. A repeated Chat with identical text could instead be a new message, so matching bytes alone is not a safe duplicate rule.

Why replay beats manual clicking

Clicking through a live session tests one run once. A replay sends the same frames through a changed parser, framing code, or session rule again in milliseconds. Keep live-network code at the edge and feed the bytes it receives into the same parser and state machine tested by replay. That design keeps transport separate from parsing and makes the protocol model reproducible. 🌐

From session replay to real-time state

The Wesnoth lobby replay above checked whether each message was legal in one conversation. A fast action game adds a second question: which version of the world should the client draw while messages are still travelling? The same capture, framing, and state-machine discipline applies, but ticks and sequence numbers become part of the state.

Real-time games replicate a simulation, not just variables

Most action games advance the world in discrete ticks. If a server runs at 60 ticks per second, one simulation step is approximately:

tick duration = 1 second / 60 = 16.67 milliseconds

The client samples input, labels it, and sends a command. The server processes commands during its own ticks and periodically sends a snapshot or delta. The client then draws frames between confirmed server states:

A field’s meaning depends on the kind of message carrying it. In Lesson 9.1’s move north, (10, 14) in the request is a desired destination, an intent; the same (10, 14) in the server’s reply is an accepted position. An acknowledgment confirms that a command arrived or was applied. A snapshot reports enough state to stand alone, while a delta reports only changes from an identified earlier state, its baseline. Equal-looking bytes can have different authority.

Several similar-looking states can therefore coexist:

State	Purpose	Important label
Last confirmed state	What the server has accepted	Server tick or snapshot ID
Predicted state	Immediate response to local input	Last locally simulated command
Interpolated state	Smooth display of remote objects	Render timestamp between snapshots
Historical state	Rewind or lag-compensation query	Past server tick or time

This explains why a coordinate found in memory can be correct yet appear to “snap back.” You may have found the predicted or rendered copy while a later server snapshot replaced it. Three facts tell the copies apart: which thread writes the field, whether its updates follow input or incoming packets, and which tick or sequence number travels beside it.

Ordering has to be carried in the message

Packet arrival order is not automatically simulation order. UDP packets can arrive late or twice; even over TCP, one stream can contain application events whose own timestamps refer to different moments. Protocols commonly carry:

• a monotonically increasing sequence number;
• a server tick or timestamp;
• an acknowledgment of the newest processed command;
• a bit mask acknowledging several earlier packets;
• a baseline ID telling which snapshot a delta modifies.

Sequence numbers often wrap. For an unsigned N-bit counter, comparisons must use modular arithmetic and accept only a bounded forward window, not a plain incoming > current test.

Work through one 16-bit wraparound. The last accepted sequence number is 65534, and the next two packets carry 65535 and then 0:

current  incoming   naive: incoming > current    (incoming - current) mod 65536
65534    65535      65535 > 65534  -> accept     1   -> accept
65535    0          0 > 65535      -> reject     1   -> accept

The naive test gets the first packet right and the second one wrong. 0 really is one step newer than 65535, but as a plain integer it is smaller, so the packet is thrown away. It gets worse from there: current never advances past 65535, so every sequence number after the wrap looks old in the same way, and the connection appears to stop receiving updates entirely.

The modular test asks a different question — how far forward is incoming from current, counting the wrap? (0 - 65535) mod 65536 is 1, a single step ahead, so the packet is accepted and current moves on. Accept only while that distance stays inside an agreed window such as 1..=32767. A distance of 32768 is exactly halfway around a 16-bit counter and cannot be classified as newer or older from the sequence number alone, so this rule refuses it. A genuinely old packet computes a distance near 65536, which also falls outside the window. The exact window is part of the protocol contract and deserves boundary tests; RFC 1982’s serial-number arithmetic explains the half-range limit.

Applying a delta to the wrong baseline may parse perfectly and still create nonsense. Robust tooling keeps the baseline ID with the bytes, refuses missing dependencies, and bounds how long incomplete state may wait.

The live bot in Lesson 9.6 returns to the simpler Wesnoth lobby conversation. It uses the same separation between framed bytes, decoded messages, and legal session actions that replay made visible.

🧩

Knowledge check

Validate order as well as bytes

A chat frame parses correctly but arrives before the protocol greeting. What should the session parser do?

1Reject it as an illegal transition for the current state2Accept it, because a clean parse proves the message is legal3Accept it and move the session on to `InLobby` automatically4Reset the frame length to zero and parse the chat again

Check answer

Finished Lesson 9.5?

Mark it done and the lesson list shows a ✓ beside it. A chapter whose lessons are all done is marked done too. Progress is saved in this browser only.

Mark lesson doneLesson done. Mark it not done

Chapter 9: 10 lessons

📝 Notes