Search

This paper presents a formal model for the scheduler of Contiki, which is an event-driven lightweight Operating System for the Internet of Things (IoT). The proposed formal model enhances our knowledge regarding the most critical components of Contiki, namely its process and event queues, and its scheduler. We first derive a state machine-based abstraction of the scheduler’s modes of operation along with the control flow abstractions of the scheduler’s most important functions. We then use a set of transformation rules to generate the formal specifications of the scheduler in Promela. The generated Promela model enables simulation and verification of the scheduler in the SPIN model checker, which makes the proposed model a valuable artifact for researchers, educators and developers of Contiki. We also report on some design flaws we discovered during model extraction, simulation and verification. The contributions of this paper can readily be extended to other lightweight event-driven operating systems for Cyber Physical Systems (CPS) and IoT.

In this paper, we evaluate the effectiveness of model slicing to provide assurance about correctness of SystemC TLM programs. The need for such assurance is important since SystemC has become a de-facto standard for building systems with hardware/software co-design. Existing approaches that enable one to transform the given SystemC TLM program into an UPPAAL model that can be verified suffer from models that result in state space explosion. This problem becomes even more complex when verifying fault-tolerance. Model slicing has the potential to provide a solution to this problem. Therefore, we focus on developing a model slicer that extends existing work on model slicing and combines it with tools to generate UPPAAL models from SystemC TLM programs and tools to add the impact of faults to those UP-PAAL models. The experimental results show that with the proposed framework, the designer is capable of verifying even very complex SystemC TLM models, which would have been impossible without the proposed approach.

In this paper, we present a software framework for adding fault-tolerance to existing finite-state programs. The input to our framework is a fault-intolerant program and a class of faults that perturbs the program. The output of our framework is a fault-tolerant version of the input program. Our framework provides (1) the first automated tool for the synthesis of fault-tolerant distributed programs, and (2) an extensible platform for researchers to develop a repository of heuristics that deal with the complexity of adding fault-tolerance to distributed programs. We also present a set of heuristics for polynomial-time addition of fault-tolerance to distributed programs. We have used this framework for automated synthesis of several fault-tolerant programs including a simplified version of an aircraft altitude switch, token ring, Byzantine agreement, and agreement in the presence of Byzantine and fail-stop faults. These examples illustrate that our framework can be used for synthesizing programs that tolerate different types of faults (process restarts, Byzantine and fail-stop) and programs that are subject to multiple faults (Byzantine and fail-stop) simultaneously. We have found our framework to be highly useful for pedagogical purposes, especially for teaching concepts of fault-tolerance, automatic program transformation, and the effect of heuristics.

International audience; We propose the notion of tamper-evident stabilization –that combines stabilization with the concept of tamper evidence– for computing systems. On the first glance, these notions are contradictory; stabilization requires that eventually the system functionality is fully restored whereas tamper evidence requires that the system functionality is permanently degraded in the event of tampering. Tamper-evident stabilization captures the intuition that the system will tolerate perturbation upto a limit. In the event that it is perturbed beyond that limit, it will exhibit permanent evidence of tampering, where it may provide reduced (possibly none) functionality. We compare tamper-evident stabilization with (conventional) stabilization and with active stabilization and propose an approach to verify tamper-evident stabilizing programs in polynomial time. We demonstrate tamper-evident stabilization with two examples and argue how approaches for designing stabilization can be used to design tamper-evident stabilization. We also study issues of composition in tamper-evident stabilization. Finally, we point out how tamper-evident stabilization can effectively be used to provide tradeoff between fault-prevention and fault tolerance.

We present the tool UFIT (Uppaal Fault Injector for Timed automata). In UFIT, we model five types of faults, namely, message loss, transient, byzantine, stuck-at, and fail-stop faults. Given the fault-free timed automata model and the selection of a type of fault, UFIT models the faults and generates the fault-affected timed automata model automatically. As a result, the designer can analyze the behavior of the model in the presence of faults. Moreover, there are several tools that extract timed automata models from higher-level programs. Hence, the designer can use UFIT to inject the faults into the extracted models.

Since SoC systems are typically used for critical scenarios, it is desirable to analyze the impact of faults on them. However, fault-impact analysis is difficult due to the high integrity of SoC systems and different levels of abstraction provided by modern system design languages such as SystemC. In this paper, we present a method for modeling and analyzing permanent faults in SystemC TLM programs. The proposed method includes three steps, namely timed model extraction, fault modeling, and fault analysis. We use UPPAAL timed automata to formally model the SystemC TLM programs and monitor how the models behave in the presence of faults. A case study is also provided to better explain our proposed approach.

Since System on Chip (SoC) systems, where integrates all components of a computer or other electronic system into a single chip, are typically used for critical scenarios, it is desirable to analyze the impact of faults on them. However, fault-impact analysis is difficult at the RTL level due to the high integrity of SoC systems and different levels of abstraction provided by modern system design languages such as SystemC. Thus, modeling faults and impact analysis at different levels of abstraction is an important task and introduces dependability-related issues from the early phases of design. In this paper, we present a method for modeling and analyzing faults in SystemC TLM programs. The proposed method includes three steps, namely timed model extraction, fault modeling and fault analysis. We use UPPAAL timed automata to formally model the SystemC TLM programs and monitor how the models behave in the presence of faults. We analyze three case studies, two with Loosely-Timed coding style, and the other with Approximately-Timed coding style.

Since SoC (System on Chip) and NoC (Network on Chip) systems are getting more complex everyday, they are subject to different types of faults including timing faults. Timing has a significant importance in NoC systems. However, their fault-affected models are not studied extensively. In this paper, we present a method for modeling and analyzing timing faults in SystemC Transaction Level Modeling (TLM) programs. The proposed method includes three steps, namely timed model extraction, fault modeling and timed model checking. We use UPPAAL timed automata to formally model the SystemC TLM programs and monitor how the models behave in the presence of timing faults. We analyze our method using a case study. This case study utilizes loosely-timed coding style, which has a loose dependency between timing and data.

Due to their increasing complexity, today's SoC (System on Chip) systems are subject to a variety of faults (e.g., soft errors, component crash, etc.), thereby making fault tolerance a highly important property of such systems. However, designing fault tolerance is a complex task in part due to the large scale of integration of SoC systems and different levels of abstraction provided by modern system design languages such as SystemC. Most existing methods enable fault injection and impact analysis as a means for increasing design dependability. Nonetheless, such methods provide little support for designing fault tolerance. To facilitate the design of fault tolerance in SoC systems, this paper propose an approach where fault tolerance is designed at the level of inter-component communication protocols in SystemC Transaction Level (TL) models. The proposed method includes four main steps, namely model extraction, fault modeling, addition of fault tolerance and refinement of synthesized fault tolerance to SystemC code. We demonstrate the proposed approach using a simple SystemC transaction level program that is subject to communication faults. We also provide a roadmap for future research at the intersection of fault tolerance and hardware-software co-design.

The behavioral correctness of parallel programs has a pivotal role in computational sciences and engineering applications as researchers draw scientific conclusions from the results generated by parallel applications. Moreover, with the advent of multicore processors, the development of parallel programs should be facilitated for the mainstream developers. While numerous programming models and APIs exist for parallel programming, we pose the view that more emphasis should be placed on designing the synchronization mechanisms of parallel programs independent from the design of their functional behaviors. More importantly, programs behaviors evolve (due to new requirements and change of configuration), thereby creating a need for techniques and tools that enable developers to reason about the behavioral evolution of parallel programs. With such motivations, we introduce a framework for automated design/evolution of the synchronization mechanisms of parallel programs.

In order to facilitate incremental modeling and analysis of fault-tolerant embedded systems, we introduce an object analysis pattern, called the detector pattern, that provides a reusable strategy for capturing the requirements of failsafe fault-tolerance in an existing conceptual model, where a failsafe system satisfies its safety requirements even when faults occur. We also present a method that (i) uses the detector pattern to help create a behavioral model of a failsafe fault-tolerant system in UML, (ii) generates and model checks formal models of UML state diagrams of the fault-tolerant system, and (Hi) visualizes the model checking results in terms of the UML diagrams to facilitate model refinement. We demonstrate our analysis method in the context of an industrial automotive application.

Several approaches exist for modeling recovery of fault-tolerant systems during the requirements analysis phase. Most of these approaches are based on design techniques for recovery. Such design-based analysis methods unnecessarily constrain an analyst when specifying recovery requirements. To remedy such restrictions, we present an object analysis pattern, called the corrector pattern, that provides a generic reusable strategy for modeling error recovery requirements for embedded systems. In addition to templates for constructing structural and behavioral models of recovery requirements, the corrector pattern also contains templates for specifying properties that can be formally verified to ensure the consistency between recovery and functional requirements. Additional property templates can be instantiated and verified to ensure the fault-tolerance of the system to which the corrector pattern has been applied. We validate our analysis method in terms of UML diagrams, where we (1) use the corrector pattern to model recovery in UML behavioral models, (2) generate and model check formal models of the resulting UML models, and (3) visualize the model checking results in terms of the UML diagrams to facilitate model refinement. We demonstrate our analysis method in the context of an industrial automotive application.

Fault-tolerance is a crucial property in many systems. Thus, mechanical verification of algorithms associated with synthesis of faulttolerant programs is desirable to ensure their correctness. In this paper, we present the mechanized verification of algorithms that automate the addition of fault-tolerance to a given fault-intolerant program using the PVS theorem prover. By this verification, not only we prove the correctness of the synthesis algorithms, but also we guarantee that any program synthesized by these algorithms is correct by construction. Towards this end, we formally define a uniform framework for formal specification and verification of fault-tolerance that consists of abstract definitions for programs, specifications, faults, and levels of fault-tolerance, so that they are independent of platform and architecture. The essence of synthesis algorithms involves fixpoint calculations. Hence, we also develop a reusable library for fixpoint calculations on finite sets in PVS.

In this paper we focus on automated techniques to enhance the fault-tolerance of a nonmasking fault-tolerant program to masking. A masking program continually satisfies its specification even if faults occur. By contrast, a nonmasking program merely guarantees that after faults stop occurring, the program recovers to states from where it continually satisfies its specification. Until the recovery is complete, however a nonmasking program can violate its (safety) specification. Thus, the problem of enhancing fault-tolerance from nonmasking to masking requires that safety be added and recovery be preserved. We focus on this enhancement problem for high atomicity programs-where each process can read all variables-and for distributed programs-where restrictions are imposed on what processes can read and write. We present a sound and complete algorithm for high atomicity programs and a sound algorithm for distributed programs. We also argue that our algorithms are simpler than previous algorithms, where masking fault-tolerance is added to a fault-intolerant program. Hence, these algorithms can partially reap the benefits of automation when the cost of adding masking fault-tolerance to a fault-intolerant program is high. To illustrate these algorithms, we show how the masking fault-tolerant programs for triple modular redundancy and Byzantine agreement can be obtained by enhancing the fault-tolerance of the corresponding nonmasking versions. We also discuss how the derivation of these programs is simplified when we begin with a nonmasking fault-tolerant program.

In this paper, we focus our attention on the problem of automating the addition of failsafe fault-tolerance where fault-tolerance is added to an existing (fault-intolerant) program. A failsafe fault-tolerant program satisfies its specification (including safety and liveness) in the absence of faults. And, in the presence of faults, it satisfies its safety specification. We present a somewhat unexpected result that, in general, the problem of adding failsafe fault-tolerance in distributed programs is NP-hard. Towards this end, we reduce the 3-SAT problem to the problem of adding failsafe fault-tolerance. We also identify a class of specifications, monotonic specifications and a class of programs, monotonic programs. Given a (positive) monotonic specification and a (negative) monotonic program, we show that failsafe fault-tolerance can be added in polynomial time. We note that the monotonicity restrictions are met for commonly encountered problems such as Byzantine agreement, distributed consensus, and atomic commitment. Finally, we argue that the restrictions on the specifications and programs are necessary to add failsafe fault-tolerance in polynomial time; we prove that if only one of these conditions is satisfied, the addition of failsafe fault-tolerance is still NP-hard.