Enhanced lattice-based adaptive random testing

ABSTRACT

Adaptive Random Testing (ART) has been proposed to improve the fault-detection capability of Random Testing (RT). Lattice-based ART (L-ART) is a distinctive ART method which generates test cases by systematically placing and then randomly shifting lattice nodes in the input domain. Previous studies showed that L-ART has a better fault-detection capability than RT, at the same generation cost. Test cases of L-ART however may be highly concentrated on certain parts of the input domain - a "skewed distribution of test cases". Because of this skewed distribution, when failure regions coincidentally reside in the area where L-ART selects a high density of test cases, L-ART can have a better fault-detection capability than when failure regions are in the low density area. Since failure regions can be in any part of the input domain, this dependency of fault-detection capability on the failure region location is undesirable. We have investigated the cause of such skewed test case distributions using L-ART. Based on our observations, we propose an enhancement to L-ART, which not only has a less-skewed test case distribution, but also demonstrates better and more consistent fault-detection capability than the original L-ART.

REFERENCES

• 1: Paul E. Ammann , John C. Knight, Data Diversity: An Approach to Software Fault Tolerance, IEEE Transactions on Computers, v.37 n.4, p.418-425, April 1988 [doi>10.1109/12.2185]
• 2: K. P. Chan, T. Y. Chen, and D. Towey. Normalized restricted random testing. In Proceedings of the 8th Ada-Europe International Conference on Reliable Software Technologies (Ada-Europe 2003), volume 2655 of Lecture Notes in Computer Science, pages 368--381, Toulouse, France, 2003. Springer-Verlag.
• 3: Kwok Ping Chan , T. Y. Chen , Dave Towey, Probabilistic Adaptive Random Testing, Proceedings of the Sixth International Conference on Quality Software, p.274-280, October 27-28, 2006 [doi>10.1109/QSIC.2006.48]
• 4: Tsong Yueh Chen , Fei-Ching Kuo , Huai Liu, Enhancing Adaptive Random Testing through Partitioning by Edge and Centre, Proceedings of the 2007 Australian Software Engineering Conference, p.265-273, April 10-13, 2007 [doi>10.1109/ASWEC.2007.20]
• 5: T. Y. Chen , D. H. Huang, Adaptive Random Testing by Localization, Proceedings of the 11th Asia-Pacific Software Engineering Conference, p.292-298, November 30-December 03, 2004 [doi>10.1109/APSEC.2004.17]
• 6: T. Y. Chen , De Hao Huang , T. H. Tse , Zongyuan Yang, An Innovative Approach to Tackling the Boundary Effect in Adaptive Random Testing, Proceedings of the 40th Annual Hawaii International Conference on System Sciences, p.262a, January 03-06, 2007 [doi>10.1109/HICSS.2007.67]
• 7: T. Y. Chen, D. H. Huang, and Zhi Quan Zhou. Adaptive random testing through iterative partitioning. In Proceedings of the 11th Ada-Europe International Conference on Reliable Software Technologies (Ada-Europe 2006), volume 4006 of Lecture Notes in Computer Science, pages 155--166, Porto, Portugal, 2006. Springer-Verlag.
• 8: T. Y. Chen, H. Leung, and I. K. Mak. Adaptive random testing. In Proceedings of the 9th Asian Computing Science Conference (ASIAN 2004), volume 3321 of Lecture Notes in Computer Science, pages 320--329, Chiang Mai, Thailand, 2004. Springer-Verlag.
• 9: Tsong Yueh Chen , Robert Merkel, An upper bound on software testing effectiveness, ACM Transactions on Software Engineering and Methodology (TOSEM), v.17 n.3, p.1-27, June 2008 [doi>10.1145/1363102.1363107]
• 10: T. Y. Chen , T. H. Tse , Y. T. Yu, Proportional sampling strategy: a compendium and some insights, Journal of Systems and Software, v.58 n.1, p.65-81, August 2001 [doi>10.1016/S0164-1212(01)00028-0]
• 11: Richard H. Cobb , Harlan D. Mills, Engineering Software Under Statistical Quality Control, IEEE Software, v.7 n.6, p.44-54, November 1990
• 12: T. Dabóczi, I. Kollr, G. Simon, and T. Megyeri. Automatic testing of graphical user interfaces. In Proceedings of the 20th IEEE Instrumentation and Measurement Technology Conference 2003 (IMTC 2003), pages 441--445, Vail, Colorado, USA, 2003. IEEE Computer Society.
• 13: B. S. Everitt. The Cambridge Dictionary of Statistics. Cambridge University Press, 1998.
• 14: Justin E. Forrester , Barton P. Miller, An empirical study of the robustness of Windows NT applications using random testing, Proceedings of the 4th conference on USENIX Windows Systems Symposium, p.6-6, August 03-04, 2000, Seattle, Washington
• 15: R. Hamlet. Random testing. In J. Marciniak, editor, Encyclopedia of Software Engineering, pages 970--978. John Wiley & Sons, second edition, 2002.
• 16: F. C. Kuo , T. Y. Chen , H. Liu , W. K. Chan, Enhancing adaptive random testing in high dimensional input domains, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244316]
• 17: P. S. Loo and W. K. Tsai. Random testing revisited. Information and Software Technology, 30(7): 402--417, 1988.
• 18: Johannes Mayer, Lattice-based adaptive random testing, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101963]
• 19: Barton P. Miller , Louis Fredriksen , Bryan So, An empirical study of the reliability of UNIX utilities, Communications of the ACM, v.33 n.12, p.32-44, Dec. 1990 [doi>10.1145/96267.96279]
• 20: E. Miller. Website testing. Software Research, Inc. http://www.soft.com/eValid/Technology/White.Papers/website.testing.html, 2005.
• 21: N. Nyman. In defense of monkey testing: Random testing can find bugs, even in well engineered software. Microsoft Corporation http://www.softtest.org/sigs/material/nnyman2.htm.
• 22: 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
• 23: L. J. White , E. I. Cohen, A Domain Strategy for Computer Program Testing, IEEE Transactions on Software Engineering, v.6 n.3, p.247-257, May 1980 [doi>10.1109/TSE.1980.234486]
• 24: 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