Quasi-random testing

ABSTRACT

Quasi-random sequences, also known as low-discrepancy or low-dispersion sequences, are sequences of points in an n-dimensional unit hypercube. These sequences have the property that points are spread more evenly throughout the cube than random point sequences, which result in regions where there are clusters of points and others that are sparsely populated. Based on the observation that program faults tend to lead to contiguous failure regions within a program's input domain, and that an even spread of random tests enhances the failure detection effectiveness for certain failure patterns, we examine the use of these sequences as a replacement for random sequences in automated testing.The limited number of quasi-random sequences available from the standard algorithms poses significant practical problems for use when testing real programs, and especially for evaluating its effectiveness. We examine the use of randomised quasi-random sequences, which are permuted in a nondeterministic fashion but still retain their low discrepancy properties, to overcome this problem, and show that testing using randomised quasi-random sequences is often significantly more effective than random testing.

REFERENCES

• 1: Association for Computing Machinery. Collected Algorithms from ACM, Vol I, II, III. Association for Computing Machinery, 1980.
• 2: P. G. Bishop. The variation of software survival times for different operational input profiles. In FTSC-23. Digitest of Papers, the Twenty-Third International Symposium on Fault-Tolerant Computing, pages 98--107. IEEE Computer Society Press, June 1993.
• 3: T. Y. Chen , R. Merkel , G. Eddy , P. K. Wong, Adaptive Random Testing Through Dynamic Partitioning, Proceedings of the Quality Software, Fourth International Conference on (QSIC'04), p.79-86, September 08-10, 2004 [doi>10.1109/QSIC.2004.6]
• 4: T. Y. Chen, F.-C. Kuo, R. Merkel, and S. Ng. Mirror adaptive random testing. Information and Software Technology, 46(15):1001--1010, 2004.
• 5: T. Y. Chen, H. Leung, and I. K. Mak. Adaptive random testing. In Proceedings of the 9th Asian Computing Science Conference, volume 3321 of Lecture Notes in Computer Science, pages 320--329, 2004.
• 6: I. Friedel and A. Keller. Fast generation of randomized low-discrepancy point sequences. In K. T. Fang, F. J. Hickernell, and H. Niederreiter, editors, Monte Carlo and Quasi-Monte Carlo Methods 2000, pages 257--273. Springer-Verlag, 2002.
• 7: T. Kollig and A. Keller. SamplePack, July 2004. http://www.uni-kl.de/AG-Heinrich/SamplePack.html.
• 8: J. Mayer. Adaptive random testing by bisection and localization. Accepted to appear in The Fifth International Workshop on Formal Approaches to Testing of Software (FATES 2005), November 2005.
• 9: H. Niederreiter. Low discrepancy and low-dispersion sequences. Journal of Number Theory, 30:51--70, 1988.
• 10: A. B. Owen. Randomly permuted (t, m, s)-nets and (t, s)-sequences. In H. Niederreiter and P.-S. Shiue, editors, Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, volume 127 of Lecture Notes in Statistics. Springer-Verlag, 1995.
• 11: A. B. Owen. Scrambled nets for accurate multivariate inegration, July 2004. http://www-stat.stanford.edu/~owen/scramblednets|.
• 12: W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, editors. Numerical Recipes. Cambridge University Press, 1986.
• 13: Donald R. Slutz, Massive Stochastic Testing of SQL, Proceedings of the 24rd International Conference on Very Large Data Bases, p.618-622, August 24-27, 1998
• 14: L. White and E. Cohen. A domain strategy for computer program testing. IEEE Transactions on Software Engineering, 6:247--257, 1980.
• 15: Takahide Yoshikawa , Kouya Shimura , Toshihiro Ozawa, Random Program Generator for Java JIT Compiler Test System, Proceedings of the Third International Conference on Quality Software, p.20, November 06-07, 2003

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Algorithms, Reliability, Verification

Keywords:
adaptive random testing, automated testing, low-discrepancy sequence, quasi-random sequence, random testing