La conception des systèmes distribués est une tâche onéreuse : les objectifs de performance, d’exactitude et de fiabilité sont étroitement liés et ont donné naissance à des compromis complexes décrits par de nombreux résultats théoriques. Ces compromis sont devenus de plus en plus importants à mesure que le calcul et le stockage se sont déplacés vers des architectures distribuées. De plus, l’absence d’approches systématiques de ces problèmes dans les outils de programmation modernes les a aggravés — d’autant que de nos jours la plupart des programmeurs doivent relever les défis liés aux applications distribués. En conséquence, il existe un écart évident entre les abstractions de programmation, les exigences d’application et la sémantique de stockage, ce qui entrave le travail des concepteurs et des développeurs. Cette thèse présente un ensemble de contributions tourné vers la conception de systèmes de stockage distribués fiables, en examinant ces questions à travers le prisme de la cohérence. Nous commençons par fournir un cadre uniforme et déclarative pour définir formellement les modèles de cohérence. Nous utilisons ce cadre pour décrire et comparer plus de cinquante modèles de cohérence non transactionnelles proposés dans la littérature. La nature déclarative et composite de ce cadre nous permet de construire un classement partiel des modèles de cohérence en fonction de leur force sémantique. Nous montrons les avantages pratiques de la composabilité en concevant et en implémentant Hybris, un système de stockage qui utilise différents modèles pour améliorer la cohérence faible généralement offerte par les services de stockage dans les nuages. Nous démontrons l’efficacité d’Hybris et montrons qu’il peut tolérer les erreurs arbitraires des services du nuage au prix des pannes. Enfin, nous proposons une nouvelle technique pour vérifier les garanties de cohérence offertes par les systèmes de stockage du monde réel. Cette technique s’appuie sur notre approche déclarative de la cohérence : nous considérons les modèles de cohérence comme invariants sur les représentations graphiques des exécutions des systèmes de stockage. Une mise en œuvre préliminaire prouve cette approche pratique et utile pour améliorer l’état de l’art sur la vérification de la cohérence. / Engineering distributed systems is an onerous task: the design goals of performance, correctness and reliability are intertwined in complex tradeoffs, which have been outlined by multiple theoretical results. These tradeoffs have become increasingly important as computing and storage have shifted towards distributed architectures. Additionally, the general lack of systematic approaches to tackle distribution in modern programming tools, has worsened these issues — especially as nowadays most programmers have to take on the challenges of distribution. As a result, there exists an evident divide between programming abstractions, application requirements and storage semantics, which hinders the work of designers and developers.This thesis presents a set of contributions towards the overarching goal of designing reliable distributed storage systems, by examining these issues through the prism of consistency. We begin by providing a uniform, declarative framework to formally define consistency semantics. We use this framework to describe and compare over fifty non-transactional consistency semantics proposed in previous literature. The declarative and composable nature of this framework allows us to build a partial order of consistency models according to their semantic strength. We show the practical benefits of composability by designing and implementing Hybris, a storage system that leverages different models and semantics to improve over the weak consistency generally offered by public cloud storage platforms. We demonstrate Hybris’ efficiency and show that it can tolerate arbitrary faults of cloud stores at the cost of tolerating outages. Finally, we propose a novel technique to verify the consistency guarantees offered by real-world storage systems. This technique leverages our declarative approach to consistency: we consider consistency semantics as invariants over graph representations of storage systems executions. A preliminary implementation proves this approach practical and useful in improving over the state-of-the-art on consistency verification.

Les systèmes collaboratifs sont aujourd’hui devenus très populaires et sont de plus en plus utilisés dans de nombreux domaines divers. De fait, les interactions de confiance des differents systèmes sont devenus une priorité. La confiance, en tant que concept informatique, a été étudiée très récemment. Cependant, dans la littérature, très peu d’attention a été portée pour évaluer l’exactitude des interactions entre entités communicantes; même si la plupart des approches se sont basées sur les mesures cumulées de ces valeurs. Pour déterminer, de façon générale, l’exactitude de ces interactions, une approche nommée Monitorage des Réseaux En-Ligne et Distribué (MRED) a été proposée. De plus, des outils prototypes ont été développés pour tester automatiquement les propriétés de confiance entre entités dans des systèmes communicants. MRED est une forme de test passif; elle analyse les réponses des systèmes et teste l’exactitude des interactions en utilisant des traces de réseaux. Comme elle dépend des propriétés à tester, une nouvelle approche a été proposée pour faire l’extraction automatique de propriétés pertinentes que l’ont pourrait, in fine, tester dans un système sous test. Notre approche repose sur le fonctionnement des systèmes de monitorage online. Nous proposons de nouvelles méthodes afin d’améliorer les techniques fournies dans l’état de l’art pour: a) évaluer efficacement les propriétés avec une complexité en temps O($n$), ce en utilisant un Automate Fini Déterministe Prolongée (AFDP); et b) élargir l’expressivité du langage proposé pour exprimer correctement les contraintes systèmes, comme les délais d’attente pour éviter le manque de ressources. Finalement, nous proposons un nouveau cadre flexible utilisable dans de très nombreux domaines, qui permet la définition de caractéristiques de confiance afin d’évaluer les entités dans des contextes différents. De surcroît, avec les évaluations des caractéristiques de confiance, nous proposons un modèle de confiance basé sur l’apprentissage automatique, en résolvant spécifiquement un problème de classification multi-classes et utilisant des Machine à vecteurs de support (SVM). A partir de ces modèles, des expérimentations ont été effectuées en simulant des caractéristiques de confiance pour estimer le niveau de confiance; une précision de plus de 96% a été obtenue / Collaborative systems are growing in use and in popularity. The need to boost the methods concerning the interoperability is growing as well; therefore, trustworthy interactions of the different systems are a priority. Trust as a computer science concept has been studied in the recent years. Nevertheless, in the literature, very little focus is placed on how to assess the correctness of the interactions between the entities; even if most approaches rely on the estimation of trust based on the accumulated measures of these values. To broadly determine the correctness of interactions without targeting a specific domain or application, an approach using Distributed On-line Network Monitoring (DONM) was proposed. Furthermore, a prototype tool-set was developed to automatically test the trust properties. DONM is a form passive testing; it analyzes systems' responses and test the correctness of the interactions via network traces. Since it relies on the stated properties to test, a novel approach was proposed to automatically extract relevant properties to test. Our approach deeply relies on the operation of On-line Monitoring Systems. That is the reason why we propose new methods to enhance the state of the art techniques to: a) efficiently evaluate properties in O(n) time complexity using an Extended Finite State Automata (EFSA) auxiliary data structure; and b) to expand the language expressiveness to properly express the constraints of such systems, such as, timeouts in order to avoid resource starvation. Finally, using the evaluation of the entities' interactions provided by our approach, trust management engines will help trustors to decide with whom and how to interact with other users or applications. We propose a new framework that is flexible for any domain, allowing trustors to define the trust features used to evaluate trustees in different contexts. Furthermore, with the evaluations of the trust features, we propose a trust model which achieves close-to-human inference of the trust assessment, by using a machine learning based trust model, namely solving a multi-class classification problem using Support Vector Machines (SVM). Using the SVM-based trust model, experiments were performed with simulated trust features to estimate trust level; an accuracy of more than 96% was achieved

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Thèse en cotutelle : Université Laval, Québec, Canada et Université Paris-Sud, Orsay, France. / Ce mémoire vise à élucider les principaux enjeux et problématiques qui caractérisent le marché de l’art actuel pour pouvoir ensuite présenter et évaluer des pistes de solutions émanant de la technologie de chaîne de blocs. Ce marché est effectivement aux prises avec certaines difficultés d’authenticité et d’authentification des œuvres d’art : on parle même d’une crise de l’expertise en authentification. Il est aussi question d'adversités dans l’établissement et la preuve de provenance des œuvres qui y circulent, car le marché repose sur un équilibre fragile et semble ne pas avoir su prendre le virage numérique à temps. Enfin, on relate aussi un manque de transparence dû au désir de confidentialité et de secret qui règne autant chez les marchands d’arts que chez les collectionneurs. Le développement croissant des technologies décentralisées a permis des avancées dans plusieurs secteurs au cours des dernières années, et il appert qu’elles pourraient potentiellement agir à titre de pilier au sein du marché de l’art par leurs caractéristiques d’immuabilité, de distribution et de transparence. Nous pourrons de ce fait constater l’utilité des registres distribués, des contrats intelligents et de la tokénisation pour pallier les problématiques observées. Il demeure toutefois que l’adoption générale de la chaîne de blocs dans un marché si séculaire n’est pas sans limites. Il conviendra alors d’étudier les obstacles que cette nouvelle technologie devra surmonter pour pouvoir garantir l’authenticité et la provenance des œuvres, de même qu’une transparence accrue sur le marché de l’art. Enfin, dans le but d’assurer une adoption équilibrée et profitable à long terme, il sera primordial de prendre compte des intérêts des divers intervenants impliqués. / This paper aims to elucidate the main issues that characterize the current art market in order to present, assess and evaluate potential solutions stemming from blockchain technology. This market is indeed grappling with certain difficulties of authenticity and authentication of works of art: there is even signs of a crisis of expertise. At the moment, it is also burdensome to establish the provenance of art circulating on the market for different reasons. Firstly, because the market is very fragile and second, because it seems to have failed to take advantage of technologies in time. Finally, we can witness a lack of transparency, mainly due to the desire for confidentiality and secrecy which reigns as much among art dealers as among collectors. The increasing development of decentralized technologies has enabled progress in several industries recently, and it appears that it could offer a certain support within the art market due to their characteristics of immutability, transparency and security. We will therefore be able to see the usefulness of distributed ledgers, smart contracts and tokenization to alleviate the problems we have observed. The fact remains, however, that the general adoption of blockchain technology in such a secular industry is not without limits It will therefore be necessary to study the challenges this new technology will have to overcome in order to guarantee the authenticity and provenance of art, as well as price transparency. Finally, in order to ensure a balanced and profitable adoption in the long term, it will be essential to take into account the interests of the various stakeholders involved.

La présente étude porte sur la capacité d'améliorer la détection des Activités de la Vie Quotidienne, AVQ (ou ADL :"Activity of Daily Life") par l'utilisation de capteur [i.e. capteurs] de mouvements portés par l'occupant d'un habitat intelligent. Les données provenant de ces capteurs devraient fusionner avec les informations issues de l'appartement pour donner une information plus pertinente par le principe de synergie [21]. La solution choisie pour le dispositif porté par la personne est l'innovation principale du projet : un réseau de capteurs disposés à plusieurs endroits sur le corps, communicant sans fil entre eux et avec le contrôle de l'appartement. Les données extraites sont le mouvement relatif du corps, et plus spécifiquement des mains et du tronc, par rapport à la verticale. De par les propriétés de ces éléments - nécessairement petits, discrets - des MEMS seront utilisés pour satisfaire ces critères. Le projet repose sur la conception des dispositifs embarqués sur l'occupant dans l'optique d'en étendre les fonctionnalités à d'autres analyses tels [i.e. telles] que le son, la position dans l'environnement, le statut médical, etc. Pour prouver la faisabilité, des capteurs externes seront ajoutés pour compléter les informations de base et donc étendre la qualité des inférences sur les activités en cours. Le mouvement est une donnée facilement détectable de par sa relative simplicité de mise en oeuvre et il fournit une bonne base de travail pour étudier de façon systématique les différents points clés de l'étude : la communication, la synergie des informations, l'analyse des activités, etc.

Les automates d'ordres, plus connus sous le nom de Message sequence Charts (MSC), ont connu une énorme popularité depuis les années 1990. Ce succès est à la fois académique et industriel. Les raisons de ce succès sont multiples : le modèle est simple et s'apprend très vite. De plus il possède une puissance d'expression supérieure à celle des automates finis, et pose des problèmes difficiles. L'apparente simplicité des MSCs est en fait trompeuse, et de nombreuses manipulations algorithmiques se révèlent rapidement être des problèmes indécidables. Dans ce document, nous revenons sur 10 années de recherches sur les Message Sequence Charts, et plus généralement sur les langages de scénarios, et tirons quelques conclusions à partir des travaux effectués. Nous revenons sur les propriétés formelles des Message Sequence charts, leur décidabilité, et les sous-classes du langage permettant la décision de tel ou tel problème. L'approche classique pour traiter un problème sur les MSCs est de trouver la plus grande classe possible sur laquelle ce problème est décidable. Un autre challenge est d'augmenter la puissance d'expression des MSCs sans perdre en décidabilité. Nous proposons plusieurs extensions de ce type, permettant la crétion dynamique de processus, ou la définition de protocoles de type "fenêtre glissante". Comme tout modèle formel, les MSCs peuvent difficilement dépasser une taille critique au delà de laquelle un utilisateur ne peut plus vraiment comprendre le diagramme qu'il a sous les yeux. Pour pallier à cette limite, une solution est de travailler sur de plus petits modules comportementaux, puis de les assembler pour obtenir des ensembles de comportements plus grands. Nous étudions plusieurs mécanismes permettant de composer des MSCs, et sur la robustesses des sous-classes de scénarios connues à la composition. La conclusion ce cette partie est assez négative: les scénarios se composent difficilement, et lorsqu'une composition est faisable, peu de propriétés des modèles composés sont préservées. Nous apportons ensuite une contributions à la synthèse automatique de programmes distribués à partir de spécification données sous forme d'automates d'ordres. Cette question répond à un besoin pratique, et permet de situer un role possible des scénarios dans des processus de conception de logiciels distribués. Nous montrons que la synthèse automatique est possible sur un sous ensemble raisonnable des automates d'ordres. Dans une seconde partie de ce document, nous étudions des applications possibles pour les MSCs. Nous regardons entre autres des algorithmes de model-checking, permettant de découvrir des erreurs au moment de la spécification d'un système distribué par des MSCs. La seconde application considérée est le diagnostic, qui permet d'expliciter à l'aide d'un modèle les comportement d'un système réel instrumenté. Enfin, nous regardons l'utilisation des MSCs pour la recherche de failles de sécurité dans un système. Ces deux applications montrent des domaines réalistes d'utilisation des scénarios. Pour finir, nous tirons quelques conclusions sur les scénarios au regard du contenu du document et du travail de ces 10 dernières années. Nous proposons ensuite quelques perspectives de recherche.

La vérification de propriétés de sûreté des logiciels distribués basés sur des canaux fifo non bornés et fiables mène directement au model checking de systèmes infinis. Nous introduisons la famille des (q)ueueing (c)oncurrent (p)rocesses (QCP) composant des systèmes de transitions locaux, par exemple des automates finis/à pile, qui communiquent entre eux par des files fifo. Le problème d'atteignabilité des états de contrôle est indécidable pour des automates communicants et des automates à plusieurs piles, et par conséquent pour QCP.Nous présentons deux solutions pour contourner ce résultat négatif :Primo, une sur-approximation basée sur l'approche abstraire-tester-raffiner qui s'appuie sur notre nouveau concept de raffinement par chemin. Cette approche mène à permettre d'écrire un semi-algorithme du type CEGAR qui est implémenté avec des QDD et réalisé dans le framework McScM dont le banc d'essai conclut notre présentation.Secundo, nous proposons des restrictions pour les QCP à des piles locales pour démêler l'interaction causale entre les données locales (la pile), et la synchronisation globale. Nous montrons qu'en supposant qu'il existe une borne existentielle sur les exécutions et qu'en ajoutant une condition sur l'architecture, qui entrave la synchronisation de deux piles, on arrive à une réponse positive pour le problème de décidabilité de l'atteignabilité qui est EXPTime-complet (et qui généralise des résultats déjà connus). La construction de base repose sur une simulation du système par un automate à une pile équivalent du point de vue de l'atteignabilité --- sous-jacente, nos deux restrictions restreignent les exécutions à une forme hors-contexte. Nous montrons aussi que ces contraintes apparaissent souvent dans des situations ``concrètes''et qu'elles sont moins restrictives que celles actuellement connues. Une autre possibilité pour arriver à une solution pratiquement utilisable consiste à supposer une borne du problème de décidabilité : nous montrons que l'atteignabilité par un nombre borné de phases est décidable par un algorithme constructif qui est 2EXPTime-complet.Finalement, nous montrons qu'élargir les résultats positifs ci-dessus à la vérification de la logique linéaire temporelle demande soit de sacrifier l'expressivité de la logique soit d'ajouter des restrictions assez fortes aux QCP --- deux restrictions qui rendent cette approche inutilisable en pratique. En réutilisant notre argument de type ``hors-contexte'', nous représentons l'ordre partiel sous-jacent aux exécutions par des grammaires hypergraphes. Cela nous permet de bénéficier de résultats connus concertant le model checking des formules de la logique MSO sur les graphes (avec largeur arborescente bornée), et d'arriver aux premiers résultats concernant la vérification des propriétés sur l'ordre partiel des automates (à pile) communicants. / The safety verification of distributed programs, that are based on reliable, unbounded fifo communication, leads in a straight line to model checking of infinite state systems. We introduce the family of (q)ueueing (c)oncurrent (p)rocesses (QCP): local transition systems, e.g., (pushdown-)automata, that are globally communicating over fifo channels. QCP inherits thus the known negative answers to the control-state reachability question from its members, above all from communicating automata and multi-stack pushdown systems. A feasible resolution of this question is, however, the corner stone for safety verification.We present two solutions to this intricacy: first, an over-approximation in the form of an abstract-check-refine algorithm on top of our novel notion of path invariant based refinement. This leads to a \cegar semi-algorithm that is implemented with the help of QDD and realized in a small software framework (McScM); the latter is benchmarked on a series ofsmall example protocols. Second, we propose restrictions for QCP with local pushdowns that untangle the causal interaction of local data, i.e., thestack, and global synchronization. We prove that an existential boundedness condition on runs together with an architectural restriction, that impedes the synchronization of two pushdowns, is sufficient and leads to an EXPTime-complete decision procedure (thus subsuming and generalizing known results). The underlying construction relies on a control-state reachability equivalent simulation on a single pushdown automaton, i.e., the context-freeness of the runs under the previous restrictions. We can demonstrate that our constraints arise ``naturally'' in certain classes of practical situations and are less restrictive than currently known ones. Another possibility to gain a practicable solution to safety verification involves limiting the decision question itself: we show that bounded phase reachability is decidable by a constructive algorithms in 2ExpTime, which is complete.Finally, trying to directly extend the previous positive results to model checking of linear temporal logic is not possible withouteither sacrificing expressivity or adding strong restrictions (i.e., that are not usable in practice). However, we can lift our context-freeness argument via hyperedge replacement grammars to graph-like representation of the partial order underlying each run of a QCP. Thus, we can directly apply the well-known results on MSO model checking on graphs (of bounded treewidth) to our setting and derive first results on verifying partial order properties on communicating (pushdown-) automata.

Le point de départ pour les systèmes décentralisés a été l’échange des fichiers, en utilisant cet approche i) pour distribuer la bande passante entre tous les nœuds concernés et ii) pour augmenter la robustesse en éliminant autant que possible les points individuels de défaillance et de contrôle et iii) en partageant également les responsabilités entre les nœuds. Si les approches le plus décentralisés sont très efficaces en termes de résilience aux pannes, pour la même raison, les performances sont limités et difficiles à analyser quand on observe plusieurs réseaux interconnectés entre eux, configurations qui peuvent être analysés à travers des outils de simulation, souvent peu efficaces dans l’analyse de l’espace de possibilités. Dans cette thèse on a développé un modèle mathématique pour la modélisation de l’interconnexion des réseaux en permettant l’étude et l’exploration d’équilibres qui grâce à l’abstraction du modèle peuvent s’appliquer à l’interconnexion des réseaux de communications, réseaux de distribution de marchandise ou réseaux de distribution d’eau. La thèse se focalise aussi sur les réseaux décentralisés MANET, ou` la communication entre nœuds mobiles est purement ≪ ad-hoc ≫ (ex: deux voitures communiquant entre eux quand ils sont proches) en utilisant i) des ≪ rateless coding ≫ pour augmenter la robustesse et minimiser la perte ou la corruption de données causées par la non fiabilité du moyen de transmission et ii) des algorithmes de ≪ pollution détection ≫, par exemple de détection de nœuds malveillants ou de paquets corrompus, cette détection et prévention étant très difficile dans des environnements fortement distribués. / The original “selling point” for decentralized networks has been file exchange, using the decentralized approach to diffuse the bandwidth cost between all the participating nodes, augmenting the robustness by avoiding single point of failures and control by sharing the responsibility between all nodes. While the most decentralized approaches are very efficient in terms of resilience they are, by the same reason, more performance limited and harder to analyze. This analysis is usually the sole realm of simulation tools, a quite in- efficient way to analyze the possibility space. We thus developed and present here a mathematical model for network interconnection, enabling the study and exploration of equilibriums and, by virtue of the abstraction of the model, perfectly applicable to any interconnection of networks, be them communication networks, social networks or, for example, water distribution networks. We also focused on decentralized networks, called MANETs, where communication between mobile nodes is purely ad-hoc based (eg.: two cars passing each other and communicating while in range), exploit- ing rateless coding to increase their robustness by minimizing data loss due to transmission unreliability, and detecting malicious nodes sending corrupted packets, a hard to detect and prevent problem in a strongly distributed environments, using SIEVE, a custom developed algorithm.

Les systèmes d'information actuels, qu'il s'agisse de réseaux d'entreprises, deservices en ligne ou encore d'organisations gouvernementales, reposent trèssouvent sur des systèmes distribués, impliquant un ensemble de machinesfournissant des services internes ou externes. La sécurité de tels systèmesd'information est construite à plusieurs niveaux (défense en profondeur). Lors de l'établissementde tels systèmes, des politiques de contrôle d'accès, d'authentification, defiltrage (firewalls, etc.) sont mises en place afin de garantir lasécurité des informations. Cependant, ces systèmes sont très souventcomplexes, et évoluent en permanence. Il devient alors difficile de maintenirune politique de sécurité sans faille sur l'ensemble du système (quand bienmême cela serait possible), et de résister aux attaques auxquelles ces servicessont quotidiennement exposés. C'est ainsi que les systèmes de détectiond'intrusions sont devenus nécessaires, et font partie du jeu d'outils desécurité indispensables à tous les administrateurs de systèmes exposés enpermanence à des attaques potentielles.Les systèmes de détection d'intrusions se classifient en deux grandes familles,qui diffèrent par leur méthode d'analyse: l'approche par scénarios et l'approchecomportementale. L'approche par scénarios est la plus courante, et elle estutilisée par des systèmes de détection d'intrusions bien connus tels queSnort, Prélude et d'autres. Cette approche consiste à reconnaître des signaturesd'attaques connues dans le trafic réseau (pour les IDS réseau) et des séquencesd'appels systèmes (pour les IDS hôtes). Il s'agit donc de détecter descomportements anormaux du système liés à la présence d'attaques. Bien que l'onpuisse ainsi détecter un grand nombre d'attaques, cette approche ne permet pasde détecter de nouvelles attaques, pour lesquelles aucune signature n'estconnue. Par ailleurs, les malwares modernes emploient souvent des techniquesdites de morphisme binaire, afin d'échapper à la détection parsignatures.L'approche comportementale, à l'inverse de l'approche par signature, se basesur la modélisation du fonctionnement normal du système. Cette approche permetainsi de détecter de nouvelles attaques tout comme des attaques plus anciennes,n'ayant recours à aucune base de données de connaissance d'attaques existantes.Il existe plusieurs types d'approches comportementales, certains modèles sontstatistiques, d'autres modèles s'appuient sur une politique de sécurité.Dans cette thèse, on s'intéresse à la détection d'intrusions dans des systèmesdistribués, en adoptant une approche comportementale basée sur une politique desécurité. Elle est exprimée sous la forme d'une politique de flux d'information. Les fluxd'informations sont suivis via une technique de propagation de marques (appeléeen anglais « taint marking ») appliquées sur les objets du systèmed'exploitation, directement au niveau du noyau. De telles approchesexistent également au niveau langage (par exemple par instrumentation de lamachine virtuelle Java, ou bien en modifiant le code des applications), ou encoreau niveau de l'architecture (en émulant le microprocesseur afin de tracer lesflux d'information entre les registres, pages mémoire etc.), etpermettent ainsi une analyse fine des flux d'informations. Cependant, nous avons choisi de nous placer au niveau du système d'exploitation, afin de satisfaire les objectifs suivants:• Détecter les intrusions à tous les niveaux du système, pas spécifiquement au sein d'une ou plusieurs applications.• Déployer notre système en présence d'applications natives, dont le code source n'est pas nécessairement disponible (ce qui rend leur instrumentation très difficile voire impossible).• Utiliser du matériel standard présent sur le marché. Il est très difficile de modifier physiquement les microprocesseurs, et leur émulation a un impact très important sur les performances du système. / Modern organisations rely intensively on information and communicationtechnology infrastructures. Such infrastructures offer a range of servicesfrom simple mail transport agents or blogs to complex e-commerce platforms,banking systems or service hosting, and all of these depend on distributedsystems. The security of these systems, with their increasing complexity, isa challenge. Cloud services are replacing traditional infrastructures byproviding lower cost alternatives for storage and computational power, butat the risk of relying on third party companies. This risk becomesparticularly critical when such services are used to host privileged companyinformation and applications, or customers' private information. Even in thecase where companies host their own information and applications, the adventof BYOD (Bring Your Own Device) leads to new security relatedissues.In response, our research investigated the characterization and detection ofmalicious activities at the operating system level and in distributedsystems composed of multiple hosts and services. We have shown thatintrusions in an operating system spawn abnormal information flows, and wedeveloped a model of dynamic information flow tracking, based on taintmarking techniques, in order to detect such abnormal behavior. We trackinformation flows between objects of the operating system (such as files,sockets, shared memory, processes, etc.) and network packetsflowing between hosts. This approach follows the anomaly detection paradigm.We specify the legal behavior of the system with respect to an informationflow policy, by stating how users and programs from groups of hosts areallowed to access or alter each other's information. Illegal informationflows are considered as intrusion symptoms. We have implemented this modelin the Linux kernel (the source code is availableat http://www.blare-ids.org), as a Linux Security Module (LSM), andwe used it as the basis for practical demonstrations. The experimentalresults validated the feasibility of our new intrusion detection principles.

Nos travaux se positionnent dans le cadre de l'algorithmique distribuée et plus particulièrement des réseaux ad hoc. Les réseaux ad hoc sont auto-organisés en permettant des échanges directs entre nœuds mobiles et ne reposent sur aucune infrastructure. Chaque nœud peut se déplacer librement et indépendamment des autres impliquant une modification perpétuelle de la topologie. Dans ce contexte, la probabilité que des défaillances surviennent dans le réseau est importante. Ces défaillances gênent le bon fonctionnement du réseau et peuvent même entrainer une paralysie de celui-ci. C'est pourquoi la conception de solutions pour de tels réseaux nécessitent des mécanismes de gestion de fautes. Parmi ceux-ci, l'approche d'auto-stabilisation permet à un système de gérer les fautes transitoires. Nous étendons cette approche pour répondre aux principaux problèmes liés à la mobilité des nœuds. Notre objectif est de répondre à un double besoin d'auto-organisation du réseau et d'optimisation du nombre de messages échangés. Notre approche consiste à découper le réseau en clusters afin de lui donner une structure hiérarchique. Cette dernière rend l'utilisation du réseau plus efficace et plus performante. L'algorithme que nous avons développé à cet effet est auto-stabilisant et n'est basé que sur des connaissances locales. Nous exploitons cette solution pour proposer deux utilisations efficaces : la diffusion d'informations dans le réseau et le routage. La diffusion d'informations exploite un arbre couvrant inter-clusters, construit sans surcoût, en parallèle de la clusterisation. Le routage quant à lui exploite cet arbre pour permettre à la fois d'optimiser le délai de bout en bout et le nombre de messages échangés. / Our work relies in the domain of distributed system, more preciselly ad hoc networks. Ad hoc networks are self-organized allowing direct exchanges between mobile nodes and do not rely on any infrastruture. Each node can move freely and independently of each others involving continuous topology variability. In this context, the probability that a failure occurs in the network is high. These failures hinder the proper functioning of the network and even causes its paralysis. Therefore, designing solutions for such networks requires fault management mechanisms. Among these, a self-stabilizating approach allows the system to withstand transient faults. We extend this approach to answer the problems induced by nodes mobility. We have two main objectives: a self-organizing network and optimizing number of exchanged messages. Our approach consists in dividing the network into clusters in order to give it a hierarchical structure. This solution allows a more efficient and effective network use. The algorithm that we developed for this purpose is a self-stabilizing algorithm based only on local informations. Based on this solution, we propose two efficient use cases: Information broadcast and a routing protocol. Information broadcast uses an inter-cluster spanning tree, generated without any overhead. In the same time as the clustering process. The routing protocol uses this tree for both round trip and number of exchanged messages optimization.