Handbook of information and communication security: Part 2

MobileAdHocNetworkRouting 21 MelodyMohandJiLi Contents 21.1 Chapter Overview. . .. . . . .. . . . .. . . . .. . . . .. 407 21.2 One-LayerReputationSystemsforMANET Routing.. . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 408 21.2.1 Watchdog and Pathrater . . . . . . . . . . . . . 408 21.2.2 CORE: A Collaborative Reputation Mechanism. . . . . . . . . . . . . . . . . . . . . . . . . 409 21.2.3 OCEAN: Observation-Based Cooperation Enforcement in Ad Hoc Networks. . . . . . . . . . . . . . . . . 409 21.2.4 SORI – Secure and Objective Reputation-Based Incentive Scheme for Ad Hoc Networks . . . . . . . . . . . . . . . . 410 21.2.5 LARS – Locally Aware Reputation System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412 21.2.6 Comparison of One-Layer Reputation Systems . . . . . . . . . . . . . . . . . 412 21.3 Two-LayerReputation Systems(with Trust) 412 21.3.1 CONFIDANT – Cooperation of Nodes: Fairness in Dynamic Ad Hoc Networks . . . . . . . . . . . . . . . . . . . 412 21.3.2 TAODV – Trusted AODV . . . . . . . . . . . 413 21.3.3 SAFE: Securing Packet Forwarding in Ad Hoc Networks. . . . . . . . . . . . . . . . . 414 21.3.4 Cooperative and Reliable Packet Forwarding on Top of AODV . . . . . . . . 415 21.3.5 Comparison of Two-Layer Reputation Systems . . . . . . . . . . . . . . . . . 416 21.4 Limitationsof Reputation Systems in MANETs . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 417 21.4.1 Limitations of Reputation and Trust Systems . . . . . . . . . . . . . . . . . . . 417 21.4.2 Limitations in Cooperation Monitoring . . . . . . . . . . 417 21.5 Conclusion and FutureDirections . . .. . . . .. 419 References .. . .. . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 419 T he Authors . .. . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 420 Instant deployment without relying on an exist-ing infrastructure makes mobile ad hoc networks (MANETs) an attractive choice for many dynamic situations. However, such flexibility comes with aconsequence–thesenetworksaremuchmorevul-nerable to attacks. Authentication and encryption are traditional protection mechanisms, yet they are ineffective against attacks such as selfish nodes and malicious packet dropping. Recently, reputation systems have been proposed to enforce cooperation among nodes. These systems have provided useful countermeasures and have been successful in deal-ing with selfish and malicious nodes. T his chapter presents a survey of the major contributions in this field. We also discuss the limitations of these ap-proaches and suggest possible solutions and future directions. 21.1 ChapterOverview A MANET is a temporarynetwork formed by wire-less mobile hosts without a presetup infrastructure. Unlike a traditional infrastructure-based wireless network where each host routes packets through an access point or a mobile router, in a MANET each host routespacketsand communicatesdirectly with its neighbors.Since MANETsoffer much more flex-ibility than traditional wireless networks, and wire-less deviceshave become common in all computers, demand for them and potential applications have been rapidly increasing. The major advantages in-clude low cost, simple network maintenance, and convenient service coverage. These benefits, however, come with a cost. Ow-ing to the lack of control of other nodes in the net- Peter Stavroulakis, Mark Stamp (Eds. , Handbook of Information and Communication Security 407 © Springer 2010 408 work, selfishness and other misbehaviors are pos-sible and easy. One of the main challenges is en-suring security and reliability in these dynamic and versatile networks. One approach is using a public key infrastructure to prevent access to nodes that are not trusted, but this central authority approach reduces the ad hoc nature of the network. Another approach is the use of reputation systems, which at-temptstodetectmisbehaviors,suchasselfishnodes, maliciouspacketdropping,spreadingfalseinforma-tion,anddenial ofservice(DoS) attacks.Themisbe-havingnodesarethenpunishedorrejectedfromthe network [21.1–3]. In reputation systems, network nodes monitor the behavior of neighbor nodes. They also com-pute and keep trackof the reputation values of their neighbors, and respond to each node (in packet forwarding or routing) according to its reputation. Some reputation systems are based only on direct observations; these are often called one-layer repu-tation systems. Others rely on both direct observa-tion and indirect (second-hand) information from a reported reputation value, misbehavior, alarm, or warning message. Some of these also include a trust mechanismthat evaluatesthe trustworthinessof in-direct information; these systems are often called two-layer reputation systems. Thischapterprovides a surveyon keyreputation systems for MANET routing. Section 21.2 presents one-layer reputation systems, Sect. 21.3 describes two-layer reputation systems, Sect. 21.4 discusses limitations of these systems, and, finally, Sect. 21.5 concludes the chapter. 21.2 One-LayerReputationSystems forMANETRouting indexnetwork routingIn this section, we describe one-layer reputation systems, i.e., systems that evaluate only the reputation of the base system, i.e., of network functionalities such as packet for-warding and routing. Reputations may be derived only from direct observations, or from both direct and indirect (second-hand) observations. These systems, however,do not have an explicit scheme to compute the trust of second-hand reputation values (whichwill be coveredin Sect.21.3).The reputation systems discussed in this section, in chronolog-ical order, are Watchdog and Pathrater [21.4], CORE [21.5], OCEAN [21.6], SORI [21.7], and 21 MobileAdHocNetworkRouting LARS [21.1]. All of them are either explicitly de-signed for or demonstrated over Dynamic Source Routing (DSR) [21.8]. 21.2.1 WatchdogandPathrater The scheme based on the Watchdog and the Pathrater, proposed by Lai et al. [21.4] was one of the earliest methods done on reputation sys-tems for MANETs. The two are tools proposed as extensions of the DSR to improve throughput in MANET in the presence of misbehaving nodes. In the proposed system, a Watchdogis used toidentify misbehaving nodes, whereas a Pathrater helps to avoid these nodes in the routing protocol. Specif-ically, the Watchdog method detects misbehaving nodes through overhearing; each node maintains a buffer of recently sent packets and compares each overheardpacketwith thepacketin thebuffertosee if there is a match. If a packet remains in the buffer for too long, the Watchdog suspects that the node that keeps the packet (instead of forwarding it) is misbehaving and increases its failure tally. If the failure tally exceeds a threshold, the Watchdog de-termines that the node is misbehaving and notifies the source node. ThePathratertoolisrunbyeachnodeinthenet-work.It allowsasourcenodetocombinetheknowl-edge of misbehaving nodes with link reliability data to choose the route that is most likely to be reliable. Each node maintains a “reliability” rating for every other network node it knows about. The “path met-ric” of a path is calculated by averaging all the node ratings in the path. A source node then chooses the most reliable path (the one with the highest average node rating) and avoids any node that is misbehav-ing. ThesetwotoolssignificantlyimproveDSR[21.8] as they can detect misbehavior at the forwarding level (network layer) instead of only at the link level (datalinklayer).TheyalsoenabletheDSRtochoose the more reliable path and to avoid misbehaving nodes. However, they have some limitations. The authors of [21.4] note that the Watchdog technique may not detect a misbehaving node in the presence of ambiguous collisions, receiver collisions, limited transmission power, false misbehavior, collusion, and partial packet dropping (see Sect. 21.5 for more discussions). Also, the Pathrater tool relies on the sourcenodetoknowtheentirepath;itcantherefore 21.2 One-Layer ReputationSystemsfor MANETRouting be applied only on source-based routing such as DSR [21.8]. 21.2.2 CORE:ACollaborative ReputationMechanism CORE is another highly well known, pioneer work in reputation systems for MANETs. Proposed by Michiardi and Molva [21.5], the system aims to solve the selfish node problem. Like Watchdog and Pathrater, CORE is also based on DSR and only evaluates reputations in the base system (i.e., the network routing and forwarding mechanisms). For each node, routes are prioritized on the basis of global reputations associated with neighbors. The global reputation is a combination of three kinds of reputation that are evaluatedby a node. These three reputations are subjective, indirect, and functional reputations. T he subjective reputation is calculated on the basis of a node’sdirect observation.The indi-rect reputation is the second-hand information that is received by the node via a reply message. Note that a reply message could be ROUTE REPLY for routing, or an ACK packet for data forwarding. The subjective and indirect reputations are evaluated for each base system function, such as routing and data forwarding. Finally, the functional reputation is defined as the sum of the subjective and indirect reputations on a specific function (such as packet forwarding function, routing function). The global reputation is then calculated as the sum of func-tional reputations with a weight assigned to each function. CORE uses some watchdog (WD) mechanism to detect misbehaving nodes. In each node, there is a WD associated with each function. Whenever a networknode needstomonitorthecorrectbehav-ior (correct function execution) of a neighbornode, it triggers a WD specific to the function. The WD stores an expected result in the buffer for each re-quest. If the expectation is met, the WD will delete the entry for the target node and the reputations of all the related nodes will be increased on the basis of the list in the reply message (the reply message contains a list of all the nodes that successfully par-ticipatedintheservice).Iftheexpectationisnotmet or a time-out occurs,the WD will decrease the sub-jective reputation of the target node in the reputa-tion table. In the CORE system, only positive infor-mation is sent over the network in reply messages. 409 It can therefore eliminate the DoS attacks caused by spreading negative information over the network. The advantages of the CORE system are that it is a simple scheme, easy to implement, and is not sensitive to the resource. CORE uses a reply mes-sage(RREP)totransmitthesecond-handreputation information. Thus, no extra message is introduced by the reputation system. When there is no inter-action from a node, the node’s reputation is grad-ually decreased, which encourages nodes to be co-operative.There are a few drawbackstoCORE. One of them is that CORE is designed to solve mainly the problem of selfish nodes; thus, it is not very efficient at dealing with other malicious problems. Moreover, CORE is a single-layer reputation sys-tem where first-handand second-hand information carry the same weight. It does not evaluate trust-worthiness before accepting second-hand informa-tion. As such, the system cannot prevent the risk of spreading incorrect second-hand information. Fur-thermore, in CORE only positive information is ex-changed between nodes. Therefore, half of the ca-pability, the part dedicated to carrying negative in-formation, is lost. In addition, reputations are only evaluatedamongone-hopneighbors,yetapathusu-ally contains multiple hops. In consequence, the re-sult maynotbepreferredor optimized for the entire path. Finally, although the original paper only de-scribed the system without any performance eval-uation, some later simulation experiments done by Carruthers and Nikolaidis have shown that CORE is most efficient in static networks; its effectiveness dropped to50% under low mobility, and it is almost noneffective in high mobility networks [21.9]. 21.2.3 OCEAN:Observation-Based CooperationEnforcement inAdHocNetworks OCEAN was proposed by Bansal and Baker [21.6], from the same group who proposed Watchdogs and Pathraters. It is a reputation system that was proposed after the CORE (described above) and the CONFIDANT (Cooperation Of Nodes: Fairness In Dynamic Ad Hoc Networks; to be described in Sect. 21.3.1) systems. The authors of OCEAN ob-served that indirect reputations (i.e., second-hand information) could easily be exploited by lying and giving false alarms, and that second-hand informa-tion required a node to maintain trust relationships 410 withothernodes.TheythereforeproposedOCEAN, a simple, direct-reputation-based system, aimed at avoiding any trust relationship, and at evaluating how well this simple approach can perform. OCEAN considers only direct observations. Based on and expanded from their early work 21 MobileAdHocNetworkRouting it suffered from poor network performance. These evaluation results showed that second-hand repu-tations with the corresponding trust mechanisms were still necessary in highly mobile environments, which some MANET applications desire. (Watchdog and Pathrater), the system consists of five modules: NeighborWatch, RouteRanker, Rank-Based Routing, Malicious Traffic Rejection, and Second Chance Mechanism. T he NeighborWatch SchemeforAdHocNetworks module is similar to the Watchdog tool [21.4]; it observesthebehaviorofitsneighbornodesbykeep- SORI,proposedbyHeetal.,focusedonselfishnodes ing track of whether each node correctly forwards every packet. Feedback from these forwarding events(both positive andnegative)isthen fed tothe RouteRanker. The RouteRanker module maintains ratings of all the neighbor nodes. In particular, it keeps a faulty node list that includes all the mis-behaving nodes. A route’s ranking as good or bad (a binary classification) depends on whether the next hop is in the faulty node list. The Rank-Based Routing module proposes adding a dynamic field in the DSR RREQ (Route Request packet), named avoid-list, which consists of a list of faulty nodes that the node wishes to avoid. The Malicious Traffic Rejection module rejects all the traffic from nodes which it considers misleading (depending on the feedback fromNeighborWatch).Finally,the Second Chance Mechanism allows a node that was once considered misleading (i.e, it was in the faulty node list) to be removed from the list on the basis of a time-out period of inactivity. To assess the performance of this direct-observation-only approach,OCEAN was compared with defenselessnodesandwith areputationsystem called SEC-HAND that was intendedto correspond to a reputation system with alarm messages repre-senting second-hand reputation information. After their application onto DSR, the results of the sim-ulation found that OCEAN significantly improved network performance as compared with defenseless nodes in the presence of selfish and misleading nodes. OCEAN and SEC-HAND performed simi-larly in static and slow mobile networks. However, SEC-HAND performed better for highly mobile networks than OCEAN since the second-hand rep-utation messages spread the bad news faster, thus allowing SEC-HAND to punish and avoid the mis-leading nodes. OCEAN, on the other hand, failed to punish the misleading nodes as severely and still permitted those nodes to route packets. Therefore, (thatdonotforwardpackets)[21.7].Theirpaperdid not address malicious nodes (such as ones sending outfalsereputations).Theauthorsnotedthattheac-tions taken, such as dropping selfish nodes’ packets solely on the basis of one node’s own observation of itsneighbornodes,couldnot effectivelypunishself-ishnodes.Theythereforeproposedthatallthenodes share the reputation information and punish selfish nodes together. In SORI, each node keeps a list of neighbor nodes discovered from overheard packets, including the numberofpacketsrequestedforforwarding andthe number of packets forwarded. The local evaluation record includes two entries, the ratio of the num-ber of packets forwarded and the number of pack-ets requested,and the confidence (equal tothe num-ber of packets forwarded). This reputation is propa-gated to all the one-hopneighbors. The overall eval-uation record iscomputedusing the local evaluation record, reported reputation values, and credibility, whichisbased on howmanypacketshavebeen suc-cessfully forwarded. Ifthe valueofthe overallevalu-ation record for a node is below a certain threshold, all the requests from that (selfish) node are dropped with probability (1 − combined overall evaluation record − δ), where δ is the margin value necessary to avoid a mutual retaliation situation. This is a very interesting, unique aspect of SORI, since punish-ment of misbehaving nodes is gradual, as opposed to the approach taken by most other schemes: set-ting a hard threshold point beyond which no inter-action with the node is made. In this way, SORI ac-tively encouragespacket forwarding and disciplines selfish behaviors. The scheme was evaluated by a simulation over DSR. SORI effectively gave an incentive to well-behaved nodes and punished selfish nodes in terms of throughput differentiation. Furthermore, the scheme also incurred no more than 8% of commu- 21.2 One-Layer ReputationSystemsfor MANETRouting 411 Table21.1 Comparison of one-layer reputation schemes Reputation systems Watchdog and Pathrater (over DSR) [21.4] CORE (over DSR) [21.5] OCEAN (over DSR) [21.6] SORI (over DSR) [21.7] LARS (over DSR) [21.1] Observations Observes if neighbor nodes forward packets. Uses direct observations only Observes packet forwarding and routing functions. Uses both direct and indirect observations Observes if neighbor nodes forward packets. Uses direct observations only Observes if neighbor nodes forward packets Observes if neighbor nodes forward packets. Uses direct observations only Reputation computation method Starts 0.5. Increased for nodes in actively used paths. Selfish node is immediately ranked −100, and the source node is notified Starts null. Increased on observed good behavior and reported positive reputation. Decreases on directly observed misbehavior. Global reputation includes subjective, indirect, and function reputations Nodes start with high reputation and the reputation decreases on directly observed misbehavior Increase/decrease on packet forwarding/drop. Reputation rating uses the rate of forwarded packets, the number of reported reputations, and the total number of forwarded packets Reputation decreases on packet drop and increases on packet forwarding. Selfish flag is set when reputation falls below a threshold, and a warning message is broadcast to k-hop neighbors Implicit evaluation of second-hand information Not applicable (no indirect reputation) Smaller weight given to indirect reputation. Indirect reputation can only be positive Not applicable (no indirect reputation) Use confidence, which is the total number of packets forwarded. Assumes no reporting of false reputations Take action upon a warning only when receiving a warning from at least m neighbors Strengths and other notes Likely the earliest work on reputation for MANET routing. Only source node is notified of selfish nodes so communication overhead is small. Avoids selfish nodes in path selection Flexible weights for functional areas. Reputation communication is only among one-hop neighbors so overhead is limited. Avoids selfish nodes in route discovery Simple but effective approach in many cases. Very small overhead since no indirect observations. Second chance mechanism overcomes transient failures. Avoids selfish nodes in path selection; rejects routing of selfish nodes Selfish nodes are punished probabilistically – their packets are dropped with probability inversely proportional to their reputations Simple. Resilient to (m −1)false accusations. Very high overhead owing to the need to broadcast warnings to all k-hop neighbors DSR Dynamic Source Routing, MANET mobile ad hoc network ... - tailieumienphi.vn