Algoritmo metaheurístico para la construcción de arreglos de cobertura mixtos de diferentes niveles de fuerza a usar en el diseño de casos de prueba de software de caja negra
DOI:
https://doi.org/10.17981/ingecuc.18.2.2022.18Palabras clave:
Arreglos de Cobertura, Arreglos de Cobertura Mixtos, Algoritmos Metaheurísticos, Algoritmos Codiciosos, Recocido SimuladoResumen
Introducción— Actualmente, la calidad del software en una característica fundamental para asegurarse un espacio en el mercado global que día a día es más competitivo y exigente. Las pruebas de software permiten a las empresas desarrolladoras de software encontrar y corregir fallos y con ello elevar la calidad de sus productos. El costo de las pruebas hoy se estima en un 50% del costo total del desarrollo de software, por esto se hace necesario encontrar formas menos costosas que garanticen altos niveles de detección de fallos. En este escenario, las pruebas de caja negra tienen un papel fundamental y dentro de estas pruebas los enfoques combinatoriales son una de las mejores opciones. En las pruebas combinatorias se hace necesario que los usuarios probadores (testers) cuenten con una herramienta que les proporcione el menor número de casos de prueba con la mayor cobertura (detección de fallos) de acuerdo con los parámetros del método (procedimiento, función u otro) que desea probar, y este es el objetivo principal de este trabajo.
Objetivo— En este artículo se presenta un algoritmo que soporta la generación de casos de prueba en pruebas de caja negra basado en la creación de Arreglos de Cobertura Mixta (MCA). Estos arreglos permiten generar el menor número de casos de prueba requeridos para probar una unidad de código con la mayor cobertura requerida (mayor posibilidad de detectar fallos). El algoritmo propuesto construye una solución inicial basado en un algoritmo codicioso (greedy) y luego mejora esta solución a través de un proceso iterativo orientado por recocido simulado (algoritmo metaheurístico) y tres formas de definir soluciones vecinas.
Metodología— La investigación se realizó siguiendo el Patrón de Investigación Iterativa propuesto por Pratt. Primero se identificaron los principales problemas reportados en el estado del arte para la construcción de MCA, luego se realizó una revisión de las propuestas de solución a estos problemas. Después se creó un primer algoritmo y luego se fue modificando en forma iterativa este algoritmo, incluyendo y removiendo componentes de acuerdo con resultados experimentales de su funcionamiento. Cuando se obtuvo la versión deseada, se realizó un proceso de afinamiento de parámetros y se comparó con los mejores resultados presentados en la literatura, resultados obtenidos por diferentes algoritmos.
Resultados— El algoritmo propuesto obtiene MCA que son competitivos (en promedio 3 casos de prueba adicionales) frente a los mejores reportados en el estado del arte en un tiempo corto de ejecución, aspecto que es de especial interés para los probadores de software.
Conclusiones— Se confirmó que el enfoque codicioso y metaheurístico basado en recocido simulado es una buena alternativa para la construcción de un MCA. Los algoritmos de construcción de soluciones vecinas son claves para encontrar el MCA requerido y en un menor tiempo de ejecución.
Descargas
Citas
A. Kovačević, “The Top 4 Trends That Will Change Software Development in the 2020s”, IEEE Computer Society, Mar. 2, 2020. [Online]. Available in: https://www.computer.org/publications/tech-news/trends/the-top-4-trends-that-will-change-software-development-in-the-2020s
A. Tripathi, K. Mishra, S. Tiwari, & N. Kumar, “Improved software cost estimation models: A new perspective based on evolution in Dynamic Environment,” J Intell Fuzzy Syst, vol. 35, no. 2, pp. 1707–1720, Jan. 2018. https://doi.org/10.3233/JIFS-169707
H. Wu, C. Nie, F. Kuo, H. Leung, & C. Colbourn, “A Discrete Particle Swarm Optimization for Covering Array Generation,” IEEE Trans Evol Composite, vol. 19, No. 4, pp. 575–591, Aug. 2015. https://doi.org/10.1109/TEVC.2014.2362532
T. Mahmoud & B. Ahmed, “An efficient strategy for covering array construction with fuzzy logic-based adaptive swarm optimization for software testing use,” Expert Syst Appl, vol. 42, no. 22, pp. 8753–8765, Dec. 2015. https://doi.org/10.1016/j.eswa.2015.07.029
J. Timaná-Peña, C. Cobos-Lozada, & J. Torres-Jimenez, “Metaheuristic algorithms for building Covering Arrays A review,” Rev Fac Ing, vol. 25, no. 43, pp. 31–45, Ene. 2016. https://doi.org/10.19053/01211129.v25.n43.2016.5295
J. Timaná, C. Cobos, & J. Torres-Jimenez, “Memetic algorithm for constructing covering arrays of variable strength based on global-best harmony search and simulated annealing,” presented at Mexican International Conference on Artificial Intelligence, MICAI, Guad., MX, 22-27 Oct. 2018. https://doi.org/10.1007/978-3-030-04491-6_2
S. Sabharwal, P. Bansal, & N. Mittal, “Construction of t-way covering arrays using genetic algorithm,” Int J Syst Assur Eng Manag, vol. 8, no. 2, pp. 264–274, Mar. 2016. https://doi.org/10.1007/s13198-016-0430-6
X. Yang, Nature-inspired Metaheuristic Algorithms, 2 ed., Cambr., UK: Luniver Press, 2010.
R. Walker & C. Colbourn, “Tabu search for covering arrays using permutation vectors,” J Stat Plan Inference, vol. 139, no. 1, pp. 69–80, Jan., 2009. https://doi.org/10.1016/j.jspi.2008.05.020
S. Esfandyari & V. Rafe, “A tuned version of genetic algorithm for efficient test suite generation in interactive t-way testing strategy,” Inf Softw Technol, vol. 94, pp. 165–185, Feb. 2018. https://doi.org/10.1016/j.infsof.2017.10.007
G. Demiroz & C. Yilmaz, “Using simulated annealing for computing cost-aware covering arrays,” Appl Soft Comput, vol. 49, pp. 1129–1144, Dec. 2016. https://doi.org/10.1016/j.asoc.2016.08.022
X. Chen, Q. Gu, A. Li, & D. Chen, “Variable strength interaction testing with an ant colony system approach,” presented at Asia-Pacific Software Engineering Conference, APSEC, PG, MY, 1-3 Dec. 2009. https://doi.org/10.1109/APSEC.2009.18
X. Bao, S. Liu, N. Zhang, & M. Dong, “Combinatorial Test Generation Using Improved Harmony Search Algorithm,” Int J Hybrid Inf Technol, vol. 8, no. 9, pp. 121–130, Sep. 2015. https://doi.org/10.14257/ijhit.2015.8.9.13
Y. Zhang, L. Cai, & W. Ji, “Combinatorial testing data generation based on bird swarm algorithm,” presented at 2nd International Conference on System Reliability and Safety, ICSRS, MIL, IT, Jan. 2018. https://doi.org/10.1109/ICSRS.2017.8272871
B. Ahmed, T. Abdulsamad & M. Potrus, ‘Achievement of minimized combinatorial test suite for configuration-aware software functional testing using the Cuckoo Search algorithm,’ Inf Softw Technol, vol. 66, pp. 13–29, Oct. 2015. https://doi.org/10.1016/j.infsof.2015.05.005
Y. Wang, M. Zhou, X. Song, M. Gu & J. Sun, “Constructing Cost-Aware Functional Test-Suites Using Nested Differential Evolution Algorithm,” IEEE Trans Evol Comput, vol. 22, no. 3, pp. 334–346, Jun. 2018. https://doi.org/10.1109/TEVC.2017.2747638
K. Zamli, B. Alkazemi & G. Kendall, “A Tabu Search hyper-heuristic strategy for t-way test suite generation,” Appl Soft Comput, vol. 44, pp. 57–74, Jul. 2016. https://doi.org/10.1016/j.asoc.2016.03.021
J. Torres-Jimenez, H. Avila-George & Izquierdo-Marquez, “A two-stage algorithm for combinatorial testing,” Optim Lett, vol. 11, no. 3, pp. 457–469, Feb. 2016. https://doi.org/10.1007/s11590-016-1012-x
I. Izquierdo-Marquez, J. Torres-Jiménez, B. Acevedo-Juárez & H. Avila-George, “A greedy-metaheuristic 3-stage approach to construct covering arrays,” Inf Sci, vol. 460-461, pp. 172–189, Sep. 2018. https://doi.org/10.1016/j.ins.2018.05.047
J. Torres-Jiménez & I. Izquierdo-Márquez, “A Simulated Annealing Algorithm to Construct Covering Perfect Hash Families,” Math Probl Eng, pp. 1–15, Jan. 2018. https://doi.org/10.1155/2018/1860673
M. Cohen, C. Colbourn & A. Ling, “Constructing strength three covering arrays with augmented annealing,” Discrete Math, vol. 308, no. 13, pp. 2709–2722, Jun. 2003. https://doi.org/10.1016/j.disc.2006.06.036
J. Torres-Jimenez & J. Perez-Torres, “A greedy algorithm to construct covering arrays using a graph representation,” Info Sci, vol. 477, pp. 234–245, Mar. 2019. https://doi.org/10.1016/j.ins.2018.10.048
J. Torres-Jiménez & I. Izquierdo-Márquez, “Improved covering arrays using covering perfect hash families with groups of restricted entries,” Appl Math Composite, vol. 369, pp. 1–10, Mar. 2020. https://doi.org/10.1016/j.amc.2019.124826
M. Martin, “SOLID: los 5 principios que te ayudarán a desarrollar software de calidad,” profile, 22 Nov. 2018 [Online]. Available in: https://profile.es/blog/principios-solid-desarrollo-software-calidad/
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2022 INGE CUC
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
Los artículos publicados son de exclusiva responsabilidad de sus autores y no reflejan necesariamente las opiniones del comité editorial.
La Revista INGE CUC respeta los derechos morales de sus autores, los cuales ceden al comité editorial los derechos patrimoniales del material publicado. A su vez, los autores informan que el presente trabajo es inédito y no ha sido publicado anteriormente.
Todos los artículos están bajo una Licencia Creative Commons Atribución-NoComercial-SinDerivadas 4.0 Internacional.
English
Español (España)
