In recent years we have become interested in the problem of assessing the probability of perfection of software-based systems which are sufficiently simple that they are "possibly perfect". By "perfection" we mean that the software of interest will never fail in a specific operating environment. We can never be certain that it is perfect, so our interest lies in claims for its probability of perfection. Our approach is Bayesian: our aim is to model the changes to this probability of perfection as we see evidence of failure-free working. Much of the paper considers the difficult problem of expressing prior beliefs about the probability of failure on demand (pfd), and representing these mathematically. This requires the assessor to state his prior belief in perfection as a probability, and also to state what he believes are likely values of the pfd in the event that the system is not perfect. We take the view that it will be impractical for an assessor to express these beliefs as a complete distribution for pfd. Our approach to the problem has three threads. Firstly we assume that, although he cannot provide a full probabilistic description of his uncertainty in a single distribution, the assessor can express some precise but partial beliefs about the unknowns. Secondly, we assume that in the inevitable presence of such incompleteness, the Bayesian analysis needs to provide results that are guaranteed to be conservative (because the analyses we have in mind relate to critical systems). Finally, we seek to prune the set of prior distributions that the assessor finds acceptable in order that the conservatism of the results is no greater than it has to be, i.e. we propose, and eliminate, sets of priors that would appear generally unreasonable. We give some illustrative numerical examples of this approach, and note that the numerical values obtained for the posterior probability of perfection in this way seem potentially useful (although we make no claims for the practical realism of the numbers we use). We also note that the general approach here to the problem of expressing and using limited prior belief in a Bayesian analysis may have wider applicability than to the problem we have addressed.

In earlier work, [11] (henceforth LR), an analysis was presented of a 1-out-of-2 software-based system in which one channel was “possibly perfect”. It was shown that, at the aleatory level, the system pfd (probability of failure on demand) could be bounded above by the product of the pfd of channel A and the pnp (probability of nonperfection) of channel B. This result was presented as a way of avoiding the well-known difficulty that for two certainly-fallible channels, failures of the two will be dependent, i.e., the system pfd cannot be expressed simply as a product of the channel pfds. A price paid in this new approach for avoiding the issue of failure dependence is that the result is conservative. Furthermore, a complete analysis requires that account be taken of epistemic uncertainty-here concerning the numeric values of the two parameters pfdAand pnpB. Unfortunately this introduces a different difficult problem of dependence: estimating the dependence between an assessor's beliefs about the parameters. The work reported here avoids this problem by obtaining results that require only an assessor's marginal beliefs about the individual channels, i.e., they do not require knowledge of the dependence between these beliefs. The price paid is further conservatism in the results.

We consider the problem of assessing the reliability of a 1-out-of-2 software-based system, in which failures of the two channels cannot be assumed to be independent with certainty. An informal approach to this problem assesses the channel probabilities of failure on demand (pfds) conservatively, and then multiplies these together in the hope that the conservatism will be sufficient to overcome any possible dependence between the channel failures. Our intention here is to place this kind of reasoning on a formal footing. We introduce a notion of "not worse than independence"' and assume that an assessor has a prior belief about this, expressed as a probability. We obtain a conservative prior system pfd, and show how a conservative posterior system pfd can be obtained following the observation of a number of demands without system failure. We present some illustrative numerical examples, discuss some of the difficulties involved in this way of reasoning, and suggest some avenues of future research.

This paper refines and extends an earlier one by the first author [1]. It considers the problem of reasoning about the reliability of fault-tolerant systems with two “channels” (i.e., components) of which one, A, because it is conventionally engineered and presumed to contain faults, supports only a claim of reliability, while the other, B, by virtue of extreme simplicity and extensive analysis, supports a plausible claim of “perfection.” We begin with the case where either channel can bring the system to a safe state. The reasoning about system probability of failure on demand ({pfd}) is divided into two steps. The first concerns aleatory uncertainty about 1) whether channel A will fail on a randomly selected demand and 2) whether channel B is imperfect. It is shown that, conditional upon knowing p_A (the probability that A fails on a randomly selected demand) and p_B (the probability that channel B is imperfect), a conservative bound on the probability that the system fails on a randomly selected demand is simply p_A \times p_B. That is, there is conditional independence between the events “A fails” and “B is imperfect.” The second step of the reasoning involves epistemic uncertainty, represented by assessors' beliefs about the distribution of (p_A, p_B), and it is here that dependence may arise. However, we show that under quite plausible assumptions, a conservative bound on system {pfd} can be constructed from point estimates for just three parameters. We discuss the feasibility of establishing credible estimates for these parameters. We extend our analysis from faults of omission to those of commission, and then combine these to yield an analysis for monitored architectures of a kind proposed for aircraft.

In recent work, we have argued for a formal treatment of confidence about the claims made in dependability cases for software-based systems. The key idea underlying this work is "the inevitability of uncertainty": It is rarely possible to assert that a claim about safety or reliability is true with certainty. Much of this uncertainty is epistemic in nature, so it seems inevitable that expert judgment will continue to play an important role in dependability cases. Here, we consider a simple case where an expert makes a claim about the probability of failure on demand (pfd) of a subsystem of a wider system and is able to express his confidence about that claim probabilistically. An important, but difficult, problem then is how such subsystem (claim, confidence) pairs can be propagated through a dependability case for a wider system, of which the subsystems are components. An informal way forward is to justify, at high confidence, a strong claim, and then, conservatively, only claim something much weaker: "I'm 99 percent confident that the pfd is less than 10-5, so it's reasonable to be 100 percent confident that it is less than 10-3." These conservative pfds of subsystems can then be propagated simply through the dependability case of the wider system. In this paper, we provide formal support for such reasoning.

This paper is concerned with the development of reliable real-time systems for use in high integrity applications. It advocates the use of diverse replicated channels, but does not require the dependencies between the channels to be evaluated. Rather it develops and extends the approach of Little wood and Rush by (for general systems) by investigating a two channel system in which one channel, A, is produced to a high level of reliability (i.e. has a very low failure rate), while the other, B, employs various forms of static analysis to sustain an argument that it is perfect (i.e. it will never miss a deadline). The first channel is fully functional, the second contains a more restricted computational model and contains only the critical computations. Potential dependencies between the channels (and their verification) are evaluated in terms of aleatory and epistemic uncertainty. At the aleatory level the events ''A fails" and ''B is imperfect" are independent. Moreover, unlike the general case, independence at the epistemic level is also proposed for common forms of implementation and analysis for real-time systems and their temporal requirements (deadlines). As a result, a systematic approach is advocated that can be applied in a real engineering context to produce highly reliable real-time systems, and to support numerical claims about the level of reliability achieved.

Society is increasingly requiring quantitative assessment of risk and associated dependability cases. Informally, a dependability case comprises some reasoning, based on assumptions and evidence, that supports a dependability claim at a particular level of confidence. In this paper we argue that a quantitative assessment of claim confidence is necessary for proper assessment of risk. We discuss the way in which confidence depends upon uncertainty about the underpinnings of the dependability case (truth of assumptions, correctness of reasoning, strength of evidence), and propose that probability is the appropriate measure of uncertainty. We discuss some of the obstacles to quantitative assessment of confidence (issues of composability of subsystem claims; of the multi-dimensional, multi-attribute nature of dependability claims; of the difficult role played by dependence between different kinds of evidence, assumptions, etc). We show that, even in simple cases, the confidence in a claim arising from a dependability case can be surprisingly low.

Fault tolerance via design diversity is often the only viable way of achieving sufficient dependability levels when using off-the-shelf components. We have reported previously on studies with bug reports of four open-source and commercial off-the-shelf database servers and later release of two of them. The results were very promising for designers of fault-tolerant solutions that wish to employ diverse servers: very few bugs caused failures in more than one server and none caused failure in more than two. In this paper we offer details of two approaches we have studied to construct reliability growth models for a 1-out-of-2 fault-tolerant server which utilize the bug reports. The models presented are of practical significance to system designers wishing to employ diversity with off-the-shelf components since often the bug reports are the only direct dependability evidence available to them.

The work described here concerns the use of so-called multilegged arguments to support dependability claims about software-based systems. The informal justification for the use of multilegged arguments is similar to that used to support the use of multiversion software in pursuit of high reliability or safety. Just as a diverse 1-out-of-2 system might be expected to be more reliable than each of its two component versions, so might a two-legged argument be expected to give greater confidence in the correctness of a dependability claim (for example, a safety claim) than would either of the argument legs alone. Our intention here is to treat these argument structures formally, in particular, by presenting a formal probabilistic treatment of "confidence,? which will be used as a measure of efficacy. This will enable claims for the efficacy of the multilegged approach to be made quantitatively, answering questions such as, "How much extra confidence about a system's safety will I have if I add a verification argument leg to an argument leg based upon statistical testing?? For this initial study, we concentrate on a simplified and idealized example of a safety system in which interest centers upon a claim about the probability of failure on demand. Our approach is to build a "Bayesian Belief Network? (BBN) model of a two-legged argument and manipulate this analytically via parameters that define its node probability tables. The aim here is to obtain greater insight than what is afforded by the more usual BBN treatment, which involves merely numerical manipulation. We show that the addition of a diverse second argument leg can indeed increase confidence in a dependability claim; in a reasonably plausible example, the doubt in the claim is reduced to one-third of the doubt present in the original single leg. However, we also show that there can be some unexpected and counterintuitive subtleties here; for example, an entirely supportive second leg can sometimes undermine an original argument, resulting, overall, in less confidence than what came from this original argument. Our results are neutral on the issue of whether such difficulties will arise in real life?that is, when real experts judge real systems.

Elections are increasingly dependent on computers and telecommunication systems. Such "e-voting" schemes create socio-technical systems (combinations of technology and human organisations) that are complex and critical, as the future of nations depends on their proper operation. Thus heated debate surrounds their adoption and the possible methods for making them demonstrably dependable. We discuss the dependability requirements for such systems, and the design issues in ensuring their satisfaction, with reference to a recent proposal that uses cryptography for fault tolerance, in order to avoid some of the perceived dangers of electronic voting. Our treatment highlights the need for considering the whole socio-technical system, and for integrating security and fault tolerance viewpoints.

My talk will present a personal and rather selective view of the state of the art of some aspects of dependability assessment for software-based systems. This short note gives a brief outline of the issues I shall address.

Redundancy and diversity are commonly applied principles for fault tolerance against accidental faults. Their use in security - to protect against intentional faults - is attracting increasing interest. I propose that there is a need for a formal probabilistic treatment, similar to the one that has brought successful insights in reliability.

Previous models have investigated the impact upon diversity - and hence upon the reliability of fault-tolerant software built from 'diverse' versions - of the variation in 'difficulty' of demands over the demand space. These models are essentially static, taking a single snapshot view of the system. In this paper, we consider a generalisation in which the individual versions are allowed to evolve - and their reliability to grow - through debugging. In particular, we examine the trade-off that occurs in testing between, on the one hand, the increasing reliability of individual versions, and on the other hand the possible diminution of diversity.

Intellectual diversity – difference – has long been used in human affairs to minimise the impact of mistakes. In the past couple of decades design diversity has been used to seek dependability in software-based systems. This use of design diversity prompted the first formal studies of the efficacy of intellectual diversity. In this paper we examine diverse arguments – in particular arguments to support claims about system dependability (reliability, safety). Our purpose is to see whether the probabilistic approach that has been so successful in design diversity can be applied to diversity in arguments. The work reported here is somewhat tentative and speculative. 1.

Summary form only given. Complexity is the enemy of dependability. The author notes that if one wants to build systems that are safe and reliable, we know that we should make them as simple as possible. Unfortunately, not all complexity is the result of poor design. Sometimes complexity is necessary. In such circumstances simplicity may not be achievable. How, then, do we make our systems dependable? It is argued that one way forward is through the use of diversity. The best-known applications of diversity in computing date back a couple of decades and involve design diversity, e.g. n-version programming. This kind of diversity, in the pursuit of fault tolerance, has had a checkered history. On the one hand, several famous experiments have shown that the benefits fall far short of what might be expected if the different versions were to fail independently. On the other hand, several serious industrial applications seem to have worked well. The major thesis of this talk, though, is that diversity is ubiquitous. In particular, the author will argue that diversity appears to be 'a good thing' not only for fault-tolerant system design but in other areas of software engineering. An example is the use of diverse methods to seek faults in software. Another is in diverse arguments - e.g. He then will try to show that the formalism developed for design diversity will work in these wider contexts. Some of the results are intuitively plausible, some of them are rather surprising and non-intuitive. Altogether, it seems that this is another area of computer science where mathematical formality can bring better understanding and, ultimately, better control over the attributes of the systems we build.

No abstract available.

Research results indicate that (as usual in software engineering) these question can only be answered with reference to each specific application context and that diversity is no “silver bullet”. But diversity is an attractive option, made more interesting by current trends like the preference for COTS items, and it is important for practitioners to go beyond the summary opinions and misunderstanding that surround it.

The limits to the reliability that can be claimed for a design-diverse fault-tolerant system are mainly determined by the dependence that must be expected in the failure behaviours of the different versions: claims for independence between version failure processes are not believable. We examine a different approach, in which a simple secondary system is used as a back-up to a more complex primary. The secondary system is sufficiently simple that claims for its perfection (with respect to design faults) are possible, but there is not complete certainty about such perfection. It is shown that assessment of the reliability of the overall fault-tolerant system in this case may take advantage of claims for independence that are more plausible than those involved in design diversity.

Considers what happens when several different fault-finding techniques are used together. The effectiveness of such multi-technique approaches depends upon a quite subtle interplay between their individual efficacies. The modeling tool we use to study this problem is closely related to earlier work on software design diversity which showed that it would be unreasonable even to expect software versions that were developed truly independently to fail independently of one another. The key idea was a "difficulty function" over the input space. Later work extended these ideas to introduce a notion of "forced" diversity. In this paper, we show that many of these results for design diversity have counterparts in diverse fault detection in a single software version. We define measures of fault-finding effectiveness and diversity, and show how these might be used to give guidance for the optimal application of different fault-finding procedures to a particular program. The effects on reliability of repeated applications of a particular fault-finding procedure are not statistically independent; such an incorrect assumption of independence will always give results that are too optimistic. For diverse fault-finding procedures, it is possible for effectiveness to be even greater than it would be under an assumption of statistical independence. Diversity of fault-finding procedures is a good thing and should be applied as widely as possible. The model is illustrated using some data from an experimental investigation into diverse fault-finding on a railway signalling application.

This paper addresses a family of probability models for the failure time process known as order statistics models. Conventional order statistics models make rather strong distributional assumptions about the detection times: typically they assume that these come from some parametric family of distributions. In this paper a new model is presented that relaxes these distributional assumptions, and—in the tradition of non-parametric statistics generally—‘allows the data to speak for themselves’. The accuracy of the new model is compared on some real data sets with the predictions that come from several of the better parametric reliability growth models © 1998 John Wiley & Sons, Ltd.

There are two main goals in testing software: (1) to achieve adequate quality (debug testing), where the objective is to probe the software for defects so that these can be removed, and (2) to assess existing quality (operational testing), where the objective is to gain confidence that the software is reliable. Debug methods tend to ignore random selection of test data from an operational profile, while for operational methods this selection is all-important. Debug methods are thought to be good at uncovering defects so that these can be repaired, but having done so they do not provide a technically defensible assessment of the reliability that results. On the other hand, operational methods provide accurate assessment, but may not be as useful for achieving reliability. This paper examines the relationship between the two testing goals, using a probabilistic analysis. We define simple models of programs and their testing, and try to answer the question of how to attain program reliability: is it better to test by probing for defects as in debug testing, or to assess reliability directly as in operational testing? Testing methods are compared in a model where program failures are detected and the software changed to eliminate them. The "better" method delivers higher reliability after all test failures have been eliminated. Special cases are exhibited in which each kind of testing is superior. An analysis of the distribution of the delivered reliability indicates that even simple models have unusual statistical properties, suggesting caution in interpreting theoretical comparisons.

Testing methods are compared in a model where program failures are detected and the software changed to eliminate them.The question considered is whether it is better to use tests that seek out failures ("debug testing") or to simulate usage and find failures along the way ("operational testing'')."Better" is measured by the delivered reliability obtained after all test failures have been eliminated.This comparison extends previous work, where the measure was the probability of detecting a failure.The theoretical treatment of the paper is probabilistic and analytical.Revealing special cases are exhibited in which each kind of testing is superior.

The large amount of literature on software reliability assessment and prediction is essentially concerned with parametric models: the inter failure time random variables are assumed to come from parametric families of distributions. Such models involve quite strong assumptions. The motivation for the present work is to relax these assumptions and-in the tradition of non parametric statistics generally-'allow the data to speak for themselves'. We present a new non-parametric model for reliability prediction which is based upon the use of kernel density estimators and compare its accuracy on some real data sets with the predictions that come from several of the better conventional models. These initial results are encouraging: the new models seem to perform as well as the best of the earlier models.

Operational testing, which aims to generate sequences of test cases with the same statistical properties as those that would be experienced in real operational use, can be used to obtain quantitative measures of the reliability of software. In the case of safety critical software it is common to demand that all known faults are removed. This means that if there is a failure during the operational testing, the offending fault must be identified and removed. Thus an operational test for safety critical software takes the form of a specified number of test cases (or a specified period of working) that must be executed failure-free. This paper addresses the problem of specifying the numbers of test cases (or time periods) required for a test, when the previous test has terminated as a result of a failure. It has been proposed that, after the obligatory fix of the offending fault, the software should be treated as if it were completely novel, and be required to pass exactly the same test as originally specified. The reasoning here claims to be conservative, in as much as no credit is given for any previous failure-free operation prior to the failure that terminated the test. We show that, in fact, this is not a conservative approach in all cases, and propose instead some new Bayesian stopping rules. We show that the degree of conservatism in stopping rules depends upon the precise way in which the reliability requirement is expressed. We define a particular form of conservatism that seems desirable on intuitive grounds, and show that the stopping rules that exhibit this conservatism are also precisely the ones that seem preferable on other grounds.

Effects of shared use on the dependability of modular software are evaluated in terms of a generally defined stochastic model. The total system in question consists of a community of n users who share a software system with m modules. The input aspect of the operational environment, reflecting user demands at the module level, is represented by a continuous-time, finite-state Markov process, called the operational profile. The profile's construction is based on the isolated profiles of individual users which, in the case of heterogeneous use, are pairwise-distinct processes. Moreover, in the presence of other users, an individual profile can differ from its isolated version due to "slowdowns" caused by sharing. This multiuser profile is then combined with a failure model which, among other things, captures "stress" due to shared use. A number of basic issues are then addressed and resolved in terms of closed-form dependability solutions obtained for elementary 2-user, 1-module systems. Specifically, three measures are investigated in this manner, providing considerable insight into how dependability, as perceived by a subject user, is affected by the profile of an interfering user.

Ideally, a measure of the security of a system should capture quantitatively the intuitive notion of ‘the ability of the system to resist attack’. That is, it should be operational, reflecting the degree to which the system can be expected to remain

There is no universally applicable software reliability growth model which can be trusted to give accurate predictions of reliability in all circumstances. A technique of analyzing predictive accuracy called the u-plot allows a user to estimate the relationship between the predicted reliability and the true reliability. It is shown how this can be used to improve reliability predictions in a very general way by a process of recalibration. Simulation results show that the technique gives improved reliability predictions in a large proportion of cases. However, a user does not need to trust the efficacy of recalibration, since the new reliability estimates produced by the technique are truly predictive and their accuracy in a particular application can be judged using the earlier methods. The generality of this approach suggests its use whenever a software reliability model is used. Indeed, although this work arose from the need to address the poor performance of software reliability models, it is likely to have applicability in other areas such as reliability growth modeling for hardware.>

Work by D.E. Eckhardt and L.D. Lee (1985), shows that independently developed program versions fail dependently. The authors show that there is a precise duality between input choice and program choice in this model and consider a generalization in which different versions can be developed using diverse methodologies. The use of diverse methodologies is shown to decrease the probability of the simultaneous failure of several versions. Indeed, it is theoretically possible to obtain versions which exhibit better than independent failure behavior. The authors formalize the notion of methodological diversity by considering the sequence of decision outcomes that constitute a methodology. They show that diversity of decision implies likely diversity of behavior for the different versions developed under such forced diversity. For certain one-out-of-n systems the authors obtain an optimal method for allocating diversity between versions. For two-out-of-three systems there seem to be no simple optimality results which do not depend on constraints which cannot be verified in practice.>

Different software reliability models can produce very different answers when called on to predict future reliability in a reliability growth context. Users need to know which, if any, of the competing predictions are trustworthy. Some techniques are presented which form the basis of a partial solution to this problem. Rather than attempting to decide which model is generally best, the approach adopted allows a user to decide on the most appropriate model for each application.

A set of criteria is proposed for the comparison of software reliability models. The intention is to provide a logically organized basis for determining the superior models and for the presentation of model characteristics. It is hoped that in the future, a software manager will be able to more easily select the model most suitable for his/her requirements from among the preferred ones.

An examination of the assumptions used in early bug-counting models of software reliability shows them to be deficient. Suggestions are made to improve modeling assumptions and examples are given of mathematical implementations. Model verification via real-life data is discussed and minimum requirements are presented. An example shows how these requirements may be satisfied in practice. It is suggested that current theories are only the first step along what threatens to be a long road.