Dans les jeux multijoueurs, où plusieurs joueurs participent à une même partie et communiquent entre eux à travers un réseau, les joueurs peuvent avoir des visions différentes du jeu en raison des délais de communication. Ceci engendre des incohérences encore plus importantes sur les réseaux mobiles tels que les réseaux 3G où les délais de communication peuvent atteindre plusieurs secondes. Des algorithmes doivent donc être mis en place pour maintenir la cohérence entre les joueurs. Ces algorithmes sont assez complexes et difficiles à programmer et mettre au point. Le but de cette thèse est de proposer une architecture logicielle qui découple la conception du jeu, de ses besoins de communication en proposant une infrastructure de communication qui pourra être interchangeable en fonction des technologies ; cette infrastructure prend la forme originale d'un composant de synchronisation. Ainsi, les conséquences des propriétés physiques du transport des informations pourront être plus ou moins masquées en intégrant dans cette infrastructure les algorithmes adéquats.

Les travaux décrits dans ce mémoire portent sur la supervision du trac dans le c÷ur de réseau, au niveau de la couche applicative. Nous illustrons l'intérêt de la supervision dans la couche 7 grâce à trois études qui montrent les bénéces obtenus pour la sécurité et pour l'évaluation de modications d'architecture du réseau. La première étude utilise l'épidémiologie, la science qui étudie les causes et la propagation des maladies. L'épidémiologie fournit des concepts et des mé- thodes pour analyser à quels risques potentiels d'infection les PC des clients ADSL sont exposés. En particulier, nous voulons analyser les risques par rapport aux applications utilisées par les clients. Grâce à la supervision applicative du trac d'un large échantillon de clients ADSL dans le c÷ur de réseau, nous construisons un prol d'utilisation du réseau pour chaque client et nous détectons ceux qui génèrent du trac malveillant. A partir de ces données, nous étudions le lien entre certaines caractéristiques des clients avec leurs risques d'être infecté. Nous mettons en évidence deux applications et un syst ème d'exploitation qui constituent des facteurs de risque. Nous en déduisons un prol de client pour lequel existe un risque important de se voir infecter par un virus informatique. La deuxième étude porte sur l'opportunité pour un opérateur d'installer des caches P2P dans son réseau. Mettre les contenus P2P en cache pourrait être un bon moyen de réduire la charge dans le réseau. Cependant, les performances des caches sont aectées par de nombreux facteurs, en relation avec les caches eux-mêmes, mais également avec les propriétés de l'overlay, les contenus P2P et la localisation du cache. Dans le but d'évaluer l'utilité potentielle des caches P2P, nous eectuons la supervision à grande échelle du trac P2P, dans le réseau opérationnel de France Télécom. Après avoir étudié certaines propriétés du trac observé, nous simulons le fonctionnement d'un cache en nous basant sur les données recueillies pendant 10 mois. Nous sommes alors en mesure d'évaluer les performances d'un cache, en termes d'économie de bande passante si un cache était réellement déployé au moment de la capture de nos traces. De plus, nous étudions l'impact sur la performance de paramètres tels que les caractéristiques du cache et de mani ère plus importante le nombre de clients servis par le cache. Les résultats montrent que l'on pourrait réduire le trac P2P d'échange de chiers de 23% avec un cache passif. Enn, la troisème étude porte sur l'opportunité pour un opérateur de réseau de coopérer avec les réseaux P2P à travers une interface de type P4P. L'approche P4P permet aux clients P2P d'améliorer leur sélection de pairs dans l'overlay. Le trac P2P représente une proportion importante du volume du trac dans les réseaux. Cependant, les systèmes P2P les plus couramment utilisés à l'heure actuelle ne tiennent pas compte de l'infrastructure réseau sous-jacente. Grâce à la supervision applicative, nous déterminons les béné- ces de P4P, d'une part pour les applications P2P et d'autre part pour les opérateurs. Les résultats de cette expérimentation indiquent que les applications P2P ont besoin de plus d'informations que seulement l'AS de provenance des sources potentielles pour améliorer leurs performances. De plus nous montrons que le trac P2P inter-domaines pourrait être réduit d'au moins 72% grâce à P4P. Nous montrons donc dans ces travaux que la supervision applicative permet : d'analyser des phénomènes complexes liés à l'usage qui est fait du ré- seau, tels que la contamination par un ver ou un virus informatique ; d'évaluer, de manière précise et quantitative, l'impact de certaines modi cations d'architecture sur le trac opérationnel. D'une manière plus générale, nous illustrons l'importance du rôle de l'opé- rateur de réseau dans le déploiement et l'exploitation des services Internet, toujours plus gourmands en bande passante, que nous ne manquerons pas de voir apparaître à l'avenir. En eet la supervision applicative est un outil essentiel pour l'évaluation des protocoles et architectures mis en ÷uvre dans les services Internet, complémentaire des autres outils dans ce domaine.

We present the BIP component framework for component-based construction of real-time systems from heterogeneous components. BIP stands for Behavior, Interaction and Priority, the three main elements for building components. It considers that systems can be obtained by composition of 3-layered components, where the lowest layer represents behavior as a set of transitions with triggers and actions; the intermediate level is the set of the interactions between the transitions of the behavior level, and the upper level is a set of dynamic priority rules. BIP has a rigorous formal semantics, and supports a system construction methodology based on a parameterized composition operator on components. The use of a layered composition operator allows incremental construction. The system construction process can be viewed as a sequence of transformations in a three-dimensional space of Behavior X Interaction X Priority, and provides a basis for the study of property preserving transformations between subclasses of systems such as untimed/timed, asynchronous/synchronous. We also provide a distributed semantics for systems in BIP, using a partial state model, and show the use of an auxiliary predicate called Oracle to preserve observational equivalence with respect to the centralized semantics. We present an implementation of BIP as a tool chain that allows modeling, static analysis and execution of BIP descriptions on a dedicated engine. Three different implementations for the engine have been provided, a centralized enumerative engine, a centralized symbolic engine and a distributed engine. We illustrate the use of the tool chain for two major application domains, Software Componentization, and Modeling mixed hw/sw systems.

La performance d'un système de localisation de source passive acoustique basé sur un ensemble de capteurs ne dépend pas seulement du choix des algorithmes d'estimation mais est aussi fortement corrélée à la géométrie du réseau de capteurs et à la position de la source. Cette thèse propose des procédures d'optimisation des estimateurs de position via un positionnement de capteurs optimal. Afin d'optimiser ce processus pour une source "quasi-statique", trois mesures de performance sont traitées, comparées et évaluées : la borne inférieure de Cramer-Rao (CRLB), la dilution de précision géométrique (GDOP) et le nombre de conditionnement. Les deux premières mesures décrivent l'influence du bruit de mesure, décrit par une fonction de probabilité connue, tandis que la dernière est une mesure non-statistique. En considérant le bruit Gaussien et l'estimateur d'un modèle linéarisé, il est montré que la même configuration est obtenue par ces trois mesures. Ensuite ces mesures de performance sont étendues pour une source mobile en proposant deux approches. La première consiste à représenter la zone de surveillance par plusieurs points représentatifs et à minimiser la moyenne des mesures de performance de tous ces points. La deuxième est une approche dynamique, qui modélise le mouvement de la source par des équations d'état. Puis des estimateurs récursifs Bayesiens (par exemple le filtre de Kalman pour des systèmes linéaires) sont appliqués afin de prédire la position future de la source. On sélectionne alors parmi tous les microphones, un sous-ensemble qui minimise la mesure de performance pour la position prédite. Ce sous-ensemble est alors utilisé pour l'estimation.

Les documents numériques sont aujourd'hui des données complexes qui intègrent d'une manière hétérogène des informations textuelles, structurelles, multimédia ainsi que des méta-données. Le langage de balisage générique XML s'est progressivement imposé comme support privilégié non seulement pour l'échange des données mais aussi pour leur stockage. La gestion des documents stockés sous les formats XML nécessite le développement de méthodes et d'outils spécifiques pour l'indexation, la recherche, le filtrage et la fouille des données. En particulier, les fonctions de recherche et de filtrage doivent prendre en compte des requêtes disposant de connaissances incomplètes, imprécises, parfois même erronées sur la structure ou le contenu des documents XML. Ces fonctions doivent par ailleurs maintenir une complexité algorithmique compatible avec la complexité des données et surtout avec leur volume toujours en forte croissance, ceci pour assurer le passage à l'échelle des solutions informatiques. Dans cette thèse, nous étudions des méthodes et développons des outils pour indexer et rechercher des informations multimédia hétérogènes stockées dans des banques de documents XML. Plus précisément, nous abordons la question de la recherche par similarité sur des données composites décrites par des éléments structurels, textuels et séquentiels. En s'appuyant sur la partie structurelle des documents XML, nous avons défini un modèle de représentation, d'indexation et d'interrogation flexible pour des types hétérogènes de données séquentielles. Les principes que nous développons mettent en oeuvre des mécanismes de recherche qui exploitent simultanément les éléments des structures documentaires indexées et les contenus documentaires non structurés. Nous évaluons également l'impact sur la pertinence des résultats retournés par l'introduction de mécanismes d'alignement approximatif des éléments structurels. Nous proposons des algorithmes capables de détecter et de suggérer les « meilleurs points d'entrée » pour accéder directement à l'information recherchée dans un document XML. Finalement, nous étudions l'exploitation d'une architecture matérielle dédiée pour accélérer les traitements les plus coûteux du point de vue de la complexité de notre application de recherche d'information structurée. v

Cette thµese est consacree à l'etude d'abstractions d'ensemble de traces adaptees µa l'analyse statique et aux transformations de programmes. Cette etude a ete menee dans le cadre de l'interpretation abstraite. Dans une premiµere partie, nous proposons un cadre general permettant de definir des analyses effectuant un partitionnement des traces. Cela permet en particulier d'utiliser des proprietes definies par l'histoire des executions, pou ecrire des disjonctions de proprietes abstraites utiles lors de l'analyse statique. Ainsi, nous obtenons des analyses plus efficaces, qui sont non seulement plus precises mais aussi plus rapides. La methode a ete implementee et eprouvee dans l'analyseur de code C Astree, et on obtient d'excellents resultats lors de l'analyse d'applications industrielles de grande taille. La seconde partie est consacree au developpement de methodes permettant d'automatiser le diagnostique des alarmes produites par un analyseur tel qu'Astree. En eff en raison de l'incompletude de l'analyseur, une alarme peut, soit reveler une veritable erreur dans le programme, soit provenir d'une imprecision de l'analyse. Nous proposons tout d'abord d'extraire des slices semantiques, c'est à ire des sous-ensembles de traces du programme, satisfaisant certaines conditions ; cette technique permet de mieux caracteriser le contexte d'une alarme et peut aider, soit àprouver l'alarme fausse, soit à montrer un veritable contexte d'erreur. Ensuite, nous definissons des familles d'analyses de dependances adaptees µa la recherche d'origine de comportements anormaux dans un programme, afin d'aider µa un diagnostique plus efficace des raisons d'une alarme. Les resultats lors de l'implementation d'un prototype sont encourageants. Enfin, dans la troisiµeme partie, nous definissons une formalisation generale de la compilation dans le cadre de l'interpretation abstraite et integrons diverses techniques de compilation certifiee dans ce cadre. Tout d'abord, nous proposons une methode fondee sur la traduction d'invariants obtenus lors d'une analyse du code source et sur la verification independante des invariants traduits. Ensuite, nous formalisons la methode de preuve d'equivalence, qui produit une preuve de correction de la compilation, en prouvant l'equivalence du programme compile et du programme source. Enfin, nous comparons ces methodes du point de vue theorique et µa l'aide de resultats experimentaux.

Nous nous sommes intéressé au problème de décodage des codes de Reed-Muller d'ordre r à travers différents types de canaux et dans différents contextes. Dans notre contexte, le mot du code Reed-Muller bruité est tous simplement une fonction booléenne. Une question naturelle avant de faire du décodage, est de savoir s'il existe ou non au moins un mots de ce code de Reed-Muller d'ordre r qui est à une distance d donnée de notre mot bruité. Ainsi on a développé dans cette thèse de tels testeurs en caractéristique 2. Dans le but d'obtenir des attaques cryptographiques, on a développé des algorithmes adaptatifs de décodage des codes de Reed-Muller d'ordre 1 et 2 en très grande longueur. Une partie application importante est consacrée à l'étude des propriétés statistiques du DES. Enfin une digression est faite sur la construction des courbes modulaires.

La gestion du trafic aerien (air-traffic management, ATM) consiste en une composante predictive (planification du trafic) et en une composante adaptative (controle du trafic). Le but de la composante predictive est de trouver un equilibre entre la demande de l'espace et la capacite disponible. Une fois que les avions ont decolle, la composante adaptative doit les guider en toute securite vers leurs destinations. Des incertitudes, telles que retards ou defaillances techniques, creent des phenomenes d'ecarts entre la composante predictive et adaptative. Cela entraine des problemes de securite ainsi qu'une utilisation sous-optimale de capacite. Meme si les causes majeures des incertitudes sont connues (incertitude de demande, incertitude de capacite, incertitude de gestion de flux), les mecanismes perturbateurs restent inconnus. L'approche de cette these est d'analyser des donnees d'ecoulement de trafic afin d'engendrer de nouvelles hypotheses sur les mecanismes qui causent des ecarts entre la composante predictive et adaptative dans l'ATM. C'est un premier pas pragmatique dans l'analyse d'un phenomene physique. Il est fonde sur le calcul des probabilites et plus precisement sur l'interpretation frequentiste des probabilites. On utilise des techniques d'analyse de donnees multi-variees et des processus ponctuels stochastiques afin d'inferer de nouvelles connaissances sur le phenomene. Nos resultats principaux sont: (i) des ecarts systematiques existent dans tous les secteurs evalues. Leur taille peut etre caracterisee par des distributions de Poisson et on constate une tendance systematique a supprimer le trafic sur des niveaux eleves de planification. C'est un resultat contre-intuitif car l'on s'attend a ce que les differents facteurs d'incertitude s'annullent en moyenne. Ensuite on montre que des perturbations aleatoires d'un processus d'arrivee causent des ecarts systematiques dans deux classes de plan de vol. On conclut que meme si toutes les incertitudes controlables etaient eliminees, des ecarts systematiques entre le nombre planifie et observe de vols apparaisseraient. Ce resultat est utile pour la planification tactique des flux. De nouvelles contraintes pour le probleme de l'allocation de creneaux peuvent etre formulees en identifiant des plans de vol qui sont robustes aux perturbations aleatoires. (ii) on montre que les ecarts se propagent uniquement le long des routes aeriennes. Aucune propagation non-attendue n'est identifiee. Cela indique que les controlleurs aeriens n'utilisent pas systematiquement le re-routage pour compenser les ecarts. On remarque egalement des probabilites de queue elevees et on propose deux (nouveaux) modeles de series chronologiques qui decrivent les caracteristiques du processus de perturbation des plans de vol. Cela indique que les perturbations sont d'une nature heterogene et non-independante. Le resultat est empirique et on affirme que le comportement observe est du a des dependances entre les avions intervenant sur un long-terme. Comme travaux futurs on propose de continuer l'identification des ordonnancements de vol qui absorbent l'impact des incertitudes non-controlables et de developper des modeles statistiques qui expliquent les echantillons long-terme de congestion. Ceci constitue une base pour la quantifiaction de l'impact des decisions locales sur la performance globale du reseau de transport.

Les travaux de cette thèse portent sur la cryptanalyse d'un système de chiffrement simple, mais important : le registre filtré. Ils concernent les deux principales familles d'attaques que sont les attaques algébriques et les attaques probabilistes. Pour les attaques algébriques, il est important de pouvoir calculer efficacement l'immunité algèbrique de la fonction booléenne par laquelle le registre est filtré. Cette quantité est intimement liée au comportement des codes de Reed-Muller sur le canal à effacements et son étude a permis la découverte de plusieurs résultats qui s'expriment naturellement dans le cadre de la théorie des codes correcteurs. Nous avons ainsi construit une nouvelle borne sur la probabilité de pouvoir compenser un nombre d'effacements fixé. Cette borne montre que l'immunité algébrique d'une fonction booléenne aléatoire est presque toujours maximale. Nous avons également explicité une méthode de décodage fondée sur des algorithmes d'algèbre linéaire creuse (comme l'algorithme de Wiedemann) qui donne un des algorithmes les plus efficace pour calculer l'immunité algébrique. Pour les attaques probabilistes, un outil très important est de parvenir à trouver efficacement de nombreux multiples de poids faible du registre à décalage du système. Un nouvel algorithme fondé sur les logarithmes discrets à été proposé. Il est particulièrement interessant pour les multiples de poids 4, améliorant dans de nombreux cas pratiques le meilleur algorithme connu. Ce travail s'est poursuivi par une nouvelle cryptanalyse probabiliste du registre filtré qui utilise ces multiples de poids faible pour reconnaître les entrées nulles de la fonction de filtrage. Cette attaque est l'une des plus efficaces connue à l'heure actuelle.

La vérification des programmes est indispensable pour maintenir un certain niveau de qualité et de fiabilité. Le test est à ce jour le moyen de vérification des logiciels le plus utilisé dans l¤industrie. La programmation par contraintes est vue comme un moyen efficace pour automatiser la génération de données de test. Dans cette thèse nous proposons une modélisation par contraintes de la sémantique du bytecode Java, ainsi qu¤une méthode, basée sur cette modélisation, pour générer automatiquement des données de test. Notre modèle à contraintes de la sémantique d¤un programme en bytecode Java permet de faire des déductions efficaces, y compris en présence de structures de données complexes ou d¤héritage. En particulier, l¤utilisation de variables de type permet de prendre en compte l¤héritage et les appels de méthodes polymorphes. Notre méthode de génération de données de test exploite le modèle à contraintes pour couvrir des instructions particulières du programme sous test. Elle se base sur un parcours en arrière du graphe de flot de contrôle pour énumérer des chemins menant aux instructions cibles. Elle est en particulier adaptée à la couverture d¤instructions non couvertes par les autres méthodes de génération de données de test. Enfin cette méthode est mise en application dans un prototype, JAUT (Java Automatic Unit Testing). Les expériences montrent que le prototype permet d¤augmenter la couverture des instructions obtenue avec les autres outils disponibles.