Write a Blog >>
Thu 23 Jan 2020 14:21 - 14:43 at Ile de France III (IDF III) - Abstract Interpretation Chair(s): Xavier Rival

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.

slides (slides.pptx)2.39MiB

Thu 23 Jan

POPL-2020-Research-Papers
14:00 - 15:05: Research Papers - Abstract Interpretation at Ile de France III (IDF III)
Chair(s): Xavier RivalINRIA/CNRS/ENS Paris
POPL-2020-Research-Papers14:00 - 14:21
Talk
Roberto BruniUniversity of Pisa, Roberto GiacobazziUniversity of Verona and IMDEA Software Institute, Roberta GoriUniversity of Pisa, Isabel Garcia-ContrerasIMDEA Software Institute, Dusko PavlovicUniversity of Hawaii
Link to publication DOI Media Attached File Attached
POPL-2020-Research-Papers14:21 - 14:43
Talk
Ryan BeckettMicrosoft Research, Aarti GuptaPrinceton University, Ratul MahajanUniversity of Washington, Intentionet, David WalkerPrinceton University
Link to publication DOI Media Attached File Attached
POPL-2020-Research-Papers14:43 - 15:05
Talk
Sung Kook KimUniversity of California, Davis, Arnaud J. VenetFacebook, Aditya V. ThakurUniversity of California, Davis
Link to publication DOI Pre-print Media Attached File Attached