Software systems composed of highly reliable components may experience few, if any, failures while undergoing heavy testing or field usage. L.M. Kaufman et al. (1997, 1998) applied "statistics of the extremes" to software reliability analysis for failure as an infrequent, unlikely occurrence /sub -/ /sub a/ so-called rare event. This paper combines (i) software failure as a rare event with (ii) a finite-state, discrete-parameter recurrent Markov chain that models both the failures (as transitions to a rare fail state) and the software usage probabilities (as transitions among usage states not involving the fail state). When conditions for rare events are met, reliability analysis in greater detail, with fewer assumptions, may be possible, and there may be additional justification for using the popular Poisson and exponential distributions for certain random variables. We describe how the Markov chain and the "Poisson law of small numbers", which has a central role in the study of rare events and extreme values, yield (a) an explicit error bound on a Poisson approximation for counts of failures as rare events in long realizations of the chain, and (b) an approximate exponential distribution for the interoccurrence time of failures as rare events. We compute both the Poisson error bound and /spl chi//sup 2/ goodness-of-fit tests for samples and the approximate distributions for a small Markov chain. A typical application of these results would be in the analysis of software reliability for systems of high-quality COTS components.

Statistical testing of software establishes a basis for statistical inference about a software system's expected field quality. This paper describes a method for statistical testing based on a Markov chain model of software usage. The significance of the Markov chain is twofold. First, it allows test input sequences to be generated from multiple probability distributions, making it more general than many existing techniques. Analytical results associated with Markov chains facilitate informative analysis of the sequences before they are generated, indicating how the test is likely to unfold. Second, the test input sequences generated from the chain and applied to the software are themselves a stochastic model and are used to create a second Markov chain to encapsulate the history of the test, including any observed failure information. The influence of the failures is assessed through analytical computations on this chain. We also derive a stopping criterion for the testing process based on a comparison of the sequence generating properties of the two chains.>

A procedure for modeling software usage with the finite state, discrete parameter Markov chain is described. It involves rigorous analysis of the specification before design and coding begin. Many benefits emerge from this process, including the ability to synthesize a macro level usage distribution from a micro level understanding of how the software will be used. This usage distribution becomes the basis for a statistical test of the software, which is fundamental to the Cleanroom development process. Some analytical results known for Markov chains that have meaningful implications and interpretations for the software development process are described.