Since its introduction in 1999, bounded model checking (BMC) has quickly become a serious and indispensable tool for the formal verification of hardware designs and, more recently, software. By leveraging propositional satisfiability (SAT) solvers, BMC overcomes some of the shortcomings of more conventional model checking methods. In model checking we automatically verify whether a state transition system (STS) describing a design has some property, commonly expressed in linear temporal logic (LTL). BMC is the restriction to only checking the looping and non-looping runs of the system that have bounded descriptions. The conventional BMC approach is to translate the STS runs and LTL formulae into propositional logic and then conjunctive normal form (CNF). This CNF expression is then checked by a SAT solver. In this thesis we study the effect on the performance of BMC of changing the translation to propositional logic. One novelty is to use a normal form for LTL which originates in resolution theorem provers. We introduce the normal form conversion early on in the encoding process and examine the simplifications that it brings to the generation of propositional logic. We further enhance the encoding by specialising the normal form to take advantage of the types of runs peculiar to BMC. We also improve the conversion from propositional logic to CNF. We investigate the behaviour of the new encodings by a series of detailed experimental comparisons using both hand-crafted and industrial benchmarks from a variety of sources. These reveal that the new normal form based encodings can reduce the solving time by a half in most cases, and up to an order of magnitude in some cases, the size of the improvement corresponding to the complexity of the LTL expression. We also compare our method to the popular automata-based methods for model checking and BMC.

Estruturas de tratamento de exceção são extremamente comuns em softwares desenvolvidos em linguagens modernas, como Java, e afetam de forma contundente o comportamento de um software quando exercitadas. Apesar destas duas características, as principais técnicas de verificação, teste de software e verificação formal, e as ferramentas a elas vinculadas, tendem a negligenciar o comportamento excepcional. Alguns dos fatores que levam a esta negligência são a não especificação do comportamento excepcional em termos de projeto e a consequente implementação das estruturas de tratamento com base no julgamento individual de cada programador. Isto resulta na não consideração de partes expressivas do código em termos de verificação e, consequentemente, a possibilidade de não serem detectados erros relativos tanto às próprias estruturas de tratamento quanto às estruturas de código vinculadas a estas. A fim de abordar este problema, propomos uma técnica, baseada em model checking, que automatiza o processo de exercício de caminhos excepcionais. Isto permite que seja observado o comportamento de um software quando da ocorrência de uma exceção. Pretendemos, com esta técnica, dar suporte para que seja aplicado aos caminhos que representam o comportamento excepcional de um software as mesmas técnicas de detecção de erros que são aplicadas aos caminhos que representam o comportamento normal e, com isso, agregar um aumento na qualidade do desenvolvimento de software. / Software developed in modern languages, such as Java, commonly present structures of exception handling. These structures, when exercised, may affect the software behavior. Despite these two characteristics, the main verification techniques, software testing and formal verification and the tools related to them, tend to neglect the exceptional behavior. The nonexistent specification of software exceptional behaviors at the design level, and, the subsequent implementation of exception handling based on the judgment of each programmer, are some factors that lead to this neglect. These factors result in the non-consideration of the expressive parts of the code in verification terms and, consequently, the impossibility of errors detection concerning either the exception treatment structures or the code structures linked to them. Taking this fact into consideration, we propose a technique based on the model checking process, which automates the process of exercising exceptional paths to address this problem. This allows the observation of the software behavior when an exception occurs. With this technique, we intend to support the application of the same error detection techniques for program normal behavior paths to the paths that represent the software exceptional behavior. Therefore, using the proposed technique, we aim to increase the software development quality.

The complex behavior of computer systems offers many challenges for formal verification. The analysis quickly becomes difficult as the number of participating processes increases. A parameterized system is a family of systems parameterized on a number n, typically representing the number of participating processes. The uniform verification problem — to check whether a property holds for each instance — is an infinite-state problem. The automated analysis of parameterized and infinite-state systems has been the subject of research over the last 15–20 years. Much of the work has focused on safety properties. Progress in verification of liveness properties has been slow, as it is more difficult in general. In this thesis, we consider verification of parameterized and infinite-state systems, with an emphasis on liveness, in the verification framework called regular model checking (RMC). In RMC, states are represented as words, sets of states as regular expressions, and the transition relation as a regular relation. We extend the automata-theoretic approach to RMC. We define a specification logic sufficiently strong to specify systems representable using RMC, and linear temporal logic properties of such systems, and provide an automatic translation from a specification into an analyzable model. We develop acceleration techniques for RMC which allow more uniform and automatic verification than before, with greater power. Using these techniques, we succeed to verify safety and liveness properties of parameterized protocols from the literature. We present a novel reachability based verification method for verification of liveness, in a general setting. We implement the method for RMC, with promising results. Finally, we develop a framework for the verification of dynamic networks based on graph transformation, which generalizes the systems representable in RMC. In this framework we verify the latest version of the DYMO routing protocol, currently being considered for standardization by the IETF.

Un comportement distribué peut être décrit avec un multi-ensemble partiellement ordonné (pomset). Bien que compacts et très intuitifs, ces modèles sont difficiles à vérifier. La principale technique utilisée dans cette thèse est de ramener les problèmes de décision de la logique MSO sur les pomsets à des problèmes de décision sur les mots. Les problèmes considérés sont la satisfiabilité et la vérification. Le problème de la vérification pour une formule donnée et un pomset consiste à décider si une interprétation est vraie, et le problème de satisfiabilité consiste à décider si un pomset répondant à la formule existe. Le problème de satisfiabilité de MSO sur pomsets est indécidable. Une procédure de semi-décision peut apporter des solutions pour de nombreux cas, en dépit du fait qu'elle peut ne pas terminer. Nous proposons un nouveau modèle, que l'on appelle ⌈-Pomset, pouvant rendre l'exploration des pomsets possible. Par conséquent, si une formule est satisfiable alors notre approche mènera éventuellement à la détection d'une solution. De plus, en utilisant les ⌈-Pomsets comme modèles pour systèmes concurrents, le model-checking de formules ordre partiel sur systèmes concurrents est décidable. Certaines expérimentations ont été faites en utilisant l'outil MONA. Nous avons comparé aussi la puissance expressive de certains modèles classiques de la concurrence comme les traces de Mazurkiewicz avec les ⌈-Pomsets. / Multiset of partially ordered events (pomset) can describe distributed behavior. Although very intuitive and compact, these models are difficult to verify. The main technique used in this thesis is to bring back decision problems for MSO over pomsets to problems for MSO over words. The problems considered are satisfiability and verification. The verification problem for a formula and a given pomset consists in deciding whether such an interpretation exists, and the satisfiability problem consists in deciding whether a pomset satisfying the formula exists. The satisfiability problem of MSO over pomsets is undecidable. A semi-decision procedures can provide solutions for many cases despite the fact that they may not terminate. We propose a new model, so called ⌈-Pomset, making the exploration of pomsets space possible. Consequently, if a formula is satisfiable then our approach will eventually lead to the detection of a solution. Moreover, using ⌈-Pomsets as models for concurrent systems, the model checking of partial order formulas on concurrent systems is decidable. Some experiments have been made using MONA. We compare also the expressive power of some classical model of concurrency such as Mazurkiewicz traces with our ⌈-Pomsets.

Estruturas de tratamento de exceção são extremamente comuns em softwares desenvolvidos em linguagens modernas, como Java, e afetam de forma contundente o comportamento de um software quando exercitadas. Apesar destas duas características, as principais técnicas de verificação, teste de software e verificação formal, e as ferramentas a elas vinculadas, tendem a negligenciar o comportamento excepcional. Alguns dos fatores que levam a esta negligência são a não especificação do comportamento excepcional em termos de projeto e a consequente implementação das estruturas de tratamento com base no julgamento individual de cada programador. Isto resulta na não consideração de partes expressivas do código em termos de verificação e, consequentemente, a possibilidade de não serem detectados erros relativos tanto às próprias estruturas de tratamento quanto às estruturas de código vinculadas a estas. A fim de abordar este problema, propomos uma técnica, baseada em model checking, que automatiza o processo de exercício de caminhos excepcionais. Isto permite que seja observado o comportamento de um software quando da ocorrência de uma exceção. Pretendemos, com esta técnica, dar suporte para que seja aplicado aos caminhos que representam o comportamento excepcional de um software as mesmas técnicas de detecção de erros que são aplicadas aos caminhos que representam o comportamento normal e, com isso, agregar um aumento na qualidade do desenvolvimento de software. / Software developed in modern languages, such as Java, commonly present structures of exception handling. These structures, when exercised, may affect the software behavior. Despite these two characteristics, the main verification techniques, software testing and formal verification and the tools related to them, tend to neglect the exceptional behavior. The nonexistent specification of software exceptional behaviors at the design level, and, the subsequent implementation of exception handling based on the judgment of each programmer, are some factors that lead to this neglect. These factors result in the non-consideration of the expressive parts of the code in verification terms and, consequently, the impossibility of errors detection concerning either the exception treatment structures or the code structures linked to them. Taking this fact into consideration, we propose a technique based on the model checking process, which automates the process of exercising exceptional paths to address this problem. This allows the observation of the software behavior when an exception occurs. With this technique, we intend to support the application of the same error detection techniques for program normal behavior paths to the paths that represent the software exceptional behavior. Therefore, using the proposed technique, we aim to increase the software development quality.

EB-3 est un langage de spécification développé pour la spécification des systèmes d'information. Le noyau du langage EB-3comprend des spécifications d'algèbre de processus afin de décrire le comportement des entités du système et des fonctions d'attributs qui sont des fonctions récursives dont l'évaluation se fait sur la trace d'exécution du système décrivant les attributs des entités. La vérification de propriétés temporelles en EB-3 est un sujet de grande importance pour des utilisateurs de EB-3. Dans cette thèse, on se focalise sur les propriétés de vivacité concernant des systèmes d'information exprimant l'éventualité que certaines actions puissent s'exécuter. La vérification des propriétés de vivacité se fait à l'aide de model checking. Dans un premier temps, on présente une sémantique opérationnelle deEB-3, selon laquelle les fonctions d'attributs sont évaluées pendant l'exécution du programme puis stockées. Cette sémantique nous permet de définir une traduction automatique de EB-3 vers LNT, qui est un langage simultané enrichi d'une algèbre de processus. Notre traduction assure la correspondance un à un entre les états et les transitions des systèmes étiquetés de transition correspondent respectivement à des spécifications EB-3 et LNT. Ensuite, on automatise la traduction grâce à l'outil EB3toLNT fournissant aux utilisateurs de EB-3 une tous les outils de vérification fonctionnelle disponible dans CADP. Dans le but d'améliorer les résultats de notre approche concernant le model checking, on explore des techniques d'abstraction dédiées aux systèmes d'information spécifiées en EB-3. En particulier, on se focalise sur une famille spécifique de systèmes qui s'appellent paramétriques dont le comportement varie en fonction de la valeur prédéfinie d'un paramètre du système. Enfin, on applique cette méthode dans le contexte de EB-3 / EB-3 is a specification language for information systems. The core of the EB-3 language consists of process algebraic specifications describing the behaviour of entities in a system, and attribute functions that are recursive functions evaluated on the system execution trace describing entity attributes. The verification ofEB-3 specifications against temporal properties is of great interest to users of EB-3. In this thesis, we focus on liveness properties of information systems, which express the eventuality that certain actions take place. The verification of liveness properties can beachieved with model checking. First, we present an operational semantics for EB-3 programs, in which attribute functions are computed during program evolution and their values are stored into program memory. This semantics permits us to define an automatic translation from EB-3 to LNT, a value-passing concurrent language with classical process algebra features. Our translation ensures the one-to-one correspondence between states and transitions of the labelled transition systems corresponding to theEB-3 and LNT specifications. Then, we automate this translation with the EB-3toLNT tool, thus equipping the EB-3 method with the functional verification features available in the model checking toolbox CADP. With the aim of improving the model checking results of this approach, we explore abstraction techniques for information systems specified inEB-3. In particular, we concentrate on a specific family of systems called parametric, whose behaviour is scaled in keeping with the predefined value of a system parameter. Finally, we apply this method on the EB-3 context

Předkládaná práce se zabývá problémem automatizované syntézy pravděpodobnostních systémů: máme-li rodinu Markovských řetězců, jak lze efektivně identifikovat ten který odpovídá zadané specifikaci? Takové rodiny často vznikají v nejrůznějších oblastech inženýrství při modelování systémů s neurčitostí a rozhodování i těch nejjednodušších syntézních otázek představuje NP-těžký problém. V dané práci my zkoumáme existující techniky založené na protipříklady řízené induktivní syntéze (counterexample-guided inductive synthesis, CEGIS) a na zjemňování abstrakce (counterexample-guided abstraction refinement, CEGAR) a navrhujeme novou integrovanou metodu pro pravděpodobnostní syntézu. Experimenty nad relevantními modely demonstrují, že navržená technika je nejenom srovnatelná s moderními metodami, ale ve většině případů dokáže výrazně překonat, někdy i o několik řádů, existující přístupy.

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.

La criticité des programmes dépasse constamment de nouvelles frontières car ils sont de plus en plus utilisés dans la prise de décision (voitures autonomes, robots chirurgiens, etc.). Le besoin de développer des programmes sûrs et de vérifier les programmes existants émerge donc naturellement.Pour prouver formellement la correction d'un programme, il faut faire face aux défis de la mise à l'échelle et de la décidabilité. Programmes composés de millions de lignes de code, complexité de l'algorithme, concurrence, et même de simples expressions polynomiales font partis des problèmes que la vérification formelle doit savoir gérer. Pour y arriver, les méthodes formelles travaillent sur des abstractions des états des programmes étudiés afin d'analyser des approximations de leur comportement. L'analyse des boucles est un axe entier de la vérification formelle car elles sont encore aujourd'hui peu comprises. Bien que certaines d'entre elles peuvent facilement être traitées, il existe des exemples apparemment très simples mais dont le comportement n'a encore aujourd'hui pas été résolu (par exemple, on ne sait toujours pas pourquoi la suite de Syracuse, simple boucle linéaire, converge toujours vers 1).L'approche la plus commune pour gérer les boucles est l'utilisation d'invariants de boucle, c'est à dire de relations sur les variables manipulées par une boucle qui sont vraies à chaque fois que la boucle recommence. En général, les invariants utilisent les mêmes expressions que celles utilisées dans la boucle : si elle manipule explicitement la mémoire par exemple, on s'attend à utiliser des invariants portant sur la mémoire. Cependant, il existe des boucles contenant uniquement des affectations linéaires qui n'admettent pas d'invariants linéaires, mais polynomiaux.Les boucles linéaires sont elles plus expressives que ce qu'il paraîtrait ?Cette thèse présente de nouvelles propriétés sur les boucles linéaires et polynomiales. Il est déjà connu que les boucles linéaires sont polynomialement expressives, au sens ou si plusieurs variables évoluent linéairement dans une boucle, alors n'importe quel monôme de ces variables évolue linéairement. La première contribution de cette thèse est la caractérisation d'une sous classe de boucles polynomiales exactement aussi expressives que des boucles linéaires, au sens où il existe une boucle linéaire avec le même comportement. Ensuite, deux nouvelles méthodes de génération d'invariants sont présentées.La première méthode est basée sur l'interprétation abstraite et s'intéresse aux filtres linéaires convergents. Ces filtres jouent un rôle important dans de nombreux systèmes embarqués (dans l'avionique par exemple) et requièrent l'utilisation de flottants, un type de valeurs qui peut mener à des erreurs d'imprécision s'ils sont mal utilisés. Aussi, la présence d'affectations aléatoires dans ces filtres rend leur analyse encore plus complexe.La seconde méthode traite d'une approche différente basée sur la génération d'invariants pour n'importe quel type de boucles linéaires. Elle part d'un nouveau théorème présenté dans cette thèse qui caractérise les invariants comme étant les vecteurs propres de la transformation linéaire traitée. Cette méthode est généralisée pour prendre en compte les conditions, les boucles imbriquées et le non déterminisme dans les affectations.La génération d'invariants n'est pas un but en soi, mais un moyen. Cette thèse s'intéresse au genre de problèmes que peut résoudre les invariants générés par la seconde méthode. Le premier problème traité est problème de l'orbite (Kannan-Lipton Orbit problem), dont il est possible de générer des certificats de non accessibilité en utilisant les vecteurs propres de la transformation considerée. En outre, les vecteurs propres sont mis à l'épreuve en pratique par leur utilisation dans le model-checker CaFE basé sur la verification de propriétés temporelles sur des programmes C. / The criticality of programs constantly reaches new boundaries as they are relied on to take decisions in place of the user (autonomous cars, robot surgeon, etc.). This raised the need to develop safe programs and to verify the already existing ones.Anyone willing to formally prove the soundness of a program faces the two challenges of scalability and undecidability. Million of lines of code, complexity of the algorithm, concurrency, and even simple polynomial expressions are part of the issues formal verification have to deal with. In order to succeed, formal methods rely on state abstraction to analyze approximations of the behavior of the analyzed program.The analysis of loops is a full axis of formal verification, as this construction is still today not well understood. Though some of them can be easily handled when they perform simple operations, there still exist some seemingly basic loops whose behavior has not been solved yet (the Syracuse sequence for example is suspected to be undecidable).The most common approach for the treatment of loops is the use of loop invariants, i.e. relations on variables that are true at the beginning of the loop and after every step. In general, invariants are expected to use the same set of expressions used in the loop: if a loop manipulates the memory on a structure for example, invariants will naturally use expressions involving memory operations. However, there exist loops containing only linear instructions that admit only polynomial invariants (for example, the sum on integers $sumlimits_{i=0}^n i$ can be computed by a linear loop and is a degree 2 polynomial in n), hence using expressions that are syntacticallyabsent of the loop. Is the previous remark wrong then ?This thesis presents new insights on loops containing linear and polynomial instructions. It is already known that linear loops are polynomially expressive, in the sense that if a variable evolves linearly, then any monomial of this variable evolves linearly. The first contribution of this thesis is the extraction of a class of polynomial loops that is exactly as expressive as linear loops, in the sense that there exist a linear loop with the exact same behavior. Then, two new methods for generating invariants are presented.The first method is based on abstract interpretation and is focused on a specific kind of linear loops called linear filters. Linear filters play a role in many embedded systems (plane sensors for example) and require the use of floating point operations, that may be imprecise and lead to errors if they are badly handled. Also, the presence of non deterministic assignments makes their analysis even more complex.The second method treats of a more generic subject by finding a complete set of linear invariants of linear loops that is easily computable. This technique is based on the linear algebra concept of eigenspace. It is extended to deal with conditions, nested loops and non determinism in assignments.Generating invariants is an interesting topic, but it is not an end in itself, it must serve a purpose. This thesis investigates the expressivity of invariantsgenerated by the second method by generating counter examples for the Kannan-Lipton Orbit problem.It also presents the tool PILAT implementing this technique and compares its efficiency technique with other state-of-the-art invariant synthesizers. The effective usefulness of the invariants generated by PILAT is demonstrated by using the tool in concert with CaFE, a model-checker for C programs based on temporal logics.

Les systèmes concurrents sont un bon choix pour ajuster les données et analyser les mécanismes sous-jacents pour leur sémantique simple mais expressive. Cependant, l’apprentissage et l’analyse de tels systèmes concurrents sont difficiles pour ce qui concerne les calculs. Lorsqu’il s’agit de grands ensembles de données, les techniques les plus récentes semblent insuffisantes, que ce soit en termes d’efficacité ou de précision. Ici, nous proposons un cadre de modélisation raffiné ABAN (Asynchronous Binary Automata Network) et développons des outils pour analyser l’atteignabilité : PermReach (Reachability via Permutation search) et ASPReach (Reachability via Answer Set Programming). Nous proposons ensuite deux méthodes de construction et d’apprentissage des modèles: CRAC (Completion via Reachability And Correlations) et M2RIT (Model Revision via Reachability and Interpretation Transitions) en utilisant des données continues et discrètes pour s’ajuster au modèle et des propriétés d’accessibilité afin de contraindre les modèles en sortie. / Concurrent systems become a good choice to fit the data and analyze the underlying mechanics for their simple but expressive semantics. However, learning and analyzing such concurrent systems are computationally difficult. When dealing with big data sets, the state-of-the-art techniques appear to be insufficient, either in term of efficiency or in term of precision. In this thesis, we propose a refined modeling framework ABAN (Asynchronous Binary Automata Network) and develop reachability analysis techniques based on ABAN: PermReach (Reachability via Permutation search) and ASPReach (Reachability via Answer Set Programming). Then we propose two model learning/constructing methods: CRAC (Completion via Reachability And Correlations) and M2RIT (Model Revision via Reachability and Interpretation Transitions) using continuous and discrete data to fit the model and using reachability properties to constrain the output models.