Skip to main navigation menu Skip to main content Skip to site footer

Vol. 25 No. 43 (2016)

Papers

Metaheuristic algorithms for building Covering Arrays: A review

https://doi.org/10.19053/01211129.v25.n43.2016.5295

Published 2016-09-01

  • Jimena Adriana Timaná-Peña
    • ,
  • Carlos Alberto Cobos-Lozada
    • ,
  • Jose Torres-Jimenez

Jimena Adriana Timaná-Peña
Universidad del Cauca (Popayán-Cauca, Colombia).

Carlos Alberto Cobos-Lozada
Universidad del Cauca (Popayán-Cauca, Colombia).

Jose Torres-Jimenez
Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional (Ciudad Victoria-Tamaulipas, México).

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

PDF HTML

References

  1. 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
  2. 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
  3. 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
  4. 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
  5. H. Ávila George, J. Torres-Jimenez, and V. H. García, Verificación de Covering Arrays: Lambert Academic Publishing, 2010.
  6. 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
  7. 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
  8. K. Meagher, “Non-Isomorphic Generation of Covering Arrays,” University of Regina, Tech. Rep., 2002.
  9. 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
  10. 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
  11. 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
  12. 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
  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
  14. R. C. Turban, “Algorithms for covering arrays,” Ph.D. dissertation, Arizona State University, 2006.
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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
  30. 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
  31. S. Luke. Essentials of Metaheuristics, 2nd ed. Lulu, 2013.
  32. M. Dorigo and T. Stützle, Ant Colony Optimization: Bradford Company, 2004. DOI: https://doi.org/10.7551/mitpress/1290.001.0001
  33. 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
  34. 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
  35. 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
  36. 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
  37. 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
  38. 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
  39. 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
  40. 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
  41. 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
  42. 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.
  43. 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
  44. 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
  45. 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
  46. 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
  47. 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
  48. 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
  49. 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
  50. J. Stardom, “Metaheuristics and the Search for Covering and Packing Arrays,” M.S. thesis, Simon Fraser University, 2001.
  51. 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
  52. 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
  53. 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
  54. 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
  55. 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
  56. 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
  57. 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
  58. 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
  59. 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
  60. 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
  61. 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
  62. 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
  63. 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
  64. 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
  65. 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
  66. 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

Downloads

Download data is not yet available.

Most read articles by the same author(s)