Specification techniques for Markov reward models

Markov reward models (MRMs) are commonly used for the performance, dependability, and performability analysis of computer and communication systems. Many papers have addressed solution techniques for MRMs. Far less attention has been paid to the specification of MRMs and the subsequent derivation of the underlying MRM. In this paper we only briefly address the mathematical aspects of MRMs. Instead, emphasis is put on specification techniques. In an application independent way, we distinguish seven classes of specification techniques: stochastic Petri nets, queuing networks, fault trees, production rule systems, communicating processes, specialized languages, and hybrid techniques. For these seven classes, we discuss the main principles, give examples and discuss software tools that support the use of these techniques. An overview like this has not been presented in the literature before. Finally, the paper addresses the generation of the underlying MRM from the high-level specification, and indicates important future research areas. This work was supported in part by the Naval Surface Warfare Center under contract N60921-92-C-0161 and by the National Science Foundation under grant CCR-9108114.     

A dependability profile within MARTE

The importance of assessing software non-functional properties (NFP) beside the functional ones is well accepted in the software engineering community. In particular, dependability is a NFP that should be assessed early in the software life-cycle by evaluating the system behaviour under different fault assumptions. Dependability-specific modeling and analysis techniques include for example Failure Mode and Effect Analysis for qualitative evaluation, stochastic Petri nets for quantitative evaluation, and fault trees for both forms of evaluation. Unified Modeling Language (UML) may be specialized for different domains by using the profile mechanism. For example, the MARTE profile extends UML with concepts for modeling and quantitative analysis of real-time and embedded systems (more specifically, for schedulability and performance analysis). This paper proposes to add to MARTE a profile for dependability analysis and modeling (DAM). A case study of an intrusion-tolerant message service will offer insight on how the MARTE-DAM profile can be used to derive a stochastic Petri net model for performance and dependability assessment.     

Qualitative temporal analysis: Towards a full implementation of the Fault Tree Handbook

The Fault Tree Handbook has become the de facto standard for fault tree analysis (FTA), defining the notation and mathematical foundation of this widely used safety analysis technique. The Handbook recognises that classical combinatorial fault trees employing only Boolean gates cannot capture the potentially critical significance of the temporal ordering of failure events in a system. Although the Handbook proposes two dynamic gates that could remedy this, a Priority-AND and an Exclusive-OR gate, these gates were never accurately defined. This paper proposes extensions to the logical foundation of fault trees that enable use of these dynamic gates in an extended and more powerful FTA. The benefits of this approach are demonstrated on a generic triple-module standby redundant system exhibiting dynamic behaviour.     

Fault tree analysis: A survey of the state-of-the-art in modeling,analysis and tools

Fault tree analysis (FTA) is a very prominent method to analyze the risks related to safety and economically critical assets, like power plants, airplanes, data centers and web shops. FTA methods comprise of a wide variety of modeling and analysis techniques, supported by a wide range of software tools. This paper surveys over 150 papers on fault tree analysis, providing an in-depth overview of the state-of-the-art in FTA. Concretely, we review standard fault trees, as well as extensions such as dynamic FT, repairable FT, and extended FT. For these models, we review both qualitative analysis methods, like cut sets and common cause failures, and quantitative techniques, including a wide variety of stochastic methods to compute failure probabilities. Numerous examples illustrate the various approaches, and tables present a quick overview of results.     

An approach to optimization of fault tolerant architectures using HiP‐HOPS

New processes for the design of dependable systems must address both cost and dependability concerns. They should also maximize the potential for automation to address the problem of increasing technological complexity and the potentially immense design spaces that need to be explored. In this paper we show a design process that integrates system modelling, automated dependability analysis and evolutionary optimization techniques to achieve the optimization of designs with respect to dependability and cost from the early stages. Computerized support is provided for difficult aspects of fault tolerant design, such as decision making on the type and location of fault detection and fault tolerant strategies. The process is supported by HiP‐HOPS, a scalable automated dependability analysis and optimization tool. The process was applied to a Pre‐collision system for vehicles at an early stage of its design. The study shows that HiP‐HOPS can overcome the limitations of earlier work based on Reliability Block Diagrams by enabling dependability analysis and optimization of architectures that may have a network topology and exhibit multiple failure modes. Copyright © 2011 John Wiley & Sons, Ltd.     

A dependability model for TMR system

Much research has been done on the dependability evaluation of computer systems. However, much of this is gone no further than study of the fault coverage of such systems, with little focus on the relationship between fault coverage and overall system dependability. In this paper, a Markovian dependability model for triple-modular-redundancy (TMR) system is presented. Having fully considered the effects of fault coverage, working time, and constant failure rate of single module on the dependability of the target TMR system, the model is built based on the stepwise degradation strategy. Through the model, the relationship between the fault coverage and the dependability of the system is determined. What is more, the dependability of the system can be dynamically and precisely predicted at any given time with the fault coverage set. This will be of much benefit for the dependability evaluation and improvement, and be helpful for the system design and maintenance.     

A synthesis of logic and bio-inspired techniques in the design of dependable systems

Much of the development of model-based design and dependability analysis in the design of dependable systems, including software intensive systems, can be attributed to the application of advances in formal logic and its application to fault forecasting and verification of systems. In parallel, work on bio-inspired technologies has shown potential for the evolutionary design of engineering systems via automated exploration of potentially large design spaces. We have not yet seen the emergence of a design paradigm that effectively combines these two techniques, schematically founded on the two pillars of formal logic and biology, from the early stages of, and throughout, the design lifecycle. Such a design paradigm would apply these techniques synergistically and systematically to enable optimal refinement of new designs which can be driven effectively by dependability requirements. The paper sketches such a model-centric paradigm for the design of dependable systems, presented in the scope of the HiP-HOPS tool and technique, that brings these technologies together to realise their combined potential benefits. The paper begins by identifying current challenges in model-based safety assessment and then overviews the use of meta-heuristics at various stages of the design lifecycle covering topics that span from allocation of dependability requirements, through dependability analysis, to multi-objective optimisation of system architectures and maintenance schedules.     

Analysis of non-Markovian repairable fault trees through rare event simulation

Dynamic fault trees (DFTs) are widely adopted in industry to assess the dependability of safety-critical equipment. Since many systems are too large to be studied numerically, DFTs dependability is often analysed using Monte Carlo simulation. A bottleneck here is that many simulation samples are required in the case of rare events, e.g. in highly reliable systems where components seldom fail. Rare event simulation (RES) provides techniques to reduce the number of samples in the case of rare events. In this article, we present a RES technique based on importance splitting to study failures in highly reliable DFTs, more precisely, on a variant of repairable fault trees (RFT). Whereas RES usually requires meta-information from an expert, our method is fully automatic. For this, we propose two different methods to derive the so-called importance function. On the one hand, we propose to cleverly exploit the RFT structure to compositionally construct such function. On the other hand, we explore different importance functions derived in different ways from the minimal cut sets of the tree, i.e., the minimal units that determine its failure. We handle RFTs with Markovian and non-Markovian failure and repair distributions—for which no numerical methods exist—and implement the techniques on a toolchain that includes the RES engine FIG, for which we also present improvements. We finally show the efficiency of our approach in several case studies.

     

From safety analysis to software requirements

Software for safety critical systems must deal with the hazards identified by safety analysis. This paper investigates, how the results of one safety analysis technique, fault trees, are interpreted as software safety requirements to be used in the program design process. We propose that fault tree analysis and program development use the same system model. This model is formalized in a real-time, interval logic, based on a conventional dynamic systems model with state evolving over time. Fault trees are interpreted as temporal formulas, and it is shown how such formulas can be used for deriving safety requirements for software components     

Rare event simulation for highly dependable systems with fast repairs

Probabilistic model checking has been used recently to assess, among others, dependability measures for a variety of systems. However, the numerical methods employed, such as those supported by model checking tools such as PRISM and MRMC, suffer from the state-space explosion problem. The main alternative is statistical model checking, which uses standard Monte Carlo simulation, but this performs poorly when small probabilities need to be estimated. Therefore, we propose a method based on importance sampling to speed up the simulation process in cases where the failure probabilities are small due to the high speed of the system’s repair units. This setting arises naturally in Markovian models of highly dependable systems. We show that our method compares favourably to standard simulation, to existing importance sampling techniques, and to the numerical techniques of PRISM.     

Jgroup/ARM: a distributed object group platform with autonomous replication management

This paper presents the design and implementation of Jgroup/ARM, a distributed object group platform with autonomous replication management along with a novel measurement‐based assessment technique that is used to validate the fault‐handling capability of Jgroup/ARM. Jgroup extends Java RMI through the group communication paradigm and has been designed specifically for application support in partitionable systems. ARM aims at improving the dependability characteristics of systems through a fault‐treatment mechanism. Hence, ARM focuses on deployment and operational aspects, where the gain in terms of improved dependability is likely to be the greatest. The main objective of ARM is to localize failures and to reconfigure the system according to application‐specific dependability requirements. Combining Jgroup and ARM can significantly reduce the effort necessary for developing, deploying and managing dependable, partition‐aware applications. Jgroup/ARM is evaluated experimentally to validate its fault‐handling capability; the recovery performance of a system deployed in a wide area network is evaluated. In this experiment multiple nearly coincident reachability changes are injected to emulate network partitions separating the service replicas. The results show that Jgroup/ARM is able to recover applications to their initial state in several realistic failure scenarios, including multiple, concurrent network partitionings. Copyright © 2007 John Wiley & Sons, Ltd.     

A global-state-triggered fault injector for distributed system evaluation

Validation of the dependability of distributed systems via fault injection is gaining importance because distributed systems are being increasingly used in environments with high dependability requirements. The fact that distributed systems can fail in subtle ways that depend on the state of multiple parts of the system suggests that a global-state-based fault injection mechanism should be used to validate them. However, global-state-based fault injection is challenging since it is very difficult in practice to maintain the global state of a distributed system at runtime with minimal intrusion into the system execution. We present Loki, a global-state-based fault injector, which has been designed with the goals of low intrusion, high precision, and high flexibility. Loki achieves these goals by utilizing the ideas of partial view of global state, optimistic synchronization, and offline analysis. In Loki, faults are injected based on a partial, view of the global state of the system, and a post-runtime analysis is performed to place events and injections into a single global timeline and to discard experiments with incorrect fault injections. Finally, the experiments with correct fault injections are used to estimate user-specified performance and dependability measures. A flexible measure language has been designed that facilitates the specification of a wide range of measures.     

A theory of independent fuzzy probability for system reliability

Fuzzy fault trees provide a powerful and computationally efficient technique for developing fuzzy probabilities based on independent inputs. The probability of any event that can be described in terms of a sequence of independent unions, intersections, and complements may be calculated by a fuzzy fault tree. Unfortunately, fuzzy fault trees do not provide a complete theory: many events of substantial practical interest cannot be described only by independent operations. Thus, the standard fuzzy extension (based on fuzzy fault trees) is not complete since not all events are assigned a fuzzy probability. Other complete extensions have been proposed, but these extensions are not consistent with the calculations from fuzzy fault trees. We propose a new extension of crisp probability theory. Our model is based on n independent inputs, each with a fuzzy probability. The elements of our sample space describe exactly which of the n input events did and did not occur. Our extension is complete since a fuzzy probability is assigned to every subset of the sample space. Our extension is also consistent with all calculations that can be arranged as a fault tree. Our approach allows the reliability analyst to develop complete and consistent fuzzy reliability models from existing crisp reliability models. This allows a comprehensive analysis of the system. Computational algorithms are provided both to extend existing models and develop new models. The technique is demonstrated on a reliability model of a three-stage industrial process     

An integrated domain analysis approach for teleoperated systems

Teleoperated systems for ship hull maintenance (TOS) are robotic systems for ship maintenance tasks, such as cleaning or painting a ship’s hull. The product line paradigm has recently been applied to TOS, and a TOS reference architecture has thus been designed. However, TOS requirements specifications have not been developed in any rigorous way with reuse in mind. We therefore believe that an opportunity exists to increase the abstraction level at which stakeholders can reason about this product line. This paper reports an experience in which this TOS domain was analyzed, including the lessons learned in the construction and use of the TOS domain model. The experience is based on the application of extensions of well-known domain analysis techniques, together with the use of quality attribute templates traced to a feature model to deal with non-functional issues. A qualitative research method (action research) was used to carry out the experience.     

关于事件注入用于网络可信性测评的几个关键指标

事件注入是源于故障注入原理,可以用于对计算机网络可信性进行测评研究。本文分析了事件注入技术在可信性测评中的应用问题,对事件注入的几个关键指标进行了相应的分析,并探讨了事件注入技术不足之处和改进方向。     

The FSAP/NuSMV-SA Safety Analysis Platform

Safety-critical systems are becoming more complex, both in the type of functionality they provide and in the way they are demanded to interact with the environment. Such a growing complexity requires an adequate increase in the capability of safety engineers to assess system safety, including analyzing the behavior of a system in degraded situations. Formal verification techniques, like symbolic model checking, have the potential of dealing with such a complexity and are now being used more often. However, existing techniques have little tool support and therefore their use for safety analysis remains limited. In this paper, we present FSAP/NuSMV-SA, a platform which aims to improve the development cycle of complex systems by providing a uniform environment that can be used both at design time and for safety assessment. The platform makes the modeling and safety assessment of complex systems easier by providing a facility for automatically augmenting a system model with failure modes, whose definitions are retrieved from a predefined library. In this way, it is possible to assess the system safety both in nominal conditions and in user-specified degraded situations, i.e., in the presence of faults. Furthermore, the platform provides a pattern-based definition of temporal logic formulas, which simplifies the definition of safety requirements. The platform consists of a graphical user interface (FSAP) and an engine (NuSMV-SA) which is based on the NuSMV model checker. The model checking engine provides a support for system simulation and standard model checking capabilities, like property verification and the generation of counterexamples. Furthermore, algorithms have been implemented to automate the generation of artifacts that are typical of reliability analysis, e.g., fault trees. The platform can derive fault trees automatically (for both monotonic and non-monotonic systems) from the definition of the system model and of the possible faults. The interface of the platform has been designed to improve usability for people who are not expert in formal verification. The platform has been evaluated in collaboration with an industrial partner and tested on some industrial case studies. This work has been developed within the European-sponsored projects ESACS, contract no. G4RD-CT-2000-00361, and ISAAC, contract no. AST3-CT-2003-501848.     

A modelling and simulation based process for dependable systems design

Complex real-time system design needs to address dependability requirements, such as safety, reliability, and security. We introduce a modelling and simulation based approach which allows for the analysis and prediction of dependability constraints. Dependability can be improved by making use of fault tolerance techniques. The de-facto example, in the real-time system literature, of a pump control system in a mining environment is used to demonstrate our model-based approach. In particular, the system is modelled using the Discrete EVent system Specification (DEVS) formalism, and then extended to incorporate fault tolerance mechanisms. The modularity of the DEVS formalism facilitates this extension. The simulation demonstrates that the employed fault tolerance techniques are effective. That is, the system performs satisfactorily despite the presence of faults. This approach also makes it possible to make an informed choice between different fault tolerance techniques. Performance metrics are used to measure the reliability and safety of the system, and to evaluate the dependability achieved by the design. In our model-based development process, modelling, simulation and eventual deployment of the system are seamlessly integrated.     

Interactive fault localization techniques in a spreadsheet environment

End-user programmers develop more software than any other group of programmers, using software authoring devices such as multimedia simulation builders, e-mail filtering editors, by-demonstration macro builders, and spreadsheet environments. Despite this, there has been only a little research on finding ways to help these programmers with the dependability of the software they create. We have been working to address this problem in several ways, one of which includes supporting end-user debugging activities through interactive fault localization techniques. This paper investigates fault localization techniques in the spreadsheet domain, the most common type of end-user programming environment. We investigate a technique previously described in the research literature and two new techniques. We present the results of an empirical study to examine the impact of two individual factors on the effectiveness of fault localization techniques. Our results reveal several insights into the contributions such techniques can make to the end-user debugging process and highlight key issues of interest to researchers and practitioners who may design and evaluate future fault localization techniques.