Mobile Ad Hoc Networks Working Group Pars Mutaf Internet-Draft INRIA Claude Castelluccia University of California, Irvine Routing hyperactivity problem statement Status of this Memo This document is an Internet-Draft and is subject to all provisions of section 3 of RFC 3667. By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she become aware will be disclosed, in accordance with RFC 3668. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on July 14, 2005. Copyright Notice Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Mutaf [Page 1] INTERNET-DRAFT 14 January 2005 Abstract The optimization offered by reactive routing relies on the observation that under normal activity a host makes a low rate of outgoing sessions to new or different hosts, and connections are locally correlated. This contrasts the fundamental behavior of address scanning worms that search for new hosts to infect at high speeds. Consequently, each infected node will frequently flood the network with route request messages targeted at possibly non-existing addresses. This phenomenon that can be called "routing hyperactivity", will probably result in excessive energy loss in mobile ad hoc networks, (in addition to other well-known impacts of Internet worms). Accordingly a simple technique is described for reducing the energy loss ~ 15 times for every node in a network. 1. Introduction Internet worms propagate through IP address scanning. The technique consists of generating probe packets to a vulnerable UDP/TCP port at many different IP addresses. Hosts that are hit by the scan respond, receive a copy of the worm and hence get infected. In particular an address scanning technique called "/n local preference scan" is generally used. This is an IP address scanning strategy where an infected host scans IP addresses close to its address with a higher probability than distant Internet addresses. The technique consists of sending probe packets to a vulnerable port of the 2^{32-n} addresses in the same subnet. For example Code RED II probed a completely random IP address 1/8th of the time. Half of the time it probed a machine in the same /8, while 3/8th of the time in the same /16. The bias toward the local /16 and /8 networks means that an infected machine may be more likely to probe a local host, based on the supposition that machines on a single network are more likely to be running the same software as machines on unrelated IP subnets [1]. This document describes a phenomenon called "routing hyperactivity" and shows the potential energy cost caused by /n local preference worms in mobile ad hoc networks. A simple but highly effective energy optimization is also described. 2. Routing hyperactivity in infected reactive networks In infrastructure networks, an Internet worm that deploys the local preference scan strategy triggers an outstanding rate of ARP requests since most of the destination IP addresses are not assigned or their MAC address is unknown. In high-speed LANs operating e.g. at 100Mbps the problem has not received considerable attention since the available local bandwidth is huge and energy consumption is not an issue. Mutaf [Page 2] INTERNET-DRAFT 14 January 2005 In reactive mobile ad hoc networks, the same Internet worms will trigger outstanding rate of flooding processes, causing excessive energy loss during an epidemic. In mobile ad hoc networks, all nodes behave as routers and take part in the discovery and maintenance of routes to other nodes in the network. In "reactive routing", the routing protocol does not take the initiative for finding a route to a destination unless it is necessary. AODV[2] and DSR[3] employ this strategy for avoiding periodic route updates which are mostly useless. On the other hand, routes are discovered on demand by flooding the network with a route request query. The session initiating node's route request packet propagates, i.e. broadcast by every node, in the network. The destination host detects the route request and responds with a unicast route reply message. The route request/reply pair establishes a bidirectional route between the session end-points. Reactive routing protocols are based on the observation that under normal activity a host makes a fairly low rate of outgoing sessions to new or different addresses, and that sessions are locally correlated. This assumption generally holds, and under normal activity the network is rarely flooded. Nevertheless, the optimization of reactive routing, contrasts the fundamental behavior of address scanning worms. These applications generate probe packets to a well-known port of many IP addresses. For each scanned address, the whole network will separately be flooded, i.e. all nodes in the network will broadcast a route request message targeted at a possibly non-existing IP address. All nodes in the network will suffer from what can be called "routing hyperactivity" and hence abnormally high energy loss. The impact will be amplified as time passes and the worm spreads within the mobile ad hoc network. Each infected node, will frequently flood the network with route request packets destined for possibly non-existing IP addresses. In AODV, upon receipt of a route request targeted at a known destination, an intermediary node can return a route reply to the source. DSR also employs similar optimizations using its own semantics and route caches. However most of the scanned addresses will be non-existing, which eliminates such possibilities. In mobile ad hoc networks, nodes enter and leave or change their address without notification. Consequently, solutions based on detecting and dropping route requests targeted at non-existing IP addresses are difficult. 3. Previous efforts Address scanners (sometimes called "horizontal port scanners") received considerable attention from the Internet community. Nevertheless, it appears that detecting and suppressing an address scanning application is surprisingly difficult. This is primarily because not all address scanners are necessarily malicious. For Mutaf [Page 3] INTERNET-DRAFT 14 January 2005 example, some applications e.g. SSH, some peer-to-peer and Windows applications have modes in which they scan in a benign attempt to locate servers[4]. In order to avoid seriously penalizing legitimate address scanners, a different approach based on rate limiting has been proposed. The technique is called "virus throttling" and consists of installing a filter on the network stack of Internet hosts. A host restricts the rate of outbound connections to new hosts such that hostile address scanners are penalized with additional delay but normal traffic is unaffected. This is a benign response that slows down but does not stop the purportedly malicious application[5]. In reactive mobile ad hoc networks, virus throttling would not only slow down propagation but also limit the bandwidth cost of address scanners. In this context, a throttling effect can easily be made by rate limiting the outbound route requests. This approach, however, is not really effective for saving "energy". An address scanning application will generate a burst of N route request floods for N different IP addresses. If route request packets are rate limited to e.g. 1 packet second, N seconds later the same amount of energy will have been consumed (by all nodes). Using simple rate limiting, energy consumption can be postponed but not truly reduced. 4. Route request aggregation A more energy-efficient optimization, that is orthogonal to rate limiting, is "route request aggregation". In response to a burst of N outgoing connection attempts of an address scanning application, a node can generate 1 route request message that carries the N target IP addresses (found in the outbound route request queue). For example, assuming a 28-byte 802.11 MAC header, an AODV route request packet is 576 bits long. Using standard route discovery, in response to an address scan, an infected node (and hence every node in the network) will broadcast N route request messages, i.e. 576 x N bits. Using route request aggregation, a route request message will carry N x 32 target IP addresses instead of 1, and all nodes will broadcast (576-32) + N x 32 bits. Consequently the energy gain of route request aggregation will be given by (for all nodes): N x 576 G = -------------------- 544 + N x 32 If, for example, N=100 is set, all nodes in the network will suffer from G=15.38 times smaller energy loss during an epidemic. Route request aggregation is applicable to both AODV and DSR. No modification is required to the path construction and maintenance semantics of the underlying routing protocol (AODV or DSR). Mutaf [Page 4] INTERNET-DRAFT 14 January 2005 5. Conclusion This document described the routing hyperactivity problem. By infecting many nodes in a mobile ad hoc network, address scanning worms may cause serious energy loss in reactive mobile ad hoc networks. Accordingly, a simple but effective energy optimization called route request aggregation was recommended. References [1] D. Moore, C. Shannon, J. Brown, "Code-Red: a case study on the spread and victims of an Internet worm", IMW, 2002. [2] C. Perkins et al, "Ad hoc On-Demand Distance Vector (AODV) Routing", RFC3561, July 2003. [3] D. Johnson et al, "The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)", draft-ietf-manet-dsr-10.txt, July 2004. [4] J. Jung, V. Paxson, A. Berger, and H. Balakrishnan, "Fast Portscan Detection Using Sequential Hypothesis Testing", Proc. IEEE Symposium on Security and Privacy, May 2004. [5] M. Williamson, "Throttling viruses: restricting propagation to defeat malicious mobile code", available at www.hpl.hp.com/techreports/2002/HPL-2002-172.pdf. Authors' Addresses Questions about this document can also be directed to the authors: Pars Mutaf Email: pars.mutaf@inria.fr INRIA Sophia-Antipolis France Claude Castelluccia Currently visiting UCI Email: claude.castelluccia@inria.fr California, USA Mutaf [Page 5] INTERNET-DRAFT 14 January 2005