COLE DE TECHNOLOGIE SUPRIEURE UNIVERSIT DU QUBEC

MMOIRE PRSENT LCOLE DE TECHNOLOGIE SUPRIEURE

COMME EXIGENCE PARTIELLE LOBTENTION DE LA MATRISE EN GNIE CONCENTRATION RSEAUX DE TLCOMMUNICATIONS M.Ing.

PAR ABDELLAOUI, Rachid

SU-OLSR UNE NOUVELLE SOLUTION POUR LA SCURIT DU PROTOCOLE OLSR.

MONTRAL, LE 05 MAI 2009 Rachid Abdellaoui, 2009

PRSENTATION DU JURY CE MMOIRE A T VALU PAR UN JURY COMPOS DE

M. Jean-Marc Robert, directeur de mmoire Dpartement gnie logiciel et T.I lcole de technologie suprieure M. Michel Kadoch, prsident du jury Dpartement gnie lectrique lcole de technologie suprieure Mme Nadjia Kara, membre du jury Dpartement gnie logiciel et T.I lcole de technologie suprieure

IL A FAIT LOBJET DUNE SOUTENANCE DEVANT JURY ET PUBLIC LE 21 AVRIL LCOLE DE TECHNOLOGIE SUPRIEURE

REMERCIEMENTS Je tiens remercier en premier mon directeur de mmoire, le professeur Jean-Marc Robert, pour l'aide qu'il m'a apporte, ses prcieux conseils et ainsi pour sa sympathie durant tout le droulement de ce travail. Je remercie aussi les membres du comit davoir accept dy participer. Je remercie galement ma famille ainsi que mes amis pour leur soutien durant toute ma matrise et la priode de rdaction de ce mmoire. Ce travail de recherche a t partiellement financ par le CRSNG subvention la dcouverte ainsi quune subvention de dmarrage de lETS.

SU-OLSR, UNE NOUVELLE SOLUTION POUR LA SCURIT DU PROTOCOLE OLSR ABDELLAOUI, Rachid RSUM Un rseau Ad-Hoc mobile (Mobile Ad-Hoc NETwork : MANET) est une collection de nuds sans fil formant un rseau dynamique sans infrastructure prexistante ou une architecture centralise. Chaque nud dans ce type de rseau fonctionne comme un routeur et utilise un protocole de routage pour acheminer les messages. OLSR (Optimized Link State Routing) est un protocole de routage proactif pour les rseaux Ad-Hoc prsent par le groupe MANET de lIETF. Ce protocole utilise des nuds appels relais multipoints (MultiPoint Relay : MPR) pour optimiser la diffusion dans le rseau. Chaque MPR doit diffuser les informations sur la topologie et racheminer les messages aux nuds destinations. Si lun de ces MPR est malicieux, il prsentera un danger pour la scurit de tout le rseau. Dans ce travail de recherche, nous avons prsent un nouveau protocole driv du protocole OLSR et qui utilise le concept de confiance entre les nuds. Lobjectif est de faire face aux attaques par mystification de lien o un nud malicieux cherche forcer ses voisins le choisir comme MPR. Le nouveau protocole SU-OLSR (SUspicious OLSR) empche tout nud qui prsente des comportements suspects dtre choisi comme MPR. Grce diverses simulations et limplmentation de SU-OLSR sous ns-2, nous avons montr que SU-OLSR fournit les mmes performances que le protocole OLSR classique malgr quil soit plus slectif lors du choix des MPR. Mots-cls : Scurit, OLSR, Rseaux Ad-Hoc, Protocoles de routage, Vulnrabilit

SU-OLSR: A NEW SOLUTION TO THWART ATTACKS AGAINST THE OLSR PROTOCOL ABDELLAOUI, Rachid ABSTRACT Mobile Ad-Hoc network (MANET) is a collection of wireless nodes forming a dynamic network without any centralized or pre-existing infrastructure. Each node in such a network has to act as a router, using a routing protocol to achieve this task. The OLSR (Optimized Link State Routing) protocol is a proactive routing protocol presented by the IETF MANET working group for ad-hoc networks. One of the key aspects of OLSR protocol is the use of special nodes called Multipoint Relay (MPR) nodes. These nodes have to broadcast the topology information through the network and to forward packets towards their destinations. If one of those nodes is malicious, it would represent a major threat against the security of the overall network. A new approach to Ad-Hoc routing protocol using the concept of trustworthiness for the neighbour nodes is presented in this thesis. We propose a new protocol to prevent a malicious node to force its neighbours to select it as a MPR node. With our SU-OLSR protocol (Suspicious OLSR), a node should not choose a neighbour as a relay node if it behaves suspiciously and demonstrates strong characteristics which would influence the MPR selection algorithm. We have ported the SU-OLSR protocol to the ns-2 simulator. This implementation and simulation results are discussed along this thesis. We have demonstrated that our solution prevents the link spoofing attack against the OLSR protocol. The performances of the SUOLSR related to the path lengths, data packet average end-to-end delivery time and data Packet Delivery Ratio (PDR) are quite comparable to the classical OLSR, if the network density assures some redundancy. Keywords: Security, OLSR, Ad-Hoc Network, Routing protocols, Vulnerability

TABLE DES MATIRES Page INTRODUCTION .....................................................................................................................1 CHAPITRE 1 LES RSEAUX SANS FIL AD-HOC ............................................................4 1.1 Historique des rseaux Ad-Hoc .....................................................................................4 1.2 Applications des rseaux Ad-Hoc ..................................................................................5 1.3 Dfis dans les rseaux Ad-Hoc ......................................................................................9 1.4 Protocoles de routage pour les rseaux Ad-Hoc ..........................................................11 1.4.1 Les types de protocoles ..................................................................................12 1.4.2 Descriptions de certains protocoles de routage pour rseaux Ad-Hoc ..........15 1.5 Le protocole OLSR ......................................................................................................22 1.5.1 Description du protocole OLSR.....................................................................22 1.5.2 Dtection de voisinage ...................................................................................23 1.5.3 Slection des Relais Multipoints ....................................................................26 1.5.4 Dclaration des relais multipoints..................................................................29 1.5.5 Calcule des routes ..........................................................................................30 1.6 Complexit et comparaison des protocoles de routage ................................................30 CHAPITRE 2 SCURIT ET VULNRABILITS DES RSEAUX AD-HOC ...............33 2.1 Objectifs de la scurit .................................................................................................33 2.1.1 Confidentialit................................................................................................33 2.1.2 Intgrit ..........................................................................................................33 2.1.3 Disponibilit...................................................................................................34 2.2 Vulnrabilits et types dattaques dans les rseaux Ad-Hoc .......................................34 2.2.1 Classification dattaques dans les rseaux Ad-Hoc .......................................34 2.2.2 Dfense contre les attaques dans les rseaux Ad-Hoc ...................................35 2.3 Vulnrabilits et types dattaques spcifiques au protocole OLSR .............................37 2.3.1 Classifications des vulnrabilits et des attaques...........................................37 2.3.2 Mcanismes de scurit proposs pour OLSR...............................................42 CHAPITRE 3 LE PROTOCOLE SU-OLSR ........................................................................49 3.1 Motivations et objectifs................................................................................................49 3.2 Revue de littrature des heuristiques de slection des MPR........................................50 3.2.1 Schmas classiques ........................................................................................50 3.2.2 Schmas bass sur des ensembles dominants connects ...............................51 3.2.3 Schmas bass sur la qualit de service .........................................................52 3.3 Le nouveau protocole SU-OLSR .................................................................................53 3.3.1 Le nouveau algorithme de slection des MPR ...............................................53 3.3.2 Messages de contrle et algorithme dinondation dans SU-OLSR ...............56 3.4 Analyse du modle dattaque .......................................................................................58 3.4.1 Hypothses et limitations ...............................................................................58 3.4.2 Modle dattaque ...........................................................................................58

VII

CHAPITRE 4 VALUATION EXPRIMENTALE DE SU-OLSR ...................................61 4.1 Problmatique et objectifs............................................................................................61 4.2 Paramtres dvaluation ...............................................................................................61 4.3 Modle sans mobilit ...................................................................................................63 4.3.1 Objectifs et implmentation du SU-OLSR et OLSR .....................................63 4.3.2 Rsultats de simulation ..................................................................................64 4.4 Environnement de simulation dynamique ...................................................................76 4.4.1 Simulateur ns-2 ..............................................................................................76 4.4.2 Implmentation de OLSR et SU-OLSR sous ns-2.........................................81 4.5 Simulation dynamique .................................................................................................82 4.5.1 Paramtres de simulations..............................................................................82 4.5.2 Outils pour analyser les traces de simulation .................................................88 4.5.3 Rsultats de simulation ..................................................................................91 CONCLUSION ........................................................................................................................99 ANNEXE I SCRIPT DE SIMULATION ........................................................................103

BIBLIOGRAPHIE .................................................................................................................108

LISTE DES TABLEAUX Page Tableau 1.1 Tableau 1.2 Tableau 1.3 Tableau 1.4 Tableau 1.5 Tableau 2.1 Tableau 4.1 Tableau 4.2 Tableau 4.3 Tableau 4.4 Tableau 4.5 Tableau 4.6 Tableau 4.7 Tableau 4.8 Tableau 4.9 Tableau 4.10 Tableau 4.11 Tableau 4.12 Champs Link Code .....................................................................................25 Valeurs possible pour le champ Link Code ...............................................25 Sommaire des protocoles proactifs ............................................................31 Sommaire des protocoles ractifs ..............................................................31 Sommaire des protocoles hybrides ............................................................32 Solutions proposes pour la scurit dans les rseaux Ad-Hoc .................36 Simulations statiques .................................................................................63 Nombre de MPR couvrent des nuds isols .............................................64 Longueur de chemins SU-OLSR (Critre I + Option I) vs OLSR.............70 Longueur de chemins SU-OLSR (Critre II + Option I) vs OLSR ...........71 Longueur de chemins SU-OLSR (Critre I + Option II-a) vs OLSR .......73 Longueur de chemins SU-OLSR (Critre I + Option II-b) vs OLSR .......74 Plateforme de simulation ...........................................................................81 Paramtres de simulation pour SU-OLSR et OLSR ..................................87 Scnarios de simulation pour SU-OLSR et OLSR ....................................87 Liste des outils dvelopps pour nos simulations ......................................91 Nombre de MPR dans le cas dune mobilit maximal 1.4 m/s ..................92 Nombre de MPR dans le cas dune mobilit maximal 10 m/s ...................92

LISTE DES FIGURES Page Figure 1.1 Figure 1.2 Figure 1.3 Figure 1.4 Figure 1.5 Figure 1.6 Figure 1.7 Figure 1.8 Figure 1.9 Figure 1.10 Figure 1.11 Figure 1.12 Figure 1.13 Figure 2.1 Figure 2.2 Figure 2.3 Figure 2.4 Figure 2.5 Figure 2.6 Figure 2.7 Figure 3.1 Figure 4.1 Extension des rseaux Mesh grce aux rseaux Ad-Hoc.............................8 VANET et VSN. ..........................................................................................9 Classification des protocoles de routage Ad-Hoc. .....................................14 Procdure de demande de recherche de route. ...........................................16 Exemple de rseau htrogne grande chelle. .......................................19 Modle hirarchique dHOLSR. ................................................................20 Zone de routage du nud S ( = 2 sauts). .................................................21 Larchitecture globale de ZRP. ..................................................................22 change des messages HELLO. ................................................................24 Format du message HELLO. .....................................................................25 Diffusion par inondation classique vs inondation par relais multipoints. ..27 Exemple de slection des relais multipoints. .............................................29 Format du message TC. .............................................................................30 Classifications des attaques dans les rseaux Ad-Hoc. ..............................35 Usurpation didentit du nud a par m (HELLO). ....................................38 Attaque sur la slection des MPR. .............................................................39 Usurpation d'identit du nud v par m (TC)..............................................40 Attaque wormhole cre par le nud m. ....................................................41 Collaboration pour crer un wormhole. .....................................................42 Isolation du nud malicieux m. .................................................................44 Application de l'algorithme de slection des MPR de SU-OLSR. ............56 Comparaison du nombre de MPR dans le cas du Critre I........................65

X

Figure 4.2 Figure 4.3 Figure 4.4 Figure 4.5 Figure 4.6 Figure 4.7 Figure 4.8 Figure 4.9 Figure 4.10 Figure 4.11

Rgion de couverture 2-sauts. .................................................................66 Nombre de MPR dans le cas du Critre II avec le coefficient 0.25. .........67 Comparaison du nombre de messages TC gnrs. ...................................68 Poids associs dans le cas de lOption II-a et II-b. ....................................72 Taux dutilisation des simulateurs rseau. .................................................77 Structure interne et communications (Plumbing) entre les composantes de deux nuds dans ns-2. ..........................................................................79 Processus de nos simulations dans ns-2. ....................................................81 Classification des modles de mobilit. .....................................................82 Mouvement d'un nud selon le modle Random Waypoint. ....................83 Exemple de 100 nuds dans 1000 m x 1000 m . .......................................84

Figure 4.12 Figure 4.13 Figure 4.14 Figure 4.15 Figure 4.16 Figure 4.17 Figure 4.18 Figure 4.19

Extrait et dtails importants dans les traces des simulations sous ns-2. ....88 Liste des MPR dans le fichier trace de simulations sous ns-2. ..................89 Diffrence de MPR choisis entre les deux protocoles (vitesse de 1.4 m/s max). ..........................................................................................................93 Diffrence de MPR choisis entre les deux protocoles (vitesse de 10 m/s max). ..........................................................................................................94 Pourcentage de paquets dlivrs PDR pour les deux protocoles. ..............95 Dlai de bout-en-bout pour les deux protocoles. .......................................96 Dlai maximal de bout-en-bout pour les deux protocoles. ........................97 Nombre de messages dlivrs. ...................................................................98

LISTE DES ABRVIATIONS, SIGLES ET ACRONYMES

ARP AODV BASH CBR CMU CSMA/CA CSMA/CD DARPA DSDV DSR DSSS HNA HOLSR IEEE IETF INRIA LAN MAC MANET MID MPR NAM

Address Resolution Protocol Ad-Hoc On demand Distance Vector Bourne-Again Shell Constant Bit Rat Carnegie Mellon University Carrier Sensing Multiple Access/Collision Avoidance Carrier Sensing Multiple Access with Collision Avoidance Defense Advanced Research Projects Agency Destination Sequenced Distance Vector routing protocol Dynamic Source Routing Direct-Sequence Spread-Spectrum Host and Network Association Hierarchical Optimized Link State Routing Protocol The Institute of Electrical and Electronics Engineers The Internet Engineering Task Force Institut National de Recherche en Informatique et Automatique Local Area Network Medium Access Control Mobile Ad-Hoc NETwork Multiple Interface Declaration Multi-Point Relays Network Animator

XII

NS-2 OLSR PDA PDR PHY PKI QOLSR QoS RAM RERR RREP RREQ RTS SU-OLSR TC TCL TTL UDP VINT WRP

Network Simulator 2 Optimized Link State Routing Protocol Personal Digital Assistant Packet Delivery Ratio Physical Layer Public Key Infrastructure Quality of Service extension introduced to the OLSR protocol Quality of Service Random Access Memory Route ERRor Route REPly Route REQuest Request To Sent SUspicious Optimized Link State Routing Protocol Topology Control Tool Command Language Time To Live User Datagram Protocol Virtual InterNetwork Testbed Wireless Routing Protocol

INTRODUCTION 1 - Point de dpart

La prolifration des ordinateurs portables et des appareils de tlcommunication sans fil (tlphone cellulaire, ordinateur et PDA) change dune manire rvolutionnaire nos architectures de tlcommunication. En effet, nous passons actuellement dun monde dordinateurs personnels un monde o l'informatique est omniprsente (Ubiquitous Computing). Chaque personne pourra partager des informations et accder plusieurs ressources sur diffrentes plateformes lectroniques quand et o elle veut. Les rcents dveloppements dans le domaine des rseaux sans fil vont acclrer sans doute la migration vers ce type de rseau. On peut noter les deux technologies concurrentes : la technologie 4G LTE (Long-term Evolution) avec un dbit thorique de 173 Mbits/s et la technologie WiMax mobile avec un dbit de 70 Mbits/s (3GPP, 2008). Linformatique omniprsente a besoin donc de solutions dinterconnexion entre ces appareils mobiles afin de faciliter la mise en place dinfrastructures flexibles. Le rseau Ad-Hoc est un excellent candidat pour rpondre ces besoins. Les rseaux Ad-Hoc sont une collection dappareils mobiles qui peuvent dynamiquement changer des informations entre eux sans utiliser une infrastructure rseau prexistante et fixe ou une administration centralise. Chaque appareil de ce type de rseau communique directement avec les autres appareils qui se trouvent dans son rayon de communication (porte radio). La communication avec les appareils distants se fait par le routage des communications travers des appareils intermdiaires. Au dbut, les rseaux Ad-Hoc ont t dvelopps pour les milieux militaires. Mais, grce leurs natures dauto-organisation et de facilit de dploiement, ces rseaux ont eu dautres vocations et dapplications civiles comme dans les situations durgence et les oprations de secours lors dun dsastre (80% de la ville de La Nouvelle-Orlans est inonde en 2005, saturation des infrastructures de tlcommunication cause dun volume trs lev d appels lors des attentats New York en

2

2001) ou lchange dinformations entre les PDA et les ordinateurs portables lors de runion La communication avec les nuds hors porte radio se fait par lintermdiaire des autres nuds qui acheminent les messages destination. Ce processus se fait grce au protocole de routage. cet effet, plusieurs protocoles de routage ont t proposs et standardiss par le groupe MANET (Mobile Ad-Hoc NETwork). La nature des rseaux Ad-Hoc, o les nuds sont mobiles et peuvent se joindre ou quitter le rseau tout moment, prsente des grands dfis pour la scurit, la qualit de service et le routage. Or la scurit est le point nvralgique des rseaux Ad-Hoc. Il est donc primordial de prserver la confidentialit, lintgrit, la non rpudiation et la disponibilit dans ce type denvironnement. Pour se faire, il est important de prvenir les attaques en particulier contre les protocoles de routage. Or, ces derniers ne proposent pas de modles de scurit ou des mcanismes pour faire face certains types dattaques.2 - Objectifs de recherche

Dans ce travail, nous nous intressons au protocole OLSR (Optimized Link State Routing Protocol) et en particulier aux vulnrabilits et aux attaques contre ce protocole. En effet, OLSR est un protocole qui utilise une diffusion optimise des messages grce des nuds appels MPR (Relais Multipoints). Les MPR permettent dacheminer les messages de la source la destination. Ils ont un rle trs important dans le rseau et tout comportement malveillant aurait un impact direct sur le bon fonctionnement du rseau. Or, un nud malicieux qui a t slectionn comme MPR aurait une position privilgie dans le rseau et pourrait altrer, modifier ou rejeter tout message qui transite par lui. Afin davoir cette position privilgie dans le rseau, un nud malicieux peut utiliser les techniques dattaques par mystification de lien. Ainsi, un nud malicieux peut forcer ses voisins le choisir comme MPR en dclarant quil couvre un nud isol (nud inexistant dans le rseau ou distant).

3

Notre objective est, donc, de proposer une nouvelle solution pour lutter contre les attaques par mystification de lien dans le cas du protocole OLSR et ainsi empcher tout nud qui prsente des comportements suspects et malveillants dtre slectionn comme MPR.3 - Organisation du mmoire

Ce mmoire est organis de la manire suivante. Le chapitre 1 introduit les rseaux Ad-Hoc et les diffrentes familles de protocoles de routage en dtaillant le fonctionnement de certains de ces protocoles. Pour sa part, le protocole OLSR sera compltement dtaill la fin de ce chapitre suivi dun sommaire comparatif de certains protocoles de routage reprsentant les trois familles : ractif, proactif et hybride. Nous prsenterons une revue de littrature dans le chapitre 2 afin de mettre la lumire sur les dfis et les attaques sur les rseaux Ad-Hoc en gnral et le protocole OLSR en particulier. Ce chapitre classifiera aussi les diffrentes solutions proposes ce sujet. Le chapitre 3 quant lui prsente notre approche et le nouveau protocole SU-OLSR prcd dune revue de littrature des diffrentes heuristiques de slection des MPR pour le protocole OLSR. Ce chapitre donne aussi le modle dattaques relatives SU-OLSR. Par des simulations dans le chapitre 4, nous avons cherch valuer et valider exprimentalement le nouveau protocole SU-OLSR dans diffrents environnements de mobilit et le comparer aux performances du protocole OLSR. Dans une premire tape, nous avons dvelopp un programme en C pour valuer SU-OLSR et OLSR dans un environnement statique. Dans une seconde phase, nous avons implment le protocole SUOLSR sous ns-2 afin de le comparer avec OLSR sous diffrents scnarios de mobilit. En conclusion, le dernier chapitre propose un rcapitulatif des principaux travaux raliss et les rsultats obtenus. Pour finir, nous donnons plusieurs perspectives lensemble des contributions ralises au cours de ce mmoire.

CHAPITRE 1 LES RSEAUX SANS FIL AD-HOC 1.1 Historique des rseaux Ad-Hoc

Au dbut, le dveloppement des rseaux Ad-Hoc a t le rsultat de la demande du milieu militaire pour le dploiement rapide dinfrastructures de tlcommunication pouvant survivre aux pannes et aux attaques. Un rseau centralis autour de stations de base nest pas une bonne option dans ce milieu car elles doivent tre dployes en premier lieu (presque impossible dans un terrain hostile) et le rseau est vulnrable dans le cas o une ou plusieurs de ces stations de base sont dtruites. Face ces limites, en 1972 le dpartement de la dfense amricaine, en particulier DARPA (The Defense Advanced Research Projects Agency), a sponsoris le programme de recherche PRNet (Jubin et Tornow, 1987) (Packets Radio Network). Ce projet traitait en particulier la problmatique de routage et laccs au mdia dans un rseau de communication multi-sauts par onde radio. En 1983, ce projet a volu vers le programme SURAN (SUrvivable RAdio Networks) qui traitait en particulier la problmatique de la scurit, la gestion dnergie et la capacit de traitement (Freebersyser et Leiner, 2001). Les objectifs taient daugmenter le nombre de nuds supports par PRNet dans une zone gographique tendue et rduire la consommation dnergie en dveloppant des nouveaux algorithmes de routage. Le LPR (Low-cost Packet Radio) a t le fruit de ces recherches en 1987 (Fifer et Bruno, 1987). La technologie LPR offrait la commutation de paquets et des amliorations aux niveaux de la scurit et la gestion de la consommation de lnergie par les nuds. Ds 1990, les ordinateurs portables ont t quips de cartes sans fil et de ports infrarouge qui permettaient la communication directe et sans intermdiaire entre les ordinateurs portables. Ainsi, la technologie de PRNet tait devenue accessible au grand public avec de

5

relles applications civiles. LIEEE (Institute of Electrical and Electronics Engineers) adoptait alors le terme rseaux Ad-Hoc pour le standard IEEE 802.11 des rseaux locaux sans fil. Avec limportance que prenaient les rseaux sans-fil, en 1994, le DARPA sponsorisait les programmes GloMo (Global Mobile Information Systems) et NTDR (Near-term Digital Radio). Ces programmes avaient pour but le dveloppement des rseaux Ad-Hoc sans fil qui offraient un environnement de communication multimdia nimporte quand et nimporte o (Leiner, Ruther et Sastry, 1996). Le NTDR est encore utilis actuellement par larme amricaine. Un certain nombre de standards ont suivi ce dveloppement des rseaux Ad-Hoc. Cest ainsi que le groupe de travail MANET (Mobile Ad-Hoc Networks) a t fond au sein de lIETF (The Internet Engineering Task Force). Ce groupe avait pour but dessayer de standardiser les protocoles de routage dans les rseaux Ad-Hoc (Corson et Macker, 1999). Plusieurs applications militaires et civiles ont suivi, par la suite, cette mergence des rseaux Ad-Hoc.1.2 Applications des rseaux Ad-Hoc

Les rseaux Ad-Hoc ont t dvelopps en premier lieu pour les communications dans le domaine militaire. Plusieurs applications de ces rseaux ont t mises en place surtout par larme amricaine :

En 1997, cette dernire a procd au test de lInternet Tactique (IT) (Freebersyser et Leiner, 2001) et la numrisation du champ de bataille en grandeur nature. La grande rvolution de lIT a t lintroduction du Force XXI Battlefield Command Brigade and Below (FBCB2) qui est une plateforme de communication base sur MANET et qui permet aux soldats de traquer en temps rel les forces allies et adverses dans le champ de bataille (FBCB2, 2008).

6

Une autre application au sein de larme amricaine est lELB ACTD (Extending the Littoral Battle-space Advanced Concept Technology Demonstration). Cette exprimentation avait pour but de dmontrer la possibilit doffrir une architecture de communication entre les navires militaires en mer et les soldats sur terre par lintermdiaire dun lien arien.

Dautres applications et projets de MANET sont actuellement en cours de dveloppement au sein de DARPA. On pourra noter en particulier le projet ITMANET (Information Theory for Mobile Ad-Hoc Networks) qui a pour but le dveloppement et lexploitation de puissantes thories concernant MANET. Ce projet stendra sur cinq ans et prendra fin en 2011 (ITMANET, 2008).

Dun autre cot, avec lmergence des technologies sans fil et la prolifration des terminaux quips de carte 802.11, des applications civiles sont apparues. On pourra en distinguer plusieurs :

Les rseaux mobiles sans fil Ad-Hoc pourraient tre utiliss dans les cas durgence et les oprations de recherche et secours lors dun dsastre (feux, inondation, sisme). Ces oprations de secours peuvent parfois avoir lieu l o les infrastructures de tlcommunication sont inexistantes, endommages ou lors dun besoin de dploiement rapide. Cest dans ce contexte que le NCS (National Communications System) a mis en place le projet NS/EP Priority Telecommunications (Suraci, Ephrath et Wullert, 2007). Cette infrastructure de tlcommunication contient le service GETS (Government Emergency Telecommunications Service), le service TSP (Telecommunications Service Priority) et finalement le service WPS (Wireless Priority Service).

Les rseaux mobiles sans fil Ad-Hoc pourraient tre utiliss pour simplifier l'intercommunication et le partage des applications entre plusieurs quipements mobiles (PDA, ordinateur portable, tlphone cellulaire ou autres) dans une zone limite quon appelle Personal Area Network (PAN). Ce principe a offert des nouvelles perspectives pour les jeux en rseau. En effet, Sony a offert le premier modle de console de jeu

7

portable PSP permettant le jeu en rseau (jusqu 16 consoles) grce la technologie AdHoc (Sony, 2008). Ainsi, avec lmergence que prennent les appareils mobiles, PAN est trs prometteur pour MANET.

Les rseaux Mesh sans fil constituent une technologie qui permettra aux rseaux Ad-Hoc dtre au cur des infrastructures de tlcommunication de demain (Bruno, Conti et Gregori, 2005). En effet, la flexibilit et la facilit quoffrent les rseaux Ad-Hoc permettent dtendre les rseaux Mesh et offrir de nouveaux services. La Figure 1.1 donne un exemple de possible interaction entre les rseaux Mesh et les rseaux Ad-Hoc sans fil.

Dautres applications sont actuellement en test comme le projet Vehicular Ad-Hoc Networks (VANET) (Yi et Moayeri, 2008). Ce type de rseau permet la communication entre les vhicules ainsi quavec les infrastructures de tlcommunication. Ainsi, un conducteur sur la route pourrait avoir un accs fiable et rapide aux informations pratiques (par exemple, ltat du trafic, la gestion de distance de scurit entre les voitures, etc). La norme 802.11p a t associe par IEEE ce projet pour grer les communications entre les entits trs forte mobilit jusqu 200km/h (Palmen et al., 2006).

Les rseaux Ad-Hoc offrent une solution faible cot pour tendre la couverture des points daccs Internet et des rseaux sans fil (UMTS, WiMax). Par exemple, les passagers dun train auraient laccs Internet grce des points daccs installs dans chaque wagon. Ces points daccs seraient relis entre eux et connects Internet par la suite via une connexion Ad-Hoc des passerelles dans les gares. Ce genre de solution est offert par une socit anglaise NOW Wireless (NowWireless, 2008). Elle commercialise dautres applications trs intressantes de la technologie Ad-Hoc : Feux de signalisation, services de pompier et police, transport intelligent, solutions pour le rseautage domestique, tlmatiques et solutions de rseaux de capteurs. Ces solutions sont dployes dans plusieurs villes (Coventry, Glasgow).

8

Figure 1.1

Extension des rseaux Mesh grce aux rseaux Ad-Hoc. Tire de Bruno, Conti et Gregori (2005, p. 126)

Les rseaux Ad-Hoc ont trouv leur place dans les rseaux de capteurs (Wireless Sensor Networks). Ce type de rseau a plusieurs applications dans les domaines commercial et environnemental (rseaux de capteurs pour observer les tsunamis, les feux de forts, la pollution, le climat, les activits sismiques, etc) (Xu, 2002). Un exemple dans le domaine commercial est la possibilit de recueillir des donnes fournies par des tiquettes intelligentes RFID par lintermdiaire de communications Ad-Hoc (utiliser par les transporteurs pour garantir la traabilit des marchandises).

9

Dans le domaine routier, le Vehicular Sensor Network (VSN) est une couche de plus dans les rseaux VANET (Voir Figure 1.2) et qui pourrait tre utilis par exemple pour la surveillance du trafic routier (Chenxi et al., 2008).

Figure 1.2 1.3 Dfis dans les rseaux Ad-Hoc

VANET et VSN.

Les rseaux Ad-Hoc ont hrit des problmes traditionnels des communications et des rseaux sans fil. Sajoutent cela, de nouveaux problmes et dfis lis spcifiquement la nature des rseaux Ad-Hoc. Ainsi, les principaux problmes de ces rseaux sont :

Interfrences radio : Avec la croissance de lutilisation des appareils sans fil, des

interfrences radio peuvent avoir lieu si des transmissions se font sur une mme

10

frquence ou des frquences proches lune de lautre. Ces interfrences peuvent perturber les communications radio et nuire leur qualit.

Erreurs de transmission : Les problmes et la particularit des transmissions radio

engendrent plus derreurs de transmission comparativement aux transmissions sur cble.

Dbit : Le dbit reste un grand challenge pour le dveloppement de certains services dans

MANET (IPTV, vido).

Signal : La puissance du signal engendre la porte radio dun terminal sans fil. Or dans

MANET, ce facteur est trs important pour garantir une certaine densit et ainsi offrir de meilleures performances ces rseaux.

Collisions : Dans un environnement sans fil, il est impossible un terminal de dtecter

les collisions lors de ses transmissions. En effet, pour dtecter les collisions, le terminal doit faire la transmission et lcoute en mme temps, ce qui est impossible.

nergie : Dans un monde de mobilit, chaque nud a la responsabilit dacheminer les

paquets qui arrivent dun nud et de les transmettre vers un nud voisin. Or lacheminement des paquets vers dautres nuds consomme de manire significative lnergie dun terminal. Dun autre ct, la batterie de chaque terminal mobile a des ressources limites et risque de causer des problmes si un terminal ne dispose pas dassez dnergie pour garantir le routage des paquets vers les autres nuds.

Routage : Chaque nud dans un rseau Ad-Hoc agit comme un terminal ou un routeur.

Ainsi, le dveloppement des protocoles Ad-Hoc doit prendre en compte plusieurs facteurs dont la mobilit, changement brusque de la topologie, maintenir dynamiquement les routes et la gestion de la consommation de lnergie lors du routage des paquets.

11

Dcouverte des services : Les rseaux Ad-Hoc sont des rseaux dynamiques. Chaque

nud peut se joindre ou quitter le rseau tout moment. Il est important doffrir chaque nud qui se joint un rseau, un mcanisme rapide et efficace pour dcouvrir les services offerts par les nuds existants.

Scurit : Les rseaux Ad-Hoc soulvent de nombreux problmes de scurit. Ces

problmes sont dus essentiellement aux protocoles de routage, lenvironnement sans fil et la nature de ces rseaux.

Qualit de Service (QoS) : La mobilit des nuds dans les rseaux Ad-Hoc rend trs

complexe la tche doffrir une bonne qualit de service.

Mobilit : La mobilit a un impact trs important sur les protocoles de routage, la

topologie et les performances du rseau, les services et la QoS.1.4 Protocoles de routage pour les rseaux Ad-Hoc

Le routage dans les rseaux Ad-Hoc prsente des dfis plus complexes en comparaison avec le routage dans les rseaux filaires traditionnels. En effet, une stratgie intelligente de routage est ncessaire pour supporter la nature et les paramtres du rseau (la mobilit, le nombre de nuds, la densit du trafic, la qualit du service et la superficie du rseau). Dans ce contexte, le groupe de travail MANET a t fond au sein de lIETF pour dfinir les spcifications des protocoles de routage pour les rseaux sans fil Ad-Hoc. Ce groupe a dfini trois types de protocoles : les protocoles proactifs, les protocoles ractifs et les protocoles hybrides.

12

1.4.1

Les types de protocoles

Protocoles de routage proactifs

Les protocoles proactifs entretiennent en permanence les routes vers chaque nud du rseau et maintiennent jour les informations et les tables de routage. Les routes sont donc tablies lavance et disponibles immdiatement lorsquelles sont sollicites. Ces protocoles reposent sur les principes du routage bas sur ltat des liens (Link-State) (McQuillan, Richer et Rosen, 1979) ou bas sur les vecteurs de distance (Distance Vector) dj utiliss dans les rseaux filaires (Perlman, 2000). Mais les ressources trs limites dans les rseaux Ad-Hoc empchent lutilisation des protocoles traditionnels dj utiliss dans les rseaux filaires. En effet, la bande passante est trs sollicite lors des changes des messages entre les nuds pour maintenir les chemins et les tables de routage dans le cas des protocoles utilisant ltat des liens ou les vecteurs de distance. Ainsi, de nouveaux protocoles ont t proposs pour pallier les problmes des protocoles traditionnels et surtout le fort taux de trafic de contrle. Dans lapproche base sur ltat des liens, chaque nud envoie priodiquement des messages de contrle ou des messages dtat des liens ses voisins et par la suite au reste des nuds du rseau. Une fois quun nud reoit ces messages, il maintient jour une vue dun sous ensemble de la topologie du rseau et applique un algorithme de plus court chemin (par exemple, lalgorithme de Dijkstra (Dijkstra, 1959)) pour dterminer les chemins vers les autres nuds (Cormen et al., 2001) . Lavantage des protocoles bass sur ltat des liens est leur possibilit de trouver immdiatement des routes alternatives dans le cas o un lien est perdu. Plusieurs routes peuvent tre utilises simultanment vers une mme destination pour rpartir la charge du trafic ou pour garantir une meilleure qualit de service. Un exemple de protocole bas sur ltat des liens est OLSR (Optimized Link State Routing) (Clausen et Jacquet, 2003). Cet algorithme est le sujet principal de cette recherche et il est prsent plus en dtail la section 1.5 de ce chapitre. Dans lapproche base sur les vecteurs de distance, chaque nud transmet tous ses voisins des copies priodiques de sa table de routage. Ces mises jour permettent chaque nud de

13

connatre les modifications apportes la topologie. Le nom de vecteur de distance provient du fait que les routes sont donnes comme un vecteur (distance, direction); La distance reprsente une mtrique, alors que la direction dfinit le prochain saut. Les protocoles bass sur les vecteurs de distance utilisent lalgorithme de Bellman-Ford (Bellman, 1957; Ford et Fulkerson, 1962). Le protocole DSDV (Destination-Sequenced Distance-Vector) est un protocole proactif bas sur les vecteurs de distance (Perkins et Bhagwat, 1994).Protocoles de routage ractifs

Le principe des protocoles ractifs est de crer et maintenir les routes selon les besoins. Ainsi, aucune route ou information de routage ne sera calcule tant quun nud na pas initi une communication pour demander une route vers le nud destinataire. Lorsquun nud a besoin dune route pour communiquer avec le destinataire, une procdure de dcouverte de route par inondation est lance dans tout le rseau. Grce cette mthode, les nuds du rseau ne gnrent aucun trafic de contrle sans quil soit ncessaire. Ceci permet de rduire la charge du trafic dans le rseau. Par contre, au moment de linondation pour la cration dune route, le mcanisme est trs coteux au niveau de la bande passante car tous les nuds participent au mcanisme. Sajoute cela, durant cette phase de recherche de route, les paquets de donnes envoyer seront mis en attente en attendant la disponibilit dune route. Ceci entrainera une grande temporisation des paquets et un dlai dattente. Le protocole AODV (Ad-Hoc On demand Distance Vector) est un exemple de protocole de routage ractif que nous allons dtailler dans le paragraphe 1.4.2 (Perkins, Royer et Das, 2002). La Figure 1.3 donne une nomenclature et une classification des principaux protocoles proactifs, ractifs et hybrides dvelopps ces dernires annes (Karmakar et Dooley, 2008). Dans la suite, on explicitera plus en dtail certains protocoles prsents dans la Figure 1.3.

14

Figure 1.3

Classification des protocoles de routage Ad-Hoc.

15

Protocoles de routage hybride

Ce type de protocole combine les mcanismes des protocoles proactifs et ractifs. Dans cette approche, les protocoles hybrides utilisent les mthodes proactives (messages priodiques de contrle) pour dcouvrir les routes dans un voisinage prdfini. Les techniques dinondation des protocoles ractifs sont utilises pour obtenir les routes vers les nuds lointains.1.4.2 Descriptions de certains protocoles de routage pour rseaux Ad-Hoc

Le protocole AODV

AODV (Ad-Hoc On demand Distance Vector) est un protocole de routage ractif bas sur les vecteurs de distance (Perkins et Royer, 1999; Perkins, Royer et Das, 2002). Il est une combinaison dune part de DSDV (Destination-Sequenced Distance Vector Protocol) avec son routage de saut par saut (Perkins et Bhagwat, 1994), et de DSR (Dynamic Source Routing Protocol) avec ses mcanismes de dcouverte et maintenance des routes (Broch, Johnson et Maltz, 2002). Avec ses mcanismes de dcouverte et de calcul de routes sur demande, AODV rduit de faon significative la consommation de ressources dans le rseau. On ajoute cela le fait quil utilise les numros de squence dans ses messages de contrle pour pallier les problmes de boucle et comptage linfini de lalgorithme de Bellman-Ford utilis dans les protocoles bass sur les vecteurs de distance (Bellman, 1957; Ford et Fulkerson, 1962; Perkins, Royer et Das, 2002). Mais lorsquil sagit dun rseau dense, le protocole devient trs coteux lors du lancement des procdures de dcouverte de routes. Le dlai dattente moyen devient aussi grand lorsquil sagit dun rseau o les nuds ont une grande mobilit. Dans ce cas, la topologie du rseau est trs instable et de nombreuses routes doivent tre recalcules.Dcouverte des routes : Avec le protocole AODV, chaque nud doit maintenir une liste de

ses voisins actifs. Cette liste est obtenue par un change priodique des messages HELLO de chaque nud avec ses voisins immdiats. Quand un nud source S veut envoyer des donnes

16

un destinataire D et quaucune route vers cette destination nest stocke dans la table de routage de la source, le nud S initialise une procdure de dcouverte de routes. La source S envoie ses voisins une demande de route RREQ (Route REQest) qui contient ladresse de S, lidentifiant de la requte, un compteur de squence, ladresse de D et le compteur de nombre de sauts avec une valeur initiale zro. Chaque nud qui reoit le message recherche dans sa table de routage locale sil existe une route vers le nud D sinon le nud qui traite la requte RREQ incrmente le nombre de sauts et la diffuse nouveau. Lorsque la requte atteint la destination D ou un nud qui connat une route vers la destination, une rponse RREP (Route REPly) est diffuse sur la mme route de rception du RREQ (chemin inverse). La rponse RREP contient ladresse source, ladresse de destination, le nombre de sauts, un numro de squence de destination et la dure de vie du paquet. La rponse RREP passe par la route inverse vers le nud source S. Ainsi chaque nud, sur cette route, enregistre une entre dans sa table de routage local vers le nud destination avant de renvoyer le paquet. Une fois la source S reoit le message, elle commence envoyer les donnes vers D (Voir Figure 1.4).

Figure 1.4

Procdure de demande de recherche de route.

17

Entretien des routes : Lchange des messages HELLO entre les voisins immdiats permet

de mettre jour la liste des voisins de chaque nud. Lorsquun nud N dtecte quun autre nud Q nest plus accessible (Q a quitt le rseau ou est hors port radio), N procde une mise jour des liens dans sa table de routage. En effet, il recherche dans sa table de routage toutes les routes qui passent par le nud Q et les dtruit avant dannoncer ses voisins actifs que la route passant par le nud Q nest plus valide. Un message RERR (Route ERRor) est envoy alors au nud source. Ainsi, la mise jour est diffuse travers le rseau saut-parsaut et le nud source initie une nouvelle procdure de recherche de route vers la destination.Le protocole OLSR

Optimized Link State Routing (Clausen et Jacquet, 2003) est un protocole de routage proactif bas sur ltat des liens pour les rseaux sans fil Ad-Hoc. Ce protocole a t choisi par le groupe de travail MANET de lInternet Engineering Task Force (IETF) comme lun des principaux protocoles de routage pour les rseaux Ad-Hoc. Lavantage dOLSR est quil utilise une technique optimise base sur des nuds appels relais multipoints MPR (MultiPoint Relays) pour une diffusion optimise des messages de contrle. Ceci rduit considrablement la charge du trafic dans le rseau. Les relais multipoints sont choisis aprs la phase de dcouverte des voisins de tous les nuds du rseau en utilisant les messages HELLO. Ces messages permettent chaque nud davoir une vision de ses voisins immdiats et les voisins 2-sauts. Le choix des MPR se fait alors en se basant sur les informations changes avec les messages HELLO. Un autre type de message de contrle de topologie TC (Topology Control) permet pour chaque nud de diffuser travers le rseau, la liste des nuds quils lont choisi comme MPR. Grce aux messages TC, tous les nuds calculent leur table de routage pour chaque destination dans le rseau. Ce protocole sera dtaill dans la section 1.5 de ce chapitre.Le protocole HOLSR

Hierarchical Optimized Link State Routing (Villasenor-Gonzalez, Ying et Lament, 2005) est un protocole bas sur les spcifications du protocole OLSR. HOLSR se classifie comme tant

18

un protocole proactif hirarchique adapt pour les rseaux sans fil htrognes grande chelle. Les rseaux htrognes sont des rseaux multifournisseurs o plusieurs gnrations de rseaux sont interconnectes (par exemple GSM, UMTS, WI-FI, WIMAX, satellite, etc). Ces types de rseaux sont caractriss par des nuds mobiles ayant des capacits de communication distinctes, une large topologie et un dfi dinteroprabilit (par exemple, les rseaux militaires). Or les protocoles de routage dj utiliss dans les rseaux Ad-hoc ne sadaptent pas aux rseaux htrognes. En effet, dans le cas dOLSR, le volume des messages de contrle augmente avec la densit et lchelle du rseau ce qui diminue les performances du protocole. Sajoute cela, limpossibilit de reconnatre les capacits de transmission des diffrents nuds et den tirer profit. Face ces limites, HOLSR a t dvelopp pour amliorer les performances, lextensibilit et rduire le volume des messages de contrle du protocole OLSR dans les rseaux htrognes grande chelle en utilisant au mieux les liens grand dbit. Le protocole HOLSR divise la topologie du rseau en plusieurs niveaux logiques. Les nuds, avec des capacits de transmission limites, sont classs dans le niveau 1. Les nuds de ce niveau sont regroups en plusieurs clusters du niveau 1 (Voir Figure 1.6). Ces nuds peuvent tre par exemple des soldats avec des appareils de communication porte limite et des liens 1 Kbps (Voir Figure 1.5). Le niveau 2 est constitu des quipements avec une ou deux interfaces sans fil qui sont capables de communiquer avec les nuds du niveau 1 et en mme temps relayer les messages au niveau 2. Les quipements du niveau 2 sont organiss en plusieurs clusters du niveau 2 et ils utilisent des moyens de communication diffrents de ceux du niveau 1 comme par exemple une bande radio. Dans la Figure 1.5, le niveau 2 est reprsent par les vhicules de combat avec des liens radio de 16 kbps.

19

Figure 1.5

Exemple de rseau htrogne grande chelle. Tire de Defence R&D Canada (2004)

De son ct, le niveau 3 reprsente les nuds haute capacit de transmission et possdant jusqu trois interfaces sans fil. Ces types de nuds peuvent communiquer avec les nuds des niveaux 1 et 2 ainsi quavec les nuds de niveau 3 (Voir Figure 1.6). Dans la Figure 1.5, le niveau 3 est reprsent par les vhicules trs grande capacit de transmission avec un lien de 400 Kbps. Durant la phase dinitialisation, le protocole HOLSR configure des nuds comme des clusters. Chaque nud dclar comme cluster, envoie des messages priodiques appels CIA (Cluster ID Announcement) pour inviter ses voisins proches joindre son cluster. Ces messages sont envoys avec les messages HELLO utiliss par OLSR afin de limiter le nombre de paquets envoys sur le rseau. Ceci permet de former les clusters de chaque niveau. Une fois la hirarchie du rseau est construite, le routage des messages entre les clusters se fait en respectant cette hirarchie. Les simulations avec OPNET (Villasenor-Gonzalez, Ying et Lament, 2005) ont dmontr que le protocole HOLSR amliore le rendement du mcanisme de routage dOLSR en

20

rduisant considrablement les messages de contrle TC. Ainsi, HOLSR amliore et adapte au mieux lextensibilit du protocole OLSR dans les vastes rseaux htrognes.

Figure 1.6 Modle hirarchique dHOLSR. Tire de Villasenor-Gonzalez, Ying et Lament (2005, p.121) Le protocole ZRP

ZRP (Zone Routing Protocol) (Haas et Pearlman, 1998; Hass, Pearlman et Samar, 2002) est un exemple de protocole hybride qui combine les approches proactive et ractive afin den tirer des avantages. Le protocole ZRP divise le rseau en diffrentes zones qui peuvent tre de diffrentes tailles. En effet, il dfinit pour chaque nud S une zone de routage exprime en nombre de sauts maximal . Ainsi, la zone de routage de S inclut tous les nuds qui sont une distance au maximum de sauts par rapport S. Les nuds qui sont exactement sauts de S sont appels nuds priphriques. lintrieur de cette zone, ZRP utilise son protocole proactif mais lextrieur de sa zone de routage il utilise son protocole ractif.

21

Figure 1.7

Zone de routage du nud S ( = 2 sauts).

Les mcanismes de routage de ZRP sont donc bass sur deux protocoles, IARP (IntrAzone Routing Protocol) (Haas, Pearlman et Samar, 2002c) et IERP (IntErzone Routing Protocol) (Haas, Pearlman et Samar, 2002b). Mais avant de passer la phase de routage, chaque nud doit connatre ses voisins. Dans ce but, ZRP utilise le protocole de contrle daccs au support (MAC) pour connatre les voisins immdiats ou le protocole NDP (Neighbour Discovery Protocol) pour la transmission et la gestion des changes de messages HELLO (Hass, Pearlman et Samar, 2002). Pour un nud S donn, ZRP utilise par la suite le protocole IARP pour dcouvrir les routes vers tous les autres nuds qui se trouvent dans la zone de routage de S. Par contre, le protocole IERP est utilis la demande pour chercher les routes entre S et une destination D qui se trouvent lextrieur de la zone de routage de S (Voir Figure 1.7). Un troisime protocole BRP (Bordercast Resolution Protocol) (Haas, Pearlman et Samar, 2002a) est inclus avec IERP pour fournir des services de bordercasting et dfinir les

22

frontires des zones c.-.-d. les nuds priphriques de chaque nud du rseau. La Figure 1.8 donne larchitecture globale de ZRP.

Figure 1.8 1.5 1.5.1 Le protocole OLSR

Larchitecture globale de ZRP.

Description du protocole OLSR

Le protocole OLSR (Optimized Link State Routing) appartient la famille des protocoles proactifs et il a t dvelopp pour les rseaux Ad-Hoc (Clausen et al., 2001; Clausen et Jacquet, 2003; Jacquet et al., 2001). Il a t dvelopp dans le cadre du projet HIPERCOM lINRIA. OLSR a t retenue par le groupe MANET de lIETF en vue dune standardisation. La version 1 dOLSR a t standardise ds 2003 et elle est spcifie dans le RFC3626 (Clausen et Jacquet, 2003). La version suivante, OLSR v2 est en cours de dveloppement et de standardisation. Cette version apporte certaines optimisations et des petites modifications, mais en gnrale elle ressemble OLSR v1. Le protocole OLSR utilise des changes priodiques de messages HELLO pour permettre chaque nud de connatre ces voisins 1-saut et 2-sauts. Par la suite, OLSR utilise une diffusion optimise des messages de contrle grce lutilisation des relais multipoints MPR. Ceci permet chaque nud davoir une vue de la topologie et ainsi utiliser un algorithme de plus court chemin pour calculer sa table de routage vers toutes les destinations.

23

Linondation par relais multipoints rduit considrablement la charge du trafic dans le rseau car juste une partie des nuds participent au processus dinondation. Ainsi, le protocole OLSR est trs souhaitable pour les rseaux trs denses. Le protocole OLSR a t mis en application dans de grands projets. La DARPA a choisi OLSR comme protocole de rfrence pour les rseaux tactiques (Brown et al., 2003). Dautres applications dans le domaine civil ont t ralises. Avec ce grand dveloppement dOLSR, de nombreuses extensions de ce protocole sont en chantier, on pourra noter par exemple : QOLSR : OLSR avec qualit de service (QoS) OLSR v6 : OLSR avec auto-configuration MOLSR : Multicast OLSR SOLSR : OLSR avec scurit PS-OLSR : OLSR avec power saving Dtection de voisinage

1.5.2

Les rseaux Ad-Hoc sont caractriss par une topologie dynamique et changeante. Afin de dtecter tout changement dans le rseau et gnrer les informations sur la topologie, le protocole OLSR se base essentiellement sur la dtection et la mise jour de la liste des voisins de chaque nud. Dans tout ce qui suit, on considre que tous les nuds ont une seule interface sans fil. On peut classifier les liens entre deux nuds en trois catgories : Asymtrique : Un lien est dit asymtrique si le premier nud reoit les messages de

lautre nud mais il na pas reu la confirmation que lautre nud lentend.Symtrique : Un lien est dit symtrique si chaque nud entend lautre. Perdu : Un lien est dit perdu si ce lien a t dclar prcdemment tant symtrique ou

asymtrique mais ce moment aucun message nest reu du nud dclar perdu.

24

Dans le but de dcouvrir les nuds voisins, chaque nud envoie priodiquement tous ses voisins des messages HELLO. Ces messages contiennent les informations concernant les nuds voisins, les nuds qui sont choisis comme MPR (c.--d. MPRSelector set) et la liste des nuds qui sont dclars par ce nud comme asymtriques. La Figure 1.9 dcrit le processus de dcouverte des voisins entre deux nuds A et B. En premier, le nud envoie B un message HELLO qui ne contient aucune information. Une fois B reoit ce message, il enregistre A comme voisin asymtrique car B ne trouve pas son adresse dans le message. Le nud B envoie par la suite un message HELLO dclarant quil entend A. Ce dernier trouve son adresse dans le message et enregistre B comme voisin symtrique. son tour, B trouve son adresse dans le message HELLO de A et dclare ce dernier comme voisin symtrique.

Figure 1.9

change des messages HELLO.

Cest ainsi que chaque nud du rseau gnre priodiquement des messages HELLO avec une dur de vie TTL=1. Ces messages sont reus par les voisins 1-saut et ne sont pas relays par ceux-ci. La Figure 1.10 prsente le format des messages HELLO. Chaque message se compose en plusieurs sections qui correspondent diffrents tats de liens. La liste des adresses des interfaces voisins qui possdent un lien symtrique sont lists dans les champs Neighbor Interface Address.

25

Figure 1.10 Format du message HELLO. Tire de Clausen et Jacquet (2003, p. 27)

Le champ Link Code de taille 8 bits, contient la fois les informations concernant les liens vers les nuds voisins et le type de ces derniers. Le Tableau 1.1 et le Tableau 1.2 prsentent la liste des valeurs possibles pour les deux champs de type de lien et type de voisin selon les spcifications du RFC3626 (Clausen et Jacquet, 2003). Tableau 1.10 1 2 3

Champs Link Code4 5 6 7

Type de voisin Tableau 1.2

Types de liens

Valeurs possible pour le champ Link CodeTypes de lien

UNSPEC_LINK ASYM_LINK SYM_LINK LOST_LINK SYM_NEIGH MPR_NEIGH NOT_NEIGH

Pas dinformations Lien asymtrique Lien symtrique Lien est perdu Types de voisin Voisin symtrique Voisin a t slectionn comme MPR Pas de voisins / Pas encore symtrique

26

Lensemble des voisins immdiats (ou 1-saut) dun nud s et qui possdent un lien symtrique avec ce dernier est not N 1 ( s ) . Les voisins 2-sauts dun nud s sont dfinis comme tant lensemble suivant : N 2 ( s ) = {y y s y N 1 ( s ) (x N 1 ( s ) )[ y N 1 ( s )]} . Ces deux ensembles N 1 ( s ) et N 2 ( s ) de chaque nud s sont construits grce aux changes priodiques des messages HELLO. Ceci permet tous les nuds davoir une vision 1-saut et 2-sauts de la topologie du rseau et ainsi avoir toutes les informations ncessaires pour construire les chemins entre une source et une destination dans la zone 1-saut et 2-sauts.1.5.3 Slection des Relais Multipoints

La technique dinondation est utilise dans plusieurs algorithmes de routage pour la diffusion des messages tous les nuds dans un rseau. Avec cette technique, chaque nud renvoie une copie du message quil reoit pour la premire fois tous ces voisins immdiats. Ce mcanisme a un impact sur les ressources du rseau en termes de bande passante. Or, les rseaux Ad-Hoc ont des ressources limites et les enjeux de performance sont capitaux. Dans ce contexte, le protocole OLSR utilise une technique appele inondation par relais multipoint pour optimiser la diffusion travers le rseau et ainsi rduire la charge du trafic. Ainsi, chaque nud s slectionne un sous ensemble de points appels MPR (Multipoint Relay) parmi ses voisins de N 1 ( s ) et qui lui permettent dtre rejoint par tous les nuds dans N 2 ( s ) (Clausen et Jacquet, 2003). Or, la connaissance de N 1 ( s ) et N 2 ( s ) de chaque nud s permet la diffusion des messages dans tout le rseau (Jacquet et al., 1997). Lchange priodique des messages HELLO permet chaque nud dans le rseau de mettre jour ses ensembles N 1 ( s ) et N 2 ( s ) . Cest ainsi que lensemble des relais multipoints est recalcul chaque changement dans la topologie du rseau.

27

Lensemble MPR(s ) des relais multipoints dun nud s forme un arbre recouvrant et il est dfini de la manire suivante : a) MPR( s ) N 1 ( s ) b)

(y N 2 ( s) )(x MPR( s) )[ y N1 ( s)]

La Figure 1.11 montre la diffrence entre linondation par relais multipoints et linondation classique. On remarque que dans le cas classique, il faut 24 retransmissions pour atteindre les nuds 3-sauts du nud s . Alors que dans le cas o on utilise les relais multipoints, seulement 11 retransmissions sont ncessaires pour avoir les mmes rsultats.

Figure 1.11

Diffusion par inondation classique vs inondation par relais multipoints.

Dans un cas gnral, pour atteindre le voisinage N 2 ( s ) dun nud s, il faut MPR( s ) + 1 missions. Donc pour minimiser le nombre dmissions possibles dans le rseau et par la suite augmenter les performances, il faut trouver un nombre minimal de relais multipoints pour chaque nud (c.--d., minimum de MPR(s ) ). Or ce problme du choix des MPR est un problme NP-complet car ceci est quivalent calculer un sous ensemble dominant dans un graphe (Qayyum, Viennot et Laouiti, 2002). Plusieurs heuristiques ont t proposes cet effet dans plusieurs articles (Clausen et Jacquet, 2003; Mans et Shrestha, 2004; Qayyum, Viennot et Laouiti, 2002) .

28

Algorithme 1.1

Slection des MPR par OLSR (RFC3626).

Pour la suite de ce mmoire, seul lalgorithme vorace prsent dans le RFC3626 sera considr (Clausen et Jacquet, 2003). Cette heuristique de slection des MPR est prsente dans lAlgorithme 1.1. Ce algorithme reprsente une solution optimale log(n) prs (Laouiti, Qayyum et Viennot, 2000; Viennot, 1998).

29

La Figure 1.12 prsente un exemple dapplication de lalgorithme dcrit prcdemment pour la slection de lensemble des relais multipoints MPR(s ) dun nud s .

Figure 1.12 1.5.4

Exemple de slection des relais multipoints.

Dclaration des relais multipoints

LAlgorithme 1.1 est utilis par chaque nud dans le rseau pour construire lensemble des relais multipoints. Afin de fournir les informations sur la topologie ncessaire pour construire les routes et ainsi garantir le routage des paquets, chaque nud qui a t slectionn comme tant MPR, diffuse priodiquement des messages de contrle de la topologie TC (Topology Control) (Clausen et Jacquet, 2003). Ces messages sont reus par tous les nuds mais transmis juste par les MPR. Chaque nud x qui a t slectionn comme MPR maintient une liste des voisins qui lont slectionn comme relais multipoint. On dfinie cette ensemble par :MPRSel ( x) = {y N 1 ( x) x MPR( y )}

30

Chaque message TC (Voir Figure 1.13), envoy par un nud x , contient la liste MPRSel (x) ainsi quun numro de squence (ANSN) associ au message. Ces messages permettent chaque nud de maintenir jour sa table dinformation sur la topologie et ainsi faciliter le calcul de sa table de routage.

Figure 1.13 Format du message TC. Tire de Clausen et Jacquet (2003, p. 42) 1.5.5 Calcule des routes

Chaque nud maintient une table de routage qui lui permet dacheminer les paquets vers un destinataire. Ces tables de routage sont calcules grce lalgorithme de plus courte chemin de Dijkstra (Dijkstra, 1959) en se basant sur les informations conserves par les nuds et aussi les informations fournies par les messages de contrle TC. Ces tables de routage sont recalcules chaque changement survenu dans la topologie et ainsi permettre de mettre jour les routes vers toutes les destinations dans le rseau.1.6 Complexit et comparaison des protocoles de routage

Les tableaux suivants donnent une brve comparaison entre plusieurs protocoles de routage pour les rseaux Ad-Hoc selon leur catgorie proactif, ractif ou hybride (Abolhasan, Wysocki et Dutkiewicz, 2004; Karmakar et Dooley, 2008; Zou, Ramamurthy et Magliveras, 2002).

31

Tableau 1.3WCC WTC SR Frquence des mises jour Priodique

Sommaire des protocoles proactifsNuds Critiques MH Advantages Diffusion optimise des messages de contrle par rapport aux autres protocoles bass su ltat des liens. Idal pour les rseaux MANET htrognes grande chelle. Simple, absence de problme de boucle de routage et de compteur linfinie. Surdbit de routage est petit par rapport DSDV; Schma dadressage simple. Petit surdbit de routage. Rduit le nombre de paquets de mise jour dans le rseau. Petit surdbit de routage et consomme peu de mmoire par rapport tous les protocoles proactifs plats. Petit WCC. Inconvnients Les informations sur les voisins 1-saut et 2-sauts sont ncessaires. Les informations sur les voisins 1-saut et 2-sauts sont ncessaires; Ajout de nouvelles structures pour former et maintenir les clusters. Importante activit sur le rseau lors des demandes de mise jour; Convergence lente; Tendance crer des boucles de routage dans les rseaux trs grands. La complexit en temps WTC est trs grande par rapport DSDV et WRP en cas des ruptures des liens entre les racines des clusters. Ncessite le GPS. Choix non optimal des routes vers les destinations; Consomme beaucoup de mmoire et surcharge le rseau dans le cas des rseaux MANET trs grands. Ajout de nouvelles structures pour former et maintenir les clusters. La charge dans le rseau augmente avec la mobilit des nuds et la taille du rseau.

OLSR

O(N)

O(D)

P

MPR

Oui

HOLSR

O(N)

O(D)

H

Priodique

Racines des clusters

Oui

DSDV

O(N)

O(D)

P

Priodique et surdemande

Non

Oui

CGSR

O(N)

O(D)

H

Priodique

Racines des clusters Non

Non

DREAM

O(N)

O(D)

P

Surdemande Surdemande

Non

STAR

O(N)

O(D)

P

Non

Non

HSR

O(n*l)

O(D)

H

Priodique

Racines des clusters Nud parent Non

Non

TBRPF

O(N)

O(D)

P

Priodique et surdemande Priodique

Oui

Rduit le nombre de paquets de mise jour Choix non optimal des routes FSR dans les rseaux trs vers les destinations. grands. Offre lextensibilit dans Choix non optimal des routes O(D) H Priodique Non Non les rseaux MANET trs LANMAR O(N) vers les destinations. grands. WCC: Worst Case Communication Complexity, c.-.-d. nombre de messages ncessaires pour effectuer une opration de mise jour; WTC: Worst Case Time complexity, c.-.-d. complexit en temps (ou le nombre dtapes) pour effectuer une mise jour; SR : Structure du routage; P: Plat; H: Hirarchique; MH: Messages Hello; N: Nombre de nuds dans le rseau; D: Diamtre du rseau; h: Hauteur de larbre de routage; n: Nombre moyen de nuds dans un cluster; l: nombre de niveaux hirarchiques. O(N) O(D) P Non

Tableau 1.4WCC [DR] WCC [MR] O(2N) WTC [DR] O(2D) WTC [MR] O(2D)

Sommaire des protocoles ractifsSR P RM Non Advantages Adapt aux topologies trs Inconvnients Grand dlai; Ncessite les

AODV

O(2N)

32

dynamiques; Possibilit de routage Multicast.

messages HELLO; Ne supporte pas des routes multiples. Grand dlai.

DSR LMR

O(2N) O(2N)

O(2N) O(2A)

O(2D) O(2D)

O(2D) O(2D)

P P

Oui Oui

Problmes de boucle de routage. Problmes de boucle de routage. Ajout de nouvelles structures O(2X) O(2A) O(2D) O(2B) H Non CBRP pour former et maintenir les clusters. Ncessite des messages HELLO O(2N) O(2D) O(2D) P Oui Multiples routes disjoints. AOMDV O(2N) priodiques. WCC: Worst Case Communication Complexity, c.-.-d. nombre de messages ncessaires pour effectuer une opration de mise jour; WTC: Worst Case Time complexity, c.-.-d. complexit en temps (ou le nombre dtapes) pour effectuer une mise jour; DR: Dcouverte de route; MR : Maintenance de route; SR : Structure du routage; P : Plat; H: Hirarchique; RM: Routes multiples; N: Nombre de nuds dans le rseau; D: Diamtre du rseau; A: Nombre de nuds affects; B: Diamtre de la rgion affect; X: Nombre de clusters dans CBRP.

Routes multiples; Les nuds intermdiaires ne stockent pas les informations sur les routes. Routes multiples. Rduit la charge de communication; Juste les clusters changent les informations de routage.

Tableau 1.5WCC [I] WCC [In,DR] WCC [In,MR] WTC [I]

Sommaire des protocoles hybridesWTC [In,DR] WTC [In,MR]

SR

Advantages Rduit la charge de communication en comparaison avec les protocoles proactifs; Dcouverte rapide des routes en comparaison avec les protocoles ractifs.

Inconvnients Problme de chevauchement des zones entre les nuds.

ZRP

O(n)

O(N+r)

O(N+r)

O(d)

O(2D)

O(2D)

P

Absence de chevauchement des Ncessite le GPS. zones. WCC: Worst Case Communication Complexity, c.-.-d. nombre de messages ncessaires pour effectuer une opration de mise jour; WTC: Worst Case Time complexity, c.-.-d. complexit en temps ou (le nombre dtapes) pour effectuer une mise jour; DR: Dcouverte de route; MR : Maintenance de route; SR : Structure du routage; P : Plat; H: Hirarchique; I: Intra zone; In: Inter zone; N: Nombre de nuds dans le rseau; D: Diamtre du rseau ; d: Diamtre dune zone locale; n: Nombre de nuds dans une zone; r: Nombre de nuds dans le chemin Reply-Path; M : Nombre de zones.

ZHLS

O(N/M)

O(N+r)

O(N+r)

O(d)

O(2D)

O(2D)

H

CHAPITRE 2 SCURIT ET VULNRABILITS DES RSEAUX AD-HOC

Ce chapitre fait la revue de littrature des diffrentes vulnrabilits dans les rseaux Ad-Hoc. Lobjectif est de donner les grandes catgories dattaques dans les rseaux Ad-Hoc et dtailler les vulnrabilits du protocole OLSR. Des solutions pour pallier les problmes de scurit dOLSR seront donnes dans la dernire partie de ce chapitre.2.1 Objectifs de la scurit

Les principaux objectifs de scurit pour les rseaux Ad-Hoc sont regroups sous trois catgories importantes : la confidentialit, lintgrit et la disponibilit. Cette approche classique est dcrite dans (Bishop, 2005).2.1.1 Confidentialit

Lobjectif de la confidentialit est de garantir laccs aux informations seulement pour les utilisateurs ou les systmes autoriss. Dans le contexte des rseaux Ad-Hoc, la confidentialit consiste refuser laccs aux informations changes entre deux nuds dans le rseau par tout nud malveillant ou non dsir. Or, les rseaux Ad-Hoc sont caractriss par la diffusion gnrale des informations, ce qui constitue un vrai challenge pour la confidentialit.2.1.2 Intgrit

Le rle de lintgrit est de garantir la protection des messages ou des informations changes dans le rseau contre toute modification ou altration par une personne non autorise. Dans les rseaux Ad-Hoc, le bon fonctionnement du rseau repose essentiellement sur lchange des messages de contrle fournissant les informations pour le routage. Dans ce contexte, il est important, en premier lieu, de garantir lintgrit des fonctionnalits de routage et des messages de contrle contre toutes les modifications non autorises.

34

En plus de lintgrit, il faut sassurer de limputabilit ou de la non-rpudiation des informations. Cette fonction donne lassurance de lidentit du nud originaire dun message. La non-rpudiation est utile dans la dtection et lisolation des nuds malicieux. Par exemple, si un nud A reoit un faux message de la part dun nud B, la non-rpudiation permet au nud A de dnoncer B et informer les autres nuds que B est compromis.2.1.3 Disponibilit

La disponibilit garantit le fonctionnement en permanence des services et garantit laccs des usagers ces services. La disponibilit est difficilement applicable dans les rseaux Ad-Hoc. En effet, cause de la mobilit des nuds, un protocole de routage ne pourrait pas maintenir toutes les routes vers tous les nuds et surtout les nuds qui quittent le rseau. Mais certains types dattaques pourraient avoir effet sur la disponibilit de nuds participant au rseau ou la disponibilit de certains services (attaques qui puisent les batteries des nuds, attaques par dni de service, etc).2.2 2.2.1 Vulnrabilits et types dattaques dans les rseaux Ad-Hoc Classification dattaques dans les rseaux Ad-Hoc

Les mcanismes de scurit dans les environnements des rseaux Ad-Hoc prsentent de grands dfis (Anjum et Mouchtaris, 2007). Ce type de rseaux a hrit la fois des problmes de scurit des rseaux cbls et aussi ceux des rseaux sans fil. Sajoute cela, la nature des rseaux Ad-Hoc qui se caractrise par une architecture peer-to-peer ouverte, une topologie dynamique et extensible, des ressources limites et un canal radio accessible par tout le monde (Anjum et Mouchtaris, 2007; Mishra, 2008). Les attaques sur les rseaux Ad-Hoc sont gnralement divises en deux catgories :

Attaques passives : Principalement des attaques dcoute de donnes. Attaques actives : Des attaques pour lesquelles un attaquant doit modifier, altrer ou gnrer des messages.

35

Figure 2.1 donne une classification des attaques par rapport aux couches OSI. Pour plus de dtails, voir Tableau 2.1.

Figure 2.1 2.2.2

Classifications des attaques dans les rseaux Ad-Hoc.

Dfense contre les attaques dans les rseaux Ad-Hoc

Plusieurs solutions ont t proposes pour pallier les problmes de scurit dans les rseaux Ad-Hoc. Le Tableau 2.1 prsente des exemples de solutions proposes pour la scurit des rseaux Ad-Hoc.

36

Tableau 2.1Attaques

Solutions proposes pour la scurit dans les rseaux Ad-HocDfinition Solutions proposesPacket Leashes (Hu, Perrig et Johnson, 2003). SEAD (Perkins et Bhagwat, 1994), ARAN (Sanzgiri et al., 2002), ARIADNE (Hu, Perrig et Johnson, 2002), SAODV (Zapata, 2002). FHSS, DSSS (Wang et al., 2006).

Un attaquant pourrait rediriger le trafic entre deux zones Wormhole gographiquement loignes pour crer un vertex dans la topologie et ainsi avoir une bonne position gographique pour contrler le trafic qui passe par lui. Un nud malicieux pourrait perturber le fonctionnement dun Attaque de routage protocole de routage en modifiant les informations de routage, fabriquer les fausses informations de routage ou usurper lidentit dun autre nud. Cest une attaque classique sur la disponibilit du canal de Brouillage (Jamming) Attaque trou noir (Backhole attack) Attaque sur les ressources communication grce la gnration massive dune grande quantit dinterfrence radio. Le but de cette attaque est la falsification des informations de routage ou le dtournement du trafic. Les rseaux MANET sont caractriss par des ressources limites (batterie et bande passante). Une attaque sur les ressources pourrait avoir des consquences sur la disponibilit. Grce cette attaque, un nud malicieux altre les messages et pourrait crer des problmes de boucle de routage, routage de Attaque Byzantine paquets vers des chemins non optimaux, slectionner les paquets rejeter Ce type dattaque est difficile dtecter car le rseau semble fonctionner correctement. Ce type dattaque consiste envoyer dlibrment des DoS Divulgation d'information Rpudiation messages pour causer une saturation de la bande passante et paralyser le rseau. Lchange des informations confidentielles doit tre protges contre lcoute ou laccs non autoris. Ce type dattaque a une consquence sur lintgrit des communications entre les nuds dans le rseau. Lusurpation didentit a pour but la falsification des Usurpation d'identit informations relatives aux identits. Ce qui pourrait conduire lisolement de nuds, lchange de fausses informations de routage et latteinte la confidentialit et lintgrit. SEAD: Secure Efficient Ad hoc Distance vector routing protocol; SAODV: Secure Ad-Hoc On-demand Distance Vector routing; ARAN: Authenticated Routing for Ad-Hoc Networks; ARIADNE: A Secure On-Demand Routing Protocol for Ad-Hoc Networks; FHSS: Frequency-Hopping Spread Spectrum; OSRP: On-demand Secure Routing Protocol; SMT: Secure Message Transmission Protocol; SRP: Secure Routing Protocol for Mobile Ad-Hoc Network; DSSS: Direct-Sequence Spread Spectrum. ARAN (Sanzgiri et al., 2002), SAODV (Zapata, 2002).. SEAD (Perkins et Bhagwat, 1994), ARIADNE (Hu, Perrig et Johnson, 2002), SAODV (Zapata, 2002). SMT (Papadimitratos et Haas, 2003), SRP (Papadimitratos et Haas, 2002). ARAN (Sanzgiri et al., 2002). OSRP (Awerbuch et al., 2002), (Awerbuch et al., 2004). SEAD (Perkins et Bhagwat, 1994). (Ramaswamy et al., 2003).

37

2.3

Vulnrabilits et types dattaques spcifiques au protocole OLSR

Dans un rseau utilisant le protocole de routage OLSR, chaque nud doit correctement gnrer et renvoyer les messages HELLO et TC selon les spcifications du protocole (Clausen et Jacquet, 2003). Une faille dans ce processus aurait un effet sur le bon fonctionnement du protocole de routage et ainsi sur le rseau. Or, le protocole OLSR ne fournit aucune spcification de scurit prendre en compte ce qui rend ce protocole vulnrable plusieurs types dattaques. Dans cette section, on fournira les diffrentes vulnrabilits du protocole OLSR en se basant sur diffrents articles et en particulier sur les travaux de (Adjih et al., 2005) et de (Clausen et Baccelli, 2005).2.3.1 a) Classifications des vulnrabilits et des attaques Gnration incorrecte du trafic

On peut distinguer deux faons de gnrer du trafic de contrle incorrect : 1. Mystification didentit (Identity spoofing) : Un nud malveillant peut gnrer un trafic de contrle prtendant quil est un autre nud. 2. Mystification de lien (Link spoofing) : Un nud malveillant peut signaler une relation de voisinage avec des nuds inexistants ou qui ne font pas partie de ses voisins. Il peut aussi signaler un ensemble incomplet de voisins.Gnration incorrecte du message HELLO

Un nud malveillant peut usurper lidentit dun autre nud en utilisant les messages HELLO (Identity spoofing). Dans la Figure 2.2, le nud malveillant m peut usurper lidentit du nud a en envoyant des messages HELLO prtendant quil est le nud a. Dans ce cas, les nuds i et g vont annoncer ses voisins que le nud a est accessible travers le nud m. Ceci peut causer des conflits de routes vers le nud a dans tout le rseau.

38

Figure 2.2

Usurpation didentit du nud a par m (HELLO).

Attaque sur la slection des MPR par mystification de lien

Le cas qui nous intresse dans ce mmoire est lorsquun nud malicieux oblige ses voisins le choisir comme relais multipoint. On appelle cette vulnrabilit attaque sur la slection des MPR par mystification de lien. Ceci peut survenir lorsquun nud malveillant signale dans ses messages HELLO une fausse relation de voisinage avec des nuds inexistants ou des nuds loigns qui ne font pas partie de ses voisins (Link spoofing). Comme il est le seul avoir un lien avec ces nuds, la spcification du protocole OLSR, et plus prcisment lAlgorithme 1.1, lui permet dtre choisi comme relais multipoint par ses voisins. Ceci entraine une fausse slection des MPR par tous les voisins de ce nud malicieux. Dans la Figure 2.3, le nud malicieux m annonce dans ses messages HELLO un lien avec un nud inexistant i. Dans ce contexte, le nud a le choisit comme MPR. Par la suite, tous les messages entre les nuds a et c passent par m et ce dernier peut les modifier ou les rejeter. Or, dans labsence de ce lien inexistant entre m et i, le nud a peut choisir soit b soit m comme MPR. Dans le mme contexte, un nud malveillant m peut crer des liens virtuels avec tous les nuds 2 sauts dun nud a. Ainsi, le nud m est lunique MPR de a. Le nud malicieux

39

peut par la suite lignorer dans ses messages TC et le nud a se retrouve alors couper du rseau. Ce type dattaque sappelle Node Isolation Attack (Kannhavong et al., 2006).

Figure 2.3

Attaque sur la slection des MPR.

Un nud malveillant peut aussi dclarer dans ses messages HELLO un ensemble incomplet de ses voisins. Les nuds ignors peuvent tre coups du reste du rseau si le nud malveillant est leur seul lien.Gnration incorrecte du message TC

Un nud malicieux peut envoyer des messages TC et usurper lidentit dun autre nud dans le rseau. Dans Figure 2.4, le nud m gnre des messages TC ayant pour origine le nud v et dclarant les nuds e et g comme voisins. Lorsquun nud dans le rseau reoit les messages TC (par exemple le nud a), il conclut que les nuds e, g et v sont voisins. Ceci entraine des conflits des routes dans le rseau et une mauvaise vision de la topologie par les nuds. Lorsque le nud a reoit un message TC de la part du nud m et v (pour lui cest de la mme origine), il va rejeter le message avec le plus petit numro de squence ANSN (Advertised Neighbor Sequence Number). Le nud malveillant doit alors gnrer des messages TC avec des ANSN plus grands que ceux envoys par le nud v. Ce mcanisme peut tre considr en lui-mme comme un type dattaque part entire. En effet, il suffit pour un nud

40

dcouter les messages TC des autres nuds lgitimes et envoyer par la suite des messages TC avec usurpation didentit des nuds avec un numro de squence plus grand que celui des messages des victimes.

Figure 2.4

Usurpation d'identit du nud v par m (TC).

Finalement, un nud malveillant peut tre choisi comme MPR lgitime par dautres nuds. Par la suite, il peut refuser de gnrer les messages TC ou dclarer dans ses TC un ensemble incomplet de voisins qui lont choisi comme MPR. Ceci peut entrainer la dconnexion du rseau de lensemble des nuds non dclars dans les messages TC du MPR malveillant.b) Relayage incorrect du trafic

Les oprations de routage et de communication dans les rseaux Ad-Hoc se basent essentiellement sur le relayage correct du trafic de routage et de donnes. Un relayage incorrect a des consquences sur le bon fonctionnement du rseau. On peut distinguer diffrents types dattaques dans cette catgorie.Relayage incorrect du trafic de contrle

Un nud malveillant peut tre choisi comme MPR lgitime par dautres nuds mais il refuse de relayer les messages TC des autres MPR. Dans le cas o il nexiste pas de route qui ne

41

passe pas par le nud malicieux, le refus de ce dernier de relayer les messages TC peut avoir comme consquence une perte de connectivit de certains nuds dans le rseau.Attaque par retransmission des messages de contrle

Un nud malicieux peut renvoyer dautres nuds des messages de contrle (TC ou HELLO) dj envoys dans le pass par dautres nuds quil a pu couter travers le rseau. Il faut que les messages renvoys par lattaquant aient des numros de squence plus levs sinon ces messages seront rejets par les nuds qui ont reu une copie originale de ces messages. Ce type dattaque cause un change de fausses informations et un conflit dans le calcul de la topologie qui peut entrainer des problmes de routage.Attaque wormhole

Ce type dattaque redirige le trafic entre deux zones gographiquement loignes pour ainsi avoir une bonne position gographique pour contrler le trafic qui passe par lui.

Figure 2.5

Attaque wormhole cre par le nud m.

Dans la Figure 2.5, le nud malicieux m cre un lien virtuel entre les nuds a et h sans tre visible par les deux nuds. Le but est de leur faire croire quils sont des nuds voisins. En effet, le nud m renvoie les messages HELLO du nud h vers a et inversement. Ainsi, chacun de ces nuds va dclarer par la suite quil a un lien symtrique entre eux. La route

42

entre a et h devient alors une route prfre par les autres nuds car cest le plus court chemin. Ce chemin est totalement contrl par le nud malveillant m ce qui prsente un danger pour lintgrit et la confidentialit des messages. Deux nuds malicieux m1 et m2 peuvent aussi collaborer pour crer une attaque wormhole entre deux zones trs loignes (Voir Figure 2.6).

Figure 2.6 Attaque trou-noir

Collaboration pour crer un wormhole.

Un nud malicieux qui a t choisi par ses voisins comme MPR peut rejeter tous les paquets de donnes reus de ses voisins (Blackhole Attack). Ce type dattaque entraine une perte de connectivit et la dgradation de la communication.2.3.2 Mcanismes de scurit proposs pour OLSR

Ces dernires annes, de nombreuses contributions ont t proposes pour la scurit du protocole OLSR (Adjih et al., 2003; Adjih et al., 2005; Adjih, Mhlethaler et Raffo, 2006; Adjih, Raffo et Mhlethaler, 2005; Dhillon et al., 2004; Raffo et al., 2004). Dans cette section, on prsentera une revue des principales solutions proposes pour scuriser le protocole OLSR.

43

Architecture de scurit pour OLSR

Ce systme a t propos et tudi dans (Adjih et al., 2003; Adjih et al., 2005; Adjih, Mhlethaler et Raffo, 2006). Lobjectif est disoler les nuds malicieux en utilisant un systme de signature et dauthentifier les messages OLSR de bout-en-bout. Ce cryptosystme repose sur lajout dune signature aux messages de contrle dOLSR. En effet, chaque nud gnre la signature lors de la cration de chaque message de contrle (HELLO/TC/HNA/MID). La signature est envoye par la suite avec le message de contrle dans le mme paquet. Or, il est impossible de signer le TTL (Time To Live) et lindice de nombre de sauts (Hop_Count) prsents dans les messages de contrle. La solution pour pallier le problme et ainsi faire face aux attaques par retransmission des messages de contrle (Replay Attacks), est dutiliser un Timestamp dans les messages au lieu du TTL (Adjih, Mhlethaler et Raffo, 2006). Le Timestamp est insr lors de la cration du message en mme temps que la signature. Ainsi, lorsquun nud reoit un message de contrle, il contrle le Timestamp et vrifier la signature du message. Si le Timestamp et la signature sont corrects, le nud traite le message; sinon ce dernier le rejette et alors le nud malicieux, originaire de ce message, se trouve isol du reste du rseau (Voir Figure 2.7). Larchitecture PKI (Public Key Infrastructure) est base sur une autorit centralise qui est soit proactive ou ractive. La version proactive envoie priodiquement les certificats tout le rseau. Par contre, la version ractive rpond sur demande aux requtes dobtention de certificat par les nuds.Mcanisme de signature avanc pour OLSR (ADVISG)

Les mcanismes de signature et de Timestamp ne sont pas suffisants pour faire face aux diffrents types dattaques. En effet, cette solution nest pas efficace dans le cas o un nud lgitime est compromis car ce nud malicieux peut alors gnrer des messages signs correctement avec son identit et ainsi envoyer de faux messages de contrle travers le rseau. Dans ce contexte, un mcanisme additionnel ADVSIG (ADVanced SIGnature) a t

44

propos (Raffo et al., 2004). Le but du mcanisme ADVSIG est de garantir lauthenticit de bout-en-bout de lensemble des informations concernant ltat des liens travers le rseau, .-.-d., assurer lintgrit du rseau et des messages changs dans ce dernier. Cette approche ncessite les mcanismes de PKI et de Timestamp dfinis dans (Adjih et al., 2003; Adjih et al., 2005). Lors de la cration des informations de la topologie et durant lchange des messages OLSR, chaque nud attache la signature ADVSIG et doit certifier lauthenticit des informations quil fournit ses voisins. Il doit aussi gnrer une preuve qui sera utilise par ses voisins pour prouver lauthenticit de ce lien avec le nud originaire du message. Ce mcanisme ne fournit pas une solution pour les attaques de type DoS ou wormhole et il ajoute une charge de trafic importante cause des signatures changes entre les nuds.

Figure 2.7

Isolation du nud malicieux m.

Mcanisme bas sur la position gographique

Une modification base sur la go-localisation a t apporte aux mcanismes prcdents (Adjih et al., 2005). Cette solution SIGLOC (SIGnature and LOCalization) prsente une approche pour faire face aux attaques de type wormhole et aux attaques par mystification des liens. En effet, les trois mcanismes regroups ensemble (PKI, Timestamp et la localisation

45

gographique) permettent de dtecter tout relayage incorrect du trafic dun point du rseau vers un autre loign.Autorit de certification distribue

Un autre mcanisme bas sur une autorit de certification entirement distribu DCA (Distributed Certificate Authority) a t propos par (Dhillon et al., 2004). Le DCA est distribu de telle manire que chaque nud peut demander un certificat de la part de nimporte quelle coalition de k nuds dans le rseau (Shareholders). Lorsquun nud demande une coalition un certificat, il doit attendre la rception de k certificats partiels avant de gnrer un certificat valide et de lutiliser dans le rseau. Ce mcanisme ncessite une intervention externe pour initialiser au dbut et mettre en place une autorit de certificat. Ceci rend cette solution difficile utiliser dans les rseaux Ad-Hoc auto-organis.Modle de confiance implicite pour le routage dans OLSR

Une approche base sur un modle de confiance implicite pour le routage dans le protocole OLSR a t propose dans (Adnane, Bidan et de Sousa Jr, 2008) et (Adnane et al., 2008). Le but est de fournir une extension au protocole OLSR base sur la confiance entre les nuds du rseau afin de renforcer le mcanisme de slection des MPR et rduire les attaques contre ce protocole. Pour ce faire, ce mcanisme procde une validation de la table de routage et des informations de routage en utilisant un modle de confiance entre les nuds. Le mcanisme suit les quatre tapes dinitialisation du protocole OLSR : dcouverte des voisins, slection des MPR, signalisation des MPR et comptage de table de routage. La rception des messages HELLO permet chaque nud x du rseau de commencer construire sa liste de voisins. Avant quil fasse confiance un de ses voisins, il doit sassurer que ce dernier opre selon les spcifications du protocole OLSR. Le nud x diffuse alors un message HELLO son voisin et devient un nud de confiance pour tous ses voisins (Marsh, 1994). Si ce voisin opre selon les spcifications du protocole, il va mettre un message HELLO pour dclarer quil a un lien avec le nud x. Par la suite, le nud x lajoute comme voisin symtrique avec qui une relation de confiance est tablie. Le calcul des MPR se base

46

sur les informations de voisinage fournit par les nuds, or ces informations sont bases sur un modle de confiance. Le choix des MPR se fait alors parmi les nuds avec qui une relation de confiance a t tablie. Cette mme relation de confiance dtermine le choix de route pour acheminer les messages car chaque MPR suggre aux nuds qui lont choisi comme MPR le plus court chemin vers la destination qui passent par les nuds qui il fait confiance.Mcanisme de rputation bas sur la contre-raction

Une approche de rputation base sur la contre-raction pour faire face aux attaques de type mystification de lien a t propose dans (Vilela et Barros, 2007). Lobjectif de ce mcanisme est de sassurer que chaque nud gnre correctement les messages de contrle. Pour ce faire, deux oprations sont utilises : le message de contre-raction et la table dvaluation. Le message de contre-raction est utilis pour indiquer le chemin parcouru par le message de contrle TC. Quand un MPR reoit un message TC, il envoie, au nud originaire du message TC, un message de contre-raction indiquant le chemin travers par le message de contrle. Dautre part, une table dvaluation est maintenue par chaque nud dans le rseau afin dval