Real-Time Verification of Network Properties Using Atomic Predicates
Authors:
- 12 March 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 24 (2) , 887-900
Abstract
Network management will benefit from automated tools based upon formal methods. Several such tools have been published in the literature. We present a new formal method for a new tool, Atomic Predicates (AP) Verifier, which is much more time and space efficient than existing tools. Given a set of predicates representing packet filters, AP Verifier computes a set of atomic predicates, which is minimum and unique. The use of atomic predicates dramatically speeds up computation of network reachability. We evaluated the performance of AP Verifier using forwarding tables and ACLs from three large real networks. The atomic predicate sets of these networks were computed very quickly and their sizes are surprisingly small. Real networks are subject to dynamic state changes over time as a result of rule insertion and deletion by protocols and operators, failure and recovery of links and boxes, etc. In a software-defined network, the network state can be observed in real time and thus may be controlled in real time. AP Verifier includes algorithms to process such events and check compliance with network policies and properties in real time. We compare time and space costs of AP Verifier with Header Space and NetPlumber using datasets from the real networks.Keywords
This publication has 12 references indexed in Scilit:
- Debugging the data plane with anteater2011
- FlowChecker2010
- Quantifying and Querying Network Reachability2010
- Network configuration in a box: towards end-to-end verification of network reachability and security2009
- Towards systematic design of enterprise networks2008
- Verification of Distributed Firewalls2008
- Firewall design: consistency, completeness, and compactness2004
- Constructing optimal IP routing tables1999
- Temporal and Modal Logic1990
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986