MC-MIPOG: A Parallel t-Way Test Generation Strategy for Multicore Systems

ETRI Journal

关键词: parallel processing;    combinatorial testing;    multi-way testing;    t-way testing;   

Others  :  1185993
DOI  :  10.4218/etrij.10.0109.0266

【 摘 要 】

Combinatorial testing has been an active research area in recent years. One challenge in this area is dealing with the combinatorial explosion problem, which typically requires a very expensive computational process to find a good test set that covers all the combinations for a given interaction strength (t). Parallelization can be an effective approach to manage this computational cost, that is, by taking advantage of the recent advancement of multicore architectures. In line with such alluring prospects, this paper presents a new deterministic strategy, called multicore modified input parameter order (MC-MIPOG) based on an earlier strategy, input parameter order generalized (IPOG). Unlike its predecessor strategy, MC-MIPOG adopts a novel approach by removing control and data dependency to permit the harnessing of multicore systems. Experiments are undertaken to demonstrate speedup gain and to compare the proposed strategy with other strategies, including IPOG. The overall results demonstrate that MC-MIPOG outperforms most existing strategies (IPOG, IPOF, IPOF2, IPOG-D, ITCH, TConfig, Jenny, and TVG) in terms of test size within acceptable execution time. Unlike most strategies, MC-MIPOG is also capable of supporting high interaction strengths of t > 6.

   

【 参考文献 】

• [1]K.C. Tai and Y. Lei, "A Test Generating Strategy for Pairwise Testing," IEEE Trans. Software Engineering, vol. 28, no. 1, 2002, pp. 109-111.
• [2]D.R. Kuhn and V. Okun, "Pseudo-Exhaustive Testing for Software," Proc. 30th Annual IEEE/NASA Software Engineering Workshop, Apr. 25-27, 2006, pp. 153-158.
• [3]Y. Lei et al., "IPOG: A General Strategy for t-Way Software Testing," Proc. 14th Annual IEEE Intl. Conf. and Workshops on the Engineering of Computer-Based Systems, Tucson, AZ, Mar. 26-29, 2007, pp. 549-556.
• [4]M. Hutchins et al., "Experiments on the Effectiveness of Dataflow- and Controlflow-Based Test Adequacy Criteria," Proc. 16th Intl. Conf. Software Engineering, May 16-21, 1994, pp. 191-200.
• [5]R. Kuhn, Y. Lei, and R. Kacker, "Practical Combinatorial Testing: Beyond Pairwise," IEEE IT Professional, vol. 10, no. 3, 2008, pp. 19-23.
• [6]M. Ellims, D. Ince, and M. Petre, "The Effectiveness of t-Way Test Data Generation," Proc. 27th Int. Con. Computer Safety, Reliability, and Security, Sept. 22-25, 2008, pp. 16-29.
• [7]A. Williams, TConfig Java Test Tool. Available: http://www.site. uottawa.ca /~awilliam. Last accessed on April 30, 2009.
• [8]B. Jenkins, Jenny test tool. http://www.burtleburtle.net./bob/ math/jenny.html. Last accessed on May 7, 2009.
• [9]J. Arshem, TVG test tool, http://sourceforge.net/projects/tvg/. Last accessed on May 7, 2009.
• [10]A. Hartman, T. Klinger, and L. Raskin, IBM Intelligent Test Case Handler, http://www.alphaworks.ibm.com/tech/whitch. Last accessed on May 7, 2009.
• [11]Y. Lei et al., "IPOG/IPOG-D: Efficient Test Generation for Multi-way Combinatorial Testing," Software Testing, Verification and Reliability, vol. 18, no. 3, 2007, pp. 125-148.
• [12]M. Forbes et al., "Refining the In-Parameter-Order Strategy for Constructing Covering Arrays," J. Research of the National Institute of Standards and Technology, vol. 113, no. 5, 2008, pp. 287-297.
• [13]R.N. Kacker et al., "Automated Combinatorial Testing for Software Systems," Mathematical and Computational Sciences Division, NIST Report, Jan. 2008, pp. 38-40.
• [14]M.B. Cohen et al., "Constructing Test Suites for Interaction Testing," Proc. 25th IEEE Int. Conf. Software Engineering, May 3-10, 2003, pp. 38-48.
• [15]A. Hartman and L. Raskin, "Problems and Algorithms for Covering Arrays," Discrete Mathematics, vol. 284, no. 1, 2004, pp. 149-156.
• [16]M. Grindal, J. Offutt, and S.F. Andler, "Combination Testing Strategies: A Survey," J. Software Testing, Verification, and Reliability, vol. 5, no. 3, 2004, pp. 167-199.
• [17]K.A. Bush, "Orthogonal Arrays of Index Unity," Annals of Mathematical Statistics, vol. 23, no. 3, 1952, pp. 426-434.
• [18]D.R. Kuhn, D. Wallace, and A. Gallo, "Software Fault Interactions and Implications for Software Testing," IEEE Trans. Software Engineering, vol. 30, no. 6, 2004, pp. 418-421.
• [19]A.W. Williams, "Determination of Test Configurations for Pair-Wise Interaction Coverage," Proc. 13th Int. Conf. Testing Communicating Systems, Aug. 29 -Sept. 1, 2000, pp. 59-74.
• [20]M. I. Younis et al., "Assessing IRPS as an Efficient Pairwise Test Data Generation Strategy," Int. J. Advanced Intelligence Paradigms, vol. 2, no. 1, 2010, pp. 90-104.
• [21]M.F.J. Klaib et al., "G2Way A Backtracking Strategy for Pairwise Test Data Generation," Proc. 15th Asia-Pacific Software Engineering Conference, vol. 3, no. 5, Dec. 03-05, 2008, pp. 463-470.
• [22]M. Grindal, J. Offutt, and J. Mellin, "Conflict Management when Using Combination Strategies for Software Testing," Proc. 18th Australian Software Engineering Conference, Apr. 10-13, 2007, pp. 255-264.
• [23]R.C. Bryce and C.J. Colbourn, "Prioritized Interaction Testing for Pairwise Coverage with Seeding and Constraints," Information and Software Technology Journal, vol. 48, no. 10, 2006, pp. 960-970.
• [24]D.M. Cohen et al., "The Combinatorial Design Approach to Automatic Test Generation," IEEE Software, vol. 13, no. 5, 1996, pp. 83-88.
• [25]Y. Lei and K.C. Tai, "In-Parameter-Order: A Test Generation Strategy for Pairwise Testing," Proc. 3rd IEEE Int. Conf. High-Assurance Systems Engineering Symposium, Nov. 13-14, 1998, pp. 254-261.
• [26]D.M. Cohen et al., "The AETG System: An Approach to Testing Based on Combinatorial Design," IEEE Trans. Software Engineering, vol. 23, no. 7, 1997, pp. 437-444.
• [27]R.C. Bryce and C.J. Colbourn, "The Density Algorithm for Pairwise Interaction Coverage," J. Software Testing, Verification and Reliability, vol. 17, no. 3, 2007, pp. 159-182.
• [28]Y.W. Tung and W.S. Aldiwan, "Automating Test Case Generation for the New Generation Mission Software System," Proc. IEEE Aerospace Conference, Mar. 18-25, 2000, pp. 431-437.
• [29]R.C. Bryce, C.J. Colbourn, and M.B. Cohen, "A Framework of Greedy Methods for Constructing Interaction Test Suites," Proc. 27th IEEE Int. Conf. Software Engineering, May 15-21, 2005, pp. 146-155.
• [30]R.C. Bryce and C.J. Colbourn, "A Density-Based Greedy Algorithm for Higher Strength Covering Arrays," Software Testing, Verification, and Reliability, vol. 19, no. 1, 2009, pp. 37-53.
• [31]M.A. Chateauneuf, C.J. Colbourn, and D.L. Kreher, "Covering Arrays of Strength Three," Designs, Codes, and Cryptography, vol. 16, no. 1, 1999, pp. 235-242.
• [32]Website for the NIST Automated Combinatorial Testing for Software (ACTS) project: http://csrc.nist.gov/groups/SNS/acts/ index.html. Last accessed on May 7, 2009.
• [33]Intel web site: http://www.intel.com/products/desktop/processors/ index.htm. Last accessed on May 7, 2009.
• [34]Intel Core 2 Quad Processors. Available at http://www.intel.com/ products/processor/core2quad/index.htm. Last accessed on May 7, 2009.
• [35]K. Chow and D. Dagastine, "How to Get the Most Performance from Sun JVM on Intel Multicore Servers," Sun Teach Day Developer Conference, Oct. 23-25, 2007.
• [36]C.J. Colbourn, Covering Array Tables, Available: http://www. public.asu.edu/~ccolbou/src/tabby/catable.html. Last accessed on July 12, 2009.