Pour satisfaire la demande du marché actuel, plusieurs outils commerciaux de vérification formelle sont apparus ces dernières années. Le niveau le plus abstrait de description accepté dans la plupart de ces outils est le niveau appelé transfert de registres, c'est-à-dire une description avec des cycles d'horloge explicitement définis. Pour rester compétitifs, néanmoins, les concepteurs sont obligés d'élever le niveau d'abstraction et commencent à utiliser des outils de synthèse de haut niveau. Cette thèse a pour objet la vérification formelle des résultats de synthèse de haut niveau par rapport à la spécification initiale décrite en VHDL. Nous proposons une méthodologie de vérification qui épouse le flot de conception et consiste en la vérification de deux étapes principales:<br />l'ordonnancement et l'allocation. La vérification de chaque étape est fondée sur un modèle de machine abstraite que nous avons défini: contrairement au modèle de machine d'états finis classique, il réduit<br />considérablement l'espace d'états d'où les registres de la partie opérative sont exclus. En outre, la machine abstraite est similaire aux descriptions VHDL utilisées lors de la synthèse et offre, par conséquent, un niveau d'abstraction plus élevé de représentation des<br />circuits. La preuve d'équivalence entre la machine abstraite et la machine d'états finis classique justifie la première et constitue une des contributions théoriques de la thèse. Un prototype d'outil basé sur la simulation symbolique a été développé et exécuté sur des benchmarks de la synthèse comportementale. La thèse<br />s'achève sur les problèmes ouverts et les axes de recherche à explorer.

Cette thèse se place dans le cadre de l'apprentissage non supervisé, qui consiste à former différents groupes à partir d'un ensemble de données, de telle manière que les données considérées comme les plus similaires soient associées au même groupe et qu'au contraire les données considérées comme différentes se retrouvent dans des groupes distincts, permettant ainsi d'extraire de la connaissance à partir de ces données. Nous proposons d'abord deux nouvelles méthodes qui prennent en compte le contexte dans lequel les groupes sont créés, c'est-à-dire le fait que les caractéristiques des différents groupes peuvent être définies sur différents sous-ensembles des attributs décrivant les données. Dans la mise en oeuvre de ces méthodes, nous avons également considéré les problématiques de la minimisation du nombre de connaissances a priori requises de la part de l'utilisateur et de la présentation des résultats sous forme compréhensible et visuelle. Nous présentons ensuite plusieurs extensions possibles de ces méthodes, dans le cadre de l'apprentissage supervisé puis face à des données semi-structurées représentées sous forme arborescente. Différentes expérimentations sur données artificielles puis sur données réelles sont présentées qui mettent en avant l'intérêt de ces méthodes. Le problème de l'évaluation des résultats produits par une méthode d'apprentissage non supervisé, et de la comparaison de telles méthodes, restant aujourd'hui un problème ouvert, nous proposons enfin une nouvelle méthode d'évaluation plus objective et quantitative que celles utilisées traditionnellement, et dont la pertinence est montrée expérimentalement.

.

L'alignement multiple de réseaux biologiques a pour objectif d'extraire des informations fonctionnelles des données haut-débit représentées sous forme de graphes. Ceci concerne, par exemple, les données d'interaction protéines-protéines, les données métaboliques ou même les données génomiques. Dans un premier temps nous proposons un formalisme précis, qui s'appuie sur les notions de graphe de données stratifié et de multigraphe d'alignement (MGA), et qui définit les alignements multiples locaux en autorisant notamment un réglage de la conservation de la topologie entre les réseaux. Nous présentons ensuite un algorithme de construction et partitionnement ''à la volée" du MGA, qui permet de traiter de façon efficace l'alignement de nombreux réseaux biologiques. Dans un second temps, nous étendons le formalisme pour parvenir à retrouver des alignements - que nous qualifions de ''partiels" - lorsqu'il y a des noeuds manquants sur certains réseaux. Nous détaillons les algorithmes associés, puis nous proposons différentes améliorations, et des variantes adaptées à des problèmes biologiques particuliers.

This dissertation presents a logical investigation of epistemic protocols, focussing on protocol-dynamics, epistemic modelling, and epistemic model checking. In Part I, we introduce logics for specifying epistemic protocols including their goals and their dynamics. Chapter 3 departures from the existing discussions about protocols in the field of Dynamic Epistemic Logic by introducing a logic which can specify both the epistemic protocols and their goals within the language. We formalize the verification problem of epistemic protocols under the assumption of meta knowl- edge about the intended goal. The subtlety of this verification problem is discussed in theory and examples. In Chapter 4, we address the question: “How can people get to know a protocol?” For this, we develop logics which are convenient for reasoning about knowledge change and protocol change. With various protocol-changing op- erators we can handle the dynamics of protocols and formalize how actions acquire new meanings as a result of protocol change. We show that all the three logics we introduced can be translated back to Propositional Dynamic Logic (PDL) on standard Kripke models, thus the techniques of modelling and model checking we develop in the other parts of the dissertation can be applied to these logics. In Part II we address the issue of epistemic modelling, in order to study model checking for the logics introduced in Part I. In Chapter 5 we propose new compo- sition operations on static and event models with arbitrary vocabularies, aiming at a compositional method for generating initial epistemic models. We prove decom- position theorems w.r.t. our new operator and demonstrate the use of our methods by various examples. Chapter 6 reports results on counting the number of different models given a finite set of initial assumptions. Restricted to image-finite models, we show that if a modal μ-calculus formula has an infinite model modulo bisimulation thenithas2א0 (cardinalityofthecontinuum)differentmodelsmodulobisimulation. On the other hand, if it does not have any infinite models modulo bisimulation then all its models can be represented in a normal form. Part III introduces abstraction techniques that are particularly useful on making the model checking more efficient. A 3-valued semantics for Public Announcement Logic is defined and studied in Chapter 7 to facilitate abstractions of models. We define a relation with vocabulary and agent mappings between concrete models and their abstractions, thus making it possible to also abstract the signatures of models. We then give a logical characterization of this abstraction relation thus showing it is safe to check properties on the abstract model instead of the original concrete model. Chapter 8 studies the PDL on so-called accelerated Kripke models where the transitions in the models are labelled by regular expressions in order to obtain informative ab- stractions. By making use of a technique of regular expression rewriting, we analyse the complexity of the model checking and satisfiability problems of this logic and give a complete axiomatization. In Part IV (Chapter 9) we survey the epistemic approaches to security protocol verification. We summarize the most important techniques in the Epistemic Tempo- ral Logic and Dynamic Epistemic Logic approaches to security protocol verification, and compare these two approaches in term of convenience. We argue that some se- curity properties can only be faithfully formalized by temporal logic with knowledge operators, but are not expressible by standard temporal logic. However, we need to pay some cost in model checking complexity, in exchange to the expressiveness we gain.

.

Most of our daily activities are carried out over the Internet, from file-sharing and social networking to home banking, online-teaching and online-blogging. Considering file-sharing as one of Internet top activities, different architectures have been proposed, designed and implemented, leading to a wide set of file-sharing networks with different performances and goals. This digital society enables as well users' profiling. As Internet users surf the World Wide Web, every sent or received packet passes through several intermediate nodes until they reach their intended destination. So, an observer will be able to determine where a packet comes from and where it goes to, to monitor and to profile users' online activities by identifying to which server they are connected or how long their sessions last. Meanwhile, anonymous communications have been significantly developed to allow users to carry out their online activities without necessarily revealing their real identity. Our contribution is twofold. On the one hand, we consider hybrid file-sharing environments, with a special focus on widely deployed real-world networks and targeting two defined goals. The first goal is to improve content indexation in the BitTorrent file-sharing environment, enabling BitTorrent content to be indexed in the Kad distributed has table and leading to a more robust BitTorrent system. The second goal is to improve content availability in the I2P file-sharing environment. We allow I2P users to anonymously access public BitTorrent content and we obtain a fully anonymous file-sharing environment, including anonymous content indexation and anonymous content distribution. On the other hand, we focus on the understanding of anonymous environments through extensive monitoring. We characterise the I2P network, targeting the entire anonymous environment and its anonymous services. We consider different aspects of the network, such as the number of users, their characteristics as well as the number of anonymous services available. Through long-term measurements on the network and along with different correlation analyses, we are able to characterise a small group of users using a specific anonymous service, such as the users from a particular city performing anonymous file-sharing.

Malgré sa complexité de résolution, le problème de SATisfaisabilité est une excellente et compétitive approche pour résoudre un large éventail de problèmes. Cela génère une forte demande pour une résolution de SAT haute performance de la part des industriels. Au fil du temps, de nombreuses approches et optimisations différentes ont été développées pour résoudre le problème plus efficacement. Ces innovations ont été faites sans prendre en compte le développement des micro processeurs actuels qui voient le nombre de leur cœurs de calcul augmenter. Cette thèse présente un nouveau type d'algorithme parallèle basé sur une forte collaboration où un processus riche est en charge de l'évaluation de l'arbre de recherche et où des processus pauvres fournissent des informations partielles ou globales, heuristiques ou logiques afin de simplifier la tâche du riche. Pour concrétiser ce solveur et le rendre efficace, nous avons étendu la notion de chemin de guidage à celle d'arbre de guidage. L'arbre de recherche est totalement partagé en mémoire centrale et tous les processeurs peuvent y travailler en même temps. Ce nouveau solveur est appelé MTSS pour Multi-Threaded SAT Solver. De plus, nous avons implémenté une tâche pour les processus riche et pauvres qui leur permet d'exécuter un solveur SAT externe, et cela, avec ou sans échange de lemmes afin de paralléliser tous types de solveurs (dédiés aux formules industrielles ou aléatoires). Ce nouvel environnement facilite la parallélisation des futures implémentations pour SAT. Quelques exemples et expérimentations, avec ou sans échange de lemmes, de parallélisation de solveurs externes sont présentées, mais aussi des résultats sur les performances de MTSS. Il est intéressant de noter que certaines accélérations sont super linéaires.

Cette thèse s'inscrit dans une étude sur la modélisation d'une tête parlante destinée à améliorer l'intelligibilité du message transmis. A partir du signal sonore notre but est d'animer un visage synthétique afin par exemple de permettre la lecture labiale. Les mouvements des lèvres et de la mâchoire dépendent fortement du phénomène de coarticulation qui peut être anticipatif ou rétentif (progressif). Si beaucoup s'accordent à penser que rétentif est essentiellement inertiel, de nombreux modèle théoriques et expérimentaux rentrent en concurrence au sujet de l'anticipation. Afin d'essayer de clarifier ce phénomène, nous avons enregistré deux corpus audiovisuels (mono et multilocuteur) nous permettant d'obtenir des informations tridimensionnelles sur un ensemble de marqueurs peints sur le visage des locuteurs. Quatre paramètres articulatoires liés aux lèvres et à la mâchoire ont retenu notre attention. Après avoir analysé les variations intra et interlocuteur, nous avons défini un algorithme de prédiction de la coarticulatìon anticipatrice basé sur des règles phonétiques et prenant en considération l'interaction entre les articulateurs. Nous avons ensuite proposé une technique pour synthétiser les mouvements articulatoires à partir de l'algorithme de prédiction précédent. Notre solution permet d'estimer avec précision les mouvements des lèvres et de le mâchoire de n'importe quelle séquence en nous basant sur les informations contenues dans un corpus monolocuteur. Le principe de base est la concaténation de séquences élémentaires de type VC...CV qui sont soit extraites du corpus, soit obtenues par complétion. Une des originalités de notre méthode est le choix des sigmoïdes pour caractériser les mouvements articulatoires. Ceci a 1'avantage de réduire considérablement la taille du modèle construit et permet de s'adapter facilement à des vitesses d'é1ocution ou des stratégies articulatoires particulières. Un autre point fort de notre méthode est de prendre en considération à la fois l'effet paradigmatique qui correspond aux caractéristiques intrinsèques des sons, mais aussi l'effet syntagmatique qui permet de conserver les contrastes entre les sons dans un énoncé. Afin d'estimer la qualité de notre synthèse coarticulatoire, nous avons ensuite mesuré les différences entre les signaux réels et les signaux synthétisés sur 1'ensemble des phrases de notre corpus. Nous avons également comparé nos résultats avec ceux obtenus après synthèse avec la technique de prédiction de la coarticulatíon de Cohen et Massaro qui avait obtenu les meilleurs scores statistiques selon une ancienne étude comparative. Si la méthode de Cohen et Massaro obtient globalement de meilleurs résultats que notre solution, nous avons montré que ce n'est pas le cas pour toutes les séquences. En particulier, notre synthèse est meilleure pour les VCCV où l'anticipation est davantage marquée.

Les environnements logiciels distribués sont de plus en plus complexes et difficiles à administrer car ils sont composés d'applications patrimoniales avec des interfaces d'administration spécifiques. De plus, les tâches d'administration menées par un humain sont sujettes à erreur et à un manque de réactivité. Ceci est particulièrement visible sur les architectures moyennement ou grandement distribuées. Pour résoudre ce problème, nous étudions la conception et l'implantation d'un système d'administration autonome. Le principe est d'encapsuler un morceau de logiciel patrimonial dans un composant puis d'administrer l'architecture patrimoniale comme une architecture à composant. Cependant, nous avons observé que les interfaces d'un modèle à composant sont de trop bas niveau et difficiles à utiliser. Nous introduisons donc des formalismes de haut niveau pour spécifier le déploiement et les politiques de reconfiguration. Cette thèse décrit ces contributions qui sont intégrées dans un prototype de système autonome baptisé TUNe.