Kleene Algebra Modulo Theories

Kleene algebras with tests (KATs) offer sound, complete, and decidable equational reasoning about regularly structured programs. Since NetKAT demonstrated how well various extensions of KATs apply to computer networks, interest in KATs has increased greatly. Unfortunately, extending a KAT to a particular domain by adding custom primitives, proving its equational theory sound and complete, and coming up with efficient automata-theoretic implementations is still an expert's task. We present a general framework for deriving KATs we call Kleene algebra modulo theories: given primitives and notions of state, we can automatically derive a corresponding KAT's semantics, prove its equational theory sound and complete, and generate an automata-based implementation of equivalence checking. Our framework is based on pushback, a way of specifying how predicates and actions interact, first used in Temporal NetKAT. We offer several case studies, including theories for bitvectors, increasing natural numbers, unbounded sets and maps, temporal logic, and network protocols. Finally, we provide an OCaml implementation that closely matches the theory: with only a few declarations, users can automatically derive an automata-theoretic decision procedure for a KAT.