En analyse de risques, les arbres d’attaque sont utilisés pour évaluer les menaces sur un système. Les méthodes formelles permettent leur analyse quantitative et leur synthèse, mais les propriétés exprimant la qualité des arbres d’attaque par rapport au système n’ont pas été formalisées. Dans ce document, nous définissons un nouveau cadre formel pour les arbres d’attaque prenant en compte un modèle opérationnel du système, et dotant les arbres d’une sémantique de chemins. Nous définissons les propriétés de correction des raffinements, et étudions leurs complexités. A partir d’une attaque optimale dans un modèle de système quantitatif, nous guidons la conception d’un arbre d’attaque, en indiquant ses feuilles qui contribuent à l’attaque optimale considérée. / In risk analysis, attack trees are used to assess threats to a system. Formal methods allow for their quantitative analysis and synthesis, but the properties expressing the quality of the attack trees with respect to the system have not been formalized. In this document, we define a new formal framework for attack trees that takes an operational model of the system into account, and provides the trees with a path semantics. We define the correctness properties of refinements, and study their computational complexity. Given an optimal attack in a quantitative system model, we guide the design of a attack tree, indicating its leaves that contribute to considered the optimal attack.

Les protocoles de sécurité modernes peuvent impliquer un participant humain de façon à ce qu'il compare ou copie de courtes chaines de caractères faisant le pont entre différents appareils. C'est par exemple le cas des protocoles basés sur une authentification à facteur multiples comme les protocoles Google 2 factor ou 3D-Secure.Cependant, de telles chaines de caractères peuvent être sujettes à des attaques par force brute. Dans cette thèse nous proposons un modèle symbolique qui inclut les capacités de l'attaquant à deviner des secrets faibles et à produire des collisions avec des fonctions de hachage dont de l'application résulte une courte chaine de caractères. Nous proposons une nouvelle procédure de décision pour analyser un protocole (restreint à un nombre borné de sessions) qui se base sur de courtes chaines de caractères. Cette procédure a été intégré dans l'outil AKISS et testé sur les protocoles du standard ISO/IEC 9798-6:2010 / Modern security protocols may involve humans in order to compare or copy short strings betweendifferent devices. Multi-factor authentication protocols, such as Google 2-factor or 3D-Secure are typical examplesof such protocols. However, such short strings may be subject to brute force attacks. In this thesis we propose asymbolic model which includes attacker capabilities for both guessing short strings, and producing collisions whenshort strings result from an application of weak hash functions. We propose a new decision procedure for analyzing(a bounded number of sessions of) protocols that rely on short strings. The procedure has been integrated in theAKISS tool and tested protocols from the ISO/IEC 9798-6:2010 standard

"We report the results of a series of crowd-sourced user studies in the formal-methods domain. Specifically, we explore the efficacy of the notion of "minimal counterexample" -- or more colloquially, "minimal bug report" -- when reasoning about logical specifications. Our results here suggest that minimal counterexamples are beneficial some specific cases, and harmful in others. Furthermore, our analysis leads to refined hypotheses about the role of minimal counterexamples that can be further evaluated in future studies. User-based evaluation has little precedent in the formal methods community. Therefore, as a further contribution, we discuss and analyze our research methodology, and offer guidelines for future user studies in formal methods research. "

Formal methods are widely used in engineering to determine whether a system exhibits a certain property (verification) or to design controllers that are guaranteed to drive the system to achieve a certain property (synthesis). Most existing techniques require a large amount of accurate information about the system in order to be successful. The methods presented in this work can operate with significantly less prior information. In the domain of formal synthesis for robotics, the assumptions of perfect sensing and perfect knowledge of system dynamics are unrealistic. To address this issue, we present control algorithms that use active estimation and reinforcement learning to mitigate the effects of uncertainty. In the domain of cyber-physical system analysis, we relax the assumption that the system model is known and identify system properties automatically from execution data. First, we address the problem of planning the path of a robot under temporal logic constraints (e.g. "avoid obstacles and periodically visit a recharging station") while simultaneously minimizing the uncertainty about the state of an unknown feature of the environment (e.g. locations of fires after a natural disaster). We present synthesis algorithms and evaluate them via simulation and experiments with aerial robots. Second, we develop a new specification language for tasks that require gathering information about and interacting with a partially observable environment, e.g. "Maintain localization error below a certain level while also avoiding obstacles.'' Third, we consider learning temporal logic properties of a dynamical system from a finite set of system outputs. For example, given maritime surveillance data we wish to find the specification that corresponds only to those vessels that are deemed law-abiding. Algorithms for performing off-line supervised and unsupervised learning and on-line supervised learning are presented. Finally, we consider the case in which we want to steer a system with unknown dynamics to satisfy a given temporal logic specification. We present a novel reinforcement learning paradigm to solve this problem. Our procedure gives "partial credit'' for executions that almost satisfy the specification, which can lead to faster convergence rates and produce better solutions when the specification is not satisfiable.

Many systems operate in uncertain, possibly adversarial environments, and their successful operation is contingent upon satisfying specific requirements, optimal performance, and ability to recover from unexpected situations. Examples are prevalent in many engineering disciplines such as transportation, robotics, energy, and biological systems. This thesis studies designing correct, resilient, and optimal controllers for discrete-time complex systems from elaborate, possibly vague, specifications. The first part of the contributions of this thesis is a framework for optimal control of non-deterministic hybrid systems from specifications described by signal temporal logic (STL), which can express a broad spectrum of interesting properties. The method is optimization-based and has several advantages over the existing techniques. When satisfying the specification is impossible, the degree of violation - characterized by STL quantitative semantics - is minimized. The computational limitations are discussed. The focus of second part is on specific types of systems and specifications for which controllers are synthesized efficiently. A class of monotone systems is introduced for which formal synthesis is scalable and almost complete. It is shown that hybrid macroscopic traffic models fall into this class. Novel techniques in modular verification and synthesis are employed for distributed optimal control, and their usefulness is shown for large-scale traffic management. Apart from monotone systems, a method is introduced for robust constrained control of networked linear systems with communication constraints. Case studies on longitudinal control of vehicular platoons are presented. The third part is about learning-based control with formal guarantees. Two approaches are studied. First, a formal perspective on adaptive control is provided in which the model is represented by a parametric transition system, and the specification is captured by an automaton. A correct-by-construction framework is developed such that the controller infers the actual parameters and plans accordingly for all possible future transitions and inferences. The second approach is based on hybrid model identification using input-output data. By assuming some limited knowledge of the range of system behaviors, theoretical performance guarantees are provided on implementing the controller designed for the identified model on the original unknown system.

Safety is a well-known and important class of property of software programs, and of systems in general. The basic notion that informs this work is that the time to think about safety is when it still exists but could be lost. The notion is not just to analyse safety as existing or not with a given system state, but also in the sense that a system is presently safe but becoming less so. Safety as considered here is not restricted to one type of property, and indeed for much of the discussion it does not matter what types of measures are used to assess safety. The work done here is for the purpose of laying a theoretical and mathematical foundation for allowing static analyses of systems to further safety. This is done using tools from lattice theory applied to the poset of system states partially ordered by reachability. Such analyses are common (e.g., with abstract interpretations of software functioning) with respect to other kinds of systems, but there does not seem to exist a formalism that permits them specifically for safety. Using the basic analytical tools developed, a study is made of the problem of composing systems from components. Three types of composition: direct sum, direct product, and exponentiation---are noted, and the first two are treated in some depth. It is shown that the set of all systems formed with the direct sum and direct product operators can be specified by a BNF grammar. A three-valued ``safety logic'' is specified, using which the safety and fault-tolerance of composed systems can be computed given the system composition. It is also shown that the set of all systems also forms separate monoids (in the sense familiar to mathematicians), and that other monoids can be derived based on equivalence classes of systems. The example of a train approaching a railroad crossing, where a gate must be closed prior to the train's arrival and opened after its exit, is considered and analysed as an example.

The thesis proposes a number of techniques for elaborating requirements constructively from high-level goals. The techniques are based on the KAOS goal-oriented method for requirements engineering. This method consists in identifying goals and refining them into subgoals until the latter can be assigned as responsibilities of single agents such as humans, devices and software. Domain properties and assumptions about the software environment are also used during the goal refinement process. The method supports the exploration of alternative goal refinements and alternative responsibility assignments of goals to agents. It also supports the identification and resolution of conflicts between goals, and the identification and resolution of exceptional agent behaviors, called obstacles, that violate goals and assumptions produced during the goal refinement process. The thesis enriches the KAOS framework through three kinds of techniques: (a) techniques for identifying agents, goal refinements, and alternative responsibility assignments, and for deriving agent interfaces from such responsibility assignments; (b) techniques for deriving operational requirements from goal specifications; (c) techniques for generating obstacles to the satisfaction of idealized goals and assumptions, and for generating alternative obstacle resolutions. The result is a coherent body of systematic techniques for requirements elaboration that are both theoretically well-founded (a formal model of agent is defined) and effective in practice (the techniques are validated on two real case studies of significant size: the London ambulance despatching system, and the Bay Area Rapid Transit train system).

The thesis proposes a number of techniques for elaborating requirements constructively from high-level goals. The techniques are based on the KAOS goal-oriented method for requirements engineering. This method consists in identifying goals and refining them into subgoals until the latter can be assigned as responsibilities of single agents such as humans, devices and software. Domain properties and assumptions about the software environment are also used during the goal refinement process. The method supports the exploration of alternative goal refinements and alternative responsibility assignments of goals to agents. It also supports the identification and resolution of conflicts between goals, and the identification and resolution of exceptional agent behaviors, called obstacles, that violate goals and assumptions produced during the goal refinement process. The thesis enriches the KAOS framework through three kinds of techniques: (a) techniques for identifying agents, goal refinements, and alternative responsibility assignments, and for deriving agent interfaces from such responsibility assignments; (b) techniques for deriving operational requirements from goal specifications; (c) techniques for generating obstacles to the satisfaction of idealized goals and assumptions, and for generating alternative obstacle resolutions. The result is a coherent body of systematic techniques for requirements elaboration that are both theoretically well-founded (a formal model of agent is defined) and effective in practice (the techniques are validated on two real case studies of significant size: the London ambulance despatching system, and the Bay Area Rapid Transit train system).

The problem of relating inter-agent and intra-agent behavioral specifications is investigated. These two views are complimentary, in that the former is closer to scenario-based user requirements whereas the latter is design-oriented. We use a graphical, user-friendly and very simple language as inter-agent specification language: Live Sequence Charts (LSC). LSC is presented and its properties are investigated: it is highly succinct, but inexpressive. There are essentially two ways to relate inter-agent and intra-agent specifications: (i) by checking that an intra-agent specification is correct with respect to some LSC specification and (ii) by automatically building an intra-agent specification from an LSC specification. Several variants of these problems exist: closed/open systems and centralized/distributed systems. We give inefficient but optimal algorithms solving all problems, besides synthesis of open distributed systems, which we show is undecidable. All the problems considered are difficult, even for a very restricted subset of LSCs, without alternatives, interleaving, conditions nor loops. We investigate the cost of extending the language with control flow constructs, conditions, real-time and symbolic instances. An implementation of the algorithms is proposed. The applicability of the language is illustrated on a real-world case study.

Wireless network access protocols are used in numerous safety critical applications. Network availability is essential for safety critical applications,since loss of availability can cause personal or material damage. An adversary can disrupt the availability of a wireless network using denial of service (DoS) attacks. The most widely used wireless protocols are vulnerable to DoS attacks. Researchers have published DoS attacks against IEEE 802.11 local area networks (LANs), IEEE 802.16 wide area networks (WANs) and GSM andUMTS mobile networks. In this work, we analyze DoS vulnerabilities in wireless network protocols and define four categories of attacks:  jamming attacks, flooding attacks, semantic attacks and implementation specific attacks. We identify semantic attacks as the most severe threat to current andfuture wireless protocols, and as the category that has received the least attention by researchers. During the first phase of the research project we discover semantic DoS vulnerabilities in the IEEE 802.11 communication protocols through manual analysis. The 802.11 standard has been subject to manual analysis of DoS vulnerabilities for more than a decade, thus our results indicate that protocol vulnerabilities can elude manual analysis. We conclude that formal methods are required in order to improve protocol robustness against semantic DoS attacks.We propose a formal method that can be used to automatically discover protocol vulnerabilities. The formal method defines a protocol model, adversary model and cost model. The protocol participants and adversary are modeled as finite state transducers, while the cost is modeled as a function of time. Our primary goal is to construct a formal method that is practical, i.e. does not require a vast amount of resources to implement, and useful, i.e. able to discover protocol vulnerabilities. We verify and validate our proposed method by modeling the 802.11w amendment to the 802.11 standard using Promela as the modeling language. We then use the SPIN model checker to verify the model properties and experiments to validate the results. The modeling and experiments result in the discovery and experimental validation of four new deadlock vulnerabilities that had eluded manual analysis. We find one deadlock vulnerability in 802.11i and three deadlock vulnerabilitiesin 802.11w. A deadlock vulnerability is the most severe form of communication protocol DoS vulnerabilities, and their discovery and removal are an essential part of robust protocol design. Thus, we conclude that our proposed formal method is both practical and useful.