Importance Sampling of Test Cases in Markovian Software Usage Models
- 1 January 1997
- journal article
- research article
- Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences
- Vol. 11 (1), 19-36
- https://doi.org/10.1017/s0269964800004642
Abstract
Recently, some authors have suggested usage models of Markov type as a technique of specifying the estimated operational use distribution of a given program. A main purpose of such models is the derivation of random test cases allowing unbiased estimates on the (un)reliability of the program in its intended environment. In this article, we show that by a shift of the transition probabilities of the Markov chain corresponding to such a model, prior information on the errorjproneness of single-program operations can be taken into account. An unbiased unreliability estimator with reduced variance is obtained. Furthermore, it is shown that minimization of the variance leads to a special stochastic optimization problem that can be demonstrated to be convex, such that efficient solution techniques apply. Some related questions are also treated in a more general, non-Markovian framework.Keywords
This publication has 11 references indexed in Scilit:
- Optimal test distributions for software failure cost estimationIEEE Transactions on Software Engineering, 1995
- Fast simulation of rare events in queueing and reliability modelsACM Transactions on Modeling and Computer Simulation, 1995
- Statistical testing of software based on a usage modelSoftware: Practice and Experience, 1995
- Fast transient simulation of Markovian models of highly dependable systemsPerformance Evaluation, 1994
- Importance sampling for markov chains: asymptotics for the varianceCommunications in Statistics. Stochastic Models, 1994
- Markov analysis of software specificationsACM Transactions on Software Engineering and Methodology, 1993
- Stochastic Approximation and Optimization of Random SystemsPublished by Springer Science and Business Media LLC ,1992
- Importance Sampling for Stochastic SimulationsManagement Science, 1989
- Theories of Program Testing and the Application of Revealing SubdomainsIEEE Transactions on Software Engineering, 1980
- Stochastic Estimation of the Maximum of a Regression FunctionThe Annals of Mathematical Statistics, 1952