Cette thèse traite du problème d'une protection en profondeur qui puisse être assurée par un système d'exploitation. Elle établit la faiblesse des solutions existantes pour l'expression des besoins de sécurité. Les approches supportent en général une seule propriété de sécurité. Nous proposons donc un langage qui permet de formaliser un large ensemble de propriétés de sécurité. Ce langage exprime les activités système directes et transitives. Il permet de formaliser la majorité des propriétés de confidentialité et d'intégrité de la littérature. Il est adapté à l'expression de modèles de protection dynamique. A titre d'exemple, un nouveau modèle dynamique est proposé pour la protection des différents domaines d'usage d'un navigateur Web. Nous définissons une méthode de compilation du langage pour analyser les appels systèmes réalisés par les processus utilisateurs. La compilation repose sur la construction et l'analyse d'un graphe de flux d'information. Nous montrons qu'en pratique la complexité reste faible. Une implantation de ce langage est proposée sous la forme d'un contrôle d'accès mandataire dynamique pour Linux. Une expérimentation à large échelle a été réalisée sur des pots-de-miel à haute interaction. Notre protection a montré son efficacité aussi bien pour les serveurs que les postes client. Il présente des perspectives intéressantes aussi bien pour la protection des systèmes que pour l'analyse de vulnérabilités. Ce travail a contribué au projet SPACLik vainqueur du défi sécurité de l'ANR SEC&SI.

In Chapter 1 we give a general introduction and motivate the need for clustering and dimension reduction methods. We continue in Chapther 2 with a review of different types of existing clustering and dimension reduction methods.<br /><br />In Chapter 3 we introduce mixture densities and the expectation-maximization (EM) algorithm to estimate their parameters. Although the EM algorithm has many attractive properties, it is not guaranteed to return optimal parameter estimates. We present greedy EM parameter estimation algorithms which start with a one-component mixture and then iteratively add a component to the mixture and re-estimate the parameters of the current mixture. Experimentally, we demonstrate that our algorithms avoid many of the sub-optimal estimates returned by the EM algorithm. Finally, we present an approach to accelerate mixture densities estimation from many data points. We apply this approach to both the standard EM algorithm and our greedy EM algorithm.<br /><br />In Chapter 4 we present a non-linear dimension reduction method that uses a constrained EM algorithm for parameter estimation. Our approach is similar to Kohonen's self-organizing map, but in contrast to the self-organizing map, our parameter estimation algorithm is guaranteed to converge and optimizes a well-defined objective function. In addition, our method allows data with missing values to be used for parameter estimation and it is readily applied to data that is not specified by real numbers but for example by discrete variables. We present the results of several experiments to demonstrate our method and to compare it with Kohonen's self-organizing map.<br /><br />In Chapter 5 we consider an approach for non-linear dimension reduction which is based on a combination of clustering and linear dimension reduction. This approach forms one global non-linear low dimensional data representation by combining multiple, locally valid, linear low dimensional representations. We derive an improvement of the original parameter estimation algorithm, which requires less computation and leads to better parameter estimates. We experimentally compare this approach to several other dimension reduction methods. We also apply this approach to a setting where high dimensional 'outputs' have to be predicted from high dimensional 'inputs'. Experimentally, we show that the considered non-linear approach leads to better predictions than a similar approach which also combines several local linear representations, but does not combine them into one global non-linear representation.<br /><br />In Chapter 6 we summarize our conclusions and discuss directions for further research.

Pour permettre une plus grande capacité de calcul les concepteurs de systèmes embarqués se tournent aujourd'hui vers les MPSoC. Malheureusement, ces systèmes sont difficiles à programmer. Un des problèmes durs est l'expression et l'optimisation des réorganisations de données au sein d'un programme. Dans cette thèse nous souhaitons proposer une chaîne de compilation qui : 1) propose une syntaxe simple et haut-niveau pour exprimer le découpage et la réorganisation des données d'un programme parallèle ; 2) définisse une exécution déterministe du programme (critique dans le cadre des systèmes embarqués) ; 3) optimise et adapte les programmes aux contraintes de l'architecture. Pour répondre au point 1) nous proposons un langage haut-niveau, SLICES, qui permet de décrire les réorganisation de données à travers des découpages multidimensionnels. Pour répondre au point 2) nous montrons qu'il est possible de compiler SLICES vers un langage de flots de données, SJD, qui s'inscrit dans le modèle des Cyclostatic Data-Flow et donc admet une exécution déterministe. Pour répondre au point 3) nous définissons un ensemble de transformations qui préservent la sémantique des programmes SJD. Nous montrons qu'il existe un sous-ensemble de ces transformations qui génère un espace de programmes équivalents fini. Nous proposons une heuristique pour explorer cet espace de manière à choisir la variante la plus adaptée à notre architecture. Enfin nous évaluons cette méthode sur deux problèmes classiques : la réduction de la mémoire consommée et la réduction des communications d'une application parallèle.

Les contraintes arithmétiques sont largement utilisées dans les langages formels comme les expressions, les grammaires d'arbres et les chemins réguliers. Ces contraintes sont utilisées dans les modèles de contenu des types (XML Schemas) pour imposer des bornes sur le nombre d'occurrences de noeuds. Dans les langages de requêtes (XPath, XQuery), ces contraintes permettent de sélectionner les noeuds ayant un nombre limité de noeuds accessibles par une expression de chemin donnée. Les types et chemins étendus avec les contraintes de comptage constituent le prolongement naturel de leurs homologues sans comptage déjà considérés comme des constructions fondamentales dans les langages de programmation et les systèmes de type pour XML. Un des défis majeurs en programmation XML consiste à développer des techniques automatisées permettant d'assurer statiquement un typage correct et des optimisations de programmes manipulant les données XML. À cette fin, il est nécessaire de résoudre certaines tâches de raisonnement qui impliquent des constructions telles que les types et les expressions XPath avec des contraintes de comptage. Dans un futur proche, les compilateurs de programmes XML devront résoudre des problèmes de base tels que le sous-typage afin de s'assurer au moment de la compilation qu'un programme ne pourra jamais générer de documents non valides à l'exécution. Cette thèse étudie les logiques capables d'exprimer des contraintes de comptage sur les structures d'arbres. Il a été montré récemment que le μ-calcul sur les graphes, lorsqu'il est étendu à des contraintes de comptage portant exclusivement sur les noeuds successeurs immédiats est indécidable. Dans cette thèse, nous montrons que, sur les arbres finis, la logique avec contraintes de comptage est décidable en temps exponentiel. En outre, cette logique fournit des opérateurs de comptage selon des chemins plus généraux. En effet, la logique peut exprimer des contraintes numériques sur le nombre de noeuds descendants ou même ascendants. Nous présentons également des traductions linéaires d'expressions XPath et de types XML comportant des contraintes de comptage dans la logique.

Les protocoles de sécurité sont des programmes informatiques qui définissent des règles d'échange entre les points d'un réseau et permettent de sécuriser les communications. Ils sont utilisés par exemple dans les distributeurs de billets, les abonnements aux chaînes de télévision payantes, la téléphonie mobile, le commerce électronique. Leur objectif est de garantir le secret d'une donnée, d'authentifier un des participants, de garantir l'anonymat ou la non-répudiation, etc. Ces programmes sont exécutés sur des réseaux ouverts facilement accessibles (comme internet). Aussi, pour démontrer qu'ils remplissent bien leurs objectifs, il est nécessaire de prendre en compte les attaques dont ils peuvent faire l'objet. L'objet de mon mémoire d'habilitation à diriger des recherches est de montrer que les méthodes formelles peuvent être utilisées avec succès pour entreprendre une analyse fine des protocoles cryptographiques, à travers une palette variée d'outils. Nous présentons des procédures pour déterminer de façon automatique si un protocole est sûr. Nous avons proposés différents algorithmes en fonction des propriétés de sécurité considérées ainsi que des primitives cryptographiques utilisées (chiffrement, signature, hachage, ou exclusif, etc.). D'autre part, nous caractérisons des conditions qui permettent de combiner les résultats précédents et de concevoir les protocoles de façon modulaire. Ces résultats se basent sur des modèles symboliques, très différents de ceux utilisés en cryptographie où la notion de sécurité est basée sur la théorie de la complexité. Cette notion de sécurité est mieux adaptée pour identifier toutes les attaques possibles dans la réalité mais, en contrepartie, les (lourdes) preuves de sécurité sont effectuées à la main et semblent difficilement automatisables. Nous avons identifié des hypothèses cryptographiques qui permettent de relier les approches cryptographiques et symboliques. Il est alors possible d'obtenir des preuves de sécurité à un niveau cryptographique, directement à partir des preuves établies (automatiquement) dans un cadre symbolique.

Ce manuscrit décrit les travaux de recherche effectués au cours de ma thèse, au sein de l'équipe informatique et recherche opérationnelle du laboratoire CREAM1, en collaboration avec le laboratoire LISA 2, et avec le soutien du Conseil Général de la ville d'Angers. Ces travaux de recherche se situent à l'intersection des domaines de l'optimisation combinatoire et des systèmes multi-agents. Ils s'inscrivent dans la continuité des propositions de modèles ou de plates-formes pour les métaheuristiques parallèles. Ce rapport réunit différentes notions du parallélisme, du paradigme multi-agents et des métaheuristiques afin d'apporter des méthodes de résolution performantes (robustes et autoadaptatives) à des problèmes d'optimisation combinatoire réels. Il démontre que l'introduction de stratégies de parallélisation et d'échange d'informations à un algorithme à population permet à ce dernier d'améliorer considérablement ses facultés de recherche de solutions. En outre, l'utilisation des agents mobiles permet une exploitation optimale des ressources de calcul inutilisées dans un organisme (laboratoire, entreprise) et de favoriser ainsi l'autonomie des processus de calcul pour pouvoir gérer les éventuelles pannes dans un réseau. Le succès de cette approche dans la résolution d'un problème de tournées de véhicules et d'un problème d'ordonnancement de production, montre l'intérêt pratique de ces méthodes et leurs retombées économiques potentielles. Ce travail de recherche représente l'une des premières explorations des possibilités offertes par deux domaines fort prometteurs de l'intelligence artificielle distribuée et de la recherche opérationnelle. L'union de méthodes auto-adaptatives et d'une puissance de calcul imposante pourrait fort bien se révéler un outil performant pour la résolution de problèmes d'une telle envergure.

Les systèmes multi-agents mettent en jeu des entités artificielles, conçues par des utilisateurs potentiellement différents, devant se coordonner pour atteindre leur but. La problématique générale est donc l'atteinte d'états "satisfaisants" en dépit de contraintes liées à la distribution des entités qui prennent part à la décision collective, et du caractère non nécessairement coopératifs de ces agents. Je discute de problèmes de vote dans le cas où les profils représentant les préférences des agents prenant part à la décision ne sont pas complètement spécifiés (à cause, par exemple, de la perte de messages du fait de la distribution, ou encore de l'impossibilité de spécifier parfaitement un profil portant sur un nombre rédhibitoire d'alternatives, comme dans le cas de domaines combinatoires). Les questions que nous abordons sont par exemple celles de la taille minimale nécessaire à encoder le profil partiel tout en restant capable de déterminer de manière certaine l'alternative choisie après complétion des votes, ou encore de la difficulté (algorithmique) liée à la détermination des alternatives que l'on peut exclure sans craindre de regretter ce choix plus tard, même si d'autres alternatives peuvent apparaîtrent. J'aborde également des procédures complètement décentralisées d'allocation de ressources. Ici on suppose que les agents débutent avec une allocation initiale et modifient de manière itérative cette allocation par le biais de contrats, c'est-à-dire de réallocation locale de ressources entre eux. En posant la contrainte que chacun de ces contrats doit être individuellement rationnel on se penche sur les garanties de convergence de tels systèmes vers de états efficaces et/ou équitables (au sens par exemple de l'égalitarisme ou l'absence d'envie). J'envisage enfin un processus de prise de décision collective plus délibératif, au sens où les agents peuvent échanger des arguments et contre-arguments, pour (éventuellement) modifier le point de vue des autres. Dans un premier temps je discute d'un cadre où les agents coopèrent en vue d'établir un diagnostic commun d'une situation, alors que les agents ne percoivent que localement leur environnement et ne disposent que de possibilités restreintes de communication. Chaque agent construit (sur la base d'informations partielles) une hypothèse qui pourra être par la suite réfutée par d'autres agents, nous sommes en présence d'un raisonnement de type non-monotone. Je présente enfin brièvement le cadre non-coopératif d'une argumentation multi-partite, où les agents peuvent avoir des opinions réellement contradictoires. Un protocole simple est proposé, qui contraint minimalement la pertinence des arguments échangés, et quelques phénomènes liés au comportement statégique des agents sont illustrés.

Dans nos travaux, nous nous sommes intéressés aux politiques d'ordonnancement en-ligne, pour lesquelles l'ordre d'exécution des tâches est déterminé sur la base des tâches actives dans le système et sans connaissance a priori des tâches qui arriveront dans le futur. Cette problématique s'étend aux réseaux informatiques pour ordonnancer les messages sur le réseau informatique interconnectant les diérents calculateurs du système temps réel. La première contribution concerne le placement et ordonnancement simultanés des tâches dans un système temps réel distribué, permettant de minimiser le nombre de processeurs nécessaires pour respecter les spécications temporelles des tâches. La seconde contribution concerne les tâches à criticité multiple. L'objectif de ce modèle est de prendre en compte la notion de criticité des diérentes tâches, comme par exemple dans la norme DO-178B utilisée en aéronautique. Enn, nous nous sommes intéressés aux systèmes multiprocesseurs ordonnancés par des algorithmes d'ordonnancement semi-partitionné. Cette classe d'algorithme utilise une stratégie par partitionnement pour répartir les tâches parmi les processeurs tout en autorisant la migration des tâches qui ne peuvent pas être aectées à un processeur donné sans violation d'échéance.

Une première partie de l'exposé sera consacrée aux automates max-plus et min-plus. Ces automates apparaissent naturellement dans des problèmes d'ordonnancement et dans certains problèmes de la théorie des langages comme la puissance finie ou la hauteur d'étoile. Je montrerai comment décider si un automate max-plus d'ambiguïté bornée réalise une série intrinsèquement non ambiguë, ce qui permet d'étendre la classe de famille dans laquelle la séquentialité des séries rationnelles max-plus est décidable. Par ailleurs, je présenterai le résultat selon lequel toute série qui est à la fois une série rationnelle max-plus et min-plus est en fait une série non ambiguë. La seconde partie de l'exposé portera sur la notion de conjugaison d'automates avec multiplicités, inspirée par la celle de conjugaison des systèmes dynamiques. Nous verrons dans quelle mesure des automates qui réalisent des séries identiques peuvent être reliés par une chaîne de conjugaison. D'autre part, nous donnerons une interprétation de cette définition matricielle en termes de revêtements d'automates. Nous verrons enfin les conséquences de la combinaison de ces deux approches.

Dans un réseau constitué de plusieurs milliers d'ordinateurs, l'apparition de fautes est inévitable. Etre capable de tester le comportement d'un programme distribué dans un environnement où l'on peut contrôler les fautes (comme le crash d'un processus) est une fonctionnalité importante pour le déploiement de programmes fiables.....