Ce travail s'inscrit dans le cadre des recherches menées autour de l'analyse et la visualisation des logiciels, notamment les logiciels à objets, et en particulier Java. Très brièvement, on peut dire que le but de cette thèse revient à tenter de répondre à une question fondamentale: comment faire pour faciliter la compréhension du logiciel par ses développeurs et concepteurs ? Ce travail de recherche est basé en grande partie sur deux axes principaux. Le premier consiste à analyser l'exécution des programmes, non seulement au niveau de la méthode, mais bien au niveau du bloc de base, pour recueillir des données d'exécutions avec un maximum de précision comme par exemple les différents types d'instances sur les sites d'appels. Le second axe considère l'utilisation des informations apportées par notre analyse dynamique de l'exécution pour permettre la visualisation de ces données. En effet, ces informations offrent des détails intéressants sur le fonctionnement du programme et aident à expliquer le comportement du logiciel, aussi bien pour déceler les problèmes de performance que les problèmes de codages. Nous proposons une technique souple et efficace qui effectue une analyse dynamique de l'exécution de programmes Java. Nous introduisons ainsi une nouvelle technique et un nouvel outil permettant de recueillir des informations encore non proposées par d'autres analyseurs. Cette approche trace l'exécution précise des programmes tout en ayant une baisse des performances d'exécution acceptable, laissant le programme final utilisable. De plus, nous proposons et expérimentons une approche basé sur la visualisation des relations au sein d'une représentation du logiciel par une métaphore de ville. Nous introduisons une nouvelle technique de représentation des relations nommée "3D Hierarchical Edge Bundles" qui est basée sur une représentation 2D existante nommée "Hierarchical Edge Bundles". Cette approche conserve la puissance de visualisation du logiciel offerte par la métaphore de la ville tout en ajoutant la représentation des relations, et cela d'une façon lisible. Ces travaux sont validés entre autres par le développement d'un outil d'analyse nommé VITRAIL JBInsTrace et d'un outil de visualisation nommé VITRAIL Visualizer. Ces outils sont la base de nos recherche actuelles sur l'étude de l'exécution des programmes objets.

Les architectures multicœurs changent notre façon d'écrire des programmes. L'écriture de programmes concurrents est bien connue pour être difficile. Traditionnellement, l'utilisation de verrous (locks) permettant au code de s'exécuter en exclusion mutuelle, a été l'abstraction la plus largement utilisée pour l'écriture des programmes concurrents. Malheureusement, il est difficile d'écrire des programmes concurrents efficaces et corrects reposant sur des verrous. En outre, les verrous présentent d'autres problèmes, notamment celui du passage à l'échelle. Le concept de mémoire transactionnelle a été proposé comme une solution à ces difficultés. Les transactions peuvent être considérées comme une abstraction de haut niveau, ou une méthodologie pour l'écriture de programmes concurrents, ce qui permet au programmeur de pouvoir déclarer des sections de code devant être exécutés de façon atomique, sans avoir à se soucier des détails de synchronisation. Malheureusement, bien qu'assurément plus facile à utiliser que les verrous, la mémoire transactionnelle souffre encore de problèmes de performance et de facilité d'utilisation. En fait, de nombreux concepts relatifs à l'utilisation et à la sémantique des transactions n'ont pas encore des normes convenues. Cette thèse propose de nouvelles solutions permettant de faciliter l'utilisation des mémoires transactionellles. La thèse débute par un chapitre qui donne un bref aperçu de la mémoire transactionnelle logicielle (STM) ainsi qu'une discussion sur le problème de la facilité d'utilisation. Les contributions à la recherche sont ensuite divisées en quatre chapitres principaux, chacun proposant une approche différente afin de rendre les STMs plus facile à utiliser.

Lors du développement des applications ubiquitaires, il est essentiel de définir des politiques de sécurité et de développerdes mécanismes de sécurité pour assurer la confidentialité et l'intégrité des applications. De nombreux langages de spécification de politiques se concentrent uniquement sur leur puissance d'expression. Les défis émergents dans les systèmes ubiquitaires ne peuvent pas être résolus par ces approches. Par exemple, la sensibilité au contexte est un élément central des systèmes ubiquitaires. Les approches existantes tiennent rarement compte des informations contextuelles dans leurs langages. Cette thèse propose une approche générative pour spécifier et implanter les politiques de sécurité dans les applications ubiquitaires. Pour définir une politique de sécurité, nous proposons un langage de spécification qui tient compte des informations contextuelles. Il permet aux développeurs de spécifier les règles de la politique et les entités requises (e.g. la description spatiale, les rôles, le contexte). Les politiques sont implémentés par des systèmes de réécriture, ce qui offre une grande puissance de vérification. Pour appliquer une politique, nous proposons une architecture qui intègre les concepts importants des politiques de sécurité (sujet, contexte, objet) dans des applications ubiquitaires. Pour mettre en oeuvre notre approche, nous avons enrichi une approche existante pour le développement des applications ubiquitaires. La spécification de la politique de sécurité et la description de l'application ubiquitaire enrichie sont utilisées pour générer un canevas de programmation qui facilite l'implémentation des mécanismes de sécurité, tout en séparant les aspects sécurités de la logique applicative.

Si la communauté internationale de géométrie algorithmique a souvent<br />la tentation de s'engouffrer dans des recherches essentiellement<br />théoriques, et en particulier combinatoires, la grande originalité des<br />travaux à l'INRIA résidait déjà à l'époque de mes débuts dans le<br />souci de leur validation expérimentale et de leur applicabilité. <br /><br />Le domaine a suivi globalement une évolution dans cette direction,<br />en particulier grâce à l'``Impact Task Force Report''. Notre intérêt pour le transfert technologique et<br />industriel, ainsi que pour l'établissement d'une plateforme pour la<br />recherche, a pris pendant ce temps une tournure encore plus concrète<br />avec notre implication très forte dans le projet CGAL<br />dont notre équipe est l'un des moteurs.<br /><br />Ce document prend le parti de présenter les travaux sous l'angle de<br />cette préoccupation pratique.<br />Il comporte deux chapitres principaux : le premier rassemble<br />des travaux sur les triangulations, le second présente des travaux sur<br />les objets courbes. Ces deux chapitres se concluent par un ensemble de<br />directions ouvertes. Le troisième chapitre survole rapidement d'autres<br />résultats.

Dans cette thèse nous proposons une approche et des outils pour faciliter la mise au point et l'utilisation de techniques d'interaction avancées au sein d'applications graphiques interactives. Nous proposons de résoudre les exigences antithétiques de la réutilisation, nécessaire à la factorisation des efforts, et de l'innovation, nécessaire à l'adaptation à de nouveaux contextes, en fournissant une pyramide d'abstractions de divers niveaux permettant leur recombinaison pour s'adapter finement aux besoins spécifiques à chaque usage. Nous proposons également d'intégrer aux langages impératifs une structure de contrôle basée sur un formalisme de machines à états hiérarchiques pour faciliter la programmation de comportements dynamiques et faire des interactions des objets à part entière du vocabulaire des programmeurs.<br /><br />Nous montrons par des exemples comme ces éléments permettent la reproduction de l'état de l'art des interactions, tant standards qu'avancées, et la mise au point de techniques d'interaction originales et performantes. Nous présentons en particulier la réalisation d'applications graphiques interactives utilisant une architecture distribuée permettant de localiser l'interaction sur le système local et de reporter le noyau fonctionnel sur une machine distante. Nous présentons enfin une technique d'interaction avancée, le pointage sémantique, qui facilite la tâche élémentaire de sélection par pointage en permettant d'utiliser deux tailles pour les objets de l'interface, l'une choisie en fonction des informations qu'ils présentent, l'autre en fonction de leur importance pour la manipulation.

Cette thèse adresse la problématique de la construction des intergiciels hautement adaptables. Ces intergiciels se caractérisent par une grande diversité des fonctionnalités fournies. Dans le domaine du transactionnel, cette diversité concerne non seulement les modèles de transactions, les protocoles de contrôle de concurrence et de reprise après défaillance, mais aussi les normes et les standards d'intégration. Notre proposition consiste à définir un canevas intergiciel capitalisant la diversité du domaine transactionnel, et permettant de construire des services de transactions hautement adaptables. Ce type de services requiert la mise en place d'une démarche de construction à granularité extrêmement fine afin de pouvoir adapter les nombreuses caractéristiques de l'intergiciel.<br /><br />Nous proposons donc de compléter l'approche issue des exogiciels avec quatre nouveaux éléments. Ainsi, nous définissons le modèle de programmation Fraclet à base d'annotations pour favoriser la programmation des abstractions fonctionnelles de l'intergiciel. Nous proposons ensuite un langage de description et de vérification de motifs d'architecture pour fiabiliser la modélisation des abstractions architecturales. Ces deux premiers éléments servent à la conception d'un canevas intergiciel à base de composants utilisant les motifs de conception comme structure architecturale extensible. Enfin, nous décrivons les configurations possibles en utilisant différents modèles de haut niveau dédiés aux caractéristiques de l'intergiciel. Nous illustrons ces concepts en présentant GoTM, un canevas intergiciel à composants pour la construction de services de transactions hautement adaptables.<br /><br />Notre approche est validée au travers de trois expériences originales. Tout d'abord, nous proposons de faciliter l'intégration des services de transactions dans les plates-formes intergicielles par la définition de politiques de démarcation transactionnelle indépendantes de la plate-forme et du type de service intégré. Ensuite, nous définissons un service de transactions composant plusieurs personnalités simultanément pour faciliter l'interopérabilité transactionnelle d'applications hétérogènes. Enfin, nous sommes en mesure de sélectionner différents protocoles de validation à deux phases pour optimiser le temps d'exécution des transactions face aux changements des conditions d'exécution de l'application.

La réduction d'énergie apparaît comme un besoin crucial dans les télécommunications modernes, tant au niveau des terminaux que des réseaux. Dans les réseaux modernes, un terminal peut se connecter à Internet via d'autres terminaux ou infrastructures à proximité, appelés relais. Bien que les relais offrent une solution intéressante pour limiter la puissance de transmission des terminaux, il n'est pas simple de garantir une réduction de la consommation d'énergie globale. Il devient alors nécessaire de développer des outils pour évaluer et quantifier la consommation d'énergie. Un terminal moderne dispose de plusieurs interfaces de communications, ce qui lui permet d'utiliser plusieurs standards. Sachant qu'un standard dispose de différents modes de communications, un terminal est multi-mode lorsqu'il possède cette capacité à communiquer sur les différents standards et modes disponibles. Nous nous sommes alors intéressés à l'utilisation du multi-mode dans le cadre des relais. Nous nous positionnons dans un contexte de radio logicielle, où la couche physique d'un terminal est représentée par des blocs programmables, ce qui facilite l'implémentation du multi-mode. Afin d'estimer la consommation d'énergie d'une radio logicielle, nous avons calculé la complexité algorithmique pour les couches physiques du 802.11g (ou Wi-Fi), de l'UMTS et du 802.15.4 (ou Zigbee). Dans cette thèse, nous avons développé des outils nous permettant d'évaluer l'intérêt d'un relais multi-mode dans la réduction d'énergie. Nous avons proposé un modèle d'énergie réaliste pour le multi-mode, qui prend en compte la couche d'accès au medium des protocoles considérés. Dans un but de réalisme accru, nous avons implémenté le multi-mode au sein de WSNet, un simulateur réseau précis, grâce auquel nous avons déterminé les paramètres ayant un impact sur la consommation d'énergie. Puis, nous avons proposé et validé des stratégies permettant de minimiser l'influence de ces paramètres.

Le concept de processeur multicœurs constitue le facteur dominant pour offrir des hautes performances aux applications parallèles. Afin de développer des applications parallèles capable de tirer profit de ces plate-formes, les développeurs doivent prendre en compte plusieurs aspects, allant de l'architecture aux caractéristiques propres à l'application. Dans ce contexte, la Mémoire Transactionnelle (Transactional Memory - TM) apparaît comme une alternative intéressante à la synchronisation basée sur les verrous pour ces plates-formes. Elle permet aux programmeurs d'écrire du code parallèle encapsulé dans des transactions, offrant des garanties comme l'atomicité et l'isolement. Lors de l'exécution, les opérations sont exécutées spéculativement et les conflits sont résolus par ré-exécution des transactions en conflit. Bien que le modèle de TM ait pour but de simplifier la programmation concurrente, les meilleures performances ne pourront être obtenues que si l'exécutif est capable de s'adapter aux caractéristiques des applications et de la plate-forme. Les contributions de cette thèse concernent l'analyse et l'amélioration des performances des applications basées sur la Mémoire Transactionnelle Logicielle (Software Transactional Memory - STM) pour des plates-formes multicœurs. Dans un premier temps, nous montrons que le modèle de TM et ses performances sont difficiles à analyser. Pour s'attaquer à ce problème, nous proposons un mécanisme de traçage générique et portable qui permet de récupérer des événements spécifiques à la TM afin de mieux analyser les performances des applications. Par exemple, les données tracées peuvent être utilisées pour détecter si l'application présente des points de contention ou si cette contention est répartie sur toute l'exécution. Notre approche peut être utilisée sur différentes applications et systèmes STM sans modifier leurs codes sources. Ensuite, nous abordons l'amélioration des performances des applications sur des plate-formes multicœurs. Nous soulignons que le placement des threads (thread mapping) est très important et peut améliorer considérablement les performances globales obtenues. Pour faire face à la grande diversité des applications, des systèmes STM et des plates-formes, nous proposons une approche basée sur l'Apprentissage Automatique (Machine Learning) pour prédire automatiquement les stratégies de placement de threads appropriées pour les applications de TM. Au cours d'une phase d'apprentissage préliminaire, nous construisons les profiles des applications s'exécutant sur différents systèmes STM pour obtenir un prédicteur. Nous utilisons ensuite ce prédicteur pour placer les threads de façon statique ou dynamique dans un système STM récent. Finalement, nous effectuons une évaluation expérimentale et nous montrons que l'approche statique est suffisamment précise et améliore les performances d'un ensemble d'applications d'un maximum de 18%. En ce qui concerne l'approche dynamique, nous montrons que l'on peut détecter des changements de phase d'exécution des applications composées des diverses charges de travail, en prévoyant une stratégie de placement appropriée pour chaque phase. Sur ces applications, nous avons obtenu des améliorations de performances d'un maximum de 31% par rapport à la meilleure stratégie statique.

L’existence de plusieurs copies d’un même fragment de code (nommées des clones dans lalittérature) dans un logiciel peut compliquer sa maintenance et son évolution. La duplication decode peut poser des problèmes de consistance, notamment lors de la propagation de correction debogues. La détection de clones est par conséquent un enjeu important pour préserver et améliorerla qualité logicielle, propriété primordiale pour le succès d’un logiciel.L’objectif général de cette thèse est de contribuer à l’usage des détecteurs de clones dans destâches de maintenance logicielle. Nous avons centré nos contributions sur deux axes de recherche.Premièrement, la méthodologie pour comparer et évaluer les détecteurs de clones, i.e. les benchmarksde clones. Nous avons empiriquement évalué un benchmark de clones et avons montré queles résultats dérivés de ce dernier n’étaient pas fiables. Nous avons également identifié des recommandationspour fiabiliser la construction de benchmarks de clones. Deuxièmement, la spécialisationdes détecteurs de clones dans des tâches de maintenance logicielle.Nous avons développé uneapproche spécialisée dans un langage et une tâche (la réingénierie) qui permet aux développeursd’identifier et de supprimer la duplication de code de leurs logiciels. Nous avons mené des étudesde cas avec des experts du domaine pour évaluer notre approche. / The existence of several copies of a same code fragment—called code clones in the literature—in a software can complicate its maintenance and evolution. Code duplication can lead to consistencyproblems, especially during bug fixes propagation. Code clone detection is therefore a majorconcern to maintain and improve software quality, which is an essential property for a software’ssuccess.The general objective of this thesis is to contribute to the use of code clone detection in softwaremaintenance tasks. We chose to focus our contributions on two research topics. Firstly, themethodology to compare and assess code clone detectors, i.e. clone benchmarks. We perform anempirical assessment of a clone benchmark and we found that results derived from this latter arenot reliable. We also identified recommendations to construct more reliable clone benchmarks.Secondly, the adaptation of code clone detectors in software maintenance tasks. We developed aspecialized approach in one language and one task—refactoring—allowing developers to identifyand remove code duplication in their softwares. We conducted case studies with domain experts toevaluate our approach.

Dans cette thèse nous nous intéressons à intégrer dans la distribution Linux produite par Mandriva une assurance qualité permettant de proposer des garanties de propriétés sur le code exécuté. Le processus de création d’une distribution implique l’utilisation de logiciels de provenances diverses pour proposer un assemblage cohérent et présentant une valeur ajoutée pour l’utilisateur. Ceci engendre une moindre maîtrise potentielle sur le code. Un audit manuel permet de s’assurer que celui-Ci présente de bonnes propriétés, par exemple, en matière de sécurité. Le nombre croissant de composants à intégrer, et la croissance de la quantité de code de chacun amènent à avoir besoin d’outils pour permettre une assurance qualité. Après une étude de la distribution nous choisissons de nous concentrer sur un paquet critique, le noyau Linux : nous proposons un état de l’art des méthodes de vérifications appliquées à ce contexte particulier, et identifions le besoin d’améliorer la compréhension de la structure du code source, la question de l’explosion combinatoire et le manque d’intégration des outils d’analyse de l’état de l’art. Pour répondre à ces besoins nous proposons une représentation du code source sous la forme d’un graphe, et l’utilisons pour aider à la documentation et à la compréhension de l’architecture du code. Des méthodes de détection de communautés sont évaluées sur ce cas pour répondre au besoin de l’explosion combinatoire. Enfin nous proposons une architecture intégrée dans le système de construction de la distribution permettant d’intégrer des outils d’analyse et de vérification de code. / In this thesis we are interested in integrating to the Linux distribution produced by Mandriva quality assurance level that allows ensuring user-Defined properties on the source code used. The core work of a distribution and its producer is to create a meaningful aggregate from software available. Those softwares are free and open source, hence it is possible to adapt it to improve end user’s experience. Hence, there is less control over the source code. Manual audit can of course be used to make sure it has good properties. Examples of such properties are often referring to security, but one could think of others. However, more and more software are getting integrated into distributions and each is showing an increase in source code volume: tools are needed to make quality assurance achievable. We start by providing a study of the distribution itself to document the current status. We use it to select some packages that we consider critical, and for which we can improve things with the condition that packages which are similar enough to the rest of the distribution will be considered first. This leads us to concentrating on the Linux kernel: we provide a state of the art overview of code verification applied to this piece of the distribution. We identify a need for a better understanding of the structure of the source code. To address those needs we propose to use a graph as a representation of the source code and use it to help document and understand its structure. Specifically we study applying some state of the art community detection algorithm to help handle the combinatory explosion. We also propose a distribution’s build system-Integrated architecture for executing, collecting and handling the analysis of data produced by verifications tools.