Markov chain techniques for software testing and reliability analysis

Cleanroom Software Engineering [40] is a new methodology that has evolved from structured programming into a promising technology for high quality software development. Cleanroom has three major components: specification, design with verification, and statistical certification testing. This dissertation describes a new approach to statistical testing by modeling software usage and the testing process as finite state, discrete parameter Markov chains. Using the software specification document as a guide, a Markov chain is constructed which models the usage of the specified software. This time homogeneous chain is used to compute stochastic properties of pertinent usage random variables before any code development begins and to generate a set of "statistically typical" test sequences. These sequences, along with any failure data they produce upon execution, are used as a training set for a second Markov chain which models the behavior of the software during testing. This second chain is updated as testing progresses and is used to compute software quality measures, such as the reliability and mean time between failure at any stage of the testing process. Comparison of the two chains is by an information theoretic discriminant function based on the ergodic properties of the stochastic processes. Among its uses this comparison yields an analytical stopping criterion for the testing process. The latter chain is updated based upon appropriate expected values to obtain a third chain which is used to predict future software quality. The model presented is a complete certification strategy encompassing usage modeling, statistical testing, and reliability analysis.