Failure correlation in software reliability models

Perhaps the most stringent restriction in most software reliability models is the assumption of statistical independence among successive software failures. The authors research was motivated by the fact that although there are practical situations in which this assumption could be easily violated, much of the published literature on software reliability modeling does not seriously address this issue. The research work in this paper is devoted to developing the software reliability modeling framework that can consider the phenomena of failure correlation and to study its effects on the software reliability measures. The important property of the developed Markov renewal modeling approach is its flexibility. It allows construction of the software reliability model in both discrete time and continuous time, and (depending on the goals) to base the analysis either on Markov chain theory or on renewal process theory. Thus, their modeling approach is an important step toward more consistent and realistic modeling of software reliability. It can be related to existing software reliability growth models. Many input-domain and time-domain models can be derived as special cases under the assumption of failure s-independence. This paper aims at showing that the classical software reliability theory can be extended to consider a sequence of possibly s-dependent software runs, viz, failure correlation. It does not deal with inference nor with predictions, per se. For the model to be fully specified and applied to estimations and predictions in real software development projects, we need to address many research issues, e.g., the detailed assumptions about the nature of the overall reliability growth, way modeling-parameters change as a result of the fault-removal attempts     

Reliability for Sparsely Connected Consecutive-k Systems

We introduce the system of consecutive failures with sparse d which is a natural extension of consecutive-k systems. Then a series of generalizations of consecutive-k systems are discussed, such as consecutive-k-out-n:F systems with sparse d, M consecutive-k-out-of-n:F systems with sparse d, and (n, f, k) :F systems with sparse d. We present the formulation for the system reliability of these generalized consecutive-k systems with various component settings in terms of the finite Markov chain imbedding idea, along with two numerical examples.     

基于Object-Z与Markov链的校园卡系统测试用例

针对提高校园卡系统准确性和可靠性测试的要求,提出了Object-Z与Markov链结合的测试用例自动生成算法.使用Object-Z对系统进行形式化规约,生成测试场景和操作顺序图;将操作顺序图转换为Markov链使用模型;根据测试场景和Markov链使用模型生成数量相对合理的测试用例.该方法无需对系统进行运行,在需求分析与测试阶段就能对系统的功能进行测试.生成的校园卡系统测试用例证明该方法是有效的,并且在提高测试覆盖率的同时,使用Markov链也能保证对系统的可靠性测试.     

The number of working periods of a repairable Markov system duringa finite time interval

In reliability analysis, continuous parameter homogeneous irreducible finite Markov processes are used to model repairable systems with time-independent transition rates between individual states. The state space is then partitioned into the set of up states and the set of down states. The number of completed repair events during a finite time interval is an important (undiscounted) cost measure for such a system; it can be expressed in terms of the number of working periods during the same time interval. This paper derives a closed-form expression for the PMF of this latter quantity. The tool used is a recent result on the joint distribution of sojourn times in finite Markov processes. The MatLab implementation of the Markov model of a 2-unit parallel power transmission system is used to demonstrate the utility of the formula. The quantity examined is the number of completed repairs during a finite time interval. The method is viable in this case whereas the more usual randomization technique is not     

Reliability analysis of interconnection networks using hierarchicalcomposition

Based on the nature of the upper- and lower-bound block diagram models of multistage interconnection networks (MINs), a series system consisting of independent subsystems is considered. To model the reliability of such a system with online repair and imperfect coverage, the usual approach is to construct and solve a large, overall Markov model. A two-level hierarchical model is instead proposed in which each subsystem is modeled as a Markov chain and the system reliability is then modeled as a series system of independent Markov components. This technique is extended to compute the instantaneous availability of the system with imperfect coverage and online repair. Extensions to allow for transient faults and phase-type repair time distributions are straightforward. It should be possible to apply this approach to other fault-tolerant MINs and to any system that can be modeled as a series system where each subsystem has a parallel-redundant structure     

Modular solution of dynamic multi-phase systems

Binary Decision Diagram (BDD)-based solution approaches and Markov chain based approaches are commonly used for the reliability analysis of multi-phase systems. These approaches either assume that every phase is static, and thus can be solved with combinatorial methods, or assume that every phase must be modeled via Markov methods. If every phase is indeed static, then the combinatorial approach is much more efficient than the Markov chain approach. But in a multi-phased system, using currently available techniques, if the failure criteria in even one phase is dynamic, then a Markov approach must be used for every phase. The problem with Markov chain based approaches is that the size of the Markov model can expand exponentially with an increase in the size of the system, and therefore becomes computationally intensive to solve. Two new concepts, phase module and module joint probability, are introduced in this paper to deal with the s-dependency among phases. We also present a new modular solution to nonrepairable dynamic multi-phase systems, which provides a combination of BDD solution techniques for static modules, and Markov chain solution techniques for dynamic modules. Our modular approach divides the multi-phase system into its static and dynamic subsystems, and solves them independently; and then combines the results for the solution of the entire system using the module joint probability method. A hypothetical example multi-phase system is given to demonstrate the modular approach.     

System reliability analysis of an N-version programming application

This paper presents a quantitative reliability analysis of a system designed to tolerate both hardware and software faults. The system achieves integrated fault tolerance by implementing N-version programming (NVP) on redundant hardware. The system analysis considers unrelated software faults, related software faults, transient hardware faults, permanent hardware faults, and imperfect coverage. The overall model is Markov in which the states of the Markov chain represent the long-term evolution of the system-structure. For each operational configuration, a fault-tree model captures the effects of software faults and transient hardware faults on the task computation. The software fault model is parameterized using experimental data associated with a recent implementation of an NVP system using the current design paradigm. The hardware model is parameterized by considering typical failure rates associated with hardware faults and coverage parameters. The authors results show that it is important to consider both hardware and software faults in the reliability analysis of an NVP system, since these estimates vary with time. Moreover, the function for error detection and recovery is extremely important to fault-tolerant software. Several orders of magnitude reduction in system unreliability can be observed if this function is provided promptly     

Approximate sensitivity analysis for acyclic Markov reliability models

Acyclic Markov chains are frequently used for reliability analysis of nonmaintained mission-critical computer-based systems. Since traditional sensitivity (or importance) analysis using Markov chains can be computationally expensive, an approximate approach is presented which is easy to compute and which performs quite well in test cases. This approach is presented in terms of a Markov chain which is used for solving a dynamic fault-tree, but the approach applies to any acyclic Markov reliability model.     

Splitting-based importance-sampling algorithm for fast simulationof Markov reliability models with general repair-policies

Markov chains with small transition probabilities occur while modeling the reliability of systems where the individual components are highly reliable and quickly repairable. Complex inter-component dependencies can exist and the state space involved can be huge, making these models analytically and numerically intractable. Naive simulation is also difficult because the event of interest (system failure) is rare, so that a prohibitively large amount of computation is needed to obtain samples of these events. An earlier paper (Juneja et al., 2001) proposed an importance sampling scheme that provides large efficiency increases over naive simulation for a very general class of models including reliability models with general repair policies such as deferred and group repairs. However, there is a statistical penalty associated with this scheme when the corresponding Markov chain has high probability cycles as may be the case with reliability models with general repair policies. This paper develops a splitting-based importance-sampling technique that avoids this statistical penalty by splitting paths at high probability cycles and thus achieves bounded relative-error in a stronger sense than in previous attempts     

Reliability Modeling Using SHARPE

Combinatorial models such as fault trees and reliability block diagrams are efficient for model specification and often efficient in their evaluation. But it is difficult, if not impossible, to allow for dependencies (such as repair dependency and near-coincident-fault type dependency), transient and intermittent faults, standby systems with warm spares, and so on. Markov models can capture such important system behavior, but the size of a Markov model can grow exponentially with the number of components in this system. This paper presents an approach for avoiding the large state space problem. The approach uses a hierarchical modeling technique for analyzing complex reliability models. It allows the flexibility of Markov models where necessary and retains the efficiency of combinatorial solution where possible. Based on this approach a computer program called SHARPE (Symbolic Hierarchical Automated Reliability and Performance Evaluator) has been written. The hierarchical modeling technique provides a very flexible mechanism for using decomposition and aggregation to model large systems; it allows for both combinatorial and Markov or semi-Markov submodels, and can analyze each model to produce a distribution function. The choice of the number of levels of models and the model types at each level is left up to the modeler. Component distribution functions can be any exponential polynomial whose range is between zero and one. Examples show how combinations of models can be used to evaluate the reliability and availability of large systems using SHARPE.     

Analytical Models for Architecture-Based Software Reliability Prediction: A Unification Framework

Traditional approaches to software reliability modeling are black box-based; that is, the software system is considered as a whole, and only its interactions with the outside world are modeled without looking into its internal structure. The black box approach is adequate to characterize the reliability of monolithic, custom, built-to-specification software applications. However, with the widespread use of object oriented systems design & development, the use of component-based software development is on the rise. Software systems are developed in a heterogeneous (multiple teams in different environments) fashion, and hence it may be inappropriate to model the overall failure process of such systems using one of the several software reliability growth models (black box approach). Predicting the reliability of a software system based on its architecture, and the failure behavior of its components, is thus essential. Most of the research efforts in predicting the reliability of a software system based on its architecture have been focused on developing analytical or state-based models. However, the development of state-based models has been mostly ad hoc with little or no effort devoted towards establishing a unifying framework which compares & contrasts these models. Also, to the best of our knowledge, no attempt has been made to offer an insight into how these models might be applied to real software applications. This paper proposes a unifying framework for state-based models for architecture-based software reliability prediction. The state-based models we consider are the ones in which application architecture is represented either as a discrete time Markov chain (DTMC), or a continuous time Markov chain (CTMC). We illustrate the DTMC-based, and CTMC-based models using examples. A detailed discussion of how the parameters of each model may be estimated, and the life cycle phases when the model may be applied is also provided     

A Novel Algebraic Framework for Analyzing Finite Population DS/SS Slotted ALOHA Wireless Network Systems with Delay Capture

A new analytic framework based on a linear algebra approach is proposed for examining the performance of a direct sequence spread spectrum (DS/SS) slotted ALOHA wireless communication network systems with delay capture. The discrete-time Markov chain model has been introduced to account for the effect of randomized time of arrival (TOA) at the central receiver and determine the evolution of the finite population network performance in a single-hop environment. The proposed linear algebra approach applied to the given Markov problem requires only computing the eigenvector II of the state transition matrix and then normalizing it to have the sum of its entries equal to 1. MATLAB computation results show that systems employing discrete TOA randomization and delay capture significantly improves throughput-delay performance and the employed analysis approach is quite easily and staightforwardly applicable to the current analysis problem.     

Polling systems with server timeouts and their application to tokenpassing networks

Polling systems have long been the subject of study and are of particular interest in the analysis of high-speed communications networks. There are many options for the scheduling policies that can be used at each polling station (exhaustive, gated, customer limited, etc.). In addition, one can impose an upper bound on the total service time delivered to customers at a station per server visit. In the most common case the upper bound is a constant for each polling station, and the resulting system model is not Markovian even when service times and interarrival times are exponential. In the paper, a comprehensive solution is developed for the major scheduling policies with time limits for each polling station. The approach is based on studying the embedded Markov chain defined at the sequence of epochs when the server arrives at each polling station. The computation of transition probabilities for the embedded chain requires transient analysis of the Markov process describing the system evolution between epochs. Uniformization methods are used to develop efficient algorithms for the transition probabilities and for system performance measures. Example problems are solved using the techniques developed to illustrate the utility of the results     

Time-varying failure rates in the availability and reliabilityanalysis of repairable systems

This paper combines time varying failure rates and Markov chain analysis to obtain a hybrid reliability and availability analysis. However, combining these techniques can, depending on the size of the system, result in solutions of the Markov chain differential matrix equations that are intractable. This paper identifies solutions that are tractable, These form the analytical baseline for the reliability and availability analysis of systems with time varying failure rates. Tractable solutions were found for the 1-component 2-state and the 2-component 4-state configurations. Time varying failure rates were characterized by a general polynomial expression. Constant, linear, and Weibull failure rate functions are special cases of this polynomial. The general polynomial failure rate provides flexibility in modeling the time varying failure rates that occur in practice     

Numerical methods for reliability evaluation of Markov closedfault-tolerant systems

This paper compares three numerical methods for reliability calculation of Markov, closed, fault-tolerant systems which give rise to continuous-time, time-homogeneous, finite-state, acyclic Markov chains. The authors consider a modified version of Jensen's method (a probabilistic method, also known as uniformization or randomization), a new version of ACE (acyclic Markov chain evaluator) algorithm with several enhancements, and a third-order implicit Runge-Kutta method (an ordinary-differential-equation solution method). Modifications to Jensen's method include incorporating stable calculation of Poisson probabilities and steady-state detection of the underlying discrete-time Markov chain. The new version of Jensen's method is not only more efficient but yields more accurate results. Modifications to ACE algorithm are proposed which incorporate scaling and other refinements to make it more stable and accurate. However, the new version no longer yields solution symbolic with respect to time variable. Implicit Runge-Kutta method can exploit the acyclic structure of the Markov chain and therefore becomes more efficient. All three methods are implemented. Several reliability models are numerically solved using these methods and the results are compared on the basis of accuracy and computation cost     

Markov chain model for multimodal biometric rank fusion

Multimodal biometric aims at increasing reliability of biometric systems through utilizing more than one biometric in decision-making process. An effective fusion scheme is necessary for combining information from various sources. Such information can be integrated at several distinct levels, such as sensor level, feature level, match score level, rank level, and decision level. In this paper, we present a multimodal biometric system utilizing face, iris, and ear biometric features through rank level fusion method using novel Markov chain approach. We first apply fisherimage technique to face and ear image databases for recognition and Hough transform and Hamming distance techniques for iris image recognition. The main contribution is in introducing Markov chain approach for biometric rank aggregation. One of the distinctive features of this method is that it satisfies the Condorcet criterion, which is essential in any fair rank aggregation system. The experimentation shows superiority of the proposed approach to other recently introduced biometric rank aggregation methods. The developed system can be effectively used by security and intelligence services for controlling access to prohibited areas and protecting important national or public information.     

Reliability Bounds for Multi-State $k$-out-of- $n$ Systems

Algorithms have been available for exact performance evaluation of multi-state k-out-of-n systems. However, especially for complex systems with a large number of components, and a large number of possible states, obtaining "reliability bounds" would be an interesting, significant issue. Reliability bounds will give us a range of the system reliability in a much shorter computation time, which allow us to make decisions more efficiently. The systems under consideration are multi-state k-out-of-n systems with i.i.d. components. We will focus on the probability of the system in states below a certain state d, denoted by Q_sd. Based on the recursive algorithm proposed by Zuo & Tian [14] for performance evaluation of multi-state k-out-of-n systems with i.i.d. components, a reliability bounding approach is developed in this paper. The upper, and lower bounds of Q_sd are calculated by reducing the length of the k vector when using the recursive algorithm. Using the bounding approach, we can obtain a good estimate of the exact Q_sd value while significantly reducing the computation time. This approach is attractive, especially to complex systems with a large number of components, and a large number of possible states. A numerical example is used to illustrate the significance of the proposed bounding approach.