TY  - GEN
N1  - This work is licensed under a Creative Commons Attribution 4.0 International License.
EP  - 90.30
AV  - public
Y1  - 2021/08//
SP  - 90.1
TI  - ProbNV: probabilistic verification of network control planes
KW  - Network Verification
KW  -  Network Simulation
KW  -  Probabilistic verification
KW  - 
Probabilistic Network Analysis
KW  -  Control Plane Analysis
KW  -  Router Configuration Analysis
T3  - Proceedings of the ACM on Programming Languages (PACMPL)
A1  - Giannarakis, N
A1  - Silva, A
A1  - Walker, D
CY  - New York, NY, United States
PB  - Association for Computing Machinery (ACM)
UR  - https://doi.org/10.1145/3473595
ID  - discovery10134268
N2  - ProbNV is a new framework for probabilistic network control plane verification that strikes a balance between generality and scalability. ProbNV is general enough to encode a wide range of features from the most common protocols (eBGP and OSPF) and yet scalable enough to handle challenging properties, such as probabilistic all-failures analysis of medium-sized networks with 100-200 devices. When there are a small, bounded number of failures, networks with up to 500 devices may be verified in seconds. ProbNV operates by translating raw CISCO configurations into a probabilistic and functional programming language designed for network verification. This language comes equipped with a novel type system that characterizes the sort of representation to be used for each data structure: concrete for the usual representation of values; symbolic for a BDD-based representation of sets of values; and multi-value for an MTBDD-based representation of values that depend upon symbolics. Careful use of these varying representations speeds execution of symbolic simulation of network models. The MTBDD-based representations are also used to calculate probabilistic properties of network models once symbolic simulation is complete. We implement the language and evaluate its performance on benchmarks constructed from real network topologies and synthesized routing policies.
ER  -