Generating transition probabilities for Markov chain usage models

In statistical testing of software, a software usage model is developed to characterize a population of uses of the software. The model is used to plan a testing program and later to generate a statistically correct sample of test cases (uses of the software). Performance on the sample is used as a basis for generalizations about operational reliability.

Although the usage model is developed from the software specifications, typically there is insufficient information to completely specify all one-step transition probabilities in the Markov chain. This work applies techniques from mathematical analysis, mathematical programming, linear algebra, and information theory to present a new approach to the representation and optimization of the transition probabilities of software usage mod- els. New contributions are:

The application of mathematical constraints and objective functions to manage information about expected software use and test management goals.
The development of an iterative process using convex programming to generate Markov chain transition probabilities that satisfy all known constraints and opti- mize an objective function.
The description and demonstration of some standard, useful constraints and objective functions to support statistical testing.
The development of a new specification complexity metric.