Modular Control Plane Verification via Temporal Invariants

Satisfiability Modulo Theory (SMT)-based tools for network control plane analysis make it possible to reason exhaustively about interactions with peer networks and to detect vulnerabilities such as accidental use of a network as transit or prefix hijacking. SMT-based reasoning also facilitates synthesis and repair. To scale SMT-based verification to large networks, we introduce Timepiece, a new modular control plane verification system. While past verifiers like Minesweeper were based on analysis of stable paths, we show that such models, when deployed naively in service of modular verification, are unsound. To rectify the situation, we adopt a routing model based around a logical notion of time and develop a sound, expressive, and scalable verification engine. Our system requires that a user specifies interfaces between module components. We develop methods for defining these interfaces using predicates inspired by temporal logic, and show how to use those interfaces to verify a range of network-wide properties such as reachability, "no transit," and "no hijacking." Verifying a prefix-filtering policy using a non-modular verification engine times out on a 320-node fattree network after 4 hours. However, Timepiece verifies a 4,500-node fattree in 6.5 minutes on a 96-core virtual machine. Modular verification of individual routers is embarrassingly parallel and completes in seconds, which allows verification to scale beyond non-modular engines, while still allowing the full power of SMT-based symbolic reasoning.