💻 computer science

Octopus: Practical Equivalence Checking of P4 Packet Parsers

This paper presents Octopus, a tool that translates P4 packet parsers into automata to efficiently verify their equivalence on consumer hardware by providing either a bisimulation proof or a counterexample bit-stream.

Original authors: Jort van Leenen, Tobias Kappé

Published 2026-08-04

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jort van Leenen, Tobias Kappé

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the internet as a massive, bustling city where data travels in tiny, sealed envelopes called "packets." Every time you send a message or stream a video, these packets zip through routers and switches, which act like super-fast traffic cops. Their job is to read the address on the envelope (the header) and decide where to send it next. But before they can read the address, they have to know how the envelope is built. Is the address at the very top? Is there a secret code inside? This job of taking a raw stream of 1s and 0s and figuring out "Okay, these first 16 bits are the port, and these next 16 are the destination" is done by a packet parser.

Think of a parser as a very strict, rule-following robot chef. It takes a long, uncut loaf of bread (the incoming data) and slices it into specific ingredients (headers and fields) based on a recipe. If the robot makes a mistake—say, it slices the crust off the wrong part or misreads the recipe—the whole meal gets ruined. In the digital world, a bad parser can lead to security holes where hackers sneak in, or the network simply crashes. Because these robots are so important, engineers want to make sure they are perfect. But checking if two different recipes (or two versions of the robot's code) do exactly the same thing is incredibly hard. It's like trying to prove two different chefs will cut a loaf of bread in the exact same way for every possible loaf in the universe, without actually baking every single one.

This is where a new tool called Octopus comes in. Created by researchers at Leiden University, Octopus is a clever piece of software designed to check if two packet parsers are "twins"—meaning they behave exactly the same way, even if their code looks different on the inside. Before Octopus, there was a tool called Leapfrog that could do this, but it was like trying to solve a giant puzzle using a supercomputer that needed more memory than a small city's power grid could provide; it often took days and crashed. Octopus, however, is the agile cousin. It uses a different strategy to solve the same puzzle, managing to finish complex checks in just a few minutes on a regular laptop.

The paper presents Octopus as a practical solution to a problem that was previously too heavy for everyday computers. The researchers built Octopus to translate P4 code (the language used to program these network parsers) into a map of possible states, essentially turning the code into a flowchart. Then, it uses a mathematical trick called "symbolic bisimulation" to walk through both parsers' flowcharts at the same time. Instead of testing every single possible piece of data (which is impossible), it tests groups of data at once using logic formulas.

The results are impressive. When the team tested Octopus against the old tool, Leapfrog, Octopus was dramatically faster and used a tiny fraction of the memory. For example, on a difficult test case that made Leapfrog run out of memory and fail, Octopus solved it in under 12 minutes. On a collection of real-world network code found online, Octopus checked hundreds of parser pairs in seconds, often finishing in less than a second per pair. The tool doesn't just say "they match" or "they don't"; it provides proof. If they match, it gives a "certificate" (a mathematical map showing why they are twins). If they don't, it produces a "counterexample"—a specific piece of data that one parser accepts but the other rejects, acting like a smoking gun for engineers to fix the bug.

The researchers are careful to note that while Octopus is much faster and more practical than its predecessor, it doesn't offer the same iron-clad, mathematically proven guarantee that the older tool did (which was built inside a formal proof system). Instead, Octopus relies on standard logic solvers to do the heavy lifting. However, the team verified that Octopus's results are trustworthy by having it generate these certificates, which can be checked independently. They also tested it on synthetic, made-up parsers that were incredibly complex, and it handled them without breaking a sweat.

In short, the paper shows that Octopus makes it possible to rigorously check network parsers on normal hardware, turning a task that used to require a supercomputer into something that can be done in the time it takes to brew a cup of coffee. It doesn't solve every possible problem (it can't handle certain types of complex, nested data stacks yet), but for the vast majority of real-world network code, it proves that checking for equivalence is now practical, fast, and reliable.

Technical Summary: Octopus – Practical Equivalence Checking of P4 Packet Parsers

Problem Statement

Packet parsers are critical components in network switches and routers, responsible for structuring incoming bit-streams into protocol headers and fields. Bugs in these parsers can lead to incorrect forwarding behavior or severe security vulnerabilities, such as the Ripple20 family of exploits. While P4 is a domain-specific language designed to mitigate memory management issues found in general-purpose languages like C, P4 programs can still contain logical errors, particularly when undergoing optimization or refactoring.

Existing tools for verifying parser correctness often face scalability limitations. Specifically, Leapfrog, a previous equivalence checker implemented in the Rocq proof assistant, constructs symbolic bisimulations to prove equivalence. However, Leapfrog's reliance on Ltac (Rocq's tactic language) to build proof objects in the Calculus of Inductive Constructions results in prohibitive resource consumption. For instance, a single benchmark required over 400 GiB of memory and nearly a day of runtime, rendering it impractical for many real-world scenarios.

Methodology

The authors present Octopus, a tool designed to perform practical equivalence checking of P4 packet parsers. Octopus translates P4 parsers into deterministic finite automata (DFA) and attempts to construct a symbolic bisimulation between two parsers.

Core Components

Automata Model:
- P4 parsers are modeled as state machines where states correspond to P4 states, and transitions depend on input bits and the current "store" (header fields and metadata).
- A configuration is defined as a triple $\langle q, s, w \rangle$ , representing the current state $q$ , the store $s$ , and a buffer $w$ of unread bits.
- The model handles the extraction of bits into headers and the execution of assignments (e.g., endianness swaps) within operation blocks.
Symbolic Bisimulation via TGFs:
- Instead of exploring concrete configurations (which are exponentially large), Octopus uses Template-Guarded Formulas (TGFs) to represent sets of configuration pairs symbolically.
- A TGF $\gamma = \langle q_<, q_>, n_<, n_>, \phi_\gamma \rangle$ tracks the states of two parsers, the number of bits in their respective buffers, and a first-order formula $\phi_\gamma$ describing the constraints on the buffers and stores.
- The algorithm (Algorithm 1) iteratively computes successor TGFs. It uses an SMT solver (defaulting to Z3) to check if new reachable pairs are already covered by existing TGFs or if they lead to a contradiction (e.g., one parser accepts while the other rejects).
Forward Construction and Optimization:
- Unlike Leapfrog, which works backward using weakest preconditions, Octopus builds the bisimulation forward using strongest postconditions (SP). This eliminates the need for certain preprocessing steps required by Leapfrog.
- The tool employs a "leaps" technique to advance both parsers simultaneously until an operation block is executed, rather than processing bit-by-bit, significantly reducing the number of steps.
Input and Output:
- Octopus integrates directly with P4C (the P4 reference compiler), accepting P4 source code or compiler intermediate representation (IR) JSON. This removes the need for manual translation to a deeply embedded representation.
- Equivalence: If parsers are equivalent, Octopus outputs a certificate consisting of a set of TGFs forming a symbolic bisimulation.
- Inequivalence: If parsers differ, it generates a counterexample bit-stream (a packet accepted by one but rejected by the other) and the execution paths taken.

Key Contributions

Practical Performance: Octopus achieves equivalence checking on consumer hardware in minutes, whereas Leapfrog often fails due to memory exhaustion or excessive runtime.
Direct P4 Support: By hooking into P4C, Octopus accepts standard P4 parsers without requiring manual translation to a specialized internal format.
Certificate Generation: The tool produces verifiable evidence for its verdicts. For equivalence, it provides a symbolic bisimulation; for inequivalence, it provides a concrete counterexample.
Scalability: The tool successfully handles benchmarks that exceeded the memory limits of previous state-of-the-art tools.

Experimental Results

The authors evaluated Octopus using Leapfrog's benchmark suite, synthetic benchmarks generated by Whippersnapper, and a collection of public P4 code.

Comparison with Leapfrog:
- On Leapfrog's benchmark suite, Octopus outperformed Leapfrog by several orders of magnitude in both runtime and memory usage.
- For the "Variable-length format 3" benchmark, Leapfrog failed to terminate (exceeding 1.4 TiB of memory), while Octopus completed the check in approximately 23 minutes (12.1 min generation + 10.9 min validation) using only 0.252 GiB of memory.
- Across all benchmarks where Leapfrog terminated, Octopus demonstrated significantly lower memory footprints (typically < 0.1 GiB vs. hundreds of GiB).
Synthetic Benchmarks:
- Using Whippersnapper, the authors tested scalability against increasing numbers of fields, headers, and parser depth.
- Runtime was largely insensitive to the number of fields (handled efficiently by leaps) but increased with the number of headers and parser tree depth due to the growth in execution paths and formula size.
- The tool successfully verified equivalences between structurally different parsers (e.g., a parser with $n$ single-field headers vs. one with a single header of $n$ fields) in seconds.
Real-World Code:
- Evaluated on 34 public P4 programs (30 within scope), Octopus performed 435 pairwise equivalence checks on a consumer laptop (Intel Core i5, 24 GiB RAM).
- Average runtime was 0.659 seconds per check, with peak memory usage averaging 51.72 MiB.
- The tool successfully identified non-trivial equivalence classes among parsers that differed syntactically but behaved identically regarding specific protocol decodings (e.g., IPv4 vs. IPv4+TCP).

Significance and Claims

The paper claims that Octopus enables practical equivalence checking of P4 packet parsers, a task previously limited by the resource constraints of formal verification tools like Leapfrog.

Trust vs. Performance: While Octopus does not provide the foundational guarantees of a proof object in the Calculus of Inductive Constructions (as Leapfrog does), it generates certificates that can be independently validated. The authors argue that the trade-off is justified by the ability to run complex checks on standard hardware in minutes.
Relational Verification: The tool focuses on relational verification (comparing two parsers) rather than verifying the functional correctness of a single parser against a specification.
Limitations: The current scope is limited to parsers where each state consumes at least one bit, no lookahead is used, and no header stacks appear. The authors note that unbounded header stacks render equivalence undecidable, but fixed-size stacks could potentially be supported.
Future Work: The authors identify certificate validation as a performance bottleneck (doubling execution time) and propose embedding certificates for SMT queries to reduce overhead. They also aim to extend support for lookahead and termination detection.

In summary, Octopus represents a shift from theoretically rigorous but practically infeasible verification to a tool that balances formal methods with the performance requirements of modern network engineering.