Probabilistic Verification of Network Configurations
Probabilistic Verification of Network Configurations
复制标题
网络配置的概率验证
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Martin T. Vechev
中科院分区：
文献类型：
--
作者：
Samuel Steffen;Timon Gehr;Petar Tsankov;Laurent Vanbever;Martin T. Vechev
并非所有重要的网络属性都需要一直被强制执行。通常，更重要的是这些属性保持的时间比例/概率。在依赖复杂的相互依赖的路由协议的网络中计算一个属性的概率是具有挑战性的，并且需要确定所有违反该属性的故障场景。大规模且准确地做到这一点超出了当前网络分析器的能力。在本文中，我们介绍NetDice，它是第一个支持边界网关协议（BGP）、开放最短路径优先协议（OSPF）、等价多路径路由（ECMP）和静态路由的可扩展且准确的概率性网络配置分析器。我们的关键贡献是一种推理算法，用于高效地探索故障场景空间。更具体地说，给定一个网络配置和一个属性φ，我们的算法会自动识别一组链路，其故障被证明不会改变φ是否成立。通过删减这些故障场景，NetDice能够准确地近似计算P(φ)。NetDice支持实际的属性以及包括相关链路故障在内的表达性故障模型。我们实现了NetDice，并在实际配置上对其进行评估。NetDice是实用的：即使在大型网络中，它也能在几分钟内精确地验证概率属性。
Not all important network properties need to be enforced all the time. Often, what matters instead is the fraction of time / probability these properties hold. Computing the probability of a property in a network relying on complex inter-dependent routing protocols is challenging and requires determining all failure scenarios for which the property is violated. Doing so at scale and accurately goes beyond the capabilities of current network analyzers. In this paper, we introduce NetDice, the first scalable and accurate probabilistic network configuration analyzer supporting BGP, OSPF, ECMP, and static routes. Our key contribution is an inference algorithm to efficiently explore the space of failure scenarios. More specifically, given a network configuration and a property φ, our algorithm automatically identifies a set of links whose failure is provably guaranteed not to change whether φ holds. By pruning these failure scenarios, NetDice manages to accurately approximate P(φ). NetDice supports practical properties and expressive failure models including correlated link failures. We implement NetDice and evaluate it on realistic configurations. NetDice is practical: it can precisely verify probabilistic properties in few minutes, even in large networks.
Tiramisu：快速多层网络验证
DOI：
--
发表时间：
2020
期刊：
17th USENIX Symposium on Networked Systems Design and Implementation
影响因子：
--
作者：
Abhashkumar, A.;Gember-Jacobson, A.;Akella, A.
通讯作者：
Akella, A.