Real-Time Verification of Network Properties Based on Header Space

Abstract

The past ten years have seen increasingly rapid advances in the field of network verification. Data plane verification plays a crucial role in this field. Recent developments of SDN, which has been proposed for improving network flexibility and programmability, make the requirement of the dynamic verification. It also provides the ability to dynamically acquire the information of the network state and the rule updating behavior, which makes it possible to perform real-time data plane verification. Previous researches for the real-time data plane verification either perform the verification on the simplified forwarding rules or trace the symbolic headers cross the network behaviors on each switch. Inspired by the discussion of the header space in HSA, we focus on rules themselves and define the computation of transform functions in header space with BDD expressions to get the connection information of rules. The BDD expression makes the transform functions and the rules can be merged as the simplest form for reducing the run time. We propose an updating algorithm based on the matrix operation for incrementally updating rules. The typical network invariants are translated to the requirements of the matrix model. At last, we try to extend the model to verify the invariants in multi-domains networks. The prototype NetV has been compared with NetPlumber and APT on the rule sets of the Standford backbone network and the Internet 2 network. The experiments show that NetV performs better than these two tools on the two rule sets with OpenFlow format. A simple experiment of the real-time verification of two domains is conducted. The result indicates that NetV has advantages over the simulative method by tracking the symbolic headers.

Keywords

• Computer network management
• formal verification
• software-defined network
• header space
• network verification