Predicting host level reachability via static analysis of routing protocol configuration

Abstract

Static analysis refers to techniques that extract and check the semantics of a program entirely from examining its source code. In this case, router configuration files can be thought of as the source code of a distributed program whose execution determines the host level reachability of the network. Static analysis brings about new challenges. Unlike a regular computer program, router configuration commands hide the detailed logic of routing protocols. Completely constructing the logic for static analysis of router configuration files is difficult and even impossible in some cases where the network has a large number of concurrently running routing processes distributed over many routers and variable network delays make the interactions between these processes too complex to understand exactly. This research takes an initial step in understanding the power of static analysis. A system is built to infer the packet forwarding table of each router from the router configuration files. The scope of the work is confined to networks where OSPF is used exclusively for routing. The system is able to infer the exact forwarding tables of the Cisco routers for several lab test networks.