Cette thèse est une contribution à la spécification et à la vérification formelles des allocateurs de mémoire dynamiques séquentiels (SDMA, en abrégé), qui sont des composants clés des systèmes d'exploitation ou de certaines bibliothèques logiciel. Les SDMA gèrent la partie tas de la mémoire des processus. Leurs implémentations utilisent à la fois des structures de données complexes et des opérations de bas niveau. Cette thèse se concentre sur les SDMA qui utilisent des structures de données de type liste pour gérer les blocs du tas disponibles pour l'allocation (SDMA à liste).La première partie de la thèse montre comment obtenir des spécifications formelles de SDMA à liste en utilisant une approche basée sur le raffinement. La thèse définit une hiérarchie de modèles classés par la relation de raffinement qui capture une grande variété de techniques et de politiques employées par le implémentations réelles de SDMA. Cette hiérarchie forme une théorie algorithmique pour les SDMA à liste et pourrait être étendue avec d'autres politiques. Les spécifications formelles sont écrites en Event-B et les raffinements ont été prouvés en utilisant la plateforme Rodin. La thèse étudie diverses applications des spécifications formelles obtenues: le test basé sur des modèles, la génération de code et la vérification.La deuxième partie de la thèse définit une technique de vérification basée sur l'interprétation abstraite. Cette technique peut inférer des invariants précis des implémentations existantes de SDMA. Pour cela, la thèse définit un domaine abstrait dont les valeurs representent des ensembles d'états du SDMA. Le domaine abstrait est basé sur un fragment de la logique de séparation, appelé SLMA. Ce fragment capture les propriétés liées à la forme et au contenu des structures de données utilisées par le SDMA pour gérer le tas. Le domaine abstrait est défini comme un produit spécifique d'un domaine abstrait pour graphes du tas avec un domaine abstrait pour des sequences finies d'adresses mémoire. Pour obtenir des valueurs abstraites compactes, la thèse propose une organisation hiérarchique des valeurs abstraites: un premier niveau abstrait la liste de tous les blocs mémoire, alors qu'un second niveau ne sélectionne que les blocs disponibles pour l’allocation. La thèse définit les transformateurs des valeurs abstraites qui capturent la sémantique des instructions utilisées dans les implémentations des SDMA. Un prototype d'implémentation de ce domaine abstrait a été utilisé pour analyser des implémentations simples de SDMA. / The first part of the thesis demonstrates how to obtain formal specifications of free-list SDMA using a refinement-based approach. The thesis defines a hierarchy of models ranked by the refinement relation that capture a large variety of techniques and policies employed by real-work SDMA. This hierarchy forms an algorithm theory for the free-list SDMA and could be extended with other policies. The formal specifications are written in Event-B and the refinements have been proved using the Rodin platform. The thesis investigates applications of the formal specifications obtained, such as model-based testing, code generation and verification.The second part of the thesis defines a technique for inferring precise invariants of existing implementations of SDMA based abstract interpretation. For this, the thesis defines an abstract domain representing sets of states of the SDMA. The abstract domain is based on a fragment of Separation Logic, called SLMA. This fragment captures properties related with the shape and the content of data structures used by the SDMA to manage the heap. The abstract domain is defined as a specific product of an abstract domain for heap shapes with an abstract domain for finite arrays of locations. To obtain compact elements of this abstract domain, the thesis proposes an hierarchical organisation of the abstract values: a first level abstracts the list of all chunks while a second level selects only the chunks available for allocation. The thesis defines transformers of the abstract values that soundly capture the semantics of statements used in SDMA implementations. A prototype implementation of this abstract domain has been used to analyse simple implementations of SDMA

La dernière décennie, la complexité des technologies embarqués a explosé et les flots de conception industrielle habituels ne suffisent plus pour proposer des produits fiables en respectant les exigences du marché. Ainsi, le développement de nouvelles méthodologies de conception est devenu un besoin impératif. La thèse vise l'amélioration des méthodologies de conception des systèmes embarqués. En proposant une approche de conception par niveaux d’abstraction, la nouvelle approche permet de guider et d’assister les concepteurs dans les étapes de conception, précisément de raffiner les composants de communication. Elle offre des garanties de préservation des propriétés fonctionnelles le long du flot de conception. La méthode proposée permet de raisonner sur les différents niveaux de description d'un système en exploitant des techniques de preuve de propriétés associées aux raffinement formel. / In the last decade, the complexity of embedded systems has exploded and the usual industrial design flows do not suffice any more to propose reliable products while respecting time to market constrain. Thus, developing new design methodologies has become an imperative. The thesis aims at the improvement of the methodologies of conception of the embedded systems. It proposes a method for assisting the process of refinement along the design flow. The proposed approach splits the design flow into multiple-levels, in order to guide the designer in the design process, from the most abstract model down to a synthesizable model. Furthermore, by using formal techniques the method allows to check the preservation of functional correctness along the design flow.

Les systèmes informatiques envahissent notre vie quotidienne et sont devenus des éléments essentiels de chacun de nos instants de vie. La technologie de l'information est un secteur d'activités offrant des opportunités considérables pour l'innovation et cet aspect paraît sans limite. Cependant, des systèmes à logiciel intégré ont donné des résultats décevants. Selon les constats, ils étaient non fiables, parfois dangereux et ne fournissaient pas les résultats attendus. La faiblesse des pratiques de développement constitue la principale raison des échecs de ces systèmes. Ceci est dû à la complexité des logiciels modernes et au manque de connaissances adéquates et propres. Le développement logiciel fournit un cadre contribuant à simplifier la conception de systèmes complexes, afin d'en obtenir une meilleure compréhension et d'assurer une très grande qualité à un coût moindre. Dans les domaines de l'automatique, de la surveillance médicale, de l'avionique..., les systèmes embarqués hautement critiques sont candidats aux erreurs pouvant conduire à des conséquences graves en cas d'échecs. La thèse vise à résoudre ce problème, en fournissant un ensemble de techniques, d'outils et un cadre pour développer des systèmes hautement critiques, en utilisant des techniques formelles à partir de l'analyse des exigences jusqu'à la production automatique de code source, en considérant plusieurs niveaux intermédiaires. Elle est structurée en deux parties: d'une part des techniques et des outils et d'autre part des études de cas. La partie concernant des techniques et des outils présente une structure intégrant un animateur de modèles en temps-réel, un cadre de correction de modèles et le concept de charte de raffinement, un cadre de modélisation en vue de la certification, un modèle du coeur pour la modélisation en boucle fermée et des outils de générations automatiques de code. Ces cadres et outils sont utilisés pour développer les systèmes critiques à partir de l'analyse des exigences jusqu'à la production du code, en vérifiant et en validant les étapes intermédiaires en vue de fournir un modèle formel correct satisfaisant les propriétés souhaitées attendues au niveau le plus concret. L'introduction de nouveaux outils concourt à améliorer la vérification des propriétés souhaitées qui ne sont pas apparentes aux étapes initiales du développement du système. Nous évaluons les propositions faites au travers de cas d'études du domaine médical et du domaine des transports. De plus, le travail de cette thèse a étudié la représentation formelle des protocoles médicaux, afin d'améliorer les protocoles existants. Nous avons complètement formalisé un protocole réel d'interprétation des ECG, en vue d'analyser si la formalisation était conforme à certaines propriétés relevant du protocole. Le processus de vérification formelle a mis en évidence des anomalies dans les protocoles existants. Nous avons aussi découvert une structure hiérarchique pour une interprétation efficace permettant de découvrir un ensemble de conditions qui peuvent être utiles pour diagnostiquer des maladies particulières à un stade précoce. L'objectif principal du formalisme développé est de tester la correction et la consistance du protocole médical / Software systems are pervasive in all walks of our life and have become an essential part of our daily life. Information technology is one major area, which provides powerful and adaptable opportunities for innovation, and it seems boundless. However, systems developed using computer-based logic have produced disappointing results. According to stakeholders, they are unreliable, at times dangerous, and fail to provide the desired outcomes. Most significant reasons of system failures are the poor development practices for system development. This is due to the complex nature of modern software and lack of adequate and proper understanding. Software development provides a framework for simplifying the complex system to get a better understanding and to develop the higher fidelity quality systems at lower cost. Highly embedded critical systems, in areas such as automation, medical surveillance, avionics, etc., are susceptible to errors, which can lead to grave consequences in case of failures. This thesis intends to contribute to further the use of formal techniques for the development computing systems with high integrity. Specifically, it addresses that formal methods are not well integrated into established critical systems development processes by defining a new development life-cycle, and a set of associated techniques and tools to develop highly critical systems using formal techniques from requirements analysis to automatic source code generation using several intermediate layers with rigorous safety assessment approach. The approach has been realised using the Event-B formalism. This thesis has mainly two parts: techniques and tools and case studies. The techniques and tools section consists of development life-cycle methodology, a framework for real-time animator, refinement chart, a set of automatic code generation tools and formal logic based heart model for close loop modeling. New development methodology, and a set of associated techniques and tools are used for developing the critical systems from requirements analysis to code implementation, where verification and validation tasks are used as intermediate layers for providing a correct formal model with desired system behavior at the concrete level. Introducing new tools help to verify desired properties, which are hidden at the early stage of the system development. We also critically evaluate the proposed development methodology and developed techniques and tools through case studies in the medical and automotive domains. In addition, the thesis work tries to address the formal representation of medical protocols, which is useful for improving the existing medical protocols. We have fully formalised a real-world medical protocol (ECG interpretation) to analyse whether the formalisation complies with certain medically relevant protocol properties. The formal verification process has discovered a number of anomalies in the existing protocols. We have also discovered a hierarchical structure for the ECG interpretation efficiently that helps to find a set of conditions that can be very helpful to diagnose particular disease at the early stage. The main objective of the developed formalism is to test correctness and consistency of the medical protocol

Nous présentons dans cette thèse intitulée "Développement d'algorithmes répartis corrects par construction" nos travaux sur le développement et la vérification formels d'algorithmes répartis. Nous nous intéressons à ces algorithmes, à cause de la difficulté de leur vérification et validation. Pour analyser ces algorithmes, nous avons choisi d'utiliser Event B pour le raffinement de modèles, la vérification de propriétés de sûreté, et TLA, pour la vérification des propriétés temporelles (vivacité et équité). Nous nous sommes focalisé sur le paradigme de correction-par-construction, basé sur la modélisation par raffinement, la preuve de propriétés, ainsi que la réutilisation de modèles/preuves/propriétés (~ patrons de conception) pour guider le développement formel des algorithmes étudiés. Nous avons mis en place un paradigme de développement lors duquel un algorithme réparti est dans un premier temps caractérisé par les services qu'il fournit, et qui sont ensuite exprimés par des propriétés de vivacité, guidant la construction des modèles Event B de cet algorithme. Les règles d'inférence de TLA nous permettent ensuite de détailler les propriétés de vivacité, et de guider le développement formel par raffinement de l'algorithme. Ce paradigme, appelé "service-as-event", est caractérisé par des diagrammes d'assertions permettant de représenter les propriétés de vivacité (en prenant en compte l'équité) des algorithmes répartis étudiés, de comprendre leurs mécanismes. Ce paradigme nous a permis d'analyser des algorithmes de routage (Anycast RP de Cisco Systems et XY pour les réseaux-sur-puce (NoC)), des algorithmes de snapshot et des algorithmes d'auto-stabilisation. / The subject of this thesis is the formal development and verification of distributed algorithms. We are interested in this topic, because proving that a distributed algorithm satisfies given specification and properties is a difficult task. We choose to use the Event B method (refinement, safety properties) and the temporal logic TLA (fairness, liveness properties) for modelling the distributed algorithms. There are several existing approaches for formalising distributed algorithms, and we choose to focus on the "correct-by-construction" paradigm, which is characterised by the use of model refinement, proof of properties (safety, liveness) and reuse of formal models/proofs/properties, developments (~ design patterns) for modelling distributed algorithms. Our works introduce a paradigm which allows us to describe an algorithm with a set of services/functionalities, which are then expressed using liveness properties. These properties guide us in developing the formal Event B models of the studied algorithms. Inference rules from TLA allow to decompose the liveness properties, therefore detailing the services and guiding the refinement process. This paradigm, called "service-as-event" is also characterized by (assertions) diagrams, which allow to graphically represent liveness properties (with respect to fairness hypotheses) and detail the mecanisms and functioning of the studied distributed algorithms. The "service-as-event" paradigm allowed us to develop and verify the following algorithms : routing algorithms, such as Anycast RP (Cisco Systems), XY for Networks-on-Chip (NoC), snapshot and self-* algorithms.

Cette thèse se situe au croisement de deux domaines : la sûreté de fonctionnement des systèmes critiques et les méthodes formelles. Nous cherchons à établir la cohérence des analyses de sûreté de fonctionnement réalisées à l’aide de modèles représentant un même système à des niveaux de détail différents. Pour cela, nous proposons une notion de raffinement dans le cadre de la conception de modèles AltaRica : un modèle détaillé raffine un modèle abstrait si le modèle abstrait simule le modèle détaillé. La vérification du raffinement de modèles AltaRica est supportée par l’outil de model-checking MecV. Ceci permet de réaliser des analyses multi-systèmes à l’aide de modèles à des niveaux de détail hétérogènes : le système au centre de l’étude est détaillé tandis que les systèmes en interface sont abstraits. Cette approche a été appliquée à l’étude d’un système de contrôle de gouverne de direction d’un avion connecté à un système de génération et distribution électrique. / This thesis links two fields : system safety analyses and formal methods.We aim at checking the consistensy of safety analyses based on formal models that represent a system at different levels of detail. To reach this objective, we introduce a refinement notion in the AltaRica modelling process : a detailed model refines an abstract model if the abstract model simulates the detailed model. The AltaRica model refinement verification is supported by the MecV model-checker. This allows to perform multi-system safety analyses using models with heterogeneous levels of detail : the main system is detailed whereas the interfaced systems remain abstract. This approach has been applied to the analysis of a rudder control system linked to an electrical power generation and distribution system.

La conception et fabrication assistées par ordinateur (CFAO) est incontournable dans la création et l'élaboration d'un produit. De même, l'infographie est couramment employée en effets spéciaux ou réalité virtuelle. Pourtant, chaque domaine utilise ses propres outils pour modéliser des surfaces. Pour répondre aux contraintes de ces deux types d'utilisations, nous proposons une nouvelle modélisation de surfaces polynomiales, interpolantes, globalement lisses (de plan tangent continu) et hiérarchique. Une surface lisse initiale est d'abord construite sur un maillage triangulaire, ce qui permet de traiter toutes les topologies. Des détails sont ensuite progressivement ajoutés par niveaux. Pour ce faire, chaque face est subdivisée en quatre sous-faces par insertion d'un sommet en milieu d'arête. Ce raffinement n'induit pas de modifications significatives sur la surface. Chaque détail est défini localement par rapport au précédent grâce à l'utilisation de repères locaux. Cette hiérarchie permet à l'ensemble des détails fins de suivre continûment le déplacement lors d'une édition de la surface. Deux applications sont ensuite proposées dans cet ouvrage : Tout d'abord, un modeleur 3D respectant la démarche créative des artistes. Celui-ci repose sur le calcul d'une forme globale progressivement affinée pour obtenir l'objet désiré, et offre la possibilité d'éditer les objets de manière intuitive en modifiant très peu de paramètres. Enfin, un outil de reconstruction est présenté pour modéliser des objets existants grâce à notre nouvelle représentation hiérarchique.

Cette thèse traite de la résolution numérique des équations de Fredholm de seconde espèce faiblement singulières, posées dans un espace de Banach. Les méthodes décrites ici sont appliquées plus particulièrement dans le cas de l'espace des fonctions continues sur un intervalle compact et dans le cas de l'espace des fonctions intégrables, au sens de Lebesgue, sur un intervalle compact. Le premier chapitre fixe brièvement le cadre théorique de cette étude. Différents types de convergence d'une suite d'opérateurs dans un espace de Banach complexe, ainsi que leurs propriétés, y sont notamment rappelés. Le deuxième chapitre est consacré à la description et à l'analyse de deux méthodes d'approximation de rang fini sur lesquelles sont appliqués trois schémas de raffinement itératif. Des majorations des erreurs relatives associées à chaque méthode et dans chacun des espaces fonctionnels considérés y sont déduites, ainsi que les taux de convergence des schémas de raffinement correspondants. Une description détaillée de la mise en \oe uvre de ces derniers est donnée. Le troisième chapitre traite de l'application de ces méthodes à la résolution numérique de l'équation de transfert. Cette équation intervient au sein d'un problème beaucoup plus vaste (émanant de la théorie du transfert) dont une brève description est donnée dans le cadre particulier des atmosphères stellaires. Des expériences numériques, portant sur la validation des méthodes proposées et sur des cas ayant un sens astrophysique, sont présentées. La fin de ce chapitre est consacrée à la description de méthodes asymptotiques de décomposition du domaine permettant de surmonter la difficulté de résoudre cette équation lorsque le paramètre d'intégration varie dans un intervalle très large, ce qui est le cas dans certaines applications astrophysiques.

L'approximation isobare du système d'équations de bilan de masse, de quantité de mouvement, d'énergie et des espèces chimiques est une approximation appropriée pour représenter les écoulements réactifs à faible nombre de Mach. Dans cette approximation, qui néglige les phénomènes acoustiques, le mélange est hydrodynamiquement incompressible et les effets thermodynamiques conduisent à une compression uniforme du système. Nous présentons une nouvelle méthode numérique pour cette approximation. Une méthode de projection incrémentale, qui utilise la forme originale du bilan de masse, assure la discrétisation temporelle des équations de Navier-Stokes. La discrétisation spatiale est réalisée avec une méthode de volumes finis sur un maillage décalé de type MAC. Un schéma de décentrement d'ordre élevé est utilisé pour les flux convectifs. Nous associons à cette discrétisation, une méthode de raffinement local multi-niveaux, basée sur l'approche de Correction de Flux à l'Interface. Une première application concerne un écoulement forcé avec masse volumique variable donnée, imitant un problème de combustion. La deuxième application est le problème de convection naturelle, tout d'abord pour de faibles variations de température puis au-delà de la limite de validité de l'approximation de Boussinesq. Enfin, la troisième application est une flamme de diffusion laminaire. Pour chacun de ces cas-test, nous montrons la robustesse de la méthode numérique proposée, notamment vis à vis des variations de masse volumique. Et nous analysons le gain en précision obtenu par la méthode de raffinement local multi-niveaux.

Cette thèse porte sur l'aide à la construction de machines d'états UML de systèmes réactifs. Elle vise à définir un cadre théorique et pragmatique pour mettre en oeuvre une approche incrémentale caractérisée par une succession de phases de construction, évaluation et correction de modèles. Ce cadre offre des moyens de vérifier si un nouveau modèle est conforme à ceux définis durant les étapes précédentes sans avoir à demander une description explicite des propriétés à vérifier. Afin de pouvoir analyser les machines d'états, nous leur associons une sémantique LTS ce qui nous a conduit à définir une procédure de transformation automatique de machines d'états en LTS. Dans un premier temps, nous avons défini et implanté des techniques de vérification de relations de conformité de LTS (red, ext, conf, et confrestr). Dans un second temps, nous nous sommes intéressés à la définition d'un cadre de construction incrémentale dans lequel plusieurs stratégies de développement peuvent être mises en \oe uvre en s'assurant que le modèle final élaboré sera une implantation conforme à la spécification initiale. Ces stratégies reposent sur des combinaisons de raffinements qui peuvent être de deux types : le raffinement vertical pour éliminer l'indéterminisme et ajouter des détails ; le raffinement horizontal pour ajouter de nouvelles fonctionnalités sans ajouter d'indéterminisme. Enfin, nous transposons la problématique de construction incrémentale d'une machine d'états à la construction d'architectures dont les composants sont des machines d'états. Des conditions sont définies pour assurer la conformité entre des architectures dans le cas de la substitution de composants.

Le travail présenté dans cette thèse est une contribution au développement des méthodes à maillage dynamique pour la résolution de système d'EDP en mécanique des fluides. Plus précisément, on met au point des schémas de volumes finis pour des maillages non-structurés, mobiles et à topologie éventuellement variable, basés sur la méthode Godunov. L'addition et la soustraction de noeuds reposent sur une généralisation des méthodes à maillage dynamique à des cas de volumes naissants ou disparaissants. Dans une première partie, on se restreint aux équations hyperboliques en une dimension. On montre que pour l'advection linéaire, le schéma satisfait les propriétés classiques des méthodes de volumes finis (principe du maximum, décroissance de la variation totale, stabilité L²) sous certaines contraintes de type CFL. Afin de s'affranchir de ces restrictions, l'intégration en temps du système discrêt est réalisée par une formulation implicite. La seconde partie de ce travail porte sur l'extension des schémas en deux dimensions d'espace. Le modèle mathématique abordé est décrit par les équations d'Euler. Par ailleurs, on cherche à intégrer le schéma dans un code où le maillage s'adapte automatiquement et simplement. On introduit alors une distribution de forces, soit attractives, soit répulsives, entre les noeuds du maillage. Le mouvement des noeuds résulte de l'obtention de l'état d'équilibre sur le domaine. Le raffinement et le déraffinement reposent sur des critères locaux, comme le gradient. Le dernier travail de cette thèse est consacré à la simultation numérique de phénomènes d'interaction fluide-structure afin de valider les algorithmes proposés. L'application concrête visée ici eset m'écoulement compressible autour d'une aile d'avion en mouvement.