Katra: Realtime Verification for Multilayer Networks


Ryan Beckett, Microsoft; Aarti Gupta, Princeton University


We present a new verification algorithm to efficiently and incrementally verify arbitrarily layered network data planes that are implemented using packet encapsulation and decapsulation. Inspired by work on model checking of pushdown systems for recursive programs, we develop a verification algorithm for networks consisting of stacks of headers. Our algorithm is based on a new technique that lazily "repairs" a decomposed stack of header sets on demand to account for cross-layer dependencies. We demonstrate how to integrate our approach with existing fast incremental data plane verifiers and have implemented our ideas in a tool called Katra. Evaluating Katra against an alternative approach based on equipping existing incremental verifiers to emulate finite header stacks, we show that Katra is between 5x-32x faster for packets with just 2 headers (layers), and that its performance advantage grows with both network size and layering.

NSDI '22 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {278376,
author = {Ryan Beckett and Aarti Gupta},
title = {Katra: Realtime Verification for Multilayer Networks},
booktitle = {19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22)},
year = {2022},
isbn = {978-1-939133-27-4},
address = {Renton, WA},
pages = {617--634},
url = {https://www.usenix.org/conference/nsdi22/presentation/beckett},
publisher = {USENIX Association},
month = apr,

Presentation Video