Metaheuristic algorithms for building Covering Arrays: A review

Abstract

Covering Arrays (CA) are mathematical objects used in the functional testing of software components. They enable the testing of all interactions of a given size of input parameters in a procedure, function, or logical unit in general, using the minimum number of test cases. Building CA is a complex task (NP-complete problem) that involves lengthy execution times and high computational loads. The most effective methods for building CAs are algebraic, Greedy, and metaheuristic-based. The latter have reported the best results to date. This paper presents a description of the major contributions made by a selection of different metaheuristics, including simulated annealing, tabu search, genetic algorithms, ant colony algorithms, particle swarm algorithms, and harmony search algorithms. It is worth noting that simulated annealing-based algorithms have evolved as the most competitive, and currently form the state of the art.

Keywords

ant colony optimization, Covering Array, genetic algorithms, harmony search algorithm, metaheuristics, particle swarm optimization, simulated annealing, tabu search

References

• S. Maity, “Software Testing with Budget Constraints,” in Information Technology: New Generations (ITNG), 2012 Ninth International Conference on, Apr. 2012, pp. 258-262. DOI: http://dx.doi.org/10.1109/itng.2012.44. DOI: https://doi.org/10.1109/ITNG.2012.44
• G. J. Myers, C. Sandler, and T. Badgett, The art of software testing, 3rd edition. Hoboken, NJ, USA: John Wiley & Sons, Jan. 2012. DOI: http://dx.doi.org/10.1002/9781119202486. DOI: https://doi.org/10.1002/9781119202486
• N. Changhai and H. Leung, “A Survey of Combinatorial Testing,” ACM Computing Surveys, vol. 43, pp. 1-11, 2011. DOI: http://dx.doi.org/10.1145/1883612.1883618. DOI: https://doi.org/10.1145/1883612.1883618
• J. Yan and J. Zhang, “Backtracking Algorithms and Search Heuristics to Generate Test Suites for Combinatorial Testing,” 30th Annual International Computer Software and Applications Conference (COMPSAC’06), Chicago, IL, 2006, pp. 385-394. DOI: http://dx.doi.org/10.1109/COMPSAC.2006.33. DOI: https://doi.org/10.1109/COMPSAC.2006.33
• H. Ávila George, J. Torres-Jimenez, and V. H. García, Verificación de Covering Arrays: Lambert Academic Publishing, 2010.
• J. Torres-Jimenez and I. Izquierdo-Márquez, “Survey of Covering Arrays,” in Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2013 15th International Symposium on, Sep. 2013, pp. 20-27. DOI: http://dx.doi.org/10.1109/synasc.2013.10. DOI: https://doi.org/10.1109/SYNASC.2013.10
• H. Ávila George, “Constructing Covering Arrays using Parallel Computing and Grid Computing,” Ph.D. dissertation, Departamento de Sistemas Informáticos y Computación, Universitad Politécnica de Valencia, Valencia, Spain, 2012. DOI: http://dx.doi.org/10.4995/thesis/10251/17027. DOI: https://doi.org/10.4995/Thesis/10251/17027
• K. Meagher, “Non-Isomorphic Generation of Covering Arrays,” University of Regina, Tech. Rep., 2002.
• J. Bracho-Rios, J. Torres-Jimenez, and E. Rodriguez-Tello, “A New Backtracking Algorithm for Constructing Binary Covering Arrays of Variable Strength,” in MICAI 2009: Advances in Artificial Intelligence. vol. 5845, A. Aguirre, et al., Eds., ed: Springer Berlin Heidelberg, 2009, pp. 397-407. DOI: http://dx.doi.org/10.1007/978-3-642-05258-3_35. DOI: https://doi.org/10.1007/978-3-642-05258-3_35
• B. Hnich, S. D. Prestwich, E. Selensky, and B. M. Smith, “Constraint Models for the Covering Test Problem,” Constraints, vol. 11 (2-3), pp. 199-219, Jul. 2006. DOI: http://dx.doi.org/10.1007/s10601-006-7094-9. DOI: https://doi.org/10.1007/s10601-006-7094-9
• D. Lopez-Escogido, J. Torres-Jimenez, E. Rodriguez-Tello, and N. Rangel-Valdez, “Strength Two Covering Arrays Construction Using a SAT Representation,” in MICAI 2008: Advances in Artificial Intelligence. vol. 5317, A. Gelbukh and E. Morales, Eds., ed: Springer Berlin Heidelberg, 2008, pp. 44-53. DOI: http://dx.doi.org/10.1007/978-3-540-88636-5_4. DOI: https://doi.org/10.1007/978-3-540-88636-5_4
• J. Torres-Jimenez, I. Izquierdo-Marquez, A. Gonzalez-Gomez, and H. Ávila-George, “A Branch & Bound Algorithm to Derive a Direct Construction for Binary Covering Arrays,” in G. Sidorov and S. Galicia-Haro (Eds.), Advances in Artificial Intelligence and Soft Computing. vol. 9413, pp. 158-177, Springer International Publishing, 2015. DOI: http://dx.doi.org/10.1007/978-3-319-27060-9_13. DOI: https://doi.org/10.1007/978-3-319-27060-9_13
• Y. Lei, R. Kacker, D. R. Kuhn, V. Okun, and J. Lawrence, “IPOG: A General Strategy for T-Way Software Testing,” presented at the Proceedings of the 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems, 2007. DOI: http://dx.doi.org/10.1109/ecbs.2007.47. DOI: https://doi.org/10.1109/ECBS.2007.47
• R. C. Turban, “Algorithms for covering arrays,” Ph.D. dissertation, Arizona State University, 2006.
• J. Zhang, Z. Zhang, and F. Ma, Automatic Generation of Combinatorial Test Data: Springer Publishing Company, Incorporated, 2014. DOI: DOI: http://dx.doi.org/10.1007/978-3-662-43429-1. DOI: https://doi.org/10.1007/978-3-662-43429-1
• G. O. H. Katona, “Two applications (for search theory and truth functions) of Sperner type theorems,” Periodica Mathematica Hungarica, vol. 3 (1-2), pp. 19-26, Mar. 1973. DOI: http://dx.doi.org/10.1007/BF02018457. DOI: https://doi.org/10.1007/BF02018457
• D. J. Kleitman, and J. Spencer, “Families of k-independent sets,” Discrete Mathematics, vol. 6 (3), pp. 255-262, 1973. DOI: http://dx.doi.org/10.1016/0012-365X(73)90098-8. DOI: https://doi.org/10.1016/0012-365X(73)90098-8
• M. A. Chateauneuf, C. J. Colbourn, and D. L. Kreher, “Covering Arrays of Strength Three,” Des Codes and Cryptogr, vol. 16 (3), pp. 235-242, May. 1999. DOI: http://dx.doi.org/10.1023/A:1008379710317. DOI: https://doi.org/10.1023/A:1008379710317
• K. Meagher and B. Stevens, “Group construction of covering arrays,” Journal of Combinatorial Designs, vol. 13 (1), pp. 70-77, Jan. 2005. DOI: http://dx.doi.org/10.1002/jcd.20035. DOI: https://doi.org/10.1002/jcd.20035
• A. Hartman, “Software and Hardware Testing Using Combinatorial Covering Suites,” in M. Golumbic and I.-A. Hartman (Eds.), Graph Theory, Combinatorics and Algorithms. vol. 34, pp. 237-266, ed: Springer US, 2005. DOI: http://dx.doi.org/10.1007/0-387-25036-0_10. DOI: https://doi.org/10.1007/0-387-25036-0_10
• C. J. Colbourn et al., “Products of mixed covering arrays of strength two,” Journal of Combinatorial Designs, vol. 14 (2), pp. 124-138, Mar. 2006. DOI: http://dx.doi.org/10.1002/jcd.20065. DOI: https://doi.org/10.1002/jcd.20065
• C. Colbourn, “Covering arrays from cyclotomy,” Des Codes and Cryptogr, vol. 55 (2-3), pp. 201-219, May. 2010. DOI: http://dx.doi.org/10.1007/s10623-009-9333-8. DOI: https://doi.org/10.1007/s10623-009-9333-8
• R. C. Bryce and C. J. Colbourn, “The density algorithm for pairwise interaction testing,” Softw Test Verif Reliab, vol. 17 (3), pp. 159-182, Sep. 2007. DOI: http://dx.doi.org/10.1002/stvr.365. DOI: https://doi.org/10.1002/stvr.365
• Y. Lei and K.-C. Tai, “In-Parameter-Order: A Test Generation Strategy for Pairwise Testing,” presented at the The 3rd IEEE International Symposium on High-Assurance Systems Engineering, 1998. DOI: http://dx.doi.org/10.1109/HASE.1998.731623. DOI: https://doi.org/10.1109/HASE.1998.731623
• M. Forbes et al., “Refining the in-parameter-order strategy for constructing covering arrays,” Journal of Research of the National Institute of Standards and Technology, vol. 113 (5), pp. 287-297, Sep. 2008. DOI: http://dx.doi.org/10.6028/jres.113.022. DOI: https://doi.org/10.6028/jres.113.022
• A. Calvagna and A. Gargantini, “T-wise combinatorial interaction test suites construction based on coverage inheritance,” Softw Test Verif Reliab, vol. 22 (7), pp. 507-526, Nov. 2012. DOI: http://dx.doi.org/10.1002/stvr.466. DOI: https://doi.org/10.1002/stvr.466
• R. N. Kacker et al., “Combinatorial testing for software: An adaptation of design of experiments,” Measurement, vol. 46 (9), pp. 3745-3752, Nov. 2013. DOI: http://dx.doi.org/10.1016/j.measurement.2013.02.021. DOI: https://doi.org/10.1016/j.measurement.2013.02.021
• F. Glover and M. Laguna, Tabu Search: Kluwer Academic Publishers, 1997. DOI: http://dx.doi.org/10.1007/978-1-4615-6089-0. DOI: https://doi.org/10.1007/978-1-4615-6089-0
• M. Gendreau, “Recent Advances in Tabu Search,” in Essays and Surveys in Metaheuristics. vol. 15, ed: Springer US, 2002, pp. 369-377. DOI: http://dx.doi.org/10.1007/978-1-4615-1507-4_16. DOI: https://doi.org/10.1007/978-1-4615-1507-4_16
• M. Gendreau and J. Y. Potvin, Handbook of Metaheuristics: Springer US, 2010. DOI: http://dx.doi.org/10.1007/978-1-4419-1665-5. DOI: https://doi.org/10.1007/978-1-4419-1665-5
• S. Luke. Essentials of Metaheuristics, 2nd ed. Lulu, 2013.
• M. Dorigo and T. Stützle, Ant Colony Optimization: Bradford Company, 2004. DOI: https://doi.org/10.7551/mitpress/1290.001.0001
• J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Neural Networks, 1995. Proc. IEEE Int. Conf. Neural Netw. on, Nov. 1995, pp. 1942-1948 vol.4. DOI: http://dx.doi.org/10.1109/icnn.1995.488968. DOI: https://doi.org/10.1109/ICNN.1995.488968
• Z. Geem et al., “A New Heuristic Optimization Algorithm: Harmony Search,” SIMULATION, vol. 76, pp. 60-68, 2001. DOI: http://dx.doi.org/10.1177/003754970107600201. DOI: https://doi.org/10.1177/003754970107600201
• M. G. H. Omran and M. Mahdavi, “Global-best harmony search,” Applied Mathematics and Computation, vol. 198 (2), pp. 643-656, May. 2008. DOI: http://dx.doi.org/10.1016/j.amc.2007.09.004. DOI: https://doi.org/10.1016/j.amc.2007.09.004
• S. Kirkpatrick and M. Vecchi, “Optimization by simmulated annealing,” science, vol. 220, pp. 671-680, 1983. DOI: http://dx.doi.org/10.1126/science.220.4598.671. DOI: https://doi.org/10.1126/science.220.4598.671
• M. B. Cohen et al., “Constructing test suites for interaction testing,” presented at the Proceedings of the 25th International Conference on Software Engineering, Portland, Oregon, 2003. DOI: http://dx.doi.org/10.1109/icse.2003.1201186. DOI: https://doi.org/10.1109/ICSE.2003.1201186
• M. B. Cohen et al., “Constructing strength three covering arrays with augmented annealing,” Discrete Mathematics, vol. 308 (13), pp. 2709-2722, Jul. 2008. DOI: http://dx.doi.org/10.1016/j.disc.2006.06.036. DOI: https://doi.org/10.1016/j.disc.2006.06.036
• J. Torres-Jimenez and E. Rodriguez-Tello, “Simulated Annealing for constructing binary covering arrays of variable strength,” in Evolutionary Computation (CEC), 2010 IEEE Congress on, 2010, pp. 1-8. DOI: http://dx.doi.org/10.1109/cec.2010.5586148. DOI: https://doi.org/10.1109/CEC.2010.5586148
• J. Torres-Jimenez and E. Rodriguez-Tello, “New bounds for binary covering arrays using simulated annealing,” Information Sciences, vol. 185 (1), pp. 137-152, Feb. 2012. DOI: http://dx.doi.org/10.1016/j.ins.2011.09.020. DOI: https://doi.org/10.1016/j.ins.2011.09.020
• A. Rodriguez-Cristerna and J. Torres-Jimenez, “A Simulated Annealing with Variable Neighborhood Search Approach to Construct Mixed Covering Arrays,” Electronic Notes in Discrete Mathematics, vol. 39, pp. 249-256, Dec. 2012. DOI: http://dx.doi.org/10.1016/j.endm.2012.10.033. DOI: https://doi.org/10.1016/j.endm.2012.10.033
• A. L. González Hernández, “Un Algoritmo de Optimizacion Combinatoria para la Construccion de Covering Arrays Mixtos de Fuerza Variable,” PhD. dissertation, Laboratorio de Tecnologías de la Información, Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional, 2013.
• A. Rodriguez-Cristerna et al., “Construction of Mixed Covering Arrays Using a Combination of Simulated Annealing and Variable Neighborhood Search,” Electronic Notes in Discrete Mathematics, vol. 47, pp. 109-116, Feb. 2015. DOI: http://dx.doi.org/10.1016/j.endm.2014.11.015. DOI: https://doi.org/10.1016/j.endm.2014.11.015
• J. Torres-Jimenez et al., “A two-stage algorithm for combinatorial testing,” Optimization Letters, pp. 1-13, 2016. DOI: http://dx.doi.org/10.1007/s11590-016-1012-x. DOI: https://doi.org/10.1007/s11590-016-1012-x
• K. J. Nurmela, “Upper bounds for covering arrays by tabu search,” Discrete Applied Mathematics, vol. 138 (1-2), pp. 143-152, Mar. 2004. DOI: http://dx.doi.org/10.1016/S0166-218X(03)00291-9. DOI: https://doi.org/10.1016/S0166-218X(03)00291-9
• R. A. Walker Ii and C. J. Colbourn, “Tabu search for covering arrays using permutation vectors,” Journal of Statistical Planning and Inference, vol. 139 (1), pp. 69-80, Jan. 2009. DOI: http://dx.doi.org/10.1016/j.jspi.2008.05.020. DOI: https://doi.org/10.1016/j.jspi.2008.05.020
• L. Gonzalez-Hernandez et al., “Construction of Mixed Covering Arrays of Variable Strength Using a Tabu Search Approach,” in Combinatorial Optimization and Applications. vol. 6508, W. Wu and O. Daescu, Eds., ed: Springer Berlin Heidelberg, 2010, pp. 51-64. DOI: http://dx.doi.org/10.1007/978-3-642-17458-2_6. DOI: https://doi.org/10.1007/978-3-642-17458-2_6
• L. Gonzalez-Hernandez, “New bounds for mixed covering arrays in t-way testing with uniform strength,” Information and Software Technology, vol. 59, pp. 17-32, Mar. 2015. DOI: http://dx.doi.org/10.1016/j.infsof.2014.10.009. DOI: https://doi.org/10.1016/j.infsof.2014.10.009
• X. Yu and M. Gen. Introduction to Evolutionary Algorithms. Springer London, 2010. DOI: http://dx.doi.org/10.1007/978-1-84996-129-5. DOI: https://doi.org/10.1007/978-1-84996-129-5
• J. Stardom, “Metaheuristics and the Search for Covering and Packing Arrays,” M.S. thesis, Simon Fraser University, 2001.
• E. Rodriguez-Tello and J. Torres-Jimenez, “Memetic Algorithms for Constructing Binary Covering Arrays of Strength Three,” in Artifical Evolution. vol. 5975, P. Collet, et al., Eds., ed: Springer Berlin Heidelberg, 2010, pp. 86-97. DOI: http://dx.doi.org/10.1007/978-3-642-14156-0_8. DOI: https://doi.org/10.1007/978-3-642-14156-0_8
• S. Sabharwal et al., “Construction of t-way covering arrays using genetic algorithm,” International Journal of System Assurance Engineering and Management, pp. 1-11, 2016. DOI: http://dx.doi.org/10.1007/s13198-016-0430-6. DOI: https://doi.org/10.1007/s13198-016-0430-6
• M. Dorigo et al., “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 26 (1), pp. 29-41, Feb. 1996. DOI: http://dx.doi.org/10.1109/3477.484436. DOI: https://doi.org/10.1109/3477.484436
• T. Shiba et al., “Using artificial life techniques to generate test cases for combinatorial testing,” in Computer Software and Applications Conference, 2004. COMPSAC 2004. Proceedings of the 28th Annual International, 2004, pp. 72-77 vol.1. DOI: http://dx.doi.org/10.1109/CMPSAC.2004.1342808. DOI: https://doi.org/10.1109/CMPSAC.2004.1342808
• D. M. Cohen et al., “The Automatic Efficient Test Generator (AETG) system,” in Software Reliability Engineering, 1994. Proceedings., 5th International Symposium on, 1994, pp. 303-309. DOI: http://dx.doi.org/10.1109/issre.1994.341392. DOI: https://doi.org/10.1109/ISSRE.1994.341392
• X. Chen et al., “Building Prioritized Pairwise Interaction Test Suites with Ant Colony Optimization,” in 9th International Conference on Quality Software, Jeju, 2009, pp. 347-352. DOI: http://dx.doi.org/10.1109/QSIC.2009.52. DOI: https://doi.org/10.1109/QSIC.2009.52
• B. S. Ahmed et al., “The development of a particle swarm based optimization strategy for pairwise testing,” Journal of Artificial Intelligence, vol. 4 (2), pp. 156-165, Feb. 2011. DOI: http://dx.doi.org/10.3923/jai.2011.156.165. DOI: https://doi.org/10.3923/jai.2011.156.165
• 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 (12), pp. 2171-2185, Dec. 2011. DOI: http://dx.doi.org/10.1016/j.jss.2011.06.004. DOI: https://doi.org/10.1016/j.jss.2011.06.004
• B. S. Ahmed et al., “Application of Particle Swarm Optimization to uniform and variable strength covering array construction,” Applied Soft Computing, vol. 12 (4), pp. 1330-1347, Apr. 2012. DOI: http://dx.doi.org/10.1016/j.asoc.2011.11.029. DOI: https://doi.org/10.1016/j.asoc.2011.11.029
• T. Mahmoud and B. S. Ahmed, “An efficient strategy for covering array construction with fuzzy logic-based adaptive swarm optimization for software testing use,” Expert Systems with Applications, vol. 42 (22), pp. 8753-8765, Dec. 2015. DOI: http://dx.doi.org/10.1016/j.eswa.2015.07.029. DOI: https://doi.org/10.1016/j.eswa.2015.07.029
• X.-S. Yang, “Harmony Search as a Metaheuristic Algorithm,” in Music-Inspired Harmony Search Algorithm. vol. 191, ed: Springer Berlin Heidelberg, 2009, pp. 1-14. DOI: http://dx.doi.org/10.1007/978-3-642-00185-7_1. DOI: https://doi.org/10.1007/978-3-642-00185-7_1
• A. R. A. Alsewari and K. Z. Zamli, “A harmony search based pairwise sampling strategy for combinatorial testing,” International Journal of the Physical Sciences, vol. 7, pp. 1062-1072, 2012. DOI: http://dx.doi.org/10.5897/IJPS11.1633. DOI: https://doi.org/10.5897/IJPS11.1633
• X. Bao et al., “Combinatorial Test Generation Using Improved Harmony Search Algorithm,” International Journal of Hybrid Information Technology, vol. 8 (9), pp. 121-130, Sep. 2015. DOI: http://dx.doi.org/10.14257/ijhit.2015.8.9.13. DOI: https://doi.org/10.14257/ijhit.2015.8.9.13
• E. K. Burke et al., “Hyper-heuristics: A survey of the state of the art,” Journal of the Operational Research Society, vol. 64 (12), pp. 1695-1724, Dec. 2013. DOI: http://dx.doi.org/10.1057/jors.2013.71. DOI: https://doi.org/10.1057/jors.2013.71
• A. LaTorre et al., “Multiple Offspring Sampling in Large Scale Global Optimization,” in 2012 IEEE Congress on Evolutionary Computation, 2012, pp. 1-8. DOI: http://dx.doi.org/10.1109/CEC.2012.6256611. DOI: https://doi.org/10.1109/CEC.2012.6256611
• P. Kitsos et al., “Exciting FPGA cryptographic Trojans using combinatorial testing,” in 2015 IEEE 26th International Symposium on Software Reliability Engineering (ISSRE), Nov. 2015, pp. 69-76. DOI: http://dx.doi.org/10.1109/issre.2015.7381800. DOI: https://doi.org/10.1109/ISSRE.2015.7381800