Dans les domaines critiques d'application de l'informatique, il peut être vital de disposer d'un génie logiciel qui soit capable de garantir le bon fonctionnement des systèmes produits. Dans ce contexte, la méthode B évènementielle promeut le développement de modèles abstraits du système à concevoir et l'utilisation de démonstrations formelles ainsi que de la relation de raffinement entre les modèles. Notre but est de pouvoir travailler sur des systèmes ayant des aspects temporels quantitatifs (propriétés et contraintes de temps) en restant au sein du cadre défini par la méthode B qui a déjà montré son efficacité par ailleurs, mais qui ne dispose pas de concepts spécifiques pour le temps. C'est ainsi que nous proposons l'introduction des contraintes de temps par le raffinement, ceci permet de respecter la philosophie de la méthode B et de systématiser cette approche par la formalisation de patrons de raffinement. Nos différentes modélisations du temps sont proposées sous la forme de patron à réappliquer sur le système à étudier. Nous pouvons donc étudier progressivement le système à partir d'une abstraction non-temporelle afin de le valider progressivement et de distribuer la difficulté de la preuve en plusieurs étapes. L'introduction des aspects temporels ne se fait que lorsque cela est nécessaire lors du processus de développement prouvé. Nous avons validé cette approche sur des études de cas réalistes en utilisant les outils logiciels de démonstration formelle de la méthode B. / Critical application domains of computer science require the use of software engineering methods that ensure that the resulting systems behave according to their intended functionality. In this context, the Event-B method uses an approach based on stepwise refinement, starting with abstract, high-level models of the system under development. The system models corresponding to different levels of abstraction are related by precise and formally proved refinement relations. Our goal is to extend this approach to systems whose requirements include quantitative real-time aspects (properties and temporal constraints). In this way, we benefit from the established qualities of the B method, while extending its scope to real-time aspects that it does not yet cover. More specifically, we propose to introduce time constraints by refinement, respecting the overall approach of the B method, and to systematize our approach by the use of refinement patterns. Different time models are represented by generic patterns that can be reused for the development of concrete systems. In this way we can gradually develop the system from a non-temporal abstraction and progressively validate its correctness, distributing the burden of proof is over several refinement steps. Temporal aspects are introduced step by step and only when necessary. We validated this approach using several real-world case studies, using the software tools for formal proof developed for the Event-B method.

L'analyse statique a pour but de vérifier qu'un programme a le comportement souhaité c.à.d. satisfait des propriétés de sûreté. Toutefois, inférer les propriétés vérifiées par un programme est un problème difficile : le théorème de Rice énonce que toute propriété non triviale d'un langage de programmation Turing-complet est indécidable. Afin de contourner cette difficulté, les analyses statiques effectuent des approximations des comportements possibles du programme. La théorie de l'interprétation abstraite permet de donner un cadre formel à ces approximations. Cette théorie, introduite par Cousot & Cousot propose un cadre d'approximation basé sur la notion de treillis, de connexion de Galois et de calculs de points fixes par itération. Ce cadre permet de définir la qualité des approximations effectuées et notamment la notion de meilleure approximation. À l'opposé, les notions quantitatives n'apparaissent pas naturellement dans ce cadre. Nous nous sommes donc posés la question de l'inférence, par analyse statique, de propriétés s'exprimant de manière quantitative (telles que l'utilisation de la mémoire ou le temps d'exécution). / Static analysis aims to verify that programs behave correctly i.e. satisfy safety properties. However, generating properties verified by a program is a difficult problem : Rice’s theorem states that any non-trivial property about the language recognized by a Turing machine is undecidable. In order to avoid this difficulty, static analyses approximate the possible behaviours of the program. Abtract interpretation theory defines a formal framework for approximating programs. This theory, introduced by Cousot & Cousot is based on the mathematical structure of lattices, Galois connections and iterative fixpoints calculus. This framework defines the notion of correct approximation and allows for qualitatively compare approximations. On the contrary, it is not suitable for handling quantitative properties (such as memory usage and execution time).

La propension des systèmes informatiques à subir des défaillances matérielles est à l'origine d'une recherche abondante afin de concevoir des systèmes dits tolérants aux pannes. Le procédé couramment retenu consiste à procéder à des réplications, donnant alors naissance à ce que l'on nomme un système distribué. La question se pose alors de savoir si l'on peut garantir que les multiples copies sont cohérentes entre elles. Ainsi, la recherche d'un accord devient-elle un problème à résoudre, à portée paradigmatique : le Consensus. Or, la complexité des algorithmes de Consensus rend la tache ardue : il n'est donc pas rare que l'on commette des erreurs lors de leur conception. De là découle l'idée, développée depuis plus de trente ans, de recourir à des procédés de vérification mécanique des algorithmes et de leurs preuves de correction. Ces procédés prennent place parmi ce que l'on désigne usuellement comme étant des méthodes formelles. C'est à la croisée des recherches en algorithmique distribuée et en méthodes formelles que se situent nos travaux. Plus spécifiquement, il s'agit de faire usage d'un logiciel de certification formelle, Isabelle/HOL, afin de garantir l'exactitude des preuves de correction d'algorithmes de Consensus exprimés dans un cadre formel uniforme du nom de Heard-Of, proposé en 2009 par Charron-Bost et Schiper. Nous montrons que, du fait de leur expression dans un même cadre formel, et du fait de leur proximité, suivant les cas, soit de conception (nombre de rondes, recours à des mécanismes de vote, ...) soit de forme syntaxique, soit d'hypothèses de fonctionnement (synchronisme partiel, ...), ces algorithmes présentent des preuves dont une part conséquente d?arguments sont communs. Cela permet de copier certains d'entre eux d'une preuve à l'autre, afin de réduire l'effort de certification : ces arguments peuvent alors être automatiquement évalués par la machine pour chacun d'entre eux, l'utilisateur n'ayant à intervenir que là où celle-ci est en peine, c'est-à-dire lorsque les différences algorithmiques induisent qu'il faille réviser les détails de l'argumentation. L'exposé que nous faisons de la certification que nous avons effectuée pour six algorithmes distribués dédiés à la résolution du problème du Consensus illustre cette démarche. Par conséquent, nous présentons d'abord les portions communes des démonstrations, puis détaillons ce qui est propre à chacune, l'objectif n'étant pas de permettre une lecture linéaire de chaque démonstration mais de mettre en évidence notre proposition / Computer systems fail. Whatever the reason of these failures, it has been a widespread approach to try and increase the faults-tolerance of a computer system through its replication. The resulting system is said to be a distributed one, in which replicas have to be kept consistent with each others. Hence, reaching agreement, and Consensus in particular, becomes the problem to solve - indeed, the paradigm. Solving Consensus (under various assumptions) is a hard task : algorithms designed on this purpose are subtle and proving their being correct is error-prone - whenever they are, which occasionally appears not to be the case. For more that thirty years, researchers interested in what is called Formal Methods have been working on mechanizing the verification process, in order to increase confidence in the correctness of (distributed) algorithms. The work we present here is at the intersection of distributed algorithms and formal methods. We use the Isabelle/HOL software to certify the correctness proof of various Consensus algorithms expressed in a uniform framework based on the Heard-Of Model, introduced by Charron-Bost and Schiper in 2009. Expressed in a common model, these algorithms, which, depending on the case, share some common mecanisms (number of steps, intermediate votes, ...), some elements of syntax, or types of assumptions (partial synchronism...), can be proved using some common arguments. As a consequence, the certification effort can be reduced by copying some intermediate lemmas from one proof to another and let the computer automatically parse them until some manual adaptation is required. This lead to the idea of certifying the correctness of multiple algorithms all together, instead of proving them one after the other, as one would do on paper in a traditional way. The effort of translation in the formal language of the proof assistant is then possibly reduced. Of course, each proof will also contain specific arguments, which will have to be isolated and translated into the software. Here, we illustrate this proposition through the presentation of formal certificates of correctness for six Consensus algorithms. As a consequence, on should not expect to find here a comprehensive linear presentation of each proof : we first show the arguments shared by multiple proofs, followed by those which are specific to each o them

Safety-critical systems depend on the fact that their software components provide services that behave correctly (i.e. satisfy their requirements). Additionally, in many cases, these systems have to be adapted or reconfigured in case of failures or when changes in requirements or in quality of service occur. When these changes appear at the software level, they can be handled by the notion of substitution. Indeed, the software component of the source system can be substituted by another software component to build a new target system. In the case of safety-critical systems, it is mandatory that this operation enforces that the new target system behaves correctly by preserving the safety properties of the source system during and after the substitution operation. In this thesis, the studied systems are modeled as state-transition systems. In order to model system substitution, the Event-B method has been selected as it is well suited to model such state-transition systems and it provides the benefits of refinement, proof and the availability of a strong tooling with the Rodin Platform. This thesis provides a generic model for system substitution that entails different situations like cold start and warm start as well as the possibility of system degradation, upgrade or equivalence substitutions. This proposal is first used to formalize substitution in the case of discrete systems applied to web services compensation and allowed modeling correct compensation. Then, it is also used for systems characterized by continuous behaviors like hybrid systems. To model continuous behaviors with Event-B, the Theory plug-in for Rodin is investigated and proved successful for modeling hybrid systems. Afterwards, a correct substitution mechanism for systems with continuous behaviors is proposed. A safety envelope for the output of the system is taken as the safety requirement. Finally, the proposed approach is generalized, enabling the derivation of the previously defined models for web services compensation through refinement, and the reuse of proofs across system models.

Les architectures des systèmes embarqués des nouvelles générations d'avions civils et militaires tendent à s'organiser autour d'une plateforme avionique constituée de calculateurs interconnectés par un réseau central. Ce type d'architecture a fait apparaitre le besoin de développer de nouvelles méthodes de conception afin d'assister le dialogue entre les concepteurs des fonctions à embarquer (commandes de vol, gestion de l'énergie, ...) et les architectes de la plateforme avionique. Il est, en particulier, primordial de s'assurer que l'allocation des ressources de la plateforme aux fonctions embarquées respecte les exigences de sûreté de fonctionnement propres aux systèmes avioniques. Dans un premier temps, un cadre général a été proposé pour modéliser et vérifier l'effet de l'allocation des ressources d'une plateforme avionique du point de la sûreté de fonctionnement. Ce cadre est fondé sur l'utilisation du langage AltaRica pour décrire formellement la propagation des défaillances au sein de systèmes embarqués et des outils associés à ce langage (model-checking, génération de séquences et d'arbres de défaillances) pour vérifier la tenue des exigences de sûreté de fonctionnement. Ce cadre a été utilisé pour étudier, d'une part, l'allocation d'équipements informatiques aux fonctions de systèmes embarqués, et d'autre part, les placements des équipements au sein de l'avion en tenant compte de risques tels que l'éclatement d'un pneu ou l'explosion d'un moteur. Dans un second temps, la génération d'allocations respectant les exigences de sûreté de fonctionnement a été étudiée. L'approche retenue est fondée sur l'expression de contraintes d'allocation sous forme d'inégalités linéaires entières et sur l'utilisation de techniques de résolution de ces contraintes. Plusieurs types de contraintes (ségrégation, co-location, exclusion, ...) sont pris en compte. De plus, des critères d'optimisation permettent de guider la résolution des contraintes de façon à proposer des allocations les plus pertinentes du point de vue des besoins des systèmes aéronautiques. Finalement, une approche intégrant les techniques de vérification et de génération a été proposée. La première étape consiste à vérifier un modèle des fonctions embarquées qui est indépendant de la plateforme avionique. Il est possible d'extraire automatiquement des contraintes d'allocation à partir des résultats de cette vérification. L'étape de résolution de contraintes génère alors une allocation sûre. Les travaux sont illustrés par deux études de cas industrielles : une fonction de suivi de terrain d'un avion de chasse et un système de génération et de distribution hydraulique d'un avion de type A320. / Abstract

La quantité croissante de données traitées par les logiciels rend légitime le besoin de garanties de confidentialité. La propriété de non-interférence assure qu'un programme ne fuite pas de données privées vers une sortie publique. Nous proposons une méthode pour construire, une multisémantique annotée capable de capturer la propriété de non-interférence pour aider à prouver formellement des analyseurs. Nous fournissons un théorème prouvé indiquant que les annotations capturent correctement la non-interférence. Le théorème de correction permet de prouver un analyseur sans s'appuyer sur la définition de non-interférence mais sur les annotations. / Because of the increasing quantity of data processed by software, the need for privacy guarantees is legitimate. The property of non-interference ensures that a program does not leak private data to a public output. We propose a framework to build an annotated multisemantics able to capture the non-interference property to help formally prove analysers. The framework comes with a proved theorem stating that the annotations correctly capture non-interference. The correctness theorem allows to prove an analyser without relying on the definition of non-interference but on the annotations.

Les problèmes logiciels sont frustrants et diminuent l’expérience utilisateur. Par exemple, la fuite de données bancaires, la publication de vidéos ou de photos compromettantes peuvent affecter gravement une vie. Comment éviter de telles situations ? Utiliser des tests est une bonne stratégie, mais certains bogues persistent. Une autre solution est d’utiliser des méthodes plus mathématiques, aussi appelées méthodes formelles. Parmi celles-ci se trouve la sémantique dénotationnelle. Elle met la sémantique extraite de vos logiciels préférés en correspondance avec des objets mathématiques. Sur ceux-ci, des propriétés peuvent être vérifiées. Par exemple, il est possible de déterminer, sous certaines conditions, si votre logiciel donnera une réponse. Pour répondre à ce besoin, il est nécessaire de s’intéresser à des théories mathématiques suffisamment riches. Parmi les candidates se trouvent le sujet de ce mémoire : la théorie des domaines. Elle offre des objets permettant de modéliser formellement les données et les instructions à l’aide de relations d’ordre. Cet écrit présente les concepts fondamentaux tout en se voulant simple à lire et didactique. Il offre aussi une base solide pour des lectures plus poussées et contient tout le matériel nécessaire à sa lecture, notamment les preuves des énoncés présentés. / Bugs in programs are definitively annoying and have a negative impact on the user experience. For example, leaks of bank data or leaks of compromising videos or photos have a serious effect on someone’s life. How can we prevent these situations from happening? We can do tests, but many bugs may persist. Another way is to use mathematics, namely formal methods. Among them, there is denotational semantics. It links the semantics of your favorite program to mathematical objects. On the latter, we can verify properties, e.g., absence of bugs. Hence, we need a rich theory in which we can express the denotational semantics of programs. Domain Theory is a good candidate and is the main subject of this master thesis. It provides mathematical objects for data and instructions based on order relations. This thesis presents fundamental concepts in a simple and pedagogical way. It is a solid basis for advanced readings as well as containing all the needed knowledge for its reading, notably proofs for all presented statements.

Mes travaux de recherche portent sur les modèles de programmation distribuée, principalement par objets et composants. Dans ce domaine, j'ai travaillé à fournir des outils facilitant la programmation d'applications distribuées à large échelle et vérifiant la correction de leur comportement. Pour faciliter la programmation d'applications distribuées je me suis intéressé à la mise au point de langages avec un fort niveau d'abstraction: objets actifs, squelettes algorithmiques, composants. Afin de vérifier la correction du comportement d'une application j'ai collaboré à la mise au point d'outils de spécification et de vérification comportementales d'applications distribuées. Mes travaux ont pour but de fournir un modèle formel des langages de programmations, des bibliothèques, et des environnements d'exécution fournies au programmeur afin de garantir un comportement sûr des applications distribuées. Ma thèse m'a permis de mettre au point le calcul ASP modélisant lecomportement des objets actifs et des futurs. Depuis, nous avons créé une version fonctionnelle de ce calcul que nous avons modélisé en Isabelle/HOL. Aussi j'ai fortement contribué à la définition d'un modèle à composants distribués -- le GCM (Grid Component model)--, à sa formalisation et à son utilisation pour programmer des composants adaptables ou autonomes. Enfin, j'ai contribué à la spécification et la vérification comportementale des programmes utilisant des objets actifs et des composants afin de garantir la sûreté de leur exécution. Actuellement, nous travaillons à la fois à une extension multi-threadée du modèle à objets actifs mieux adaptée aux machines multi-coeurs, et à l'utilisation de méthodes formelles pour mettre au point et prouver la correction d'un algorithme de diffusion pour réseau pair-à-pair de type CAN (Content Adressable Network). Ce manuscrit fournit une vue d'ensemble de tous ces travaux.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Le contrôle d'accès permet de spécifier une partie de la politique de sécurité d'un SI (système d'informations). Une politique de CA (Contrôle d'accès) permet de définir qui a accès à quoi et sous quelles conditions. Les concepts fondamentaux utilisés en CA sont : les permissions, les interdictions (ou prohibitions), les obligations et la SoD (séparation des devoirs). Les permissions permettent d'autoriser une personne à accéder à des ressources. Au contraire les prohibitions interdisent à une personne d'accéder à certaines ressources. Les obligations lient plusieurs actions. Elles permettent d'exprimer le fait qu'une action doit être réalisée en réponse à une première action. La SoD permet de sécuriser une procédure en confiant la réalisation des actions composant cette procédure à des agents différents. Différentes méthodes de modélisation de politiques de contrôle d'accès existent. L'originalité de la méthode EB3Sec issue de nos travaux repose sur deux points :- permettre d'exprimer tous les types de contraintes utilisées en CA dans un même modèle,- proposer une approche de modélisation basée sur les événements. En effet, aucune des méthodes actuelles ne présente ces deux caractéristiques, au contraire de la méthode EB3Sec. Nous avons défini un ensemble de patrons, chacun des patrons correspond à un type de contraintes de CA. Un modèle réalisé à l'aide de la méthode EB3Sec peut avoir différentes utilisations :- vérification et simulation,- implémentation. La vérification consiste à s'assurer que le modèle satisfait bien certaines propriétés, dont nous avons défini différents types. Principalement, les blocages doivent être détectés. Ils correspondent à des situations où une action n'est plus exécutable ou à des situations où plus aucune action n'est exécutable. Les méthodes actuelles des techniques de preuves par vérification de modèles ne permettent pas de vérifier les règles dynamiques de CA. Elles sont alors combinées à des méthodes de simulation. Une fois qu'un modèle a été vérifié, il peut être utilisé pour implémenter un filtre ou noyau de sécurité. Deux manières différentes ont été proposées pour réaliser cette implémentation : transformer le modèle EB3Sec vers un autre langage, tel XACML, possédant une implémentation ayant déjà atteint la maturité ou réaliser un noyau de sécurité utilisant le langage EB3Sec comme langage d'entrée / Access control allows one to specify a part of the security Policy of an IS (information system). An AC (access control) policy defines which conditions must old for someone to have access to something. Main concepts used in AC are: permissions, prohibitions, obligations and SoD (separation of duty). Permissions allow someone to access to some resources. On the opposite, prohibitions forbid users to have access to some resources. Obligations link at least two actions: when a user performs an action, he must perform another one. SoD secures an action by dividing it in different tasks, and entrusting the execution of these tasks to different users. Many AC policies modelling methods already exist. The main particularities of the EB3Sec methods are:- All AC concepts can be expressed in a unique model,- This modelling method is event-based. No existing AC modelling methods presents these two characteristics. We define a set of patterns; each pattern corresponds to a specific AC constraint. An EB3Sec model can be used for different purposes:- Simulation and verification,- Implementation.Verifying a model consists in checking that the model complies with some properties that we have defined. Mainly, blocking must be detected. Blocking corresponds to a step of execution where no action can be executed or to situations where an action cannot be performed anymore. Current model checking methods cannot be used to check properties on dynamic AC constraints. Thus, model-checking techniques are combined to simulation techniques. Once a model is verified, it can be transformed in an implementation. To implement an EB3Sec model two ways can be considered: the EB3Sec model can be translated into an other language, such as XACML, which possesses a mature implementation, or a security kernel using EB3Sec as input language can be implemented