A Fast Quantitative Analyzer for NetKAT
Thomas Lu, Qiancheng Fu, Kevin Batz, Oliver Bøving, Tiago Ferreira, Mark Moeller, Nate Foster, Alexandra Silva
cs.PL
Jul 15, 2026 · v1
TL;DR
The weighted NetKAT symbolic analysis framework, including weighted symbolic packet programs and semiring semantics, is formalized in Lean.
Abstract
When designing a network, engineers must navigate trade-offs (e.g., one topology offers more aggregate bandwidth, another lower latency or better resilience) that demand reasoning about quantitative properties. We present a fast analyzer for quantitative network properties based on weighted NetKAT (wNetKAT), a domain-specific language that provides a semantic foundation for quantitative reasoning by modeling network behavior using weights drawn from a semiring. At the core of our development is the design of a symbolic data structure – weighted symbolic packet programs (wSPPs) – that compactly represent the semantics of weighted policies, for which a direct implementation would be intractable. We show how to compute all policy constructs symbolically; unsurprisingly, the crux is Kleene star, for which we design a tailored algorithm. We further develop trace-carrying Pareto semirings, which compute multi-objective frontiers together with the network paths that realize them. We formalize the development in Lean and provide an optimized Rust implementation. Being parametric on a semiring, our implementation covers both classical and quantitative analyses: we show that it is competitive with KATch, a heavily optimized Boolean-reachability verifier, and orders of magnitude faster than McNetKAT and Storm on probabilistic analyses. A case study comparing Fat-tree and Jellyfish data-center topologies shows the framework supports multi-objective design-time analysis.
Problem
Network engineers must reason about quantitative properties (bandwidth, latency, resilience) when designing networks, requiring efficient analysis of quantitative network policies. Direct implementations of weighted NetKAT semantics are intractable.
Approach
A fast analyzer for weighted NetKAT (wNetKAT) is developed, based on weights drawn from a semiring. A symbolic data structure called weighted symbolic packet programs (wSPPs) compactly represents weighted policy semantics, with all policy constructs computed symbolically including a tailored Kleene star algorithm. Trace-carrying Pareto semirings compute multi-objective frontiers along with realizing network paths. The development is formalized in Lean with an optimized Rust implementation.
Results
The implementation is competitive with KATch (a Boolean-reachability verifier) and orders of magnitude faster than McNetKAT and Storm on probabilistic analyses. A case study comparing Fat-tree and Jellyfish data-center topologies demonstrates multi-objective design-time analysis.