Retour au site du LAAS-CNRS

Résumé

Dans ce mémoire nous proposons des systèmes de communication anonyme à faible latence. Pour cela nous étudions les performances des systèmes basés sur les primitives classiques : envoi superposé ou bourrage chiffré pour lémission, et diffusion avec adressage implicite pour la réception, quand les groupes dutilisateurs potentiels sont contraints à être de petite taille, peu changeants, ou localisés. Nous proposons lutilisation des protocoles de récupération dinformations privée (ou protocoles PIR pour Private Information Retrieval) comme alternative à la diffusion avec adressage implicite, et nous étudions les systèmes en résultant. Ces systèmes permettent de réduire significativement le coût des communications, au prix dun coût calculatoire important. Au moyen dexemples, nous montrons que ces nouvelles solutions offrent un meilleur choix dans certaines situations, notamment pour les utilisateurs connectés au service par Internet. Dans un deuxième temps, nous mettons en avant les relations entre les différentes techniques et montrons que les systèmes basés sur les primitives classiques ne sont en fait que des instances dune famille qui, par lutilisation de la récupération dinformations privée, devient nombreuse et polyvalente. Ainsi, on dispose de beaucoup plus de degrés de liberté pour limplémentation de solutions fournissant des communications anonymes dans le cadre des groupes dutilisateurs sous contraintes.

Abstract

In this thesis, we present different systems providing low-latency anonymous communications. We first study the performance of systems based on well known primitives such as superposed sending and encrypted padding for transmission, and broadcast with implicit addressing for reception, when the group of potential users is restricted to be small, closed, or localized. We propose the usage of Private Information Retrieval (PIR) protocols as an alternative to broadcast with implicit addressing, and we study the resulting systems. These systems allow us to trade communication cost, for computational cost. Through some examples, we show that the new solutions offer a better choice in some situations, specially when the users are connected to the service through the Internet. Then, we put forward how the different approaches are related, and show that the systems based on classic primitives are in fact just some instances of a family, which becomes much larger and versatile through the introduction of PIR protocols.

Mots-Clés / Keywords

Protection de la vie privée; Communications anonymes; Récupération dinformations privée; Privacy; Anonymous communication; Private information retrieval;

Abstract

With the wide development of microsystems, it is likely that they will be massively used in critical control systems. This raises many new challenges, among which the definition of a dependable communication network with high integrity level. The study of standard communication networks and their basic commonly used transmission errors detection techniques based on CRC codes shows that they cannott ensure the required integrity level. To reach this integrity level, we propose an original solution - an evolutive error control function - based on the slowly evolution characteristic of the control systems considered, for which the integrity is considered for a set of consecutive messages and not for a single message. The validation of the proposed solution is based on MATLAB simulation models we have developed. The study case is about the integration of thousands of micro-surfaces such as micro-spoilers in future flight control systems.

Résumé

Vu le développement important des micro-systèmes, leur utilisation sous forme de nappes dans les systèmes de commande-contrôle critiques est une vraie opportunité. Cela soulève néanmoins des défis, parmi lesquels, la définition dun système de communication à haut niveau dintégrité. Létude que nous avons effectuée sur des réseaux standard montre que les protections classiques à base de codes CRC ne permettent pas dobtenir le niveau dintégrité visé. Pour latteindre, nous avons proposé une solution originale - fonction de contrôle évolutive - qui tire profit du fait que, pour les systèmes de commande-contrôle envisagés (systèmes à dynamique lente), lintégrité est à considérer sur un lot de messages et non sur un seul message. La solution proposée a ensuite été validée via des simulations Matlab-Simulink. Le cas d'étude utilisé est celui de systèmes de commande de vol du futur, en vue de pouvoir commander des nappes de milliers de micro-surfaces tels que des micro-spoilers

Mots-Clés / Keywords

Systèmes de commande-contrôle; Systèmes critiques temps réel; Nappes de microsystèmes; Réseaux de communication temps-réel; Sûreté de fonctionnement; Intégrité des communications; Evaluation; Systèmes de commandes de vol; Control systems; Real-time critical systems; Micro-systems arrays; Communication networks; Dependability; Data communication integrity; Flight control system;

Résumé

Cette thèse porte sur le développement d'une approche de modélisation pragmatique permettant aux concepteurs d'applications et systèmes mis en Suvre sur le web d'évaluer la disponibilité du service fourni aux utilisateurs. Multiples sources d'indisponibilité du service sont prises en compte, en particulier i) les défaillances matérielles ou logicielles affectant les serveurs et ii) des dégradations de performance (surcharge des serveurs, temps de réponse trop long, etc.). Une approche hiérarchique multi-niveau basée sur une modélisation de type performabilité est proposée, combinant des chaînes de Markov et des modèles de files d'attente. Les principaux concepts et la faisabilité de cette approche sont illustrés à travers l'exemple d'une agence de voyage. Plusieurs modèles analytiques et études de sensibilité sont présentés en considérant différentes hypothèses concernant l'architecture, les stratégies de recouvrement, les fautes, les profils d'utilisateurs, et les caractéristiques du trafic.

Abstract

This thesis presents a pragmatic modeling approach allowing designers of applications and systems implemented on the web to evaluate the service availability provided to the users. Multiple sources of service unavailability are taken into account, in particular i) hardware and software failures affecting the servers, and ii) performance degradation (overload of servers, very long response time, etc.). An hierarchical multi-level approach is proposed based on performability modeling, combining Markov chains and queueing models. The main concepts and the feasibility of this approach are illustrated using a web-based travel agency. Various analytical models and sensitivity studies are presented considering different assumptions with respect to the architectures, recovery strategies, faults, users profile and traffic characteristics.

Mots-Clés / Keywords

Sûreté de fonctionnement; Web; Performabilité; Disponibilité de service; Modélisation hiérarchique; Dependability; Performability; Service availability; Hierarchical modeling; Evaluation;

Résumé

Conscient que la réflexivité permet d'améliorer la conception et la maintenance des applications, en séparant leurs aspects fonctionnels et non-fonctionnels, nous explorons dans cette thèse le potentiel réflexif de lintergiciel CORBA. Afin deffectuer une analyse en profondeur, nous avons développé une plate-forme à composants fournissant de manière transparente des mécanismes classiques de réplication. Cette plate-forme nous a permis de montrer les limites de la spécification actuelle des intercepteurs CORBA, PIs (Portable Interceptors). Nous avons identifié précisément certaines difficultés de mise en oeuvre, notamment à cause de la dépendance des intercepteurs vis-à-vis du serveur auquel ils sont attachés et la faible contrôlabilité des interactions réparties. À la lumière de ce travail, nous proposons une amélioration du potentiel réflexif de la norme CORBA actuelle afin de la rendre plus adaptée à la mise en oeuvre des mécanismes de tolérance aux fautes.

Abstract

Reflection makes it possible to improve the design and maintenance of the applications, by separating their functional and non-functional aspects. Based on our analysis of the reflective fault tolerant approaches, we defined a new classification that shows the pertinence of this approach with respect to more conventional ones to provide fault tolerance. The core contribution of this thesis is to explore the reflexive capabilities of the CORBA middleware standard i.e. Portable Interceptors, to build fault tolerant distributed applications. In order to carry out an in-depth analysis of such capabilities, we designed a generic component based platform, called DAISY "Dependable Adaptative Interceptors and Serialization-based sYstem", providing replication mechanisms in a transparent way. DAISY enabled us to show the limits of the current CORBA Portable Interceptors specification. We identified precisely some implementation problems due to some crucial drawbacks of their current definition, in particular, the dependence of the interceptors with respect to the application to which they are attached and the weak controllability of the interactions between them. In the light of this work, we propose an improvement of the current CORBA standard specification in order to enhance its reflective capabilities and adapt the CORBA Portable Interceptors to suit the implementation of fault tolerance mechanisms.

Mots-Clés / Keywords

Tolérance aux fautes; Architecture CORBA; Réflexivité; Intercepteurs; Fault tolerance; CORBA architecture; Reflection; Portable Interceptors;

Résumé

Les développeurs des systèmes informatiques, y compris critiques, font souvent appel à des systèmes dexploitation sur étagère. Cependant, un mauvais fonctionnement dun système dexploitation peut avoir un fort impact sur la sûreté de fonctionnement du système global, doù la nécessité de trouver des moyens efficaces pour caractériser sa sûreté de fonctionnement. Dans cette thèse, nous étudions létalonnage de la sûreté de fonctionnement des systèmes dexploitation par rapport aux comportements défectueux de lapplication. Nous spécifions les propriétés quun étalon de sûreté de fonctionnement doit satisfaire. Après, nous spécifions les mesures et la mise en oeuvre des trois étalons destinés à comparer la sûreté de fonctionnement de différents systèmes dexploitation. Ensuite, nous développons les prototypes des trois étalons. Ces prototypes servent à comparer les différents systèmes dexploitation des familles Windows et Linux, et pour montrer la satisfaction des propriétés identifiées.

Abstract

System developers are increasingly resorting to off-the-shelf operating systems, even in critical application domains. Any malfunction of the operating system may have a strong impact on the dependability of the global system. Therefore, it is important to make available information about the operating systems dependability. In our work, we aim to specify dependability benchmarks to characterize the operating systems with respect to the faulty behavior of the application. We specify three benchmarks intended for comparing the dependability of operating systems belonging to different families. We specify the set of measures and the procedures to be followed after defining the set of properties that a dependability benchmark should satisfy. After, we present implemented prototypes of these benchmarks. They are used to compare the dependability of operating systems belonging to Windows and Linux, and to show that our benchmarks satisfy the identified properties.

Mots-Clés / Keywords

Systèmes d'exploitation; Étalonnage de sûreté de fonctionnement; Injection de fautes; Analyse de performance; Robustesse; Operating systems; Dependability Benchmarking; Fault injection; Performance analysis; Robustness;

Résumé

Les pilotes de périphériques composent désormais une part essentielle des systèmes dexploitation. Plusieurs études montrent quils sont fréquemment à lorigine des dysfonctionnements des systèmes opératoires. Dans ce mémoire, nous présentons une méthode pour lévaluation de la robustesse des noyaux face aux comportements anormaux des pilotes de périphériques. Pour cela, après avoir analysé et précisé les caractéristiques des échanges entre les pilotes et le noyau (DPI - Driver Programming Interface), nous proposons une technique originale dinjection de fautes basée sur la corruption des paramètres des fonctions manipulées au niveau de cette interface. Nous définissons différentes approches pour lanalyse et linterprétation des résultats observés pour obtenir des mesures objectives de sûreté de fonctionnement. Ces mesures permettent la prise en compte de différents points de vue afin de répondre aux besoins réels de lutilisateur. Enfin, nous illustrons et validons lapplicabilité de cette méthode par sa mise en Suvre dans le cadre dun environnement expérimental sous Linux. La méthode proposée contribue à la caractérisation de la sûreté de fonctionnement des noyaux vis-à-vis des défaillances des pilotes du système. Limpact des résultats est double : a) permettre au développeur de tels logiciels didentifier les faiblesses potentielles affectant la sûreté de fonctionnement du système, b) aider un intégrateur dans le choix du composant le mieux adapté à ses besoins.

Abstract

Device drivers are becoming the most significant part of operating system kernels. Several studies have shown that such drivers are the most important source for operating system malfunctions. In this dissertation, we develop a method for objectively characterizing the impact of faulty drivers on the robustness of the kernels. First, elaborating on the analysis and specification of the way device drivers interact with the kernel (DPI - Driver Programming Interface), we propose a novel technique based on a series of controlled experiments using fault injection targeting the kernel core function parameters. We are also defining various approaches for analysing and interpreting the observed results to derive sensible dependability measures that accommodate various points of view in order to meet the real needs of the user of the method. Finally, experiments targeting the Linux kernel are reported that illustrate and validate the method. The proposed method contributes to the dependability characterization of kernels with respect to faulty drivers of the system. The impact of the results is twofold: a) allow the developer of such software components to identify the potential weaknesses that may impair dependability, b) support an integrator in selecting of the best component suited to its needs.

Mots-Clés / Keywords

Système d'exploitation; Sûreté de fonctionnement; Pilotes de périphériques; Expériences contrôlées; Injection de fautes; Operating systems; Dependability; Device drivers; Controlled experiments; Fault injection;

Résumé

La connexion de systèmes critiques à Internet pose de sérieux problèmes de sécurité. En effet, les techniques classiques de protection sont souvent inefficaces, dans ce nouveau contexte. Dans cette thèse, nous proposons une architecture générique tolérant les intrusions pour serveurs Internet. Cette architecture est basée sur les principes de redondance avec diversification afin de renforcer les capacités du système à faire face aux attaques. En effet, une attaque vise généralement une application particulière sur une plateforme particulière et savère très souvent inefficace sur les autres. Larchitecture comprend plusieurs serveurs Web (COTS) redondants et diversifiés, et un ou plusieurs mandataires mettant en Suvre la politique de tolérance aux intrusions. Loriginalité de cette architecture réside dans son adaptabilité. En effet, elle utilise un niveau de redondance variable qui sadapte au niveau dalerte. Nous présentons deux variantes de cette architecture destinées à différents systèmes cibles. La première architecture est destinée à des systèmes complètement statiques où les mises à jours sont effectuées hors-ligne. La deuxième architecture est plus générique, elle considère les systèmes complètement dynamiques où les mises à jours sont effectuées en temps réel. Elle propose une solution basée sur un mandataire particulier chargé de gérer les accès à la base de données. Nous avons montré la faisabilité de notre architecture, en implémentant un prototype dans le cadre dun exemple dune agence de voyages sur Internet. Les premiers tests de performances ont été satisfaisants, les temps de traitements des requêtes sont acceptables ainsi que le temps de réponse aux incidents.

Abstract

The connection of critical systems to the Internet is raising serious security problems, since the conventional protection techniques are rather inefficient in this new context. This thesis proposes a generic architecture for intrusion tolerant Internet servers. This architecture is based on redundancy and diversification principles, in order to increase the system resilience to attacks: usually, an attack is targeted at a particular software, running on a particular platform, and fails on others. The architecture is composed of redundant tolerance proxies that mediate client requests to a redundant bank of diversified application servers (COTS). The redundancy is deployed here to increase the availability and integrity of the system. To improve its performance, we have introduced the notion of adaptive redundancy: the redundancy level is selected by the proxies according to the current alert level. We present two architecture variants targeting different classes of Internet servers. The first one is proposed for fully static servers such as Web distribution with static content that provide stable information, which can be updated offline. The second architecture is proposed for fully dynamic systems where the updates are executed immediately on the on-line database. We have demonstrated the feasibility of this architecture by implementing an example of an Internet travel agency. The first performance tests are satisfactory, with acceptable request execution times and fast enough recovery after incidents.

Mots-Clés / Keywords

Tolérance aux fautes; Tolérance aux intrusions; Sécurité informatique; Internet; Fault tolerance; Intrusion tolerance; Adaptive redundancy;

Résumé

Nos travaux étudient la conception du test en complément de preuves : l'objectif est de définir des critères de sélection de test qui ciblent les lacunes de ces preuves. Le champ d'application proposé est la vérification d'algorithmes de tolérance aux fautes. Les preuves considérées peuvent être des démonstrations informelles, publiées dans la littérature, ou des preuves formelles inachevées. Dans le premier cas, nous définissons une méthode basée sur une reformulation du discours informel sous forme d'un arbre de preuve. L'arbre offre une représentation de l'articulation logique de la démonstration, ainsi qu'un support pour son analyse pas à pas. La faisabilité et l'efficacité du test guidé par la preuve sont évaluées expérimentalement sur deux exemples d'algorithmes incorrects : un algorithme d'ordonnancement de tâches, et un algorithme d'appartenance de groupe. Les résultats montrent que l'identification des lacunes de la preuve peut s'avérer efficace pour guider le test, sous réserve que l'analyse de l'arbre ne mette pas en évidence un manque de rigueur affectant l'ensemble de la démonstration. Dans le cas de preuves formelles, nous reprenons le principe d'un test basé sur l'arbre de preuve. L'établissement d'un lien entre les lemmes non prouvés et des sous-espaces d'entrée de test peut alors être plus problématique que précédemment. L'étude expérimentale d'un autre algorithme d'appartenance de groupe, partiellement prouvé avec le système PVS, montre néanmoins que, lorsqu'un lien est possible, cette information peut s'avérer pertinente pour guider le test.

Abstract

Our work studies the design of testing to supplement correctness proofs: the goal is to define test selection criteria which focus on the weak parts of the proof. The proposed field of application is the verification of fault-tolerance algorithms. The target proofs can be informal demonstrations, published in the literature, or partial formal proofs. In the first case, we define a method based on the reformulation of the informal discourse as a proof tree. This tree offers a representation of the logical structure of the demonstration, and a support for its step by step analysis. The feasibility and efficiency of proof guided testing are experimentally assessed using two examples of flawed algorithms: a task scheduling algorithm, and a group membership algorithm. The results show that identification of the weak parts of the proof can be effective to guide testing, provided that the tree analysis does not reveal a lack of rigor affecting the whole demonstration. In the case of formal proofs, we retain the principle of testing based on the proof tree. Establishing a link between unproved lemmas and subspaces of the test input domain can be more difficult than previously. Still, the experimental study of another group membership algorithm, partially proved with the PVS system, shows that, if a link can be established, this information can be relevant to guide testing.

Mots-Clés / Keywords

Sûreté de fonctionnement; Algorithmes de tolérance aux fautes; Collaboration de techniques de vérification; Vérification du logiciel; Test; Preuve mathématique; Dependability; Fault Tolerance Algorithms; Collaboration of Verification Techniques; Software Verification; Testing levels of classes; Mathematical Proof;

Résumé

Les environnements informatiques académiques ou industriels utilisent de grands parcs de systèmes interconnectés, le plus souvent hétérogènes, incluant un nombre important de machines et serveurs Unix, Windows NT et Windows 2000. Ces environnements sont conçus pour favoriser le partage des ressources et le travail coopératif entre les utilisateurs. Néanmoins, ces avantages peuvent être compromis par des défaillances du réseau de communication, des applications ou des systèmes hôtes. Le meilleur moyen pour comprendre le comportement de systèmes informatiques en présence de fautes est de collecter des données issues de l'observation de leur comportement dans leur environnement opérationnel. Nos travaux portent sur le développement et la mise en Suvre de méthodes permettant de faciliter la collecte et lexploitation pour des analyses de sûreté de fonctionnement de fichiers enregistrés automatiquement par certains systèmes dexploitation. Les systèmes ciblés dans notre étude sont des machines Unix, Windows NT et Windows 2000 interconnectés au travers dun réseau local. Outre la définition et la mise en Suvre de la stratégie de collecte de données opérationnelles, le traitement des données vise à extraire les informations pertinentes et à obtenir des mesures quantitatives pour caractériser les systèmes du point de vue de la sûreté de fonctionnement. La méthode et les résultats obtenus sont destinés à aider les administrateurs systèmes à suivre et analyser la sûreté de fonctionnement de leur parc de machines. L'analyse conjointe des deux plates-formes parmi les plus utilisées aujourd'hui (Unix, Windows) nous a permis de réaliser des analyses comparatives. Nous avons aussi montré comment les mesures estimées à partir des données opérationnelles peuvent être intégrées dans une modélisation analytique permettant dévaluer la disponibilité telle quelle est perçue par les utilisateurs. Lanalyse comparative des mesures caractérisant les systèmes et des celles reflétant la perception des utilisateurs constitue aussi un résultat original de nos travaux.

Abstract

Academic and industrial computing environments are mainly based on interconnected heterogeneous systems including a large number of Unix, Windows NT and Windows 2000 workstations and servers. These environments are designed to facilitate resource sharing and cooperative work between users. However, these benefits may be compromised by failures affecting the communication network, the applications or the end systems. There is no better way to understand the behavior of computing environments in the presence of faults than by direct measurement, analysis and assessment based on data obtained from the observation of their behavior in an operational environment. Our work focuses on the development and the implementation of methods allowing data collection and dependability analysis of log files automatically recorded by some operating systems. The target systems in our study are Unix, Windows NT and Windows 2000 systems interconnected in a local area network. Besides the definition and the implementation of the data collection strategy, the data processing aims to extract the relevant information and to obtain quantitative measures in order to characterize the target systems from a dependability point of view. The method and the results obtained are intended to help system administrators to observe and analyze the dependability characteristics of their systems. The joint analysis of two commonly used platforms (Unix, Windows) has allowed us to make comparative analyses. We also showed how the measures assessed from operational data can be integrated within an analytical modeling allowing the estimation of user-perceived availability. The comparative analysis of measures characterizing the systems and those reflecting users perceptions represents another original result of our work.

Mots-Clés / Keywords

Sûreté de fonctionnement; Evaluation expérimentale; Collecte de données; Analyse de données; Disponibilité; Modélisation analytique; Analyse de dépendances; Dependability; Experimental evaluation; Data collection; Data analysis; Availability dependency analysis;

Résumé

Le développement dInternet et la généralisation de son utilisation ont entraîné lémergence de nouvelles applications réparties à grande échelle, le commerce électronique par exemple. Mais ces applications posent des problèmes de sécurité difficiles à résoudre, en raison du grand nombre dutilisateurs et de machines concernés. Des solutions existent pour bien garantir la sécurité des communications point à point et pour restreindre les connexions à un sous-réseau, mais elles sont dune efficacité limitée, et souvent intrusives vis-à-vis de la protection de la vie privée des utilisateurs. Dans le but de lever ces limitations et de contrôler de façon efficace lexécution dapplications réparties sur un nombre plus ou moins grand de machines du réseau, nous avons développé des schémas dautorisation à la fois souples pour permettre de contrôler des applications de tous types, et efficaces par lapplication du principe du moindre privilège : seules les opérations nécessaires au fonctionnement de lapplication doivent être autorisées. Larchitecture que nous proposons est organisée autour de serveurs dautorisation répartis, tolérants aux fautes accidentelles et aux intrusions, et de moniteurs de référence sur chaque site participant. Les serveurs dautorisation vérifient si les requêtes doivent être autorisées, et, dans ce cas, génèrent des preuves dautorisation composées de capacités et de coupons qui sont ensuite vérifiées par les moniteurs de référence. Ces coupons forment un mécanisme de délégation original qui respecte le principe du moindre privilège. Compte-tenu de lhétérogénéité des systèmes connectés, il nest pas envisageable dintégrer un moniteur de référence spécifique dans le système opératoire de chaque site. Cest pourquoi les moniteurs de référence sont en partie implantés dans des cartes à puce Java.

Abstract

Internet development and generalization of its use have led to the emergence of new, largely distributed applications, for example e-commerce. These applications pose security problems that are difficult to solve, because of the great number of users and machines. Solutions exist to guarantee the security of point-to-point communications and to restrict connections to sub-networks, but they are limited and often privacy intrusive. In order to overcome these limitations and to provide efficient protection of distributed applications on a large number of distributed machines, we have developed a flexible authorization scheme that can be used to control all kinds of applications. Our scheme implements the least privilege principle : only those operations necessary for the applications execution must be authorized. The architecture that we propose is organized around distributed authorization servers, which could be made tolerant to accidental faults and intrusions, and reference monitors on each participating site. The authorization servers check whether requests must be authorized, and, in this case, generate authorization proofs made up of capabilities and vouchers which are then verified by reference monitors. The vouchers form an original mechanism of delegation, which conforms to the least privilege principle. Given the heterogeneity of the connected systems, we have implemented the reference monitors using Java smart cards in order to avoid intrusive changes to all the different operating systems present in the Internet

Mots-Clés / Keywords

Sécurité informatique; Contrôle d'accès; Serveur dautorisation; Délégation des droits daccès; Internet; Tolérance aux intrusions; Moniteur de référence; Preuve dautorisation; Computer security; Access control; Authorization server; Delegation of access rights; Intrusions tolerance; Reference monitor; Authorization proof;