Résilience et application aux protocoles de routage dans les réseaux de capteurs

Wireless Sensor Networks (WSNs) are composed of a large number of low-cost, low power, and multifunctional sensor nodes that communicate at short distances through wireless links. In many cases these sensor nodes are deployed over a large geographic area in order to collect physical world data (temperature, humidity, pollution, etc.) and route them towards one or few destinations called the "sinks". This thesis focuses on the security issues of multi-hop routing protocols, especially on the resiliency concept. The rapid deployment capabilities, due to the lack of infrastructure, as well as the self organized and potentially fault-tolerant nature of WSNs make them attractive for multiple applications spanning from environmental monitoring (temperature, pollution, etc.) to building industrial automation (electricity/gas/water metering, event detection, home automation, etc.). Security is particularly challenging in WSNs. Because of their open and unattended deployment, in possibly hostile environments, powerful adversaries can easily launch Denial-of-Service (Dos) attacks, cause physical damage to sensors, or even capture them to extract sensitive information (encryption keys, identities, addresses, etc.). Consequently, the node compromise poses severe security and reliability concerns, since it allows an adversary to be considered as a legitimate node inside the network. After node compromise, an adversary can seek to disrupt the functionality of network layer by launching attacks such as node replication, Sybil, Selective forwarding, Sinkhole, Wormhole, etc. To cope with these "insider" attacks, stemming from node compromise, "beyond cryptography" algorithmic solutions must be envisaged to complement the traditional cryptographic solutions. Firstly, we propose the resiliency concept. Our goal is to propose a definition of the resiliency in our context (security of WSNs routing protocols) and a new metric to compare routing protocols. The originality of this metric is that we combine the graphical representation (qualitative information) with the aggregation method (quantitative information). We introduce a two dimensional graphical representation with multiple axes forming an equiangular polygon surface. This method allows to aggregate meaningfully several parameters and makes it easier to visually discern various tradeoffs, thus greatly simplifying the process of protocol comparison. Secondly, we propose the protocol behaviors enhancing resiliency. Our proposition consists in three elements: (i) introduce random behaviors (ii) limit route length (iii) introduce data replication. Random behaviors increase uncertainty for an adversary, making the protocols unpredictable. Data replication allows route diversification between the sources and the sink, thus improving the delivery success and fairness. Limitation of the route length is necessary to reduce the probability of a data packet to meet a malicious insider along the route. The quantitative metric enables to propose a new resiliency taxonomy of WSNs routing protocols. According to this taxonomy, the gradient based routing is the most resilient when it is combined with the proposed behaviors. Thirdly, several variants of the gradient-based routing (classical and randomized) under more complex and realistic adversary model (several combined attacks) are considered to extend our simulations. Several values of bias are introduced to the randomized variants and two data replication methods (uniform and adaptive) are considered. Without attacks, the most biased variants without replications are the most efficient. However, under moderate attacks, the replication uniform is the most adapted, while under intense attacks, the replication adaptive is the most suitable. Finally, a theoretical study of the resiliency is introduced. We present an analytical study of the biased random walk routing under attacks. The influence of bias is evaluated and two replication methods that previously evaluated by simulations are considered. After presenting the delivery success and the energy consumption of all scenarios, we evaluate them with our resiliency metric. This study permits to confirm the results obtained with simulations and it shows that the bias is essential to enhance the resiliency of random routing. The work presented in this thesis focuses on the resiliency. This concept is relatively new, especially in the network protocol engineering. Through this thesis, we wanted to give our view on this topic by focusing on the "beyond cryptography" algorithmic solutions of WSNs routing protocols.Les réseaux de capteurs sans fil sont constitués d'un grand nombre de nœuds, déployés pour collecter des données du monde physique (température, humidité, pollution etc.) et les transmettre, de manière autonome, vers un ou plusieurs points de collectes appelés "puits". Dans cette thèse, nous nous focalisons sur la sécurité des protocoles de routage multi-sauts, plus particulièrement, sur la notion de résilience aux attaques. Les domaines d'applications des réseaux de capteurs sont variés, allant du suivi médical à la surveillance environnementale en passant par le bâtiment intelligent ou le monitoring urbain (éclairage, pollution, relevé de compteurs d'eau/électricité/gaz etc.). Dans ces applications, les capteurs sont souvent déployés dans des environnements ouverts et accessibles permettant aux éventuels attaquants de les détruire ou de les capturer afin d'en extraire les données sensibles (clés de chiffrement, identité, adresse, etc.). La compromission des nœuds est un problème majeur pour la sécurité de réseaux de capteurs, puisqu'un adversaire peut s'introduire à l'intérieur du périmètre de sécurité. Les méthodes traditionnelles, basées sur la cryptographie, permettent d'obtenir une sécurité de base (authentification, confidentialité, intégrité, non répudiation etc.), mais ne permettent pas toujours de se prémunir contre les attaques dues à la compromission des nœuds (réplication des nœuds, Sybil, Selective forwarding, Blackhole, Sinkhole, Wormhole etc.). Dans le but d'apporter des solutions algorithmiques complémentaires aux solutions cryptographiques, nous étudions la résilience des protocoles de communication en présence d'adversaires internes visant à perturber le routage de l'information à travers le réseau. Dans un premier temps, nous introduisons le concept de résilience. Notre objectif est de proposer une définition explicitant le terme de résilience dans notre contexte et une métrique, permettant de comparer efficacement les protocoles de routage. L'originalité de cette métrique est d'utiliser à la fois une représentation graphique et une méthode de calcul quantitative liée à celle-ci. La représentation graphique à deux dimensions permet une vision synthétique de la résilience des protocoles selon plusieurs paramètres de performance. La méthode de calcul quantitative liée à cette représentation graphique agrège les valeurs des paramètres et permet de classifier les protocoles en termes de résilience. Grâce à cet outil, nous avons évalué la résilience de plusieurs protocoles de routage classiques de différentes catégories. Cette étude nous a permis d'identifier les mécanismes permettant d'améliorer la résilience des protocoles. Dans un second temps, nous proposons les mécanismes résilients de routage pour les réseaux de capteurs. Les mécanismes résilients que nous proposons consistent en trois éléments : (i) introduire un comportement aléatoire (ii) limiter la longueur des routes (iii) ajouter de la réplication de paquets. Les comportements aléatoires augmentent l'incertitude pour les adversaires, rendant les protocoles moins prévisibles, les réplications des données permettent de bénéficier la diversification des routes créées entre les sources et le puits, en améliorant ainsi le succès et l'équité de livraison et la limitation de la longueur des routes est nécessaire pour diminuer la probabilité qu'un paquet tombe sur un nœud attaquant en route. La connexité entre les capteurs et le puits est ainsi augmentée. Grâce à notre métrique de résilience, nous avons proposé une nouvelle taxonomie de résilience. Selon cette taxonomie, le routage par gradient et la marche aléatoire biaisée avec les mécanismes proposés sont les plus résilients. Nous avons donc évalué par la suite le routage par gradient en cas d'attaques combinées pour approfondir notre étude, mais aussi pour savoir si ces mécanismes proposés permettent d'augmenter la résilience même en cas d'attaques plus complexes, visant différents aspects du routage (construction des routes, paquets de contrôle, etc.). Nous avons introduit plusieurs valeurs de biais aux variantes aléatoires du routage par gradient pour étudier l'influence de l'entropie et nous les avons comparées à sa version classique. Nous avons également évalué leur résilience en introduisant deux types de réplications (uniformes et adaptatives). Sans attaques, ce sont les variantes les plus biaisées sans réplications qui sont les plus performantes. En cas d'attaques peu importantes, les réplications uniformes sont plus efficaces, tandis qu'en cas d'attaques plus intenses, ce sont les réplications adaptatives qui se montrent les plus efficaces. Les études menées jusqu'à ici étaient produites par des simulations et nous avions donc besoin d'une justification théorique. Nous avons donc proposé une étude théorique de la marche aléatoire biaisée en cas d'attaques de non-retransmission des paquets. Nous avons évalué l'influence du biais, mais aussi les deux réplications que nous avions évaluées précédemment par des simulations. En premier lieu, nous avons étudié le succès de livraison et la consommation d'énergie pour tous les scénarios. Ensuite, nous les avons évalués selon notre métrique de résilience. Cette étude a permit de confirmer les résultats d'étude par simulations et elle a montré que le biais est indispensable pour la résilience et le seuil d'entropie bénéfique à la résilience est e=0.7 quand la réplication de données est introduite. En dessous de cette valeur, la marche aléatoire est inefficace à cause de la longueur de chemins trop importante. L'ensemble des travaux réalisés dans cette thèse se concentre autour de la résilience. Ce concept reste assez nouveau, en particulier dans le domaine des réseaux et télécommunications. À travers cette thèse, nous avons voulu donner notre vision sur ce thème en nous concentrant sur les problématiques de sécurité des protocoles de routage dans le contexte des réseaux de capteurs