Dans le domaine médical, la numérisation des documents et l’utilisation des dossiers patient électroniques (DPE, ou en anglais EHR pour Electronic Health Record) offrent de nombreux avantages, tels que la facilité de recherche et de transmission de ces données. Les systèmes informatiques doivent reprendre ainsi progressivement le rôle traditionnellement tenu par les archivistes, rôle qui comprenait notamment la gestion des accès à ces données sensibles. Ces derniers doivent en effet être rigoureusement contrôlés pour tenir compte des souhaits de confidentialité des patients, des règles des établissements et de la législation en vigueur. SGAC, ou Solution de Gestion Automatisée du Consentement, a pour but de fournir une solution dans laquelle l’accès aux données du patient serait non seulement basée sur les règles mises en place par le patient lui-même mais aussi sur le règlement de l’établissement et sur la législation. Cependant, cette liberté octroyée au patient est source de divers problèmes : conflits, masquage des données nécessaires aux soins ou encore tout simplement erreurs de saisie. Pour effectuer ces vérifications, les méthodes formelles fournissent des moyens fiables de vérification de propriétés tels que les preuves ou la vérification de modèles. Cette thèse propose des méthodes de vérification adaptées à SGAC pour le patient : elle introduit le modèle formel de SGAC, des méthodes de vérifications de propriétés. Afin de mener ces vérifications de manière automatisée, SGAC est modélisé en B et Alloy ; ces différentes modélisations donnent accès aux outils Alloy et ProB, et ainsi à la vérification automatisée de propriétés via la vérification de modèles ou model checking. / Abstract : In healthcare, data digitization and the use of the Electronic Health Records (EHR) offer several benefits, such as the reduction of the space occupied by data, or the ease of data search or data exchanges. IT systems must gradually take up the archivist’s role by managing the accesses over sensitive data, which have to be compliant with patient wishes, hospital rules, as well as laws and regulations. SGAC, or Solution de Gestion Automatisée du Consentement (Automated Consent Management Solution), aims to provide a solution in which access to patient data would be based on patient rules, hospital rules and laws. However, the freedom granted to the patient can cause several problems : conflicts, concealment of crucial data needed to treat the patient adequately, and data-capture errors. Therefore, verification and validation of policies are essential : formal methods provide reliable ways, such as proofs or model checking, to conduct verifications of properties. This thesis provides verification methods applied on SGAC for the patient : it introduces the formal model of SGAC, methods to verify properties such as data access resolution, hidden data detection or redundant rule identification. Modeling of SGAC in B and Alloy provides access to the tools Alloy and ProB, and thus, automated property verification through model checking.

Satisfiability (SAT) and satisfiability modulo theories (SMT) solvers are high-performance automated propositional and first-order theorem provers, used as underlying tools in many formal verification and artificial intelligence systems. Theoretic and engineering advancement of solver technologies improved the performance of modern solvers; however, the increased complexity of those solvers calls for formal verification of those tools themselves. This thesis discusses two methods to formally certify SAT/SMT solvers. The first method is generating proofs from solvers and certifying those proofs. Because new theories are constantly added to SMT solvers, a flexible framework to safely add new inference rules is necessary. The proposal is to use a meta-language called LFSC, which is based on Edinburgh Logical Framework. SAT/SMT logics have been encoded in LFSC, and the encoding can be easily and modularly extended for new logics. It is shown that an optimized LFSC checker can certify SMT proofs efficiently. The second method is using a verified programming language to implement a SAT solver and verify the code statically. Guru is a pure functional programming language with support for dependent types and theorem proving; Guru also allows for efficient code generation by means of resource typing. A modern SAT solver, called versat, has been implemented and verified to be correct in Guru. The performance of versat is shown to be comparable with that of the current proof checking technology.

Le test à base de modèle, en particulier test basé sur des assistants à la preuve, réduit de façon transparente l'écart entre la théorie, le modèle formel, et l’implémentation d'un système informatique. Actuellement, les techniques de tests offrent une possibilité d'interagir directement avec de "vrais" systèmes : via différentes propriétés formelles, les tests peuvent être dérivés et exécutés sur le système sous test. Convenablement, l'ensemble du processus peut être entièrement automatisé. Le but de cette thèse est de créer un environnement de test de séquence à base de modèle pour les programmes séquentiels et concurrents. Tout d'abord une théorie générique sur les monades est présentée, qui est indépendante de tout programme ou système informatique. Il se trouve que notre théorie basée sur les monades est assez expressive pour couvrir tous les comportements et les concepts de tests. En particulier, nous considérons ici : les exécutions séquentielles, les exécutions concurrentes, les exécutions synchronisées, les exécutions avec interruptions. Sur le plan conceptuel, la théorie apporte des notions comme la notion raffinement de test, les cas de tests abstraits, les cas de test concrets, les oracles de test, les scénarios de test, les données de tests, les pilotes de tests, les relations de conformités et les critères de couverture dans un cadre théorique et pratique. Dans ce cadre, des règles de raffinement de comportements et d'exécution symbolique sont élaborées pour le cas générique, puis affinées et utilisées pour des systèmes complexes spécifique. Comme application pour notre théorie, nous allons instancier notre environnement par un modèle séquentiel d'un microprocesseur appelé VAMP développé au cours du projet Verisoft. Pour le cas d'étude sur la concurrence, nous allons utiliser notre environnement pour modéliser et tester l'API IPC d'un système d'exploitation industriel appelé PikeOS.Notre environnement est implémenté en Isabelle / HOL. Ainsi, notre approche bénéficie directement des modèles, des outils et des preuves formelles de ce système. / Formal methods can be understood as the art of applying mathematical reasoningto the modeling, analysis and verification of computer systems. Three mainverification approaches can be distinguished: verification based on deductive proofs,model checking and model-based testing.Model-based testing, in particular in its radical form of theorem proving-based testingcite{brucker.ea:2012},bridges seamlessly the gap between the theory, the formal model, and the implementationof a system. Actually,theorem proving based testing techniques offer a possibility to directly interactwith "real" systems: via differentformal properties, tests can be derived and executed on the system under test.Suitably supported, the entire process can fully automated.The purpose of this thesis is to create a model-based sequence testing environmentfor both sequential and concurrent programs. First a generic testing theory basedon monads is presented, which is independent of any concrete program or computersystem. It turns out that it is still expressive enough to cover all common systembehaviours and testing concepts. In particular, we consider here: sequential executions,concurrent executions, synchronised executions, executions with abort.On the conceptual side, it brings notions like test refinements,abstract test cases, concrete test cases,test oracles, test scenarios, test data, test drivers, conformance relations andcoverage criteria into one theoretical and practical framework.In this framework, both behavioural refinement rules and symbolic executionrules are developed for the generic case and then refined and used for specificcomplex systems. As an application, we will instantiate our framework by an existingsequential model of a microprocessor called VAMP developed during the Verisoft-Project.For the concurrent case, we will use our framework to model and test the IPC API of areal industrial operating system called PikeOS.Our framework is implemented in Isabelle/HOL. Thus, our approach directly benefitsfrom the existing models, tools, and formal proofs in this system.

Since the mid-1990s, formal verification has become increasingly important because it can provide guarantees that a software system is free of bugs and working correctly based on a provided model. Verification of biological and medical systems is a promising application of formal verification. Human neural networks have recently been emulated and studied as a biological system. Some recent research has been done on modelling some crucial neuronal circuits and using model checking techniques to verify their temporal properties. In large case studies, model checkers often cannot prove the given property at the desired level of generality. In this thesis, we provide a model using the Coq proof assistant and prove some properties concerning the dynamic behavior of some basic neuronal structures. Understanding the behavior of these modules is crucial because they constitute the elementary building blocks of bigger neuronal circuits. By using a proof assistant, we guarantee that the properties are true in the general case, that is, true for any input values, any length of input, and any amount of time. In this thesis, we define a model of human neural networks. We verify some properties of this model starting with properties of neurons. Neurons are the smallest unit in a human neuronal network. In the next step, we prove properties about functional structures of human neural networks which are called archetypes. Archetypes consist of two or more neurons connected in a suitable way. They are known for displaying some particular classes of behaviours, and their compositions govern several important functions such as walking, breathing, etc. The next step is verifying properties about structures that couple different archetypes to perform more complicated actions. We prove a property about one of these kinds of compositions. With such a model, there is the potential to detect inactive regions of the human brain and to treat mental disorders. Furthermore, our approach can be generalized to the verification of other kinds of networks, such as regulatory, metabolic, or environmental networks.

Software defects can frequently be traced to poorly-specified requirements. Many software teams manage their requirements using tools such as checklists and databases, which lack a formal semantic mapping to system behavior. Such a mapping can be especially helpful for safety-critical systems. Another limitation of many requirements analysis methods is that much of the analysis must still be done manually. We propose techniques that automate portions of the requirements analysis process, as well as clarify the syntax and semantics of requirements models using a variety of methods, including machine learning tools and our own tool, VeriCCM. The machine learning tools used help us identify potential model elements and verify their correctness. VeriCCM, a formalized extension of the causal component model (CCM), uses formal methods to ensure that requirements are well-formed, as well as providing the beginnings of a full formal semantics. We also explore the use of statecharts to identify potential abnormal behaviors from a given set of requirements. At each stage, we perform empirical studies to evaluate the effectiveness of our proposed approaches.

No description available.

L'injection de faute est une méthode bien connue pour évaluer la robustesse et détecter les vulnérabilités des systèmes. La détection des vulnérabilités créées par injection de fautes a été approchée par différentes méthodes. Dans la littérature deux approches existent: les approches logicielles et les approches matérielles. Les approches logicielles peuvent fournir une large et rapide couverture, mais ne garantissent pas la présence de vulnérabilité dans le système. Les approches matérielles sont incontestables dans leurs résultats, mais nécessitent l’utilisation de matériaux assez coûteux et un savoir-faire approfondi, qui ne permet tout de même pas dans la majorité des cas de confirmer le modèle de faute représentant l'effet créé. Dans un premier lieu, cette thèse se concentre sur l'approche logicielle et propose une approche automatisée qui emploie les techniques de la vérification formelle pour détecter des vulnérabilités créées par injection de faute au niveau binaire. L'efficacité de cette approche est montrée en l'appliquant à des algorithmes de cryptographie implémentés dans les systèmes embarqués. Dans un second lieu, cette thèse établit un rapprochement entre les deux approches logicielles et matérielles sur la détection de vulnérabilité d'injection de faute en comparant les résultats des expériences des deux approches. Ce rapprochement des deux approches démontre que: toutes les vulnérabilités détectées par l'approche logicielle ne peuvent pas être reproduites dans le matériel; les conjectures antérieures sur le modèle de faute par des attaques d'impulsion électromagnétique ne sont pas précises ; et qu’il y a un lien entre les résultats de l’approche logicielle et l'approche matérielle. De plus, la combinaison des deux approches peut rapporter une approche plus précise et plus efficace pour détecter les vulnérabilités qui peuvent être créées par injection de faute. / Fault injection is a well known method to test the robustness and security vulnerabilities of systems. Detecting fault injection vulnerabilities has been approached with a variety of different but limited methods. Software-based and hardware-based approaches have both been used to detect fault injection vulnerabilities. Software-based approaches can provide broad and rapid coverage, but may not correlate with genuine hardware vulnerabilities. Hardware-based approaches are indisputable in their results, but rely upon expensive expert knowledge, manual testing, and can not confirm what fault model represent the created effect. First, this thesis focuses on the software-based approach and proposes a general process that uses model checking to detect fault injection vulnerabilities in binaries. The efficacy and scalability of this process is demonstrated by detecting vulnerabilities in different cryptographic real-world implementations. Then, this thesis bridges software-based and hardware-based fault injection vulnerability detection by contrasting results of the two approaches. This demonstrates that: not all software-based vulnerabilities can be reproduced in hardware; prior conjectures on the fault model for electromagnetic pulse attacks may not be accurate; and that there is a relationship between software-based and hardware-based approaches. Further, combining both software-based and hardware-based approaches can yield a vastly more accurate and efficient approach to detect genuine fault injection vulnerabilities.

For modeling and reasoning about complex systems, symbolic methods provide a prominent way to tackle the state explosion problem. It is well known that for symbolic approaches based on binary decision diagrams (BDD), the ordering of BDD variables plays a crucial role for compact representations and efficient computations. We have extended the popular probabilistic model checker PRISM with support for automatic variable reordering in its multi-terminal-BDD-based engines and report on benchmark results. Our extensions additionally allow the user to manually control the variable ordering at a finer-grained level. Furthermore, we present our implementation of the symbolic computation of quantiles and support for multi-reward-bounded properties, automata specifications and accepting end component computations for Streett conditions.

Reactive systems are computer systems that maintain continuous interaction with the environment in which they operate. Such systems are nowadays part of our daily life: think about common yet critical applications like engine control units in automotive, aircraft autopilots, medical aided- devices, or micro-controllers in mass production. Clearly, any flaw in such critical systems can have catastrophic consequences. However, they exhibit several characteristics, like resource limitation constraints, real-time responsiveness, concurrency that make them difficult to implement correctly. To ensure the design of reactive systems that are dependable, safe, and efficient, researchers and industrials have advocated the use of so-called formal methods, that rely on mathematical models to express precisely and analyze the behaviors of these systems.Automata theory provides a fundamental notion such as languages of program executions for which membership, emptiness, inclusion, and equivalence problems allow us to specify and verify properties of reactive systems. However, these Boolean notions yield the correctness of the system against a given property that sometimes, falls short of being satisfactory answers when the performances are prone to errors. As a consequence, a common engineering approach is not just to verify that a system satisfies a property, but whether it does so within a degree of quality and robustness.This thesis investigates the expressibility, recognition, and robustness of quantitative properties for program executions.• Firstly, we provide a survey on languages definable by regular automata with Presburger definable constraints on letter occurrences for which we provide descriptive complexity. Inspired by this model, we introduce an expression formalism that mixes formula and automata to define quantitative languages \ie function from words to integers. These expressions use Presburger arithmetic to combine values given by regular automata weighted by integers. We show that quantitative versions of the classical decision problems such as emptiness, universality, inclusion, and equivalence are computable. Then we investigate the extension of our expressions with a ''Kleene star'' style operator. This allows us to iterate an expression over smaller fragments of the input word, and to combine the results by taking their iterated sum. The decision problems quickly turn out to be not computable, but we introduce a new subclass based on a structural restriction for which algorithmic procedures exist.• Secondly, we consider a notion of robustness that places a distance on words, thus defining neighborhoods of program executions. A language is said to be robust if the membership satisfiability cannot differ for two ''close'' words, and that leads to robust versions of all the classical decision problems. Our contribution is to study robustness verification problems in the context of weighted transducers with different measures (sum, mean-payoff, and discounted sum). Here, the value associated by the transducer to rewrite a word into another denotes the cost of the noise that this rewriting induce. For each measure, we provide algorithms that determine whether a language is robust up to a given threshold of error and we solve the synthesis of the robust kernel for the sum measure. Furthermore, we provide case studies including modeling human control failures and approximate recognition of type-1 diabetes using robust detection of blood sugar level swings.• Finally, we observe that algorithms for structural patterns recognition of automata often share similar techniques. So, we introduce a generic logic to express structural properties of automata with outputs in some monoid, in particular, the set of predicates talking about the output values is parametric. Then, we consider three particular automata models (regular automata, transducers, and automata weighted by integers) and instantiate the generic logic for each of them. We give tight complexity results for the three logics with respect to the pattern recognition problem. We study the expressiveness of our logics by expressing classical structural patterns characterizing for instance unambiguity and polynomial ambiguity in the case of regular automata, determinizability, and finite-valuedness in the case of transducers and automata weighted by integers. As a consequence of our complexity results, we directly obtain that these classical properties can be decided in logarithmic space. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Over the last decades, autonomous robots have been considered in a variety of applications such  as persistent monitoring, package delivery and cooperative transportation. These applications often require the satisfaction of a set of complex tasks that need to be possibly performed in a timely manner. For example, in search and rescue missions, UAVs are expected to cover a set of regions within predetermined time intervals in order to increase the probability of identifying the victims of an accident. Spatio-temporal tasks of this form can be easily expressed in Signal Temporal Logic (STL), a predicate language that allow us to formally introduce time-constrained tasks such as visit area A between 0 and 5 min or robot 1 should move in a formation with robot 2 until robot 1 reaches region B between 5 and 20 sec. Existing approaches in control under spatio-temporal tasks encode the STL constraints using mixed-integer expressions. In the majority of these works, receding horizon schemes are designed and long planning horizons are considered that depend on the temporal constraints of the STL tasks. As a result, the complexity of these problems may increase with the number of the tasks or the length of the time interval within which a STL task needs to be satisfied. Other approaches, consider a limited STL fragment and propose computationally efficient feedback controllers that ensure the satisfaction of the STL task with a minimum, desired robustness. Nevertheless, these approaches do not consider actuation limitations that are always present in real-world systems and thus, yield controllers of arbitrarily large magnitude.  In this thesis, we consider the control problem under spatio-temporal constraints for systems that are subject to actuation limitations. In the first part, receding horizon control schemes (RHS) are proposed that ensure the satisfaction or minimal violation of a given set of STL tasks. Contrary to existing approaches, the planning horizon of the RHS scheme can be chosen independent of the STL task and hence, arbitrarily small, given the initial feasibility of the problem. Combining the advantages of the RHS and feedback strategies, we encode the STL tasks using control barrier functions that are designed either online or offline and design controllers that aim at maximizing the robustness of the STL task. The recursive feasibility property of the framework is established and a lower bound on the violation of the STL formula is derived. In the next part, we consider a multi-agent system that is subject to a STL task whose satisfaction may involve a large number of agents in the team. Then, the goal is to decompose the global task into local ones the satisfaction of each one of which  depends only on a given sub-team of agents. The proposed decomposition method enables the design of decentralized controllers under local STL tasks avoiding unnecessary communication among agents.  In the last part of the thesis, the coordination problem of multiple platoons is considered and related tasks such as splitting, merging and distance maintenance are expressed as Signal Temporal Logic tasks. Then, feedback control techniques are employed ensuring the satisfaction the STL formula, or alternatively minimal violation in presence of actuation limitations. / De senaste ̊artiondena har autonoma robotar sett en rad nya användningsområden, såsom ̈overvakning, paketleverans och kooperativ transport. Dessa innebär ofta att en samling komplexa uppgifter måste lösas på kort tid. Inom Search and Rescue (SAR), till exempel, krävs att drönare hinner genomsöka vissa geografiska regioner inom givna tidsintervall. Detta för att ̈oka chansen att identifierade drabbade vid en olycka. Den här typen av uppgift i tid och rum (spatio-temporal) kan enkelt uttryckas med hjälp av Signal Temporal Logic (STL). STL ̈är ett språk som tillåter oss att på ett formellt sätt formulera tidsbegränsade uppgifter, såsom besök område A mellan o och 5 minuter, eller robot 1 ska röra sig i formationtillsammans med robot 2 till dess att robot 1 når område B mellan 5 och 20 sekunder. Nuvarande lösningar till styrproblem av spatio-temporal-typen kodar STL-begränsningar med hjälp av mixed-integer-uttryck. Majoriteten av lösningarna involverar receding-horizon-metoder med långa tidshorisonter som beror av tidsbegränsningarna i STL-uppgifterna. Detta leder till att problemens komplexitet ̈ökar med antalet deluppgifter inom och tiden för STL-uppgifterna. Andra lösningar bygger på restriktiva STL-fragment och beräkningsmässigt effektiva ̊aterkopplingsregulatorer som garanterar STL-begränsningarna med minimal önskad robusthet. Dessvärre tar dessa sällan hänsyn till fysiska begräsningar hos regulatorn och ger ofta godtyckligt stora styrsignaler. I den här licentiatuppsatsen behandlar vi styrproblem med begräsningar i rum och tid, samt den ovan nämnda typen av fysiska regulatorbegränsningar. I den första delen presenterar vi receding-horizon-metoder (RHS) som uppfyller kraven i STL-uppgifter, eller minimalt bryter mot dessa. Till skillnad från tidigare lösningar så kan tidshorisonten i våra RHS-metoder väljas oberoende av STL-uppgifterna och därmed göras godtyckligt kort, så länge ursprungsproblemet ̈ar lösbart. Genom att formulera STL-uppgifterna som control barrier funktioner kan vi kombinera fördelarna hos RHS och ̊återkoppling. Vi härleder en rekursiv lösbarhetsegenskap och en undre gräns på ̈overträdelsen av STL-kraven. I den andra delen behandlar vi multi-agent-system med uppgifter i tid och rum som berör många agenter. Målet är att bryta ner den globala uppgiften i fler men enklare lokala uppgifter som var och en bara involverar en given delmängd av agenterna. Vår nedbrytning till ̊åter oss att konstruera decentraliserade regulatorer som löser lokala STL-uppgifter, och kan i och med det markant minska kommunikationskostnaderna i j̈ämförelse med centraliserad styrning. I den sista delen av uppsatsen behandlar vi samordning av flera grupper. Vi uttrycker uppgifter såsom delning, sammanslagning och avståndshållning med hjälp av STL, och utnyttjar sedan ̊aterkoppling för att uppfylla eller minimalt bryta mot kraven. / <p>QC 20220311</p>