Why Packet Shape Is Not Enough
SPAR is an approach to protocol-format inference that asks a deceptively simple question: can a fuzzing system test whether packet fields make sense together, rather than merely whether a packet has a plausible shape? This series uses SPAR and its Babel routing-protocol case to build a concrete answer. The goal is not to treat an LLM as an oracle, but to understand how RFC rules, formal constraints, reference parsers, and implementation behavior can challenge one another—and where that process still stops short of complete protocol assurance.
The packet is more than its fields
A network packet is often introduced as a sequence of fields. It has a type, a length, perhaps a flag, an address, a counter, and a payload. A parser reads those fields in order and decides whether the bytes can be interpreted. That description is useful, but incomplete. It describes the packet’s syntax: its visible structure, field boundaries, primitive types, and local size rules.
Protocols also have semantics. A semantic rule says that the meaning or validity of one field depends on another. A length may be computed from a value that appeared earlier. A flag may select a different layout. A reserved value in one field may be forbidden only when a state or mode in another field has a particular value. These are not extra decorations on top of the packet. They are part of what the packet means.
The difference matters because local checks can all succeed while a relationship check fails. Suppose a packet contains an address-encoding field and a count of omitted address bytes. Each value may lie within its individual numeric range. That does not prove that the combination describes a valid address. A parser that checks only the fields in isolation can accept bytes that are well-shaped but internally inconsistent.
This is the distinction behind the paper’s central concern. Existing techniques can often recover the syntactic structure of a protocol—where fields are and what kinds of values they contain—while missing semantic dependencies among those fields. The result is not simply an imperfect description. It can weaken every later security task that depends on the description: generated tests may fail to exercise a meaningful invalid state, and a parser may be judged against a model that never recorded the rule it violates.
Why a plausible packet can still be dangerous
The important failures in this setting do not need to look dramatic. A malformed packet that crashes a parser is easy to recognize as a problem. A packet that is accepted, parsed, and used to make a wrong routing or state decision can be harder to notice. It may not corrupt memory or produce an immediate process failure. Its damage can emerge later, in address computation, route selection, resource use, or the interaction between several protocol messages.
Babel, a loop-avoiding distance-vector routing protocol, gives this abstract problem a precise shape. Babel packets are built from type-length-value structures, and its Update messages contain fields including an address encoding, a prefix length, an omitted-byte count, and the prefix itself. The fields are not independent. The address encoding determines how the prefix is interpreted, while the prefix length and omitted-byte count help determine how much prefix data follows.
One rule in RFC 8966 is especially revealing: when the address encoding, or AE, equals 3, the Omitted field must be zero. The rule is easy to overlook if each field is read separately. A value of 3 can be a permitted AE value; a nonzero Omitted value can be representable as a byte; yet their combination is invalid under the protocol’s semantics. The packet can therefore pass a superficial shape test while contradicting the rule that gives its fields a coherent interpretation.
The USENIX paper uses this relationship to describe a bug in FRRouting’s Babel implementation. The implementation did not enforce the dependency between AE and Omitted. Because those fields and the Prefix participate in computing valid network addresses, accepting the invalid combination could lead to incorrect address computation and routing consequences. The paper connects the omission to suboptimal or congested paths and to a potential traffic-based denial-of-service condition. The precise exploit inputs are not needed to understand the lesson: the defect is a missing relationship check, not a missing byte-boundary check.
That distinction also explains why “fuzzing found no crash” is not a sufficient conclusion. If the test generator never expresses the relationship, it may never create the targeted invalid combination. If the implementation accepts that combination without an obvious runtime symptom, a crash-oriented oracle may not flag it. The missing semantic rule has hidden the failure from both sides of the test: the input corpus and the expected outcome.
This does not mean that syntax-focused fuzzers are useless, or that every semantic defect will evade them. It means that they are aimed at a narrower question. They ask whether a parser handles varied byte arrangements and field values. Semantics-aware testing asks an additional question: does the implementation enforce the conditions that connect those values, including conditions that are distributed across an RFC’s prose and cross-references?
What SPAR makes explicit
SPAR addresses this gap by generating two complementary artifacts from RFC documents: a formal packet-format specification and a reference packet parser. The format describes fields and the predicates that constrain them. The parser provides an executable interpretation of the same material. Neither artifact is treated as infallible. Instead, each can be used to test the other.
That choice is important. If a deployed implementation is used as the only source of truth, a missing check can be mistaken for an unstated protocol rule. The paper’s design deliberately separates format inference from existing implementations so that implementation behavior can become the object of scrutiny. The RFC remains the normative starting point, while the generated format and parser are working representations that must expose their disagreements.
The basic test idea is easy to state. A packet that satisfies the formal constraints should be accepted by the reference parser. A packet that violates one selected constraint while preserving the others should be rejected. If the parser accepts the negative packet, either the parser or the format has a problem that needs inspection. In the other direction, if the parser rejects a packet that the format considers valid, the format may be missing a constraint or misunderstanding the RFC. The same pattern can then be applied to an implementation under test.
For the Babel example, the meaningful negative case is not arbitrary noise. It is a packet that keeps the surrounding Update structure coherent while violating the specific AE/Omitted relationship. That makes the result interpretable. An observed acceptance points to a particular semantic contract, rather than merely showing that the implementation received unusual bytes.
The paper reports this approach across eight protocols, not only Babel. Babel is the clearest case because its RFC makes the relationship visible in a small packet fragment and the paper links it to an implementation defect. The broader evaluation matters because it tests whether the idea survives beyond one carefully chosen example. But the case and the benchmark answer different questions: Babel explains what a semantic dependency looks like in practice; the larger study measures how reliably the method recovered such dependencies within its stated scope.
The question this series will keep asking
Once a protocol is viewed as a set of fields plus relationships, fuzzing changes in a specific way. The important input is no longer just “another packet.” It is a packet designed to test a claim about the protocol. Some packets should satisfy the claim. Others should violate one relationship deliberately. The value of the corpus comes from knowing what each test is meant to establish.
That shift raises four connected questions. First, can the rules be recovered from natural-language RFCs without silently dropping the dependencies that matter? Second, can those rules be represented precisely enough to generate both valid and targeted invalid packets? Third, can a reference parser and the formal description challenge one another rather than repeating the same omission? Finally, when the model and a real implementation disagree, what does the evidence establish about the implementation—and what remains uncertain?
SPAR’s contribution is a proposed answer to the middle of that chain: use adversarial interaction between complementary LLM-driven tasks, with solver-backed packet generation supplying concrete disagreements. Its reported security findings then test whether the inferred semantics are useful outside the generated artifacts. The method is promising precisely because it turns a hidden dependency into something that can be stated, violated, observed, and investigated.
It is also bounded. A mutually consistent format and parser are not a proof that every packet, protocol state, or vendor behavior has been covered. The paper’s evaluated formats have a particular structure, and its packet-generation optimizations trade exhaustive combinations for tractable, targeted tests. Those boundaries are not reasons to dismiss semantic fuzzing. They are the conditions under which its results should be read.
The first practical lesson is therefore narrower than “use AI to fuzz protocols.” Before a system can test semantics, someone—or something that can be checked—must make the semantic rule explicit. Babel’s Update packet shows why that is difficult: the rule is not contained in one isolated field, and a missing check can matter even when parsing appears to succeed. The next step is to examine how such relationships are represented as invariants, and how the Babel example turns field-level description into a testable contract.