Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-03T02:01:47.475Z Has data issue: false hasContentIssue false
  • English
  • Français

Importance Sampling of Test Cases in Markovian Software Usage Models

Published online by Cambridge University Press:  27 July 2009

Walter J. Gutjahr
Walter J. Gutjahr
Affiliation:
Department of Statistics, Operations Research and Computer Science, University of Vienna, Universitatsstrasse 5/9 A-1010 Vienna, Austria
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 11 , Issue 1 , January 1997 , pp. 19 - 36
Copyright
Copyright © Cambridge University Press 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Asmussen, S. & Rubinstein, R. (1995). Steady state rare event simulation in queuing models and its complexity properties. In Dshalalow, J. (ed.). Advances in Queuing: Theory, Methods and Open Problems. Boca Raton, FL: CRC Press.Google Scholar
2.Glynn, P.W. (1994). Importance sampling for Markov chains: Asymptotics for the variance. Communications in Statistics–Stochastic Models 10(4): 701–717.CrossRefGoogle Scholar
3.Glynn, P.W. & Iglehart, D.L. (1989). Importance sampling for stochastic simulations. Management Science 35(11): 1367–1392.CrossRefGoogle Scholar
4.Gutjahr, W.J. (1995). Optimal test distributions for software failure cost estimation. IEEE Transactions on Software Engineering SE-21: 219–228.CrossRefGoogle Scholar
5.Gutjahr, W.J. (1995). Partition testing vs. random testing: The influence of uncertainty. Technical Report, University of Vienna, Vienna.Google Scholar
6.Hamlet, R. & Taylor, R. (1988). Partition testing does not inspire confidence. In Proceedings of the 2nd Workshop on Software Testing, Verification, and Analysis 07: 206–215.Google Scholar
7.Heidelberger, P. (1995). Fast simulation of rare events in queuing and reliability models. ACM Transactions on Modeling and Computer Simulation 5(1): 43–85.CrossRefGoogle Scholar
8.Kiefer, J. & Wolfowitz, J. (1952). Stochastic estimation of the maximum of a regression function. Annals of Mathematical Statistics 23: 462–466.CrossRefGoogle Scholar
9.Ljung, P., Pflug, G., & Walk, H. (1992). Stochastic Approximation and Optimization of Stochastic Systems. Basel: Birkhaus.CrossRefGoogle Scholar
10.Rubinstein, R.Y. (1981). Simulation and the Monte Carlo Method. New York: Wiley.CrossRefGoogle Scholar
11.Shahabuddin, P. (1994). Fast transient simulation of Markovian models of highly dependable systems. Performance Evaluation 20: 266–286.CrossRefGoogle Scholar
12.Walrand, J. (1988). An Introduction to Queuing Networks. New York: Prentice-Hall.Google Scholar
13.Walton, G.H., Poore, J.H., & Trammell, J. (1995). Statistical testing of software based on a usage model. Software–Practice and Experience 25(1): 97–108.CrossRefGoogle Scholar
14.Weyuker, E.J. & Ostrand, T.J. (1980). Theories of program testing and the application of revealing subdomains. IEEE Transactions on Software Engineering SE-6: 236–245.CrossRefGoogle Scholar
15.Whittaker, J.A. (1992). Markov chain techniques for software testing and reliability analysis. Ph.D. dissertation, University of Tennessee, Knoxville.Google Scholar
16.Whittaker, J.A. & Poore, J.H. (1993). Markov analysis of software specifications. ACM Transactions on Software Engineering and Methodology 2(1): 93–106.CrossRefGoogle Scholar
17.Woit, D.M. (1994). Operational profile specification, test case generation, and reliability estimation for modules. Thesis, Queen's University, Kingston, Ontario, Canada.Google Scholar