HOME > Abstract

[PDF Full Text (747KB)]

MC-MIPOG: A Parallel t-Way Test Generation Strategy for Multicore Systems
Mohammed I. Younis, and Kamal Z. Zamli
Abstract :	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.
Key word :	t-way testing, multi-way testing, combinatorial testing, parallel processing.
DOI :	http://dx.doi.org/10.4218/etrij.10.0109.0266
Cite this :	Mohammed I. Younis, and Kamal Z. Zamli, "MC-MIPOG: A Parallel t-Way Test Generation Strategy for Multicore Systems," ETRI Journal, vol. 32, no. 1, Feb. 2010, pp. 73-83. http://dx.doi.org/10.4218/etrij.10.0109.0266
References :	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.
Reader   Evaluation :	Important   Innovative   Insightful   Useful

This article has been downloaded 2,599 times.

ETRI Journal Vol.32, No.1

Regular Papers

	A Low-Complexity 128-Point Mixed-Radix FFT Processor for MB-OFDM UWB Systems
	Sang-In Cho, and Kyu-Min Kang ETRI Journal, vol.32, no.1, Feb. 2010, pp.1-10 http://dx.doi.org/10.4218/etrij.10.0109.0232
	Novel UWB Transceiver for WBAN Networks: A Study on AWGN Channels
	Chengshi Zhao, Zheng Zhou, and Kyungsup Kwak ETRI Journal, vol.32, no.1, Feb. 2010, pp.11-21 http://dx.doi.org/10.4218/etrij.10.0108.0738
	Game Traffic Classification Using Statistical Characteristics at the Transport Layer
	Young-Tae Han, and Hong-Shik Park ETRI Journal, vol.32, no.1, Feb. 2010, pp.22-32 http://dx.doi.org/10.4218/etrij.10.0109.0236
	Harmonic Identification Algorithms Based on DCT for Power Quality Applications
	Alejandro G. Yepes, Francisco D. Freijedo, Jesus Doval-Gandoy, Oscar Lopez, Pablo Fernandez-Comesaña, and Jano Malvar Álvarez ETRI Journal, vol.32, no.1, Feb. 2010, pp.33-43 http://dx.doi.org/10.4218/etrij.10.0109.0342
	Improvement of Ultra-wideband Link Performance over Bands Requiring Interference Mitigation in Korea
	Ahmad M. Rateb, Syarifah Kamilah Syed-Yusof, and Norsheila Fisal ETRI Journal, vol.32, no.1, Feb. 2010, pp.44-52 http://dx.doi.org/10.4218/etrij.10.0109.0218
	Electronic Feedback System for Stabilization of Fiber Ring Resonator
	Sommart Sang-Ngern, and Athikom Roeksabutr ETRI Journal, vol.32, no.1, Feb. 2010, pp.53-61 http://dx.doi.org/10.4218/etrij.10.0109.0320
	Design of an Internal Antenna with Near-Omnidirectional H-Plane Radiation Pattern over Ultra-wide Bandwidth
	Youngki Lee, Seokjin Hong, Jeongpyo Kim, and Jaehoon Choi ETRI Journal, vol.32, no.1, Feb. 2010, pp.62-67 http://dx.doi.org/10.4218/etrij.10.0109.0271
	Effects of Channel Electron In-Plane Velocity on the Capacitance-Voltage Curve of MOS Devices
	Ling-Feng Mao ETRI Journal, vol.32, no.1, Feb. 2010, pp.68-72 http://dx.doi.org/10.4218/etrij.10.0109.0386
	MC-MIPOG: A Parallel t-Way Test Generation Strategy for Multicore Systems
	Mohammed I. Younis, and Kamal Z. Zamli ETRI Journal, vol.32, no.1, Feb. 2010, pp.73-83 http://dx.doi.org/10.4218/etrij.10.0109.0266
	Dual-Port SDRAM Optimization with Semaphore Authority Management Controller
	Jaehwan Kim, and Jongwha Chong ETRI Journal, vol.32, no.1, Feb. 2010, pp.84-92 http://dx.doi.org/10.4218/etrij.10.0109.0262
	Linear Corrector Overcoming Minimum Distance Limitation for Secure TRNG from (17, 9, 5) Quadratic Residue Code
	Young-Sik Kim, Ji-Woong Jang, and Dae-Woon Lim ETRI Journal, vol.32, no.1, Feb. 2010, pp.93-101 http://dx.doi.org/10.4218/etrij.10.0109.0141
	Practical Second-Order Correlation Power Analysis on the Message Blinding Method and Its Novel Countermeasure for RSA
	HeeSeok Kim, Tae Hyun Kim, Joong Chul Yoon, and Seokhie Hong ETRI Journal, vol.32, no.1, Feb. 2010, pp.102-111 http://dx.doi.org/10.4218/etrij.10.0109.0249
	Sheetlike Waveguide for 2.4 GHz and 5 GHz Bands
	Kunsun Eom, and Arai Hiroyuki ETRI Journal, vol.32, no.1, Feb. 2010, pp.112-119 http://dx.doi.org/10.4218/etrij.10.0109.0142
	A Modified Fixed-Threshold SMO for 1-Slack Structural SVMs
	Changki Lee, and Myung-Gil Jang ETRI Journal, vol.32, no.1, Feb. 2010, pp.120-128 http://dx.doi.org/10.4218/etrij.10.0109.0425
	Mobile Telecommunications Market Regulations and Carrier Performance: The Korean Case
	Chuhwan Park, Sung-Soo Han, and Wang-hun Seok ETRI Journal, vol.32, no.1, Feb. 2010, pp.129-138 http://dx.doi.org/10.4218/etrij.10.0109.0179

Letters

	Performance of Selective Decode-and-Forward Relay Networks with Partial Channel Information
	Xianyi Rui ETRI Journal, vol.32, no.1, Feb. 2010, pp.139-141 http://dx.doi.org/10.4218/etrij.10.0209.0329
	GPS L5 Acquisition Schemes for Fast Code Detection and Improved Doppler Accuracy
	Inone Joo, Cheonsig Sin, Sanguk Lee, and Jaehoon Kim ETRI Journal, vol.32, no.1, Feb. 2010, pp.142-144 http://dx.doi.org/10.4218/etrij.10.0209.0414
	Approximation for the Two-Dimensional Gaussian Q-Function and Its Applications
	Jinah Park, and Seungkeun Park ETRI Journal, vol.32, no.1, Feb. 2010, pp.145-147 http://dx.doi.org/10.4218/etrij.10.0209.0352
	Compact Planar Dual-Wideband Bandstop Filters with Cross Coupling and Open-Ended Stepped Impedance Resonators
	Vamsi Krishna Velidi, and Subrata Sanyal ETRI Journal, vol.32, no.1, Feb. 2010, pp.148-150 http://dx.doi.org/10.4218/etrij.10.0209.0341
	Fully Integrated HBT MMIC Series-Type Extended Doherty Amplifier for W-CDMA Handset Applications
	Chanhoe Koo, Junghyun Kim, and Youngwoo Kwon ETRI Journal, vol.32, no.1, Feb. 2010, pp.151-153 http://dx.doi.org/10.4218/etrij.10.0209.0360
	Measurement Accuracy of Oscillation-Based Test of Analog-to-Digital Converters
	Peter Mrak, Anton Biasizzo, and Franc Novak ETRI Journal, vol.32, no.1, Feb. 2010, pp.154-156 http://dx.doi.org/10.4218/etrij.10.0209.0285
	TRE+: Extended Tree-Based Routing Ethernet
	Juan A. Carral, Guillermo Ibáñez, Alberto García-Martínez, Miguel A. Lopez-Carmona, and Ivan Marsa-Maestre ETRI Journal, vol.32, no.1, Feb. 2010, pp.157-159 http://dx.doi.org/10.4218/etrij.10.0209.0388
	Maximum Likelihood Training and Adaptation of Embedded Speech Recognizers for Mobile Environments
	Youngkyu Cho, and Dongsuk Yook ETRI Journal, vol.32, no.1, Feb. 2010, pp.160-162 http://dx.doi.org/10.4218/etrij.10.0209.0242
	Fast 3D Mesh Compression Using Shared Vertex Analysis
	Euee Seon Jang, Seoungwook Lee, Bonki Koo, Daiyong Kim, and Kyoungsoo Son ETRI Journal, vol.32, no.1, Feb. 2010, pp.163-165 http://dx.doi.org/10.4218/etrij.10.0209.0357
	Symmetric Adiabatic Logic Circuits against Differential Power Analysis
	Byong-Deok Choi, Kyung Eun Kim, Ki-Seok Chung, and Dong Kyue Kim ETRI Journal, vol.32, no.1, Feb. 2010, pp.166-168 http://dx.doi.org/10.4218/etrij.10.0209.0247
	Value of Number Portability on Internet Phones
	Jung Eun Ku, Sang Woo Lee, and Tchanghee Hyun ETRI Journal, vol.32, no.1, Feb. 2010, pp.169-171 http://dx.doi.org/10.4218/etrij.10.0209.0356