Abstract interpretation of distributed network control planes
Abstract interpretation of distributed network control planes
复制标题
DOI：
10.1145/3371110
复制
发表时间：
2019-12
影响因子：
--
通讯作者：
Ryan Beckett;Aarti Gupta;Ratul Mahajan;D. Walker
中科院分区：
文献类型：
--
作者：
Ryan Beckett;Aarti Gupta;Ratul Mahajan;D. Walker
大多数计算机网络的控制平面运行分布式路由协议，以确定是否转发流量。网络控制飞机配置的错误经常击倒关键的在线服务，从而给服务提供商带来经济损失，并为用户带来巨大的困难。通过提前模拟验证可以帮助查找配置错误，但是对于大型工业网络而言，此类技术昂贵甚至是棘手的。我们探索了抽象解释来解决这一基本规模挑战的使用，并发现正确的抽象可以降低网络模拟的渐近复杂性。基于此观察结果，我们构建了一种称为Shapeshifter的工具，用于可及性分析。在来自大型云提供商的127个生产网络的套件上，Shapeshifter在最新的模拟器上提供了渐近的运行时和内存的改进。这些收益的精度最小。我们的摘要分析准确地预测了95％网络的所有目的地以及剩余5％的大多数目的地的可达性。我们还发现，对网络控制平面的抽象解释不仅加快了现有分析的速度，而且促进了新的分析。我们通过对Border Gateway协议（BGP）（全球部署的路由协议）的新目标“劫持”分析来说明这一优势。
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.