We are interested in a simply stated, yet increasingly important network security problem: how to detect the existence of compromised routers in a link-state routing system and remove them from the routing fabric. The root of this problem arises from the key role that routers play in modern packet switched data networks. To a first approximation, networks can be modeled as a series of point-to-point links connecting pairs of routers to form a directed graph. Since few endpoints are directly connected, data must be forwarded -- hop-by-hop -- from router to router towards its destination. If a router in this fabric is compromised, then an attacker may drop, delay, reorder, corrupt or re-route any of the packets passing through that router. Such a capability can be used to deny service to legitimate hosts, to implement ongoing network surveillance or to provide an efficient man-in-the-middle functionality for attacking end systems.
Such attacks are not simply theoretically feasible, but are practiced today. Attackers have repeatedly demonstrated their ability to compromise routers, either by exploiting weak passwords or latent software vulnerabilities, and standard built-in commands are sufficient to drop or delay packets without requiring any modification to the router's code base. Moreover, several widely published documents provide a standard cookbook for transparently "tunneling" packets from a compromised router through an arbitrary third-party host and back again -- effectively amplifying the attacker's abilities to including arbitrary packet sniffing, injection or modification. Such attacks can be extremely difficult to detect manually, and it can be even harder to isolate which particular router or group of routers have been compromised.
The problem of detecting and removing compromised routers can be thought of as an instance of anomalous behavior-based intrusion detection. That is, a compromised router can be identified by correct routers when it exhibits behavior deviating from what is expected. We break this problem into three subproblems: traffic monitoring, information distribution, and countermeasures.