Construction of Variable Strength Covering Array for Combinatorial Testing Using a Greedy Approach to Genetic Algorithm

• Autorzy: Bansal P , Sabharwal S , Mittal N , Arora S

Identyfikatory

DOI

10.5277/E-INF150107

• Języki publikacji: EN

Abstrakty

EN

The limitation of time and budget usually prohibits exhaustive testing of interactions between components in a component based software system. Combinatorial testing is a software testing technique that can be used to detect faults in a component based software system caused by the interactions of components in an effective and efficient way. Most of the research in the field of combinatorial testing till now has focused on the construction of optimal covering array (CA) of fixed strength t which covers all t-way interactions among components. The size of CA increases with the increase in strength of testing t, which further increases the cost of testing. However, not all components require higher strength interaction testing. Hence, in a system with k components a technique is required to construct CA of fixed strength t which covers all t-way interactions among k components and all ti-way (where ti > t) interactions between a subset of k components. This is achieved using the variable strength covering array (VSCA). In this paper we propose a greedy based genetic algorithm (GA) to generate optimal VSCA. Experiments are conducted on several benchmark configurations to evaluate the effectiveness of the proposed approach.

Słowa kluczowe

EN

combinatorial testing; variable strength covering array; genetic algorithm; greedy approach

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: e-Informatica Software Engineering Journal
• Rocznik: 2015
• Tom: Vol. 9, nr 1
• Strony: 87--105
• Opis fizyczny: Bibliogr. 49 poz., rys., tab.

Twórcy

autor

Bansal P

• Netaji Subhas Institute of Technology, University of Delhi

autor

Sabharwal S

• Netaji Subhas Institute of Technology, University of Delhi

autor

Mittal N

• Netaji Subhas Institute of Technology, University of Delhi

autor

Arora S

• School of Computer Science and Engineering, Vellore Institute of Technology, Tamil Nadu

Bibliografia

• [1] D.M. Cohen, S.R. Dalal, M.L. Fredman, and G.C. Patton, “The AETG system: An approach to testing based on combinatorial design,” IEEE Transactions on Software Engineering, Vol. 23, No. 7, 1997, pp. 437–444.
• [2] A. Hartman, “Software and hardware testing using combinatorial covering suites,” in Graph Theory, Combinatorics and Algorithms. Springer, 2005, pp. 237–266.
• [3] D.M. Cohen, S.R. Dalal, A. Kajla, and G.C. Patton, “The automatic efficient test generator (AETG) system,” in 5th International Symposium on Software Reliability Engineering. IEEE, 1994, pp. 303–309.
• [4] D.M. Cohen, S.R. Dalal, J. Parelius, and G.C. Patton, “The combinatorial design approach to automatic test generation,” IEEE software, No. 5, 1996, pp. 83–88.
• [5] K. Burr and W. Young, “Combinatorial test techniques: Table-based automation, test generation and code coverage,” in Proc. of the Intl. Conf. on Software Testing Analysis & Review. San Diego, 1998.
• [6] S.R. Dalal, A. Jain, N. Karunanithi, J. Leaton, C.M. Lott, G.C. Patton, and B.M. Horowitz, “Model-based testing in practice,” in Proceedings of the 21st international conference on Software engineering. ACM, 1999, pp. 285–294.
• [7] D.R. Kuhn, D.R. Wallace, and A.M. Gallo Jr, “Software fault interactions and implications for software testing,” IEEE Transactions on Software Engineering,, Vol. 30, No. 6, 2004, pp. 418–421.
• [8] D.R. Kuhn and M.J. Reilly, “An investigation of the applicability of design of experiments to software testing,” in 27th Annual NASA Goddard/IEEE Software Engineering Workshop. IEEE, 2002, pp. 91–95.
• [9] M.B. Cohen, P.B. Gibbons, W.B. Mugridge, C.J. Colbourn, and J.S. Collofello, “A variable strength interaction testing of components,” in 27th Annual International Computer Software and Applications Conference. IEEE, 2003, pp. 413–418.
• [10] Y. Lei and K.C. Tai, “In-parameter-order: A test generation strategy for pairwise testing,” in Third IEEE International High-Assurance Systems Engineering Symposium. IEEE, 1998, pp. 254–261.
• [11] C. Nie and H. Leung, “A survey of combinatorial testing,” ACM Computing Surveys (CSUR), Vol. 43, No. 2, 2011, p. 11.
• [12] A. Hedayat, N. Sloane, and J. Stufken, Orthogonal Arrays, ser. Springer Series in Statistics. Springer, New York, 1999.
• [13] R. Mandl, “Orthogonal latin squares: an application of experiment design to compiler testing,” Communications of the ACM, Vol. 28, No. 10, 1985, pp. 1054–1058.
• [14] M.B. Cohen, P.B. Gibbons, W.B. Mugridge, and C.J. Colbourn, “Constructing test suites for interaction testing,” in 25th International Conference on Software Engineering. IEEE, 2003, pp. 38–48.
• [15] J.H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence. MIT press, 1992.
• [16] K.F. Man, K.S. Tang, and S. Kwong, “Genetic algorithms: concepts and applications,” IEEE Transactions on Industrial Electronics, Vol. 43, No. 5, 1996, pp. 519–534.
• [17] S.K. Khalsa and Y. Labiche, “An orchestrated survey of available algorithms and tools for combinatorial testing,” in IEEE 25th International Symposium on Software Reliability Engineering (ISSRE). IEEE, 2014, pp. 323–334.
• [18] C.J. Colbourn, M.B. Cohen, and R. Turban, “A deterministic density algorithm for pairwise interaction coverage.” in IASTED Conf. on Software Engineering. Citeseer, 2004, pp. 345–352.
• [19] J. Arshem. TVG download web page. (2009). [Online]. http://sourceforge.net/projects/tvg
• [20] J. Czerwonka, “Pairwise testing in real world: Practical extensions to test case generator,” in PNSQC’06: Proceedings of 24th Pacific Northwest Software Quality Conference, 2006, pp. 419–430.
• [21] Z. Wang, B. Xu, and C. Nie, “Greedy heuristic algorithms to generate variable strength combinatorial test suite,” in The Eighth International Conference on Quality Software. IEEE, 2008, pp. 155–160.
• [22] Z. Wang and H. He, “Generating variable strength covering array for combinatorial software testing with greedy strategy,” Journal of Software, Vol. 8, No. 12, 2013, pp. 3173–3181.
• [23] S.A. Abdullah, Z.H. Soh, and K.Z. Zamli, “Variable-strength interaction for t-way test generation strategy.” International Journal of Advances in Soft Computing & Its Applications, Vol. 5, No. 3, 2013.
• [24] M. Forbes, J. Lawrence, Y. Lei, R.N. Kacker, and D.R. Kuhn, “Refining the in-parameter-order strategy for constructing covering arrays,” Journal of Research of the National Institute of Standards and Technology, Vol. 113, No. 5, 2008, pp. 287–297.
• [25] L. Yu, Y. Lei, R.N. Kacker, and D.R. Kuhn, “ACTS: A combinatorial test generation tool,” in IEEE Sixth International Conference on Software Testing, Verification and Validation (ICST). IEEE, 2013, pp. 370–375.
• [26] S. Ali, L.C. Briand, H. Hemmati, and R.K. Panesar-Walawege, “A systematic review of the application and empirical investigation of search-based test case generation,” IEEE Transactions on Software Engineering,, Vol. 36, No. 6, 2010, pp. 742–762.
• [27] B.J. Garvin, M.B. Cohen, and M.B. Dwyer, “Evaluating improvements to a meta-heuristic search for constrained interaction testing,” Empirical Software Engineering, Vol. 16, No. 1, 2011, pp. 61–102.
• [28] C. Blum and A. Roli, “Metaheuristics in combinatorial optimization: Overview and conceptual comparison,” ACM Computing Surveys (CSUR), Vol. 35, No. 3, 2003, pp. 268–308.
• [29] B. Jenkins. Jenny download web page. (2005). [Online]. http://burtleburtle.net/bob/ math/jenny.html
• [30] T. Shiba, T. Tsuchiya, and T. Kikuno, “Using artificial life techniques to generate test cases for combinatorial testing,” in Proceedings of the 28th Annual International Computer Software and Applications Conference. IEEE, 2004, pp. 72–77.
• [31] X. Chen, Q. Gu, A. Li, and D. Chen, “Variable strength interaction testing with an ant colony system approach,” in APSEC’09. Asia-Pacific Software Engineering Conference. IEEE, 2009, pp. 160–167.
• [32] L. Gonzalez-Hernandez, N. Rangel-Valdez, and J. Torres-Jimenez, “Construction of mixed covering arrays of variable strength using a tabu search approach,” in Combinatorial Optimization and Applications. Springer, 2010, pp. 51–64.
• [33] J.D. McCaffrey, “An empirical study of pairwise test set generation using a genetic algorithm,” in Seventh International Conference on Information Technology: New Generations (ITNG). IEEE, 2010, pp. 992–997.
• [34] P. Flores and Y. Cheon, “PWiseGen: Generating test cases for pairwise testing using genetic algorithms,” in IEEE International Conference on Computer Science and Automation Engineering (CSAE), Vol. 2. IEEE, 2011, pp. 747–752.
• [35] B.S. Ahmed and K.Z. Zamli, “A variable strength interaction test suites generation strategy using particle swarm optimization,” Journal of Systems and Software, Vol. 84, No. 12, 2011, pp. 2171–2185.
• [36] A.R.A. Alsewari and K.Z. Zamli, “Design and implementation of a harmony-search-based variable-strength t-way testing strategy with constraints support,” Information and Software Technology, Vol. 54, No. 6, 2012, pp. 553–568.
• [37] J. LI, D. XING, and Y. ZHAO, “Combinatorial test suite generation of variable strength based on harmony search,” Journal of Network & Information Security, Vol. 4, No. 2, 2013, pp. 177–188.
• [38] X. Chen, Q. Gu, J. Qi, and D. Chen, “Applying particle swarm optimization to pairwise testing,” in IEEE 34th Annual Computer Software and Applications Conference (COMPSAC). IEEE, 2010, pp. 107–116.
• [39] J. Stardom, “Metaheuristics and the search for covering and packing arrays,” Ph.D. dissertation, Simon Fraser University, 2001.
• [40] Genetic Algorithms in Search, Optimization, and Machine Learning, 1st ed. Reading, Mass: Addison-Wesley Professional, Jan. 1989.
• [41] H. Maaranen, K. Miettinen, and M.M. Mäkelä, “Quasi-random initial population for genetic algorithms,” Computers & Mathematics with Applications, Vol. 47, No. 12, 2004, pp. 1885–1895.
• [42] Y.W. Leung and Y. Wang, “An orthogonal genetic algorithm with quantization for global numerical optimization,” IEEE Transactions on Evolutionary Computation, Vol. 5, No. 1, 2001, pp. 41–53.
• [43] H. Maaranen, K. Miettinen, and A. Penttinen, “On initial populations of a genetic algorithm for continuous optimization problems,” Journal of Global Optimization, Vol. 37, No. 3, 2007, pp. 405–436.
• [44] S. Rahnamayan, H.R. Tizhoosh, and M.M. Salama, “A novel population initialization method for accelerating evolutionary algorithms,” Computers & Mathematics with Applications, Vol. 53, No. 10, 2007, pp. 1605–1614.
• [45] H. Wang, Z. Wu, J. Wang, X. Dong, S. Yu, and C. Chen, “A new population initialization method based on space transformation search,” in Fifth International Conference on Natural Computation, Vol. 5. IEEE, 2009, pp. 332–336.
• [46] P. Bansal, S. Sabharwal, S. Malik, V. Arora, and V. Kumar, “An approach to test set generation for pair-wise testing using genetic algorithms,” in Search Based Software Engineering. Springer, 2013, pp. 294–299.
• [47] D. Ortiz-Boyer, C. Hervás-Martínez, and N. García-Pedrajas, “CIXL2: A crossover operator for evolutionary algorithms based on population features.” J. Artif. Intell. Res.(JAIR), Vol. 24, 2005, pp. 1–48.
• [48] S.M. Libelli and P. Alba, “Adaptive mutation in genetic algorithms,” Soft Computing, Vol. 4, No. 2, 2000, pp. 76–80.
• [49] P. Flores. PWiseGen download web page. (2010). [Online]. https://code.google.com/p/pwisegen/