StacKAT : Infinite State Network Verification DOI: 10.1145/3729257 Journal: PACMPL Volume: 9 PLDI 158 6 CCS: Networks Network reliability CCS: Theory of computation Semantics and reasoning CCS: Theory of computation Automated reasoning CCS: Theory of computation Logic and verification
Jules Jacobs, Nate Foster, Tobias Kappé, Dexter Kozen, Lily Saada, Alexandra Silva, Jana Wagemaker · 2025
Read StacKAT : Infinite State Network Verification DOI: 10.1145/3729257 Journal: PACMPL Volume: 9 PLDI 158 6 CCS: Networks Network reliability CCS: Theory of computation Semantics and reasoning CCS: Theory of computation Automated reasoning CCS: Theory of computation Logic and verification by Jules Jacobs, Nate Foster, Tobias Kappé, Dexter Kozen, Lily Saada, Alexandra Silva, Jana Wagemaker (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-13383.txt.
Introduction
Jules Jacobs and co-authors build StacKAT, a language for checking network behavior in systems whose state can grow without bound. Networks parse packets, route them, and log telemetry, tasks that need memory of what came before. Older check languages lack a stack, so they cannot state such behavior well.
StacKAT treats packet headers as fixed fields and the unparsed rest as a stack with push and pop moves. That view lets programs state parsing, source routing, and telemetry in one tongue. The team gives a decision method for whether two programs act alike, built on finite automata. When programs differ, the method can show a case that splits them. A full rule set for program equality is also given and proved complete. Operators gain a sound way to verify tricky network code.
Catalog record
| CREATOR | Jules Jacobs, Nate Foster, Tobias Kappé, Dexter Kozen, Lily Saada, Alexandra Silva, Jana Wagemaker |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-13383
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
StacKAT : Infinite State Network Verification DOI: 10.1145/3729257 Journal: PACMPL Volume: 9 PLDI 158 6 CCS: Networks Network reliability CCS: Theory of computation Semantics and reasoning CCS: Theory of computation Automated reasoning CCS: Theory of computation Logic and verification Jules Jacobs, Nate Foster, Tobias Kappé, Dexter Kozen, Lily Saada, Alexandra Silva, Jana Wagemaker Abstract . We develop StacKAT , a network verification language featuring loops, finite state variables, nondeterminism, and—most importantly—access to a stack with accompanying push and pop operations. By viewing the variables and stack as the (parsed) headers and (to-be-parsed) contents of a network packet, StacKAT can express a wide range of network behaviors including parsing, source routing, and telemetry. These behaviors are difficult or impossible to model using existing languages like NetKAT . We develop a decision procedure for StacKAT program equivalence, based on finite automata. This decision procedure provides the theoretical basis for verifying network-wide properties and is able to provide counterexamples for inequivalent programs. Finally, we provide an axiomatization of StacKAT equivalence and establish its completeness. 1. Introduction NetKAT ( Anderson et al. 2014 ; Foster et al. 2015 ; Smolka et al. 2015 ) is a domain-specific language for specifying and verifying network behavior. Formally, a NetKAT program is a regular expression over assignments f\mathrel{\!\shortleftarrow\!}v and guards f\mathrel{\!=\!}v : 1 1 1 NetKAT also has a special action \mathsf{dup} , which we omit here for the sake of simplicity but discuss in a later section. \displaystyle e::=0\mid 1\mid e_{1}+e_{2}\mid e_{1}\cdot e_{2}\mid e^{*}\mid f\mathrel{\!=\!}v\mid f\mathrel{\!\shortleftarrow\!}v Expressions like (f\mathrel{\!\shortleftarrow\!}3\,+\,f\mathrel{\!=\!}3\cdot f\mathrel{\!\shortleftarrow\!}4)^{*} represent traces similar to the regular expression (a+b\cdot c)^{*} , but with imperative actions f\mathrel{\!\shortleftarrow\!}3 , f\mathrel{\!=\!}3 , and f\mathrel{\!\shortleftarrow\!}4 instead of letters a , b , and c . The action f\mathrel{\!\shortleftarrow\!}v sets a variable f to a constant value v , and the guard f\mathrel{\!=\!}v discards the current trace if variable f is not v . As such, NetKAT can be viewed as an imperative programming language over a simple data model—i.e., network packets represented as finite records from header fields f to values v . Because NetKAT can assign and check equality only with respect to constants, it is too simple to model general-purpose imperative programs written in languages like Python or C. But it turns out to be an ideal model for the kind of computation that arises in high-speed network data planes. Network devices like routers, switches, firewalls, etc., process packets using efficient piplines that classify packets using predicates formulated in terms of constant values ( f\mathrel{\!=\!}v ) and modify packets using actions that assign packet headers to possibly new constant values ( f\mathrel{\!\shortleftarrow\!}v ). Moreover, NetKAT can model not only the behavior of individual devices, but also the collective behavior of different interlinked devices, by designating a variable \mathsf{sw} as the packet’s current location, and representing the movement of a packet to switch k as an assignment \mathsf{sw}\mathrel{\!\shortleftarrow\!}k . Many practical network verification questions can be formulated in terms of equivalence queries—e.g., reachability, waypointing, correct compilation, and more ( Anderson et al. 2014 ) . Fortunately, a NetKAT expression e can mention only finitely many values and local variables, and the values v are drawn from a finite domain of numerical constants; hence, it has finite state. As a result, semantic equivalence of NetKAT programs is decidable, though the procedure is non-trivial ( Foster et al. 2015 ; Moeller et al. 2024 ) . However, NetKAT ’s restriction to a finite state space precludes modeling a variety of behaviors that arise in practice. First, on real-world devices, packets are not represented as finite records, but as sequences of bytes. 2 2 2 Most devices impose an upper limit on the size of a packet—i.e., the so-called Maximum Transmission Unit (MTU), but mathematically, it is more natural to treat packets as having arbitrary size. In the same way, we usually treat memory on a general-purpose computer as being unbounded, even though physical devices have a finite amount of memory. When a packet enters a switch it must be parsed to “extract” the relevant headers into local variables. Likewise, when a packet exits a switch, the local variables must be serialized (or “deparsed” to use P4’s term ( Bosshart et al. 2014 ) ) back into bytes. By convention, the unparsed portion of the packet is carried along as the payload. To faithfully model packet parsing and serialization in all the various forms used on different devices, NetKAT ’s finite records are insufficient. Second, certain network protocols are not finite state. In source routing schemes ( Sunshine 1977 ) , the packet not only stores its IPv4 destination address, but encodes the entire forwarding path in a stack. Each router pops an element off the stack and forwards the packet to the corresponding next hop. As paths can in principle be arbitrarily long, the stack cannot be encoded using a finite record. Dually, protocols that collect telemetry push records onto a stack to log observations about how the packet was processed at each hop on the end-to-end path. In similar fashion, tunneling protocols prepend a new set of headers to the packet, encapsulating the original headers in the payload, and use the newly added headers to route through a subnetwork. When the packet ultimately leaves the subnetwork, the new headers are removed and the original headers are restored from the payload. There are also protocols like Segment Routing and MPLS that combine aspects of tunneling and source routing. NetKAT ’s finite records are also insufficient for modeling these protocols. In this paper, we extend NetKAT to StacKAT , enriching its data model so that a packet \langle h,s\rangle comprises both a finite record h mapping fields to values as well as a stack s representing the unparsed portion of the packet. To manipulate the record, we use NetKAT ’s existing constructs. To manipulate the stack, we add \mathsf{push}(v) and \mathsf{pop}(v) constructs as follows: \displaystyle e::=\underbrace{0\mid 1\mid e_{1}+e_{2}\mid e1\cdot e2\mid e^{*}\mid f\mathrel{\!=\!}v\mid f\mathrel{\!\shortleftarrow\!}v}_{\text{{NetKAT} (dup-free)}}\mid\underbrace{\mathsf{push}(v)\mid\mathsf{pop}(v)}_{\text{New {StacKAT} operations}} The new instruction \mathsf{push}(v) pushes a value v onto the stack, and \mathsf{pop}(v) tests that the top of the stack is v and removes it, dropping the packet if the top of the stack is not v (similar to the guard f\mathrel{\!=\!}v ). In many examples, the stack can be thought of as a sequence of bytes that represent the rest of the packet, while the variables hold information extracted from the raw data. Hence, with these simple extensions, StacKAT can model parsing, source routing, telemetry, tunneling, and MPLS, as well as the \mathsf{dup} instruction used to generate traces in NetKAT ’s original semantics. Various fragments of StacKAT are obviously decidable. For instance, equivalence of StacKAT expressions that do not use push or pop is trivially decidable by a reduction to NetKAT . Also, equivalence of StacKAT expressions that use only push (resp. pop )—and neither local variables nor pop (resp. push )—is also trivially decidable, by reduction to equivalence of regular expressions. However, it is not clear whether equivalence of arbitrary StacKAT programs is decidable, because the addition of a stack results in infinitely many states. Moreover, equivalence of StacKAT programs needs to take into account subtle interactions of \mathsf{push}(-) and \mathsf{pop}(-) . For instance, we