Improved techniques for software testing based on Markov chain usage models

In statistical testing of software all possible uses of the software, at some level of abstraction, are represented by a statistical model wherein each possible use of the software has an associated probability of occurrence [16]. Test cases are drawn from the sample population of possible uses according to the sample distribution and run against the software under test. Various statistics of interest, such as the estimated failure rate and mean time to failure of the software are computed. The testing performed is evaluated relative to the population of uses to determine whether or not to stop testing.

The model used to represent use of the software in this work is a finite state, time homogeneous, discrete parameter, irreducible Markov chain [10]. In a Markov chain usage model the states of use of the software are represented as states in the Markov chain [1,18, 21,22]. User actions are represented as state transitions in the Markov chain. The probability of a user performing a certain action given that the software is in a particular state of use is represented by the associated transition probability in the Markov chain. The usage model always contains two special states, the (Invoke) state and (Terminate) state. The (Invoke) state represents the software prior to invocation and the (Terminate) state represents the software after execution has ceased. All test cases start from the (Invoke,) state and end in the (Terminate) state.

Given a Markov chain based usage model it is possible to analytically compute a number of statistics useful for validation of the model, test planning, test monitoring, and evaluation of the software under test. Example statistics include the expected test case length and associated variance, the probability of a state or arc appearing in a test case, the long run probability of the software being in a certain state of use [22]. Test cases are randomly generated from the usage model, i.e., randomly sampled based on the use distribution. These test cases are run against the software and estimates of reliability are computed.