Gimer Cervera

Michel Barbeau
email: barbeau@scs.carleton.ca

Evangelos Kranakis
email: kranakis@scs.carleton.ca

Joaquin Garcia-Alfaro
email: joaquin.garcia-alfaro@acm.org

Security Issues in Link State Routing Protocols for MANETs

In link state routing networks, every node has to construct a topological map through the generation and exchange of routing information. Nevertheless, if a node misbehaves then the connectivity in the network is compromised. The proactive Optimized Link State Routing (OLSR) protocol has been designed exclusively for Mobile Ad Hoc Networks (MANETs). The core of the protocol is the selection of Multipoint Relays (MPRs) as an improved flooding mechanism for distributing link state information. This mechanism limits the size and number of control traffic messages. As for several other routing protocols for MANETs, OLSR does not include security measures in its original design. Besides, OLSR has been extended to address a number of problems in MANETs. For example, Hierarchical OLSR (HOLSR) has been proposed to address scalability and Multipath OLSR (MP-OLSR) to address fault tolerance. However, these OLSR extensions can be affected either by inheriting or adding new security threats. In this chapter, we present a review of security issues and countermeasures in link state routing protocols for MANETs.

Introduction

The design of a secure and efficient routing protocol for Mobile Adhoc Networks (MANETs) is a challenging problem. Routing protocols proposed for MANETs assume a trusted and cooperative environment. Therefore, several mechanisms to enhance security in MANETs have been proposed. The proactive Optimized Link State Routing (OLSR) [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF] protocol has been designed exclusively for MANETs. The core of the protocol is the concept of Multipoint Relay (MPR). A valid MPR set, is defined as a subset of one-hop neighbors, such that all two-hop neighbors are covered through at least one node in the MPR set. In OLSR, every node has to select a valid MPR set. This mechanism allows to flood the network with control traffic information. OLSR comprises Hello and Topology Control (TC) messages. Every node periodically generates Hello messages. Within each Hello message a node reports its one-hop neighbors. Receiver nodes learn about its one and two hop neighbors. TC messages are used to discover nodes at more than two hops away. TC messages are generated and retransmitted exclusively by the MPRs. Unlike other link state routing protocols (e.g., OSPF [START_REF] Moy | Open Shortest Path First (OSPF) version 2, RFC2328[END_REF]), the MPRs report partial link state information. Therefore, the MPR mechanism reduces the size and amount of control traffic information flooded in the network.

OLSR is defined in RFC 3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF]. A second version of the protocol, i.e., OL-SRv2, is presented by Clausen et al. as an Internet-Draft in [START_REF] Clausen | Optimized link state routing protocol version 2 (OLSRv2), RFC3666 ,Work in progress. Project Hipercom, INRIA, Internet Draft[END_REF]. OLSRv2 implements the same basic mechanisms and algorithms for distributing control traffic (i.e., MPR-based flooding). As many other routing protocols for MANETs, OLSR and OLSRv2 are not secure by design. The selection of the MPRs and exchange of topology control information are important vulnerability targets. In this context, a malicious node is defined as a node that interrupts the flooding of control traffic information or does not obey the rules of the protocol. The terms: malicious, misbehaving, attacker and intruder are equivalent. Therefore, several authors proposed countermeasures to prevent or mitigate security threats in link state routing protocols for MANETs. For instance, in [START_REF] Adjih | Securing the OLSR routing protocol with or without compromised nodes in the network[END_REF][START_REF] Raffo | Security schemes for the OLSR protocol for ad hoc networks[END_REF][START_REF] Raffo | Securing OLSR using node locations[END_REF], Raffo et al., reviewed vulnerabilities in OLSR. In [START_REF] Clausen | Vulnerability analysis of the optimized link state routing protocol version 2 (OLSRv2)[END_REF][START_REF] Clausen | Digital signatures for admittance control in the optimized link state routing protocol version 2[END_REF], Clausen et al., studied security risk in OLSRv2. The authors proposed cryptographic mechanisms to enhance: integrity, confidentiality, reliability and service availability (fault-tolerance). Countermeasures to secure OLSR can be classified in two categories: cryptographic mechanisms to avoid impersonation or replay attacks, and Intrusion Detection Systems (IDS) [START_REF] Adjih | Securing the OLSR routing protocol with or without compromised nodes in the network[END_REF] to prevent altered information from an authenticated node. Nevertheless, cryptographic models are challenging because in MANETs there is no centralized authority. The network performance drops due to additional computation. Reputation models or IDS mechanisms are designed to detect malicious behavior. Nevertheless, they increase the network traffic and need time to detect misbehaving nodes. Additionally, when a malicious behavior is detected, an efficient method to report untrusted nodes is needed. Moreover, flooding disruption [START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF] attacks can be perpetrated in networks with cryptographic capabilities. For instance, if a node refuses to retransmit TC messages on behalf of other nodes (e.g., to save energy), then the connectivity is disrupted.

In this chapter, we present a review of security issues in OLSR networks, existing solutions and our proposed countermeasures. In addition to OLSR, we review the Hierarchical OLSR (HOLSR) [START_REF] Villasenor-Gonzalez | HOLSR: A hierarchical proactive routing mechanism for mobile ad hoc networks[END_REF] protocol proposed by Villasenor et al. to address scalability and the Multipath OLSR (MP-OLSR) [START_REF] Yi | Simulation and performance analysis of MP-OLSR for mobile ad hoc networks[END_REF][START_REF] Yi | Implementation of multipath and multiple description coding in OLSR[END_REF][START_REF] Yi | Multipath OLSR: Simulation and Testbed[END_REF][START_REF] Yi | Multipath optimized link state routing for mobile ad hoc networks[END_REF], proposed by Yi et al., to address security, fault tolerance and reliability. This chapter is based on the work presented in [START_REF] Cervera | Mitigation of topology control attacks in OLSR networks[END_REF][START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF][START_REF] Cervera | Preventing the Cluster Formation Attack Against the Hierarchical OLSR Protocol: Invited Talk[END_REF]. In [START_REF] Cervera | Mitigation of topology control attacks in OLSR networks[END_REF], we analyzed the effect of control traffic attacks in OLSR networks and the selection of MPR sets with additional coverage to miti-gate their effect. The MPR selection with additional coverage is presented in RFC 3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF], we name it k-Covered-MPR selection. However, additional coverage reduces the performance of the network due to additional control traffic information (i.e., TC messages). We proposed a k-Robust-MPR selection. In a k-Robust-MPR selection a node selects, when possible, k + 1 disjoint MPR sets to guarantee that even if k of the selected MPR sets become invalid, the remaining set is still a valid MPR set. Our proposed MPR selection offers equivalent protection against control traffic attacks but reducing the overhead generated by additional control traffic information.

In [START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF], we presented a taxonomy of flooding disruption attacks and their effect in HOLSR networks. HOLSR uses TC messages for intra-cluster communications and implements Hierarchical TC (HTC) messages for inter-cluster communications. HOLSR implements the MPR flooding mechanism for distributing control traffic information. HTC messages are flooded exclusively by the MPRs. Therefore, the inter-cluster communications are also affected by flooding disruption attacks. In [START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF], we proposed to mitigate the effect of the attacks against HTC messages by selecting MPR sets with additional coverage (i.e., k-Robust-MPR and k-Covered-MPR selections). Additionally, the cluster formation phase in hierarchical OLSR networks can be disturbed. In [START_REF] Cervera | Preventing the Cluster Formation Attack Against the Hierarchical OLSR Protocol: Invited Talk[END_REF], we presented an algorithm based on hash chains to enforce the cluster formation phase in HOLSR networks. In HOLSR, Cluster ID Announcement (CID) messages are implemented to organize the network in clusters. A misbehaving node may maliciously alter mutable fields (e.g., hop count) in CID messages to unbalance the distribution of nodes in clusters. Our solution allows a node to detect and discard invalid CID messages. Our algorithm can be implemented in other hierarchical approaches that use messages with mutable fields to organize the network in clusters. Finally, we analyze vulnerabilities in multipath OLSR-based networks. MP-OLSR is based on the MPR flooding mechanism to distribute control traffic information in the network. The construction of multiple paths in MP-OLSR has two phases: topology discovery and route computation. In the first phase, the nodes obtain information about the network topology through the exchange of Hello and TC messages. In the second phase, the nodes compute multiple paths to a particular destination in the network based on the information gathered during the first phase. These two phases are affected by flooding disruption attacks. Additionally, MPRs report partial link state information. Therefore, MP-OLSR nodes only acquire a partial view of the network. We analyze how the construction of multiple paths in MP-OLSR networks is affected by flooding disruption attacks and incomplete view of the network topology.

We describe different link state routing protocols for MANETs, their specific vulnerabilities and proposed countermeasures. The chapter is organized as follows: in Section 2, we review the OLSR protocol, flooding disruption attacks and related work. HOLSR, other OLSR-based hierarchical approaches and their vulnerabilities are described in Section 3, MP-OLSR and its security risks are presented in Section 4 and finally, Section 5 concludes the chapter. 2 Optimized Link State Routing (OLSR)

This section presents an overview of the OLSR protocol and its vulnerabilities. OLSR is a proactive routing protocol designed for MANETs. The core of the protocol is the selection, by every node, of MPRs among their one-hop neighbors. The MPR set is selected such that all two-hop neighbors are reachable through at least one MPR. Fig. 1 compares the MPR mechanism and classical flooding. In Fig. 1(a), control traffic information is retransmitted by all the one-hop neighbors. In Fig. 1(b), control traffic information is retransmitted exclusively by the MPRs. This optimization improves the network performance by reducing the size and number of control traffic messages in the network. OLSR is defined in RFC3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF]. A second version of the protocol, i.e., OLSRv2, is presented by Clausen et al. in an Internet-Draft [START_REF] Clausen | Optimized link state routing protocol version 2 (OLSRv2), RFC3666 ,Work in progress. Project Hipercom, INRIA, Internet Draft[END_REF]. OLSRv2 uses and extends: the MANET Neighbor Discovery Protocol (NHDP) [START_REF] Clausen | I-D: MANET Neighborhood Discovery Protocol (NHDP)[END_REF], RFC5444 -Generalized MANET Packet/Message Format [START_REF] Clausen | RFC5444: Generalized mobile ad hoc network (manet) packet/message format[END_REF], RFC5497 -Representing Multi-Value Time in MANETs [START_REF] Clausen | RFC5497: Representing Multi-Value Time in Mobile Ad Hoc Networks (MANETs)[END_REF] and RFC5148 -Jitter Considerations in MANETs [START_REF] Clausen | RFC5148: Jitter Considerations in Mobile Ad Hoc Networks (MANETs)[END_REF] (optional). These protocols were all originally created as parts of OLSRv2, but have been specified separately for wider use. OLSRv2 retains the same basic mechanisms and algorithms for distributing control traffic (i.e., MPR-based flooding) but provides a more efficient signaling framework and implements some message simplifications.

OLSR nodes flood the network with link state information messages. The link state information is constructed by every node and involves periodically sending Hello and TC messages. This information is used to determine the best path to every destination in the network. Due to the proactive nature, the routes are immediately available when needed. The OLSR protocol is based on hop by hop routing, i.e., each routing table lists, for each reachable destination, the address of the next node along the path to that destination. To construct a topology map, every node implements a topology discovery mechanism leveraging the periodic exchange of control traffic messages. Topology discovery includes: link sensing, neighbor detection and topology sensing. In the first phase, every node populates its local link information base (link set) and establishes communication with their symmetric neighbors, i.e., nodes with bidirectional communication. This phase is exclusively concerned with the OLSR interface addresses and ability to exchange packets between such OLSR interfaces. During the neighbor detection phase, every node populates its neighborhood information base (i.e., one-hop and two-hop neighbor set). The link sensing and neighbor detection phases are based on the periodic exchange of Hello messages. Hello messages are solely transmitted to one-hop neighbors. In every Hello message, the nodes report their one-hop neighbors. This information allows every node to construct and maintain neighbor tables, as well as to select its MPR set. In the neighbor table, each node records the information about the one-hop neighbor link status (i.e., unidirectional, bidirectional or MPR), with this information every node builds its MPR selector set, i.e., the neighbors that selected that node as their MPR. OLSR detects and eliminates duplicate messages. OLSR keeps track of recently received messages by using a duplicate table. Therefore, when a message has been received and included in the duplicate table, the payload is not examined and the message is automatically discarded.

Topology sensing is achieved through the exchange of TC messages. TC messages are generated and retransmitted exclusively by the MPRs. TC messages have a Time-to-Live (TTL) field that is decremented every time an MPR retransmits the message. These messages allow each node to construct its topology table and to declare its MPR selector set. A TC message contains the MPR selector set of its originator. A node that has an empty MPR selector set does not send or retransmit any TC message. An MPR forwards a message only if it comes from a node in its MPR selector set (i.e., a source-dependant mechanism). This forwarding algorithm is defined in RFC 3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF]. Using the information from TC messages, each node maintains a topology table where each entry consists of:

• an identifier of a possible destination, i.e., an MPR selector in a TC message,

• an identifier of a last-hop node to that destination, i.e., the originator of the TC message, and • an MPR selector set sequence number [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF].

It implies that a possible destination (i.e., an MPR selector) can be reached through the originator of the TC message. If there is an entry in the topology table whose last-hop address corresponds to the originator of a new TC message and Fig. 2 Example of an OLSR network.

the MPR selector set sequence number is greater than the sequence number in the received message, then the new message is discarded. Routing tables are constructed using the information from the one-hop neighbor, two-hop neighbor and topology tables.

OLSR implements two optional messages: Multiple Interface Declaration (MID) and Host and Network Association (HNA). They are exclusively retransmitted by the MPRs following the default forwarding algorithm defined in RFC 3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF]. MID messages are used to declare the presence of multiple interfaces on a node. HNA messages are employed to inject external routing information into an OLSR network and provide connectivity to nodes with non-OLSR interfaces (e.g., Internet). MID messages are implemented in a network with multiple interface nodes. Additional information is necessary in order to map interface addresses to main addresses. In OLSR, the main address is defined as the OLSR interface address. A node with multiple interfaces must generate periodically MID messages announcing all its interfaces to other nodes in the network. Thus, every node in an OLSR network will associate multiple interfaces to a node's main address. Nodes with just one interface do not generate MID messages and their main address is the OLSR interface address. A node with several interfaces, where only one of them is participating in an OLSR network must not generate MID messages. Upon receiving a MID message, the information is stored in an Interface Association table. This information is used to construct the routing tables. When a node misbehaves and does not retransmit TC, HNA or MID messages, the proper construction of the routing tables is compromised. Table 1 presents all the messages implemented in OLSR. In summary, the network topology discovery process is performed as follows:

1. First, every node periodically generates Hello messages to advertise itself and establish bidirectional links with its one-hop neighbors. Hello messages are not retransmitted. Fig. 2 shows an example of an OLSR network. Node a includes nodes b, c and f in its one-hop neighbor set after exchanging Hello messages and establishing bidirectional links. 2. In subsequent Hello messages, every node reports its one-hop neighborhood. Receiver nodes identify their two-hop neighbors and compute their MPR set. In Fig. 2, nodes d, e, g and h are included in node a's two-hop neighbor table. Node a selects nodes b and f as its MPRs. Nodes a, b, f and g are selected as MPRs.

3. Nodes report their MPR set within their following Hello messages. If the receiver node was selected as an MPR, then it includes the sender node in its selector set, e.g., node b includes a in its selector set. 4. Nodes with a non empty selector set periodically generate TC messages advertising all nodes within their selector set. TC messages are retransmitted exclusively by the MPRs. To reach nodes more than two hops away, node a depends on the TC messages generated by all the MPRs. For instance, node g must periodically generate TC messages advertising its selector set, i.e., nodes f and i. TC messages generated by node g are retransmitted exclusively by nodes f , a and b. 5. When a node receives a TC message, it includes the contained information in its topology table. In Fig.

Related Work

As many other routing protocols for MANETs, OLSR is not secure by design. Vulnerabilities in OLSR have been studied extensively. For instance, in [START_REF] Adjih | Securing the OLSR routing protocol with or without compromised nodes in the network[END_REF], Adjih et al. present security risks in the OLSR protocol and countermeasures based on cryptographic mechanisms to secure the protocol with or without compromised nodes in the network. The authors claim that an efficient securing mechanism should ensure the network integrity even when the network is subject to attacks that interrupt the connectivity. In [START_REF] Clausen | Vulnerability analysis of the optimized link state routing protocol version 2 (OLSRv2)[END_REF][START_REF] Herberg | Security Issues in the Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] Clausen and Herberg review security issues in OLSRv2.

The authors analyze the basic algorithms that constitute the OLSRv2, and identify possible vulnerabilities and attacks.

Several authors have contributed with cryptographic mechanisms to secure OLSR. Cryptographic mechanism are proposed to enforce: integrity, authentication and confidentiality. Thus, public-key encryption is used for confidentiality, digital signature for integrity of the messages and digital certificates for authentication. However, the implementation of a Public Key Infrastructure (PKI) in MANETs is difficult due to the lack of a central authority (CA). Additionally, the efficient distribution of public and private keys is a challenging problem. Timestamps are implemented with digital signatures to assure the freshness of the message. However, time synchronization is difficult to achieve particularly in MANETs.

According to Adjih et al. [START_REF] Adjih | Securing the OLSR routing protocol with or without compromised nodes in the network[END_REF], a cryptographic capable node is a node that has received valid keys to sign and verify messages. A misbehaving node can be also a cryptographic capable node. For example, in Fig. 2, node g may decide not to forward TC messages to node i or refuse to select an MPR set. In both cases, the connectivity of the network is compromised. Intrusion Detection Systems (IDS) are implemented to analyze malicious behavior in the network. However, once a misbehaving node has been detected, an efficient reputation model is needed to convey to other nodes the results observed by the IDS. In this chapter, we focus on attacks that prevent a node to acquire a complete network topology map. These attacks can be launched even in networks with cryptographic capabilities. In Section 2.2, we review them more precisely. In the following, we present some contributions to secure the OLSR protocol. We classify them in cryptographic mechanisms and IDS systems.

Cryptographic Mechanisms

In this section, we describe proposed solution based on cryptographic mechanisms. In [START_REF] Clausen | Digital signatures for admittance control in the optimized link state routing protocol version 2[END_REF], Clausen et al. present a digital signature mechanism for authentication and authorization in OLSRv2. The authors introduce the concept of admittance control for OLSRv2 networks and suggest a security extension based on digital signatures. They compare several standard digital signature algorithms such as: RSA, DSA, ECDSA and HMAC. The goal is to enable trusted nodes and to disable non-trusted nodes from participating in the control message exchange between routers, thereby providing a mode-of-operation similar to traditional mechanism employed for preserving network integrity in routed networks. Additionally, a performance study of the propose extension is presented to quantify the impact of increased control traffic overhead and increased message generation as well as processing time. The authors observed that HMAC requires significantly less time than ECDSA, DSA and RSA for generating a message signature. For the verification of a message signature, HMAC likewise spends substantially less time than ECDSA and DSA, whereas RSA is close to HMAC. Verification of RSA signatures has much greater overhead but is faster than both ECDSA and DSA.

In [START_REF] Raffo | Securing OLSR using node locations[END_REF], Raffo et al., examined security issues related to the OLSR protocol, and enumerate a number of possible attacks against the integrity of the OLSR routing infrastructure. In particular, authors study attacks when a mechanism of digitally signed routing messages is deployed and an attacker may have taken control over trusted nodes. Their solution is based on inclusion of the geographical position of the sending node in control messages and on evaluation of reliability of links; this is accomplished using a GPS device and a directional antenna embedded in each node. Signatures with timestamps are sufficient to thwart attacks such as incorrect traffic generation and incorrect traffic relaying, when only legitimate nodes can sign control packets. Adding the node location in signature messages allows the network to avoid wormhole attacks and false messages generated by misbehaving nodes.

Raffo also presented in his Ph.D. thesis [START_REF] Raffo | Security schemes for the OLSR protocol for ad hoc networks[END_REF], a classification of possible attacks in OLSR networks. The author proposed a security architecture based on digital signatures. Additionally, the author proposed other techniques such as: reuse of previous topology information to validate the actual link state, cross-check of advertised routing control data with the node's geographical position, and intra-network misbehavior detection and elimination via flow coherence control or passive listening. Countermeasures in case of compromised nodes are also considered. Furthermore, the author assesses practical problems concerning the choice of a suitable symmetric or asymmetric cipher, alternatives for the algorithm of cryptographic key distribution, and the selection of a method for signature time stamping. In summary, the author presented an outline of different signature algorithms. The author suggested the study and design of better cryptographic algorithms, i.e., algorithms that use a smaller signature size to reduce computation complexity would increase the suitability of his proposed OLSR security architectures.

In [START_REF] Khakpour | WATCHMAN: An overlay distributed AAA architecture for mobile ad hoc networks[END_REF], Khakpour et al., aboarded the access control problem in MANETs. The authors proposed a hierarchical distributed AAA (Authentication, Authorization, and Accounting) architecture for proactive link state routing protocols. This proposal contains a lightweight and secure design of an overlay authentication and authorization paradigm for mobile nodes as well as a reliable accounting system to enable operators to charge nodes based on their connection time. The authors also suggest a hierarchical distributed AAA server architecture with a resource and location aware election mechanism. Moreover, this proposal mitigates the OLSR security issues and eventually defines a node priority-based quality of service. The design of the architecture targets a minimum signaling overhead as well as calculation cost. In fact, different tasks are fairly distributed among distributed AAA servers. The calculation cost and overhead signaling is trivial compared to OLSR signaling and routing computations.

Intrusion Detection Systems

In this section we describe proposed solutions based on Intrusion Detection Systems (IDS). In [START_REF] Abdellaoui | SU-OLSR: A new solution to thwart attacks against the OLSR protocol[END_REF], Abdellaoui and Robert, proposed the SU-OLSR protocol (SU for suspicious) to prevent attacks against against OLSR-based routing protocols. In SU-OLSR the MPR selection is based on the trustworthiness of nodes. A malicious node might force its neighbors to choose it as an MPR node. Hence, a node should never select a neighbor as an MPR node if it behaves suspiciously and shows spe-cific characteristics which would influence the MPR selection. Authors also show that to compute optimal paths, the optimality should not depend only on the length of a path but also whether or not it goes through fully or partially trusted MPR nodes. In [START_REF] Adnane | Autonomic trust reasoning enables misbehavior detection in OLSR[END_REF], Adnane et al., proposed a trust based reasoning for OLSR that allows each node to correlate information provided by Hello, TC messages and data packets information so as to validate its local view of the global network topology. In their approach, when an inconsistency is detected between any received messages and its local view, the reasoning node is able to identify the compromised route. Their approach does not require any modification of the bare OLSR, but only the integration of the trust reasoning model on each node. Wu et al. present in [START_REF] Wu | A survey of attacks and countermeasures in mobile ad hoc networks[END_REF] an overview of attacks according to the protocol layers, security attributes and mechanisms. Additionally, they present preventive approaches following the order of the layered protocol layers and an overview of reactive approaches based on IDS mechanism for MANET as a second line of defense to thwart attacks. [START_REF] Vilela | A feedback reputation mechanism to secure the optimized link state routing protocol[END_REF] a feedback reputation mechanism which assesses the integrity of routing control traffic by correlating local routing data with feedback messages sent by the receivers of control traffic. Based on this assessment, misbehaving nodes are shown to be reliably detected and can be adequately punished in terms of their ability to communicate through the network. In [START_REF] Cuppens | Property based intrusion detection to secure OLSR[END_REF], Cuppens et al. investigate the use of Aspect-Oriented Programming (AOP) in MANETs to provide availability issues in proactive routing protocols. Their approach is based on a detection-reaction process. Authors formally describe normal and incorrect node behaviors to derive security properties using AOP. The proposed algorithm verifies if those security properties are violated. If they are, then the detector node sends to its neighborhood the detection information to avoid choosing the intruder as part of valid paths to be constructed. A node chooses valid paths based on the reputation of other nodes.

Vilela et al., present in

Security Issues in OLSR Networks

In this section, we describe security attacks against the topology map acquisition process in OLSR networks. According to Herberg and Clausen [START_REF] Herberg | Security Issues in the Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF], in OLSR networks every node must acquire and maintain a routing table that effectively reflects the network topology. Additionally, the routing tables constructed by every node must converge, i.e., all nodes must have an identical topology map. Therefore, the target of a misbehaving node may be that the nodes in the network (a) build inconsistent routing tables that do not reflect the accurate network topology, or (b) acquire an incomplete topology map. In link state routing protocols, some attacks can be launched even in networks with either cryptographic capabilities or IDS mechanisms implemented, e.g., a misbehaving node refuses to compute a valid MPR set. The exchange of control traffic information and the MPR selection process are important vulnerability targets. In this chapter, we focus on flooding disruption attacks [START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF], Fig. 3. In this kind of attacks, the target of an attacker is to disrupt the topology map acquisition process by disturbing the flooding of valid control traffic information. In [START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF], we presented a taxonomy of these attacks and countermeasures based on the selection of the MPR sets with additional coverage. The taxonomy we presented in [START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF] divides the attacks in two categories:

• Incorrect MPR Selection: in this category, the malicious node either selects an incomplete MPR set or forces other nodes to compute an incorrect MPR set. To launch the attack, the malicious node may either generate control traffic information with a false identity (i.e., identity spoofing) or report inexistent links to other nodes (i.e., link spoofing). As a consequence, the affected node computes an invalid MPR set, i.e., some of its two-hop neighbors are not covered through at least one node in its MPR set. • Incorrect Relaying: in this category, the malicious node does not generate control traffic information (i.e., TC, MID or HNA messages) or does not forward valid messages on behalf of other nodes, e.g., selfish attack. In a variation of the attack, a malicious node may report incomplete information or eliminate some information reported by other nodes, e.g., slanderer behavior. Additionally, the misbehaving node can maliciously alter mutable fields in the messages before forwarding them, e.g., hop limit attack.

Fig. 3 summarizes flooding disruption attacks in OLSR networks and the mechanisms used to perform them. In the sequel, we present these security threats in more detail. In Section 2.3 we present countermeasures to mitigate the effect of the attacks.

Incorrect MPR Selection

In this section, we describe vulnerabilities against the MPR selection process and some techniques to launch the attacks, i.e., link or identity spoofing.

Identity Spoofing. The identity spoofing attack [START_REF] Herberg | Security Issues in the Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] is performed by a malicious node pretending to be a different node in the network. The goal of the attack is to report false information about nodes one or two-hops away in order to maliciously affect the MPR selection process. Fig. 4(a) illustrates an example where node x spoofs the identity of node d and broadcasts Hello message advertising a valid link with node c. Then, node a receives Hello messages from node x indicating that node d has links with nodes c and f. In this case, node a selects incorrectly node d as the only element in its MPR set. In consequence, node c is unreachable through the MPR set and never receives TC messages. Fig. 4(b), presents an example where the attacker affects the MPR selection of a node at distance two hops. The malicious node x spoofs the identity of node c, i.e., nodes f and e generate Hello messages advertising node c as a one-hop neighbor. From the point of view of node a, nodes b, e, f and d have node c as a one-hop neighbor. As a result of the attack, node a can select incorrectly nodes f or e as an MPR. In this case, nodes b and d do not forward control traffic information to node c because they are not included in the MPR set.

Link Spoofing. The link spoofing attack [START_REF] Herberg | Security Issues in the Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] is performed by a malicious node that reports an inexistent link to other nodes in the network. The objective of the attacker is to manipulate the information about the nodes one or two hops away and be selected as part of the MPR set. Once the malicious node has been selected as an MPR, it neither generates nor forwards control traffic information. The flooding disruption attack due to link spoofing is illustrated in Fig. 5(a). In this example, node x spoofs links to nodes e and c. Node x sends Hello messages and looks like the best option to be selected as an MPR for node a. Node a receives the Hello messages from node x and computes incorrectly its MPR set by selecting node x as the only element to reach nodes e and c. Thus, all routing information do not reach nodes two hops away from node a. A variant of the attack can be performed by a misbehaving node either reporting a link to an inexistent node (i.e. a phantom node) or selecting an invalid MPR set. For instance, in Fig. 5(b), node a is forced to select node x as an MPR because is the only node to reach the inexistent node w. In the second case, a malicious node may disrupt the flooding of topology control information by misbehaving during the MPR selection process. Fig. 6(a) illustrates the attack. Node x wants to be selected as the only MPR of node a. Then, it spoofs a link to node g and generates Hello messages announcing node g as a one-hop neighbor and its only MPR. From the perspective of node a, nodes c and g can be reached through node x. Then, node x is the best candidate to be selected as an MPR for node a. Thus, node x receives and forwards TC messages from node a. However, those messages never reach node d because any one-hop neighbor of node x retransmits the messages. This attack exploits the source dependent requirement in OLSR to forward control traffic information. In this case, for nodes a, b, c and e, node x is not included in their selector table and they never forward any message from node x.

Incorrect Relaying

A misbehaving node can disrupt the integrity of the network by either incorrectly generating or relaying control traffic information on behalf of other nodes. Consider x in Fig. 6(a) as a misbehaving node. Node x wants to be selected as the only MPR of node a. Then, it spoofs a link to node g and generates Hello messages announcing node g as a one-hop neighbor. From the perspective of node a, nodes c and g can be reached through node x. Thus, node x is selected by node a as its only MPR and might perform the following incorrect behaviors:

• Selfish behavior. The attack is performed by a node that misbehaves and neither generates nor forwards TC messages. To increase the effectiveness of the attack, the malicious node might establish false links to other nodes in the network and force its one-hop neighbors to select it as their MPR. Fig. 6(a) illustrates an example where node x has been selected by node a as an MPR but it does not relay control traffic on behalf of other nodes. As a result, node d does not receive con- trol traffic information from node a. Note that in an OLSR network, the attacker can choose not to forward any particular message, i.e., TC, MID or HNA messages.

• Slanderer behavior. Due to message size limitations, an MPR may report only a partial list of elements in its selector set, i.e., an MPR may generate more than one TC message to report its entire selector set. A receiver can not know if an MPR reports its entire selector set in more than one TC message. The information gathered from the TC messages is accumulated in its topology table and is only eliminated when the validity time has expired. Thus, a misbehaving node can always generate TC messages without reporting all nodes in its selector table claiming that the size of the messages is not enough to include all nodes in its selector table. As a result, if node x generates TC messages without including node a, node d is not able to compute a path to node a.

• Hop Limit attack. A malicious node x may drastically decrease the hop limit (TTL value) when forwarding a TC message, e.g., setting the hop limit equal to zero. This reduces the scope of retransmitting the message. The attack can be performed by a malicious node that has not been selected as an MPR. For instance, in Fig. 6(b), a control message is forwarded by node a and received by both nodes x and b. Previously node b was selected by node a as its MPR. However node x forwards the message without any delay or jitter such that its retransmission is received before the valid message from b arrives. Before forwarding, it reduces the hop limit of the message. The affected node, node c, processes the message and mark it as already received, ignoring future valid copies from b. Thus, the message with a very low hop limit will not reach the whole network.

Countermeasures

In an OLSR network, the MPR selection reduces at minimum the overhead generated by control traffic messages, if every node selects its MPR set with the following conditions:

• the MPR set is kept at minimum, • an MPR retransmits control traffic messages if and only if the sender node is included in its selector table, and • only partial link state information is transmitted, i.e., an MPR reports only links with its selector nodes.

Nevertheless, we can loosen up the previous restriction in order to offer a higher level of security while maintaining a tradeoff between security and performance. In [START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF], we present strategies based on the selection of MPRs with additional coverage, a non source-dependent forwarding mechanism and redundant information. The selection of MPRs with additional coverage is defined in RFC3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF], we named it in [START_REF] Cervera | Mitigation of topology control attacks in OLSR networks[END_REF] the k-Covered-MPR selection. In this approach, every node selects its MPR set such that any two-hop neighbor is covered by k one-hop neighbors, whenever possible. However, the overhead generated by the excessive number of TC messages reduces the performance of the network. This problem is addressed with the k-Robust-MPR selection presented in [START_REF] Cervera | Mitigation of topology control attacks in OLSR networks[END_REF], which balances security and traffic overhead. In the k-Robust-MPR selection, every node computes an MPR set that is composed of, at most, k+1 disjoint sets, i.e., every two-hop node is covered, when possible, by k+1 disjoint sets of one-hop neighbors. In a k-Robust-MPR selection, it is possible to discard a maximum of k invalid MPR sets and all nodes two hops away are still covered by the remaining elements in the MPR set. In a non sourcedependant mechanism the MPRs retransmit all TC messages even if the sender node is not part of their selector set. Redundant information is possible by tunning the TC redundancy parameter. This parameter is defined in the RFC3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF] and has three options:

• MPRs report their selector table when TC redundancy is equal to zero, • MPRs report their selector table and MPRs when TC redundancy is equal to one, and • MPRs report their one-hop neighbors when TC redundancy is equal to two.

Advertising redundant information increases the size of the TC messages, but more links are advertised. In [START_REF] Cervera | Mitigation of topology control attacks in OLSR networks[END_REF], we compared both k-Covered-MPR and k-Robust-MPR selections in the presence of misbehaving nodes. We measured the number of nodes with complete routing tables after the execution of the OLSR protocol. Our experiments showed that our k-Robust-MPR selection reduces the amount of traffic generated by the k-Covered-MPR selection, and offered equivalent protection against control traffic attacks. Our k-Robust-MPR selection increased the performance ratio of the number of nodes with complete routing tables over the number of topology control messages.

Hierarchical OLSR

In this section, we present the Hierarchical OLSR (HOLSR) protocol and its vulnerabilities. By nature, MANETs are formed of heterogeneous nodes that can join the network following an unpredictable pattern. Furthermore, scalability is a problem in MANETs. In [START_REF] Villasenor-Gonzalez | HOLSR: A hierarchical proactive routing mechanism for mobile ad hoc networks[END_REF], Villasenor-Gonzalez et al. define scalability as the capacity of the network to adjust or to maintain its performance even if the number of nodes increases. OLSR is a flat routing protocol and its performance degrades when the number of nodes increases due to a higher number of topology control messages propagated through the network. The MPR mechanism is local and therefore very scalable. However, the diffusion of link state information by all the nodes is less scalable. Hence, OLSR's performance decreases in large ad hoc networks. Additionally, OLSR does not differentiate the capabilities of the nodes and, in consequence, does not exploit nodes with higher capabilities. HOLSR is an approach designed to improve the scalability of the OLSR protocol in large-scale heterogeneous networks.

The main improvements are a reduction of topology control traffic and an efficient use of high capacity nodes. HOLSR organizes the network in hierarchical clusters. This architecture reduces the routing complexity, i.e., in case a link is broken only nodes inside the same cluster have to recalculate their routing table while nodes in other clusters are not affected. Nodes are organized according to their capacities. The network architecture is illustrated in Fig. 7. At level 1, we have low-capability nodes with a single interface, represented by circles. Nodes at the topology level 2 are equipped with up to two wireless interfaces, designated by squares. Nodes at level 2 employ one interface to communicate with nodes at level 1. Nodes at level 3, designated by triangles, represent high-capacity nodes with up to three wireless interfaces to communicate with nodes at every level. Thus, in Fig. 7, node F3 represents node F's interface at level 3. The only restriction for every node at levels 2 and 3 is that they have at least one interface to communicate with nodes at its levels. For instance, in Fig. 7 nodes F2 and F3 represent node F's interfaces at levels 2 and 3 respectively. Nodes A1 and A2 represent node A's interfaces to establishes communication with nodes at levels 1 and 2 respectively. Node D2 has only one interface and can just communicate with nodes at level 2. In the example, the notation used to name the clusters reflects the level of the cluster and cluster head, e.g., C1.A1 means that the cluster is at level 1 and cluster head is node A1, which is node A's interface at level 1. HOLSR allows formation of multiple clusters. Unlike OLSR, HOLSR nodes can exchange Hello and TC messages exclusively within each cluster. This constraint reduces the broadcast traffic.

Across cluster topology control information is exchanged via specialized HOLSR nodes designated as cluster heads. Cluster heads are selected and nodes are classified according to their capabilities at the startup of the HOLSR process. A cluster is formed by a group of same-level mobile nodes that have selected a common cluster head. Nodes can move from one cluster to another and associate with the nearest cluster head. Any node participating in multiple topology levels automatically becomes the cluster head of the lower-level cluster. In HOLSR, a cluster head declares its status and invites other nodes to join in by periodically sending out Cluster ID Announcement (CID) messages. These and Hello messages are transmitted in the same packet using a grouping technique. This reduces the number of packet transmissions. A CID message contains two fields: cluster head, that represents the interface address of the originator of the message, and distance, which is the distance in hops to the cluster head generating the message. Every time the cluster head generates a CID message, the field distance is set to zero. A receiver node joins the cluster head and sends a new CID message. The new CID message increments the value of the distance. It invites other nodes to join the same cluster. The cluster formation process is described in more detail in [START_REF] Villasenor-Gonzalez | HOLSR: A hierarchical proactive routing mechanism for mobile ad hoc networks[END_REF].

The hierarchical architecture must support the exchange of topology control information between clusters without introducing additional overhead. Thus, Hierarchical TC (HTC) messages are generated by the cluster heads and used to transmit the membership information of a cluster to higher level nodes. HTC forwarding is enabled by the MPRs and restricted within a cluster. Nodes at the highest topology level have full knowledge of all nodes in the network. Their routing tables are as large as they would be in an OLSR network. However, in lower levels, the size of the routing table of every node is restricted by the size of the cluster and it is smaller than in OLSR. For instance, in Fig. 7 the cluster head A2 generates a HTC message at level 2 announcing that nodes 1, 2 and A1 are members of its cluster at level 1. The message is relayed to all nodes at the same level. Node B3 generates HTC messages at level 3 advertising that nodes 1, 2, 3, 4, 5, 7, 8, A1, B1, C1 (at level 1) and A2, B2, C2, D2 (at level 2) are members of its cluster. Table 2 presents a summary of the messages implemented in HOLSR networks.

Control messages are generated and propagated exclusively within each cluster unless a node is located in the overlapping zone of several clusters, i.e., a border node. For example, in Fig. 7 node 2 is within the border of cluster C1.A1 and may accept a TC or a HTC message from node 3 located in cluster C1.B1 (i.e., nodes 2 and 3 are border nodes). However, node 2 does not retransmit. Thus, except for the border nodes, knowledge of member nodes is restricted to the cluster itself. Data transfer between nodes in the same cluster is achieved directly using the routing tables. However, when transmitting data to destinations outside the local scope of a cluster, the cluster head is used as a gateway. A different strategy might be used, when transmitting data between border nodes in different clusters at the same level. Border nodes in different clusters at the same topology level can communicate directly without having to follow the strict clustering hierarchy. Therefore, HOLSR offers two main advantages (a) the traffic control reflecting local movements is restricted to each cluster (thus, reducing the routing table computation overhead), and (b) an efficient use of high-capacity nodes without overloading them.

Related Work

In this section, we review other hierarchical models based on OLSR to improve scalability in MANETs.

Cluster OLSR

In [START_REF] Ros | Cluster-based OLSR extensions to reduce control overhead in mobile ad hoc networks[END_REF], Ros et al. present the Cluster OLSR (C-OLSR) protocol. Unlike HOLSR, C-OLSR does not assume any particular cluster formation algorithm nor existence of higher capacity nodes. C-OLSR implements OLSR inside every cluster and uses the MPR mechanism for distributing control traffic at both inter-cluster and intracluster levels. C-OLSR limits the forwarding of TC messages inside every cluster to minimize the number control traffic messages. Every node can compute routes to any other node inside its cluster. To reach nodes in other clusters, nodes create routes to every cluster and not to every node. When a data packet arrives to a destination cluster, every node has enough information to deliver the packet to its final destination. This mechanism reduces the size of the routing tables.

For inter-cluster communications, Cluster Hello (C-Hello) and Cluster Topology Control (C-TC) messages are defined. C-Hello messages are used to sense neighboring clusters and to compute the Cluster MPR (C-MPR) set. C-Hello messages are flooded within the receiver cluster but not retransmitted to neighbor clusters. A C-MPR is a cluster selected to reach other clusters and mitigate the overhead of distributing C-TC messages for inter-cluster communications. C-TC messages advertise the nodes within a cluster to all the network. Fig. 8, shows an example of a C-OLSR network. At the first level, nodes are organized in clusters. The second level, shows how clusters are linked. Gray clusters are C-MPRs, e.g., C1.A is a C-MPR and node A is the cluster head. When a node in a cluster needs to send a data packet to a node inside another cluster, it computes a path through the clusters selected as C-MPRs, i.e., C1.A, C2.B, C3.C and C4.D.

When a C-Hello or C-TC messages arrive to a cluster, they are relayed to every node in the cluster. This allows nodes to learn about clusters topological information. C-TC messages must be relayed to adjacent clusters, only if the sender of the message has selected the receiver node as an C-MPR. To support this hierarchical architecture, every C-OLSR node has additional information repositories: one-hop neighbor cluster set, two-hop neighbor cluster set, cluster topology set, cluster MPR set and cluster MPR selector set. The information in these repositories supports inter-cluster communications. In C-OLSR, not every node has to generate intercluster information. The generation of C-Hello and C-TC messages can be done according to three different algorithms: a cluster head-based algorithm, a distributed algorithm or a hybrid approach. In the former case, only cluster heads generate control information. In the second algorithm, topology information is generated exclusively by border nodes. Finally, in the hybrid approach, C-Hello messages are generated by border nodes and C-TC messages are generated by the cluster heads. In all cases, the selected C-MPRs are responsible for forwarding C-TC messages.

The Multi-level OLSR Routing Using the HNA Extension

In [START_REF] Voorhaen | MORHE: A transparent multi-level routing scheme for ad hoc networks[END_REF], Voorhaen et al. present a multi-level routing scheme for ad hoc networks based on OLSR. The Multi-level OLSR Routing using the HNA Extension (MORHE) protocol improves scalability by exploiting high capability nodes. Using HNA messages and hierarchical addressing, MORHE constructs an overlay network formed by nodes with higher capabilities. Nodes with higher capabilities are selected as cluster heads. A cluster head is called a backbone node. Backbone nodes are chosen before network deployment and have more than one interface. Nodes are organized into clusters around every backbone node. Fig. 9, shows an example of a two-levels MORHE network. Nodes A, B,C, D and E are backbone nodes. Backbone nodes use one interface to communicate with the nodes inside their cluster and the second interface for inter-cluster communications. For instance, backbone node A, communicates with the nodes at the first level through the interface A1 and uses interface A2 to communicate with other backbone nodes. OLSR is implemented at each level.

MORHE is similar to HOLSR, nonetheless it only uses HNA messages already defined in the RFC 3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF]. Each backbone node periodically sends HNA messages informing other backbone nodes that it can reach all the nodes in the subnet that it is connected to. When a backbone node receives a HNA message, it updates its association database. Every backbone node uses HNA messages to inform all the nodes in its cluster about other clusters that can be reached. HNA messages are distributed using the MPR mechanism as defined in OLSR. Nodes can communicate directly with every node inside its cluster. Backbone nodes enable communication between nodes in different clusters. When a packet arrives at a backbone node, it attempts to find a route to the destination in its cluster. If this fails, then the backbone node retransmits the message to another backbone node. If the receiver finds a route, then it forwards the packet inside its cluster. In a MORHE network, every cluster is identified as a subnetwork. For instance, in Fig. 9, the network is divided in five subnetworks. Every backbone node has the IP addresses of every subnetwork in its association table. For example, 192.168.1.0/24 is the prefix of an IPv4 subnetwork, having 24 bits allocated for the network prefix, the remaining 8 bits are reserved for host addressing. If a node inside the subnetwork 192.168.0.0/24 needs to communicate with a node in the subnetwork 192.168.2.0/24, then it sends the packet to its backbone node which retransmits the packet to its final destination.

Tree Clustering

In [START_REF] Baccelli | OLSR scaling with hierarchical routing and dynamic tree clustering[END_REF][START_REF] Baccelli | OLSR trees: A simple clustering mechanism for OLSR[END_REF], Baccelli proposed a Tree Clustering mechanism to enable hierarchical routing within an OLSR network. Each cluster is a tree. Their head is the root. To organize the network in trees, every node selects as its parent the adjacent node with the maximum number of one-hop neighbors. The parent of a node is called a node's preferred neighbor. A node with maximum degree, i.e., maximum number of neighbors, is selected as the root of the three. The network is then viewed as a forest, i.e., a collection of logical trees. To form and maintain trees, OLSR nodes periodically exchange Branch messages. These messages are piggy-backed with Hello messages. Branch messages are not retransmitted. Within a Branch message, a node specifies its identity, the tree it belongs to, its parent in the tree and its distance in hops to the root. Roots can choose to limit the size of their three by imposing a maximum depth value. The organization in trees is dynamic. A mechanism allows to switch between a traditional flat networking, i.e., flat mode or a hierarchical networking, i.e., tree mode. The mechanism to transit between the flat mode and the tree mode is explained in detail in [START_REF] Baccelli | OLSR scaling with hierarchical routing and dynamic tree clustering[END_REF].

Within a tree, OLSR nodes operate as if there was no tree, except that messages originated by a node in a different tree are not considered and not forwarded, the root is responsible for the communication between the tree and the rest of the network, and a node in contact with another tree i.e., a leaf node, must inform its entire tree (specially its root), of the distance to reach other roots. A leaf node must generate a Leaf message for each other tree it reaches. In a Leaf message, the node specifies its ID, the root of the neighbor tree and the estimated distance between the roots, i.e., the sum between its depth in its tree, and the distance to the root of the neighbor tree. With this information, every root is able to compute the shortest path to reach its neighbor roots. This protocol employs Hello and TC messages within every tree, but implements Super-Hello (S-Hello), Super-TC (S-TC) and Super-HNA (S-HNA) messages for inter-cluster communications. Super messages are generated exclusively by the roots. These messages are identical to regular messages except for an additional field that includes the IP address of the next root to reach. Unlike regular messages, Super-messages are routed using the constructed paths instead of being flooded. Super-messages are unicasted using the shortest root-to-root path advertised by Leaf messages. Super-messages are the only messages to be forwarded outside a tree. MPR selection is performed as if there were no trees. When a tree mode is activated, the scope of TC messages is limited to the tree they were generated. However, Super-messages are forwarded between clusters following the MPR flooding mechanism.

To allow hierarchical routing, routes exchange Super-messages in order to identify other roots and construct a Super-topology. S-Hello and S-TC messages allow the roots to construct a super-topology formed by roots. The roots periodically ex- change S-Hello messages to learn about other roots in neighbor trees (i.e., onesuper-hop neighbors). As in OLSR, every root computes its super-MPR set formed by other roots. A super set of MPRs is used for distributing S-TC messages among clusters. S-Hello messages are not forwarded. S-TC messages are forwarded by the S-MPRs. S-TC messages include the super-selector set, i.e., the roots that have selected the sender as a S-MPR. Finally, every root generates S-HNA messages to inform other roots about the link state information within its cluster. Therefore, every root is aware of the link state information of other threes. Routing among clusters is achieved using the information between S-TC and S-HNA messages. Traffic outside the tree scope is achieved via the root nodes. Fig. 10 shows an example of a tree clustering hierarchical architecture. Nodes A, B,C, D and E are selected as roots. These nodes have the maximum degree. Root node A selects B as its MPR to reach root trees C, D and E. When a node inside cluster C1.A needs to communicate with a node inside cluster C5.E, it sends the data traffic to its root node A which retransmits the traffic to its final destination trough B and E.

Table 3 presents a summary of the features of each hierarchical approach that we reviewed. Unlike MORHE and C-OLSR, HOLSR and the Tree clustering approaches include a cluster formation mechanism. MORHE and HOLSR were de- Leaf, Branch, S-Hello, S-TC and S-HNA Yes signed for heterogeneous networks and multiple hierarchical levels. C-OLSR and Tree clustering were designed for homogeneous networks and two hierarchical levels. Nevertheless, these approaches might be implemented in networks with heterogeneous capabilities. All approaches implement the MPR mechanism for distributing control traffic messages.

Security Issues in HOLSR Networks

Note that in all described approaches, the exchange of control traffic at both intracluster and inter-cluster levels is performed by using the MPR mechanism. Security is no addressed. Therefore, they are vulnerable to the flooding disruption attacks described in Section 2.2. The cluster formation phase is vulnerable to malicious behavior. In [START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF][START_REF] Cervera | Preventing the Cluster Formation Attack Against the Hierarchical OLSR Protocol: Invited Talk[END_REF], we describe in detail security threats to both the cluster formation and topology map acquisition phases.

In HOLSR, the flow of CID messages is an important vulnerability target. The hop count has to be updated every time a new message is retransmitted. Thus, a malicious node might alter this field to unsettle the cluster formation process. The attack, has a bigger impact when a malicious node drastically reduces the hop count field. Because receivers accept the CID message with the lowest hop count value. Thus, when an attacker increases drastically the value, receivers automatically discard the altered message and accept valid messages from other nodes. When a node that generates a CID message reinitializes the value of the field hop count, the receiver nodes may join a farther cluster head and discard valid CID messages from closer cluster heads. We address the case where the hop count field is maliciously reduced. For instance, Fig. 11 2 and 3) process the message and incorrectly join CH A . Note that the lowest value that can be used to reinitialize the field hop count is two because CID messages with a field hop count equal to one are generated exclusively by the cluster heads. We assume that the attacker has only one interface. It can not impersonate a cluster head. It only modifies the hop count value. This attack can affect other OLSR-based hierarchical approaches. For instance, a misbehaving node may alter the field distance in Branch messages in the Tree Clustering approach proposed by Baccelli, reviewed in Section 3.1.3.

Countermeasures

In [START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF][START_REF] Cervera | Preventing the Cluster Formation Attack Against the Hierarchical OLSR Protocol: Invited Talk[END_REF], we describe in detail security threats in both the cluster formation and topology map acquisition phases. Countermeasures to mitigate the effect of the attacks are also presented. In the former case, in [START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF], we analyze the effect of flooding disruption attacks in HOLSR networks to interrupt the propagation of HTC messages. We proposed additional coverage in the selection of MPRs at any hierarchical level. We analyze the effect of flooding disruption attacks. Unlikely flat OLSR networks, when a malicious nodes attempts to interrupt the propagation of HTC messages the inter-cluster communication is affected. Our proposed solution is based on the selection of MPRs with additional coverage, i.e., k-Covered-MPR and k-Robust-MPR selections. Our results showed that it is possible to mitigate the effect of the attack by adding additional coverage. The k-Covered-MPR selection increased the chances of mitigate the attack but the performance of the network reduces due to an increased number of TC and HTC messages. Our proposed k-Covered-MPR selection offers an equivalent level of protection but reducing the amount of TC and HTC messages flooded in the network.

In [START_REF] Cervera | Preventing the Cluster Formation Attack Against the Hierarchical OLSR Protocol: Invited Talk[END_REF], we presented a solution based on hash chains to protect mutable fields in HOLSR networks. Our algorithm Hash-Chained CID Dissemination (HCCD) allows to detect and discard invalid CID messages. A valid cluster head (CH j ) generates a random number s j , i.e., a nonce that is only known by the originator of the message. After, it initializes the hop count field i equal to one and computes the Max j value by applying t times the hash function h(x) to the nonce s j , such that Max j is equal to h t (s j ). We assume that Max j and the value of t are known by all the nodes in the network during the execution of the protocol. Additionally, CH j applies i times the hash function to s j , to obtain h i (s j ). Then, CH j generates a CID message with the fields: < Max j , h i (s j ), i >. The receiver node verifies that the CID message is valid by applying ti times the hash function to h i (s j ) and comparing the result with Max j . Therefore, if Max j is equal to h t-i (h i (s j )), then the hop count value i has not been altered and the received CID message is valid. Finally, the receiver node joins CH j until it receives a CID message from a different cluster head with a lower hop count value. In the mean time, the receiver node generates periodically CID messages announcing its cluster head and the hop count distance to reach it, i.e., < Max j , h(h i (s j )), i + 1 >. Our solution is based on the work presented by Hong et al. in [START_REF] Hong | Secure OLSR[END_REF]. The authors presented a wormhole detective mechanism and an authentication protocol to strengthen the neighbor relationship establishment in standard OLSR. The authors used digital signatures to ensure the non-mutable fields and hash chains to secure the Hop Count and TTL fields. Their solution is similar to our proposed algorithm, however it is implemented in flat OLSR to protect only standard control traffic messages. We address a different kind of attack in HOLSR networks. Our mechanism protects the integrity of CID messages and enforces the proper distribution of nodes in every cluster. In [START_REF] Cervera | Preventing the Cluster Formation Attack Against the Hierarchical OLSR Protocol: Invited Talk[END_REF], our experiments showed that the distribution of nodes is less balanced when the hop count in CID messages is maliciously altered. We also showed that we can prevent this kind of attacks by applying our proposed algorithm. Note that our mechanism, can be also applied in other hierarchical routing protocols for MANETs that utilize mutable information to organize the network in clusters.

Multipath OLSR-based Routing

In this section, we analyze a multipath routing strategy based on OLSR that takes advantage of the MPR flooding mechanism. In [START_REF] Yi | Simulation and performance analysis of MP-OLSR for mobile ad hoc networks[END_REF][START_REF] Yi | Implementation of multipath and multiple description coding in OLSR[END_REF][START_REF] Yi | Multipath OLSR: Simulation and Testbed[END_REF][START_REF] Yi | Multipath optimized link state routing for mobile ad hoc networks[END_REF], Yi et al. proposed the Multipath OLSR (MP-OLSR) routing protocol aiming to enhance load-balancing, energy-conservation, Quality-of-Service (QoS) and security. MP-OLSR is a hybrid multipath routing protocol. In MP-OLSR, the OLSR proactive behavior is changed for on-demand route computation. MP-OLSR becomes a source routing protocol. There are two phases: topology discovery and routes computation. During topology discovery, nodes obtain a partial topology map just like in OLSR. However, MP-OLSR nodes do not construct routing tables. During routes computation, nodes calculate multiple paths to reach any other node in the network following an on-demand scheme. MP-OLSR implements Multiple Description Coding (MDC) for data transfer. MDC adds redundancy to information streams and split them up into several sub-streams to improve the integrity of data. These sub-streams are sent along multiple paths from the source to the destination. MP-OLSR implements source routing with route recovery and loop detection to adapt to the changes in the network topology. Thus, when data transfer is required, route recovery and loop detection allow every node to detect if a path is not valid anymore and to find a new path to reach the final destination. MP-OLSR uses the Dijkstra's algorithm to discover routes. The routes that are obtained can be grouped in two categories:

1. Disjoint: In this category we have two types of disjoint paths: node-disjoint and link-disjoint. Node-disjoint paths type do not share nodes except for the source and destination nodes. Link-disjoint paths can share some nodes but all the links are different. 2. Inter-twisted: In this case, the paths may share several links.

To construct disjoint paths, MP-OLSR defines cost functions to obtain new paths that tend to be node-disjoint or link-disjoint. Once a path is computed, a function f p is used to increase the costs c of the links that belong to the computed path, e.g., f p (c) = 3c. A function f e is defined to increase the cost of the links of the nodes included in the path previously obtained. In MP-OLSR, neither nodes nor links used in computed paths are eliminated. This strategy allows MP-OLSR to construct multiple paths in sparse networks where is not always possible to find strictly node-disjoint paths. In addition, to increase the chances of constructing node-disjoint paths, the MPRs report all their one-hop neighbors (i.e., the TC redundancy parameter is equal to two). Consider f id as the identity function, i.e., f id (c) = c. Therefore, to construct disjoint paths, there are three possibilities:

• if f id = f e < f p , then paths tend to be link-disjoint;

• if f id < f e = f p , then paths tend to be node-disjoint;

• if f id < f e < f p , then paths also tend to be node-disjoint, but when not possible they tend to be link-disjoint.

For example, in Fig. 12(a), node s attempts to construct multiple paths to node d. MP-OLSR implements a Multipath Dijkstra's algorithm to obtain the shortest paths. Consider initial cost c of each link equal to one and f p (c) = 3c and f e (c) = c, i.e., a penalty is only applied to the used links. The first time the Dijkstra's algorithm is applied, the computed path is s → c → d. Thus, the cost of the links (s, c) and (c, d) is changed from one to three using f p , see Fig. 12(b). The second path we obtain is:

s → b → c → h → d. The cost of the links (s, b), (b, c), (c, h) and (h, d) is set to three. Finally, the third computed path is: s → a → c → f → g → d.
The cost of all used links is set to three, see Fig. 12(c). These three paths are link-disjoint. To obtain paths that tend to be node-disjoint, we define functions f p (c) = 3c and f e (c) = 2c. In this case, the penalty is also applied to the used nodes. First, the path s → c → d is computed and the cost of the links is updated. The links that include a node in the computed path -except for the source s and the destination d-are set to two, see Fig. 12(d). Then, the next path we obtain is: s → a → e → f → g → d. These two paths are node-disjoint. The path: s → a → c → h → d, is an example of an inter-twisted path.

Related Work

In this section, we present other multipath routing strategies based on OLSR. Several multipath routing approaches take advantage of the proactive behavior and MPR flooding mechanism proposed in OLSR. The strategies proposed, attempt to improve security, QoS, load balancing or energy consumption. However, all strategies proposed are not secure by design. For instance, in [START_REF] Kun | The research and simulation of multipath-OLSR for mobile ad hoc network[END_REF], Kun et al., proposed a different version of multipath OLSR using IP-source routing. Based on the Dijkstra's algorithm, nodes calculate multiple node-disjoint paths. Additionally, the authors introduce an algorithm of load-assigned to transmit data through the paths based on the congestion information of all intermediate nodes on each path. Badis and Al Agha [START_REF] Badis | QOLSR multi-path routing for mobile ad hoc networks based on multiple metrics: bandwidth and delay[END_REF], also proposed a path selection criteria and multi-path calculation based on bandwidth and delay to improve QoS in OLSR networks (QOLSR). The resulting protocol, computes multiple loop-free and node-disjoint paths. The authors implement the shortest-widest path algorithm to guarantee loop-free routes. Additionally, they evaluated and compared QOLSR multipath routing versus a QOLSR single-path routing using a scalable simulation model. In [START_REF] Srinivas | Minimum energy disjoint path routing in wireless ad-hoc networks[END_REF], Srinivas and Modiano proposed algorithms for finding minimum energy disjoint paths in wireless networks. Their main contribution is a polynomial time algorithm for the minimum energy k node-disjoint problem. Node-disjoint paths are more resilient to failures. However, the authors showed that link-disjoint paths save more energy. Zhou et al.

proposed in [START_REF] Zhou | A novel routing protocol for ad hoc sensor networks using multiple disjoint paths[END_REF] the Source Routing based Multi-Path OLSR (SR-MPOLSR) protocol. The protocol implements the Dijkstra's algorithm to calculate multiple disjoint routes. Data transmission at the source is carried out through predetermined multiple paths (i.e., source routing). The loads are distributed in a weighted roundrobin fashion. These strategies proposed attempt to construct multiple link-disjoint or node-disjoint paths. However, all approaches are affected by the flooding disruption attacks described in Section 2.2. Nodes in OLSR-based multipath routing protocols only acquire a partial view of the topology network. These problems are described in the following section.

Security issues in Multipath OLSR-based Networks

Multipath OLSR-based approaches are vulnerable to the flooding disruption attacks [START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF] attacks presented in Section 2.2 during the topology discover and route computation phases. An attacker may refuse to retransmit control traffic or may select an invalid MPR set to prevent other nodes from calculating disjoint paths to reach other nodes in the network. MP-OLSR constructs non disjoint multiple paths.

The protocol computes several routes, but it is impossible to know how many of them are disjoint. When a node part of several paths misbehaves, all paths are affected. All OLSR-based multipath strategies use the MPR mechanism to flood the network with control traffic. However, only partial topology information is generated by the MPRs. We identify two vulnerabilities in all OLSR-based multipath routing strategies: the nodes in an OLSR network only obtain a partial view of the network topology and they are affected by the security threats presented in Section 2.2. The MPRs generate and forward TC messages to advertise their selector set to other nodes at more than two hops away. However, with this information nodes only obtain a partial view of the topology. This is because TC messages only report partial link state information. For instance, Fig. 13(a) shows the complete topology of an MP-OLSR network. Gray nodes represent MPRs. Fig. 13(b) shows the perspective of node s after the topology discovery phase. The links (g, j), (i, l), ( j, d), (l, d), ( j, k) and (l, k) are not reported in TC messages. Thus, the link between node g and j is not reported because neither g nor j are MPRs. Node k is an MPR but it does not report links to nodes j and l because they are not included in its selector set. From the perspective of node s, k is the only node that reaches node d. Hence, it is not possible to compute multiple disjoint paths. To increase the chances of finding disjoint paths, the MPRs in an MP-OLSR networks report more information in their TC messages by tunning their TC redundancy parameter. The TC redundancy parameter is defined locally by every node. Nodes with different TC redundancy values can coexist. MP-OLSR nodes set their TC redundancy parameter to two. However, the size of the TC messages increases and in some situation it is not enough to report important links. For example, Fig. 13(c) shows the network perspective of node s if the MPRs report their one-hop neighbors, i.e., TC redundancy parameter equal to two. Hence, node s is aware of the links ( j, k) and (l, k). However, the links (g, j), (i, l), ( j, d) and (l, d) remain unreported. Fig. 13(c) also shows that all the possible routes to reach node d include node k. When node k misbehaves, all the computed paths are compromised.

Countermeasures

The MPR selection with additional coverage (i.e., k-Robust-MPR or k-Covered-MPR) helps to mitigate the attacks against the construction of disjoint paths. Addi-tional coverage helps to advertise more links and construct multiple node-disjoint paths without increasing the size of the messages. In OLSR networks, the MPRs form a Connected Dominating Set (CDS). A CDS is a subset of connected nodes such that if a node in the network is not part of the CDS, then it has a link to a node in the CDS. Every node must be able to construct a CDS of the network with the information gathered during the topology discovery phase. We define an MPRCDS as a CDS such that every node in the CDS has been selected as an MPR. When the nodes select their MPRs following a k-Covered-MPR selection we obtain a k-CCDS. When the nodes compute their MPRs following a k-Robust-MPR selection we obtain a k-RCDS. Therefore, if a node obtains a more complete view of the network (i.e., k-CCDS or k-RCDS), then it is able to find alternative routes to compute disjoint paths.

Conclusion and Future Work

In link state routing protocols for MANETs, the generation and exchange of control traffic messages are important vulnerability targets. A malicious node may perpetrate an attack by flooding the network with incorrect information or by preventing other nodes from acquiring a complete network topology map. We presented security threats in link state routing protocols based on OLSR. Particularly, we addressed flooding disruption attacks in OLSR networks. This kind of attacks can be carried out in networks with cryptographic capabilities. Additionally, a review of related work and proposed countermeasures is also presented. In addition, we reviewed security threats in other link state routing protocols based on OLSR. We presented vulnerabilities and countermeasures specific to HOLSR and MP-OLSR.

Future Work

The k-Robust-MPR selection may be affected either by a malicious node, that generates false links to avoid the selection of k+1 disjoint MPR sets or due to the network topology. As part of future work, we consider an extended k-Robust-MPR selection to address the cases when is not possible to select multiple disjoint MPR sets.

Countermeasures against more complex attacks during the cluster formation phase in hierarchical OLSR-based networks is also part of further research. A mechanism to improve the selection of multiple disjoint routes in OLSR-based networks is required. To improve load balancing, nodes with the smallest number of nodes in their selector set should be privileged to be included in the computed paths. Clearly, in sparse networks is not always possible to compute disjoint paths. Nevertheless, multipath routing takes advantage of large and dense networks. Then, the cases where the construction of multiple node-disjoint paths is affected either by an incomplete view of the network topology or by the presence of a misbehaving node should be addressed.

  (a) Classical flooding. (b) MPR mechanism.

Fig. 1

 1 Fig. 1 MPR based mechanism against the classical flooding. Consider gray nodes as the originators of a TC message and black nodes as MPRs.

Fig. 3

 3 Fig.3Taxonomy of flooding disruption attacks[START_REF] Cervera | Mitigation of flooding disruption attacks in HOLSR networks[END_REF].

Fig. 4

 4 Fig. 4 Flooding disruption due to identity spoofing attacks. In Fig. 4(a) node x spoofs d and reports an incorrect link between nodes c and d (one-hop address duplication). In Fig. 4(b), node x spoofs c and affects node a's MPR selection (two-hop address duplication).

Fig. 5

 5 Fig. 5 Flooding disruption due to link spoofing attacks. In Fig. 5(a), node x spoofs links to nodes e and c. In Fig. 5(b), node x spoofs links to nodes e and the inexistent node w.

Fig. 6

 6 Fig.6Flooding disruption due to protocol disobedience. In Fig.6(a), node x never selects a valid MPR set. In Fig.6(b), node x modifies and forwards incorrectly TC messages.

Fig. 7

 7 Fig. 7 Example of a hierarchical architecture with heterogeneous nodes.

Fig. 8

 8 Fig. 8 Example of a Cluster OLSR network. Consider gray clusters as C-MPRs.

Fig. 10

 10 Fig. 10 Tree clustering. Black nodes represents the roots of the tree. Branches of the trees are shown with solid lines between nodes. Links that are not branches are dashed.

  (a) shows the correct propagation of CID messages. Fig. 11 (b) shows an example of the attack. In Fig. 11 (b), M 1 is a malicious node at distance six hops from cluster head CH B . M 1 receives CID messages from CH B , and generates a new CID message assigning the incorrect value two to the field hop count. Thus, all nodes at distance from CH B , greater or equal than four hops (nodes CID message propagation. b) Incorrect CID message propagation, decreasing the hop count value.

Fig. 11

 11 Fig. 11 Cluster formation attack in HOLSR networks.

Fig. 12

 12 Fig.12OLSR network. In Fig.12(a), consider the cost of all links equal to one.

  Node s perspective of the network. TC redundancy equal to 0.

  Node s perspective of the network. TC redundancy equal to 2.

Fig. 13

 13 Fig. 13 Network topology perspective of node s. Gray nodes represent MPRs.

Table 1

 1 Summary of control traffic messages in OLSR networks. MID and HNA messages are optional.

	Messages Generated by	Retransmitted by Reported information
	Hello	Every node	N/A	One-hop neighbors
	TC	MPRs	MPRs	MPR Selector Set
	MID	Nodes with more than one interface MPRs	All available interfaces
	HNA	Nodes with external access	MPRs	External routing information

  2, after receiving TC messages from node g, node a identifies node g as the last hop to reach node i. Note that node b receives TC messages from nodes a and f . However, node b stores the recently received TC messages in its duplicate table and discards future copies of the same message. 6. Finally, routing tables are constructed using information from the one-hop and two-hop neighbors and the topology table. Every node executes the Dijkstra's algorithm to obtain the shortest path to every other node more than two hops away. For instance, to reach node i, node a constructs a path trough nodes f and g. The shortest path to reach every other node in the network is always composed by MPRs. For example, to reach node d, node i constructs a path composed by nodes g, f and b. 7. Routing tables include the next node and number of hops to reach every other node in the network. Node i stores in its routing table only the next hop to reach node d (i.e., node g) and the number of hops (i.e., four hops). Thanks to the MPR mechanism, the nodes are aware of every other node in the network but some links are never advertised. For instance, node a never receives information about the link between nodes h and i, or between nodes e and c.

	8. Optionally, a node with more than one interface generates MID messages. A
	node with access to an external network generates HNA messages. Information
	contained in MID and HNA messages is loaded in routing tables.

Table 2

 2 Summary of control traffic messages in HOLSR networks.

	Messages	Generated by	Retransmitted by	Reported information
	Hello	Every node	N/A	One-hop neighbors
	TC	MPRs	MPRs	MPR Selector Set
	CID	Cluster heads	N/A	Cluster head Identification
	HTC	Cluster heads	MPRs	Nodes within a cluster

  Example of a MORHE network. Consider black nodes as backbone nodes.

						HNA
		HNA			196.168.0.0/24
		196.168.0.0/24			196.168.2.0/24
	HNA	196.168.1.0/24			196.168.3.0/24
	196.168.0.0/24	196.168.3.0/24		B2	196.168.4.0/24	HNA
	196.168.1.0/24	196.168.4.0/24			196.168.1.0/24
	196.168.2.0/24 196.168.4.0/24	C2				A2	196.168.3.0/24 196.168.2.0/24
	D2			196.168.0.0/24 HNA	B1	196.168.4.0/24
				196.168.1.0/24
		C1	E2	196.168.2.0/24 196.168.3.0/24		Cluster C2.B
		Cluster C3.C				A1
	D1					Cluster C1.A
			E1			-Cluster head
	Cluster C4.D			Cluster C5.E
	Fig. 9

Table 3

 3 Comparison of OLSR-based hierarchical approaches. All approaches implement Hello and TC message for intra-cluster communications.

	Routing	Network	Logical	Messages	Cluster For-
	Protocol		Levels		mation Alg.
	HOLSR Heterogeneous n	CID and HTC	Yes
	MORHE Heterogeneous n	HNA	No
	C-OLSR Homogeneous 2	C-Hello and C-TC	No
	Tree	Homogeneous 2

Gimer Cervera, Michel Barbeau, Joaquin Garcia-Alfaro and Evangelos Kranakis

Acknowledgment

The authors graciously acknowledge the financial support received from the following organizations: Natural Sciences and Engineering Research Council of Canada (NSERC), Mathematics of Information Technology and Complex Systems (MITACS), Institut Telecom, Spanish Ministry of Science and Innovation (grants TSI2007-65406-C03-03 E-AEGIS and CONSOLIDER-INGENIO CSD2007-00004 ARES), National Council of Science and Technology (CONACYT), and Ministry of Education of Mexico (SEP, Program for Academic Improvement).