An On-Demand Secure Routing Protocol Resilient toByzantine FailuresBaruch Awerbuch, David Holmer, Cristina Nita-Rotaru and Herbert RubensDepartment of Computer ScienceJohns Hopkins University3400 North Charles St.Baltimore, MD 21218 USA{baruch, dholmer, crisn, herb}@cs.jhu.eduABSTRACTAn ad hoc wireless network is an autonomous self-organizingsystem of mobile nodes connected by wireless links wherenodes not in direct range can communicate via intermediatenodes. A common technique used in routing protocols for adhoc wireless networks is to establish the routing paths on-demand, as opposed to continually maintaining a completerouting table. A significant concern in routing is the abil-ity to function in the presence of byzantine failures whichinclude nodes that drop, modify, or mis-route packets in anattempt to disrupt the routing service.We propose an on-demand routing protocol for ad hocwireless networks that provides resilience to byzantine fail-ures caused by individual or colluding nodes. Our adaptiveprobing technique detects a malicious link after log n faultshave occurred, where n is the length of the path. Theselinks are then avoided by multiplicatively increasing theirweights and by using an on-demand route discovery proto-col that finds a least weight path to the destination.Categories and Subject DescriptorsC.2.0 [General]: Security and protection; C.2.1 [NetworkArchitecture and Design]: Wireless communication; C.2.2[Network Protocols]: Routing protocolsGeneral TermsAlgorithms, Design, Reliability, Security, TheoryKeywordsad hoc wireless networks, on-demand routing, security, byzan-tine failuresPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.WiSe’02, September 28, 2002, Atlanta, Georgia, USA.Copyright 2002 ACM 1-58113-585-8/02/0009 ...$5.00.1. INTRODUCTIONAd hoc wireless networks are self-organizing multi-hopwireless networks where all the hosts (nodes) take part inthe process of forwarding packets. Ad hoc networks caneasily be deployed since they do not require any fixed in-frastructure, such as base stations or routers. Therefore,they are highly applicable to emergency deployments, nat-ural disasters, military battle fields, and search and rescuemissions.A key component of ad hoc wireless networks is an ef-ficient routing protocol, since all of the nodes in the net-work act as routers. Some of the challenges faced in adhoc wireless networks include high mobility and constrainedpower resources. Consequently, ad hoc wireless routing pro-tocols must converge quickly and use battery power effi-ciently. Traditional proactive routing protocols (link-state[1] and distance vectors [1]), which use periodic updates orbeacons which trigger event based updates, are less suit-able for ad hoc wireless networks because they constantlyconsume power throughout the network, regardless of thepresence of network activity, and are not designed to tracktopology changes occurring at a high rate.On-demand routing protocols [2, 3] are more appropriatefor wireless environments because they initiate a route dis-covery process only when data packets need to be routed.Discovered routes are then cached until they go unused fora period of time, or break because the network topologychanges.Many of the security threats to ad hoc wireless routingprotocols are similar to those of wired networks. For exam-ple, a malicious node may advertise false routing informa-tion, try to redirect routes, or perform a denial of serviceattack by engaging a node in resource consuming activitiessuch as routing packets in a loop. Furthermore, due to theircooperative nature and the broadcast medium, ad hoc wire-less networks are more vulnerable to attacks in practice [4].Although one might assume that once authenticated, anode should be trusted, there are many scenarios where thisis not appropriate. For example, when ad hoc networks areused in a public Internet access system (airports or con-ferences), users are authenticated by the Internet serviceprovider, but this authentication does not imply trust be-tween the individual users of the service. Also, mobile de-vices are easier to compromise because of reduced physicalsecurity, so complete trust should not be assumed.Our contribution. We focus on providing routing surviv-ability under an adversarial model where any intermediatenode or group of nodes can perform byzantine attacks suchas creating routing loops, misrouting packets on non-optimalpaths, or selectively dropping packets (black hole). Only thesource and destination nodes are assumed to be trusted. Wepropose an on-demand routing protocol for wireless ad hocnetworks that operates under this strong adversarial model.It is provably impossible under certain circumstances, forexample when a majority of the nodes are malicious, to at-tribute a byzantine fault occurring along a path to a specificnode, even using expensive and complex byzantine agree-ment. Our protocol circumvents this obstacle by avoidingthe assignment of “guilt” to individual nodes. Instead it re-duces the possible fault location to two adjacent nodes alonga path, and attributes the fault to the link between them.As long as a fault-free path exists between two nodes, theycan communicate reliably even if an overwhelming majorityof the network acts in a byzantine manner.Our protocol consists of the following phases:• Route discovery with fault avoidance. Using floodingand a faulty link weight list, this phase finds a leastweight path from the source to the destination.• Byzantine fault detection. This phase discovers faultylinks on the path from the source to the destination.Our adaptive probing technique identifies a faulty linkafter log n faults have occurred, where n is the lengthof the path.• Link weight management. This phase maintains a weightlist of links discovered by the fault detection algorithm.A multiplicative increase scheme is used to penalizelinks which are then rehabilitated over time. This listis used by the route discovery phase to avoid faultypaths.The rest of the paper is organized as follows. Section 2summarizes related work. We further define the problemwe are