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.....

La production de dessins animés 2D qui suit actuellement un schéma mis en place dans les années 1920 fait intervenir un très grand nombre de compétences humaines et de métiers différents. Par opposition à ce mode de travail traditionnel, la production de films de synthèse 3D, en exploitant les technologies et les outils les plus récents de modélisation et d'animation 3D, s'affranchit en bonne partie de cette composante artisanale et vient concurrencer l'industrie du dessin animé traditionnel en termes de temps et coûts de fabrication. <br />Les défis à relever par l'industrie du dessin animé 2D se posent donc en termes de :<br />1. Réutilisation des contenus selon le paradigme d'accès «Create once, render many»,<br />2. Facilité d'échange et de transmission des contenus ce qui nécessite de disposer d'un unique format de représentation,<br />3. Production efficace et économique des contenus requérant alors une animation automatisée par ordinateur.<br />Dans ce contexte compétitif, cette thèse, réalisée dans le cadre du projet industriel TOON financé par la société Quadraxis (www.quadraxis.com) et supporté par l'Agence Nationale de Valorisation de la Recherche (ANVAR), a pour objectif de contribuer au développement d'une plate-forme de reconstruction, déformation et animation de modèles 3D de visages pour les dessins animés 2D. Vecteurs de la parole et des expressions, les visages nécessitent en effet une attention particulière quant à leur modélisation et animation conforme aux souhaits des créateurs de dessins animés. <br />Un état de l'art des méthodes, outils et systèmes contribuant à la création de modèles 3D faciaux et à leur animation est présenté et discuté au regard des contraintes spécifiques qui régissent les règles de création des dessins animés 2D et la chaîne de fabrication traditionnelle.<br />Ayant identifié les verrous technologiques à lever, nos contributions ont porté sur :<br /> l'élaboration d'une méthode de conception de visages virtuels 3D à partir d'une part d'un modèle 3D de type seamless, adapté aux exigences d'animation sans rupture, et d'autre part d'un ensemble de dessins 2D représentant les caractéristiques faciales,<br /> la mise au point d'une procédure de création de poses clés, mettant en œuvre plusieurs méthodes de déformation non-rigide,<br /> la conception d'un module d'animation 3D compatible avec le standard MPEG-4/AFX. <br /><br />Les développements réalisés, intégrés dans un premier prototype de la plate-forme FaceTOON, montrent un gain en temps de 20% sur l'ensemble de la chaîne de production tout en assurant une complète interopérabilité des applications via le standard MPEG-4.

Le Web connaît ces dernières années un essor important qui implique la mise en place de nouvelles solutions de distribution de contenu répondant aux exigences de performance, passage à l'échelle et robustesse. De plus, le Web 2.0 a favorisé la participation et la collaboration entre les utilisateurs tout en mettant l'accent sur les systèmes P2P qui reposent sur un partage de ressources et une collaboration décentralisée. Nous avons visé, à travers cette thèse, la construction d'une infrastructure P2P pour la distribution de contenu. Toutefois, cette tâche est difficile étant donné le comportement dynamique et autonome des pairs ainsi que la nature des overlays P2P. Dans une première étape, nous nous intéressons au partage de fichiers en P2P. Nous abordons le problème de consommation de bande passante sous deux angles : l'inefficacité de la recherche et les transferts de fichiers longue distance. Notre solution Locaware consiste à mettre en cache des index de fichiers avec des informations sur leurs localités. Elle fournit également un support efficace pour les requêtes par mots clés qui sont courantes dans ce genre d'applications. Dans une deuxième étape, nous élaborons une infrastructure CDN P2P qui permet à tout site populaire et sous-provisionné de distribuer son contenu, par l'intermédiaire de sa communauté d'utilisateurs intéressés. Pour un routage efficace, l'infrastructure Flower-CDN combine intelligemment différents types d'overlays avec des protocoles épidémiques tout en exploitant les intérêts et les localités des pairs. PetalUp-CDN assure le passage à l'échelle alors que les protocoles de maintenance garantissent la robustesse face à la dynamicité des pairs. Nous évaluons nos solutions au travers de simulations intensives ; les résultats montrent des surcoûts acceptables et d'excellentes performances, en termes de taux de hit et de temps de réponse.

Bien souvent utilisée comme outils d'intégration et d'échange entre les différentes parties de projets scientifiques interdisciplinaires, la simulation numérique est en plein essor dans les sciences sociales, et notamment la simulation multi-agents. En effet, la capacité de calcul de plus en plus puissante des ordinateurs et les méthodes de recherche individu-centrées en sciences sociales (micro-économie ou individualisme méthodologique, pour ne citée que celles-ci) ont suscité un intérêt croissant pour la représentation logicielle de processus interagissant les un avec les autres dans le cadre d'un phénomène qualifié de complexe. Notre thèse se positionne ainsi dans ce contexte, plus particulièrement au niveau des relations causales entre des comportements microscopiques en interaction et un phénomène macroscopique émergeant. Notre travail de recherche s'inscrit dans un projet mené en collaboration avec des sociologues qui vise à rendre compte de phénomènes organisationnels. Plutôt que de s'emparer de cas empiriques et de produire des modèles ad'hoc, nous proposons une démarche innovante consistant à formaliser une théorie sociologique : la Sociologie de l'Action Organisée (SAO) de M. Crozier et E. Friedberg. L'intérêt d'une telle modélisation est de disposer d'un méta-modèle sociologiquement fondé permettant de modéliser de façon formelle différentes organisations relevant de son champ d'expertise. Nous proposons de mettre en œuvre cette formalisation via un laboratoire virtuel, SocLab, permettant d'éditer le modèle d'une organisation puis de mener des expériences et tester nos hypothèses. Du méta-modèle de la SAO à l'outil d'expérimentation SocLab, notre thèse propose une démarche méthodologique pour l'analyse organisationnelle assistée par l'expérimentation virtuelle. Dans la perspective d'analyser la causalité émergente des processus organisationnels, nous avons défini une série d'indicateurs numériques qui servent de base aux interprétations indispensables à la vérification et la validation d'un modèle. Ces indicateurs permettent de caractériser acteurs, relations, et transactions dans les termes de la SAO et de comparer différents modèles, d'une même organisation ou d'organisations différentes. Nous présentons ensuite un modèle d'agent adaptatif à base de règles qui rend compte du comportement stratégique des acteurs dont la rationalité est orientée vers la coopération tel que le postule la SAO. Nous présentons par ailleurs une méthodologie de validation des modèles de rationalité. Enfin nous illustrons notre démarche avec un cas d'étude issu du corpus SAO, que nous modélisons, soumettons à diverses hypothèses, que nous interprétons et (in)validons par la simulation. Outre la démarche de formalisation de la SAO et le développement du laboratoire virtuel SocLab, la thèse présente de nombreuses originalités que ce soit au niveau des concepts développés autour de l'échange et de la coopération, au niveau du modèle d'agent stratégique-coopératif, ou au niveau des outils d'analyse produits ou mis en œuvre. L'intérêt principal réside dans le développement d'une démarche rigoureuse couvrant de nombreux aspects de l'utilisation de l'expérimentation virtuelle en sociologie qui devrait permettre au chercheur, à l'étudiant comme aux consultants en organisation de produire des raisonnements solides sur le /phénomène organisation/.

L'unité du travail réside en ce qu'on s'intéresse à la recherche de structure dans les données numériques (issues de données multimédia), en vue d'y faciliter la recherche d'information. Le cadre méthodologique de la résolution est que nous privilégions ici celui des modèles probabi- listes, en particulier les mélanges de lois, et de l'estimation statistique associée. La recherche de structure implique que le jeu de données étudié est composé de sous-populations de caracté- ristiques distinctes : il s'agit de séparer et de caractériser ces sous-populations, deux problèmes fortement imbriqués. Les entités extraites et les attributs qu'on en leur associe seront alors directement utiles pour la recherche d'information.