Fault and timing analysis in critical multi-core systems: A survey with an avionics perspective
---
paper_title: Fault-tolerant computer system design

paper_content:

In the ten years since the publication of the first edition of this book, the field of fault-tolerant design has broadened in appeal, particularly with its emerging application in distributed computing. This new edition specifically deals with this dynamically changing computing environment, incorporating new topics such as fault-tolerance in multiprocessor and distributed systems.
---
paper_title: Precise contention-aware performance prediction on virtualized multicore system

paper_content:

Virtualized multicore contention - aware performance prediction model.Virtual machine contention sensitivity and intensity features collection.Quantify the precise levels of performance degradation between VMs. Multicore systems are widely deployed in both the embedded and the high end computing infrastructures. However, traditional virtualization systems can not effectively isolate shared micro architectural resources among virtual machines (VMs) running on multicore systems. CPU and memory intensive VMs contending for these resources will lead to serious performance interference, which makes virtualization systems less efficient and VM performance less stable. In this paper, we propose a contention-aware performance prediction model on the virtualized multicore systems to quantify the performance degradation of VMs. First, we identify the performance interference factors and design synthetic micro-benchmarks to obtain VM's contention sensitivity and intensity features that are correlated with VM performance degradation. Second, based on the contention features, we build VM performance prediction model using machine learning techniques to quantify the precise levels of performance degradation. The proposed model can be used to optimize VM performance on multicore systems. Our experimental results show that the performance prediction model achieves high accuracy and the mean absolute error is 2.83%.
---
paper_title: Emulation of Transient Software Faults for Dependability Assessment: A Case Study

paper_content:

Fault Tolerance Mechanisms (FTMs) are extensively used in software systems to counteract software faults, in particular against faults that manifest transiently, namely Mandelbugs. In this scenario, Software Fault Injection (SFI) plays a key role for the verification and the improvement of FTMs. However, no previous work investigated whether SFI techniques are able to emulate Mandelbugs adequately. This is an important concern for assessing critical systems, since Mandelbugs are a major cause of failures, and FTMs are specifically tailored for this class of software faults. In this paper, we analyze an existing state-of-the-art SFI technique, namely G-SWFIT, in the context of a real-world fault-tolerant system for Air Traffic Control (ATC). The analysis highlights limitations of G-SWFIT regarding its ability to emulate the transient nature of Mandelbugs, because most of injected faults are activated in the early phase of execution, and they deterministically affect process replicas in the system. We also notice that G-SWFIT leaves untested the 35% of states of the considered system. Moreover, by means of an experiment, we show how emulation of Mandelbugs is useful to improve SFI. In particular, we emulate concurrency faults, which are a critical sub-class of Mandelbugs, in a fully representative way. We show that proper fault triggering can increase the confidence in FTMs' testing, since it is possible to reduce the amount of untested states down to 5%.
---
paper_title: Two Techniques for Transient Software Error Recovery

paper_content:

The traditional approaches for fault tolerance in software — the recovery block approach and the N-version programming — are too expensive, and consequently of limited practical use. Experience has shown that techniques, such as rollback and retry, that do not employ multiple versions of software are able to mask a range of software faults that exhibit transient software failures. These techniques are cost effective as they do not employ design diversity for supporting fault tolerance. In this report we discuss two such techniques that can be used to enhance the reliability of software systems.
---
paper_title: Assessing Dependability with Software Fault Injection: A Survey

paper_content:

With the rise of software complexity, software-related accidents represent a significant threat for computer-based systems. Software Fault Injection is a method to anticipate worst-case scenarios caused by faulty software through the deliberate injection of software faults. This survey provides a comprehensive overview of the state of the art on Software Fault Injection to support researchers and practitioners in the selection of the approach that best fits their dependability assessment goals, and it discusses how these approaches have evolved to achieve fault representativeness, efficiency, and usability. The survey includes a description of relevant applications of Software Fault Injection in the context of fault-tolerant systems.
---
paper_title: Formal verification of fault tolerance in safety-critical reconfigurable modules

paper_content:

Demands for higher flexibility in aerospace applications has led to increasing deployment of reconfiguarble modules. In several cases the industry is looking into Field Programmable Gate Arrays (FPGA) as a means of efficient adaption of existing components. This paper addresses the safety analysis issues for reconfigurable modules with an emphasis on FPGAs. FPGAs act as digital hardware but in the context of safety analysis they should be treated as software, i.e. with added demands on formal analysis. The contributions of this paper are twofold. First, we illustrate a development process using a language with formal semantics (Esterel) for design, formal verification of high-level design, and automatic code generation down to synthesizable VHDL. We argue that this process reduces the likelihood of systematic (permanent) faults in the design, and still produces VHDL code that may be of acceptable quality (size of FPGA, delay). Secondly, in a general approach that is equally applicable to other formal design languages, we illustrate how the effect of transient fault modes and faults in external modules can be formally studied. We modularly extended the component design model with fault models that represent specific or random faults (e.g. radiation leading to bit flips in the component under design), and transient or permanent faults in the rest of the environment. Some faults corrupt inputs to the component and others jeopardise the effect of output signals that control the environment. This process supports a formal version of Failure Modes and Effects Analysis (FMEA). The set-up is then used to formally determine which (single or multiple) fault modes cause violation of the top-level safety-related property, much in the spirit of fault-tree analyses (FTA). All of this is done with out building the fault tree and using a common model for design and for safety analyses. An aerospace hydraulic monitoring system is used to illustrate the analysis of fault tolerance .
---
paper_title: Survey of fault tolerance techniques for shared memory multicore/multiprocessor systems

paper_content:

With the advent of modern nano-scale technology, it has become possible to implement multiple processing cores on a single die. The shrinking transistor sizes however have made reliability a concern for such systems as smaller transistors are more prone to permanent as well as transient faults. To reduce the probability of failures of such systems, online fault tolerance techniques can be applied. These techniques need to be efficient as they execute concurrently with applications running on such systems. This paper discusses the challenges involved in online fault tolerance and existing work which tackles these challenges. We classify fault tolerance into four different steps which are proactive fault management, error detection, fault diagnosis and recovery and discuss related work for each step, with focus on techniques for shared memory multicore/multiprocessor systems. We also highlight the additional difficulties in tolerating faults for parallel execution on shared memory multicore/multiprocessor systems.
---
paper_title: Why Do Computers Stop And What Can Be Done About It?

paper_content:

An analysis of the failure statistics of a commercially available fault-tolerant system shows that administration and software are the major contributors to failure. Various approaches to software fault-tolerance are then discussed -- notably process-pairs, transactions and reliable storage. It is pointed out that faults in production software are often soft (transient) and that a transaction mechanism combined with persistent processpairs provides fault-tolerant execution -- the key to software fault-tolerance.
---
paper_title: Automotive embedded software: Migration challenges to multi-core computing platforms

paper_content:

The introduction of multi-core computing platforms aims at providing more computing resources and additional interfaces to answer the needs of new automotive control strategies with respect to computing performances and connectivity (e.g. connected vehicle, hybrid powertrains). At the same time, the parallel execution and resulting resources and timing conflicts require a paradigm change for the embedded software. Consequently, efficient migration of legacy software on multi-core platform, while guaranteeing at least the same level of integrity and performance as for single cores, is a significant challenge. The contributions of this paper are (1) to provide a state-of-practice survey on multi-core CPUs and operating systems for the automotive domain, and (2) based on this survey to provide guidelines for the migration of legacy SW. Finally the related challenges and opportunities for the development of high-integrity control systems on multi-cores, as platform for dependable systems are discussed.
---
paper_title: A few open problems and solutions for software technologies for dependable distributed systems

paper_content:

Abstract Software technologies are of paramount importance in the current and upcoming systems. In certain application domains, their design has to fit a difficult equation involving not only the expected functionality, but also broader dependable characteristics. Functional and non-functional characteristics have to adhere to requirements such as openness, adaptation, device heterogeneity, energy, or footprint. In this paper, we present a few challenges in some selected areas around the theme of software technologies for dependable distributed systems. These selected areas are real-time, security in software forensics, and adaptation for cyber-physical systems from the perspective of the middleware. This serves as a context for the special issue in which this paper is contained, that gathers a set of valuable contributions in topics related to these domains. Lastly, we present a set of contributions that are part of this special issue that approach the problem from different perspectives.
---
paper_title: Survey of fault tolerance techniques for shared memory multicore/multiprocessor systems

paper_content:

With the advent of modern nano-scale technology, it has become possible to implement multiple processing cores on a single die. The shrinking transistor sizes however have made reliability a concern for such systems as smaller transistors are more prone to permanent as well as transient faults. To reduce the probability of failures of such systems, online fault tolerance techniques can be applied. These techniques need to be efficient as they execute concurrently with applications running on such systems. This paper discusses the challenges involved in online fault tolerance and existing work which tackles these challenges. We classify fault tolerance into four different steps which are proactive fault management, error detection, fault diagnosis and recovery and discuss related work for each step, with focus on techniques for shared memory multicore/multiprocessor systems. We also highlight the additional difficulties in tolerating faults for parallel execution on shared memory multicore/multiprocessor systems.
---
paper_title: Why Do Computers Stop And What Can Be Done About It?

paper_content:

An analysis of the failure statistics of a commercially available fault-tolerant system shows that administration and software are the major contributors to failure. Various approaches to software fault-tolerance are then discussed -- notably process-pairs, transactions and reliable storage. It is pointed out that faults in production software are often soft (transient) and that a transaction mechanism combined with persistent processpairs provides fault-tolerant execution -- the key to software fault-tolerance.
---
paper_title: Fault-tolerant computer system design

paper_content:

In the ten years since the publication of the first edition of this book, the field of fault-tolerant design has broadened in appeal, particularly with its emerging application in distributed computing. This new edition specifically deals with this dynamically changing computing environment, incorporating new topics such as fault-tolerance in multiprocessor and distributed systems.
---
paper_title: Assessing Dependability with Software Fault Injection: A Survey

paper_content:

With the rise of software complexity, software-related accidents represent a significant threat for computer-based systems. Software Fault Injection is a method to anticipate worst-case scenarios caused by faulty software through the deliberate injection of software faults. This survey provides a comprehensive overview of the state of the art on Software Fault Injection to support researchers and practitioners in the selection of the approach that best fits their dependability assessment goals, and it discusses how these approaches have evolved to achieve fault representativeness, efficiency, and usability. The survey includes a description of relevant applications of Software Fault Injection in the context of fault-tolerant systems.
---
paper_title: Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance

paper_content:

This paper is based on a conjecture that the more confidence one needs in a task execution time bound (the less tolerant one is of missed deadlines), the larger and more conservative that bound tends to become in practice. We assume different tasks perform functions having different criticalities and requiring different levels of assurance. We assume a task may have a set of alternative worst-case execution times, each assured to a different level of confidence. This paper presents ways to use this information to obtain more precise schedulability analysis and more efficient preemptive fixed priority scheduling. These methods are evaluated using workloads abstracted from production avionics systems.
---
paper_title: PROARTIS: Probabilistically Analyzable Real-Time Systems

paper_content:

Static timing analysis is the state-of-the-art practice of ascertaining the timing behavior of current-generation real-time embedded systems. The adoption of more complex hardware to respond to the increasing demand for computing power in next-generation systems exacerbates some of the limitations of static timing analysis. In particular, the effort of acquiring (1) detailed information on the hardware to develop an accurate model of its execution latency as well as (2) knowledge of the timing behavior of the program in the presence of varying hardware conditions, such as those dependent on the history of previously executed instructions. We call these problems the timing analysis walls. In this vision-statement article, we present probabilistic timing analysis, a novel approach to the analysis of the timing behavior of next-generation real-time embedded systems. We show how probabilistic timing analysis attacks the timing analysis walls; we then illustrate the mathematical foundations on which this method is based and the challenges we face in the effort of efficiently implementing it. We also present experimental evidence that shows how probabilistic timing analysis reduces the extent of knowledge about the execution platform required to produce probabilistically accurate WCET estimations.
---
paper_title: Measurement-Based Probabilistic Timing Analysis for Multi-path Programs

paper_content:

The rigorous application of static timing analysis requires a large and costly amount of detail knowledge on the hardware and software components of the system. Probabilistic Timing Analysis has potential for reducing the weight of that demand. In this paper, we present a sound measurement-based probabilistic timing analysis technique based on Extreme Value Theory. In all the experiments made as part of this work, the timing bounds determined by our technique were less than 15% pessimistic in comparison with the tightest possible bounds obtainable with any probabilistic timing analysis technique. As a point of interest to industrial users, our technique also requires a comparatively low number of measurement runs of the program under analysis, less than 650 runs were needed for the benchmarks presented in this paper.
---
paper_title: Practical Task Allocation for Software Fault-Tolerance and Its Implementation in Embedded Automotive Systems

paper_content:

Due to the advent of active safety features and automated driving capabilities, the complexity of embedded computing systems within automobiles continues to increase. Such advanced driver assistance systems (ADAS) are inherently safetycritical and must tolerate failures in any subsystem. However, fault-tolerance in safety-critical systems has been traditionally supported by hardware replication, which is prohibitively expensive in terms of cost, weight, and size for the automotive market. Recent work has studied the use of software-based faulttolerance techniques that utilize task-level hot and cold standbys to tolerate fail-stop processor and task failures. The benefit of using standbys is maximal when a task and any of its standbys obey the placement constraint of not being co-located on the same processor. We propose a new heuristic based on a "tiered" placement constraint, and show that our heuristic produces a better task assignment that saves at least one processor up to 40% of the time relative to the best known heuristic to date. We then introduce a task allocation algorithm that, for the first time to our knowledge, leverages the run-time attributes of cold standbys. Our empirical study finds that our heuristic uses no more than one additional processor in most cases relative to an optimal allocation that we construct for evaluation purposes using a creative technique. We have designed and implemented our software fault-tolerance framework in AUTOSAR, an automotive industry standard. We use this implementation to provide an experimental evaluation of our task-level fault-tolerance features. Finally, we present an analysis of the worst-case behavior of our task recovery features.
---
paper_title: PLR: A Software Approach to Transient Fault Tolerance for Multicore Architectures

paper_content:

Transient faults are emerging as a critical concern in the reliability of general-purpose microprocessors. As architectural trends point toward multicore designs, there is substantial interest in adapting such parallel hardware resources for transient fault tolerance. This paper presents process-level redundancy (PLR), a software technique for transient fault tolerance, which leverages multiple cores for low overhead. PLR creates a set of redundant processes per application process and systematically compares the processes to guarantee correct execution. Redundancy at the process level allows the operating system to freely schedule the processes across all available hardware resources. PLR uses a software-centric approach to transient fault tolerance, which shifts the focus from ensuring correct hardware execution to ensuring correct software execution. As a result, many benign faults that do not propagate to affect program correctness can be safely ignored. A real prototype is presented that is designed to be transparent to the application and can run on general-purpose single-threaded programs without modifications to the program, operating system, or underlying hardware. The system is evaluated for fault coverage and performance on a four-way SMP machine and provides improved performance over existing software transient fault tolerance techniques with a 16.9 percent overhead for fault detection on a set of optimized SPEC2000 binaries.
---
paper_title: Fault-tolerant computer system design

paper_content:

In the ten years since the publication of the first edition of this book, the field of fault-tolerant design has broadened in appeal, particularly with its emerging application in distributed computing. This new edition specifically deals with this dynamically changing computing environment, incorporating new topics such as fault-tolerance in multiprocessor and distributed systems.
---
paper_title: High-Assurance Reconfigurable Multicore Processor Based Systems

paper_content:

The current trend in the silicon industry has been a steady migration towards Chip Multicore Processor (CMP) system to harvest more throughputs. However, chip multicore processors report higher values of soft errors, thereby degrading the overall system reliability. Hence, engineers have been wary of using CMP architectures for safety-critical embedded real-time system applications that require high reliability levels. The larger users of these processors also dictate the processor migration trends. With newer processor architectures, the older ones are destined to become obsolete. This paper compares typical safety-critical architectures and investigates the reliabilities of different CMP architectures. We present the fault tolerance framework and detailed reliability analysis of fault-tolerant single-core and multi-core based systems. The analysis results are then used to compare the reliability of CMP architectures with the corresponding reliability of single processor architectures. Although a CMP system does encounter degradation, by applying some system level dependability assurance mitigation features, its reliability can be enhanced. This enables CMP systems to be effectively deployed in critical applications.
---
paper_title: Thread Shadowing: Using Dynamic Redundancy on Hybrid Multi-cores for Error Detection

paper_content:

Dynamic thread duplication is a known redundancy technique for multi-cores. The approach duplicates a thread under observation for some time period and compares the signatures of the two threads to detect errors. Hybrid multi-cores, typically implemented on platform FPGAs, enable the unique option of running the thread under observation and its copy in different modalities, i.e., software and hardware. We denote our dynamic redundancy technique on hybrid multi-cores as thread shadowing. In this paper we present the concept of thread shadowing and an implementation on a multi-threaded hybrid multi-core architecture. We report on experiments with a block-processing application and demonstrate the overheads, detection latencies and coverage for a range of thread shadowing modes. The results show that trans-modal thread shadowing, although bearing long detection latencies, offers attractive coverage at a low overhead.
---
paper_title: Precise contention-aware performance prediction on virtualized multicore system

paper_content:

Virtualized multicore contention - aware performance prediction model.Virtual machine contention sensitivity and intensity features collection.Quantify the precise levels of performance degradation between VMs. Multicore systems are widely deployed in both the embedded and the high end computing infrastructures. However, traditional virtualization systems can not effectively isolate shared micro architectural resources among virtual machines (VMs) running on multicore systems. CPU and memory intensive VMs contending for these resources will lead to serious performance interference, which makes virtualization systems less efficient and VM performance less stable. In this paper, we propose a contention-aware performance prediction model on the virtualized multicore systems to quantify the performance degradation of VMs. First, we identify the performance interference factors and design synthetic micro-benchmarks to obtain VM's contention sensitivity and intensity features that are correlated with VM performance degradation. Second, based on the contention features, we build VM performance prediction model using machine learning techniques to quantify the precise levels of performance degradation. The proposed model can be used to optimize VM performance on multicore systems. Our experimental results show that the performance prediction model achieves high accuracy and the mean absolute error is 2.83%.
---
paper_title: Emulation of Transient Software Faults for Dependability Assessment: A Case Study

paper_content:

Fault Tolerance Mechanisms (FTMs) are extensively used in software systems to counteract software faults, in particular against faults that manifest transiently, namely Mandelbugs. In this scenario, Software Fault Injection (SFI) plays a key role for the verification and the improvement of FTMs. However, no previous work investigated whether SFI techniques are able to emulate Mandelbugs adequately. This is an important concern for assessing critical systems, since Mandelbugs are a major cause of failures, and FTMs are specifically tailored for this class of software faults. In this paper, we analyze an existing state-of-the-art SFI technique, namely G-SWFIT, in the context of a real-world fault-tolerant system for Air Traffic Control (ATC). The analysis highlights limitations of G-SWFIT regarding its ability to emulate the transient nature of Mandelbugs, because most of injected faults are activated in the early phase of execution, and they deterministically affect process replicas in the system. We also notice that G-SWFIT leaves untested the 35% of states of the considered system. Moreover, by means of an experiment, we show how emulation of Mandelbugs is useful to improve SFI. In particular, we emulate concurrency faults, which are a critical sub-class of Mandelbugs, in a fully representative way. We show that proper fault triggering can increase the confidence in FTMs' testing, since it is possible to reduce the amount of untested states down to 5%.
---
paper_title: A user-level library for fault tolerance on shared memory multicore systems

paper_content:

The ever decreasing transistor size has made it possible to integrate multiple cores on a single die. On the downside, this has introduced reliability concerns as smaller transistors are more prone to both transient and permanent faults. However, the abundant extra processing resources of a multicore system can be exploited to provide fault tolerance by using redundant execution. We have designed a library for multicore processing, that can make a multithreaded user-level application fault tolerant by simple modifications to the code. It uses the abundant cores found in the system to perform redundant execution for error detection. Besides that, it also allows recovery through checkpoint/rollback. Our library is portable since it does not depend on any special hardware. Furthermore, the overhead (up to 46% for 4 threads), our library adds to the original application, is less than other existing approaches, such as Respec.
---
paper_title: Two Techniques for Transient Software Error Recovery

paper_content:

The traditional approaches for fault tolerance in software — the recovery block approach and the N-version programming — are too expensive, and consequently of limited practical use. Experience has shown that techniques, such as rollback and retry, that do not employ multiple versions of software are able to mask a range of software faults that exhibit transient software failures. These techniques are cost effective as they do not employ design diversity for supporting fault tolerance. In this report we discuss two such techniques that can be used to enhance the reliability of software systems.
---
paper_title: Assessing Dependability with Software Fault Injection: A Survey

paper_content:

With the rise of software complexity, software-related accidents represent a significant threat for computer-based systems. Software Fault Injection is a method to anticipate worst-case scenarios caused by faulty software through the deliberate injection of software faults. This survey provides a comprehensive overview of the state of the art on Software Fault Injection to support researchers and practitioners in the selection of the approach that best fits their dependability assessment goals, and it discusses how these approaches have evolved to achieve fault representativeness, efficiency, and usability. The survey includes a description of relevant applications of Software Fault Injection in the context of fault-tolerant systems.
---
paper_title: Fault tolerance on multicore processors using deterministic multithreading

paper_content:

This paper describes a software based fault tolerance approach for multithreaded programs running on multicore processors. Redundant multithreaded processes are used to detect soft errors and recover from them. Our scheme makes sure that the execution of the redundant processes is identical even in the presence of non-determinism due to shared memory accesses. This is done by making sure that the redundant processes acquire the locks for accessing the shared memory in the same order. Instead of using record/replay technique to do that, our scheme is based on deterministic multithreading, meaning that for the same input, a multithreaded program always have the same lock interleaving. Unlike record/replay systems, this eliminates the requirement for communication between the redundant processes. Moreover, our scheme is implemented totally in software, requiring no special hardware, making it very portable. Furthermore, our scheme is totally implemented at user-level, requiring no modification of the kernel. For selected benchmarks, our scheme adds an average overhead of 49% for 4 threads.
---
paper_title: Formal verification of fault tolerance in safety-critical reconfigurable modules

paper_content:

Demands for higher flexibility in aerospace applications has led to increasing deployment of reconfiguarble modules. In several cases the industry is looking into Field Programmable Gate Arrays (FPGA) as a means of efficient adaption of existing components. This paper addresses the safety analysis issues for reconfigurable modules with an emphasis on FPGAs. FPGAs act as digital hardware but in the context of safety analysis they should be treated as software, i.e. with added demands on formal analysis. The contributions of this paper are twofold. First, we illustrate a development process using a language with formal semantics (Esterel) for design, formal verification of high-level design, and automatic code generation down to synthesizable VHDL. We argue that this process reduces the likelihood of systematic (permanent) faults in the design, and still produces VHDL code that may be of acceptable quality (size of FPGA, delay). Secondly, in a general approach that is equally applicable to other formal design languages, we illustrate how the effect of transient fault modes and faults in external modules can be formally studied. We modularly extended the component design model with fault models that represent specific or random faults (e.g. radiation leading to bit flips in the component under design), and transient or permanent faults in the rest of the environment. Some faults corrupt inputs to the component and others jeopardise the effect of output signals that control the environment. This process supports a formal version of Failure Modes and Effects Analysis (FMEA). The set-up is then used to formally determine which (single or multiple) fault modes cause violation of the top-level safety-related property, much in the spirit of fault-tree analyses (FTA). All of this is done with out building the fault tree and using a common model for design and for safety analyses. An aerospace hydraulic monitoring system is used to illustrate the analysis of fault tolerance .
---
paper_title: Survey of fault tolerance techniques for shared memory multicore/multiprocessor systems

paper_content:

With the advent of modern nano-scale technology, it has become possible to implement multiple processing cores on a single die. The shrinking transistor sizes however have made reliability a concern for such systems as smaller transistors are more prone to permanent as well as transient faults. To reduce the probability of failures of such systems, online fault tolerance techniques can be applied. These techniques need to be efficient as they execute concurrently with applications running on such systems. This paper discusses the challenges involved in online fault tolerance and existing work which tackles these challenges. We classify fault tolerance into four different steps which are proactive fault management, error detection, fault diagnosis and recovery and discuss related work for each step, with focus on techniques for shared memory multicore/multiprocessor systems. We also highlight the additional difficulties in tolerating faults for parallel execution on shared memory multicore/multiprocessor systems.
---
paper_title: SAFER: System-level Architecture for Failure Evasion in Real-time Applications

paper_content:

Recent trends towards increasing complexity in distributed embedded real-time systems pose challenges in designing and implementing a reliable system such as a self-driving car. The conventional way of improving reliability is to use redundant hardware to replicate the whole (sub)system. Although hardware replication has been widely deployed in hard real-time systems such as avionics, space shuttles and nuclear power plants, it is significantly less attractive to many applications because the amount of necessary hardware multiplies as the size of the system increases. The growing needs of flexible system design are also not consistent with hardware replication techniques. To address the needs of dependability through redundancy operating in real-time, we propose a layer called SAFER(System-level Architecture for Failure Evasion in Real-time applications) to incorporate configurable task-level fault-tolerance features to tolerate fail-stop processor and task failures for distributed embedded real-time systems. To detect such failures, SAFER monitors the health status and state information of each task and broadcasts the information. When a failure is detected using either time-based failure detection or event-based failure detection, SAFER reconfigures the system to retain the functionality of the whole system. We provide a formal analysis of the worst-case timing behaviors of SAFER features. We also describe the modeling of a system equipped with SAFER to analyze timing characteristics through a model-based design tool called SysWeaver. SAFER has been implemented on Ubuntu 10.04 LTS and deployed on Boss, an award-winning autonomous vehicle developed at Carnegie Mellon University. We show various measurements using simulation scenarios used during the 2007 DARPA Urban Challenge. Finally, we present a case study of failure recovery by SAFER when node failures are injected.
---
paper_title: Why Do Computers Stop And What Can Be Done About It?

paper_content:

An analysis of the failure statistics of a commercially available fault-tolerant system shows that administration and software are the major contributors to failure. Various approaches to software fault-tolerance are then discussed -- notably process-pairs, transactions and reliable storage. It is pointed out that faults in production software are often soft (transient) and that a transaction mechanism combined with persistent processpairs provides fault-tolerant execution -- the key to software fault-tolerance.
---
paper_title: Automotive embedded software: Migration challenges to multi-core computing platforms

paper_content:

The introduction of multi-core computing platforms aims at providing more computing resources and additional interfaces to answer the needs of new automotive control strategies with respect to computing performances and connectivity (e.g. connected vehicle, hybrid powertrains). At the same time, the parallel execution and resulting resources and timing conflicts require a paradigm change for the embedded software. Consequently, efficient migration of legacy software on multi-core platform, while guaranteeing at least the same level of integrity and performance as for single cores, is a significant challenge. The contributions of this paper are (1) to provide a state-of-practice survey on multi-core CPUs and operating systems for the automotive domain, and (2) based on this survey to provide guidelines for the migration of legacy SW. Finally the related challenges and opportunities for the development of high-integrity control systems on multi-cores, as platform for dependable systems are discussed.
---
paper_title: dOSEK: the design and implementation of a dependability-oriented static embedded kernel

paper_content:

Because of shrinking structure sizes and operating voltages, computing hardware exhibits an increasing susceptibility against transient hardware faults: Issues previously only known from avionics systems, such as bit flips caused by cosmic radiation, nowadays also affect automotive and other cost-sensitive “ground-level” control systems. For such cost-sensitive systems, many software-based measures have been suggested to harden applications against transient effects. However, all these measures assume that the underlying operating system works reliably in all cases. We present software-based concepts for constructing an operating system that provides a reliable computing base even on unreliable hardware. Our design is based on two pillars: First, strict fault avoidance by static tailoring and elimination of susceptible indirections. Second, reliable fault detection by finegrained arithmetic encoding of the complete kernel execution path. Compared to an industry-grade off-the-shelf RTOS, our resulting dOSEK kernel thereby achieves a robustness improvement by four orders of magnitude. Our results are based on extensive fault-injection campaigns that cover the entire space of single-bit faults in random-access memory and registers.
---
paper_title: C'Mon: a predictable monitoring infrastructure for system-level latent fault detection and recovery

paper_content:

Embedded and real-time systems must balance between many often conflicting goals including predictability, high utilization, efficiency, reliability, and SWaP (size, weight, and power). Reliability is particularly difficult to achieve without significantly impacting the other factors. Though reliability solutions exist for application-level, they are invalidated by system-level faults that are particularly difficult to detect and recover from. This paper presents the C'Mon system for predictably and efficiently monitoring system-level execution, and validating that it conforms with the high-level analytical models that underlie the timing guarantees of the system. Latent faults such as timing errors, incorrect scheduler decisions, unbounded priority inversions, or deadlocks are detected, the faulty component is identified, and using previous work in system recovery, the system is brought back to a stable state – all without missing deadlines.
---
paper_title: Predictable, Efficient System-Level Fault Tolerance in C^3

paper_content:

Predictable reliability is an increasingly important aspect of embedded and real-time systems. This includes the ability to recover from unknown faults in a manner that maintains system timing guarantees, even when these faults occur within system components. This paper presents the C3 system, which is the first system implementation we know of for predictable, system-level fault tolerance that doesn't require physical redundancy. We introduce both the system design, and two timing analyses that enable the predictable recovery from faults in operating system components, and identify recovery inversion as a main impediment to schedulable recovery. C3 provides fault-tolerance for low-level system components using a combination of efficient u-reboots, and an interface-driven mechanism to recreate component state. C3 introduces on-demand recovery that properly prioritizes aspects of the recovery process to avoid this inversion and not inhibit system timeliness. We compare this system to both eager recovery, and to check pointing of a Para virtualized real-time OS.
---
paper_title: One Bit is (Not) Enough: An Empirical Study of the Impact of Single and Multiple Bit-Flip Errors

paper_content:

Recent studies have shown that technology and voltage scaling are expected to increase the likelihood that particle-induced soft errors manifest as multiple-bit errors. This raises concerns about the validity of using single bit-flips for assessing the impact of soft errors in fault injection experiments. The goal of this paper is to investigate whether multiple-bit errors could cause a higher percentage of silent data corruptions (SDCs) compared to single-bit errors. Based on 2700 fault injection campaigns with 15 benchmark programs, featuring a total of 27 million experiments, our results show that single-bit errors in most cases yields a higher percentage of SDCs compared to multiple-bit errors. However, in 8% of the campaigns we observed a higher percentage of SDCs for multiple-bit errors. For most of these campaigns, the highest percentage of SDCs was obtained by flipping at most 3 bits. Moreover, we propose three ways of pruning the error space based on the results.
---
paper_title: Accurate Model for Application Failure Due to Transient Faults in Caches

paper_content:

To select an appropriate level of error protection in caches, the impact of various protection schemes on the cache Failure In Time (FIT) rate must be evaluated for a target benchmark suite. However, while many simulation tools exist to evaluate area, power and performance for a set of benchmark programs, there is a dearth of such tools for reliability. This paper introduces a new cache reliability model called PARMA+ that has unique features which distinguish it from previous models. PARMA+ estimates a cache's FIT rate in the presence of spatial multi-bit faults, single-bit faults, temporal multi-bit faults and different error protection schemes including parity, ECC, early write-back and bit-interleaving. We first develop the model formally, then we demonstrate its accuracy. We have run reliability simulations for many distributions of large and small fault patterns and have compared them with accelerated fault injection simulations. PARMA+ has high accuracy and low computational complexity.
---
paper_title: Risk Assessment of Railway Transportation Systems using Timed Fault Trees

paper_content:

Safety is an essential requirement for railway transportation. There are many methods that have been developed to predict, prevent, and mitigate accidents in this context. All of these methods have their own purpose and limitations. This paper presents a new useful analysis technique: timed fault tree analysis. This method extends traditional fault tree analysis with temporal events and fault characteristics. Timed fault trees (TFTs) can determine which faults need to be eliminated urgently, and it can also provide how much time have been left at least to eliminate the root failure to prevent accidents. They can also be used to determine the time taken for railway maintenance requirements, and thereby improve maintenance efficiency, and reduce risks. In this paper, we present the features and functionality of a railway transportation system, and principles and rules of TFTs. We demonstrate the applicability of our framework by a case study on a simple railway transportation system. Copyright © 2014 John Wiley & Sons, Ltd.
---
paper_title: Model Predictive Real-Time Monitoring of Linear Systems

paper_content:

The predictive monitoring problem asks whether a deployed system is likely to fail over the next T seconds under some environmental conditions. This problem is of the utmost importance for cyber-physical systems, and has inspired real-time architectures capable of adapting to such failures upon forewarning. In this paper, we present a linear model-predictive scheme for the real-time monitoring of linear systems governed by time-triggered controllers and time-varying disturbances. The scheme uses a combination of offline (advance) and online computations to decide if a given plant model has entered a state from which no matter what control is applied, the disturbance has a strategy to drive the system to an unsafe region. Our approach is independent of the control strategy used: this allows us to deal with plants that are controlled using model-predictive control techniques or even opaque machine-learning based control algorithms that are hard to reason with using existing reachable set estimation algorithms. Our online computation reuses the symbolic reachable sets computed offline. The real-time monitor instantiates the reachable set with a concrete state estimate, and repeatedly performs emptiness checks with respect to a safety property. We classify the various alarms raised by our approach in terms of what they imply about the system as a whole. We implement our real-time monitoring approach over numerous linear system benchmarks and show that the computation can be performed rapidly in practice. Furthermore, we also examine the alarms reported by our approach and show how some of the alarms can be used to improve the controller.
---
paper_title: FAME: Fault-attack Aware Microprocessor Extensions for Hardware Fault Detection and Software Fault Response

paper_content:

Fault attacks are a known serious threat to embedded software security. We propose FAME, a low-cost and flexible approach to defend embedded software against fault attacks. FAME offers a combination of fault detection in hardware and fault response in software. A hardware fault detection unit continuously monitors the system status. When a fault injection is detected, an alarm signal triggers a secure trap mechanism that passes the control to a software trap handler. The trap handler applies a suitable fault response policy, which may include a broad variety of responses such as clearing sensitive data or issuing system-wide alerts. This enables a targeted, fast fault detection as well as an application-dependent, user-defined fault response. FAME requires much lower overhead than traditional countermeasure techniques in software or hardware. We demonstrate a prototype implementation of FAME using a modified LEON3 processor, and we analyze the hardware and software overhead to thwart setup-time violation attacks. The hardware area overhead is 7.4% and 14.2% in the number of LUTs and registers, respectively. The overhead of the software trap handler on top of an AES-128 program is 0.59%--0.71% in footprint and 1.01%--2.35% in performance, depending on the security policy. In contrast, traditional countermeasures that use redundant hardware or software against similar faults have at least double overhead.
---
paper_title: Practical Task Allocation for Software Fault-Tolerance and Its Implementation in Embedded Automotive Systems

paper_content:

Due to the advent of active safety features and automated driving capabilities, the complexity of embedded computing systems within automobiles continues to increase. Such advanced driver assistance systems (ADAS) are inherently safetycritical and must tolerate failures in any subsystem. However, fault-tolerance in safety-critical systems has been traditionally supported by hardware replication, which is prohibitively expensive in terms of cost, weight, and size for the automotive market. Recent work has studied the use of software-based faulttolerance techniques that utilize task-level hot and cold standbys to tolerate fail-stop processor and task failures. The benefit of using standbys is maximal when a task and any of its standbys obey the placement constraint of not being co-located on the same processor. We propose a new heuristic based on a "tiered" placement constraint, and show that our heuristic produces a better task assignment that saves at least one processor up to 40% of the time relative to the best known heuristic to date. We then introduce a task allocation algorithm that, for the first time to our knowledge, leverages the run-time attributes of cold standbys. Our empirical study finds that our heuristic uses no more than one additional processor in most cases relative to an optimal allocation that we construct for evaluation purposes using a creative technique. We have designed and implemented our software fault-tolerance framework in AUTOSAR, an automotive industry standard. We use this implementation to provide an experimental evaluation of our task-level fault-tolerance features. Finally, we present an analysis of the worst-case behavior of our task recovery features.
---
paper_title: C'Mon: a predictable monitoring infrastructure for system-level latent fault detection and recovery

paper_content:

Embedded and real-time systems must balance between many often conflicting goals including predictability, high utilization, efficiency, reliability, and SWaP (size, weight, and power). Reliability is particularly difficult to achieve without significantly impacting the other factors. Though reliability solutions exist for application-level, they are invalidated by system-level faults that are particularly difficult to detect and recover from. This paper presents the C'Mon system for predictably and efficiently monitoring system-level execution, and validating that it conforms with the high-level analytical models that underlie the timing guarantees of the system. Latent faults such as timing errors, incorrect scheduler decisions, unbounded priority inversions, or deadlocks are detected, the faulty component is identified, and using previous work in system recovery, the system is brought back to a stable state – all without missing deadlines.
---
paper_title: Predictable, Efficient System-Level Fault Tolerance in C^3

paper_content:

Predictable reliability is an increasingly important aspect of embedded and real-time systems. This includes the ability to recover from unknown faults in a manner that maintains system timing guarantees, even when these faults occur within system components. This paper presents the C3 system, which is the first system implementation we know of for predictable, system-level fault tolerance that doesn't require physical redundancy. We introduce both the system design, and two timing analyses that enable the predictable recovery from faults in operating system components, and identify recovery inversion as a main impediment to schedulable recovery. C3 provides fault-tolerance for low-level system components using a combination of efficient u-reboots, and an interface-driven mechanism to recreate component state. C3 introduces on-demand recovery that properly prioritizes aspects of the recovery process to avoid this inversion and not inhibit system timeliness. We compare this system to both eager recovery, and to check pointing of a Para virtualized real-time OS.
---
paper_title: SAFER: System-level Architecture for Failure Evasion in Real-time Applications

paper_content:

Recent trends towards increasing complexity in distributed embedded real-time systems pose challenges in designing and implementing a reliable system such as a self-driving car. The conventional way of improving reliability is to use redundant hardware to replicate the whole (sub)system. Although hardware replication has been widely deployed in hard real-time systems such as avionics, space shuttles and nuclear power plants, it is significantly less attractive to many applications because the amount of necessary hardware multiplies as the size of the system increases. The growing needs of flexible system design are also not consistent with hardware replication techniques. To address the needs of dependability through redundancy operating in real-time, we propose a layer called SAFER(System-level Architecture for Failure Evasion in Real-time applications) to incorporate configurable task-level fault-tolerance features to tolerate fail-stop processor and task failures for distributed embedded real-time systems. To detect such failures, SAFER monitors the health status and state information of each task and broadcasts the information. When a failure is detected using either time-based failure detection or event-based failure detection, SAFER reconfigures the system to retain the functionality of the whole system. We provide a formal analysis of the worst-case timing behaviors of SAFER features. We also describe the modeling of a system equipped with SAFER to analyze timing characteristics through a model-based design tool called SysWeaver. SAFER has been implemented on Ubuntu 10.04 LTS and deployed on Boss, an award-winning autonomous vehicle developed at Carnegie Mellon University. We show various measurements using simulation scenarios used during the 2007 DARPA Urban Challenge. Finally, we present a case study of failure recovery by SAFER when node failures are injected.
---
paper_title: Real-time scheduling algorithm for safety-critical systems on faulty multicore environments

paper_content:

An algorithm (called FTM) for scheduling of real-time sporadic tasks on a multicore platform is proposed. Each task has a deadline by which it must complete its non-erroneous execution. The FTM algorithm executes backups in order to recover from errors caused by non-permanent and permanent hardware faults. The worst-case schedulability analysis of FTM algorithm is presented considering an application-level error model, which is independent of the stochastic behavior of the underlying hardware-level fault model. Then, the stochastic behavior of hardware-level fault model is plugged in to the analysis to derive the probability of meeting all the deadlines. Such probabilistic guarantee is the level of assurance (i.e., reliability) regarding the correct functional and timing behaviors of the system. One of the salient features of FTM algorithm is that it executes some backups in active redundancy to exploit the parallel multicore architecture while other backups passively to avoid unnecessary execution of too many active backups. This paper also proposes a scheme to determine for each task the number of backups that should run in active redundancy in order to increase the probability of meeting all the deadlines. The effectiveness of the proposed approach is demonstrated using an example application.
---
paper_title: A four-mode model for efficient fault-tolerant mixed-criticality systems

paper_content:

Mixed-criticality systems (MCS) integrate components from different levels of criticality onto the same platform. MCS, like all other electronic systems, are susceptible to transient faults. These systems must mitigate the effects of faults and provide recovery mechanisms when faults occur. In this paper, we consider the problem of designing and scheduling certifiable fault-tolerant mixed-criticality systems. To address certification and transient faults, two-mode models must treat any single overrun or fault as a combination of the two, reserving time for the re-execution of tasks with extended execution time. We therefore propose a new four-mode model that addresses fault and execution time overrun with separate modes. This model, combined with the selective continuation of low-criticality tasks, improves the quality of service (QoS) to these tasks while providing the same guarantee to high-criticality tasks. Experimental results show that QoS improvements of up to 42.9% can be achieved by the new model. Furthermore, we show how the model and its schedulability analysis can be calibrated to realistic failures rates to achieve even more efficient designs.
---
paper_title: On the scheduling of fault-tolerant mixed-criticality systems

paper_content:

We consider in this paper fault-tolerant mixed-criticality scheduling, where heterogeneous safety guarantees must be provided to functionalities (tasks) of varying criticalities (importances). We model explicitly the safety requirements for tasks of different criticalities according to safety standards, assuming hardware transient faults. We further provide analysis techniques to bound the effects of task killing and service degradation on the system safety and schedulability. Based on our model and analysis, we show that our problem can be converted to a conventional mixed-criticality scheduling problem. Thus, we broaden the scope of applicability of the conventional mixed-criticality scheduling techniques. Our proposed techniques are validated with a realistic flight management system application and extensive simulations.
---
paper_title: Fault-tolerant and real-time scheduling for mixed-criticality systems

paper_content:

The design and analysis of real-time scheduling algorithms for safety-critical systems is a challenging problem due to the temporal dependencies among different design constraints. This paper considers scheduling sporadic tasks with three interrelated design constraints: (i) meeting the hard deadlines of application tasks, (ii) providing fault tolerance by executing backups, and (iii) respecting the criticality of each task to facilitate system's certification. First, a new approach to model mixed-criticality systems from the perspective of fault tolerance is proposed. Second, a uniprocessor fixed-priority scheduling algorithm, called fault-tolerant mixed-criticality (FTMC) scheduling, is designed for the proposed model. The FTMC algorithm executes backups to recover from task errors caused by hardware or software faults. Third, a sufficient schedulability test is derived, when satisfied for a (mixed-criticality) task set, guarantees that all deadlines are met even if backups are executed to recover from errors. Finally, evaluations illustrate the effectiveness of the proposed test.
---
paper_title: Static mapping of mixed-critical applications for fault-tolerant MPSoCs

paper_content:

This paper presents a static mapping optimization technique for fault-tolerant mixed-criticality MPSoCs. The uncertainties imposed by system hardening and mixed criticality algorithms, such as dynamic task dropping, make the worst-case response time analysis difficult for such systems. We tackle this challenge and propose a worst-case analysis framework that considers both reliability and mixed-criticality concerns. On top of that, we build up a design space exploration engine that optimizes fault-tolerant mixed-criticality MPSoCs and provides worst-case guarantees. We study the mapping optimization considering judicious task dropping, that may impose a certain service degradation. Extensive experiments with real-life and synthetic benchmarks confirm the effectiveness of the proposed technique.
---
paper_title: Probabilistic WCET estimation in presence of hardware for mitigating the impact of permanent faults

paper_content:

Fine-grained disabling and reconfiguration of hardware elements (functional units, cache blocks) will become economically necessary to recover from permanent failures, whose rate is expected to increase dramatically in the near future. This fine-grained disabling will lead to degraded performance as compared to a fault-free execution. Until recently, all static worst-case execution time (WCET) estimations methods were assuming fault-free processors, resulting in unsafe estimates in the presence of faults. The first static WCET estimation technique dealing with the presence of permanent faults in instruction caches was proposed in [1]. This study probabilistically quantified the impact of permanent faults on WCET estimates. It demonstrated that the probabilistic WCET (pWCET) estimates of tasks increase rapidly with the probability of faults as compared to fault-free WCET estimates. In this paper, we show that very simple reliability mechanisms allow mitigating the impact of faulty cache blocks on pWCETs. Two mechanisms, that make part of the cache resilient to faults are analyzed. Experiments show that the gain in pWCET for these two mechanisms are on average 48% and 40% as compared to an architecture with no reliability mechanism.
---
paper_title: DTM: Degraded Test Mode for Fault-Aware Probabilistic Timing Analysis

paper_content:

Existing timing analysis techniques to derive Worst-Case Execution Time (WCET) estimates assume that hardware in the target platform (e.g., the CPU) is fault-free. Given the performance requirements increase in current Critical Real-Time Embedded Systems (CRTES), the use of high-performance features and smaller transistors in current and future hardware becomes a must. The use of smaller transistors helps providing more performance while maintaining low energy budgets, however, hardware fault rates increase noticeably, affecting the temporal behaviour of the system in general, and WCET in particular. In this paper, we reconcile these two emergent needs of CRTES, namely, tight (and trustworthy) WCET estimates and the use of hardware implemented with smaller transistors. To that end we propose the Degraded Test Mode (DTM) that, in combination with fault-tolerant hardware designs and probabilistic timing analysis techniques, (i) enables the computation of tight and trustworthy WCET estimates in the presence of faults, (ii) provides graceful average and worst-case performance degradation due to faults, and (iii) requires modifications neither in WCET analysis tools nor in applications. Our results show that DTM allows accounting for the effect of faults at analysis time with low impact in WCET estimates and negligible hardware modifications.
---
paper_title: Failure-Dependent timing analysis - a new methodology for probabilistic worst-case execution time analysis

paper_content:

Embedded real-time systems are growing in complexity, which goes far beyond simplistic closed-loop functionality. Current approaches for worst-case execution time (WCET) analysis are used to verify the deadlines of such systems. These approaches calculate or measure the WCET as a single value that is expected as an upper bound for a system's execution time. Overestimations are taken into account to make this upper bound a safe bound, but modern processor architectures expand those overestimations into unrealistic areas. Therefore, we present in this paper how of safety analysis model probabilities can be combined with elements of system development models to calculate a probabilistic WCET. This approach can be applied to systems that use mechanisms belonging to the area of fault tolerance, since such mechanisms are usually quantified using safety analyses to certify the system as being highly reliable or safe. A tool prototype implementing this approach is also presented which provides reliable safe upper bounds by performing a static WCET analysis and which overcomes the frequently encountered problem of dependence structures by using a fault injection approach.
---
paper_title: Static probabilistic worst case execution time estimation for architectures with faulty instruction caches

paper_content:

Semiconductor technology evolution suggests that permanent failure rates will increase dramatically with scaling, in particular for SRAM cells. While well known approaches such as error correcting codes exist to recover from failures and provide fault-free chips, they will not be affordable anymore in the future due to their growing cost. Consequently, other approaches like fine-grained disabling and reconfiguration of hardware elements (e.g. individual functional units or cache blocks) will become economically necessary. This fine-grained disabling will degrade performance compared to a fault-free execution. To the best of our knowledge, all static worst-case execution time (WCET) estimation methods assume fault-free processors. Their result is not safe anymore when fine-grained disabling of hardware components is used. In this paper we provide the first method that statically calculates a probabilistic WCET bound in the presence of permanent faults in instruction caches. The proposed method derives a probabilistic WCET bound for a program, cache configuration, and probability of cell failure. As our method relies on static analysis to bound the longest path, its probabilistic nature only stems from the probability that faults actually occur. Our method is computationally tractable because it does not require an exhaustive enumeration of all the possible combinations of faulty cache blocks. Experimental results show that it provides WCET estimates very close to, but never below, the method that derives probabilistic WCETs by enumerating all possible locations of faulty cache blocks. The proposed method not only allows to quantify the impact of permanent faults on WCET estimates, but, most importantly, can be used in architectural exploration frameworks to select the most appropriate fault management mechanisms and design parameters for current and future chip designs.
---
paper_title: Static probabilistic timing analysis in presence of faults

paper_content:

Accurate timing prediction for software execution is becoming a problem due to the increasing complexity of computer architecture, and the presence of mixed-criticality workloads. Probabilistic caches were proposed to set bounds to Worst Case Execution Time (WCET) estimates and help designers improve system resource usage. However, as technology scales down, system fault rates increase and timing behavior is affected. In this paper, we propose a Static Probabilistic Timing Analysis (SPTA) approach for caches with evict-on-miss random replacement policy using a state space modeling technique, with consideration of fault impacts on both timing analysis and task WCET. Different scenarios of transient and permanent faults are investigated. Results show that our proposed approach provides tight probabilistic WCET (pWCET) estimates and as fault rate increases, the timing behavior of the system can be affected significantly.
---
paper_title: SCIPS: An emulation methodology for fault injection in processor caches

paper_content:

Due to the high level of radiation endured by space systems, fault-tolerant verification is a critical design step for these systems. 12Space-system designers use fault-injection tools to introduce system faults and observe the system's response to these faults. Since a processor's cache accounts for a large percentage of total chip area and is thus more likely to be affected by radiation, the cache represents a key system component for fault-tolerant verification. Unfortunately, processor architectures limit cache accessibility, making direct fault injection into cache blocks impossible. Therefore, cache faults can be emulated by injecting faults into data accessed by load instructions. In this paper, we introduce SPFI-TILE, a software-based fault-injection tool for many-core devices. SPFI-TILE emulates cache fault injections by randomly injecting faults into load instructions. In order to provide unbiased fault injections, we present the cache fault-injection methodology SCIPS (Smooth Cache Injection Per Skipping). Results from MATLAB simulation and integration with SPFI-TILE reveal that SCIPS successfully distributes fault-injection probabilities across load instructions, providing an unbiased evaluation and thus more accurate verification of fault tolerance in cache memories.
---
paper_title: A fast and scalable fault injection framework to evaluate multi/many-core soft error reliability

paper_content:

Increasing chip power densities allied to the continuous technology shrink is making emerging multiprocessor embedded systems more vulnerable to soft errors. Due the high cost and design time inherent to board-based fault injection approaches, more appropriate and efficient simulation-based fault injection frameworks become crucial to guarantee the adequate design exploration support at early design phase. In this scenario, this paper proposes a fast and flexible fault injector framework, called OVPSim-FIM, which supports parallel simulation to boost up the fault injection process. Aiming at validating OVPSim-FIM, several fault injection campaigns were performed in ARM processors, considering a market leading RTOS and benchmarks with up to 10 billions of object code instructions. Results have shown that OVPSim-FIM enables to inject faults at speed of up to 10,000 MIPS, depending on the processor and the benchmark profile, enabling to identify erros and exceptions according to different criteria and classifications.
---
paper_title: A fault-injection methodology for the system-level dependability analysis of multiprocessor embedded systems

paper_content:

This paper presents a methodology for the system-level dependability analysis of multiprocessor embedded systems. The methodology is based on fault injection and features an error analysis approach offering to the designer the possibility to specify custom monitoring and classification actions at both application and architecture levels. In particular, a debug-like mechanism offers the possibility to interpret architectural raw data observed during the simulation at application level with a function call/return granularity, thus offering the possibility to analyze the propagation of the errors in the various functionalities of the executed application. A framework for automating the proposed methodology has been implemented within a state-of-the-art SystemC/TLM simulation platform for multiprocessor specifications provided with a fault injection engine. The effectiveness of the methodology has been demonstrated in two different case studies, showing how the proposed approach is able to produce an accurate dependability report highlighting the criticalities in both the architecture and the application of the system under design.
---
paper_title: Evaluating SEU fault-injection on parallel applications implemented on multicore processors

paper_content:

The widespread use of multicore processors in computing systems and the imperative necessity of exploiting massive parallelism to improve performance and dependability, make mandatory to evaluate the impact of SEUs on parallel applications running on multicore processors. This paper presents a method and preliminary results of SEU fault-injection campaigns performed on parallel applications implemented on a quad-core processor. Two representative benchmarks applications were considered for the analysis.
---
paper_title: QEMU-Based Fault Injection for a System-Level Analysis of Software Countermeasures Against Fault Attacks

paper_content:

Physical attacks, such as fault attacks, pose a decisive threat for the security of devices in the Internet of Things. An important class of countermeasures for fault attacks is fault tolerant software that is applicable for systems based on COTS hardware. In order to evaluate software countermeasures against fault attacks, fault injection is needed. However, established fault injection approaches require manufactured products or hardware details (e.g. netlists, RTL models), which are not available when using COTS hardware. In this paper, we present a QEMU-based fault injection platform that supports commercial COTS processors that are widely-used in the embedded domain. This framework allows a system-level analysis of software countermeasures by featuring the simulation of high-level hardware faults targeting, for example, memory cells, register cells, or the correct execution of instructions. The framework supports the generation of realistic fault attack scenarios. We illustrate the practicability of the approach by presenting two exemplary use cases.
---
paper_title: On the injection of hardware faults in virtualized multicore systems

paper_content:

Abstract Virtualized multicore systems represent an emerging computing paradigm in the critical systems industry. Virtualization-based solutions leverage the different cores of the processor to run operating systems and applications within separate partitions, to support the development of parallel mixed-criticality systems, and to improve fault-tolerance by protecting and isolating the operating environments. The critical systems industry is subjected to international standards, which recommend fault injection as a mean to contribute with evidence to safety cases. This paper proposes a framework to inject hardware faults in virtualized multicore systems. Our proposal capitalizes on the error reporting architecture of modern processors and allows injecting faults both at hypervisor- and guest-OS-level. We implement the framework in the context of the widely used Intel Core i7 processor and Xen hypervisor. We demonstrate the use of the framework by means of about 60,000 injection experiments in a Linux-based virtualized multicore system installation.
---
paper_title: Fault injection and fault handling: An MPSoC demonstrator using IEEE P1687

paper_content:

As fault handling in multi-processor system-on-chips (MPSoCs) is a major challenge, we have developed an MPSoC demonstrator that enables experimentation on fault injection and fault handling. Our MPSoC demonstrator consists of (1) an MPSoC model with a set of components (devices) each equipped with fault detection features, so called instruments, (2) an Instrument Access Infrastructure (IAI) based on IEEE P1687 that connects the instruments, (3) a Fault Indication and Propagation Infrastructure (FIPI) that propagates fault indications to system-level, (4) a Resource Manager (RM) to schedule jobs based on fault statuses, (5) an Instrument Manager (IM) connecting the IAI and the RM, and (6) a Fault Injection Manager (FIM) that inserts faults. The main goal of the demonstrator is to enable experimentation on different fault handling solutions. The novelty in this particular demonstrator is that it uses the existing test features, i.e. IEEE P1687 infrastructure, to assist fault handling. The demonstrator is implemented and a case study is performed.
---
paper_title: Emulation of Transient Software Faults for Dependability Assessment: A Case Study

paper_content:

Fault Tolerance Mechanisms (FTMs) are extensively used in software systems to counteract software faults, in particular against faults that manifest transiently, namely Mandelbugs. In this scenario, Software Fault Injection (SFI) plays a key role for the verification and the improvement of FTMs. However, no previous work investigated whether SFI techniques are able to emulate Mandelbugs adequately. This is an important concern for assessing critical systems, since Mandelbugs are a major cause of failures, and FTMs are specifically tailored for this class of software faults. In this paper, we analyze an existing state-of-the-art SFI technique, namely G-SWFIT, in the context of a real-world fault-tolerant system for Air Traffic Control (ATC). The analysis highlights limitations of G-SWFIT regarding its ability to emulate the transient nature of Mandelbugs, because most of injected faults are activated in the early phase of execution, and they deterministically affect process replicas in the system. We also notice that G-SWFIT leaves untested the 35% of states of the considered system. Moreover, by means of an experiment, we show how emulation of Mandelbugs is useful to improve SFI. In particular, we emulate concurrency faults, which are a critical sub-class of Mandelbugs, in a fully representative way. We show that proper fault triggering can increase the confidence in FTMs' testing, since it is possible to reduce the amount of untested states down to 5%.
---
paper_title: Assessing Dependability with Software Fault Injection: A Survey

paper_content:

With the rise of software complexity, software-related accidents represent a significant threat for computer-based systems. Software Fault Injection is a method to anticipate worst-case scenarios caused by faulty software through the deliberate injection of software faults. This survey provides a comprehensive overview of the state of the art on Software Fault Injection to support researchers and practitioners in the selection of the approach that best fits their dependability assessment goals, and it discusses how these approaches have evolved to achieve fault representativeness, efficiency, and usability. The survey includes a description of relevant applications of Software Fault Injection in the context of fault-tolerant systems.
---
paper_title: PLR: A Software Approach to Transient Fault Tolerance for Multicore Architectures

paper_content:

Transient faults are emerging as a critical concern in the reliability of general-purpose microprocessors. As architectural trends point toward multicore designs, there is substantial interest in adapting such parallel hardware resources for transient fault tolerance. This paper presents process-level redundancy (PLR), a software technique for transient fault tolerance, which leverages multiple cores for low overhead. PLR creates a set of redundant processes per application process and systematically compares the processes to guarantee correct execution. Redundancy at the process level allows the operating system to freely schedule the processes across all available hardware resources. PLR uses a software-centric approach to transient fault tolerance, which shifts the focus from ensuring correct hardware execution to ensuring correct software execution. As a result, many benign faults that do not propagate to affect program correctness can be safely ignored. A real prototype is presented that is designed to be transparent to the application and can run on general-purpose single-threaded programs without modifications to the program, operating system, or underlying hardware. The system is evaluated for fault coverage and performance on a four-way SMP machine and provides improved performance over existing software transient fault tolerance techniques with a 16.9 percent overhead for fault detection on a set of optimized SPEC2000 binaries.
---
paper_title: DTM: Degraded Test Mode for Fault-Aware Probabilistic Timing Analysis

paper_content:

Existing timing analysis techniques to derive Worst-Case Execution Time (WCET) estimates assume that hardware in the target platform (e.g., the CPU) is fault-free. Given the performance requirements increase in current Critical Real-Time Embedded Systems (CRTES), the use of high-performance features and smaller transistors in current and future hardware becomes a must. The use of smaller transistors helps providing more performance while maintaining low energy budgets, however, hardware fault rates increase noticeably, affecting the temporal behaviour of the system in general, and WCET in particular. In this paper, we reconcile these two emergent needs of CRTES, namely, tight (and trustworthy) WCET estimates and the use of hardware implemented with smaller transistors. To that end we propose the Degraded Test Mode (DTM) that, in combination with fault-tolerant hardware designs and probabilistic timing analysis techniques, (i) enables the computation of tight and trustworthy WCET estimates in the presence of faults, (ii) provides graceful average and worst-case performance degradation due to faults, and (iii) requires modifications neither in WCET analysis tools nor in applications. Our results show that DTM allows accounting for the effect of faults at analysis time with low impact in WCET estimates and negligible hardware modifications.
---
paper_title: A user-level library for fault tolerance on shared memory multicore systems

paper_content:

The ever decreasing transistor size has made it possible to integrate multiple cores on a single die. On the downside, this has introduced reliability concerns as smaller transistors are more prone to both transient and permanent faults. However, the abundant extra processing resources of a multicore system can be exploited to provide fault tolerance by using redundant execution. We have designed a library for multicore processing, that can make a multithreaded user-level application fault tolerant by simple modifications to the code. It uses the abundant cores found in the system to perform redundant execution for error detection. Besides that, it also allows recovery through checkpoint/rollback. Our library is portable since it does not depend on any special hardware. Furthermore, the overhead (up to 46% for 4 threads), our library adds to the original application, is less than other existing approaches, such as Respec.
---
paper_title: Fault tolerance on multicore processors using deterministic multithreading

paper_content:

This paper describes a software based fault tolerance approach for multithreaded programs running on multicore processors. Redundant multithreaded processes are used to detect soft errors and recover from them. Our scheme makes sure that the execution of the redundant processes is identical even in the presence of non-determinism due to shared memory accesses. This is done by making sure that the redundant processes acquire the locks for accessing the shared memory in the same order. Instead of using record/replay technique to do that, our scheme is based on deterministic multithreading, meaning that for the same input, a multithreaded program always have the same lock interleaving. Unlike record/replay systems, this eliminates the requirement for communication between the redundant processes. Moreover, our scheme is implemented totally in software, requiring no special hardware, making it very portable. Furthermore, our scheme is totally implemented at user-level, requiring no modification of the kernel. For selected benchmarks, our scheme adds an average overhead of 49% for 4 threads.
---
paper_title: Static probabilistic timing analysis in presence of faults

paper_content:

Accurate timing prediction for software execution is becoming a problem due to the increasing complexity of computer architecture, and the presence of mixed-criticality workloads. Probabilistic caches were proposed to set bounds to Worst Case Execution Time (WCET) estimates and help designers improve system resource usage. However, as technology scales down, system fault rates increase and timing behavior is affected. In this paper, we propose a Static Probabilistic Timing Analysis (SPTA) approach for caches with evict-on-miss random replacement policy using a state space modeling technique, with consideration of fault impacts on both timing analysis and task WCET. Different scenarios of transient and permanent faults are investigated. Results show that our proposed approach provides tight probabilistic WCET (pWCET) estimates and as fault rate increases, the timing behavior of the system can be affected significantly.
---
paper_title: Probabilistic WCET estimation in presence of hardware for mitigating the impact of permanent faults

paper_content:

Fine-grained disabling and reconfiguration of hardware elements (functional units, cache blocks) will become economically necessary to recover from permanent failures, whose rate is expected to increase dramatically in the near future. This fine-grained disabling will lead to degraded performance as compared to a fault-free execution. Until recently, all static worst-case execution time (WCET) estimations methods were assuming fault-free processors, resulting in unsafe estimates in the presence of faults. The first static WCET estimation technique dealing with the presence of permanent faults in instruction caches was proposed in [1]. This study probabilistically quantified the impact of permanent faults on WCET estimates. It demonstrated that the probabilistic WCET (pWCET) estimates of tasks increase rapidly with the probability of faults as compared to fault-free WCET estimates. In this paper, we show that very simple reliability mechanisms allow mitigating the impact of faulty cache blocks on pWCETs. Two mechanisms, that make part of the cache resilient to faults are analyzed. Experiments show that the gain in pWCET for these two mechanisms are on average 48% and 40% as compared to an architecture with no reliability mechanism.
---
paper_title: Practical Task Allocation for Software Fault-Tolerance and Its Implementation in Embedded Automotive Systems

paper_content:

Due to the advent of active safety features and automated driving capabilities, the complexity of embedded computing systems within automobiles continues to increase. Such advanced driver assistance systems (ADAS) are inherently safetycritical and must tolerate failures in any subsystem. However, fault-tolerance in safety-critical systems has been traditionally supported by hardware replication, which is prohibitively expensive in terms of cost, weight, and size for the automotive market. Recent work has studied the use of software-based faulttolerance techniques that utilize task-level hot and cold standbys to tolerate fail-stop processor and task failures. The benefit of using standbys is maximal when a task and any of its standbys obey the placement constraint of not being co-located on the same processor. We propose a new heuristic based on a "tiered" placement constraint, and show that our heuristic produces a better task assignment that saves at least one processor up to 40% of the time relative to the best known heuristic to date. We then introduce a task allocation algorithm that, for the first time to our knowledge, leverages the run-time attributes of cold standbys. Our empirical study finds that our heuristic uses no more than one additional processor in most cases relative to an optimal allocation that we construct for evaluation purposes using a creative technique. We have designed and implemented our software fault-tolerance framework in AUTOSAR, an automotive industry standard. We use this implementation to provide an experimental evaluation of our task-level fault-tolerance features. Finally, we present an analysis of the worst-case behavior of our task recovery features.
---
paper_title: PLR: A Software Approach to Transient Fault Tolerance for Multicore Architectures

paper_content:

Transient faults are emerging as a critical concern in the reliability of general-purpose microprocessors. As architectural trends point toward multicore designs, there is substantial interest in adapting such parallel hardware resources for transient fault tolerance. This paper presents process-level redundancy (PLR), a software technique for transient fault tolerance, which leverages multiple cores for low overhead. PLR creates a set of redundant processes per application process and systematically compares the processes to guarantee correct execution. Redundancy at the process level allows the operating system to freely schedule the processes across all available hardware resources. PLR uses a software-centric approach to transient fault tolerance, which shifts the focus from ensuring correct hardware execution to ensuring correct software execution. As a result, many benign faults that do not propagate to affect program correctness can be safely ignored. A real prototype is presented that is designed to be transparent to the application and can run on general-purpose single-threaded programs without modifications to the program, operating system, or underlying hardware. The system is evaluated for fault coverage and performance on a four-way SMP machine and provides improved performance over existing software transient fault tolerance techniques with a 16.9 percent overhead for fault detection on a set of optimized SPEC2000 binaries.
---
paper_title: Understanding Shared Memory Bank Access Interference in Multi-Core Avionics

paper_content:

Deployment of multi-core platforms in safety-critical applications requires reliable estimation of worst-case response time (WCRT) for critical processes. Determination of WCRT needs to accurately ...
---
paper_title: Thread Shadowing: Using Dynamic Redundancy on Hybrid Multi-cores for Error Detection

paper_content:

Dynamic thread duplication is a known redundancy technique for multi-cores. The approach duplicates a thread under observation for some time period and compares the signatures of the two threads to detect errors. Hybrid multi-cores, typically implemented on platform FPGAs, enable the unique option of running the thread under observation and its copy in different modalities, i.e., software and hardware. We denote our dynamic redundancy technique on hybrid multi-cores as thread shadowing. In this paper we present the concept of thread shadowing and an implementation on a multi-threaded hybrid multi-core architecture. We report on experiments with a block-processing application and demonstrate the overheads, detection latencies and coverage for a range of thread shadowing modes. The results show that trans-modal thread shadowing, although bearing long detection latencies, offers attractive coverage at a low overhead.
---
paper_title: A four-mode model for efficient fault-tolerant mixed-criticality systems

paper_content:

Mixed-criticality systems (MCS) integrate components from different levels of criticality onto the same platform. MCS, like all other electronic systems, are susceptible to transient faults. These systems must mitigate the effects of faults and provide recovery mechanisms when faults occur. In this paper, we consider the problem of designing and scheduling certifiable fault-tolerant mixed-criticality systems. To address certification and transient faults, two-mode models must treat any single overrun or fault as a combination of the two, reserving time for the re-execution of tasks with extended execution time. We therefore propose a new four-mode model that addresses fault and execution time overrun with separate modes. This model, combined with the selective continuation of low-criticality tasks, improves the quality of service (QoS) to these tasks while providing the same guarantee to high-criticality tasks. Experimental results show that QoS improvements of up to 42.9% can be achieved by the new model. Furthermore, we show how the model and its schedulability analysis can be calibrated to realistic failures rates to achieve even more efficient designs.
---
paper_title: DTM: Degraded Test Mode for Fault-Aware Probabilistic Timing Analysis

paper_content:

Existing timing analysis techniques to derive Worst-Case Execution Time (WCET) estimates assume that hardware in the target platform (e.g., the CPU) is fault-free. Given the performance requirements increase in current Critical Real-Time Embedded Systems (CRTES), the use of high-performance features and smaller transistors in current and future hardware becomes a must. The use of smaller transistors helps providing more performance while maintaining low energy budgets, however, hardware fault rates increase noticeably, affecting the temporal behaviour of the system in general, and WCET in particular. In this paper, we reconcile these two emergent needs of CRTES, namely, tight (and trustworthy) WCET estimates and the use of hardware implemented with smaller transistors. To that end we propose the Degraded Test Mode (DTM) that, in combination with fault-tolerant hardware designs and probabilistic timing analysis techniques, (i) enables the computation of tight and trustworthy WCET estimates in the presence of faults, (ii) provides graceful average and worst-case performance degradation due to faults, and (iii) requires modifications neither in WCET analysis tools nor in applications. Our results show that DTM allows accounting for the effect of faults at analysis time with low impact in WCET estimates and negligible hardware modifications.
---
paper_title: On the scheduling of fault-tolerant mixed-criticality systems

paper_content:

We consider in this paper fault-tolerant mixed-criticality scheduling, where heterogeneous safety guarantees must be provided to functionalities (tasks) of varying criticalities (importances). We model explicitly the safety requirements for tasks of different criticalities according to safety standards, assuming hardware transient faults. We further provide analysis techniques to bound the effects of task killing and service degradation on the system safety and schedulability. Based on our model and analysis, we show that our problem can be converted to a conventional mixed-criticality scheduling problem. Thus, we broaden the scope of applicability of the conventional mixed-criticality scheduling techniques. Our proposed techniques are validated with a realistic flight management system application and extensive simulations.
---
paper_title: A user-level library for fault tolerance on shared memory multicore systems

paper_content:

The ever decreasing transistor size has made it possible to integrate multiple cores on a single die. On the downside, this has introduced reliability concerns as smaller transistors are more prone to both transient and permanent faults. However, the abundant extra processing resources of a multicore system can be exploited to provide fault tolerance by using redundant execution. We have designed a library for multicore processing, that can make a multithreaded user-level application fault tolerant by simple modifications to the code. It uses the abundant cores found in the system to perform redundant execution for error detection. Besides that, it also allows recovery through checkpoint/rollback. Our library is portable since it does not depend on any special hardware. Furthermore, the overhead (up to 46% for 4 threads), our library adds to the original application, is less than other existing approaches, such as Respec.
---
paper_title: WCET(m) Estimation in Multi-core Systems Using Single Core Equivalence

paper_content:

Multi-core platforms represent the answer of the industry to the increasing demand for computational capabilities. From a real-time perspective, however, the inherent sharing of resources, such as memory subsystem and I/O channels, creates inter-core timing interference among critical tasks and applications deployed on different cores. As a result, modular per-core certification cannot be performed, meaning that: (1) current industrial engineering processes cannot be reused, (2) software developed and certified for single-core chips cannot be deployed on multi-core platforms as is. In this work, we propose the Single Core Equivalence (SCE) technology: a framework of OS-level techniques designed for commercial (COTS) architectures that exports a set of equivalent single-core virtual machines from a multi-core platform. This allows per-core schedulability results to be calculated in isolation and to hold when multiple cores of the system run in parallel. Thus, SCE allows each core of a multi-core chip to be considered as a conventional single-core chip, ultimately enabling industry to reuse existing software, schedulability analysis methodologies and engineering processes.
---
paper_title: Fault tolerance on multicore processors using deterministic multithreading

paper_content:

This paper describes a software based fault tolerance approach for multithreaded programs running on multicore processors. Redundant multithreaded processes are used to detect soft errors and recover from them. Our scheme makes sure that the execution of the redundant processes is identical even in the presence of non-determinism due to shared memory accesses. This is done by making sure that the redundant processes acquire the locks for accessing the shared memory in the same order. Instead of using record/replay technique to do that, our scheme is based on deterministic multithreading, meaning that for the same input, a multithreaded program always have the same lock interleaving. Unlike record/replay systems, this eliminates the requirement for communication between the redundant processes. Moreover, our scheme is implemented totally in software, requiring no special hardware, making it very portable. Furthermore, our scheme is totally implemented at user-level, requiring no modification of the kernel. For selected benchmarks, our scheme adds an average overhead of 49% for 4 threads.
---
paper_title: Failure-Dependent timing analysis - a new methodology for probabilistic worst-case execution time analysis

paper_content:

Embedded real-time systems are growing in complexity, which goes far beyond simplistic closed-loop functionality. Current approaches for worst-case execution time (WCET) analysis are used to verify the deadlines of such systems. These approaches calculate or measure the WCET as a single value that is expected as an upper bound for a system's execution time. Overestimations are taken into account to make this upper bound a safe bound, but modern processor architectures expand those overestimations into unrealistic areas. Therefore, we present in this paper how of safety analysis model probabilities can be combined with elements of system development models to calculate a probabilistic WCET. This approach can be applied to systems that use mechanisms belonging to the area of fault tolerance, since such mechanisms are usually quantified using safety analyses to certify the system as being highly reliable or safe. A tool prototype implementing this approach is also presented which provides reliable safe upper bounds by performing a static WCET analysis and which overcomes the frequently encountered problem of dependence structures by using a fault injection approach.
---
paper_title: Static probabilistic worst case execution time estimation for architectures with faulty instruction caches

paper_content:

Semiconductor technology evolution suggests that permanent failure rates will increase dramatically with scaling, in particular for SRAM cells. While well known approaches such as error correcting codes exist to recover from failures and provide fault-free chips, they will not be affordable anymore in the future due to their growing cost. Consequently, other approaches like fine-grained disabling and reconfiguration of hardware elements (e.g. individual functional units or cache blocks) will become economically necessary. This fine-grained disabling will degrade performance compared to a fault-free execution. To the best of our knowledge, all static worst-case execution time (WCET) estimation methods assume fault-free processors. Their result is not safe anymore when fine-grained disabling of hardware components is used. In this paper we provide the first method that statically calculates a probabilistic WCET bound in the presence of permanent faults in instruction caches. The proposed method derives a probabilistic WCET bound for a program, cache configuration, and probability of cell failure. As our method relies on static analysis to bound the longest path, its probabilistic nature only stems from the probability that faults actually occur. Our method is computationally tractable because it does not require an exhaustive enumeration of all the possible combinations of faulty cache blocks. Experimental results show that it provides WCET estimates very close to, but never below, the method that derives probabilistic WCETs by enumerating all possible locations of faulty cache blocks. The proposed method not only allows to quantify the impact of permanent faults on WCET estimates, but, most importantly, can be used in architectural exploration frameworks to select the most appropriate fault management mechanisms and design parameters for current and future chip designs.
---
paper_title: Survey of fault tolerance techniques for shared memory multicore/multiprocessor systems

paper_content:

With the advent of modern nano-scale technology, it has become possible to implement multiple processing cores on a single die. The shrinking transistor sizes however have made reliability a concern for such systems as smaller transistors are more prone to permanent as well as transient faults. To reduce the probability of failures of such systems, online fault tolerance techniques can be applied. These techniques need to be efficient as they execute concurrently with applications running on such systems. This paper discusses the challenges involved in online fault tolerance and existing work which tackles these challenges. We classify fault tolerance into four different steps which are proactive fault management, error detection, fault diagnosis and recovery and discuss related work for each step, with focus on techniques for shared memory multicore/multiprocessor systems. We also highlight the additional difficulties in tolerating faults for parallel execution on shared memory multicore/multiprocessor systems.
---
paper_title: SAFER: System-level Architecture for Failure Evasion in Real-time Applications

paper_content:

Recent trends towards increasing complexity in distributed embedded real-time systems pose challenges in designing and implementing a reliable system such as a self-driving car. The conventional way of improving reliability is to use redundant hardware to replicate the whole (sub)system. Although hardware replication has been widely deployed in hard real-time systems such as avionics, space shuttles and nuclear power plants, it is significantly less attractive to many applications because the amount of necessary hardware multiplies as the size of the system increases. The growing needs of flexible system design are also not consistent with hardware replication techniques. To address the needs of dependability through redundancy operating in real-time, we propose a layer called SAFER(System-level Architecture for Failure Evasion in Real-time applications) to incorporate configurable task-level fault-tolerance features to tolerate fail-stop processor and task failures for distributed embedded real-time systems. To detect such failures, SAFER monitors the health status and state information of each task and broadcasts the information. When a failure is detected using either time-based failure detection or event-based failure detection, SAFER reconfigures the system to retain the functionality of the whole system. We provide a formal analysis of the worst-case timing behaviors of SAFER features. We also describe the modeling of a system equipped with SAFER to analyze timing characteristics through a model-based design tool called SysWeaver. SAFER has been implemented on Ubuntu 10.04 LTS and deployed on Boss, an award-winning autonomous vehicle developed at Carnegie Mellon University. We show various measurements using simulation scenarios used during the 2007 DARPA Urban Challenge. Finally, we present a case study of failure recovery by SAFER when node failures are injected.
---
paper_title: Fault-tolerant and real-time scheduling for mixed-criticality systems

paper_content:

The design and analysis of real-time scheduling algorithms for safety-critical systems is a challenging problem due to the temporal dependencies among different design constraints. This paper considers scheduling sporadic tasks with three interrelated design constraints: (i) meeting the hard deadlines of application tasks, (ii) providing fault tolerance by executing backups, and (iii) respecting the criticality of each task to facilitate system's certification. First, a new approach to model mixed-criticality systems from the perspective of fault tolerance is proposed. Second, a uniprocessor fixed-priority scheduling algorithm, called fault-tolerant mixed-criticality (FTMC) scheduling, is designed for the proposed model. The FTMC algorithm executes backups to recover from task errors caused by hardware or software faults. Third, a sufficient schedulability test is derived, when satisfied for a (mixed-criticality) task set, guarantees that all deadlines are met even if backups are executed to recover from errors. Finally, evaluations illustrate the effectiveness of the proposed test.
---
paper_title: Static mapping of mixed-critical applications for fault-tolerant MPSoCs

paper_content:

This paper presents a static mapping optimization technique for fault-tolerant mixed-criticality MPSoCs. The uncertainties imposed by system hardening and mixed criticality algorithms, such as dynamic task dropping, make the worst-case response time analysis difficult for such systems. We tackle this challenge and propose a worst-case analysis framework that considers both reliability and mixed-criticality concerns. On top of that, we build up a design space exploration engine that optimizes fault-tolerant mixed-criticality MPSoCs and provides worst-case guarantees. We study the mapping optimization considering judicious task dropping, that may impose a certain service degradation. Extensive experiments with real-life and synthetic benchmarks confirm the effectiveness of the proposed technique.
---
paper_title: Static probabilistic timing analysis in presence of faults

paper_content:

Accurate timing prediction for software execution is becoming a problem due to the increasing complexity of computer architecture, and the presence of mixed-criticality workloads. Probabilistic caches were proposed to set bounds to Worst Case Execution Time (WCET) estimates and help designers improve system resource usage. However, as technology scales down, system fault rates increase and timing behavior is affected. In this paper, we propose a Static Probabilistic Timing Analysis (SPTA) approach for caches with evict-on-miss random replacement policy using a state space modeling technique, with consideration of fault impacts on both timing analysis and task WCET. Different scenarios of transient and permanent faults are investigated. Results show that our proposed approach provides tight probabilistic WCET (pWCET) estimates and as fault rate increases, the timing behavior of the system can be affected significantly.
---
paper_title: Probabilistic WCET estimation in presence of hardware for mitigating the impact of permanent faults

paper_content:

Fine-grained disabling and reconfiguration of hardware elements (functional units, cache blocks) will become economically necessary to recover from permanent failures, whose rate is expected to increase dramatically in the near future. This fine-grained disabling will lead to degraded performance as compared to a fault-free execution. Until recently, all static worst-case execution time (WCET) estimations methods were assuming fault-free processors, resulting in unsafe estimates in the presence of faults. The first static WCET estimation technique dealing with the presence of permanent faults in instruction caches was proposed in [1]. This study probabilistically quantified the impact of permanent faults on WCET estimates. It demonstrated that the probabilistic WCET (pWCET) estimates of tasks increase rapidly with the probability of faults as compared to fault-free WCET estimates. In this paper, we show that very simple reliability mechanisms allow mitigating the impact of faulty cache blocks on pWCETs. Two mechanisms, that make part of the cache resilient to faults are analyzed. Experiments show that the gain in pWCET for these two mechanisms are on average 48% and 40% as compared to an architecture with no reliability mechanism.
---
paper_title: Practical Task Allocation for Software Fault-Tolerance and Its Implementation in Embedded Automotive Systems

paper_content:

Due to the advent of active safety features and automated driving capabilities, the complexity of embedded computing systems within automobiles continues to increase. Such advanced driver assistance systems (ADAS) are inherently safetycritical and must tolerate failures in any subsystem. However, fault-tolerance in safety-critical systems has been traditionally supported by hardware replication, which is prohibitively expensive in terms of cost, weight, and size for the automotive market. Recent work has studied the use of software-based faulttolerance techniques that utilize task-level hot and cold standbys to tolerate fail-stop processor and task failures. The benefit of using standbys is maximal when a task and any of its standbys obey the placement constraint of not being co-located on the same processor. We propose a new heuristic based on a "tiered" placement constraint, and show that our heuristic produces a better task assignment that saves at least one processor up to 40% of the time relative to the best known heuristic to date. We then introduce a task allocation algorithm that, for the first time to our knowledge, leverages the run-time attributes of cold standbys. Our empirical study finds that our heuristic uses no more than one additional processor in most cases relative to an optimal allocation that we construct for evaluation purposes using a creative technique. We have designed and implemented our software fault-tolerance framework in AUTOSAR, an automotive industry standard. We use this implementation to provide an experimental evaluation of our task-level fault-tolerance features. Finally, we present an analysis of the worst-case behavior of our task recovery features.
---
paper_title: PLR: A Software Approach to Transient Fault Tolerance for Multicore Architectures

paper_content:

Transient faults are emerging as a critical concern in the reliability of general-purpose microprocessors. As architectural trends point toward multicore designs, there is substantial interest in adapting such parallel hardware resources for transient fault tolerance. This paper presents process-level redundancy (PLR), a software technique for transient fault tolerance, which leverages multiple cores for low overhead. PLR creates a set of redundant processes per application process and systematically compares the processes to guarantee correct execution. Redundancy at the process level allows the operating system to freely schedule the processes across all available hardware resources. PLR uses a software-centric approach to transient fault tolerance, which shifts the focus from ensuring correct hardware execution to ensuring correct software execution. As a result, many benign faults that do not propagate to affect program correctness can be safely ignored. A real prototype is presented that is designed to be transparent to the application and can run on general-purpose single-threaded programs without modifications to the program, operating system, or underlying hardware. The system is evaluated for fault coverage and performance on a four-way SMP machine and provides improved performance over existing software transient fault tolerance techniques with a 16.9 percent overhead for fault detection on a set of optimized SPEC2000 binaries.
---
paper_title: A fast and scalable fault injection framework to evaluate multi/many-core soft error reliability

paper_content:

Increasing chip power densities allied to the continuous technology shrink is making emerging multiprocessor embedded systems more vulnerable to soft errors. Due the high cost and design time inherent to board-based fault injection approaches, more appropriate and efficient simulation-based fault injection frameworks become crucial to guarantee the adequate design exploration support at early design phase. In this scenario, this paper proposes a fast and flexible fault injector framework, called OVPSim-FIM, which supports parallel simulation to boost up the fault injection process. Aiming at validating OVPSim-FIM, several fault injection campaigns were performed in ARM processors, considering a market leading RTOS and benchmarks with up to 10 billions of object code instructions. Results have shown that OVPSim-FIM enables to inject faults at speed of up to 10,000 MIPS, depending on the processor and the benchmark profile, enabling to identify erros and exceptions according to different criteria and classifications.
---
paper_title: C'Mon: a predictable monitoring infrastructure for system-level latent fault detection and recovery

paper_content:

Embedded and real-time systems must balance between many often conflicting goals including predictability, high utilization, efficiency, reliability, and SWaP (size, weight, and power). Reliability is particularly difficult to achieve without significantly impacting the other factors. Though reliability solutions exist for application-level, they are invalidated by system-level faults that are particularly difficult to detect and recover from. This paper presents the C'Mon system for predictably and efficiently monitoring system-level execution, and validating that it conforms with the high-level analytical models that underlie the timing guarantees of the system. Latent faults such as timing errors, incorrect scheduler decisions, unbounded priority inversions, or deadlocks are detected, the faulty component is identified, and using previous work in system recovery, the system is brought back to a stable state – all without missing deadlines.
---
paper_title: Predictable, Efficient System-Level Fault Tolerance in C^3

paper_content:

Predictable reliability is an increasingly important aspect of embedded and real-time systems. This includes the ability to recover from unknown faults in a manner that maintains system timing guarantees, even when these faults occur within system components. This paper presents the C3 system, which is the first system implementation we know of for predictable, system-level fault tolerance that doesn't require physical redundancy. We introduce both the system design, and two timing analyses that enable the predictable recovery from faults in operating system components, and identify recovery inversion as a main impediment to schedulable recovery. C3 provides fault-tolerance for low-level system components using a combination of efficient u-reboots, and an interface-driven mechanism to recreate component state. C3 introduces on-demand recovery that properly prioritizes aspects of the recovery process to avoid this inversion and not inhibit system timeliness. We compare this system to both eager recovery, and to check pointing of a Para virtualized real-time OS.
---
paper_title: DTM: Degraded Test Mode for Fault-Aware Probabilistic Timing Analysis

paper_content:

Existing timing analysis techniques to derive Worst-Case Execution Time (WCET) estimates assume that hardware in the target platform (e.g., the CPU) is fault-free. Given the performance requirements increase in current Critical Real-Time Embedded Systems (CRTES), the use of high-performance features and smaller transistors in current and future hardware becomes a must. The use of smaller transistors helps providing more performance while maintaining low energy budgets, however, hardware fault rates increase noticeably, affecting the temporal behaviour of the system in general, and WCET in particular. In this paper, we reconcile these two emergent needs of CRTES, namely, tight (and trustworthy) WCET estimates and the use of hardware implemented with smaller transistors. To that end we propose the Degraded Test Mode (DTM) that, in combination with fault-tolerant hardware designs and probabilistic timing analysis techniques, (i) enables the computation of tight and trustworthy WCET estimates in the presence of faults, (ii) provides graceful average and worst-case performance degradation due to faults, and (iii) requires modifications neither in WCET analysis tools nor in applications. Our results show that DTM allows accounting for the effect of faults at analysis time with low impact in WCET estimates and negligible hardware modifications.
---
paper_title: A fault-injection methodology for the system-level dependability analysis of multiprocessor embedded systems

paper_content:

This paper presents a methodology for the system-level dependability analysis of multiprocessor embedded systems. The methodology is based on fault injection and features an error analysis approach offering to the designer the possibility to specify custom monitoring and classification actions at both application and architecture levels. In particular, a debug-like mechanism offers the possibility to interpret architectural raw data observed during the simulation at application level with a function call/return granularity, thus offering the possibility to analyze the propagation of the errors in the various functionalities of the executed application. A framework for automating the proposed methodology has been implemented within a state-of-the-art SystemC/TLM simulation platform for multiprocessor specifications provided with a fault injection engine. The effectiveness of the methodology has been demonstrated in two different case studies, showing how the proposed approach is able to produce an accurate dependability report highlighting the criticalities in both the architecture and the application of the system under design.
---
paper_title: QEMU-Based Fault Injection for a System-Level Analysis of Software Countermeasures Against Fault Attacks

paper_content:

Physical attacks, such as fault attacks, pose a decisive threat for the security of devices in the Internet of Things. An important class of countermeasures for fault attacks is fault tolerant software that is applicable for systems based on COTS hardware. In order to evaluate software countermeasures against fault attacks, fault injection is needed. However, established fault injection approaches require manufactured products or hardware details (e.g. netlists, RTL models), which are not available when using COTS hardware. In this paper, we present a QEMU-based fault injection platform that supports commercial COTS processors that are widely-used in the embedded domain. This framework allows a system-level analysis of software countermeasures by featuring the simulation of high-level hardware faults targeting, for example, memory cells, register cells, or the correct execution of instructions. The framework supports the generation of realistic fault attack scenarios. We illustrate the practicability of the approach by presenting two exemplary use cases.
---
paper_title: Failure-Dependent timing analysis - a new methodology for probabilistic worst-case execution time analysis

paper_content:

Embedded real-time systems are growing in complexity, which goes far beyond simplistic closed-loop functionality. Current approaches for worst-case execution time (WCET) analysis are used to verify the deadlines of such systems. These approaches calculate or measure the WCET as a single value that is expected as an upper bound for a system's execution time. Overestimations are taken into account to make this upper bound a safe bound, but modern processor architectures expand those overestimations into unrealistic areas. Therefore, we present in this paper how of safety analysis model probabilities can be combined with elements of system development models to calculate a probabilistic WCET. This approach can be applied to systems that use mechanisms belonging to the area of fault tolerance, since such mechanisms are usually quantified using safety analyses to certify the system as being highly reliable or safe. A tool prototype implementing this approach is also presented which provides reliable safe upper bounds by performing a static WCET analysis and which overcomes the frequently encountered problem of dependence structures by using a fault injection approach.
---
paper_title: Static probabilistic worst case execution time estimation for architectures with faulty instruction caches

paper_content:

Semiconductor technology evolution suggests that permanent failure rates will increase dramatically with scaling, in particular for SRAM cells. While well known approaches such as error correcting codes exist to recover from failures and provide fault-free chips, they will not be affordable anymore in the future due to their growing cost. Consequently, other approaches like fine-grained disabling and reconfiguration of hardware elements (e.g. individual functional units or cache blocks) will become economically necessary. This fine-grained disabling will degrade performance compared to a fault-free execution. To the best of our knowledge, all static worst-case execution time (WCET) estimation methods assume fault-free processors. Their result is not safe anymore when fine-grained disabling of hardware components is used. In this paper we provide the first method that statically calculates a probabilistic WCET bound in the presence of permanent faults in instruction caches. The proposed method derives a probabilistic WCET bound for a program, cache configuration, and probability of cell failure. As our method relies on static analysis to bound the longest path, its probabilistic nature only stems from the probability that faults actually occur. Our method is computationally tractable because it does not require an exhaustive enumeration of all the possible combinations of faulty cache blocks. Experimental results show that it provides WCET estimates very close to, but never below, the method that derives probabilistic WCETs by enumerating all possible locations of faulty cache blocks. The proposed method not only allows to quantify the impact of permanent faults on WCET estimates, but, most importantly, can be used in architectural exploration frameworks to select the most appropriate fault management mechanisms and design parameters for current and future chip designs.
---
paper_title: Open Challenges for Probabilistic Measurement-Based Worst-Case Execution Time

paper_content:

The worst-case execution time (WCET) is a critical parameter describing the largest value for the execution time of programs. Even though such a parameter is very hard to attain, it is essential as part of guaranteeing a real-time system meets its timing requirements. The complexity of modern hardware has increased the challenges of statically analyzing the WCET and reduced the reliability of purely measuring the WCET. This has led to the emergence of probabilistic WCETs (pWCETs) analysis as a viable technique. The low probability of appearance of large execution times of a program has motivated the utilization of rare events theory like extreme value theory (EVT). As pWCET estimation based on EVT has matured as a discipline, a number of open challenges have become apparent when applying the existing approaches. This letter enumerates key challenges while establishing a state of the art of EVT-based pWCET estimation methods.
---
paper_title: SAFER: System-level Architecture for Failure Evasion in Real-time Applications

paper_content:

Recent trends towards increasing complexity in distributed embedded real-time systems pose challenges in designing and implementing a reliable system such as a self-driving car. The conventional way of improving reliability is to use redundant hardware to replicate the whole (sub)system. Although hardware replication has been widely deployed in hard real-time systems such as avionics, space shuttles and nuclear power plants, it is significantly less attractive to many applications because the amount of necessary hardware multiplies as the size of the system increases. The growing needs of flexible system design are also not consistent with hardware replication techniques. To address the needs of dependability through redundancy operating in real-time, we propose a layer called SAFER(System-level Architecture for Failure Evasion in Real-time applications) to incorporate configurable task-level fault-tolerance features to tolerate fail-stop processor and task failures for distributed embedded real-time systems. To detect such failures, SAFER monitors the health status and state information of each task and broadcasts the information. When a failure is detected using either time-based failure detection or event-based failure detection, SAFER reconfigures the system to retain the functionality of the whole system. We provide a formal analysis of the worst-case timing behaviors of SAFER features. We also describe the modeling of a system equipped with SAFER to analyze timing characteristics through a model-based design tool called SysWeaver. SAFER has been implemented on Ubuntu 10.04 LTS and deployed on Boss, an award-winning autonomous vehicle developed at Carnegie Mellon University. We show various measurements using simulation scenarios used during the 2007 DARPA Urban Challenge. Finally, we present a case study of failure recovery by SAFER when node failures are injected.
---
paper_title: Fault injection and fault handling: An MPSoC demonstrator using IEEE P1687

paper_content:

As fault handling in multi-processor system-on-chips (MPSoCs) is a major challenge, we have developed an MPSoC demonstrator that enables experimentation on fault injection and fault handling. Our MPSoC demonstrator consists of (1) an MPSoC model with a set of components (devices) each equipped with fault detection features, so called instruments, (2) an Instrument Access Infrastructure (IAI) based on IEEE P1687 that connects the instruments, (3) a Fault Indication and Propagation Infrastructure (FIPI) that propagates fault indications to system-level, (4) a Resource Manager (RM) to schedule jobs based on fault statuses, (5) an Instrument Manager (IM) connecting the IAI and the RM, and (6) a Fault Injection Manager (FIM) that inserts faults. The main goal of the demonstrator is to enable experimentation on different fault handling solutions. The novelty in this particular demonstrator is that it uses the existing test features, i.e. IEEE P1687 infrastructure, to assist fault handling. The demonstrator is implemented and a case study is performed.
---
paper_title: Static probabilistic timing analysis in presence of faults

paper_content:

Accurate timing prediction for software execution is becoming a problem due to the increasing complexity of computer architecture, and the presence of mixed-criticality workloads. Probabilistic caches were proposed to set bounds to Worst Case Execution Time (WCET) estimates and help designers improve system resource usage. However, as technology scales down, system fault rates increase and timing behavior is affected. In this paper, we propose a Static Probabilistic Timing Analysis (SPTA) approach for caches with evict-on-miss random replacement policy using a state space modeling technique, with consideration of fault impacts on both timing analysis and task WCET. Different scenarios of transient and permanent faults are investigated. Results show that our proposed approach provides tight probabilistic WCET (pWCET) estimates and as fault rate increases, the timing behavior of the system can be affected significantly.
---
paper_title: Emulation of Transient Software Faults for Dependability Assessment: A Case Study

paper_content:

Fault Tolerance Mechanisms (FTMs) are extensively used in software systems to counteract software faults, in particular against faults that manifest transiently, namely Mandelbugs. In this scenario, Software Fault Injection (SFI) plays a key role for the verification and the improvement of FTMs. However, no previous work investigated whether SFI techniques are able to emulate Mandelbugs adequately. This is an important concern for assessing critical systems, since Mandelbugs are a major cause of failures, and FTMs are specifically tailored for this class of software faults. In this paper, we analyze an existing state-of-the-art SFI technique, namely G-SWFIT, in the context of a real-world fault-tolerant system for Air Traffic Control (ATC). The analysis highlights limitations of G-SWFIT regarding its ability to emulate the transient nature of Mandelbugs, because most of injected faults are activated in the early phase of execution, and they deterministically affect process replicas in the system. We also notice that G-SWFIT leaves untested the 35% of states of the considered system. Moreover, by means of an experiment, we show how emulation of Mandelbugs is useful to improve SFI. In particular, we emulate concurrency faults, which are a critical sub-class of Mandelbugs, in a fully representative way. We show that proper fault triggering can increase the confidence in FTMs' testing, since it is possible to reduce the amount of untested states down to 5%.
---
paper_title: Evaluating SEU fault-injection on parallel applications implemented on multicore processors

paper_content:

The widespread use of multicore processors in computing systems and the imperative necessity of exploiting massive parallelism to improve performance and dependability, make mandatory to evaluate the impact of SEUs on parallel applications running on multicore processors. This paper presents a method and preliminary results of SEU fault-injection campaigns performed on parallel applications implemented on a quad-core processor. Two representative benchmarks applications were considered for the analysis.
---
paper_title: On the injection of hardware faults in virtualized multicore systems

paper_content:

Abstract Virtualized multicore systems represent an emerging computing paradigm in the critical systems industry. Virtualization-based solutions leverage the different cores of the processor to run operating systems and applications within separate partitions, to support the development of parallel mixed-criticality systems, and to improve fault-tolerance by protecting and isolating the operating environments. The critical systems industry is subjected to international standards, which recommend fault injection as a mean to contribute with evidence to safety cases. This paper proposes a framework to inject hardware faults in virtualized multicore systems. Our proposal capitalizes on the error reporting architecture of modern processors and allows injecting faults both at hypervisor- and guest-OS-level. We implement the framework in the context of the widely used Intel Core i7 processor and Xen hypervisor. We demonstrate the use of the framework by means of about 60,000 injection experiments in a Linux-based virtualized multicore system installation.
---

Title: Fault and Timing Analysis in Critical Multi-Core Systems: A Survey with an Avionics Perspective

Section 1: Introduction
Description 1: Introduces the problem statement and the purpose of the paper, providing an overview of the complexities introduced by multi-core systems in the context of safety-critical avionics systems.

Section 2: Basic Concepts
Description 2: Reviews some basic notions used in the rest of the paper, essential for understanding the concepts discussed.

Section 3: Fault Tolerance Methods 
Description 3: Discusses representative fault tolerance methods targeting transient and permanent hardware faults in multi-core systems.

Section 4: Fault Injection 
Description 4: Examines fault injection techniques and their applicability in multi-core systems, especially for validating fault tolerance mechanisms.

Section 5: Safety-Critical Systems
Description 5: Provides an overview of safety critical systems across various domains and their safety standards that guide validation and certification.

Section 6: Mixed-Criticality Systems
Description 6: Discusses the concept of mixed-criticality systems, which host functions with different safety levels on the same computing platform.

Section 7: WCET Estimations
Description 7: Explores methods for estimating worst-case execution time (WCET) on multi-core processors and their complexities, especially in the presence of faults.

Section 8: Fault Injection Emulating Hardware Faults
Description 8: Focuses on methods for injecting faults in hardware components to study the robustness of multi-core systems.

Section 9: Fault Injection Emulating Software Bugs
Description 9: Discusses software fault injection techniques for simulating software errors and their effectiveness in multi-core systems.

Section 10: Discussions
Description 10: Compares and evaluates the surveyed methods regarding their applicability to fault tolerance in multi-core systems.

Section 11: Conclusion
Description 11: Summarizes the findings, identifying gaps and future research directions for WCET/WCRT estimation and fault tolerance in multi-core systems.