Fabien Dagnat
email: fabien.dagnat@telecom-bretagne.eu

Gwendal Simon
email: gwendal.simon@telecom-bretagne.eu

Xu Zhang
email: xu.zhang@telecom-bretagne.eu

Toward Decentralized Package Management

The mutation of the software economy toward crowdsourcing, the explosion of the number of devices and the increasing need for quickly-released software call for revisiting the way software are deployed and managed. The current approach adopted by most software package management systems is to rely on a single distributor, who collects packages from upstream sources, tests, releases and distributes them through a centralized channel, called repository. In this paper, we identify the major downsides of this centralized architecture and promote a distributed approach for software deployment. That is, in a network consisting of interconnected symmetric peers, all the developers are allowed to release and distribute software asynchronously. The discovery and retrieval of software is achieved through the communication among peers. We highlight the impacts of using such an approach and define a specific format of metadata that supports distributed package release.

Introduction

The size of the free and open source software community (two millions sourceforge users 1 ) and the number of application store developers (90, 000 so far 2 ) illustrate the importance of crowdsourced software, i.e. software produced by a large number of loosely coordinated developers. At least two statements explain the sustained growth of crowdsourced software.

1. crowdsourced software has become a key economical argument. Apple typically takes advantage of the number of third-party applications available exclusively on its devices. The capacity to offer, as fast as possible, the largest and most diverse set of software is a critical need.

2. crowdsourcing enables fast and customized software evolution. Free software producers often distribute their programs in the form of source code, so that any developers having enough expertise can improve their functionalities according to users' need.

However, the deployment of crowdsourced software is a frustrating and error-prone task. Modern software is generally composed by a large number of inter-dependent components, called packages. A package can run correctly only when all its dependency requirements are satisfied and all the configurations are done properly. Installing or upgrading a package can break other packages or lead to unexpected performance of the system. The global consistency of a software distribution is extremely hard to maintain when the packages are independently produced. Facing this issue, the approach adopted by current large systems such as the GNU/Linux distributions is to rely on a single distributor, who collects packages from upstream sources, approves them and publishes them together in a repository. Such centralized architecture enables the distributor to manage packages within a bounded space, so that the consistency of the composition of packages can be optimized [START_REF] Mancinelli | Managing the Complexity of Large Free and Open Source Package-Based Software Distributions[END_REF].

In this paper, we argue the repository-based approach can not fulfill the need of crowdsourced software deployment. It exhibits some majors drawbacks that are intrinsically contradictory to the idea of crowdsourcing:

• managing a large repository for crowdsourced software is expensive. A recent analysis show that it costs Apple approximately $1.3 billion per year to run iTunes and its App Store. The investment is still increasing as more capacity is required to face the growth of software content. 3 • relying on a single distributor is a supplier-side approach while software has become a fast moving consumer good (FMCG). Flexible and on-demand evolution is a highly desired feature offered by crowdsourced software. But the centralized administration leads to censorship which limits the degree of liberty developers can have. On the Web, it is common to see open platform developers complain about arbitrary software selection rules or unreasonable distribution fees. 4 • approving and releasing third party software through a single channel is time consuming. It increases the time-to-market and degrades the availability of the newest products. Users are facing security risks due to delayed updates or bug fixes. 5 Many open source distributions have timebased release cycles, which are scheduled at slow pace. For Debian, the time between two consecutive releases is approximately 18 -24 months. Even packages in the unstable repository are continuously uploaded from the upstream sources, a large amount of users would prefer to install the stable distribution, which contains secure but obsoleted packages.

• repository-based approach can not fix the dependency hell. Maintaining the global consistency of the repository is not a scalable solution. To reduce the complexity of dependency resolution, GNU/Linux distribution repositories limit their number of packages (12,000 packages in average 6 ). Mobile application stores have larger scale (200,000 for Android Market and 300,000 for the App Store 7 ), but they do not handle package dependency at all. Packages on these platforms are generally self-contained small bundles. They are rarely allowed to declare dependency on others packages or no dependency check is done by the repository maintainer.

• repositories implies "boundaries" on software. Currently one repository (distributor) serves uniquely for one specific type of device or operating system. For instance, the iPhone App Store does not distribute applications for the Android Market. However, in the future Internet of Things, zillions of general hardware devices running heterogeneous software systems will be interconnected. Boundaries will disappear one day or another. It is important to have a uniform but scalable approach for deploying all kinds of packages.

• the dependence on a single point is an undesired property for both package storage and distribution. Users may be unable to upgrade their packages if the repository hosting the software stops providing the service. As a conclusion, the central repository is a key limitation in the distribution and management of crowdsourced packages. To tackle the drawbacks listed above, this paper promotes using distributed approach for package management. We imagine a network consisting of interconnected symmetric peers, atop which all the developers are allowed to publish and distribute new packages and updates at anytime. Both the release and delivery of packages should be handled in a decentralized way. As a beginning of our work, this paper only describes the original idea. We identify the major changes that should be made to support distributed package release and propose a new metadata format needed for decentralized upgrade. At last, a blueprint of our future work is presented.

Impacts of Decentralization

Building a repository-less package management system (PMS) raises a number of open issues, as all the tasks of developing, managing, and deploying software are distributed across peers in the network. We define a peer as any device with a computational capacity, including servers, personal computers, mobile handsets, wireless sensors and any programmable object in the Internet of Things. In this paper, despite the heterogeneity of the population, we consider that all peers are symmetric in terms of functionalities and the roles they play in the software production life-cycle. A peer is not only a producer who creates, tests, releases and distributes packages, but also a consumer who uses software build from packages. Compared to conventional PMS, a repository-less approach differs in the following concerns.

• decentralized software evolution: the idea we would like to explore is that any peer should be able to release new versions of packages at any time. This statement will probably launch a wide debate among developers. Indeed, in component-based software, the communication between interdependent packages is hard coded into the source code and the binding is based on the component's name. Even if packages can explicitly specify dependency in their metadata, we can't guarantee the completeness of this information provided by untrusted third parties. An elegant method for dependency management is still lacking. But anyway, this issue also exists in repository-based PMS. As we will refer later, some research works has already been initiated to address it.

• upgrade without total order: in a centralized PMS, the version number of a package is conventionally encoded using an integer or a date denoting the total order among versions. This no longer works for distributed PMS as packages are produced independently and asynchronously, creating distinct branches in the evolution history. That is, neither the order is total, nor the version identifier uniqueness can be guaranteed. Hence, a new version encoding scheme must be proposed. It needs to be mentioned that, in current FOSS distributions, packages already have tree-like evolving histories. Once a package is distributed in an official release, it needs to be maintained independently from the development line. At this point, a distinct upgrading branch is derived. In the Debian bug tracking system, the whole evolution history of a package is recorded in the change log so that the branches of versions can be tracked. However, this information is not contained in the package metadata and the meta-installer has no mean to distinguish versions in different branches.

• policy free release management: releasing software independently is easy when dealing with selfcontained small packages maintained by individual or small group of developers. However for larger projects like Debian, GNOME and OpenOffice, the production life-cycle relies on the coordination of a large number of volunteers 8 . Releases continually produced by untrusted outsiders of the projects will inevitably impact the project's image, even under the assumption that they are all certified to have enough quality and do not violate any dependency on the official packages. Hence, they should be signed and distinguished from the official releases. A project can still maintain its own repository and release policy. The repository is however considered as a powerful peer, which has no privileged authority over other peers.

• distributed data storage and retrieval: packages are stored on peers across the network. Searching and delivering packages should be achieved through the coordination of peers. Packages should not be removed immediately after being unpacked as done in most Linux operating systems. To guarantee fast and reliable retrieval, non-installed packages need also to be cached. No repository means no central point to consult for new package upgrades. The discovery (notification) of new product should be driven by user's interest. In this content, social networks of users and products should arise and become the support of modification propagations.

Related Works

To the best of our knowledge, no previous studies have discussed the overall approach for distributed package management. But each of the aspects mentioned above has been addressed seperately. [START_REF] Mancinelli | Managing the Complexity of Large Free and Open Source Package-Based Software Distributions[END_REF] describes a repository-based dependency management approach. The authors formalized the problem of testing whether a package is installable within a collection of packages. They model each package dependency as boolean variable whose value specifies whether it is installed. The installability of a package therefore can be verified by testing the conjunction of all its dependencies. The complexity of solving such a SAT problem is NP-complete and is time consuming when the repository is large. Nix [START_REF] Dolstra | Efficient upgrading in a purely functional component deployment model[END_REF] is a purely functional component deployment tool, it allows different versions of a same component to be installed side-by-side, thus supports non-destructive upgrade. Components are unpacked into isolated directories, which are indexed using the cryptographic hashes of all the inputs needed to build and run them. By doing so, Nix guarantees the completeness of dependencies specification and avoids interference between components sharing common dependency. However, the problem of decentralized upgrade is not covered in this work. In [START_REF] Oreizy | Decentralized software evolution[END_REF], the authors propose an architectural-based approach to enable decentralized software evolution. They use connectors as communication routers to bind components, which enables changing the binding decisions without altering the components. As architectural descriptions only focus on the high level structural view of component, they are not expressive enough to reflect physical constraints on components and the environment. At last, [START_REF] Van | Continuous release and upgrade of component-based software[END_REF] highlights the importance and difficulty of continuously releasing updates to users. It presents an algorithm that automatically generates incremental updates from build and testing processes. This approach requires all the dependencies and reverse dependencies of the packages to be known, thus can't be extended to repository-less deployment.

A Metadata Format for Decentralized Upgrade

In this section, we formally define the essential metadata needed for distributed package management. Instead of using a pair of name and version number, we use the cryptographic hash of the package data as its identifier. The package's entire evolution history is contained in the metadata. By using Bloom filters, two package histories can be compared efficiently to decide whether one package is an upgrade of the other.

Definition 1. A package p is a pair (pid, vid) where p.pid encodes the family of the package and p.vid identifies its version.

A sufficiently long hash (e.g. the 128 bit MD5 cryptographic hash) of the binary package data can be used as the vid to ensure its uniqueness. A package can be identified by using only the vid; the pid is however needed for denoting a group of packages derived from a single root. Without version identifier in a total order, the inheritance relation among packages can't be explicitly extracted from the vid. Definition 2. The replace relation between two packages p and q, noted p ≻ q, means that the package p (respectively q) is a direct successor of q (resp. ancestor of p).

A given package can have several successors if new packages are concurrently released. In order to prevent an explosion of release branches, we also support merging several package versions, i.e., having several replace relations in the same package. Note also that replace can also implement a subsumption relation, that is a package p can replace a package q with p.pid = q.pid. The evolution history is thus represented by a Directed Acyclic Graph (DAG). Definition 3. The history DAG of a package family P is the directed graph G P = (V, E) such that V contains (i) all packages p with p.pid = P and (ii) all packages q with p ∈ V and p ≻ q. A directed edge

(q → p) in E is equivalent to p ≻ q.
With the subsumption relation, the history DAG can have several roots, and packages with different pid may belong to the same history DAG. A package p may exist in several history DAG, but there exists a unique history DAG G P such that p.pid = P. We call it the history of p. We can then deduce the set of ancestors of a package p from the history of p. Definition 4. The ancestors of a package p are all packages q such that there exists a path from q to p in the history of p.

Hence it is possible to check whether a package p upgrades an installation by testing whether an installed package is ancestor of p.

The size of the ancestor set grows constantly. Transmitting this information requires extra bandwidth and looking up in large data set is time-consuming. A scalable solution is to associate with each package a compressed metadata, called ancestor summary (or summary in short), from which it is possible to know whether an installed package belongs to the ancestor set. A Bloom filter is a good candidate: it has constant length and it supports efficient membership tests. A Bloom filter may yield a false positive suggesting that an element is in a set even though it is not. This does not induce serious problem as before really upgrading, a peer can verify the replace relationship using the complete history. Hence false positive only causes useless download but not installation of package.

By definition, a Bloom filter representing a set S of n elements is a vector of m bits, initially all set to 0. For each element x ∈ S, k independent hash functions h 1 , h 2 , . . . , h k are used to encode the element (string) into an integer over the range {1, . . . , m}. All bits h i (x) are set to 1, 1 ≤ i ≤ k. To check whether an element y is in S is checking whether all the bits h i (y) are set to 1, 1 ≤ i ≤ k. By choosing appropriate values of k and m, the false positive rate can be limited to a negligible small value.

Note also that augmenting the replace relation with information is possible, e.g. developer updates, minor updates and major upgrades [?].

Finally, release management depends on user behavior and community rules. The emerging usages are unpredictable: exponential growth of the number of versions, development of merge bots, encapsulation of dependent packages in order to prevent incompatibility with future versions, and so on.

Perspective Works

In order to test our proposal, we are currently implementing a prototype of decentralized package manager. More precisely, a peer-level simulator have been developed. It emulates the logic of all the opera- tions performed by a peer to locally install, upgrade or remove a package. The packages being deployed are old Debian packages collected from the Debian Snapshot Repository9 , with their metadata transformed into our specific format. Yet we can not evaluate our system on a real decentralized upgrading scenario as Debian packages do not have branches in their evolution history. In a next step, we plan to acquire source packages directly from upstream sources and combine our prototype with the Nix 10 package manager. Research on higher level functionalities is also going on. Some peer-to-peer algorithms will be implemented in our future works to enable the notification and delivery of packages.

Open issues

The design and implementation of a complete system requires investigation on a wide range of topics. Many open issues are left for future research.

Inter-dependent devices Pervasive software often require to be deployed onto more than one devices. For example, a digital home management software spread over a lot of captors, actuators and the various electronic devices of a house. In such a context, updating a package on one peer may force another peer to update some of its packages as the interface between packages must remain compatible. We already realized early work on the problem of coordinated dependency resolution for the deployment of distributed component-based applications in a LAN. But, the complete formalization of this approach and its adaptation to the Internet of Things remain open issues.

Certification mechanism and failure recovery Package management security is essential to the overall security of the computing system [START_REF] Cappos | Package Management Security[END_REF]. As any peer can release a new package at anytime, it is impossible to prevent the spread of malware. A distributed trust system is required for evaluating packages. Even though we are not able to propose a precise solution by now, we believe that a reputation evaluation approach based on social network could be used to select the most trusted peers [START_REF] Xiong | PeerTrust: Supporting Reputation-Based Trust for Peer-to-Peer Electronic Communities[END_REF]. The more a peer is trusted, the better it will be considered as a source for download. However, peer-to-peer trust and reputation systems have not been yet implemented at a large scale. The security requirements and the perspective to scale to the Internet of Things requires major progresses in the evaluation of these systems. Besides a certification mechanism, the system must also be able to prevent failure and to recover if any failure arise. The recent work of [START_REF] Di | Supporting Software Evolution in Component-Based FOSS Systems[END_REF] on using a model-driven approach to simulate upgrades combined with roll-back mechanism concentrates on unintentional failure but could serve as a basis to explore a more defensive approach.

Figure 1 :

 1 Figure 1: Conceptual model of a repository-less package management system

http://en.wikipedia.org/wiki/SourceForge

http://www.mobiledevhq.com/developers

http://www.cyrius.com/journal/

http://snapshot.debian.org/


Gimer Cervera

Michel Barbeau
email: barbeau@scs.carleton.ca

Joaquin Garcia Alfaro

Evangelos Kranakis
email: kranakis@scs.carleton.ca

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

Mitigation of topology control traffic attacks in OLSR networks

published or not. The documents may come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

The Optimized Link State Routing (OLSR) [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF] protocol, is a proactive link state routing protocol for Mobile Ad hoc networks (MANETs). As many other routing protocols, OLSR did not include security constrains in its original design. The core of the protocol is the selection, by every node, of Multipoint Relays (MPRs) among their one-hop symmetric neighbors. The nodes selected as MPRs are responsible of generating and forwarding control traffic messages and used to form optimal routes from a given node to any destination in the network. Thus, if an MPR fails or misbehaves sending or forwarding control traffic information, the connectivity of the network is compromised. The standard OLSR specification (RFC3626, Section 20), enumerates security considerations for confidentiality, integrity and interaction with external routing domains, but does not include security measures. Our research focus on mitigating control traffic attacks in OLSR.

Selecting the MPR sets as small as possible ensures that the overhead of the protocol is kept at minimum. However, adding extra coverage in the selection of the MPRs is an alternative solution to mitigate the effect of control traffic attacks. Additional MPR coverage, ensures that reachability for a node is advertised by more nodes. The RFC3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF], Section 16, defines an MPR coverage parameter (MPR Coverage) to specify by how many MPRs any strict two-hop node should be covered. We present this approach in function k-covered-MPR. Nevertheless, the overhead of the protocol increases considerably due to excessive control traffic messages.

We propose function k-robust-MPR, in order to improve the selection of MPRs with additional coverage. Thus every node selects, when it is possible, k + 1 disjoint MPRs sets. The union of the k + 1 disjoint sets is a k-robust-MPR set, if we remove a maximum of k elements from the MPR set of a given node n, all nodes two hops away from node n are still covered by the remaining elements in the k-robust-MPR set. We tested the two functions under the presence of two types of misbehaving nodes. One adversary interrupts the proper flooding of the control traffic messages, and the second one, generates them incorrectly. Our results show that our improved MPR selection offers a better balance between the protection against control traffic attacks and the overhead generated by the increased number of messages.

A. Control Traffic Attacks to OLSR

The generation and exchange of critical information are important vulnerability targets. The control messages flood the network to allow every node to create optimal paths to any destination in the network. If a node misbehaves by generating or forwarding incorrect control traffic information the integrity of the network is compromised. During the execution of the protocol, each node broadcasts Hello messages to advertise their presence among their one-hop neighbors, to learn about their two-hop neighbors and to select its MPRs. The MPRs generate and retransmit Topology Control(TC) Messages. The information from Hello and TC messages allows every node to construct their routing tables. Thus, in an OLSR network, the nodes have two principal tasks to perform [START_REF] Vilela | A feedback reputation mechanism to secure the optimized link state routing protocol[END_REF]: (1) to generate correctly routing information (i.e., Hello and TC messages), and (2) to correctly relay traffic on behalf of other nodes in the network.

A target of an attack can be that legitimate nodes never receive correct control traffic messages or store incorrect information to affect negatively the network topology. The attacks at the routing level can be classified in two categories [START_REF] Cuppens | Misbehaviors detection to ensure availability in OLSR[END_REF]: incorrect traffic generation and incorrect traffic relaying.

• Incorrect traffic generation: a node misbehaves by generating incorrect Hello or TC messages under a false identity or generating control traffic messages reporting an incorrect set of links. An attacker can either hide valid links or insert non-existing links. In all cases, the network connectivity is disrupted. • Incorrect traffic relaying: if a node decides to drop valid packets, e.g., an MPR refuses to forward TC messages, the network will experience a degradation of communication. Equally, an attacker misbehaves by resending old valid control messages (not timestamped), or forwarding altered control messages. The nodes in the network will receive wrong information and update their routing tables with stale information. Additionally, two or more nodes can collude to perform an attack. For instance, misbehaving nodes can establish invalid links and replay valid information in different regions of an OLSR network mounting a wormhole attack. This type of attack is particularly severe, because it is difficult to detect even in a network where security constraints (i.e., authentication, integrity and confidentiality) are implemented.

B. Contributions of the Paper

In this paper, we propose an improved MPR selection with additional coverage (cf., function k-robust-MPR) to mitigate the effect of traffic control message attacks. We compare our function against the MPR selection with additional coverage (cf., function k-covered-MPR) proposed in the RFC3626. We analyze the cost and benefit of functions k-covered-MPR and k-robust-MPR for the selection of MPR with extra coverage in the presence of misbehaving nodes in an OLSR network. We also present the correctness of both functions in Section IV-C. Our function k-robust-MPR, mitigates the effect of the adversaries performing control traffic attacks and affecting negatively the construction of the routing tables for every node in an OLSR network. We also compare functions kcovered-MPR and k-robust-MPR to measure the level of mitigation against two types of adversaries. The experiments show that it is possible to offer equivalent protection but reducing the overhead due to the excessive number of control traffic messages generated by function k-covered-MPR. Additionally, function k-robust-MPR increases the performance ratio between the number of nodes with complete routing tables and the increased number of TC messages.

C. Related Work

The vulnerabilities in the OLSR protocol have been studied extensively. In general, the aim of security mechanisms are integrity and service availability(fault-tolerance). We can classify measurements in two categories [START_REF] Adjih | Securing the OLSR routing protocol with or without compromised nodes in the network[END_REF], [START_REF] Raffo | Securing OLSR using node locations[END_REF], [START_REF] Vilela | A feedback reputation mechanism to secure the optimized link state routing protocol[END_REF], [START_REF] Kannhavong | A study of a routing attack in OLSR-based mobile ad hoc networks[END_REF], [START_REF] Adnane | Autonomic trust reasoning enables misbehavior detection in OLSR[END_REF]: i) cryptographic mechanisms to avoid attacks such as impersonation, replay or modification attacks, and ii) Intrusion Detection Systems (IDS) to prevent altered information from an authenticated node. Nevertheless, cryptographic models are challenging because in MANETs they have no centralized authority and reputation models require additional computation, increase the traffic in the network and need certain period of time to detect a misbehaving node, and during that time, the integrity of the network is compromised. Our scheme focuses on service availability and security by implementing an improved MPR selection with additional coverage. In the literature, authors implement the MPR Coverage parameter in terms of fault tolerance, load balancing, reliability and Qualityof-Service(QoS) [START_REF] Mueller | Multipath routing in mobile ad hoc networks: issues and challenges[END_REF], [START_REF] Yi | Simulation and performance analysis of MP-OLSR for mobile ad hoc networks[END_REF]. However, they do not analyze their approaches with a security perspective. An improvement of the OLSR flooding method presented in [START_REF] Adjih | Computing connected dominated sets with multipoint relays[END_REF] proposes the transformation of MPRs into Connected Dominating Sets (CDS). The use of these CDS-based algorithms for the flooding of topological data as a replacement of the standard flooding procedure of OLSR is claimed by the authors as a promising trade-off between minimization and reliability. However, they do not address the use of an additional coverage in the selection of the MPR sets, for tuning the flooding process once the CDS has been built. In [START_REF] Villanueva | Extending network knowledge: making OLSR a quality of service conducive protocol[END_REF] authors provide a balance between selecting additional coverage using the MPR Coverage parameter proposed in [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF] and redundancy in the link-state information (TC Redundancy parameter) to improve the QoS of the protocol. Nonetheless, they analyze their approach using the MPR with extra coverage proposed in [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF] and without the presence of misbehaving nodes. In [START_REF] Viennot | Bi-connectivity, k-Connectivity and multipoint relays[END_REF], authors prove that an MPR selection with additional coverage can be used to preserve k-connectivity in an OLSR network; based on that approach we improve the selection of MPRs with additional coverage to reduce the overhead generated for excessive control messages and to mitigate traffic control attacks.

Organization of the paper -Section II reviews the OLSR protocol and its vulnerabilities. Section III describes our adversaries model. Section IV presents the selection of MPRs with extra coverage described in the RFC3626 and our krobust-MPR selection. Additionally, we present the correctness of functions k-covered-MPR and k-robust-MPR. Section V shows our experimental results.

II. OLSR AND ITS SECURITY FLAWS

This section presents an overview of the OLSR protocol and its security flaws. OLSR is a proactive routing protocol designed for MANETs. The core of the protocol is the selection, by every node, of Multipoint Relays (MPRs) among their onehop symmetric neighbors. 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 Topology Control (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 hop by hop routing, i.e., each routing table lists, for all reachable destinations, the address of the next node along the path to that destination.

Hello messages are transmitted to one-hop neighbors. These messages are not retransmitted further. Every node uses the received information to learn about its one-hop and twohop neighbors. That information allows to construct and to maintain neighbor tables. In the neighbor table, each node records the information about the one-hop neighbor link status (unidirectional, bidirectional or MPR). With this information every node builds its MPR selector set, i.e., the number of neighbors who have selected that node as their MPR. The MPRs are selected such that all two-hop neighbors are reachable through, at least, one MPR.

TC messages are broadcasted and retransmitted exclusively by the MPRs. These messages allow each node to construct its topology table and to declare its MPR Selector Set. The MPR Selector Set is the set of nodes that have selected a given node as an MPR. A node that has an empty MPR Selector Set does not send or retransmit any TC message. An MPR forwards a message if it comes from a node in its MPR Selector Set. Using the information of TC messages each node maintains a topology table where each entry consists of: (i) an identifier of a possible destination, i.e., an MPR selector in a TC message, (ii) an identifier of a last-hop node to that destination, i.e., the originator of the TC message, and (iii) an MPR Selector Set sequence number [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF]. Routing tables are constructed using the information from the neighbor and topology table.

The selection and behavior of the MPRs are critical vulnerability targets. As many other routing protocols, OLSR did not include security measures in its design. A node has an incorrect behavior if it is either generating or relaying incorrect control messages in an OLSR network [START_REF] Cuppens | Misbehaviors detection to ensure availability in OLSR[END_REF]. In the OLSR protocol, each node needs to construct and maintain routing tables. A valid entry in a routing table corresponds to a known path to another node in the network. MPRs are selected as intermediate nodes for all routes. Thus, all the destinations to routes partially constructed or broken are excluded from the routing table. Any failure during the control traffic relaying [START_REF] Cuppens | Property based intrusion detection to secure OLSR[END_REF] affects the link-state information and integrity of the network. For instance, if a node selected as an MPR is misbehaving and decides not to retransmit TC messages (e.g., to save energy) compromises the proper construction of routing tables for the entire network.

III. ADVERSARY MODEL

In this section, we describe the characteristics of our adversaries. Flooding the network with TC messages allows nodes to construct a path to all destinations. The TC messages are generated exclusively by the MPRs, each MPR includes in the messages all its selector nodes. Thus, the receptor of the message learns that the original sender is the last-hop to all the nodes included in the message. If an MPR misbehaves generating or forwarding TC messages, then the connectivity of the entire network is compromised. In [START_REF] Cuppens | Misbehaviors detection to ensure availability in OLSR[END_REF], authors define node profiles according to their behavior in a network during the execution of the OLSR protocol. We select the Selfish and Slanderer node profiles as active attackers.

• A Selfish node, is an MPR that decides neither to generate nor to retransmit TC messages. Figure 1(a) is an example of a selfish attack. For instance, consider node 2 as an MPR of node 0, and node 5 an MPR of node 2. If node 2 broadcasts a TC message, then node 5 might be responsible to retransmit the message but may decide not to do so. In consequence, nodes 7 and 8 will never learn that the last-hop to reach node 0 is node 2. • A Slanderer node, is an MPR that generates incorrect information, i.e., an MPR that does not declare a complete MPR Selector Set. Figure 1(b), is an example of a slanderer attack. Node 3 has been selected by nodes 0,1,2 and 4 as an MPR. Node 3 is an attacker and generates a TC message but without including node 1 in the message. Node 6 receives and forwards the message. In consequence, node 8 will never be aware of the presence of node 1.

These misbehaving nodes affect the integrity and the proper construction of routing tables for each node in the network. The nodes can be isolated and will not compute a complete view of the network topology. We consider that a node's routing table is affected if at least one element for a valid path in the network is missing. In both cases, alternative paths between nodes can help to mitigate the attacks. For instance, in Figure 1(a) node 2 can select node 5 or nodes 4 and 6 as MPRs. Thus, node 2 can reach nodes 7 and 8 trough nodes 4 and 6. We analyze in the sequel two approaches for additional coverage in the selection of MPRs: the function presented in the RFC3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF] (cf., function k-covered-MPR), and an alternative selection of disjoint MPR sets (cf., function krobust-MPR). The objectives are to minimize the overhead generated by an increased number of TC messages in the network and to offer equivalent protection in the presence of misbehaving nodes.

IV. MPR COMPUTATION WITH ADDITIONAL COVERAGE

This section describes the selection of MPRs with extra coverage presented in the RFC3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF] and our proposed function k-robust-MPR choosing disjoint groups of MPRs. In [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF], additional coverage is defined as the ability of a node to select redundant MPRs. The selection of MPRs must be as small as possible to reduce the overhead due to flooding the network with TC messages. Nevertheless, additional coverage allows a node to advertise its presence to more nodes in the network. In this manner, extra coverage helps to maintain the integrity of the network in spite of the presence of misbehaving nodes during the execution of the OLSR protocol. However, the overhead generated by the increased number of TC messages reduces the performance of the network. This problem is addressed with our improved function krobust-MPR (cf. subsection IV-B), which balances additional coverage and traffic overhead.

A. RFC3626's MPR Coverage Parameter

The RFC3626 [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF] defines the MPR Coverage parameter to specify by how many one-hop nodes any two-hop neighbors must be covered. If MPR Coverage is equal to one then the overhead is kept at minimum and the function is equivalent to the MPR selection without additional coverage specified in [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF], Section 8.3.1. If MPR Coverage is equal to k, a node selects its MPR set such as any two-hop neighbor is covered by k one-hop neighbors, whenever possible. A poorly covered node, is a node in the two-hop neighborhood that cannot be covered by at least k nodes in the one-hop neighborhood. The MPR Coverage parameter is local to every node in the network. Nodes with different values of MPR Coverage may operate in a same network. Function k-covered-MPR describes the MPR selection with coverage k defined in [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF], Section 16.1. To explain functions k-covered-MPR and k-robust-MPR, we will use the following notation:

• d(n, u): number of hops between nodes n and u.

• N 1 (n) := {n 1 : d(n, n 1 ) ≤ 1}. • N ≤2 (n) := {n 2 : d(n, n 2 ) ≤ 2}. • N 2 (n) := N ≤2 (n) \ N 1 (n). • degree(n,n 1 ): returns the number of nodes in N 2 (n) such that N 1 (n 1 ) ∩ N 2 (n) = ∅, assuming that n 1 ∈ N 1 (n). • M : M is an MPR set for node n ⇔ M ⊆ N 1 (n) such that for every node n 2 ∈ N 2 (n), N 1 (n 2 ) ∩ M = ∅.
• reachability(n, n 1 , A): returns the number of nodes in

N 2 (n) such that d(n 1 , n 2 ) ≤ 1 and N 1 (n 2 ) ∩ A = ∅, assuming that A ⊆ N 1 (n) and n 1 ∈ N 1 (n) \ A.
• required(n,A): returns a set B, such that B ⊆ N 1 (n), and for every b ∈ B, d(b, a) ≤ 1, assuming that a ∈ A and A ⊆ N 2 (n).

• linked(n, A): returns a set B, such that B ⊆ N 2 (n), and for every node b ∈ B, N 1 (b) ∩ A = ∅, assuming that A ⊆ N 1 (n).

• nextNode(n, A, B) : returns a node a ∈ A such that a provides the largest degree(n, a) and reachability(n, a, B). We assume that A, B ⊆ N 1 (n) and A ∩ B = ∅. • PoorlyCovered: subset of N 2 (n) formed by every node

n 2 ∈ N 2 (n) such that |N 1 (n 2 ) ∩ N 1 (n)| < k. • WellCovered: subset of N 2 (n) formed by every node n 2 ∈ N 2 (n) such that |N 1 (n 2 ) ∩ N 1 (n)| ≥ k. Function k-covered-MPR,
with respect to a given node n works as follows [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF]:

1) First, we obtain the poorly covered nodes in N 2 (n).

Then, we include in the MPR set M , the nodes in N 1 (n) that poorly cover nodes in N 2 (n). 2) We remove the poorly covered nodes from N 2 (n).

3) While there exist nodes in N 2 (n) not yet covered by at least k nodes in the MPR set:

• We add to M the node n 1 in N 1 (n) not in the MPR set, that provides the largest reachability(n, n 1 , M ) and degree(n,n 1 ).

• We eliminate all the nodes in N 2 (n) now covered by at least, k nodes in the MPR set. For instance, according to the example presented in Figure 2, the MPR sets selected by all the nodes, derived in polynomial time by function k-covered-MPR, corresponds to column four in Table I.

Node

Possible disjoint No extra Proof: Suppose that if we apply the function k-covered to node n then it is possible to have a node n 2 in N 2 (n) such that |N 1 (n 2 ) ∩ N 1 (n)| is greater than or equal to k and n 2 is not in S. However, according to the definition of function k-covered, every node n 2 in N 2 (n) is inspected by the foreach-loop and, if |N 1 (n 2 ) ∩ N 1 (n)| is greater or equal to k, we add node n 2 to S in the body of the loop. Thus, S is equal to the union of every node in N 2 (n) covered by at least k nodes in N 1 (n).

k-covered-MPR k-robust-MPR MPR sets coverage k = 2 k = 2 0 {{2},{3},{1,4}} {2} {2,3} {2,3,1,4} 1 {{6}} {6} {6,5,2,0} {6} 2 {{6},{7,5}} {6}
Theorem 1 Let M be the set obtained by applying function k-covered-MPR to node n. Every node in N 2 (n) with exactly k neighbors in N 1 (n), such that k is less than k, is covered by exactly k nodes in M .

Proof: Consider M as the set obtained by applying function k-covered-MPR to node n. Then, suppose that there exists a node n 2 in N 2 (n) with exactly k neighbors in N 1 (n), k less than k, that is not covered by k nodes in M . However, by applying function k-covered-MPR, in line 2, and according to Lemma 1, we assign to the set WellCovered every node in N 2 (n) covered by at least k nodes in N 1 (n). In line 3, we assign to the PoorlyCovered set all the nodes in N 2 (n) not in the set WellCovered. Then in line 4, for every node n 2 in PoorlyCovered, we assign to M every node

n 1 in N 1 (n) such that N 1 (n) ∩ N 1 (n 2 ) is not equal to the empty set. Therefore, every node in N 2 (n) with k neighbors in N 1 (n) is covered by exactly k nodes in M .
Theorem 2 Let M be the set obtained by applying function k-covered-MPR to node n. Then, every node in N 2 (n) with exactly k neighbors in N 1 (n), such that k is greater than or equal to k, is covered by, at least, k nodes in M .

Proof: Consider M as the set with coverage k obtained by applying function k-covered-MPR to node n. Then, suppose that there exists a node n 2 in N 2 (n) with exactly k neighbors in N 1 (n), k greater than or equal to k, that is not covered by at least k nodes in M . However, in line 2, we assign to the set WellCovered all nodes in N 2 (n) covered by at least k nodes in N 1 (n). We assign to the PoorlyCovered set every node in N 2 (n) not in WellCovered. Thus, according to Theorem 1, we assign to M the nodes in N 1 (n) that poorly cover all nodes in the PoorlyCovered set. Then, we repeat the following procedure until every node in WellCovered is covered by, at least, k nodes in M :

• In lines 6 and 7, we eliminate every node in the set WellCovered covered by, at least, k nodes in M . • If WellCovered is not equal to the empty set, then we add to M the node in N 1 (n) that covers the largest number of elements in N 2 (n). Therefore, if k is greater than or equal to k, every node in

N 2 (n) with k neighbors in N 1 (n), is covered by, at least, k nodes in M .
Lemma 2 Let M i be a set obtained by applying function MPR-set to node n, such that M i is not equal to the empty set and M i ⊆ N 1 (n). Then M i successfully covers all nodes in N 2 (n) (i.e., M i is a valid MPR candidate).

Proof: Consider that after applying function MPR-set to node n with parameters Remainder, a subset of N 1 (n), and S, equal to N 2 (n), it is possible to obtain a set M i not equal to the empty set, such that M i does not cover all elements in N 2 (n). However, by applying function MPR-set to node n, if |linked(n, Remainder)| is equal to |S|, then we can construct a set M i , such that M i covers all elements in S. In function MPR-set line 3, we add to M every node in Remainder that is the only one to provide reachability to a node in S. After that, while there exist nodes in S that are not yet covered by, at least, one node in M i , we select a new node n 1 from Remainder not in M i that covers the largest number of nodes in S. Thus, we obtain M i such that |linked(n, M i )| is equal to |S|. Therefore, if M i is not equal to the empty set, we can affirm that every node in S is covered by, at least, one node in M i and so that every set M i returned by function M P R-set is, indeed, a valid MPR set.

Theorem 3 Let M be a set obtained by applying function krobust-MPR to node n. Then M is a valid MPR set, i.e., M covers all the nodes in N 2 (n).

Proof: Suppose that by applying function k-robust-MPR we obtain a set M , such that that M is not a valid MPR set. However, according to Lemma 2, if M i is not equal to the empty set, then M i is a valid MPR set. Notice that, function krobust-MPR invokes function MPR-set k + 1 times, such that k is greater than or equal to zero and less than or equal to k. Since M is the union of k + 1 disjoint valid MPR sets, we can affirm that M is a valid MPR set.

Corollary 1 Let M be a valid MPR set obtained by applying function k-robust-MPR to node n. If a node in N 2 (n) is covered by k nodes in N 1 (n), with k less than or equal to k and there is no k in N 1 (n) such that k is less than k . Then, it is possible to invoke a maximum of k times function MPRset and M is a k -robust-MPR set.

Proof: Suppose that there exists a node n 2 in N 2 (n) such that n 2 is covered by k nodes in N 1 (n), then it is possible to invoke function MPR-set k times to obtain k-robust-MPR set. However, by applying function k-robust-MPR to node n, we invoke function MPR-set with parameters n, Remainder and S. Initially, in line 3 we assign to Remainder the set N 1 (n), and every time a valid M i is obtained from function MPR-set, we subtract the set M i from Remainder. Thus, if a node in N 2 (n) is covered by k nodes in N 1 (n), after invoking function MPR-set k times, then there exists a node n 2 in N 2 (n) that is not covered in Remainder and |linked(n, Remainder)| is less than |N 2 (n)|. Then, function MPR-set returns the empty set and M is equal to the union of k valid disjoint M i sets.

Theorem 4 Let M be the set obtained by iteratively applying k +1 times function MPR-set from function k-robust-MPR with parameters n and k, such that k is greater than zero and less than or equal to k. Then, for any S subset of M of size k , the nodes in M not in S still cover all the nodes in N 2 (n).

Proof: Suppose that M is a valid MPR set obtained by applying function k-robust-MPR to node n, and the elements in M not in S do not cover all nodes in N 2 (n). However, every M i in M is obtained by applying k times function MPR-set to node n. According to Corollary 1, we have k + 1 valid M i sets in M . We consider the worst case when every element in S belongs to a different M i and we have k invalid M i sets in M . Consider M equal to the union of k invalid M i , i.e., M is equal to the union of M k +1 and M such that, according to the definition of function MPR-set, |linked(n, M k +1 )| is equal to |N 2 (n)|. Then, M k +1 is a valid MPR set and the elements in M not in M still cover all nodes in N 2 (n). Therefore, nodes in M not in S are a valid MPR set.

V. EXPERIMENTS

We conducted simulations to confirm that our k-robust-MPR set selection allows to minimize the effect of misbehaving nodes and helps to reduce the overhead generated by the k-covered-MPR function proposed in the standard OLSR protocol. To measure the effectiveness of our proposal, we count the number of nodes that were able to find a path to all nodes in the network after executing the two different MPR selection methods, for a certain period of time. Additionally, we take into account, the number of retransmissions during simulations. We conducted our simulations using the NS-2 simulator [START_REF] Mccanne | The network simulator: NS-2. Software package retrieved from[END_REF], version 2.29, with the UM-OLSR [START_REF] Ros | an implementation of the OLSR (optimized link state routing) protocol for the NS-2 network simulator[END_REF] package. We modified the original UM-OLSR code to implement the k-robust and k-covered MPR functions.

The RFC3626 considers that nodes with different characteristics can coexist in an OLSR network. For our experiments, we assume that all the nodes have the same characteristics, every node has just one interface and all the links between the nodes are bidirectional. Additionally, all the nodes have the same willingness to carry and forward traffic on behalf of other nodes, except for those that have been selected as misbehaving nodes. The misbehaving nodes do not collude to perform an attack. Table II describes the parameters for our simulations in NS-2. In our experiments, no data traffic is generated and all the scenarios are static.

We test functions k-robust-MPR and k-covered-MPR (with and without additional coverage), against one to five selfish or slanderer nodes. We test one hundred different topologies and one hundred nodes in each case. For each topology, we test all the approaches. In all the topologies, the misbehaving nodes are selected at random among all the MPRs. For our experiments, the nodes are distributed in ten clusters. In [START_REF] Villasenor-Gonzalez | HOLSR: a hierarchical proactive routing mechanism for mobile ad hoc networks[END_REF] Simulator authors organize an OLSR network in clusters in a hierarchical architecture. We can consider our topology as a particular set of clusters at the same level. The nodes in each cluster follow a Zipf [START_REF] Devroye | Non-uniform random variate generation[END_REF] distribution. Then, following this distribution the nodes are located in the center of each cluster with higher probability. Thus, it is possible to obtain topologies where at least 40% of the nodes have k-robust MPR sets, with k ≥ 1.

Figure 3 depicts the average number of nodes with complete routing tables and 95% confidence intervals. It shows how our strategy offers additional protection to mitigate the effect of misbehaving nodes in contrast with the selection of MPRs without additional coverage. We point out that is not always possible to find k-robust MPR sets for all the nodes in the network. In consequence, if the number of misbehaving nodes increase the level of protection decrease. Notice that our k-robust-MPR function mitigates the effect of misbehaving nodes with a better performance than the k-covered-MPR (cf. Figure 3(c)). Figure 4 depicts our results, but with one to five slanderer nodes. Again, we observe that our k-robust-MPR function mitigates the effect of misbehaving nodes with a better performance than the k-covered-MPR (cf. Figure 4(c)).

VI. CONCLUSION

In this paper, we proposed an improved MPR selection with additional coverage (cf., function k-robust-MPR) to mitigate control traffic attacks in an OLSR network. Our goal is to provide service availability and security. In our proposal, every node selects, if it is possible, k+1 disjoint MPR sets. As a result, we obtain a k-robust-MPR set. The RFC3626 defines an MPR selection with additional coverage (cf., function kcovered-MPR), however, the number of topology control messages increases considerably reducing the performance of the network. We compared functions k-covered-MPR and k-robust-MPR 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 show that our function k-robust-MPR reduces the amount of traffic generated by function k-covered-MPR, and offers equivalent protection against control traffic attacks. Additionally, our function k-robust-MPR increases the performance ratio of the number of nodes with complete routing tables over the number of topology control messages.

Fig. 1 .

 1 Fig.1. Example of a selfish and a slanderer attack. In (a), node 5 is a selfish node and has been selected by node 2 as an MPR. In (b), node 3 is a slanderer node and has been selected by node 1 as an MPR.

Fig. 2 .

 2 Fig. 2. Consider nodes 2, 3, 6 and 9 as MPRs, selected with no extra coverage.

  -MPR, k=2 k-robust-MPR, k=1 k-covered-MPR, k=1 (a) Number of Topology Control messages.

  No. misbehaving nodes (Selfish) 100Nodes ClustersDistribution k-covered-MPR, k=2 k-robust-MPR, k=1 k-covered-MPR, k=1 (b) Percentage of nodes with complete routing tables. nodes (Selfish) k-robust-MPR, k=1 k-covered-MPR, k=2 (c) Performance ratio.

Fig. 3 .

 3 Fig. 3. Comparative of functions k-covered-MPR and k-robust-MPR under the presence of selfish nodes.

  -MPR, k=2 k-robust-MPR, k=1 k-covered-MPR, k=1 (a) Number of Topology Control messages.

  No. misbehaving nodes (Slanderer) 100Nodes ClustersDistribution k-covered-MPR, k=2 k-robust-MPR, k=1 k-covered-MPR, k=1 (b) Percentage of nodes with complete routing tables. nodes (Slanderer) k-robust-MPR, k=1 k-covered-MPR, k=2 (c) Performance ratio.

Fig. 4 .

 4 Fig. 4. Comparative of functions k-covered-MPR and k-robust-MPR under the presence of slanderer nodes.

Acknowledgments -Research supported by: Natural Sciences and Engineering Research Council of Canada (NSERC), Mathematics of Information Technology and Complex Systems (MITACS), Institut TELECOM (programme Futur et Ruptures), Spanish Ministry of Science (grants TSI2007-65406-C03-03 E-AEGIS and CONSOLIDERINGENIO 2010 CSD2007-00004 ARES), National Council of Science and Technology (CONACYT) , and Ministry of Education of Mexico (SEP, Program for Academic Improvement).

In this section, we describe function k-robust-MPR that improves the selection of MPR sets with additional coverage. Function k-robust-MPR computes an MPR set that is composed of, at most, k + 1 disjoint groups, i.e., every two-hop node is covered, if possible, by k + 1 disjoint groups of onehop neighbors. Function k-robust-MPR works as follows:

1) First, by invoking function MPR-set, we obtain a subset M i such that M i is subset of N 1 (n) and covers all the nodes in N 2 (n). 2) We repeat the function until it is not possible to find a new disjoint subset M i that covers all the nodes in N 2 (n) or we have found a maximum of k + 1 disjoint subsets.

3) The MPR set is formed by the union, if it is possible, of k disjoint subsets M i . If we apply function k-robust-MPR to the example depicted by Figure 2, then we obtain the set of MPRs shown in Table I, column five. For example, the execution of function k-robust-MPR on node 0, with parameter k equal to two, returns the MPR set {2, 3, 1, 4}, which is 2-robust.

C. Correctness of the Functions

In this section, we demonstrate the correctness of functions kcovered-MPR and k-robust-MPR.

Lemma 1 Let S be the set returned by applying function kcovered to node n. Every node in N 2 (n) covered by at least k nodes in N 1 (n), is in S.