Property Tests for Parsers and Protocols

How property-based tests expose parser and protocol bugs through invariants, generators, shrinking, and round trips.

Software ยท Verification

Example tests prove specific cases. Property tests search a space of cases and check invariants that should hold across that space. They are especially useful for parsers and protocols because malformed input space is larger than any hand-written fixture list.

Property shape

A property has three parts:

  1. generate input,
  2. execute the system under test,
  3. assert an invariant.

For an encoder and parser:

\[parse(encode(x)) = x\]

For canonical encodings:

\[encode(parse(bytes)) = canonical(bytes)\]

For streaming parsers, chunking should not change the result:

\[parse(a \Vert b) = parse\_stream([a,b])\]

where $\Vert$ means concatenation.

Parser invariants

Good parser properties include:

  • valid messages round-trip,
  • invalid messages are rejected without panic,
  • partial messages return need more data only when progress is possible,
  • maximum lengths are enforced before allocation,
  • unknown opcodes fail closed or route to an extension path,
  • incremental and one-shot parsing agree,
  • error recovery resumes at a documented boundary,
  • accepted values satisfy protocol constraints.

A fuzz target that only asserts no crash is useful, but weak. Add semantic invariants when possible.

Generators

Generators should produce valid, near-valid, and invalid inputs. Pure random bytes find crashes. Structured generators find semantic bugs.

Seed classes for a binary protocol:

Class Examples
valid smallest, largest, common messages
length bugs zero, one less, exact max, one above max
framing truncated header, extra bytes, repeated delimiter
encoding invalid UTF-8, embedded NUL, noncanonical varint
state duplicate handshake, out-of-order ack, replayed message

Shrinking is the reason property tests are debuggable. The framework reduces a failing case to a smaller reproducer that still violates the property.

Stateful protocols

For protocols with sessions, generate command sequences and compare the implementation against a simple model. The model can be slower and simpler than production code.

Example invariant:

\[state_{impl}(commands) = state_{model}(commands)\]

The model should encode externally visible behavior, not copy production internals.

Practical checks

  • Put size limits on generated inputs.
  • Keep tests deterministic under recorded seeds.
  • Save failing cases as regression fixtures.
  • Track coverage of message variants and parser states.
  • Test allocation and recursion limits explicitly.
  • Run fast property tests in normal CI and deeper fuzzing separately.

Design guidance

Property tests work best when the core parser is pure and host-buildable. Keep sockets, timers, logging, and metrics outside the byte-to-result function. Then test the protocol contract directly.

Source anchors