Computational investigations of quasirandom sequences in generating test cases for specification-based tests
Abstract
This paper presents work on generation of specification-driven test cases based on quasirandom (low-discrepancy) sequences instead of pseudorandom numbers. This approach is novel in software testing. This enhanced uniformity of quasirandom sequences leads to faster generation of test cases covering all possibilities. We demonstrate by examples that quasirandom sequences can be a viable alternative to pseudorandom numbers in generating test cases. In this paper, we present a method that can generate test cases from a decision table specification more effectively via quasirandom numbers. Analysis of a simple problem in this paper shows that quasirandom sequences achieve better data than pseudorandom numbers, and have the potential to converge faster and so reduce the computational burden. The use of different quasirandom sequences for generating test cases is presented in this paper.
References
[1]
Abdurazik, A. and P. Ammann and W. Ding and J. Offutt. 2000. Evaluation of Three Specification- Based Testing Criteria.Sixth IEEE International Conference on Complex Computer Systems (ICECCS'00) 179--187.
[2]
Chang, K. H. and S. Liao and R. Chapman. 2000. Test Scenario Geneneration Based On Formal Specification And Usage. International Journal of Software Engineering and Knowledge Engineering. 10(2):1--17.
[3]
Chi, H. and M. Mascagni and T. Warnock. 2005. On the Optimal Halton Sequences. Mathematics and Computers in Simulation. 70(1): 9--21.
[4]
Chi, H and E. L. Jones and D. Evans. 2006. Generating Test Data for Specification-based Tests via Quasirandom Sequences. Lecture Notes in Computer Science.3994: 773--780.
[5]
Fox, B. 1986. Implementation and relative efficiency of quasirandom sequence generators", ACM Trans. on Mathematical Software. 12:362--376.
[6]
Glora, N. and H. Pu and W. O. Rom. 1995. Evaluation of Process Tools in Systems Analysis. Information and Technology. 37: 1191--1126.
[7]
Goodenough, J. B. and S. L. Gerhart. 1975. Toward a theory of test data selection. Proceedings of the international conference on Reliable software. 493--510.
[8]
Hong, H. S. and F. J. Hickernell. 2003. Algorithm 823: Implementing Scrambled Digital Sequences. ACM Transactions on Mathematical Software. 29 (2): 95--109.
[9]
Jones, E. L. 2005. Automated Support for Test-driven Specification. Proceedings of the 9th IASTED International Conference on Software Engineering and Applications. 218--223.
[10]
Jones, E. L. 2006. Test-Driven Specification: Paradigm and Automation. 44th ACM Southeast Conference, March 10--12, Melbourne, Florida.
[11]
Keller, A. 1995. A Quasi-Monte Carlo Algorithm for the Global Illumination Problem in the Radiosity Setting. Lecture Notes in Statistics (Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing). 106: 239--251.
[12]
Knuth, D. E. 1997. The Art of Computer Programming, vol. 2: Seminumerical Algorithms. New York, Cambridge University Press.
[13]
Kuipers, L. and H. Niederreiter. 1974. Uniform Distribution of Sequences. New York, John Wiley and Sons.
[14]
Loh, W. L. 2003. On the asymptotic distribution of scrambled net quadrature. Annals of Statistics. 31: 1282--1324.
[15]
Morokoff, W. J. and R. E. Caflish. 1994. Quasirandom sequences and their discrepancy. SIAM Journal on Scientific Computing. 15: 1251--1279.
[16]
Muccini, H. and A. Bertolino and P. Inverardi. 2004. Using Software Architecture for Code Testing. IEEE Trans. on Software Engineering. 30(3): 160--17.
[17]
Niederreiter, H. 1992. Random Number Generations and Quasi-Monte Carlo Methods. Philadelphia, SIAM.
[18]
Owen, A. 2004. Halton Sequences Avoid the Origin. Research Report, Stanford University. Available online via <http://www-stat.stanford.edu/~owen/reports/halton.pdf> {accessed July 12, 2006}.
[19]
Papageorgiou, A. and J. Traub. 1997. Beating Monte Carlo. RISK. 9:63--65.
[20]
Podgurski, A. and W. Masri and Y. McCleese and F. G. Wolff and C. Yang. 1999. Estimation of software reliability by stratified sampling, ACM Trans. Softw. Eng. Methodol. 8(3): 263--283.
[21]
Press, W. H. and S. A. Teukolsky and W. T. Vetterling and B. P. Flannery. 1992 Numerical Recipes in C. Reading, Massachusetts. Addison-Wesley.
[22]
Soboí. I. M. 1967. Uniformly distributed sequences with additional uniformity properties. USSR Comput. Math. and Math. Phy. 16: 236--242.
[23]
Spanier, J. and E. Maize. 1994. Quasirandom methods for estimating integrals using relatively small sampling. SIAM Review. 36: 18--44.
[24]
Stocks, P. and D. Carrington. 1993. Test template framework: A specification-based testing case study. Proceedings of Int. Symp. Software Testing and Analysis, Cambridge, MA. 11--18.
[25]
Tezuka, S. 1995. Uniform Random Numbers, Theory and Practice. IBM Japan, Kluwer Academic Publishers.
- Computational investigations of quasirandom sequences in generating test cases for specification-based tests
Recommendations
Generating test data for specification-based tests via quasirandom sequences
ICCS'06: Proceedings of the 6th international conference on Computational Science - Volume Part IVThis paper presents work on generation of specification- driven test data, by introducing techniques based on a subset of quasirandom sequences (completely uniformly distributed sequences) to generate test data. This approach is novel in software ...
Computational investigations of low-discrepancy sequences
The Halton, Sobol, and Faure sequences and the Braaten-Weller construction of the generalized Halton sequence are studied in order to assess their applicability for the quasi Monte Carlo integration with large number of variates. A modification of the ...
Computational investigations of scrambled Faure sequences
The Faure sequence is one of the well-known quasi-random sequences used in quasi-Monte Carlo applications. In its original and most basic form, the Faure sequence suffers from correlations between different dimensions. These correlations result in ...
Comments
Information & Contributors
Information
Published In
December 2006
2429 pages
ISBN:1424405017
- Editors:
- L. Felipe Perrone,
- Barry G. Lawson,
- Jason Liu,
- Frederick P. Wieland,
- General Chair:
- David Nicol,
- Program Chair:
- Richard Fujimoto
Sponsors
- IIE: Institute of Industrial Engineers
- ASA: American Statistical Association
- IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
- IEEE-CS\DATC: The IEEE Computer Society
- SIGSIM: ACM Special Interest Group on Simulation and Modeling
- NIST: National Institute of Standards and Technology
- (SCS): The Society for Modeling and Simulation International
- INFORMS-CS: Institute for Operations Research and the Management Sciences-College on Simulation
Publisher
Winter Simulation Conference
Publication History
Published: 03 December 2006
Check for updates
Qualifiers
- Article
Conference
WSC06
Sponsor:
- IIE
- ASA
- IEICE ESS
- IEEE-CS\DATC
- SIGSIM
- NIST
- (SCS)
- INFORMS-CS
Acceptance Rates
WSC '06 Paper Acceptance Rate 177 of 252 submissions, 70%;
Overall Acceptance Rate 3,413 of 5,075 submissions, 67%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 145Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 07 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in