一句话：用抽象解释降低分布式网络控制平面模拟的渐近复杂度，实现高效可达性分析。
网络控制平面通过分布式路由协议决定流量转发，配置错误常导致严重服务中断，而预先模拟验证在大规模工业网络上代价高甚至不可行。本文探索用抽象解释应对这一扩展性挑战，发现合适的抽象可降低网络模拟的渐近复杂度。作者据此构建了面向可达性分析的工具 ShapeShifter，并在某大型云厂商的 127 个生产网络上评估。与当前最优模拟器相比，该工具在运行时间和内存上取得渐近改进，且精度损失很小：对 95% 的网络能准确预测所有目的地的可达性，对其余 5% 能准确预测大多数目的地。文章还表明，对网络控制平面进行抽象解释不仅加速已有分析，也催生了新的分析，例如针对边界网关协议（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.
@article{paperbot569,
title = {Abstract interpretation of distributed network control planes},
author = {Ryan Beckett and Aarti Gupta and Ratul Mahajan and David Walker},
journal = {Proceedings of the ACM on Programming Languages},
volume = {4},
number = {POPL},
year = {2019},
doi = {10.1145/3371110}
}