MESSI: Behavioral Testing of BGP Implementations
Talkat 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24) · 2024-04-16..04-18·
summary
MESSI is a model-based tester that symbolically generates joint configuration–state–route triples to exercise BGP behavior, producing about 150K tests and finding 22 correctness bugs across FRR, Quagga, GoBGP, BIRD, Batfish and one closed-source stack. The design uses modular models (filtering, decision, aggregation, dynamics), enumerated regular-expression shapes with DFA-based example generation, and bounded incremental-update deltas to expose stateful bugs like failed route-map updates and mask-handling errors.
AI-written summary · about
chapters (12)
- 0:00MESSI and BGP testing
- 2:29Existing BGP test limits
- 3:34MESSI tool overview
- 4:36Model-based BGP testing
- 6:01BGP testing challenges
- 7:04Modular exploration
- 8:55Statefulness in BGP
- 9:17BGP Dynamics testing
- 11:47Regex challenges in route maps
- 13:14Hybrid regex testing
- 15:00Bugs found by MESSI
- 16:47Contributions
related talks
12mMetha: Network Verifiers Need To Be Correct Too!
35mRoute to Bugs: Analyzing the Security of BGP Message Parsing
12mxBGP: Faster Innovation in Routing Protocols
21mModel-Agnostic and Efficient Exploration of Numerical State Space of Real-World...
20mFirebolt: Finding Bugs in Programmable Data Plane Generators
26mEnhancing network diagnosis with reflection in Prolog (extended abstract)
46mLessons learned from monitoring a large production network
11mRunning BGP in Data Centers at Scale