Thomas Clausen
email: thomas@thomasclausen.org

Ulrich Herberg
email: ulrich.herberg@us.fujitsu.com

Matthias Philipp
email: matthias.philipp@inria.fr

A Critical Evaluation of the "IPv6 Routing Protocol for Low Power and Lossy Networks" (RPL)

With RPL -the "IPv6 Routing Protocol for Lowpower Lossy Networks" -emerging as a Proposed Standard "Request For Comment" (RFC) in the Internet Engineering Task Force (IETF) after a ∼2-year development cycle, this paper presents a critical evaluation of the resulting protocol and its applicability and limits. The paper presents a selection of observations of the protocol characteristics, exposes experiences acquired when producing a prototype implementation of RPL, and presents results obtained from testing this protocol -both in a network simulator, and in real-world experiments on a wireless sensor network testbed. The paper aims at providing a better understanding of possible weaknesses and limits of RPL, notably the possible directions that further protocol developments should explore, in order to address these.

I. INTRODUCTION

RPL -the "Routing Protocol for Low Power and Lossy Networks" (RPL) [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] -is a proposal for an IPv6 routing protocol for Low-power Lossy Networks (LLNs), by the ROLL Working Group in the Internet Engineering Task Force (IETF). This routing protocol is intended to be the IPv6 routing protocol for LLNs and sensor networks, applicable in all kinds of deployments and applications of LLNs. The unofficial goal, of the ROLL Working Group, is to prevent fragmentation in the sensor networking market by providing an IP-based routing standard, and solicit broad industrial support behind that standard.

The objective of RPL and ROLL is to target networks which "comprise up to thousands of nodes", where the majority of the nodes have very constrained resources, where the network to a large degree is "managed" by a (single or few) central "supernodes", and where handling mobility is not an explicit design criteria. Supported traffic patterns include multipoint-to-point, point-to-multipoint and point-topoint traffic. The emphasis among these traffic patterns is to optimize for multipoint-to-point traffic, to reasonably support point-to-multipoint traffic and to provide basic features for point-to-point traffic, in that order.

As of early 2011, RPL has been deemed "ready" by the IETF, for publication as a "Proposed Standard" RFC (Request for Comments). The implication of a protocol being labeled "Proposed Standard" is that it is considered generally stable: well-understood and community reviewed, no known design issues pending, and with some community support. "Proposed Standard" is, however, only the first step on what is called the Standards Track1 -experiences with the protocol, from testing and operational deployments, as well as detailed studies of its characteristics and behaviors, may result in protocol changes or retraction.

It is thus opportune to consider the protocol, at its current level of specification, in order to understand which aspects of it necessitate further investigations, and in order to identify possibly weak points which may restrict the deployment scope of the protocol. This paper has as objective to provide a critical evaluation of RPL, in the spirit of better understanding its characteristics and limits.

A. Paper Outline

The remainder of this paper is organized as follows: section II provides an overview of the functional parts of RPLthe algorithms for constructing the basic forwarding structures, as well as protocol signaling. Sections III-XII each explore a specific aspect of RPL, and provide a critical analysis of the impact of the underlying hypotheses made by the designers of RPL. Where possible, abstract reflections on the protocol are complemented by simulation results and results from experiments in a test-bed with real sensor devices. Section XIII concludes this paper by providing both a summary of the observations made, as well as the authors position regarding the applicability of RPL and the possible directions that protocol development should take, in order that IPv6 routing protocols for LLNs can progress -both on the IETF Standards Track and in wide-scale real world deployments.

II. RPL OVERVIEW

The basic construct in RPL is a "Destination Oriented Directed Acyclic Graph" (DODAG), depicted in figure 1. In a converged LLN, each RPL router has identified a stable set of parents, each of which is a potential next-hop on a path towards the "root" of the DODAG, as well as a preferred parent. Each router, which is part of a DODAG (i.e. has selected parents) will emit DODAG Information Object (DIO) messages, using link-local multicast, indicating its respective rank in the DODAG (i.e. distance to the DODAG root according to some metric(s), in the simplest form hop-count). Upon having received a (number of such) DIO messages, a router will calculate its own rank such that it is greater than the rank of each of its parents, select a preferred parent and then itself start emitting DIO messages.

The DODAG formation thus starts at the DODAG root (initially, the only router which is part of a DODAG), and spreads gradually to cover the whole LLN as DIOs are received, parents and preferred parents are selected and further routers participate in the DODAG. The DODAG root also includes, in DIO messages, a DODAG Configuration Object, describing common configuration attributes for all RPL routers in that network -including their mode of operation, timer characteristics etc. RPL routers in a DODAG include a verbatim copy of the last received DODAG Configuration Object in their DIO messages, permitting also such configuration parameters propagating through the network. A Distance Vector protocol, RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] restricts the ability for a router to change rank. A router can freely assume a smaller rank than previously advertised (i.e. logically move closer to the root) if it discovers a parent advertising a lower rank, and must then disregard all previous parents of higher ranks. The ability for a router to assume a greater rank (i.e. logically move farther from the root) than previously advertised is restricted, to avoid count-to-infinity problems. The root can trigger "global recalculation" of the DODAG by increasing a sequence number, DODAG version, in DIO messages.

The DODAG so constructed is used for installing routes: the "preferred parent" of an RPL router can serve as a default route towards the root, or the root can embed in its DIO messages the destination prefixes, included by DIOs generated by RPL routers through the LLN, to which connectivity is provided by the root. Thus, RPL by way of DIO generation provides "upward routes" or "multipoint-to-point routes" from the sensors inside the LLN and towards the root.

"Downward routes" are enabled by having sensors issue Destination Advertisement Object (DAO) messages, propagating as unicast via parents towards the DODAG root. These describe which prefixes belong to, and can be reached via, which RPL router. In a network, all RPL routers must operate in either of storing-mode or non-storing-mode, specified by way of a "Mode of Operation" (MOP) flag in the DODAG Configuration Object from the root. Depending on the MOP, DAO messages are forwarded differently towards the root:

DAOs from an RPL router, and from all routers on the path between it and the root, it can use source routing for reaching advertised destinations inside the LLN.

• In storing-mode, each RPL router on the path between the originator of a DAO and the root records a route to the prefixes advertised in the DAO, as well as the nexthop towards these (the router, from which the DAO was received), then forwards the DAO to its preferred parent. "Point-to-point routes", for communication between devices inside the LLN and where neither of the communicating devices are the DODAG root, are as default supported by having the source sensor transmit via its default route to the DODAG root (i.e., using the upward routes) which will then, depending on the "Mode of Operation" for the DODAG, either add a source-route to the received data for reaching the destination sensor (downward routes in non-storing-mode) or simply use hop-by-hop routing (downward routes in storing-mode). In the case of storing-mode, if the source and the destination for a point-to-point communication share a common ancestor other than the DODAG root, a downward route may be available (and used) before reaching the DODAG root.

A. RPL Message Emission Timing -Trickle Timers

RPL message generation is timer-based, with the root able to configure back-off of message emission intervals using Trickle [START_REF] Levis | Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks[END_REF], specified in [START_REF] Levis | RFC6206: The Trickle Algorithm[END_REF]. Trickle, as used in RPL, stipulates that a RPL router transmits a DIO "every so often" -except if receiving a number of DIOs from neighbor routers, enabling the router to determine if its DIO transmission is redundant.

When an RPL router transmits a DIO, there are two possible outcomes: either every neighbor router that hears the message finds that the information contained is consistent with its own state (i.e., the received DODAG version number received corresponds with that which the RPL router has recorded and no better rank is advertised than that which is recorded in the parent set) -or, a recipient RPL router detects that either the sender of the DIO or itself has out-of-date information. If the sender has out-of-date information, then the recipient RPL router schedules transmission of a DIO to update this information. If the recipient RPL router has out-of-date information, then it updates based on the information received in the DIO.

With Trickle, an RPL router will schedule emission of a DIO at some time, t, in the future. When receiving a DIO containing information consistent with its own information, the RPL router will record that "redundant information has been received" by incrementing a redundancy counter, c. At the time t, if c is below some "redundancy threshold", then it transmits its DIO. Otherwise, transmission of a DIO at this time is suppressed, c is reset and a new t is selected to twice as long time in the future -bounded by a pre-configured maximum value for t. If, on the other hand, the RPL router has received an out-of-date DIO from one of its neighbors, t is reset to a pre-configured minimum value and c is set to zero. In both cases, at the expiration of t, the RPL router will verify if c is below the "redundancy threshold" and if so transmitotherwise, increase t and stay quiet.

III. RPL DATA TRAFFIC FLOWS RPL makes a-priori assumptions of traffic patterns: sensorto-root traffic (multipoint-to-point) is predominant, root-tosensor traffic (point-to-multipoint) is rare and sensor-to-sensor traffic is somewhat esoteric. While not specifically called out thus in [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF], the resulting protocol design reflects these assumptions in that mechanism constructing multipoint-topoint paths is efficient in terms of control traffic generated and state required, point-to-multipoint path construction much less so -and sensor-to-sensor paths subject to potentially significant stretch.

An RPL router selects from among its parents a "preferred parent", to serve as a default route towards the root (and to prefixes advertised by the root). Thus, RPL provides "upward routes" or "multipoint-to-point routes" from the sensors towards the root. An RPL router which wishes to act as a destination for traffic ("downward routes" or "point-tomultipoint") issues DAOs upwards in the DODAG towards the root, describing which prefixes belong to, and can be reached via, that RPL router. Sensor-to-sensor routes are supported by having the source sensor transmit, via its default route, towards the root. In non-storing mode, the data will reach the root, which will send the data packet downward towards the destination sensor. In storing mode, the source and the destination may have a common ancestor other than the DODAG root, which may provide a downward route to the destination.

A. Why This Is A Critical Point

The data traffic characteristics assumed by RPL do not represent a universal distribution of traffic patterns in LLNs:

• There are scenarios where sensor-to-sensor traffic is a more common occurrence, documented e.g. in [START_REF] Martocci | Building Automation Routing Requirements in Low Power and Lossy Networks[END_REF]. • There are scenarios, where all traffic is bi-directional, e.g. in case sensor devices in the LLN are, in majority, "actively read": a request is issued by the root to a specific sensor, and the sensor value is expected returned. For the former, all sensor-to-sensor paths include the root, possibly causing congestion on the communications medium near the root, and draining energy from the intermediate RPL routers on an unnecessarily long path. If sensor-tosensor traffic is common, RPL routers near the root will be particularly solicited as relays, especially in non-storing mode. For the latter, all RPL routers are required to generate DAOs, which generates a considerable control traffic overhead [START_REF] Clausen | A Comparative Performance Study of the Routing Protocols LOAD and RPL with Bi-Directional Traffic in Lowpower and Lossy Networks (LLN)[END_REF].

IV. FRAGMENTATION

Fragmentation of IP packets appears when the size of the IP datagram is larger than the Maximum Transmission Unit (MTU) supported by the link layer. When an IP packet is fragmented, all fragments of that IP packet must be successfully received by a router, in order that the IP packet is successfully received -otherwise, the whole IP packet is lost. Moreover, the additional link-layer frame overhead for each of the fragments increases the capacity required from the medium, and may consume more energy for transmitting a higher number of frames on the network interface.

RPL is an IPv6 routing protocol, designed to operate on constrained link layers, such as 802.15.4 [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF], with a maximum MTU of 127 bytes -a deviation from the otherwise specified minimum MTU of 1280 bytes for IPv6 [START_REF] Deering | RFC2460: Internet Protocol, Version 6 (IPv6) Specification[END_REF]. Reducing the need of fragmentation of packets on such a link layer, compression adaptation layers exist [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF], [START_REF] Hui | Compression Format for IPv6 Datagrams in Low Power and Lossy Networks (6LoWPAN)[END_REF], reducing the overhead of the IPv6 header from at least 40 octets to a minimum of 2 octets. With a physical layer packet size of 127 octets, a maximum frame overhead of 25 octets and 21 octets for link layer security [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF], 81 octets remain for L2 payload. Further subtracting 2 octets for the compressed IPv6 header leaves 79 octets for L3 data payload.

The second L in LLN indicating Lossy [START_REF]ROLL Charter[END_REF], higher loss rates than typically seen in IP networks are expected, rendering fragmentation important to avoid.

DIO messages consist of a mandatory base object, facilitating DODAG formation, and additional options for e.g. autoconfiguration and network management. The base object contains two unused octets, reserved for future use, resulting in two bytes of unnecessary zeros, sent with each DIO message. The Prefix Information option, used for automatic configuration of address, is even worse: it carries four unused octets to be compatible with IPv6 neighbor discovery.

A. Why This Is A Critical Point

While 79 octets may seem to be sufficient to carry RPL control messages, consider the following: RPL control messages are carried in ICMPv6, and the mandatory ICMPv6 header consumes 4 octets. The DIO base another 24 octets. If link metrics are used, that consumes at least another 8 octets2 . The DODAG Configuration Object consumes up to a further 16 octets, for a total of 52 octets. Adding a Prefix Information Object for address configuration consumes another 32 octets, for a total of 84 octets -thus exceeding the 79 octets available for L3 data payload and causing fragmentation of such a DIO. As a point of reference, the ContikiRPL [START_REF] Tsiftes | Low-Power Wireless IPv6 Routing with ContikiRPL[END_REF] implementation includes both the DODAG Configuration option and the Prefix Information option in all DIO message. Any other options, e.g. Route Information options indicating prefixes reachable through the root, worsen this situation.

RPL may further increase the probability of fragmentation of also user data traffic: for non-storing-mode, RPL employs source-routing for all downward traffic. [START_REF] Hui | An IPv6 Routing Header for Source Routes with RPL[END_REF] specifies the RPL Source Routing header, which imposes a fixed overhead of 8 octets per IP packet leaving 71 octets remaining from the MTU -from which must be deducted a variable number of octets, depending on the length of the route. With fewer octets available for data payload, RPL thus increases the probability for fragmentation of also data packets. This, in particular, for longer paths, e.g. in point-to-point traffic between sensors inside the LLN, where data packets transit through the DODAG root and are then source-routed to the destination.

V. DAO MECHANISM RPL specifies two distinct and incompatible "modes of operation" for downward traffic: storing mode, where each RPL router is assumed to maintain routes to all destinations in its sub-DODAG, i.e. routers that are "deeper down" in the DAG, and non-storing mode, where only the root stores routes to destinations in the LLN.

A. Why This Is A Critical Point

In addition to possible fragmentation, as discussed in section IV, the maximum length of the source routing header [START_REF] Hui | An IPv6 Routing Header for Source Routes with RPL[END_REF] is limited to 136 octets, including an 8 octet long header. As each IPv6 address has a length of 16 octets, not more than 8 hops from the source to the destination are possible for "raw IPv6". Using address compression [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF], the maximum path length may not exceed 64 hops. This excludes scenarios with long "chain-like" topologies, such as traffic lights along a street.

In storing mode, each RPL router has to store routes for destinations in its sub-DODAG. This implies that, for RPL routers near the root, the required storage is only bounded by the number of paths to all other destinations in the network. As RPL targets constrained devices with little memory, but also has as ambition to be operating networks consisting of thousands of routers, the storing capacity on these RPL routers may not be sufficient. Indeed, [START_REF] Ko | Evaluating the performance of rpl and 6lowpan in tinyos[END_REF] argues that practical experiences suggest that RPL in storing mode should be limited to networks of less than ∼30 routers. Aggregation / summarization of addresses may be advanced as a possible argument that this issue is of little significance -section VI will discuss why such an argument does not apply.

In short, the mechanisms in RPL force the choice between requiring all RPL routers to have sufficient memory to store route entries for all destinations (storing-mode) -or, suffer increased risk of fragmentation, and thus loss of data packets, while consuming network capacity by way of source routing through the DODAG root.

In RPL, the "mode of operation" stipulate that either downward routes are not supported (MOP=0), or that they are supported by way of either storing or non-storing mode. In case downward routes are supported, RPL does not provide any mechanism for discriminating between which routes should or should not be maintained. In particular, in order to calculate paths to a given destination, all intermediaries between the DODAG root and that destination must themselves be reachable -effectively rendering downward routes in RPL an "allor-none" situation. In case a destination is unreachable, all the DODAG root may do is require all destinations to re-issue their DAOs 3 , possibly provoking a broadcast-storm-like situation. This, in particular, as [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] does not specify DAO message transmission constraints, in particular specifies no mechanism for adapting DAO emission to the network capacity.

A final point on the DAO mechanism: RPL supports pointto-point traffic only by way of relaying through the DODAG 3 By issuing a DIO with an increased DODAG version number.

root. In networks where point-to-point traffic is no rare occasion, this causes unduly long paths (with possibly increased energy consumption, increased probability of packet losses) as well as possibly congestion around the DODAG root.

VI. AGGREGATION

As indicated in section V, in storing mode, a RPL router is expected to be able to store routing entries for all destinations in its "sub-DODAG", i.e., routing entries for all destinations in the network where the path to the DODAG root includes that RPL router.

In the Internet, no single router stores explicit routing entries for all destinations -no router has a routing table with 2 32 entries for IPv4 routing. Rather, IP addresses are assigned hierarchically, such that an IP address does not only uniquely identify a network interface, but also its topological location in the network, as illustrated in figure 2. Colloquially speaking, all addresses with the same prefix are reachable by way of the same router -which can, therefore, advertise only that prefix. Other routers need only record a single routing entry for that prefix, knowing that as the IP packet reaches the router advertising that prefix, more precise routing information is available.

A. Why This Is A Critical Point

In RPL, each RPL router acquires a number of parents, as described in section II, from among which it selects one as its preferred parent and, thus, next-hop on the path to the DODAG root. RPL routers maintain a parent set containing possibly more than a single parent so as to be able to rapidly select an alternative preferred parent, should the previously selected such become unavailable. Thus expected behavior is for an RPL router to be able to change its point of attachment towards the DODAG root. If IP addresses are assigned in a strictly hierarchical fashion, and if scalability of the routing state maintained in storing mode is based on this hierarchy, then this entails that each time a RPL router changes its preferred parent, it must also change its own IP address -as well as cause RPL routers in its "sub-DODAG" to do the same. RPL does not specify signaling for reconfiguring addresses in a sub-DODAG.

A slightly less strict hierarchy can be envisioned, where a router can change its preferred parent without necessarily changing addresses of itself and of its sub-DODAG, provided that its former and new preferred parents both have the same preferred parent, and have addresses hierarchically assigned from that -from the "preferred grandparent". With reference to figure 1, this could be e changing its preferred parent from d to c, provided that both d and c have b as preferred parent. Doing so would impose a restriction on the parent-set selection, admitting only parents which have themselves the same parent -thus, no longer having a DODAG but a simple tree, loosing redundancy in the network connectivity. RPL does not specify rules for admitting only parents with identical grand-parents into the parent set -although such is not prohibited either, if the loss of redundancy from constructing a tree is acceptable.

The DODAG root incrementing the DODAG version number is the mechanism by which RPL enables global reconfiguration of the network, reconstructing the DODAG with (intended) more optimal paths. In case of addressing hierarchies being enforced, so as to enable aggregation, this will either restrict the ability for an optimal DODAG construction, or will trigger global address autoconfiguration so as to ensure addressing hierarchies.

Finally, with IP addresses serving a dual role of an identifier of both an end-point for communication and a topological location in the network, changing the IP address of a device, so as to reflect a change in network topology, also entails interrupting ongoing communication to or through that device. Additional mechanisms (e.g. a DNS-like system) mapping "communications identifies" and "IP addresses" is requireda topic investigated, but not resolved, in the Internet 4 .

VII. BIDIRECTIONALITY HYPOTHESIS

Parents (and the preferred parent) are selected based on receipt of DIOs, without verification of the ability for a RPL router to successfully communicate with the parent -i.e. without any bidirectionality check of links. However, the basic use of links is for "upward" routes, i.e. for the RPL router to use a parent (the preferred parent) as relay towards the DODAG root -in the opposite direction of the one in which the DIO was received.

A. Why This Is A Critical Point

Unidirectional links are no rare occurrence, such as is known from wireless multi-hop networks. If an RPL router receives a DIO on such a unidirectional link, and selects the originator of the DIO as parent, that would be a bad choice: unicast traffic in the upward direction would be lost. If the router had verified the bidirectionality of links, it might have selected a better parent, to which it has a bidirectional link.

VIII. WHY NUD IS NOT A SOLUTION

[1] suggests using Neighbor Unreachability Detection (NUD) [START_REF] Narten | Neighbor Discovery for IP version 6 (IPv6)[END_REF] to detect and recover from the situation of unidirectional links between a RPL router and its (preferred) parent(s). When, e.g., a router a tries (and fails) to actually use router b for forwarding traffic, NUD is supposed engaged to detect and prompt corrective action, e.g. by way of selecting an alternative preferred parent.

NUD is based upon observing if a data packet is making forward progress towards the destination, either by way of indicators from upper-layer protocols (such as TCP) 5 orfailing that -by unicast probing by way of transmitting a unicast Neighbor Solicitation message and expecting that a solicited Neighbor Advertisement message be returned.

A. Why This Is A Critical Point

An RPL router may receive, transiently, a DIO from a router, closer (in terms of rank) to the root than any other router from which a DIO has been received. Some, especially wireless, link layers may exhibit different transmission characteristics between multicast and unicast transmissions 6 , leading to a (multicast) DIO being received from farther away than a unicast transmission can reach. DIOs are sent (downward) using link-local multicast, whereas the traffic flowing in the opposite direction (upward) is unicast. Thus, a received (multicast) DIO may not be indicative of useful unicast connectivity -yet, RPL might cause this RPL router to select this attractive router as its preferred parent. This may happen both at initialization or at any time during the LLN lifetime, as RPL allows attachment to a "better parent" at any time.

A DODAG so constructed may appear stable and converged until such time that unicast traffic is to be sent and, thus, NUD invoked. Detecting only at that point that unicast connectivity is not maintained, and causing local (and possibly global) repairs exactly at that time, may lead to traffic not being deliverable. As indicated in section VI, if scalability is dependent on addresses being assigned hierarchically, changing point-ofattachment may entail more than switching preferred parent.

Also, absent all RPL routers consistently advertising their reachability through DAO messages, a protocol requiring bidirectional flows between the communicating devices, such as TCP, will be unable to operate.

Finally, upon having been notified by NUD that the "next hop" is unreachable, an RPL router must discard the preferred parent and select another -hoping that this time, the preferred parent is actually reachable. Also, if NUD indicates "no forward progress" based on an upper-layer protocol, there is no guarantee that the problem stems exclusively from the preferred parent being unreachable. Indeed, it may be a problem farther ahead, possibly outside the LLN, thus changing preferred parent will do nothing to alleviate the situation.

IX. RPL IMPLEMENTABILITY AND COMPLEXITY

RPL is designed to operate on "RPL routers [...] with constraints on processing power, memory, and energy (battery power)" [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]. However, the 163 pages long specification of RPL 7 , describes complex mechanisms (e.g. the upwards and downward data flows, a security solution, manageability of RPL routers, auxiliary functions for autoconfiguration of RPL routers, etc.), and provides no less than 9 message types, and 10 different message options.

To give one example, the ContikiRPL implementation 8 , which provides only storing-mode and no security features, consumes about 50 KByte of memory. Sensor hardware, such as MSP430 sensor platforms, does not contain much more memory than that, i.e. there may not be much space left to deploy any application on the RPL router.

A. Why This Is A Critical Point

Since RPL is designed to be the routing protocol for LLNs, which covers all the diverse applications requirements listed in [START_REF] Martocci | Building Automation Routing Requirements in Low Power and Lossy Networks[END_REF], [START_REF] Pister | Industrial Routing Requirements in Low-Power and Lossy Networks[END_REF], [START_REF] Brandt | Home Automation Routing Requirements in Low-Power and Lossy Networks[END_REF], [START_REF] Dohler | Routing Requirements for Urban Low-Power and Lossy Networks[END_REF], it is possible that (i) due to limited memory capacity of the RPL routers, and (ii) due to expensive development cost of the routing protocol implementation, many RPL implementations will only support a partial set of features from the specification, leading to non-interoperable implementations.

X. RPL UNDERSPECIFICATION

While [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] is verbose in many parts, as described in section IX, some mechanisms are underspecified.

While for DIOs, the Trickle timer specifies an efficient and easy-to-understand timing for message transmission, the timing of DAO transmission is not explicit. As each DAO may have a limited lifetime, one "best guess" for implementers would be to send DAO periodically, just before the life-time of the previous DAO expires. Since DAOs may be lost, another "best guess" would be to send several DAOs shortly one after the other in order to increase probability that at least one DAO is successfully received.

The same underspecification applies for DAO-ACK messages: optionally, on reception of a DAO, an RPL router may acknowledge successful reception by returning a DAO-ACK. Timing of DAO-ACK messages is unspecified by RPL.

A. Why This Is A Critical Point

By not specifying details about message transmission intervals and required actions when receiving DAO and DAO-ACKs, implementations may exhibit a bad performance if not carefully implemented. Some examples are:

1) If DAO messages are not sent in due time before the previous DAO expires (or if the DAO is lost during transmission), the routing entry will expire before it is renewed, leading to a possible data traffic loss.

2) RPL does not specify to use jitter [START_REF] Clausen | Jitter Considerations in Mobile Ad Hoc Networks (MANETs)[END_REF] (i.e. small random delay for message transmissions). If DAOs are sent periodically, adjacent routers may transmit DAO messages at the same time, leading to link layer collisions. 3) In non-storing mode, the "piece-wise calculation" of routes to a destination from which a DAO has been received, relies on previous reception of DAOs from intermediate routers along the path. If not all of these DAOs from intermediate routers have been received, route calculation is not possible, and DAO-ACKs or data traffic cannot be sent to that destination.

Other examples of underspecification include the local repair mechanism, which may lead to loops and thus data traffic loss, if not carefully implemented: a router discovering that all its parents are unreachable, may -according to the RPL specification -"detach" from the DODAG, i.e. increase its own rank to infinity. It may then "poison" its sub-DODAG by advertising its infinite rank in its DIOs. If, however, the router receives a DIO before it transmits the "poisoned" DIO, it may attach to its own sub-DODAG, creating a loop. If, instead, it had waited some time before processing DIOs again, chances are it would have succeeded in poisoning its sub-DODAG and thus avoided the loop.

XI. TRICKLE CONVERGENCE

Trickle [START_REF] Levis | RFC6206: The Trickle Algorithm[END_REF] is used by RPL to schedule transmission of DIO messages, with the objective to minimize the amount of transmitted DIOs while ensuring a low convergence time of the network. The theoretical behavior of Trickle is well understood, and the convergence properties are well studied [START_REF] Levis | Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks[END_REF]. Simulations of the mechanism, such as [START_REF] Herberg | Study of Multipoint-to-Point and Broadcast Traffic Performance in the 'IPv6 Routing Protocol for Low Power and Lossy Networks' (RPL)[END_REF], confirm these theoretical studies.

In real-world environments, however, varying link qualities may cause the algorithm to converge less well: frequent message losses entail resets of the Trickle timer and more frequent and unpredicted message emissions. This has been observed in an experimental testbed: 69 RPL routers 9 were positioned in a fixed grid topology. This resulted in DODAGs being constructed with an average of 2.45 children per RPL router and an average rank 10 of 3.58.

Figure 3 shows the number of DIO messages that are emitted (counting each retransmission at intermediate routers) per interval of 10 seconds, in both the test bed and an identical scenario simulated in Ns2. The Ns2 simulation parameters were chosen to match the testbed environment, as far as possible (80 routers, 1265x1265m area, 1800s simulation time, 802.11, two-ray-ground model, 250m transmission range, no mobility, JRPL implementation [START_REF] Herberg | JRPL web site[END_REF]).

While the number of DIOs, emitted per 10 second interval in the whole network, rapidly drops in the simulation, a constant 9 MSP430-based wireless sensor routers with IEEE 802.15.4, using [START_REF] Tsiftes | Low-Power Wireless IPv6 Routing with ContikiRPL[END_REF] IPv6 stack and RPL without downward routes; the parameters of the Trickle timer were set to the implementation defaults (minimum DIO interval: 4 s, DIO interval doublings: 8, redundancy constant: 10). 10 Hop count.

A. Why This Is A Critical Point

The varying link quality in real-world environments results in frequent changes of the best parent, which triggers a reset of the Trickle timer and thus the emission of DIOs. Therefore Trickle does not converge as well for links that are fluctuating in quality as in theory.

The resulting higher control overhead due to frequent DIO emission, leads to higher bandwidth and energy consumption as well as possibly to an increased number of collisions of frames, as observed in [START_REF] Herberg | Study of Multipoint-to-Point and Broadcast Traffic Performance in the 'IPv6 Routing Protocol for Low Power and Lossy Networks' (RPL)[END_REF]. XII. LOOPS Section 7.1. describes one way in which routing loops can occur in RPL. [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] states that it "guarantees neither loop free path selection nor tight delay convergence times, but can detect and repair a loop as soon as it is used. RPL uses this loop detection to ensure that packets make forward progress [...] and trigger repairs when necessary". This implies that a loop may only then be detected and fixed when data traffic is sent through the network.

In order to trigger a local repair, RPL relies on the "direction" information (with values "up" or "down"), contained in an IPv6 hop-by-hop option header [START_REF] Hui | RPL Option for Carrying RPL Information in Data-Plane Datagrams[END_REF] of a data packet. If an "upward" data packet is received by a RPL router, but the previous hop of the packet is listed with a lower rank in the neighbor set, the RPL router concludes that there must be a routing loop and it may therefore trigger a local repair. For downward traffic in non-storing mode, the root can detect loops if the same router identifier (i.e. IP address) appears at least twice in the path towards a destination.

A. Why This Is A Critical Point

The reason for RPL to repair loops only when detected by a data traffic transmission is to reduce control traffic overhead. However, there are two problems in repairing loops only when so triggered: (i) the triggered local repair mechanism delays forward progress of data packets, increasing end-to-end delays, and (ii) the data packet has to be buffered during repair.

(i) may seem as the lesser of the two problems, since in a number of applications, such as data acquisition in smart metering applications, an increased delay may be acceptable. However, for applications such as alarm signals or in home automation (e.g. a light switch), increased delay may be undesirable.

As for (ii), RPL is supposed to run on LLN routers with "constraints on [...] memory" [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]; buffering incoming packets during the route repair may not be possible for all incoming data packets, leading to dropped packets. Depending on the transport protocol, these data packets must be retransmitted by the source or are definitely lost.

If carefully implemented with respect to avoiding loops before they occur, the impact of the loop detection in RPL may be minimized. However, it can be observed that with current implementations of RPL, such as the ContikiRPL implementation, loops do occur frequently. During the experiments described in section XI, a snapshot of the DODAG was taken every ten seconds. In 74.14 % of the 4114 snapshots, at least one loop was observed. Further investigation revealed that in all these cases the DODAG was partitioned, and the loop occurred in the sub-DODAG that no longer had a connection to the DODAG root. When the link to the only parent of a router breaks, the router may increase its rank and -when receiving a DIO from a router in its sub-DODAG -attach itself to its own sub-DODAG, thereby creating a loop -as detailed in section X.

While it can be argued that the observed loops are harmless since they occur in a DODAG partition that has no connection to the root anyway, they show that the state of the network is inconsistent. Even worse, when the broken link re-appears, it is possible that in certain situations the loop is only then repaired when data traffic is sent, possibly leading to data loss (as described above). This can occur if the link to the previous parent is reestablished, but the rank of that previous parent has increased in the meantime.

Another problem with the loop repair mechanism arises in non-storing mode when using only downward traffic: while the root can easily detect loops (as described above), it has no direct means to trigger a local repair where the loop occurs. Instead, it can only trigger a global repair by increasing the DODAG version number, leading to a Trickle timer reset and increased control traffic overhead in the network caused by DIO messages, and therefore a possible energy drain of the routers and congestion of the channel.

XIII. CONCLUSION AND POSITION

Modulo the issues presented regarding bi-directionality of links and the possibility of loops, DODAG formation, and so the multipoint-to-point route provisioning mechanism, is elegant and relatively well understood, although the difference in convergence between theory/simulation and real-world sensor network behaviors necessitates further exploration. DIO message generation/processing rules and the Trickle timers [START_REF] Levis | RFC6206: The Trickle Algorithm[END_REF] are relatively straight-forward to implement, and the state required in each router is minimal and bounded.

The DAO mechanism is what enables downward routes, bi-directional traffic flows and sensor-to-sensor flows by way of dog-leg-routing through the root, is less elegant. Problems include "underspecification", e.g. of the proper behavior with respect to DAO-ACKs and DAO retransmissions and message generation intervals, as well as two incompatible modes-ofoperation: storing mode, wherein all LLN routers are expected to have "unbounded" memory (or, at least, enough to store complete routing tables), and non-storing mode necessitating source-routing thus possibly more fragmentation and higher probability of IP packets being lost. Both of these appear to be challenging in Low-power Lossy Networks with resourceconstrained devices -as does addressing scalability concerns by way of address aggregation appear unfeasible in a such self-forming network.

Loops are a real problem in RPL, confirmed experimentally. Even in non-storing mode, where the DODAG root performs source-routing to destinations inside the LLN, loops are a problem: while they can be detected when constructing the source route, the only corrective measure that the DODAG root can take is to trigger global reconstructions of the DODAGa complete "reboot" of the LLN.

Figure 1 .

 1 Figure 1. RPL Basic Construct: DODAGs

Figure 2 .

 2 Figure 2. Addressing hierarchies in the Internet

Figure 3 .

 3 Figure 3. Trickle convergence for simulation and real world experiment

The Standards Track in the IETF consists of "Proposed Standard", "Draft Standard", and "Internet Standard", in increasing order of maturity.

• In non-storing-mode, an RPL router originates DAO messages, advertising one or more of its parents, and unicast it to the DODAG root. Once the root has received

Using a hop count metric; other metrics may require more.

The IETF LISP working group, https://datatracker.ietf.org/wg/lisp/charter/, is chartered to address this issue.

Though not called out in[START_REF] Narten | Neighbor Discovery for IP version 6 (IPv6)[END_REF], also from lower-layer protocols (such as Link Layer ACKs).

Such is the case for some implementations of IEEE 802.11b, where multicast/broadcast transmissions are sent at much lower bit-rates than are unicast. IEEE 802.11b is, of course, not suggested as a viable interface for LLNs, but serves to illustrate that such asymmetric designs exist.

Plus additional specifications for routing headers[START_REF] Hui | An IPv6 Routing Header for Source Routes with RPL[END_REF], Trickle timer[START_REF] Levis | RFC6206: The Trickle Algorithm[END_REF], routing metrics[START_REF] Vasseur | Routing Metrics used for Path Calculation in Low Power and Lossy Networks[END_REF] and objective function[START_REF] Thubert | RPL Objective Function 0[END_REF].

http://www.sics.se/contiki


Jiazi Yi
email: yi.jiazi@gmail.com

Thomas Clausen
email: thomas@thomasclausen.org

Ulrich Herberg
email: ulrich@herberg.name

Vulnerability Analysis of the Simple Multicast Forwarding (SMF) Protocol for Mobile Ad Hoc Networks

If deployments of Mobile Ad Hoc Networks (MANETs) are to become common outside of purely experimental settings, protocols operating such MANETs must be able to preserve network integrity, even when faced with careless or malicious participants. A first step towards protecting a MANET is to analyze the vulnerabilities of the routing protocol(s), managing the connectivity. Understanding how these routing protocols can be exploited by those with ill intent, countermeasures can be developed, readying MANETs for wider deployment and use.

One routing protocol for MANETs, developed by the Internet Engineering Task Force (IETF) as a multicast routing protocol for efficient data dissemination, is denoted "Simplified Multicast Forwarding" (SMF). This protocol is analyzed, and its vulnerabilities described, in this paper.

SMF consists of two independent components: (i) duplicate packet detection and (ii) relay set selection, each of which presents its own set of vulnerabilities that an attacker may exploit to compromise network integrity. This paper explores vulnerabilities in each of these, with the aim of identifying attack vectors and thus enabling development of countermeasures.

I. INTRODUCTION

Network integrity in wired, multi-hop networks is largely preserved by physically controlling access to the communications channel between routers: know thy peers, know which behavior to expect from thy peers, trust thy peers -and be able to disconnect thy peers if they show not worthy of that trust. In a MANET (Mobile Ad hoc NETwork), often operated over wireless interfaces, such is less obvious: physical access to the media between routers is not delimited by a cable, but is available to anyone within transmission range; the network topology is time-varying, either due to router mobility or due to time-varying characteristics of the channel; traffic is often retransmitted over the same wireless interface as the one over which it was received. Consequently, MANET protocols are conceived to manage conditions where less -or no -apriori structure is present between peers, and are exposed to characteristics not commonly found in classic wired networks.

This exposure also renders MANET protocol more vulnerable to attacks, although two things shall be noted. First, MANET protocols by way of their lack of a-priori infrastructure knowledge and lack of physical access control to the communications channel are simply "exposing" and rendering more easily exploitable vulnerabilities already present in classic networks (e.g., such as injecting rogue traffic in a network). Second, MANET protocols having to manage specific characteristics (e.g., retransmission of traffic on an interface over which it was received), introduces new, specific protocol mechanisms, which may be open to attacks.

A. Background and History

The "Simple Multicast Forwarding" (SMF) protocol [START_REF] Macker | Simplified Multicast Forwarding[END_REF] is a multicast routing protocol for MANET-wide efficient broadcasting, employing reduced relay sets for decreasing the number of redundant retransmissions of a data packet. Reduced relay sets so used were introduced in and standardized for IP networks by way of the Optimized Link State Routing Protocol (OLSR [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF]) in 2003, where such were used for substantially reducing the protocol overhead incurred by diffusion of routing protocol control traffic (link state advertisements, in [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] denoted "TC messages"). The reduced relay set mechanism in OLSR is based on Multi-Point Relays (MPRs) [START_REF] Qayyum | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF]. This concept was retained and used in an extension of OSPF for MANET areas [START_REF] Clausen | OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF]. The reactive MANET routing protocol AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] also uses MANET-wide broadcast of its control traffic (route requests). [START_REF] Clausen | Optimizing Route Length in Reactive Protocols for Ad Hoc Networks[END_REF] showed that using MPRs for flooding such control traffic resulted not just in reduced channel load, but also in shorter unicast paths. Other experimental routing protocols, including [START_REF] Ogier | Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)[END_REF] and [START_REF] Ogier | Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding[END_REF], have used different relay set selection mechanisms, and the Internet Engineering Task Force (IETF) is standardizing the MANET routing protocol OLSRv2 [START_REF] Clausen | The Optimized Link State Routing Protocol version 2[END_REF], retaining the MPR concept.

The success of such reduced relay sets for protocol control traffic diffusion lead to investigations into using such also for user data traffic, including [START_REF] Jacquet | Diffusion mechanisms for multimedia broadcasting in mobile ad hoc networks[END_REF] and [START_REF] Clausen | Investigating data broadcast performance in mobile ad-hoc networks[END_REF], ultimately leading to the IETF proposing development of SMF [START_REF] Macker | Simplified Multicast Forwarding[END_REF] as an experimental protocol.

B. SMF Overview

SMF provides basic IP multicast routing for MANETs. It consists of two main components: multicast "Duplicate Packet Detection" (DPD) and "Relay Set Selection" (RSS).

1) Multicast Duplicate Packet Detection (DPD): DPD is used as part of the forwarding process to check if an incoming packet has been previously received (and forwarded)and therefore should be dropped -or not. In MANETs, as illustrated in figure 1, duplicate packets are a common fact of life: router n1 is retransmitting a broadcast packet received from router n0 on the same interface as the one over which it was received, so as to ensure receipt also by router n2causing router n0 to receive the packet a second time. DPD is achieved by a router maintaining a record of recently processed multicast packets, and comparing received multicast packets herewith. A duplicate packet detected is silently dropped and not inserted into the forwarding path of that router, nor delivered to an application. DPD, as proposed by SMF, supports both IPv4 and IPv6 and for each suggests two duplicate packet detection mechanisms: 1) header content identification-based DPD (I-DPD), using packet headers, in combination with flow state, to estimate temporal uniqueness of a packet, and 2) hash-based DPD (H-DPD), employing hashing of selected header fields and payload for the same effect.

2) Relay Set Seletion: RSS produces a reduced relay set for use when relaying information across the MANET. SMF supports the use of several relay set algorithms, including E-CDS (Essential Connected Dominating Set), S-MPR (Sourcebased Multi-Point Relay), or MPR-CDS. Those algorithms are based on localized election, derived from those explored for efficient topology diffusion in MANET routing protocols.

C. Statement of Purpose

While multicast protocols and efficient flooding mechanisms are well studied for performance and convergence properties, little work considers also security issues and implications of the protocols in use -which assume that the routers in the networks can be "trusted" to perform properly. In any deployment scenario, however, this assumption cannot be taken at face value: the "accessibility" of a wireless communications channel may open access to malicious routers attempting to participate in the network -or an otherwise non-malicious router may simply be misconfigured.

If deployments of MANETs are to become common outside experimental settings, protocols operating in such networks must be resilient to such malice or misconfiguration. A first step towards such resilience is to understand the vulnerabilities of a given protocol and identify probable attack vectors hereon.

This paper analyses SMF in order to understand its vulnerabilities. Various threats, from accidental misbehavior of routers or from intentionally malicious attackers, are studied, and threat sources, threat actions, threat consequences, etc. are explored. While the study is generally based on SMF, the components of SMF, such as duplicate packet detection and relay set selection, are common in other multicast routing protocols, and may therefore be also more generally applicable.

While the paper has the ambition of being thorough, in matters of security it is prudent to be explicit to not claim completeness of an analysis.

D. Paper Outline

The remainder of the paper is organized as follows. In section II, threats to DPD are first discussed. Possible attacks to the Relay Set Selection Vector (RSSV), which is used for identify different types of RSS algorithms, are presented in section III. The general threats to RSS are presented in section IV. The paper is concluded in section V.

II. THREATS TO DUPLICATE PACKET DETECTION

The DPD mechanism is based on a unique identity check of the incoming packets. A router needs to record a history of processed multicast packets so as to ensure that a given packet is processed and forwarded at most once -which entails that such history must be maintained for at least the maximum network traversal time of a packet. However, neither IPv4 nor IPv6 contains mechanisms for uniquely identifying a given packet. SMF introduces two mechanisms compensating this: I-DPD and H-DPD. This section discusses attacks on each of these, as well as the consequences on protocol operation that such may have.

A. Identification-based DPD (I-DPD)

For I-DPD, a DPD identifier in the packet header is used for identification of a packet. In case of fragmented packets, and packets using IPsec, the contained fragment and packet sequence numbers can be used. When neither is present, an additional identifier in the packet header is needed. SMF proposes an IPv6 header option to this effect, recognizing that adding such IP packet header information is not supported for IPv4.

The identification of a packet is, then, based on the source IP address and the sequence number (from IPsec, fragment number or header option). In this way, when each intermediate router receives a packet, it can determine if the packet has been received before.

1) Pre-play Attack: If a malicious router can obtain the (source IP, sequence number) of a packet, it can inject (invalid) packets with exactly the same identification information into the network. As such an invalid packets propagates through the network, if arriving before the valid packet with same identification information, this valid packets will be discarded as a duplicate. If further sequence numbers are predictable, a malicious router can inject invalid packets with valid sequence numbers in advance, ensuring that subsequent valid packets are discarded as duplicates. Figure 2 illustrates an example of a pre-play attack. Router a is the source and generates a multicast packet with sequence number n. When the malicious router X receives the packet, it injects an invalid packet with the same sequence number n. Routers which receive the invalid packet first will discard subsequent arrivals of the valid packet. The consequence hereof depends on the network topology: as depicted in figure 2, the attack might not affect routers that are farther away from the malicious router than they are from the source router (i.e., routers e and h), as the valid packet might reach those routers first. For routers closer to the attacker than to the source (i.e., router g and f ), the invalid packet will be received first, causing subsequently arriving valid packets to be dropped. For routers with equal distance (router c and d), it depends on the link status and the transmission of the routers. When the succession of sequence numbers from a source is predictable, a malicious router can, upon having observed a valid packet being generated by a legitimate router, conduct a pre-play attack by injecting invalid packets with not-yet-usedbut-soon-to-be-used sequence numbers. As shown in figure 3, if an incremental algorithm is used for generating sequence numbers, X can thereby prohibit corresponding valid packets from attaining the part of the network reachable from X without passing through a. The following packets from a with seq = n + 1, seq = n + 2, etc, will be regarded as duplicate packets and discarded. Another possible pre-play attack is based on the Time-to-Live (TTL) or hop limit field 1 . As routers only forward packets 1 Henceforth, TTL is used indiscriminately for both TTL and hop-limit.

with T T L > 1, a malicious router can forward an otherwise valid packet, while drastically reducing the TTL hereof. This will inhibit recipient routers from later forwarding the same multicast packet, even if received with a different TTLessentially a malicious router thus can instruct its neighbors to block forwarding of valid multicast packets. As the TTL of a packet is intended to be manipulated by intermediaries forwarding it, classic methods such as signatures are typically calculated with setting TTL fields to some pre-determined value (e.g., 0) -such is for example the case for IPsec Authentication Headers' [START_REF] Kent | IP Authentication Header[END_REF] -rendering such an attack more difficult to both detect and counter. If the malicious router has access to a "wormhole" through the network (a directional antenna, a tunnel to a collaborator or a wired connection, allowing it to bridge parts of a network otherwise distant) it can make sure that the packets with such an artificially reduced TTL arrive before their unmodified counterparts. Figure 4 illustrates an example of this attack, with X being the malicious router. On receiving a packet with T T L = 63 and seq = n, X broadcasts the same packet, but with an artificially reduced T T L = 1. For routers near X, such as c, d, and e, if they receive the packet with the artificially reduced TTL before the valid packet arrives, the valid packet will be discarded. If a wormhole between X and a distant router i exists, X can inject the packet with the artificially reduced TTL to i, and to the part of the network reachable through iwhich would subsequently discard later arriving valid packets. 2) Sequence Number Attack: In a pre-play attack, a malicious router makes use of the DPD mechanism to force other routers to discard otherwise valid packets -thus preventing these from reach parts of the network. A malicious router can also seek to disable DPD, by modifying the sequence number in packets that it forwards. Thus, routers will not be able to detect an actual duplicate packet as a duplicate -rather, they will treat them as new packets, i.e., process and forward them. The consequence of this attack is an increased channel load, the origin of which appears to be a router other than the malicious router.

In figure 5, when the malicious router X receives the packet (seq = n) from router a, it simply modifies the sequence number to n + i, and sends it back to the network. Router c will not be able to detect the duplicate packet, which should be discarded. . Sequence number attack. X is the malicious router and modifies the sequence number to disturb duplicate packet detection [START_REF] Macker | Simplified Multicast Forwarding[END_REF] proposes use of IPsec sequence numbers as packet identifiers. If IPsec is used, authentication and integrity of the packets is usually assumed protected. In a MANET environment, the usage of IPsec is still not well defined -problems include key distribution mechanisms, suitable cryptographic algorithms and the use of IPsec for multicast. Furthermore, to the best of the authors knowledge, few deployments of MANETs employ IPsec. Therefore, this paper does not consider the usage of the IPsec options as presented in [START_REF] Macker | Simplified Multicast Forwarding[END_REF].

B. Hash-based DPD (H-DPD)

In H-DPD, a hash of the non-mutable header fields, options fields and data payload is used as identifier of a packet, replacing explicit sequence numbers. Each packet is, thus, uniquely identified by the IP address of the source of the packet, and this hash-value. When a source host generates a packet, or when a gateway ingresses the packet into the MANET, it calculates the hash-value hereof. In case the source host or gateway identifies that it recently has generated or injected a packet with the same hash-value, it inserts a "Hash-Assist Value (HAV)" IPv6 header option into the packet, shown in figure 6, generated such that calculating the hash also over this HAV will render the resulting value unique. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1| Hash Assist Value (HAV) ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Note that the hash value in SMF is applied only to provide a low probability of collision, and is specifically not used for cryptographic or authentication purposes. Also note that threats, similar to those discussed in section II-A continue to apply for when using H-DPD. One advantage of H-DPD over I-DPD may be, however, that as the hash-value is calculated also over the data payload of the packets, predicting subsequent hash-values and conducting a pre-play attack is somewhat harder.

Introducing a header option, however, also introduces a potential vulnerability: the HAV header option is only used when the source or the ingressing router detects that a previously generated packet has an identical hash value as this packet. A malicious router which discovers the existence of a HAV header in a packet can therefore conclude that a hash collision is possible if the HAV header is absent. Thus, it needs to simply remove the HAV header before retransmitting the packet, which may cause the packet to be dropped by recipients. Again, in doing so the malicious router causes the packet to be dropped not by itself, but by other routers in the network.

As shown in figure 7, a is the source router and X is the malicious router. At the source a, it generates a packet p, and stores the corresponding hash h(p) = x in its DPD cache. The following packet p generated, has the same hash as the previous packet, i.e. h(p ) = h(p) = x. The source router a is able to detect the hash collision by comparing it with the records in its DPD cache. Therefore, a adds an HAV header as shown in figure 6, to avoid a possible collision by having a new hash value h(p + HAV ) = x . When the malicious router X receives packet p , it can conclude that a collision might happen by removing the HAV header. On receiving packet p at router b, a record with hash h(p) = x is saved in the DPD cache. The consequence is that packet p cannot be distinguished by router b after the HAV header being removed because it has the same hash h(p ) = x. Similarly, a malicious router can disrupt DPD by adding an HAV header option to a packet. This modified packet cannot produce the same hash value as the original packet, so it cannot be detected as a duplicate packet. This is similar to the attack in I-DPD, where a malicious router can change the sequence number for the same effect.

In figure 8, router a forwards the packet p with h(p) = x to router b and x. The malicious router X, instead of forwarding the original packet unmodified to b, adds an HAV header option with hash h(p+HAV ) = x = x. The router b is unable to detect the duplicate packet and processes and forwards it as a new packet.

Another possible attack for a malicious router is to transmit many packets with identical payload and IP header within a short time interval ("beacons"). This has several implications when H-DPD is used: (i) similar to a "jamming" attack, the increased load on the channel may lead to increased number of collisions of data and control traffic packets. (ii) An (adjacent) router receiving such a beacon has to calculate and add a HAV header option to the packet header. This operation is time-consuming, and the packet has to be stored while the header option is generated. If a large number of beacons is received by a router, memory and CPU resources may thus be exhausted by this "Denial of Service" attack. (iii) When a packet is retransmitted by the adjacent router, an entry is stored in the hash cache for some amount of time. A large number of beacons within a short time may lead to an overflow of that buffer. Depending on what cache management is used, olderpossibly "legitimate" -hash entries may be dropped from the cache, leading to an effective deactivation of the hash-based DPD mechanism.

III. THREAT TO RELAY SET SELECTION VECTOR (RSSV)

Reduced Relay Set Selection (RSS) in SMF is achieved by distributed algorithms that dynamically calculate a topological Connected Dominating Set (CDS). Such algorithms are generally based on the presence of a neighbor discovery protocol, such as the "Neighborhood Discovery Protocol" (NHDP) [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF], providing 1-hop and 2-hop neighborhood information. The relay set is then computed by using one from among a set of possible algorithms, such as E-CDS, S-MPR, etc. These algorithms are not interoperable, hence routers in a MANET must communicate to their neighborhood which algorithm(s) they respectively support. To this end, [START_REF] Macker | Simplified Multicast Forwarding[END_REF] defines a "Relay Set Selection Vector" (RSSV), by way of message and address block TLVs [START_REF] Clausen | Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF] to be used with the NHDP HELLO message exchange, allowing a router to declare which RSS algorithms it and its immediate neighbors support 2 .

In SMF, two TLV types are defined for RSS algorithms:

• An SMF message TLV type, which is used to identify the existence of an SMF instance operating in conjunction with NHDP. • An SMF address block TLV type, which is used to share the RSS algorithm configuration information among 2hop neighbors. In both TLVs, a value is assigned to represent each RSS algorithm.

A. RSSV Spoofing

Given the fact that there may be different RSS algorithms operating concurrently in the same network, a router will have to select relay sets according to compatibility of the algorithms operating in its immediate and 2-hop neighborhoods. A potential attack is, therefore, if a router -intentionally or otherwise -share false RSSV information for itself or for its neighbors.

For example, in figure 9, router a is about to select its relays. The following RSS algorithms are used in different routers:

• E-CDS: router b, d, e

• S-MPR: router c, f, g • MPR-CDS: router h All routers, faithfully, declare their RSSV. Based on the messages from routers b, h and c, router a learns what algorithms are supported by both its direct neighbors and its 2-hop neighbors. This allows router a to observe that while router h provides topological coverage to all of the 2-hop routers (d, e, f, g), router h runs an RSS algorithm different from all of d, e, f, g. Therefore, if a selects h as relay, h may not be able to select relays among d, e, f, g and thus packet forwarding beyond d, e, f, g would not happen. Router a also learns that router b runs the same RSS algorithm as the 2hop neighbors d, e, reachable via b -and that router c runs the same RSS algorithm as the 2-hop neighbors f, g, reachable via c. Router a can therefore select b and c as relays, knowing that both of these will be able to not only provide coverage to all 2-hop neighbors, but also be able to select proper relays among these 2-hop neighbors. A malicious router, spoofing the RSSV of its 2-hop neighbors, is shown in figure 10: X declares itself with RSSV=MPR-CDS in message TLVs, and further declares that d, e, f, g have RSSV=MPR-CDS. Thus, router a will choose X as sole relay: from the information available to a, X provides optimal topological coverage of the 2-hop neighborhood -and by running the same RSS as (declared for) all 2-hop neighbors, should be able to also do proper relay set selection with these. As a consequence, X will "take control" of the multicast traffic in its neighborhood -in this case, be able to prohibit b and c from being selected as relays and, thus, if X isnot actually forwarding traffic or performing RSS, disrupt network connectivity.

Finally, X might simply declare that all other routers have (only) RSSV=CF, classical flooding, thus degrading the network performance to that of a simple flooding domain.

B. RSSV Indirect Jamming

In a neighbor discovery based mechanism, a malicious router can intentionally and frequently alter the information declared -including the RSSV -so as to cause generation of inordinate amounts of control traffic by legitimate routers. Such indirect jamming is discussed in [START_REF] Herberg | Security Issues in the Optimized Link State Routing Protocol Version 2 (OLSRV2)[END_REF] for neighborhood discovery and link state advertisement, and also applies for the RSSV, which a malicious router may alter and signal frequently, causing its neighborhood to launch (possibly computationally intensive) RSS recalculations and signal selected relay set (causing increased channel occupation) as well as the change of its neighbor's status.

As shown in figure 11, the malicious router X first declares itself as RSSV=E-CDS at t 0 . Router a will signal the change of its neighbor in its HELLO message at t 1 upon receiving the message from X. In a relatively short time, X advertises in a HELLO that RSSV=S-MPR, and a link to another router b at t 1 . When a receives this message at t 2 , it will believe that X has changed its status, then calculate its MPR set and broadcast a new HELLO message. The above action can be repeated to consume the power of a and the bandwidth. IV. THREATS TO RELAY SET SELECTION [START_REF] Macker | Simplified Multicast Forwarding[END_REF] provides a framework for RSS, without requiring the use of any specific RSS algorithm. This section will, therefore, not explore the vulnerabilities of a specific RSS algorithm, but rather general threats to the framework of SMF relay set selection.

A. Eavesdropping

Eavesdropping is a common and easy passive attack in a wireless environment. Once a packet is transmitted, any suitable transceiver can potentially obtain a copy, for immediate or later decoding. Neither the source nor intended destination can detect this. As previously indicated, SMF uses a neighborhood discovery protocol for providing each router with 1-hop and 2hop topological information. A malicious router can eavesdrop on the NHDP message exchange and thus learn this local topology information, as well as some source and destination addresses of data packets transmitted.

Eavesdropping will not have direct threat to the network nor to SMF, but it can provide crucial network information such as identity of communicating routers, link characteristic, router configuration, etc., enabling other attacks.

B. Message Timing Attack

As NHDP is used to make relay set selection decisions, vulnerabilities of this protocol also affect SMF operation. NHDP control messages define two types of timing information:

• Validity time, the time upon receipt during which the information contained within the message should be considered valid. • Interval time, the time after which the next control message from the same router should be expected. For validity time, since information contained in control messages is considered valid only for the duration indicated, an attacker can simply eavesdrop on NHDP messages from its neighbors, then instantly replay a received such message -but modified to have a low validity time, illustrated in figure 12. Router b broadcasts a HELLO message with valiT ime = 6s. Router a receives the messages and marks the link between itself and b is valid for 6 seconds. X eavesdrops on the messages, obtains the identity of router b, then transmits the HELLO message with valiTime=0.1s. Receipt of this message by a causes a to replace previously received link information, and therefore consider the link between itself and b as invalid after very short time (0.1 second). For SMF, this means that b will not be selected as relay by a even it may provide good connectivity to other parts of the network. A similar threat is possible using the interval time, where a malicious router can behave as described above and also indicate a low interval time. The recipient of this message will expect a subsequent control message within this very short time -which will not arrive. As a consequence, the recipient decreases the link quality, or may even discard this link. Further vulnerabilities to the NHDP exist in uni-cast routing protocol also, as described in [START_REF] Herberg | Security Issues in the Optimized Link State Routing Protocol Version 2 (OLSRV2)[END_REF].

C. Multicast Disruption

RSS algorithms are based on a router having topological information describing its 1-hop and 2-hop neighborhood. Thus, a malicious routers can spoof the links to or identities of other routers in the network, and thus disrupt connectivity and prevent multicast traffic from reaching parts of the network. Figure 13 gives an example hereof, by way of link spoofing. The malicious router, X, eavesdrops on NHDP control traffic, and learns of the existence of e and f as 2-hop neighbors by way of b and c, respectively. X itself participates in NHDP, however declares (spoofs) in its control messages that it, too, has links to all neighbors of b and ci.e.,declares the dotted links in figure 13. When a is to select relays, it will choose X as its relay -X which may, then, simply not re-transmit any multicast traffic received and thereby disconnecting e and f from a. A similar attack is possible by way of identity spoofing, as indicated in figure 14. The malicious router, X, eavesdrop on NHDP control traffic and learns of the existence of c as a 2-hop neighbor by way of b. X itself then commences participating in NHDP, but presenting itself under the same identity as bthus a will see c as a direct neighbor and not select b as relay. As a consequence, c is not able to receive multicast traffic, again being disconnected from the network.

D. Broadcast Storm

In MANETs, a broadcast storm caused by classical flooding is a serious problem because radio signals of two or more adjacent routers transmitting at the same time are likely to overlap. This can result in redundancy, contention and collisions [START_REF] Tseng | The broadcast storm problem in a mobile ad hoc network[END_REF]. Avoiding broadcast storms is one of the reasons why RSS algorithms are used -in SMF as well as in routing protocols such as [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF].

In contrast to the attacks described in section IV-C, a malicious router may attack an SMF network by attempting to degrade RSS so as to produce classic flooding, illustrated in figure 15. Bold lines with arrows present the intended multicast traffic if the RSS algorithm run properly: b, d, f, h are selected as relays by a, and c, e, g, i just receive packets from a without forwarding.

A malicious router X may disrupt this by overhearing NHDP control traffic, thus learning of the 1-hop neighborhood of a. X may, then, generate control messages performing both identity spoofing and link-spoofing, pretending to be one of the 1-hop neighbors of a (e.g., any or all of b, c, d, e, f, g, h, i) and declare that links to non-existing routers e.g., z, x, y, v, w exist for these, causing a to select more (or all) of its 1-hop neighbors as relays, degrading into classic flooding.

X may overhear control messages from some of the 1-hop neighbors of a and thus learn of their 2-hop neighborhoods -and spoof links that it thus knows are non-existing. Such would be the case for f and g, for example. For b and i, X may not know what their 2-hop neighbors are, however may "make an educated guess" when selecting links to spoof. While this reduces network performance by disabling RSS and producing classical flooding, the effect of this attack is only local. Except if X has accomplices throughout the network, b, c, d, e, f, g, h and i likely will be able to select proper relay sets.

V. CONCLUSION

This paper has analyzed vulnerabilities of the "Simple Multicast Forwarding" (SMF) Protocol for Mobile Ad Hoc Networks. In addition to vulnerabilities inherited from its use of NHDP for acquiring local topology information allowing reduced relay set selection, SMF introduces two Duplicate Packet Detection mechanisms, each introducing additional vulnerabilities: disrupting network connectivity, as well as allowing a malicious router to incite other routers to produce unnecessary packet re-transmissions -thereby consuming precious channel resources.

SMF also provides a framework for enabling different relay set selection algorithms, to be used within SMF. As such algorithms may not be interoperable, this framework introduces a signaling mechanism (RSSV) whereby a router shares the algorithms it support itself -as well as the algorithms supported by its neighbors. Intended to allow a router to select its relays such that the RSS algorithms of these are compatible with algorithms of its 2-hop neighbors, the RSSV also allows a malicious router to present conflicting or incorrect information, skewing relay set selection and possibly disrupting network connectivity.

Using NHDP for acquiring local topology, SMF inherits vulnerabilities of NHDP, such as eavesdropping, message timing attack, which are also common in uni-cast protocols. Additionally, SMF also introduces vulnerabilities by way of , link spoofing, node spoofing, etc., allowing a malicious router to provoke connectivity disruption or a broadcast storm by degrading even RSS behavior to classical flooding.

Figure 1 .

 1 Figure 1. The need for duplicate detection: retransmission over the same interface as a packet was received.

Figure 2 .

 2 Figure 2. Pre-play attack: X is a malicious router, which generates invalid packets with valid sequence numbers.

Figure 3 .

 3 Figure 3. Pre-play attack by predicting sequence number. X is a malicious router, which generates invalid packets with predicted sequence number.

Figure 4 .

 4 Figure 4. Pre-play attack based on TTL values. X is the malicious router which forwards the packets with reduced TTL values.

Figure 5

 5 Figure 5. Sequence number attack. X is the malicious router and modifies the sequence number to disturb duplicate packet detection

  -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... |0|0|0| OptType | Opt. Data Len | +-

-+Figure 6 .

 6 Figure 6. The Hash Assist Value header option in H-DPD mode

Figure 7 .

 7 Figure 7. Attack based on the HAV field: The malicious router X produces a hash collision by removing the HAV field.

Figure 8 .

 8 Figure 8. Attack by adding a HAV header option: The malicious router X disables duplicate packet detection by adding a HAV header option.

Figure 9 .

 9 Figure 9. Relay set selection considering RSSV: Router a makes the decision based on the RSSV declared by TLVs.

Figure 10 .

 10 Figure 10. Attack on the RSSV to disrupt the relay set selection: The malicious router X spoofs the RSSV of d, e, f, g.

Figure

  Figure Indirect jamming in RSSV:The malicious router X changes the declaration of its RSSV frequently to make router a generate more control traffic.

Figure 12 .

 12 Figure 12. Validity timing attack: The malicious router X spoofs b and declares a short validity time of the link.

Figure 13 .

 13 Figure 13. Multicast disruption by link spoofing: X spoofs the link to e and f.

Figure 14 .

 14 Figure 14. Multicast disruption by node spoofing. X spoofs the identify of router c to wipe c from the multicast domain

Figure 15 .

 15 Figure 15. The broadcast storm attack: The bold line with arrow represents normal multicast traffic, and the dashed line the redundant traffic caused by having all the 1-hop neighbors of a be selected as relays.

While several RSS are supported in the same network, it is not clearly specified in the current revision of SMF[START_REF] Macker | Simplified Multicast Forwarding[END_REF] whether a router can concurrently support several different RSS at the same time.