Cette thèse développe des outils permettant de prouver qu’un système dynamique est sûr. En supposant qu’une partie de l’espace d’état est dangereuse, un système dynamique est dit sûr lorsque son état n’atteint jamais cette partie dangereuse au cours du temps, quel que soit l’état initial appartenant à un ensemble d’états initiaux admissibles et quel que soit le niveau de perturbation restant dans un domaine admissible. Les outils proposés cherchent à établir des preuves de sûreté pour des systèmes décrits par des modèles dynamiques non-linéaires et des modèles dynamiques hybrides. Prouver qu’un système dynamique est sûr en calculant explicitement l’ensemble des trajectoires possibles du système lorsque le modèle dynamique est non-linéaire et perturbé reste une tâche très difficile. C’est pourquoi cette thèse aborde ce problème à l’aide de fonctions barrières paramétrées. Une barrière, lorsqu’elle existe, permet de partitionner l’espace d’état et d’isoler l’ensemble des trajectoires possibles de l’état du système de la partie dangereuse de l’espace d’état. La fonction paramétrique décrivant la barrière doit satisfaire un certain nombre de contraintes impliquant la dynamique du modèle, l’ensemble des états initiaux possibles, et l’ensemble dangereux. Ces contraintes ne sont pas convexes en général, ce qui complique la recherche de fonctions barrières satisfaisantes. Précédemment, seules des fonctions barrières polynomiales ont été considérées pour des modèles dynamiques polynomiaux. Cette thèse considère des systèmes dynamiques relativement généraux avec des barrières paramétriques quelconques. Les solutions présentées exploitent des outils de satisfaction de contraintes sur des domaines continus et des outils issus de l’analyse par intervalles. Dans un premier temps, cette thèse considère des systèmes dynamiques non-linéaires à temps continu. Le problème de conception d’une barrière paramétrique est formulé comme un problème de satisfaction des contraintes sur des domaines réels avec des variables quantifiées de manière existentielle et universelle. L’algorithme CSC-FPS a été adapté afin de résoudre le problème de synthèse de barrière. Cet algorithme combine une exploration de l’espace des paramètres de la barrière et une phase de vérification des propriétés de la barrière. A l’aide de contracteurs, il est possible de significativement accélérer la recherche de solutions. Dans un second temps, ces résultats sont étendus au cas de systèmes décrits par des modèles dynamiques hybrides. La propriété de sûreté doit être prouvée lors de l’évolution à temps continu du système dynamique, mais aussi pendant les transitions du système. Ceci nécessite l’introduction de contraintes supplémentaires qui lient les fonctions barrières associées à chaque mode à temps continu entre elles. Réaliser la synthèse de toutes les fonctions barrières pour les différents modes simultanément n’est envisageable que pour des systèmes de très petite dimension avec peu de modes. Une approche séquentielle a été proposée. Les contraintes liées aux transitions sont introduites progressivement entre les modes pour lesquels une barrière a déjà été obtenue. Lorsque certaines contraintes de transition ne sont pas satisfaites, une méthode de backtracking doit être mise en œuvre afin de synthétiser des barrières offrant une meilleure prise en compte des contraintes de transition non satisfaites. Ces approches ont été évaluées et comparées avec des techniques de l’état de l’art sur des systèmes décrits par des modèles à temps continu et des modèles hybrides. / This thesis addresses the problem of proving the safety of systems described by non-linear dynamical models and hybrid dynamical models. A system is said to be safe if all trajectories of its state do not reach an unsafe region. Proving the safety of systems by explicitly computing all its trajectories when its dynamic is non-linear or when its behavior is described by an hybrid model with non-linear dynamics remains a challenging task. This thesis considers the barrier function approach to prove the safety of a system. A barrier function, when it exists, partitions the state space and isolates the trajectories of the system starting from any possible initial values of the state and the unsafe part of the state space. The set of constraints, which have to be satisfied by a barrier function are usually non-convex, rendering the search of satisfying barrier functions hard. Previously, only polynomial barrier functions were taken in consideration and for systems with polynomial dynamics. This thesis considers relatively general dynamical systems with generic non-linear barrier functions. The solutions presented are based on template barrier functions, constraint satisfaction problems, and interval analysis. The first part of the thesis focuses on non-linear dynamical systems. The barrier function design problem is formulated as a constraint satisfaction problem that can be solved using tools from interval analysis. This formulation allows one to prove the safety of a non-linear dynamical system by finding the parameters of a template barrier function such that all constraints are satisfied using the FPS-CSC algorithm, which has been adapted and supplemented with contractors to improve its efficiency. The second part of the thesis is dedicated to the design of barrier functions for systems described by hybrid dynamical models. Safety properties have to be proven during the continuous-time evolution of the system, but also during transitions. This leads to additional constraints that have to be satisfied by candidate barrier functions. Solving all the constraints simultaneously to find all the barrier functions is usually computationally intractable. In the proposed approach, the algorithm explores all the locations sequentially. Transition constraints are introduced progressively between the already explored locations. Backtracking to previous location is considered when transition constraints are not satisfied. The efficiency of the proposed approaches has been compared with state-of-the-art solutions.

Afin d'assurer disponibilité et réactivité, de nombreux systèmes distribués reposent sur des bases de données répliquées qui maintiennent des copies (répliques) des données sur différents serveurs. la cohérence constitue un défi important dans la mise en oeuvre des bases de données répliquées. les concepteurs de bases de données repliquées doivent faire un choix difficile entre une cohérence forte, qui guarantit une large gamme d'invariants applicatifs, mais qui est lente et fragile, et une réplication asynchrone, qui assure un bon niveau de disponibilité et de réactivité, mais laisse le programmeur face à de possibles anomalies liées à la concurrence.pour résoudre ce dilemme, des bases de données commerciales et recherche fournissent une cohérence hybride qui permet au programmeur d'exiger une cohérence forte pour certaines opérations, et d'ainsi permettre une synchronisation.cette thèse étudie l'analyse et la mise en oeuvre d'une application et de la cohérence associée, de manière à assurer les invariants de cette application avec un minimum d'exigences de cohérence. les trois principales contributions de cette thèse sont: 1) nous proposons le premier outil d'analyse statique destiné à prouver la validité d'invariants d'applications de base de données à modèle de cohérence hybride. 2) nous présentons la mise en application de notre outil d'analyse dans le cadre de la conception d'un système de fichiers dont la sémantique permet un comportement similaire à posix et à un coût résonable. 3)nous proposons un ensemble de patterns utiles, susceptibles d'aider les développeurs d'application dans l'implémentation d'invariants les plus communs. / Distributed databases take advantage of replication to bring data close to the client, and to always be available. the primary challenge for such databases is to ensure consistency. recent research provide hybrid consistency models that allow the database supports asynchronous updates by default, but synchronisation is available upon request. to help programmers exploit the hybrid consistency model, we propose a set of useful patterns,proof rules, and tool for proving integrity invariants of applications. in the first part, we study a sound proof rule that enables programmers to check whether the operations of a given application semantics maintain the application invariants under a given amount of parallelism. we have developed a smt-based tool that automates this proof, and verified several example applications using the tool. in the second part, we apply the above methodology to the design of a replicated file system.the main invariant is that the directory structure forms a tree. we study three alternative semantics for the file system. each exposes a different amount of parallelism, and different anomalies. using our tool-assisted rules, we check whether a specific file system semantics maintains the tree invariant, and derive an appropriate consistency protocol. in the third part of this thesis, we present three classes of invariants: equivalence, partial order, and single-item generic. each places some constraints over the state. each of these classes maps to a different storage-layer consistency property: respectively, atomicity, causal ordering, or total ordering.

Ce travail s'inscrit dans le cadre des recherches menées autour de la compilation des langages de classes, notamment Eiffel, et plus généralement des langages à objets à typage statique. Très brièvement, on peut dire que le but de cette thèse revient à tenter de répondre à une question fondamentale: comment mieux compiler les langages à objets, c'est à dire comment avoir des programmes plus rapides et plus sûrs ? Ce travail de recherche est basé en grande partie sur l'analyse statique, abordée via deux axes principaux. Le premier consiste à pouvoir effectuer des contrôles de validité et de cohérence du programme, et ce non seulement sur les programmes finis, mais bien dès le début du développement, de façon à pouvoir assister au maximum les développeurs durant la phase de conception et d'implantation. Le second axe, qui est la substance même de cette thèse, considère l'utilisation des informations apportées par l'analyse statique du système pour améliorer la qualité du code généré. En effet, ces informations offrent des possibilités importantes en terme d'optimisation du code généré, aussi bien par des optimisations liées aux algorithmes que par des optimisations sur les structures de données. Nous proposons et expérimentons une approche basée sur la duplication et la spécialisation du code par analyse globale du système, afin d'implanter de façon efficace les structures de données et le code du programme compilé, notamment en ce qui concerne la liaison dynamique. Nous introduisons ainsi une nouvelle méthode de liaison dynamique, basée sur des arbres de branchement directs, dont les performances sont supérieures ou égales à celles des systèmes actuels classiques à base de tables d'indirection. Cette approche est également étendue à la génération par le compilateur d'un ramasse-miettes automatiquement adapté à l'application compilée. Nous menons aussi certaines études pour évaluer les optimisations permises par l'utilisation massive de l'aliasing dans un compilateur écrit dans un langage de classes, ainsi que des moyens de mieux maîtriser cette technique. Ces travaux sont validés entre autres par le développement d'un compilateur Eiffel nommé SmallEiffel et de ses bibliothèques, qui, très largement diffusés et utilisés, sont devenus The GNU Eiffel Compiler.

Les systèmes temps-réel strict sont soumis à des contraintes temporelles dont le non respect peut entraîner des conséquences économiques, écologiques, humaines catastrophiques. Le processus de validation, garantissant la sûreté de ces logiciels en assurant le respect de ces contraintes dans toutes les situations possibles y compris le pire cas, se base sur la connaissance à priori du pire temps d'exécution de chacune des tâches du logiciel. Cependant, l'obtention de ce pire temps d'exécution est un problème difficile pour les architectures actuelles, en raison des mécanismes matériels complexes pouvant amener une variabilité importante du temps d'exécution. Ce document se concentre sur l'analyse du comportement temporel pire cas des hiérarchies de mémoires cache, afin de déterminer leur contribution au pire temps d'exécution. Plusieurs approches sont proposées afin de prédire et d'améliorer le pire temps d'exécution des tâches s'exécutant sur des processeurs multi-cœurs disposant d'une hiérarchie de mémoires cache avec des niveaux partagés entre les différents cœurs de calculs.

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 HierarchicalEdge Bundles" qui est basée sur une représentation 2D existante nommée "HierarchicalEdge 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 / This work falls within the scope of research pertaining to the analysis and the visualization of software systems, especially for object oriented languages, and more precisely Java. In a nutshell, it can be said the aim of this thesis is to try to answer a fundamental question: what can we do to ease the understanding of software by its designers and developers ? This research work is mainly based on two axes. The first axis consists in analyzing software runtime, not only at method level, but also at basic bloc level, so as to be able to get meaningful and precise information about the runtime. For instance, we can acquire the different types of instances on call sites at runtime. The second axis considers the use of information coming from our dynamic analyzer of software runtime and allowing the visualization of these data. Indeed, this kind of information offers important details about software functioning and provide a way to explain the behavior of software, so as to identify performance, coding and even design and architecture issues. We propose a technique that allows flexible and efficient dynamic analysis of the execution of Java programs. We thus introduce a new technique and tool for gathering information not yet offered by other analyzers. This approach precisely traces the execution of programs with acceptable performance penalty, that is while keeping the traced programs usable. In addition, we propose and experiment an approach based on visualizing relationships within a software city representation. We introduce a new technique for representing relationships in 3D named the "3D Hierarchical Edge Bundles" that is based on an existing 2D technique, the "Hierarchical Edge Bundles". This approach keeps the power of the software city metaphor while adding the representation of the relationships within the software, in a readable way. These works are validated by, among others things, the development of a tracer and analyzer tool called VITRAIL JBInsTrace and a visualization tool called VITRAIL Visualizer. These tools are used on our current researches which consist in studying runtime of object-oriented programs

Développer des analyseurs statiques nécessite une manipulation intensive de structures d'arbres et de graphes représentant le programme. La finalité de cette thèse est de proposer des constructions de langage dédiées au prototypage d'outils d'analyse et de transformation de programmes et inspirées de la réécriture de termes et de termes-graphes. L'originalité de notre approche est d'embarquer ces nouvelles constructions dans les langages généralistes sous la forme d'un langage dédié embarqué. Les travaux de cette thèse se fondent sur le langage Tom qui propose d'embarquer des constructions de réécriture dans des langages généralistes comme Java. La première contribution de cette thèse a été de formaliser les langages embarqués sous le concept de langage îlot. Ce formalisme a ainsi permis de certifier la compilation du langage Tom. Nos travaux sur l'analyse de Bytecode nous ont ensuite conduit à réfléchir à la représentation et la manipulation de graphes de flot de programmes et nous avons alors proposé des constructions de langage inspirées de la réécriture de termes-graphes. Une autre contribution de cette thèse est la conception d'un langage de stratégies adapté à l'expression de propriétés sur un programme. Associé au filtrage, ce langage permet d'exprimer de manière déclarative des analyses et des transformations sur des arbres ou des graphes. Enfin, l'ensemble des propositions de cette thèse a été intégré au langage Tom sous la forme de nouvelles constructions syntaxiques ou d'améliorations de constructions existantes et a ainsi pu être appliqué à l'analyse du langage Java.

La problématique abordée dans ce travail est celle de la gestion mémoire automatique pour des programmes Java temps-réel embarqués. Dans des langages comme le C ou le C++, la mémoire est typiquement gérée explicitement par le programmeur, ce qui est la source de nombreuses erreurs d'exécution causées par des manipulations hasardeuses. Le coût de correction de telles erreurs est très important car ces erreurs sont rarement reproductibles et donc difficiles à appréhender. En Java la gestion mémoire est entièrement automatique, ce qui facilite considérablement le développement. Cependant, les techniques classiques de recyclage de la mémoire, typiquement basées sur l'utilisation d'un ramasse-miettes, sont souvent considérées comme inapplicables dans le contexte des applications temps-réel embarquées, car il est très difficile de prédire leur temps de réponse. Cette incompatibilité est un frein important à l'adoption de langages de haut niveau comme Java dans ce domaine.<br />Pour résoudre le problème de la prévisibilité du temps d'exécution des opérations mémoire, nous proposons une approche fondée sur l'utilisation d'un modèle mémoire en régions. Cette technique, en groupant physiquement les objets de durées de vie similaires dans des zones gérées d'un seul bloc, offre en effet un comportement temporel prévisible. Afin de décider du placement des objets dans les différentes régions, nous proposons un algorithme d'analyse statique qui calcule une approximation des relations de connexion entre les objets. Chaque structure de données est ainsi placée dans une région distincte. L'analyse renvoie également au programmeur des informations sur le comportement mémoire du programme, de façon à le guider vers un style de programmation propice à la gestion mémoire en régions, tout en pesant le moins possible sur le développement. <br />Nous avons implanté un gestionnaire mémoire automatique en régions dans la machine virtuelle JITS destinée aux systèmes embarqués à faibles ressources. Les résultats expérimentaux ont montré que notre approche permet dans la plupart des cas de recycler la mémoire de façon satisfaisante, tout en présentant un comportement temporel prévisible. Le cas échéant, l'analyse statique indique au développeur quels sont les points problématiques dans le code, afin de l'aider à améliorer son programme.

Dans cette thèse, on présente un cadre théorique général d'analyse statique pour l'inférence de propriétés `structurelles' ou d'`usage' des programmes. Le terme `structurel', emprunté à la théorie de la démonstration, suggère un rapport étroit avec la logique linéaire, où les règles structurelles de contraction et affaiblissement jouent un rôle important. Le problème de l'analyse statique consiste à trouver une traduction d'un langage source dans le style de PCF vers un langage comportant des annotations structurelles. On montre que l'on peut characteriser l'ensemble de traductions possibles comme des solutions d'un ensemble d'inequations appropriées. Plus particulièrement, on s'intéresse à la plus petite solution, qui correspond à la traduction la plus précise ou optimale. La plus grande partie de ce manuscrit de thèse est dédié à un seul cas d'étude, l'analyse linéaire, dont l'objectif est de déterminer les valeurs qui sont utilisées une seule fois. On decrit d'abord une version de l'analyse linéaire très simplifiée, en suite on introduise des extensions qui comportent des notions de sous-typage et du polymorphisme d'annotations, ce étant clé dans la pratique, car il permet à l'analyse de garder son pouvoir expressif en présence de modules compilés séparément.

Le sujet de cette thèse est le développement de méthodes pour l'analyse automatique des programmes informatiques. Une des applications majeures est la conception d'outils pour découvrir les erreurs de programmations avant qu'elles ne se produisent, ce qui est crucial à l'heure où des tâches critiques mais complexes sont confiées à des ordinateurs. Nous nous plaçons dans le cadre de l'interprétation abstraite, qui est une théorie de l'approximation sûre des sémantiques de programmes, et nous nous intéressons en particulier aux domaines abstraits numériques spécialisés dans la découverte automatique des propriétés des variables numérique d'un programme.<br />Dans cette thèse, nous introduisons plusieurs nouveaux domaines numériques abstraits et en particulier le domaine des zones (permettant de découvrir des invariants de la forme X-Y≤c, des zones de congruence (X≡Y+c [b]) et des octogones (±X ±Y≤c). Ces domaines sont basés sur les concepts existants de graphe de potentiel, de matrice de différences bornées et sur l'algorithmique des plus courts chemins. Ils sont intermédiaires, en terme de précision et de coût, entre les domaines non relationnels (tel celui des intervalles), très peu précis, et les domaines relationnels classiques (tel celui des polyèdres), très coûteux. Nous les nommons " faiblement relationnels ". Nous présentons également des méthodes permettant d'appliquer les domaines relationnels à l'analyse de nombres à virgule flottante, jusqu'à présent uniquement réalisable par des domaines non relationnels donc peu précis. Enfin, nous présentons des méthodes génériques dites de " linéarisation " et de " propagation de constantes symboliques " permettant d'améliorer la précision de tout domaine numérique, pour un surcoût réduit.<br />Les méthodes introduites dans cette thèse ont été intégrées à Astrée, un analyseur spécialisé dans la vérification de logiciels embarqués critiques et se sont révélées indispensables pour prouver l'absence d'erreurs à l'exécution de logiciels de commande de vol électrique. Ces résultats expérimentaux viennent justifier l'intérêt de nos méthodes pour des cadre d'applications réelles.

L'objectif de la thèse est de développer des méthodologies et des outils pour la vérification compositionnelle et incrémentale des systèmes à base de composants. Nous proposons une méthode compositionnelle pour vérifier des propriétés de sûreté. La méthode est basée sur l'utilisation des deux types d'invariants: invariants de composant qui expriment des aspects locaux des systèmes et invariants d'interaction qui caractérisent les contraintes globales induites par les synchronisations fortes entre les composants. Nous offrons des techniques efficaces pour calculer ces invariants. Nous proposons également une nouvelle méthode de vérification incrémentale qui prend la conception incrémentale du système en compte. L'intégration de la vérification dans le processus de conception permet de déceler une erreur dès qu'elle apparaît. En outre, cette méthode permet d'éviter de refaire tous les processus de vérification par la réutilisation de résultats intermédiaires. Elle prend des avantages des structures de systèmes pour faire face à la complexité de la vérification globale et, par conséquent, réduit significativement le coût de la vérification en temps et en mémoire utilisée. Les méthodes compositionnelles et incrémentales ont été mises en oeuvre dans la chaîne d'outil D-Finder. Les résultats expérimentaux obtenus sur plusieurs études de cas non triviales montrent l'efficacité de nos méthodes ainsi que les capacités de D-Finder.