Les systèmes temps-réel critiques doivent exécuter leurs tâches dans les délais impartis. En cas de défaillance, des événements peuvent avoir des catastrophes économiques. Des classifications des défaillances par rapport aux niveaux des risques encourus ont été établies, en particulier dans les domaines des transports aéronautique et automobile. Des niveaux de criticité sont attribués aux différentes fonctions des systèmes suivant les risques encourus lors d'une défaillance et des probabilités d'apparition de celles-ci. Ces différents niveaux de criticité influencent les choix d'architecture logicielle et matérielle ainsi que le type de composants utilisés pour sa réalisation. Les systèmes temps-réels modernes ont tendance à intégrer sur une même plateforme de calcul plusieurs applications avec différents niveaux de criticité. Cette intégration est nécessaire pour des systèmes modernes comme par exemple les drones (UAV) afin de réduire le coût, le poids et la consommation d'énergie. Malheureusement, elle conduit à des difficultés importantes lors de leurs conceptions. En plus, ces systèmes doivent être certifiés en prenant en compte ces différents niveaux de criticités.Il est bien connu que le problème d'ordonnancement des systèmes avec différents niveaux de criticités représente un des plus grand défi dans le domaine de systèmes temps-réel. Les techniques traditionnelles proposent comme solution l’isolation complète entre les niveaux de criticité ou bien une certification globale au plus haut niveau. Malheureusement, une telle solution conduit à une mauvaise des ressources et à la perte de l’avantage de cette intégration. En 2007, Vestal a proposé un modèle pour représenter les systèmes avec différents niveaux de criticité dont les tâches ont plusieurs temps d’exécution, un pour chaque niveau de criticité. En outre, les conditions de validité des stratégies d’ordonnancement ont été définies de manière formelle, permettant ainsi aux tâches les moins critiques d’échapper aux délais, voire d’être abandonnées en cas de défaillance ou de situation d’urgence.Les politiques de planification conventionnelles et les tests d’ordonnoncement se sont révélés inadéquats.Dans cette thèse, nous contribuons à l’étude de l’ordonnancement dans les systèmes avec différents niveaux de criticité. La surcharge d'un système est représentée sous la forme d'un ensemble de tâches pouvant décrire l'exécution sur l'hyper-période de tâches ou sur une durée donnée. Ce modèle nous permet d’étudier la viabilité des tests de correction basés sur la simulation pour les systèmes avec différents niveaux de criticité. Nous montrons que les tests de simulation peuvent toujours être utilisés pour ces systèmes, et la possibilité de l’ordonnancement du pire des scénarios ne suffit plus, même pour le cas de l’ordonnancement avec priorité fixe. Nous montrons que les politiques d'ordonnancement ne sont généralement pas prévisibles. Nous définissons le concept de faible prévisibilité pour les systèmes avec différents niveaux de criticité et nous montrons ensuite qu'une classe spécifique de stratégies à priorité fixe sont faiblement prévisibles. Nous proposons deux tests de correction basés sur la simulation qui fonctionnent pour des stratégies faiblement prévisibles.Nous montrons également que, contrairement à ce que l’on croyait, le contrôle de l’exactitude ne peut se faire que par l’intermédiaire d’un nombre linéaire de préemptions.La majorité des travaux reliés à notre domaine portent sur des systèmes à deux niveaux de criticité en raison de la difficulté du problème. Mais pour les systèmes automobiles et aériens, les normes industrielles définissent quatre ou cinq niveaux de criticité, ce qui nous a motivés à proposer un algorithme de planification qui planifie les systèmes à criticité mixte avec théoriquement un nombre quelconque de niveaux de criticité. Nous montrons expérimentalement que le taux de réussite est supérieur à celui de l’état de la technique. / Real-time safety-critical systems must complete their tasks within a given time limit. Failure to successfully perform their operations, or missing a deadline, can have severe consequences such as destruction of property and/or loss of life. Examples of such systems include automotive systems, drones and avionics among others. Safety guarantees must be provided before these systems can be deemed usable. This is usually done through certification performed by a certification authority.Safety evaluation and certification are complicated and costly even for smaller systems.One answer to these difficulties is the isolation of the critical functionality. Executing tasks of different criticalities on separate platforms prevents non-critical tasks from interfering with critical ones, provides a higher guaranty of safety and simplifies the certification process limiting it to only the critical functions. But this separation, in turn, introduces undesirable results portrayed by an inefficient resource utilization, an increase in the cost, weight, size and energy consumption which can put a system in a competitive disadvantage.To overcome the drawbacks of isolation, Mixed Criticality (MC) systems can be used. These systems allow functionalities with different criticalities to execute on the same platform. In 2007, Vestal proposed a model to represent MC-systems where tasks have multiple Worst Case Execution Times (WCETs), one for each criticality level. In addition, correctness conditions for scheduling policies were formally defined, allowing lower criticality jobs to miss deadlines or be even dropped in cases of failure or emergency situations.The introduction of multiple WCETs and different conditions for correctness increased the difficulty of the scheduling problem for MC-systems. Conventional scheduling policies and schedulability tests proved inadequate and the need for new algorithms arose. Since then, a lot of work has been done in this field.In this thesis, we contribute to the study of schedulability in MC-systems. The workload of a system is represented as a set of jobs that can describe the execution over the hyper-period of tasks or over a duration in time. This model allows us to study the viability of simulation-based correctness tests in MC-systems. We show that simulation tests can still be used in mixed-criticality systems, but in this case, the schedulability of the worst case scenario is no longer sufficient to guarantee the schedulability of the system even for the fixed priority scheduling case. We show that scheduling policies are not predictable in general, and define the concept of weak-predictability for MC-systems. We prove that a specific class of fixed priority policies are weakly predictable and propose two simulation-based correctness tests that work for weakly-predictable policies.We also demonstrate that contrary to what was believed, testing for correctness can not be done only through a linear number of preemptions.The majority of the related work focuses on systems of two criticality levels due to the difficulty of the problem. But for automotive and airborne systems, industrial standards define four or five criticality levels, which motivated us to propose a scheduling algorithm that schedules mixed-criticality systems with theoretically any number of criticality levels. We show experimentally that it has higher success rates compared to the state of the art.We illustrate how our scheduling algorithm, or any algorithm that generates a single time-triggered table for each criticality mode, can be used as a recovery strategy to ensure the safety of the system in case of certain failures.Finally, we propose a high level concurrency language and a model for designing an MC-system with coarse grained multi-core interference.

Automated vehicles are assumed to play an important role in the future of mobility, but their operation must be provably safe. They consist of automated driving systems (ADSs) that perform various automated driving tasks without the active participation of a human driver. These automated driving tasks can be mainly categorized as perception, decision-making, and motion control. These tasks must be accomplished by the components of an ADS, which must be seamlessly integrated to ensure safety. The complexity of the ADS architecture makes the safety assessment rather challenging. This complexity is further exacerbated when automated vehicles need to interact in different traffic situations. Design, verification, and testing of ADSs as simulation models provide a safer and cost-efficient early development opportunity compared to real-world testing. To this end, a capable simulation framework that incorporates the simulation models of ADSs must be developed for designing, implementing, and testing these models in a traffic simulation. The main contributions of this thesis are denoted as (i), (ii), and (iii). Safety assessment of ADS can be done either experimentally by (i) simulation-based testing in (ii) a simulation framework or theoretically (iii) using formal methods. Simulation-based testing requires two components: (i) efficient testing strategies for different ADS components and (ii) a simulation framework containing the models of ADS components for applying these testing strategies. Simulation-based testing alone cannot prove or guarantee safety. In order to complement the safety assessment process, whenever applicable, (iii) formal methods must be utilized to derive theoretical safety proofs for certain types of systems for a set of assumptions. Formal methods for synthesis include methods such as correct-by-construction of control protocols and reachability analysis for dynamic systems, which can be used to design provably safe decision-making and control algorithms. The correct-by-construction synthesis of discrete control protocols can be used as safety filters for decision-making algorithms, such as autonomous intersection management algorithms, to verify the safety of taken actions. The reachability analysis is useful for predicting trajectories for possible maneuvers in a finite time horizon for an automated vehicle on a highway. By over-approximating these ego vehicle trajectories, safety verification of possible maneuvers can be done by comparing them to the possible trajectories of other vehicles. A game-theoretical decision-making approach, such as minimax, can augment safety in maneuver planning by considering the worst-case situations up to a finite time horizon. Such an online maneuver planning algorithm reconsiders the maneuvers at each planning cycle in a receding horizon fashion. However, to apply formal methods, certain assumptions must be made about complex parts of ADSs, and therefore, simulation-based testing is still needed to check the validity of these assumptions in simulation models. Safety assessment with a holistic approach is presented that combines the previously mentioned contributions of this thesis (i), (ii), and (iii) into a workflow of modeling, design/synthesis, and testing. Such an approach is essential for developing safe algorithms for ADSs in a simulation framework.:Kurzfassung v Abstract vii Contents ix 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Scope of the Thesis . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Research Questions . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . 3 2 Safety Assessment of Automated Driving Systems - State of the Art 5 2.1 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Definition of ADS . . . . . . . . . . . . . . . . . . . . 5 2.1.2 Meaning of Safety for ADS . . . . . . . . . . . . . . . 8 2.1.3 Testing for Safety . . . . . . . . . . . . . . . . . . . . 12 2.1.4 Simulation Frameworks for ADSs and AVs . . . . . . 14 2.1.5 Roles of Formal Methods . . . . . . . . . . . . . . . . 16 2.2 Challenges and Contributions . . . . . . . . . . . . . . . . . 18 2.2.1 Challenges in the State-of-the-Art . . . . . . . . . . . 18 2.2.2 The Contributions . . . . . . . . . . . . . . . . . . . 21 3 Simulation-based Testing using Fault Injection 23 3.1 Related Work and Preliminaries . . . . . . . . . . . . . . . . 24 3.1.1 Fault Injection . . . . . . . . . . . . . . . . . . . . . 24 3.1.2 Fault Types and Parameters . . . . . . . . . . . . . . 27 3.1.3 Testing for ADS safety using FI . . . . . . . . . . . . 30 3.1.4 Metrics and Specifications for Safety Evaluation . . . 33 3.1.5 Simulative Error Propagation Analysis . . . . . . . . 35 3.2 Developing a Testing Strategy using Fault Injection . . . . . 36 3.2.1 Automated Testing . . . . . . . . . . . . . . . . . . . 37 3.2.2 Using Domain-specific Knowledge . . . . . . . . . . . 40 3.2.3 Smart Testing Strategy . . . . . . . . . . . . . . . . . 41 3.3 Application of Testing Strategies . . . . . . . . . . . . . . . 42 3.3.1 Testing of ACC Systems for Fault Tolerance using Fault Injection . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.3.2 Discovering Fault Parameter Space using Smart Testing Strategy . . . . . . . . . . . . . . . . . . . . . . . 48 3.4 General Functionalities for Efficient Tools . . . . . . . . . . . 52 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4 A Framework for Simulating Automated Driving Systems in Traffic 55 4.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.1.1 Levels of Detail in Traffic Simulation . . . . . . . . . 56 4.1.2 Traffic Simulations and Scenario-based Testing . . . . 59 4.1.3 Generic ADS Architecture . . . . . . . . . . . . . . . 64 4.2 Preliminaries and Definitions . . . . . . . . . . . . . . . . . . 65 4.2.1 Map and Path Planning . . . . . . . . . . . . . . . . 66 4.2.2 Decision Making and Trajectories . . . . . . . . . . . 67 4.2.3 Vehicle Motion Control . . . . . . . . . . . . . . . . . 68 4.3 Mapping the ADS structure into a Simulation Model . . . . 72 4.3.1 Sensor-based Perception . . . . . . . . . . . . . . . . 72 4.3.2 V2X Communication . . . . . . . . . . . . . . . . . . 73 4.3.3 Global Path Planner . . . . . . . . . . . . . . . . . . 75 4.3.4 Behavioral Planner/Maneuver Planner . . . . . . . . 78 4.3.5 Longitudinal and Lateral Motion Control . . . . . . . 80 4.4 Interfaces and Layering between Modules . . . . . . . . . . . 81 4.4.1 Relations between Discrete Decision-Making and Continuous Control . . . . . . . . . . . . . . . . . . . . . 82 4.4.2 Vehicles and the Infrastructure - Autonomous Intersection Management . . . . . . . . . . . . . . . . . . . . 83 4.5 Instantiating a Model-based Traffic Simulation . . . . . . . . 86 4.5.1 Traffic Simulation Environment Architecture . . . . . 88 4.5.2 Road Network and the Map Format . . . . . . . . . . 91 4.5.3 Scenario-based Traffic Simulation as Test Cases . . . 95 4.5.4 Overview of the Simulation Framework with Fault Injection . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.6 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.6.1 Urban Traffic Simulations . . . . . . . . . . . . . . . 101 4.6.2 Fault-Error-Failure Chain Analysis for Safety Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5 Using Formal Methods for Safe Algorithms Design 111 5.1 Control Protocol Synthesis . . . . . . . . . . . . . . . . . . . 111 5.1.1 Related Work and Preliminaries . . . . . . . . . . . . 111 5.1.1.1 Finite State Transition Systems . . . . . . . 112 5.1.1.2 Linear Temporal Logic and Büchi Automaton 113 5.1.1.3 Correct-by-Construction Control Protocol Synthesis . . . . . . . . . . . . . . . . . . . 114 5.1.2 Application in an Autonomous Intersection Management Algorithm . . . . . . . . . . . . . . . . . . . . . 116 5.1.2.1 Modeling the Intersection and the Behaviors of the Vehicles . . . . . . . . . . . . . . . . 116 5.1.2.2 Specifications for Synthesis . . . . . . . . . 120 5.1.2.3 Algorithm for Safe Decision-Making for AIM 122 5.2 Game-Theoretical Decision-Making and Trajectory Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.2.1 Related Work and Preliminaries . . . . . . . . . . . . 125 5.2.1.1 Game-Theoretical Minimax Decision-Making 126 5.2.1.2 Reachability Analysis for Trajectory Generation . . . . . . . . . . . . . . . . . . . . . . 127 5.2.1.3 Motion in Frenet Coordinates . . . . . . . . 130 5.2.1.4 Modeling of AVs and Maneuvers . . . . . . 132 5.2.2 Application in a Safe Maneuver Planning Algorithm . 137 5.2.2.1 Fixed Abstraction and the Over- Approximation of Trajectories . . . . . . . . 138 5.2.2.2 Safety Quantification of Maneuvers . . . . . 140 5.2.2.3 Minimax Decision-Making for Safe Maneuver Planning . . . . . . . . . . . . . . . . . . . 143 5.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 6 Safety Assessment with a Holistic Approach 151 6.1 Overview and the Application of the Approach . . . . . . . . 152 6.2 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 6.2.1 Case Study 1: Safety of an Autonomous Intersection Management Algorithm . . . . . . . . . . . . . . . . 155 6.2.1.1 Modeling . . . . . . . . . . . . . . . . . . . 155 6.2.1.2 Design/Synthesis . . . . . . . . . . . . . . . 157 6.2.1.3 Testing and Results . . . . . . . . . . . . . 159 6.2.1.4 Conclusion . . . . . . . . . . . . . . . . . . 161 6.2.2 Case Study 2: Safety of a Maneuver Planning Algorithm for Highway Driving . . . . . . . . . . . . . . . 162 6.2.2.1 Modeling . . . . . . . . . . . . . . . . . . . 163 6.2.2.2 Design/Synthesis . . . . . . . . . . . . . . . 163 6.2.2.3 Testing and Results . . . . . . . . . . . . . 167 6.2.2.4 Conclusion . . . . . . . . . . . . . . . . . . 175 7 Conclusions 177 7.1 Main Findings . . . . . . . . . . . . . . . . . . . . . . . . . . 178 7.2 Answers to the Research Questions . . . . . . . . . . . . . . 179 7.3 Possible Future Directions . . . . . . . . . . . . . . . . . . . 181 Appendix A Additional Details 185 A.1 Rigid Bodies of the Vehicles . . . . . . . . . . . . . . . . . . 185 A.2 Collision Detection . . . . . . . . . . . . . . . . . . . . . . . 186 A.3 Trajectory Tracking in Frenet Coordinates . . . . . . . . . . 187 References 189