On the Survivability of Routing Protocols in Ad Hoc Wireless NetworksBaruch Awerbuch, Reza Curtmola,David Holmer and Herbert RubensDepartment of Computer ScienceJohns Hopkins UniversityBaltimore, MD 21218 USA{baruch, crix, dholmer, herb}@cs.jhu.eduCristina Nita-RotaruDepartment of Computer SciencePurdue UniversityWest Lafayette, IN 47907 [email protected] routing protocols are able to provide servicein the presence of attacks and failures. The strongest attacksthat protocols can experience are attacks where adversarieshave full control of a number of authenticated nodes that be-have arbitrarily to disrupt the network, also referred to asByzantine attacks. This work examines the survivability ofad hoc wireless routing protocols in the presence of severalByzantine attacks: black holes, flood rushing, wormholesand overlay network wormholes. Traditional secure rout-ing protocols that assume authenticated nodes can alwaysbe trusted, fail to defend against such attacks. Our pro-tocol, ODSBR, is an on-demand wireless routing protocolable to provide correct service in the presence of failuresand Byzantine attacks. We demonstrate through simulationits effectiveness in mitigating such attacks. Our analysisof the impact of these attacks versus the adversary’s effortgives insights into their relative strengths, their interactionand their importance when designing wireless routing pro-tocols.1 IntroductionThe wide-spread adoption of portable computing devicescombined with the recent advances in wireless technologyhas lead to increases in productivity in the corporate and in-dustrial sectors. While these recent advances have enhancedexisting business processes, they have also introduced newsecurity vulnerabilities.Traditionally, networks have strongly relied on physicalsecurity. The concept of a network firewall is an exampleof this approach. A firewall is intended to provide an accesscontrol division between the insecure public network (theInternet) and the seemingly secure private internal corpo-rate network. However, in the context of wireless networks,the assumption about the physical security of the networkinfrastructure is unrealistic. The wireless shared medium isexposed to outsiders and susceptible to a wide range of at-tacks such as: jamming of the physical layer, disruption ofthe medium access control layer, attacks against the rout-ing protocols, targeted attacks on the transport protocols, oreven attacks intended to disrupt specific applications.In addition to the vulnerabilities of the wireless commu-nication to outside attacks, the ultra portability of moderndevices provides an increased susceptibility to theft. In2003, 59% of companies surveyed in the CSI/FBI Com-puter Crime and Security Survey [1] reported that laptopshad been stolen. The likelihood of devices being capturedis even higher for military devices operating in a battlefieldenvironment. Once captured, these devices can be used toattack the network from inside. Therefore, there is a needfor protocols able to operate correctly not only in the pres-ence of failures and outside attacks but also when part ofthe network is under the control of the adversary. Attacksdenoted by arbitrary (malicious) behavior are also known asByzantine [2] attacks and protocols able to provide servicein the presence of attacks and failures are often referred toas survivable protocols.Many secure routing protocols focus only on providingauthentication and integrity of messages. Authenticationand data integrity mechanisms, although needed in order toprevent injection, modification and impersonation attacks,do not provide protection against Byzantine attacks sincethey cannot force a node to behave as specified by the pro-tocol. Below, we outline several Byzantine attacks that areconsidered in this work. We believe they are representativeof the types of attacks that are likely to be mounted againstad hoc wireless routing protocols, and they cover a widerange of adversarial strengths. Individual techniques wereproposed [3, 4, 5, 6, 7] to mitigate each of these attacks, butODSBR [8] is the only full-fledged protocol that can with-stand all of them.A Black Hole Attack is a basic Byzantine attack wherethe adversary drops entirely or selectively data packets,while still participating in the routing protocol. As a result,whenever an adversarial node is selected on a path, data willbe lost partially or entirely on that path.A Flood Rushing Attack exploits the flood duplicate sup-pression technique used by many wireless routing proto-cols. If an attacker succeeds in rushing an authenticatedflood through the network before the flood traveling througha legitimate route, then the legitimate version will be ig-nored and only the adversarial version will be propagated.This attack may result in establishing many adversarial con-trolled paths. Authentication techniques can not prevent theattack, since adversaries are authenticated nodes.A Byzantine Wormhole Attack is an attack in which twocolluding adversaries cooperate by tunneling packets be-tween each other in order to create a shortcut (or wormhole)in the network. This tunnel can be created by using a pri-vate communication channel, such as a pair of radios anddirectional antennas, or by using the existing ad hoc net-work infrastructure. The adversaries can use the low costappearance of the wormhole in order to increase the proba-bility of being selected on paths, and then attempt to eitherdisrupt the network by selectively dropping the data pack-ets, or to perform traffic analysis. Note that for a Byzantinewormhole, the wormhole link exists between two compro-mised (adversarial) nodes, while in a traditional wormholetwo honest nodes are tricked into believing that there existsa direct link between them.A Byzantine Overlay Network Wormhole Attack is amore general (and stronger) variant of the previous attack,which occurs when several nodes are compromised andform an overlay network. By tunneling packets through theoverlay network, the adversaries make it appear to the rout-ing protocol that they are all neighbors, which considerablyincreases their chances of being selected on routes and fa-cilitates further attacks.In this work we study the survivability of ad hoc wirelessrouting protocols in the presence of failures and Byzantineattacks. Our contributions are:• We present a detailed description of several Byzantineattacks (black hole, flood rushing, wormhole and over-lay