Abstract interpretation of distributed network control planes
Open Access
- 20 December 2019
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 4 (POPL) , 1-27
Abstract
The control plane of most computer networks runs distributed routing protocols that determine if and how traffic is forwarded. Errors in the configuration of network control planes frequently knock down critical online services, leading to economic damage for service providers and significant hardship for users. Validation via ahead-of-time simulation can help find configuration errors but such techniques are expensive or even intractable for large industrial networks. We explore the use of abstract interpretation to address this fundamental scaling challenge and find that the right abstractions can reduce the asymptotic complexity of network simulation. Based on this observation, we build a tool called ShapeShifter for reachability analysis. On a suite of 127 production networks from a large cloud provider, ShapeShifter provides an asymptotic improvement in runtime and memory over the state-of-the-art simulator. These gains come with a minimal loss in precision. Our abstract analysis accurately predicts reachability for all destinations for 95% of the networks and for most destinations for the remaining 5%. We also find that abstract interpretation of network control planes not only speeds up existing analyses but also facilitates new kinds of analyses. We illustrate this advantage through a new destination "hijacking" analysis for the border gateway protocol (BGP), the globally-deployed routing protocol.Keywords
Funding Information
- Defense Advanced Research Projects Agency (HR0011-17-C-0047)
- National Science Foundation (1704336 1837030)
This publication has 29 references indexed in Scilit:
- Scaling network verification using symmetry and surgery2016
- A static analyzer for large safety-critical softwareACM SIGPLAN Notices, 2003
- The octagon abstract domain2002
- The stable paths problem and interdomain routingIEEE/ACM Transactions on Networking, 2002
- Automatic predicate abstraction of C programsACM SIGPLAN Notices, 2001
- Counterexample-Guided Abstraction Refinement2000
- The powerset operator on abstract interpretationsTheoretical Computer Science, 1999
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- Automatic discovery of linear restraints among variables of a program1978
- Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints1977