L'analyse des systèmes communiquant par file a fait l'objet d'études scientifiques nombreuses mais qui n'ont pu offrir des solutions totalement satisfaisantes. Nous proposons d'aborder ce problème dans le cadre de l'interprétation abstraite, en définissant des treillis abstraits adaptés à ce type de systèmes. Nous considérons d'abord le cas où les messages échangés sont assimilables à un alphabet fini, puis nous nous attaquons au cas, plus difficile, des messages portant des valeurs entières ou réelles. Ce problème nous amène à définir et à étudier un nouveau type d'automate, les automates de treillis. Ces automates de treillis peuvent également être utilisés pour l'analyses des programmes utilisant une pile d'appels.

Le but de cette thèse est de présenter une analyse statique générique pour des programmes multitâche écrits en Java.<br />Les programmes multitâche exécutent plusieurs tâches en parallèle. Ces tâches communiquent implicitement par le biais de la mémoire partagée et elles se synchonisent sur des moniteurs (les primitives wait-notify, etc..). Il y a quelques années, les architectures avec double processeurs ont commencé à être disponibles sur le marché à petit prix. Aujourd'hui, presque tous les ordinateurs ont au moins deux noyaux, la tendance actuelle du marché étant de mettre de plus en plus de processeurs par puce. Cette révolution amène également de nouveaux défis en matière de programmation, car elle demande aux développeurs d'implanter des programmes multitâche. Le multitâche est supporté en natif par la plupart des langages de programmation courants, comme Java et C#.<br />Le but de l'analyse statique est de calculer des informations sur le comportement d'un programme, de manière conservative et automatique. Une application de l'analyse statique est le développement d'outils qui aident au débogage des programmes. Plusieurs méthodes d'analyse statique ont été proposées. Nous suivrons le cadre de l'interprétation abstraite, une théorie mathématique permettant de définir des approximations correctes de sémantiques de programmes. Cette méthode a déjà été utilisée pour un large spectre de langages de programmation.<br />L'idée fondamentale des analyseurs statiques génériques est de développer un outils qui puissent être interfacé avec différents domaines numériques et différentes propriétés. Pendant ces dernières années, beaucoup de travaux se sont attaqués à cet enjeu, et ils ont été appliqué avec succès pour déboguer des logiciels industriels. La force de ces analyseurs réside dans le fait qu'une grande partie de l'analyse peut être réutilisée pour vérifier plusieurs propriétés. L'utilisation de différents domaines numériques permet le développement d'analyses plus rapides mais moins précises, ou plus lentes mais plus précises.<br /><br />Dans cette thèse, nous présentons la conception d'un analyseur générique pour des programmes multitâche. Avant tout, nous définissons le modèle mémoire, appelé happens-before memory model. Puis, nous approximons ce modéle mémoire en une semantique calculable. Les modéles mémoire définissent les comportements autorisés pendant l'exé-cution d'un programme multitâche. Commençant par la définition (informelle) de ce modèle mémoire particulier, nous définissons une sémantique qui construit toutes les exécutions finies selon ce modèle mémoire. Une exécution d'un programme multitâche est décrite par une function qui associe les tâches à des séquences (ou traces) d'états. Nous montrons comment concevoir une sémantique abstraite calculable, et nous montrons formellement la correction des résultat de cette analyse.<br />Ensuite, nous définissons et approximons une nouvelle propriété qui porte sur les comportements non-déterministes causés par le multitâche, c'est à dire aux entrelacements arbitraires pendant l'exécution de differentes instructions de lecture. Avant tout, le non déterminisme d'un programme multitâche se définit par une différence entre plusieurs exécutions. Si deux exécutions engendrent des comportements différents dus au valeurs qui sont lues ou écrites en mémoire partagée, alors le programme est non déterministe. Nous approximons cette propriété en deux étapes: dans un premier temps, nous regroupons, pour chaque tâche, la valeur (abstraite) qui peut être écrite dans la mémoire partagée à un point de programme donné. Dans un deuxième temps, nous résumons toutes les valeurs pouvant être écrites en parallèle, tout en nous rapellant l'ensemble des tâches qui pourraient les avoir écrites. à un premier niveau d'approximation, nous introduisons un nouveau concept de déterminisme faible. Nous proposons par ailleurs d'autres manière affaiblir la propriété de déterminisme, par exemple par projection des traces et des états, puis nous définissons une hierarchie globale de ces affaiblissements. Nous étudions aussi comment la présence de conflit sur les accès des données peut affecter le déterminisme du programme.<br />Nous appliquons ce cadre de travail théorique à Java. En particulier, nous définissons une sémantique du language objet de Java, selon sa spécification. Ensuite, nous approximons cette sémantique afin de garder uniquement l'information qui est nécessaire pour l'analyse des programmes multitâche. Le cœur de cette abstraction est une analyse d'alias qui approxime les références afin d'identifier les tâches, de vérifier les accès en mémoire partagée, et de détecter quand deux tâches ont un moniteur commun afin d'en déduire quelles parties du code ne peuvent pas être éxécutées en parallèle.<br />L'analyseur générique qui est décrit ci-dessus a été entierement implanté, dans un outils appelé Checkmate. Checkmate est ainsi le premier analyseur générique pour des programmes multitâche écrits en Java. Des résultats expérimentaux sont donnés et analysés en détails. En particulier, nous étudions la précision de l'analyse lorsqu'elle est appliquée à des schémas courants de la programmation concurrente, ainsi qu'à d'autres exemples. Nous observons également les performances de l'analyse lorsqu'elle est appliquée à une application incrémentale, ainsi qu'à des exemples de références bien connus.<br />Une autre contribution de cette thèse est l'extension d'un analyseur générique existant qui s'appelle Clousot et qui permet de vérifier le non débordement des mémoires tampons. Il s'avère que cette analyse passe à l'échelle des programmes industriels et qu'elle est précise. En résumé, nous présentons une application d'un analyseur statique générique industriel existant pour détecter et prouver une propriété présentant un intérêt pratique, ce qui montre la puissance de cette approche dans le développement d'outils qui soient utiles pour les développeurs.

Cette these presente un ensemble de techniques qui permettent l'optimisation des performances des systèmes reseaux modernes. Ces techniques reposent sur l'analyse et la transformation des programmes impliquées dans la mise en oeuvre des protocoles reseaux. La première de ces techniques fait appel à la spécialisation de programmes pour optimiser des piles de protocoles réseaux. La deuxième, que nous avons nommée spécialisation distante, permet à des systèmes embarqués limités en ressources de bénéficier de la spécialisation de programmes en déportant à travers le réseau les opérations de spécialisation à une machine distante moins limitée. La troisième propose un nouvel allocateur de mémoire qui optimise l'utilisation des caches matériels faite par un serveur réseau. Enfin, la quatrième technique utilise l'analyse de programmes statiques pour intégrer l'allocateur proposé dans un serveur réseau existant. On appelle ces techniques optimisations compilateur parce qu'elles opèrent sur le flot des données et du contrôle dans des programmes en les transformant pour qu'ils fonctionnent plus efficacement. Les programmes réseaux possèdent une propriété fondamentale qui les rend faciles à manipuler de cette manière : ils sont basés sur une conception qui les organise en différentes couches, chacune englobant une fonctionalité bien définie. Cette propriété introduit dans le code des bloques fonctionnelles bien définis qui sont ´equivalents aux procédures et aux fonctions d'un langage généraliste. Dans la première partie de cette thèse, la spécialisation de programmes est utilisée pour créer différentes configurations de ces bloques qui correspondent à différents contextes d'utilisation. Au départ, chacun de ces bloques fonctionnels, tels que ceux utilisés dans le protocole TCP et dans le routage des trames, est conçu et développé pour fonctionner dans des conditions variées. Cependant, dans certaines situations spécifiques (comme dans le cas d'un réseaux haut-performance sans aucune congestion), certaines caractéristiques (comme les algorithmes du control de congestion de TCP) n'ont pas d'utilité. La spécialisation peut donc instancier ces bloques de code en éliminant les parties non-necessaires et en appliquant des transformations du flot des données et du contrôle pour rendre plus efficace leur fonctionnement. Une fois que ces bloques individuels sont rendus spécialisables, on bénéficie de l'encapsulation propre d'une pile de protocole en couches. Chacune de ces couches peut être spécialisée pour obtenir une pile de protocole spécialisée. Car cette façon d'utiliser la spécialisation de programmes est nouvelle et nécessite un style de programmation bien différent par rapport à ce qu'il existe : il faut de l'assistance pour les développeurs d'applications sous forme de bibliothèques et d'interfaces de programmation. De plus, la spécialisation a un inconvénient : il est très gourmand comme processus et donc ne peut pas être invoqué arbitrairement. Ces besoins sont traités dans la deuxième contribution de cette thèse, La spécialisation distante. La spécialisation distante est un ensemble de méchanismes et d'interfaces développées comme des extensions du noyau d'un système d'exploitation. Ces extensions permettent de déporter le processus de la spécialisation `à travers le réseau sur un système distant. La spécialisation distante fournit les avantages de la spécialisation dynamique de programmes à des systèmes qui en bénéficie potentiellement le plus, c'est `à dire, les systèmes embarqués. Traditionnellement, ces systèmes ont utilisé du code optimisé à la main. Cependant, produire ce code implique une procédure lente et produit des erreurs dans le code résultant. De plus, cette procédure n'arrive pas à exploiter des opportunités d'optimisation sophistiquées qui peuvent être identifiiés facilement par les outils automatisés. La spécialisation distante permet d'obtenir un tel code optimisé automatiquement à l'exécution, une fois que le système est préparé et rendu spécialisable. Une application peut dans ce cas demander des versions spécialisées des composant OS correspondant à des contextes particuliers à travers le réseau. En suite, on considère les serveurs réseaux. La spécialisation optimise effectivement du code qui est limité en performance par l'exécution des instructions sur le processeur, en éliminant des instructions non nécessaires et en rendant plus efficaces les instructions restantes. Mais pour les applications qui ont des inefficacités plus importantes, la spécialisation est inefficace, car malgré des améliorations importantes au niveau des instructions, la partie améliorée étant petite, les gains globaux sont insignifiants. Le facteur traditionnel qui limite les systèmes réseaux en performance est celui des opérations I/O. Par contre, les systèmes réseaux modernes sont maintenant équipés de suffisamment de mémoire. Donc, les op´erations I/O ne constituent plus le goulot d'´étranglement. A l'inverse, l'accès à la mémoire occupe maintenant cette position. Aujourd'hui, les accès à la mémoire cûutent jusqu'à 100 fois plus que d'autres opérations notamment la manipulation des registres. Cette thèse propose un nouvel allocateur de mémoire qui s'appelle Stingy Allocator pour minimiser le nombre de défauts cache dans un serveur orienté événement. La notion de bloques facilite, à nouveau, l'application de notre stratégie d'optimisation. Les bloques d'exécution dans un serveur orienté événement s'appelle des étapes et peuvent être identifiées et analysées par un outil automatisé une fois déclaré par un programmeur sous forme d'annotation pour le code. L'allocateur Stingy dépend du fait que ces étapes peuvent s'exécuter dans des ordres différents sans avoir un effet important sur la sémantique globale de l'application. Combiné à une nouvelle approche d'ordonnancement qui arrange différentes étapes pour limiter l'utilisation de la mémoire, Stingy Allocator assure que toute la mémoire allouée par le serveur soit bornée et qu'il reste dans les caches du système. Un ensemble d'outils a été développé pour intégrer Stingy Allocator dans des programmes existants. Ces outils ont été utilisés pour optimiser des applications existantes. Avec l'aide de ces outils, un programmeur peut modifier un serveur réseau pour qu'il se serve de Stingy Allocator sans comprendre intimement le fonctionnement de celui-ci. Chacune des parties d´ecrites au-dessus a été évaluée dans le contexte des programmes existants. La spécialisation des piles de protocole a été évaluée rigoureusement sur la pile TCP/IP du noyau de Linux. Celle-ci a aussi été ´etudiée dans le contexte de la pile TCP/IP de FreeBSD. La spécialisation distante a été utilisée pour spécialiser dynamiquement la pile TCP/IP de Linux ainsi que le serveur web TUX. Nos expériences ont démontré des réductions importantes dans la taille du code résultant (amélioré d'un facteur de 2 à 20) et des améliorations appréciables en terme de performance, les gains ´etant entre un facteur de 1.12 et 1.4.

Ce mémoire résume mon activité de recherche de 2000 à 2008, qui s'est orientée autour des passerelles de services logicielles de type OSGi. L'activité a été financée par 1 projet national de type ACI GRID [Projet DARTS 2002b] sur 2 ans (2000-2002), 1 projet Européen [Projet MUSE 2007] sur 4 ans (2003-2007) et 1 ANR sécurité [Projet LISE 2010] sur 3 ans (2008-2011). Durant ces années j'ai fait soutenir 2 thèses [Masri 2005, Royon 2007] et en suit une autre. J'ai formé et encadré environ 6 stagiaires par an, autour des technologies que nous utilisons, qui se répartissent entre des étudiants de Mastère recherche, de projets de fin d'étude et de stages d'élèves ingénieurs. J'ai également eu le support de 4 ingénieurs de recherche financés par les différents projets. J'emploie encore actuellement 2 ingénieurs. Mon activité est fortement dirigée par le génie logiciel des intergiciels et se situe à la frontière entre les problématiques issues de la grille de calcul, de l'administration de systèmes, des systèmes d'exploitations et de la sécurité. J'ai pris soin de diffuser et de publier l'ensemble des travaux réalisés dans l'équipe dans des journaux, dans des conférences, dans des workshops mais aussi et surtout dans la rédaction de rapports techniques et par la diffusion de code open-source dans les communautés concernées. Je suis responsable de l'équipe intergiciel du laboratoire CITI qui est structuré en 5 équipes autour des thèmes suivants : Senseurs, Protocoles, Modèles, Intergiciels, Systèmes embarqués. Ce mémoire reflète une synthèse de mes activités en présentant les différentes extensions que nous avons conçues et intégrées à un intergiciel système pour applications ambiantes. Il est structuré en deux parties et une conclusion. La première partie présente un état de l'art sur les intergiciels et la seconde partie présente les extensions que nous avons étudiées, implantées et diffusées. Ces extensions sont faites dans les domaine suivants : – Distribution de services, on montre comment on étend notre intergiciel système local – administration de services, on montre comment on peut superviser et monitorer des équipements ambiants, – virtualisation de services, on montre comment exécuter des services dans des espaces presque isolés, c'est à dire offrant le support mais pas le contrôle de l'isolation, – réduction de services, on montre comment économiser de la place disque pour l'exécution sur des environnements ne permettant pas d'héberger localement les piles d'exécution standard, – sécurisation, on montre comment identifier et gérer les problèmes de sécurité dans des environnements extensibles.

Ce manuscrit présente les travaux de recherche, d'encadrement et de développement que j'ai effectués au cours des huit dernières années. Ma première motivation a été de rendre utilisables les concepts liés à la notion de réécriture. Pour cela, ma stratégie a consisté à proposer un langage, dénommé Tom, construit comme une extension de langages existants, et non comme un langage à part entière. L'intérêt principal de cette approche, appelée Îlot Formel, est de fournir de nouvelles constructions aux programmeurs sans pour autant changer leur environnement de travail.<br />Cette approche, permettant de combiner différents formalismes est étudiée d'un point de vue formel.<br />Dans un deuxième temps, je me suis intéressé à la confiance que les programmeurs peuvent avoir dans les programmes qu'ils écrivent et dans les outils qu'ils utilisent.<br />Ces travaux m'ont amené à proposer des constructions de haut niveau (filtrage équationnel, anti-termes et stratégies) ainsi qu'à formaliser leur sémantique.<br />Nous présentons également une méthode originale qui permet certifier que le code produit par le compilateur Tom préserve bien la sémantique de ces constructions.

La problématique de cette thèse est celle de la construction de systèmes auto-administrables, c'est-à-dire de systèmes prenant eux-mêmes en charge <br />les fonctions d'administration classiquement dévolues à des humains. La construction de tels systèmes requiert à la fois l'utilisation d'une technologie logicielle adaptée et la mise en place d'une algorithmique dédiée.<br /><br />Concernant la technologie logicielle, nous proposons une démarche de construction d'infrastructures logicielles radicalement configurables, appelée « exogiciel ». Cette démarche, inspirée de la philosophie exo-noyaux, vise à minimiser le nombre d'abstractions - fonctionnelles, non fonctionnelles et architecturales - imposées au développeur d'applications. <br />Nous illustrons ce concept d'exogiciel à travers la présentation de DREAM, un canevas logiciel à composants pour la construction d'intergiciels de <br />communication.<br /><br />Concernant les aspects algorithmiques de la construction de systèmes autonomes, une approche classique, adoptée par la théorie de la commande, <br />est de mettre en place des boucles de commande. Dans cette thèse, nous présentons deux éléments de base des boucles de commande : LeWYS, un canevas <br />logiciel à composants permettant de construire des systèmes d'observation de systèmes distribués, et FREECAST, un protocole de diffusion de groupe avec <br />ordre total uniforme. Par ailleurs, nous montrons comment les différents logiciels présentés dans cette thèse peuvent s'intégrer dans JADE, un <br />intergiciel développé au sein du projet SARDES pour construire des boucles de commande pour l'administration autonome de systèmes.

No description available.

This habilitation introduces the question-learn-test-feedback pattern that resulted from a series of investigations in the domains of software testing and modular software construction. The contributions to these fields are of various natures, but are all fundamentally related through two major assumptions: software construction paradigms have to constantly evolve in order to deal with the increasingly complex requirements that software-intensive systems have to meet; a tester's perspective can support this evolution through the development of effective testing techniques and new empirical knowledge about these paradigms. Abstraction, modularity and separation of concerns have been advocated as key factors for rigorous software engineering for a long time. These principles have been incarnated by various software construction paradigms such as object-oriented programming and design, model-driven development and aspect-oriented modeling. These paradigms evolve in order to deal with the increasing number of heterogeneous requirements, the large number of variations and the need for adaptation that software-intensive systems have to integrate. The work presented here is about the integration of effective testing techniques in these paradigms and how this led us towards a more precise understanding of these paradigms. A major discovery in our work is that we could follow a systematic pattern when investigating these paradigms to integrate error detection capabilities. First, we have to question these paradigms about the new assumptions they introduce on software systems. When answering these questions we can can perform the following actions: learn through rigorous evaluation of hypotheses about these paradigms; test software systems developed in these new paradigms; provide feedback to the paradigms in the form of new construction techniques that improve testability. We capture these four facets for the investigation of software construction paradigms in the question-learn-test-feedback pattern (QLTF). This habilitation reports on investigations in three software construction techniques: object-oriented programming and design, aspect-oriented programming, model transformations. Each investigation is synthesized around the question-learn-test-feedback pattern.

DAEX is a metaheuristic designed to improve the plan quality and the scalability of an encapsulated planning system. DAEX is based on a state decomposition strategy, driven by an evolutionary algorithm, which benefits from the use of a classical planning heuristic to maintain an ordering of atoms within the individuals. The proof of concept is achieved by embedding the domain-independent satisficing YAHSP planner and using the critical path h1 heuristic. Experiments with the resulting algorithm are performed on a selection of IPC benchmarks from classical, cost-based and temporal domains. Under the experimental conditions of the IPC, and in particular with a universal parameter setting common to all domains, DAEYAHSP is compared to the best planner for each type of domain. Results show that DAEYAHSP performs very well both on coverage and quality metrics. It is particularly noticeable that DAEX improves a lot on plan quality when compared to YAHSP, which is known to provide largely suboptimal solutions, making it competitive with state-of-the-art planners. This article gives a full account of the algorithm, reports on the experiments and provides some insights on the algorithm behavior.

La dépendance croissante de la société à l'égard des systèmes logiciels nécessite de concevoir des logiciels robustes, adaptatifs et disponibles sans interruption. De tels systèmes proposent souvent de nombreux points de variation avec de nombreuses variantes, conduisant à une explosion combinatoire du nombre des configurations. Il devient rapidement impossible de spécifier et de valider toutes ces configurations lors de la conception d'un système adaptatif complexe. Cette thèse présente une approche dirigée par les modèles et basée sur la modélisation par aspects pour contenir la complexité de systèmes logiciels adaptatifs (Dynamically Adaptive Systems, DAS). Lors de la conception, les différentes facettes d'un DAS (variabilité, environnement/contexte, raisonnement et architecture) sont capturées à l'aide de différents méta-modèles dédiés. En particuliers, les variants de chaque point de variation sont raffinés à l'aide d'aspect (niveau model). Ces modèles sont embarqués à l'exécution pour contrôler et automatiser le mécanisme de reconfiguration dynamique. Le système courant et son contexte d'exécution sont abstraits par des modèles. Selon le contexte courant (modèle) un composant de raisonnement interprète le modèle de raisonnement et détermine un ensemble de variantes bien adaptées au contexte. Nous utilisons un tisseur d'aspects (niveau model) pour dériver automatiquement l'architecture correspondante à cette sélection de variantes. Ainsi, les concepteurs du DAS n'ont pas besoin de spécifier toutes les configurations : au contraire, chaque configuration est automatiquement construite lorsqu'il y en a besoin. Nous utilisons finalement une comparaison de modèle pour automatiser entièrement le processus de reconfiguration dynamique, sans avoir besoin d'écrire des scripts de reconfiguration de bas niveau. Les modèles embarqués à l'exécution sont des miroirs reflétant ce qui se produit vraiment dans le système courant. Il est cependant possible de travailler sur des copies de ces modèles, indépendamment du système courant et de re-synchronizer ces copies avec la réalité pour adapter réellement le système courant. En d'autres termes, notre approche permet d'exécuter des activités offline (pendant que le système fonctionne, mais indépendamment de lui) telles que la conception continue (continuous design) ou la prévision