Abstract
An attractive target for a computer system attackeris the router. An attacker in control of a routercan disrupt communication by dropping or misrout-ing packets passing through the router. We present aprotocol called WATCHERS that detects and reacts torouters that drop or misroute packets. WATCHERSis based on the principle of conservation of ow ina network: all data bytes sent into a node, and notdestined for that node, are expected to exit the node.WATCHERS tracks this ow, and detects routers thatviolate the conservation principle. We show thatWATCHERS has several advantages over existing net-work monitoring techniques. We argue that WATCH-ERS' impact on router performance and WATCHERS'memory requirements are reasonable for many envi-ronments. We demonstrate that in ideal conditionsWATCHERS makes no false-positive diagnoses. Wealso describe how WATCHERS can be tuned to per-form nearly as well in realistic conditions.c 1998 IEEE. Personal use of this mate-rial is permitted. However, permission toreprint/republish this material for advertisingor promotional purposes or for creating newcollective works for resale or redistribution toservers or lists, or to reuse any copyrightedcomponent of this work in other works mustbe obtained from the IEEE. Kirk Bradley's current a
liation is SRI International, 333Ravenswood Avenue, Menlo Park, CA 94025-3493 (e-mail:bradley[at]systech.sri.com). This work has been supported bythe National Security Agency INFOSEC University ResearchProgram under Contract No. DOD-MDA904-96-1-0118, and bythe Defense Advanced Research Projects Agency under grantARMY/DAAH 04-96-1-0207.1 IntroductionThe router is a primary component in the infras-tructure of today's Internet, and is therefore an at-tractive target for attackers. If an attacker can gaincontrol of a router, the attacker can disrupt commu-nication by dropping or misrouting packets passingthrough the router. We present a protocol that detectsand reacts to routers that drop or misroute packets.The protocol is called WATCHERS: Watching forAnomalies in Transit Conservation: a Heuristic forEnsuring Router Security. WATCHERS protects therouters in an autonomous system (AS), a set of routersand networks controlled by one administrative author-ity. WATCHERS is distributed: each participatingrouter concurrently runs the WATCHERS algorithm.Each router checks incoming packets to see if theyhave been routed correctly. Also, each router countsthe data bytes that pass through neighboring routers.Periodically, the routers report their counter valuesto one another, and each router checks if any of itsneighbors have violated the principle of conservationof ow. This principle asserts that all data bytes sentinto a node, and not destined for that node, are ex-pected to exit the node. When a router
nds a neigh-bor that violates the principle, or a neighbor that ismisrouting packets, the router stops sending packetsto that neighbor. Eventually, the bad router is e
ec-tively removed from the network, because all of thebad router's neighbors stop sending packets to it.WATCHERS has four signi
cant advantages overother network monitoring techniques: A network monitoring tool (e.g., traceroute [5] oran implementation of the Simple Network Man-agement Protocol (SNMP) [4]) may fail to detectan attack because the attacker is able to disruptmessages sent by the tool, including messages be-tween separate tool components. WATCHERSuses ooded transmissions (see Section 1.1) andmessage authentication to prevent attackers frominterfering with communication. WATCHERS can detect routers that selectivelydrop or misroute packets, as well as routers thatcooperate to conceal malicious behavior. When they detect suspicious behavior, most net-work monitoring techniques are unable to locatethe malicious (or faulty) routers, or they areonly able to identify a list of potential suspects[4, 5, 8, 13]. WATCHERS can identify the exactrouter(s) which are dropping or misrouting pack-ets. In ideal conditions we show that WATCHERSnever identi
es a good router as bad (i.e., nevermakes a false-positive diagnosis). We also showhowWATCHERS can be tuned to perform nearlyas well in realistic conditions.The rest of this section provides background in-formation on (1) our model of an AS, (2) routing,(3) malicious router behavior, and (4) current routermonitoring techniques and their limitations1. Section2 presents the WATCHERS protocol. Section 3 de-scribes future research tasks. The Appendix provesthat WATCHERS is correct: WATCHERS does notmake any false-positive diagnoses (when certain con-ditions hold). For more details on this work, consultthe comprehensive report


DOWNLOAD FULL REPORT
http://cs.ucdavis.edu/research/tech-repo...-97-17.pdf