Nuno P. Lopes, Nikolaj Bjørner, Patrice Godefroid, Karthick Jayaraman, George Varghese
Network Verification is a form of model checking in which a model of the network is checked for properties stated using a specification language. Existing network verification tools lack a general specification language and hardcode the network model. Hence they cannot, for example, model policies at a high level of abstraction. Neither can they model dynamic networks; even a simple packet format change requires changes to internals. Standard verification tools (e.g., model checkers) have expressive specification and modeling languages but do not scale to large header spaces. We introduce Network Optimized Datalog (NoD) as a tool for network verification in which both the specification language and modeling languages are Datalog. NoD can also scale to large to large header spaces because of a new filter-project operator and a symbolic header representation.
As a consequence, NoD allows checking for beliefs about network reachability policies in dynamic networks. A belief is a high-level invariant (e.g., “Internal controllers cannot be accessed from the Internet”) that a network operator thinks is true. Beliefs may not hold, but checking them can uncover bugs or policy exceptions with little manual effort. Refuted beliefs can be used as a basis for revised beliefs. Further, in real networks, machines are added and links fail; on a longer term, packet formats and even forwarding behaviors can change, enabled by OpenFlow and P4. NoD allows the analyst to model such dynamic networks by adding new Datalog rules.
For a large Singapore data center with 820K rules, NoD checks if any guest VM can access any controller (the equivalent of 5K specific reachability invariants) in 12 minutes. NoD checks for loops in an experimental SWAN backbone network with new headers in a fraction of a second. NoD generalizes a specialized system, SecGuru, we currently use in production to catch hundreds of configuration bugs a year. NoD has been released as part of the publicly available Z3 SMT solver.
N. P. Lopes, N. Bjørner, P. Godefroid, K. Jayaraman, G. Varghese. Checking Beliefs in Dynamic Networks. In Proc. of the 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI), May 2015.
@inproceedings{nod-nsdi15,
title = {Checking Beliefs in Dynamic Networks},
author = {Nuno P. Lopes and Nikolaj Bj{\o}rner and Patrice Godefroid and Karthick Jayaraman and George Varghese},
booktitle = {Proc. of the 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI)},
month = may,
year = 2015
}