Securing the AODV Protocol Using Specification-Based Intrusion Detection Hoda M. Hassan Mohy Mahmoud Sherif El-Kassas American University in Cairo American University in Cairo American University in Cairo 24 Falaki Street 24 Falaki Street 24 Falaki Street Cairo 11511, Egypt Cairo 11511, Egypt Cairo 11511, Egypt +2 02 0123635479 +2 02 0105144451 +2 02 0101200166

[email protected] [email protected] [email protected]

ABSTRACT RREQ message will be broadcasted further until it reaches the This paper presents an implementation of an Intrusion Detection destination. The destination, on its turn, unicasts a RREP to the System (IDS) aiming to secure the AODV protocol designed for source node. As the RREP message propagates back to the MANET. The IDS is designed as multiple static agents that run on a source node the required route is set up.To avoid loops in the subset of the nodes in the network and executes a monitoring route established by the AODV, destination sequence numbers protocol that observes the process of route establishment. The are introduced. Sequence numbers are used to identify the monitoring protocol uses specification based intrusion detection to freshness of routes. Sequence numbers are carried in both the identify misuses to the routing messages. The IDS design is a RREQ and RREP messages, and are incremented each time a correlation of previous work done in the field of MANET security. mobile node sends a RREQ or a RREP. The sequence number The IDS is implemented using ns-2 simulator and its ability to detect in a RREP message must be larger than or equal to the one attacks was tested using previously devised attack scripts. Detailed carried in the corresponding RREQ message to avoid the source specification for the runtime behavior of the AODV protocol was node to adopt a stale route. When the source node receives derived in the process of implementation. several RREP messages, it chooses the route in the RREP message with the largest sequence number. If all RREP Categories and Subject Descriptors messages have the same sequence number the, the route with C.2.0 C.2.1 C.2.2 [Computer-Communication Networks]: General – the smaller hop count will be chosen. More details about Security and Protection. Network Architecture and Design –Wireless AODV can be found in [4] Communication. Network Protocols –Routing Protocols. 1.2 Overview of the Presented Work One of the major vulnerabilities of mobile ad hoc networks is General Terms the cooperative nature of the underlying routing protocols that Algorithms, Management, Measurement, Performance, Design, assumes the robust behavior of all nodes in the network. Such Experimentation, Security. assumption renders the network susceptible to different types of attacks. This paper presents an Intrusion Detection System Keywords (IDS) aiming to secure the AODV protocol [4] through routing AODV, IDS, Specification-based detection, network monitoring. message monitoring. The IDS developed has a distributed 1. INTRODUCTION design and runs on several nodes in the network. The intrusion detection function is performed by the monitoring protocol, 1.1 Overview of the Ad Hoc On-demand which is responsible for tracing all Route Request (RREQ) and Distance Vector (AODV) Protocol Route Reply (RREP) message exchanges to ensure correct AODV is one of the reactive routing protocols developed for route establishment from source to destination. The IDS design MANET. AODV builds routing tables on demand. When a source integrates the work done in [1] and [2] and uses specification node needs to establish a route to a destination node, it broadcasts a based intrusion detection technique to identify misuses done to route request message (RREQ) to all its neighbors. Each the routing messages. The IDS is simulated using the ns-2 intermediate node receiving a RREQ message checks its routing simulator. The IDS performance is evaluated in normal network table for the requested route. conditions and with the introduction of attacks. The IDS ability to detect attacks is measured using the attack scripts against the If a valid route is found, a route reply message (RREP) will be AODV protocol previously developed by Ning and Sun in [3], unicast back to the node initiating the route request, otherwise the and which presents a systematic analysis of insider attacks against the AODV protocol. Permission to make digital or hard copies of all or part of this work for 2. PREVIOUS RESEARCH WORK personal or classroom use is granted without fee provided that copies are not Chin-Yang Tseng et. al. in [2] proposed a specification-based made or distributed for profit or commercial advantage and that copies bear monitoring for the AODV protocol that attempt to detect this notice and the full citation on the first page. To copy otherwise, or intrusions as violations to the correct behavior of the protocol. republish, to post on servers or to redistribute to lists, requires prior specific They suggested tracing the routing messages issued by nodes permission and/or a fee. during route discovery from the source to the destination and Q2SWinet’06, October 2, 2006, Torremolinos, Malaga, Spain. back to the source. Distributed special nodes called Network Copyright 2006 ACM 1-59593-486-3/06/0010...$5.00. Monitors (NMs) perform the role of monitoring. A Network 33 Monitor (NM) keeps track of all routes generated by the nodes in its movement scenario for the nodes is designed to generate the neighborhood. An extra field was added to the route Request (RREQ) following cases: header, to enable the NM to match a current RREQ with a previously detected RREQ. NM uses finite state machines to detect anomalies in Detect a routing the request-reply flow. More details can be found in [2]. message Oleg Kachirski and Ratan Guha in [1] proposed a modular IDS architecture based on mobile agents. This architecture distributed the functionality of the IDS among the nodes of the network such that Search for Mac some nodes have higher-level functionalities as monitoring network in neighbor list traffic and deciding on intrusion behavior. To select such key nodes Oleg Kachirski and Ratan Guha devised an algorithm called Clustered Network-Monitoring Selection Algorithm. The algorithm sums the number of connection a node has as well as its neighbors, and the Yes If MAC No value resulting from this calculation, represents what they called as the is found connectivity index of each node, and is used to choose monitoring nodes. More details about the algorithm is found in [1] Yes No If IP_Mac Ask neighbor match 3. SPECIFICATION-BASED IDS FOR AODV NM PROTOCOL Analyze routing Anomaly Detected The IDS design is a correlation of the work done in [1] and [2]. The Messages IP Spoofing IDS is implemented as a two stage process. The first stage is to choose network monitoring nodes (NMs) using the Clustered Network- Monitoring Selection Algorithm introduced by Karchirski and Guha, Figure 1. Validating IP and MAC Addresses in [1] with some variations. In the second stage the NM nodes will run the Monitoring Protocol that will be responsible for monitoring the • New RREQ for which the source node is not register at the flow of the RREQ and RREP messages. The main focus of this newly neighboring NM • Forwarded RREQ for which the source node is not registered at devised protocol is to ensure the correct order in which the routing messages (RREQ/RREP) are exchanged as well as the integrity of the neighboring NM • Forwarded RREP for which the source node is not registered at contents of these messages. In the process of developing the Monitoring Protocol the AODV specifications were detailed and the different constraints for the RREQ and RREP messages were derived. the neighboring NM To be able to analyze a RREQ-RREP flow and verify that it abides by • New RREP issued by a destination node which is not registered the derived constraints each two consecutive messages need to be at the neighboring NM compared. For a RREP flow the source of the RREP message can be identified using the IP address in the IP header to identify the node Table 1 shows the simulation parameters used and figure 4 forwarding the RREP. As for a RREQ message, its predecessor will be displays the starting network topology as well as the node identified by adding an extra field to the RREQ header to indicate the movements. The nodes selected to be monitors are highlighted previous node. This was suggested by Tseng, et. al in [2]. Also different RREP flows initiated by different intermediate nodes need to be distinguished from each other, therefore an extra field identifying Detected Detected New RREQ Forwarded the IP address for the node initiating the RREP flow will also be added RREQ message to the RREP header. NM nodes listen in promiscuous mode to the wireless link. Each NM node is responsible to monitor the routing No Yes Retrieve Session tree HC==0 traffic belonging to the nodes in its cluster. For each detected routing message (RREQ or RREP), the Mac and IP addresses of the source Ye No node are validated. If source node is one of the nodes to be monitored No RREQID < Session Tree Yes Found then the routing message will be analyzed. Otherwise neighboring NM Saved ID will be informed about the detected message. On receiving messages from neighboring NMs, each NM will analyze the message contents. Ye Dst IP No The flow charts in figure 1,2 and 3 denotes the sequence of monitoring <> saved steps. No Src Sqn < Yes Saved Sqn 4. EXPERTIMENTAL RESULTS Ye Sqn <> No Anomaly The IDS was simulated using the ns-2 network simulator release 2.27 Detected saved Sqn and its code was incorporated into the simulator code as a new agent that runs on the simulated nodes. The IDS performance was evaluated 1.Update node info Ye No without the introduction of attacks, as well as with the introduction of 2.Create Session HC == attacks. The attack scripts used in testing are imported from [3]. tree saved 4.1 Simulation of the IDS in Normal Conditions Anomaly 1.Update RREQ session info Two scripts were simulated to evaluate the IDS performance. In the 2.Insert new node in Session Detecte first script the nodes were static, but in the second the nodes were tree mobile. Yet the nodes chosen to be NM were static since it is assumed that a NM does not leave the cluster it is assigned to monitor. The Figure 2. Analyze RREQ Messages 34 Table 2 shows the result of executing the NM selection algorithm at 0 ƒ Modify and Forward (MF): The attacker modifies one or sec and at 50 sec of the simulation time more fields in a received routing message and then forwards the message to its neighbor(s) ƒ The IDS traced the different RREQ-RREP flows initiated by the nodes. The IDS resulted in delaying the route discovery due to Forge Reply (FR): The attacker sends a faked RREP inducing monitoring messages as well as the processing overhead in message in response to a RREQ message. the monitoring nodes ƒ Active Forge (AF): The attacker sends a faked routing message without receiving any related message. IP-MAC The simulation parameters for the attack scripts are identical to validated RREP Table 1 except for the node speed which ranges from 0m/sec to Message 3.5 m/sec. Table 3 and 4 list the type of attacks for the RREQ and RREP message and the response of the IDS for each case. Yes A monitored No node Table 1. Simulation Parameters for the IDS Operation in Normal Conditions Get session tree using DSt_IP in RREP Number of nodes 20 Send an inquire Transmission Range 250m message Simulation Area 1000m*600m Yes No Tree is Simulation time 100 seconds found Anomaly Connection Type CBR detected Packet Rate 2pkt/sec No Rreplying Number of connections 5 Yes node is in the tree Physical Link Bandwidth 2Mbps Network Monitor Selection 50 sec Interval Node speed 0-20 m/sec Yes Next hop No IP is in tree 2 4 1 14 Yes RREP initiator No 11 0 IP == Dst_IP 13 3 12 7 9 15 6 5 Analyze Analyze Destination 17 Intermediate 18 Figure 3. Analyze RREP Messages 8 16 4.2 IDS Simulation with the Introduction of Figure 4. Network Topology Attacks The imported attack scripts used to evaluate the performance of the IDS have different misuse goals as argued by Ning and Sun in [3]. Table 2. NM nodes and Monitored Node List These misuse goals can be listed as follows ƒ NM at List of NM at List of monitored Route Disruption (RD): Breaking down an existing route or 0 sec monitored nodes 50 sec nodes preventing a new route from being established ƒ 1 13 1 13 Route invasion (RI): An inside attacker adds itself into a route 7 0,5,7,9,11,12,14,7 7 0,5,7,9,11,12,14,19, between two endpoints of a communication channel 17 ƒ Node isolation (NI): Preventing a given node from 8 10 8 10 communicating with any other node in the network by disrupting 9 6,15 10 8,18 all possible routes starting from a given node. 10 8,18 11 1,2,3 ƒ Resource consumption (RC): Consuming the communication 11 1,2,3,4 14 4 bandwidth in the network or storage space at individual nodes. 14 19 16 16 To achieve the previous goals different types of composite attacks (the 16 16 17 6,5 attack is composed of more than one misused message) were induced in the network. These were identified by Ning and Sun as follows 35 Table 3. IDS Response for RREQ Attacks Attack Misuse No. of IDS Response 5. CONCLUSION AND FUTURE WORK An Intrusion detection system aiming at securing the AODV type Goal scripts protocol was developed using specification-based detection MF RD 8 The IDS failed in one script technique and it is based on previous work done in [1] and [2]. because there was no route The IDS performance in detecting misuse to the AODV routing available between the source message was tested using imported scripts previously designed and the destination, so the and simulated by Ning and Sun in [3]. The scripts presented a fake RREQ message did not systematic analysis of different misuses to the routing message of reach the NM monitoring the the AODV protocol. The scripts were adjusted to run the IDS. destination node The IDS was able to detect all routing message misuses except MF NI 8 The IDS detected all Faked for the RREQ message active forge misuse aimed at consuming RREQ the network resource. In all cases the attack was detected as a MF RI 8 The IDS detected all Faked violation to one of the AODV protocol specifications. From the RREQ messages results obtained the following can be concluded MF RC 8 The IDS detected all Faked RREQ messages 1. The IDS can effectively detect IP spoofing AF RD 8 The IDS failed in one script 2. Forging the hop count in the RREP messages can be because there was no route immediately detected and confirmed available between the source 3. Forging destination sequence number in the RREP and the destination, so the messages can only be detected and confirmed when the fake RREQ message did not NM receive the RREP message issued by the reach the NM monitoring the destination destination node AF NI 8 The IDS detected all Faked 4. Forging the RREQ ID in RREQ messages can be RREQ messages immediately detected and confirmed AF RI 1 The IDS detected the Faked Future work includes adapting the IDS to accommodate for RREQ messages node moving out of the cluster in which they are registered AF RC 8 The IDS failed to detect this as well as adopting other performance measures to evaluate attack due to the relaxation of the IDS performance. the assumption that all MAC and IP address pairs are to be registered in all NM nodes 6. REFERENCES [1] Karchirski, O. and Guha, R., “Effective Intrusion Detection Table 4. IDS Response for RREP Attacks Using Multiple Sensors in Wireless Ad Hoc Networks”, In Attack Misuse No. IDS Response Proceedings of the 36th Hawaii International Conference on type Goal script System Sciences (HICSS’03) p.57. FR RD 8 IDS detected all faked RREP [2] Tseng, C., Y., Balasubramanyam, P., Ko, C., messages due to inconsistent Limprasittiporn, R., Rowe, J., Levitt, K., “A Specification- RREP field values based Intrusion Detection System for AODV”, Proceedings FR RI 8 IDS failed to detect the faked of the 1st ACM workshop on Security of ad hoc and sensor RREP message twice since networks, 2003, pp. 125-134. the destination node did not http://portal.acm.org/citation.cfm?id=986858.986876 issue a reply so the NM was not able to decide on the fake [3] Ning, P., Sun, K., “How to Misuse AODV: A case Study of value of sequence number Insider Attacks against Mobile Ad-hoc Routing Protocols”, used to conduct the attack. In Proceedings of the 4th Annual IEEE Information FR NI 8 IDS detected all faked RREP Assurance Workshop, pp. 60-67, West Point, June 2003 messages due to inconsistent [4] Perkins, C. E., Royer, E. M., “Ad hoc On-Demand Distance RREP field values Vector Routing”, Proceedings of the 2nd IEEE Workshop AF RD 8 IDS failed twice since the on Mobile Computing Systems and Applications, New dest node is out of range Orleans, LA, February 1999, pp. 90-100. AF RI 8 All attacks were detected AF NI 8 All attacks were detected AF RC 1 The attack was detected 36