Paper Title (use style: paper title) - ER Publications



BlackHole Attack Prevention in AODV-Based MANET

Ume-Hani Syed1, Dr.Arif Iqbal Umar2, Fahad Khurshid3

123Department of Information Technology

123Hazara University, Mansehra, Pakistan

1hani_syed01@, 2arifiqbalumar@, 3fahadkhurshid@hu.edu.pk

Abstract: Ad hoc On-demand Distance Vector (AODV) is a reactive wireless ad hoc routing protocol. An effective routing protocol as it has minimum overhead of control messages management as well as efficient and fast reaction in response of these control messages. On the other hand, AODV also has various security limitations and exposed to different internal and external attacks. Black Hole attack is an internal attack, a malicious node presenting itself to be legitimate in that network hence intercepts all the traffic which was routed to the destination. In order to avoid and detect Black Hole attack, intense studies have been made to make AODV safe but there are still several security concerns that need to be tackled. In this paper a method is proposed to enhance the route discovery process in AODV-enabled Mobile Ad hoc Networks (MANETs). Proposed method attempts to improve AODV route discovery process against Black Hole attack by secure entry in Routing Table and tries to provide better performance than various methods proposed before.

Keywords: AODV, Route Discovery, Sequence number, TTL, Black hole Attack.

Introduction

Mobile adhoc network (MANET) has several mobile nodes connected together regardless of any central access point. It has limited computing power, bandwidth, nodes battery and distance etc. MANET has an edge over conventional wired network as easy to deploy anytime anywhere. It has several mobile nodes depending upon the type of application. Mobile nodes are free to move and join, as of mobility the topology is dynamic in nature.

MANET uses different routing protocols for route establishment. It uses proactive and reactive protocols. In proactive routing protocols it periodically exchanges routing information with mobiles nodes. Unlike proactive routing protocols, reactive protocols exchange route information only when needed. Some of the protocols are hybrid in nature as they have the best of both [25].

AODV is reactive routing protocol for MANET; it uses sequence numbers for route freshness. AODV is a loop free, supports bulk of mobile hosts and self starting. AODV uses sequence numbers for the freshness of route. There are many possible attacks in AODV based MANET some of them are internal and some of them are external. Internal attacks are hard to detect Black hole attack is one of them. In Black Hole attack malicious node enters the network and claims that it has the shortest path to the destination hence intercepts all of the data. It exploits one of the best features of AODV that is the shortest path to the destination in a very sophisticated way. It is hard to prevent Black hole attack by any single solution. In this paper a mechanism is proposed to prevent Black Hole attack which improves AODV route discovery mechanism. An additional table i.e rrep_table is used to store more than one RREP’s as in [19]. To prevent Black Hole attack we have introduced an algorithm which ignores RREP from black hole node and selects one of legitimate RREP from rrep_table and store it into routing table. This will result a secure and legitimate route establishment between the nodes in AODV based MANET.

The rest of paper is ordered as follows. Section-II presents background information about AODV routing protocol, related terminologies, awareness of problem, and how the black hole attack is performed on AODV. Section-III reviews the several solutions to black hole attacks. In section-IV proposed solution against black hole attack is presented. Section-V shows the robustness of proposed solution. Finally section-VI concludes the paper.

Background

1 Ad hoc on-demand Distance Vector

The Ad hoc On Demand Distance Vector is a routing protocol and it is designed for ad hoc networks. It has the capability of multi-cast and uni-cast routing. AODV establishes and maintains the routes between mobile nodes when it is demanded.

1 Route Discovery Process: AODV establishes routes via broadcasting a RREQ. If a source node needs to establish a route towards destination and it does not have route before, then the source node broadcasts a RREQ in AODV network. Intermediate nodes get the control packet and build the route in routing table back to the source node after freshen the information. RREQ also contains the broadcast ID, IP address of source node, present sequence number of destination node and Time-To-Live value. TTL field in RREQ message allows control over how long the RREQ is propagated for every retry[19]. Primarily Route Requests are sent with small TTL value to bound their dissemination. If Route Reply is not received within small traversal time(TTL), then try larger time for RREQ traversal in network. A RREP may send by a node after receiving RREQ if:

1 it has a route towards destination with sequence number equal to or greater than the sequence number in received RREQ, or

2 it is the destination node.

In above case, node uni-casts a RREP backward to source node. If not then RREQ is broadcasted further. AODV nodes maintain the broadcast ID and IP address of source node's RREQ. A RREQ is discarded and do not forwarded if it is processed before.

[pic]

1. Route discovery process in AODV[19]

Source node starts forwarding data packets to the destination when it receives RREP. Source node do update its Routing Table used for destination if:

3 it receives a RREP later with small hop count but same sequence number, or

4 a RREP having greater sequence number.

Source node accepts the RREP with highest sequence number if multiple RREPs are received.

2 Role of Sequence Numbers: Incrementing sequence numbers of participating nodes contribute to keep the information fresh and route is established through those nodes which have highest sequence number. When a node starts a route discovery process or responds to RREQ control packet, destination node renews its sequence number.

2 BlackHole Attack

A kind of denial of service attack. It occurs when a malicious node sends a RREP with a very high sequence number after receiving RREQ. Intermediate nodes in Black Hole attack environment will consider it freshest route and send information via malicious node.

3 Understanding of Problem

Issue arises when a malicious node enters into the network and acts as black hole node. It can disrupts the network activity and degrade its performance. The black hole node gets the RREQ and immediately sends a RREP with exponentially high sequence number state that it has freshest and shortest route towards destination. Source node may receive this RREP before other RREPs. It may also receive this RREP after other RREPs but before legitimate RREP. Source node establishes the route through black hole node and start data transmission. Black hole node drops all the data packets instead of sending to destination node. As a result, Black hole nodes become the reason of failure in the routing protocols.

Literature Review

In this section, previously published techniques and their limitations are discussed related to Black Hole attack in AODV MANET. There have been many works done against Black Hole attack in AODV-enabled MANETs.

Example of work done by R. Yerneni and Anil Sarje in [1], proposed an additional control packet MREQ(Modified Request) carries random number after RREP. Random number does not upgrade at any node but malicious node replies another highest random number and detected. In this scheme, each time random number generation consumes memory and time. In case of suspicion, double times wait for RREP, then again send MREQ and wait for MREP, find duplicate random number then establish path.

K. Lakshmi et al. in [23], sources node maintains an additional Request-Reply (RR) Table stores all incoming RREPs with Dest.Seq.no. and nodeID for specified time. Unusual highest Seq.No.'s are considered as malicious node MID. From remaining choose one as legitimate route. Proposed solution fails when remaining entries also contain any malicious node. Also incoming RREP's waiting time limit is not defined.

L. Himral et al. in [11] proposed the algorithm by modifying the work of [23]. Waiting time steps are eliminated for incoming RREP packets at source node so no time limit is defined in proposed algorithm for RREP storage in Route-Reply Table.

In [3], R. Dr. S. Tamilarasan Modified the work of [23] and [11] in their proposed algorithm by carrying same approach but adding time limit for RREP storage. Idea fails when remaining entries also contain any malicious node.

Vishnu K and A.J. Paul in [21], selects Back Bone Nodes (BBN) those have powerful battery and range. New entering nodes request to nearest BBN for assigning the unique IP addresses for themselves. Not assigned IP addresses are saved as Restricted IP (RIP) at BBN. If RREP from destination received by source node and also from RIP then dummy packet is sent to monitor the performance of that packet. Loss of dummy packet shows the IP address of replying node is suspected. Much processing overhead by selection of BBN, assigning IP address to each node, separating RIP, propagation and monitoring of dummy packets, then Black/gray hole detection process.

In [5] Rajesh et al. proposed Opinion AODV(OAODV) algorithm. OREQ packet is sent after RREP received with the RREP source ID. After receiving OREP source node, the ratio of Request Weight to Reply Weight is calculated for each other. If more replies forwarded than request then Black hole attack is detected. This scheme also failed if legitimate nearest nodes may send more and instant replies.

In [12] J. Sen et al. proposed algorithm and introduced two concepts: DRI table has two fields, information on routing packet 'through' and 'from' the node. “Cross check” checks the reliability of Next Hop Node(NHN) and Intermediate Node(IN) with the help of DRI fields. Here cross checking for node reliability causes processing delay. Maintaining DRI table at each node is considerable bandwidth loss in MANET.

Herminder and Shweta in [13], adopts a feedback method to avoid transmission through black hole nodes. The packets coming at the immediate previous nodes to black-nodes are propagated back to the sender. Sender follows an another safer route toward destination. But packets propagate back to sender from malicious nodes, it consumes time and increases processing overhead.

M. Raza and S. Irfan in [18] proposed FRIMM (Forced Routing Information Modification Model). Network is constructed as centralized network using server, Access Points(AP) and nodes. Nodes cannot communicate directly with server without AP. If AP does not get response from node requesting for server then there is a black hole node. AP scan the network and detect communication between legal and black hole node and also fetches the malicious node's MAC address and throw to server. Server attacks malicious node by DoS jamming and divert the affected node’s traffic towards AP. This approach also has limitations as it is costly approach and wastage of hardware resources. Extra burden on access point causes communication delay between server and access point.

Ms. Nidhi et. al in [8] proposed two solutions to make network safe from black hole attack. First solution guarantees to locate a secure route towards the destination node but the data packet will never be sent if no shared hops or nodes between the routes. other solution gives a reliable and fast action to find malicious replies but two additional table maintenance for stale Seq.nos. is additional overhead.

By Kitisak O et al. in [14], modified ETX(Expected Transmission count) named Secure ETX(SETX) proposed to counter Black hole attack. Scheme does not stop cooperative black hole attacks.

Ms. Sonali and Mrs. S. R. Chaudhary in [16] proposed a novel mechanism as an improvement in TWOACK scheme i.e. E-TWOACK. It senses the suspicious node by using detection system and reduces the misbehavior detection overhead while the detection efficiency gets increased. But a safe link is considered as suspicious because acknowledgement packets can also be dropped due to traffic congestion.

In [17], Po-Chun et. al proposed BDSR (Baited-Black-hole DSR) avoids and senses the black hole attack depend on assembling protection design of proactive and reactive in MANET. Proactive detection must execute at initial stage of each routing, it is extra processing overhead if there is large infrastructure and no malicious node present in the network. In proposed approach of Latha T et al. in [30], store RREPs in Route Reply Table (CRRT) and check for any repeated next hop node in reply path. Select that path if yes. Otherwise select random route. But in case of random selection of route from CRRT, here are pretty high chances to route data packet through black hole node.

As in related work of [6,10,22,25 and 29], store all incoming RREPs in a table. Additional check is implemented to find exponentially high RREP sequence number that is considered as Black hole node. Alarm packets are generated to all participating nodes and add Black hole nodes in malicious list at each node and eliminated from any routing process. In these approaches, generation of ALARM packet to each node consumes memory. Routing Table lookup and updating the Routing Table slightly increase the routing overhead.

In [2,4,9 and 26], Trust models/Trust values is another approach used for selection of secure route. Trust level of participant nodes in AODV is measured by using duplicate trust value control messages. Trust value increments by 1 if duplicate control message is received from neighboring node and decreases by 1 if duplicate control message is not received in Time-To-Live(TTL). Drawback of Trust models is handling overhead of duplicate control message if large infrastructure. Trusted table maintenance at each node is memory consumption. Waiting and analyzing for highest trust value for establishing route from source to destination. Collecting trust values, monitoring and maintaining between upper bound and lower bound causes delay and overhead.

Intrusion detection techniques in [15,20 and 24]are also used for black hole attack solution. Audit data collection at each node and detects intrusion on the basis of audit data. But audit data collection at each node causes bandwidth consumption and has additional management overhead.

Related work of [7,27 and 28], uses additional control packets sent for route verification from source to destination after RREP control packet is received. If Seq.No. of RREP is greater than and equals to Seq.No. of additional RREP packet then there exists black hole node. Generation and handling of these control packets cause bandwidth consumption and causes extra processing overhead.

In our base paper [19], K.A. Jalil, Z. Ahmad and J. Manan proposed ERDA (Enhanced Route Discovery AODV) scheme, RREP packets are stores in RREP_Table. Proposed solution accepts the second RREP for route selection and putting first RREP in malicious node table. Proposed solution fails if second RREP also came from any malicious node.

Existing approaches have their limitations and are less helpful in order to avoid and detect black hole nodes or routes in AODV-based MANET. Our solution selects a secure and shortest path from source to destination by using proposed algorithms. Proposed solution does not detect and eliminate black hole nodes from the network but avoids malicious routes towards destination for data transmission.

Proposed Solution

In order to overcome high processing overhead and latency by using cryptography and for the purpose of secure Routing Table entry, a robust and improved method is proposed to overcome the existing limitations.

Proposed method introduces a counter at each participating node in ad hoc network. Which counts how many times a node has been visited. Initially counter = 0.

4 Steps Ivolved in Proposed Solution

1 When destination node 'D' is approached first time at count=1, destination node replies back to source node via two same RREP messages using Algorithm1. Thus two same entries in RREP_Table for source node 'S'.

2 After first approach to 'D' (at counter= 2 to 4), single RREP message is sent to source node and entered in RREP table.

3 RREP table has to be updated at each RREP message.

4 The RREP_Table is checked using Algorithm2 and matches entries with each other until two(2) entries with same nodeID and same Dest.Seq.no. is found in maximum TTL (Time-To-Live) defined for route discovery process.

5 RREP_Table stops updating until two same entries found.

6 Discard all other entries in RREP_Table except both same entries.

7 Routing Table for source node 'S' is then updated with RREP_Table entry.

8 Once Routing Table at source node is updated, flush the RREP_Table to avoid memory consumption.

[pic]

[pic]

2. Secure routing table update in AODV

5 Algorithm1—PseudoCode for RREP_Table Entry

1. set count = 0

2. count = 1 to 4

//Destination node will send back no more than 4 RREPs

3. if { (D receives RREQ) than

// D is Destination node

4. increment count by 1 and store n ( RREQ.seq.no.

// Store RREQ sequence no. in variable n

5. If (D_count = 1 and RREQ.seq.no.=n) than

//Check whether the stored RREQ sequence no at count 1 is similar or not, if yes then step6

6. { RREP_Table = rrep from Destination;

// Reply to source node and update RREP Table with two similar entries by step7

7. Replicate packet of step6 and Go to step4; }

8. else RREP_Table = rrep from Destination; }}

// Update RREP_Table with RREP received at source node.

9. if (data packet received by the destination) than

// When data transmitted from source to destination

10. Reset count to 0

// Reset count until count reaches the limit 4 for further RREQ processing

11. Else if (RREQ.seq.no.!= n) than

//When a fresh Route discovery process is initiated by source node and received at destination node

12. Go to step4

6 Algorithm2—Pseudo Code for Legitimate RREP Entry in Routing Table

1. Compare each row with its next row by using Two Dimensional Array.

2. Continue until two consecutive rows entries are similar.

3. Update Routing_Table with one of that similar entries in a row.

4. Stop Comparison.

5. Discard RREP_Table entries for avoiding memory consumption.

7 Algorithm2—Actual Comparison Code for RREP_Table Entries

a[][] is two dimensional array for comparison of rows in Routing Table and [i] represents rows and [j] represents columns.

[pic]

Analysis of Proposed Scheme

Main contribution of our proposed algorithms is to keep record of those RREPs in routing table only sent by destination node. RREPs from black hole attack is stored in an additional table and discarded later.

Our proposed scheme does not use any additional check, which increases the communication cost and causes much processing overhead. For instance; threshold or peak value check before each data packet transmission. Our solution does not use local or global IDS systems, additional supportive hardware resources, additional control and ACK packets. Consequently; a secure, shortest and legitimate route is established between mobile node with less communication cost and processing delay.

Conclusion

Paper presented security limitations in existing Route Discovery process of AODV in black hole attack environment. Routing Table is falsely updated with malicious route entry if it has greatest sequence number then route reply from legitimate nodes is rejected. After studying related work done and their limitations against black hole attack in AODV, a robust method is proposed to overcome the limitations in existing work and make secure Routing Table update that won't allow malicious route entry in Routing Table. Hence secure, shortest and legitimate route is established from source to destination.

Future work could be to perform simulation and present simulated results for analyzing the effectiveness of proposed solution.

References

1] R. Yerneni and A.K Sarje. "Enhancing performance of AODV against Black Hole attack," in Proceedings of the CUBE Conference International Information Technology, 2012, pp. 857-862.

2] A.P. Renold and R. Parthasarathy. "Source based Trusted AODV Routing Protocol for Mobile Ad hoc Networks," in Proceedings of the International Conference on Advances in Computing, Communications and Informatics(ICACCI), 2012, pp. 271-1275.

3] Dr. S. Tamilarasan. " Securing AODV Routing Protocol from Black Hole Attack." International Journal of Computer Science and Telecommunications(IJCST), vol. 3, no. 7, pp. 52-56, Jul. 2012.

4] Y.K. Jain and N.K. Sharma. "Secure Trust Based Dynamic Source Routing in MANETs." International Journal of Scientific & Engineering Research(IJSER), vol. 3, no. 8, pp. 1-7, Aug. 2012.

5] R. Yerneni and A.K. Sarje. " Secure AODV protocol to mitigate Black hole attack in Mobile Ad hoc Networks," in Proceedings of IEEE Third International Conference on Computing Communication & Networking Technologies (ICCCNT), 2012, pp. 1-5.

6] R.H. Jhaveri, S.J. Patel and D.C. Jinwala. "A Novel Approach for GrayHole and BlackHole Attacks in Mobile Ad-hoc Networks," in Proceedings of IEEE Second International Conference on Advanced Computing & Communication Technologies, 2012, pp. 556-560.

7] P.K. Singh and G. Sharma. "An Efficient Prevention of Black Hole Problem in AODV Routing Protocol in MANET," in Proceedings of IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications, 2012, pp. 902-906.

8] Ms. N. Sharma and Mr. A. Sharma. " The Black-hole node attack in MANET," in Proceedings of IEEE Second International Conference on Advanced Computing & Communication Technologies, 2012, pp. 546-550.

9] Y. khamayseh, A. Bader, W. Mardini, and M.B. Yasein. "A New Protocol for Detecting Black Hole Nodes in Ad Hoc Networks." International Journal of Communication Networks and Information Security(IJCNIS), vol. 3, no. 1, pp. 36-47, Apr. 2011.

10] M.A. Obaida et al. "AODV Robust (AODVR): An Analytic Approach to Shield Ad-hoc Networks from Black Holes." International Journal of Advanced Computer Science and Applications(IJACSA), vol. 2, no. 8, pp. 97-102, 2011.

11] L. Himral et al. "Preventing AODV Routing Protocol from Black Hole Attack." International Journal of Engineering Science and Technology (IJEST), vol. 3, no. 5, pp. 3927-3932, May 2011.

12] J. Sen, S. Koilakonda and A. Ukil. " A Mechanism for Detection of Cooperative Black Hole Attack in Mobile Ad Hoc Networks," in Proceedings of IEEE Second International Conference on Intelligent Systems, Modelling and Simulation, 2011, pp. 338-343.

13] H. Singh and Shweta. "AN APPROACH FOR DETECTION AND REMOVAL OF BLACK HOLE IN MANETS." International Journal of Research in IT & Management(IJRIM), vol. 1, no. 2, pp. 78-87, Jun. 2011.

14] K. Osathanunkul and N. Zhang. "A Countermeasure to Black Hole Attacks in Mobile Ad hoc Networks," in Proceedings of IEEE International Conference on Networking, Sensing and Control, 2011, pp. 508-513.

15] M. Abdelhaq, S. Serhan, R. Alsaqour and R. Hassan. "A Local Intrusion Detection Routing Security over MANET Network," in Proceedings of IEEE International Conference on Electrical Engineering and Informatics, 2011, pp. 1-6.

16] Ms. S.P. Botkar and Mrs. S.R. Chaudhary. "An Enhanced Intrusion detection System using Adaptive Acknowledgment based Algorithm," in Proceedings of IEEE World Congress on Information and Communication Technologies, 2011, pp. 606-611.

17] P.C. Tsou et al. "Developing a BDSR Scheme to Avoid Black Hole Attack Based on Proactive and Reactive Architecture in MANETs," in Proceedings of ICACT, 2011, pp. 755-760.

18] M. Raza and S.I. Hyder. "A Forced Routing Information Modification Model for Preventing Black Hole Attacks in Wireless Ad Hoc Network," in Proceedings of IEEE 9th International Bhurban Conference on Applied Sciences & Technology (IBCAST), 2011, pp. 418-422.

19] K.A. Jalil, Z. Ahmad, J.L.A. Manan. "Securing Routing Table Update in AODV Routing Protocol," in Proceedings of IEEE Conference on Open Systems (ICOS), 2011, pp. 116-121.

20] Y.F. Alem and Z.C. Xuan. "Preventing Black Hole Attack in Mobile Ad-hoc Networks Using Anomaly Detection," in Proceedings of IEEE 2nd International Conference on Future Computer and Communication, vol. 3, 2010, pp. 672-676.

21] A.J. Paul and V. Kumar. "Detection and Removal of Cooperative Black/Gray hole attack in Mobile ADHOC Networks." International Journal of Computer Applications, vol. 1, no. 22, pp. 38-42, 2010.

22] N. Mistry, D.C. Jinwala, and M. Zaveri. "Improving AODV Protocol against Blackhole Attacks," in proc. of IMECS, 2010, pp. 1034-1039.

23] K. Lakshmi et al. " Modified AODV Protocol against Blackhole Attacks in MANET." International Journal of Engineering and Technology , vol. 2, no. 6, pp. 444-449, 2010.

24] M.Y. Su, K.L. Chiang and W.C. Liao. "Mitigation of Black-Hole Nodes in Mobile Ad Hoc Networks," in proceedings of IEEE International Symposium on Parallel and Distributed Processing with Applications, 2010, pp. 162-167.

25] P. N. Raj and P.B. Swadas. " Dpraodv: A Dyanamic Learning System Against Blackhole Attack in Aodv Based Manet." The International Journal of Computer Science Issues(IJCSI), vol.1, pp. 54-59, Aug. 2009.

26] M. Medadian, M.H. Yektaie and A.M. Rahmani. "Combat with Black Hole Attack in AODV routing protocol in MANET," in Proceedings of IEEE First Asian Himalayas International(AH-ICI), 2009, pp. 1-5.

27] S. Lu, L. Li, K.Y. Lam and L. Jia. "SAODV: A MANET Routing Protocol that can Withstand Black Hole Attack," in Proceedings of IEEE International Conference on Computational Intelligence and Security, 2009, pp. 421-425.

28] X.Y. Zhang, Y. Sekiya and Y. Wakahara. " Proposal of a Method to Detect Black Hole Attack in MANET," in Proceedings of IEEE International Symposium on Autonomous Decentralized Systems(ISADS), 2009, pp. 1-6.

29] L. Tamilselvan and Dr. V. Sankaranarayanan. "Prevention of Co-operative Black Hole Attack in MANET." The Journal of Networks, vol. 3, no. 5, pp. 13-20, May 2008.

30] L. Tamilselvan and Dr.V. Sankaranarayanan. "Prevention of Blackhole Attack in MANET," in Proceedings of IEEE The 2nd International Conference on Wireless Broadband and Ultra Wideband Communications, 2007, pp. 21.

31]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download