Algoritmo genético multiobjetivo para selección de casos de tests Multiobjective genetic algorithm for test cases selection Trabajo de Fin de Máster Curso 2020–2021 Autor Carlos Martín Testillano Director Mercedes García Merayo Máster en Ingeniería Informática Facultad de Informática Universidad Complutense de Madrid Algoritmo genético multiobjetivo para selección de casos de tests Multiobjective genetic algorithm for test cases selection Trabajo de Fin de Máster en Ingeniería Informática Departamento de Sistemas Informáticos y Computación Autor Carlos Martín Testillano Director Mercedes García Merayo Convocatoria: Junio 2021 Calificación: 10 Máster en Ingeniería Informática Facultad de Informática Universidad Complutense de Madrid 8 de Julio 2021 Dedicatoria A mi familia, por mostrarme el camino y ser siempre el mejor ejemplo. v Agradecimientos Gracias a Mercedes y a Miguel, por su esfuerzo y dedicación, y por ayudarme a seguir aprendiendo. A mis padres, por su apoyo incondicional, su eterna confianza y su constante exigencia. A mi hermana, por ser siempre mi mejor amiga. A mis abuelos, por hacerme sentir orgulloso de mis logros. Y a Arancha, por creer y ayudarme a creer en mí. vii Resumen El testing de software es una de las principales técnicas utilizadas para validar la co- rrección de un sistema, y consiste en definir una serie de pruebas o tests para determinar si el sistema bajo prueba cumple la especificación. Sin embargo, no es posible definir to- das las pruebas posibles para realizar esta comprobación, por lo que surge la necesidad de hacer una selección de casos de test. En este trabajo proponemos un marco de selección de casos de test, con el apoyo de la técnica de mutation testing. Para realizar la selección del subconjunto de casos de test se ha diseñado un algoritmo genético multiobjetivo que trata de optimizar la solución en base a dos factores: maximizar el mutation score, que en nuestro caso permite distinguir entre mutantes además de la especificación, y minimizar el número total de entradas necesarias para el subconjunto de tests. Combinando estas técnicas hemos conseguido obtener un conjunto de soluciones que mejoran a las obtenidas por medio de los algoritmos genéticos y el mutation score tradicionales, y además hemos logrado determinar que la aplicación de la heurística de cruce en un punto en el algoritmo genético reporta soluciones sensiblemente mejores. Palabras clave Testing de máquinas de estados finitos, Mutation testing, Algoritmos genéticos, Algoritmos multiobjetivo, NSGA-II. ix Abstract Software testing is one of the main techniques used to validate the correctness of a system, and consists of defining a series of tests to determine whether the system under test meets the specification. However, it is not viable to define all the possible tests to perform this verification, so the need to make a selection of test cases arises. In this thesis we propose a test case selection framework, applying the mutation testing technique. To perform the test case subset selection we rely on a multi-objective genetic algorithm that seeks to optimize the solution based on two factors: maximizing the mutation score, which in our case allows to distinguish between mutants as well as the specification, and minimizing the total number of inputs required for the subset of tests. By combining these techniques we have managed to obtain a set of solutions that improve those obtained by means of the traditional techniques on genetic algorithms and the mutation score, and we have also managed to determine that the application of the one-point crossover heuristic in the genetic algorithm yields significantly better solutions. Keywords Finite state machine testing, Mutation testing, Genetic algorithms, Multi-objective algo- rithms, NSGA-II. xi Índice 1. Introducción 1 1.1. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3. Plan de trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Preliminares 5 2.1. Mutation Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. Algoritmos genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3. Algoritmos Multiobjetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3. Diseño del algoritmo 19 3.1. Especificaciones, Mutantes y Tests . . . . . . . . . . . . . . . . . . . . . . . 19 3.2. Objetivos considerados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3. Algoritmo genético multiobjetivo . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4. Consideraciones finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4. Experimentos 33 xiii 4.1. Descripción de los experimentos . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2. Evaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2.1. Resultados para reemplazo elitista usando NSGA-II . . . . . . . . . 36 4.2.2. Comparación de heurísticas usando reemplazo elitista con NSGA-II . 39 5. Conclusiones y Trabajo Futuro 43 6. Introduction 45 6.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.2. Objetives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.3. Work plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.4. Document structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7. Conclusions and Future Work 49 Bibliografía 51 Índice de figuras 2.1. Esquema principal algoritmo genético . . . . . . . . . . . . . . . . . . . . . . 10 2.2. Regiones de dominancia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3. Frontera de Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4. Cálculo de la distancia de concentración . . . . . . . . . . . . . . . . . . . . 15 3.1. Ejemplos de máquinas de estados finitos . . . . . . . . . . . . . . . . . . . . 20 3.2. Ejemplos de mutaciones de máquinas de estados finitos . . . . . . . . . . . . 22 3.3. Truncamiento en 25 % . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.4. Cruce en un punto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.5. Cruce uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.6. Mutación por agregación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.7. Mutación por sustitución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.8. Reemplazo elitista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.9. Proceso NSGA-II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.1. Comparación NSGA-II vs. reeemplazo directo para Espc I. Torneo-Uniforme- Agregación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2. Comparación NSGA-II vs. reemplazo directo para Espc I. Truncamiento-Un punto-Sustitución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 xv 4.3. Comparación NSGA-II vs. reemplazo directo para Espc II. Torneo-Uniforme- Agregación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4. Comparación NSGA-II vs. reemplazo directo para Espc II. Truncamiento- Un punto-Sustitución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.5. Comparación heurísticas NSGA-II para Espc I. . . . . . . . . . . . . . . . . 40 4.6. Comparación heurísticas NSGA-II para Espc II. . . . . . . . . . . . . . . . 41 Índice de tablas 2.1. Ejemplo de diferenciadores y d-vectores . . . . . . . . . . . . . . . . . . . . 7 2.2. Comparativa de mutation scores . . . . . . . . . . . . . . . . . . . . . . . . 8 xvii Capı́tulo 1 Introducción En esta memoria de trabajo de fin de máster, se describe un problema de optimización a resolver, y se muestra la metodología, el desarrollo y los avances realizados para poder afrontarlo, al igual que se estudiará la validez de la propuesta. 1.1. Motivación El testing de software es una de las principales técnicas utilizadas para validar la co- rrección de un sistema, es decir, para comprobar que no presenta fallos (Ammann y Offutt, 2016). Normalmente, el comportamiento esperado de los sistemas se da en forma de pruebas (o tests), que se utilizan para determinar si el sistema bajo prueba cumple la especificación, o si por el contrario, contiene errores. No obstante, uno de los principales inconvenientes que tiene el testing de software es que el número de tests necesarios para chequear todos los comportamientos del sistema puede ser infinito. Por ello surge la necesidad de seleccio- nar un número suficiente de pruebas que detecten la mayor parte de errores en base a un determinado criterio. Con el fin de reducir el número de casos de test que se van a aplicar para comprobar la validez de un sistema, se debe seleccionar un subconjunto de todos los posibles. Para deter- minar dicho subconjunto, es necesario establecer una métrica que nos permita determinar la calidad de cada test, con el fin de filtrar y mantener únicamente los mejores en el sub- conjunto finalmente seleccionado. Para determinar qué conjuntos de tests son los mejores se utilizan técnicas de priorización de casos de test, que sirven para ordenarlos en base a 1 2 Capítulo 1. Introducción una propiedad deseable, como su capacidad para detectar errores (Catal y Mishra, 2013). En esta línea, la técnica de mutation testing es interesante para evaluar la efectividad de un conjunto de tests (King y Offutt, 1991; Offutt et al., 1996; Hierons et al., 2010; Jia y Harman, 2011; Lou et al., 2015; Shin et al., 2019). Para ello se crean sistemas similares al sistema bajo prueba aplicando pequeñas modificaciones individuales sobre este último, como puede ser eliminar fragmentos de código, intercambiar operadores aritméticos o in- tercambiar operadores relacionales. Mediante la aplicación de los tests a los mutantes y el sistema original se puede determinar aquellos con mayor capacidad de detección de errores, es decir, los que ponen de manifiesto más diferencias en el comportamiento de los mutantes respecto al del sistema original. La idea es que si un conjunto de tests distingue al sistema bajo prueba de otros sistemas similares a él pero con fallos, entonces puede ser un buen conjunto para determinar errores en dicho sistema. De este modo se puede llevar a cabo una ordenación de los casos de test basada en dicha capacidad de detección de errores. La aproximación que habitualmente se utiliza en mutation testing para determinar la calidad de un conjunto de tests está basada en cuántos errores es capaz de detectar. Sin embargo, recientemente ha surgido una nueva propuesta que además del número de errores detectados también contempla y fomenta la diversidad de casos de test (Shin et al., 2018, 2019). En este caso se valora más la capacidad del conjunto de tests para distinguir mutantes que para distinguir dichos mutantes del programa original. De esta forma, se priorizan los tests que antes ayudan a distinguir entre todos los mutantes. En este trabajo, se propone un algoritmo genético para obtener un buen subconjunto de tests a partir de un conjunto de tests inicial. Comenzando con una población aleatoria, esta técnica evoluciona hacia soluciones óptimas. Este trabajo supone una extensión de una propuesta previa para selección de casos de tests en el ámbito de máquinas de estados finitos (Benito-Parejo y Merayo, 2020). En este trabajo se pretende optimizar la calidad de los casos de test en base a su capacidad de detección de errores y su diversidad a la hora de detectarlos, así como la longitud de los mismos, es decir, el número de entradas que han de aplicarse para su ejecución. Para ello, se aplica un algoritmo avanzado de optimización multiobjetivo (Deb et al., 2002) que permite hacer una priorización óptima de conjuntos de casos de test en base a los dos objetivos mencionados. Este algoritmo ha sido completamente implementado y se presentan los resultados obtenidos de su aplicación a distintas especificaciones y conjuntos de tests. 1.2. Objetivos 3 1.2. Objetivos El principal objetivo de este trabajo es aplicar y combinar nuevas técnicas de mutation testing y algoritmos genéticos para el diseño y la implementación de un marco de selección de casos de test. Este marco deberá guiar la minimización del número de entradas que necesita el subconjunto de casos de test a la vez que se maximiza el número de mutantes diferentes a los que dichos tests matan. Para ello se han definido los siguientes subobjetivos: En primer lugar se va a aplicar la técnica del criterio de distinción de mutantes, con el fin de obtener un subconjunto de tests más óptimo que el que se consigue con el mutation score tradicional, que determina la calidad del conjunto únicamente comparando los mutantes con la especificación. De esta forma se determina que un subconjunto de casos de test es mejor que otro, es decir, tiene un mutation score mayor, cuantos más mutantes diferentes distinga. Por otro lado, vamos utilizar este mutation score junto con el número de entradas que necesita el subconjunto de casos de test para determinar la calidad de dicho subconjunto. Para ello vamos a aplicar el algoritmo multiobjetivo NSGA-II en el método de reemplazo del algoritmo genético, con el fin de poder ordenar en base a estos objetivos las soluciones parciales en cada generación, de tal forma que siempre se mantengan las que más optimizan dichos objetivos. Por último, vamos a comprobar la efectividad de esta nueva combinación, determi- nando si el uso del criterio de distinción de mutantes para determinar la calidad de un subconjunto de tests, unido a la aplicación del algoritmo genético multiobjetivo NSGA-II para obtener el mejor subconjunto de casos de test, reporta soluciones más óptimas que los métodos tradicionales. 1.3. Plan de trabajo Para alcanzar el objetivo principal del trabajo, ha sido necesario gestionar las tareas a realizar de manera conveniente. Para ello, se ha dividido el trabajo en diferentes fases de diseño, desarrollo y depuración, y se ha iterado cíclicamente por todas ellas, revisitando las fases necesarias con el fin de alcanzar los mejores resultados posibles. Las fases que se 4 Capítulo 1. Introducción han definido son: 1. Fase de familiarización y entendimiento a) Familiarización con mutation testing. b) Familiarización con algoritmos genéticos. c) Familiarización con el criterio de distinción de mutantes. d) Familiarización con el algoritmo NSGA-II. 2. Fase de diseño e implementación a) Diseño e implementación del distinguishing mutation score. b) Diseño e implementación del criterio de reemplazo elitista usando NSGA-II. c) Adaptación de la estructura del sistema para aplicar los nuevos criterios. 3. Fase de depuración a) Depuración y optimización del algoritmo de distinguishing mutation score. b) Depuración y optimización de los algoritmos NSGA-II. c) Depuración y optimización de la estructura general del sistema. 4. Pruebas y resultados a) Diseño de las pruebas. b) Ejecución de las pruebas e interpretación de los resultados. 1.4. Estructura del documento El presente documento se estructura de la siguiente forma: En el capítulo 2 se hace una introducción a los conceptos teóricos sobre los que se basa el trabajo. En el capítulo 3 se describe la propuesta para la selección de casos de test. En el capítulo 4 se definen y muestran los resultados de los experimentos ejecutados. En el capítulo 5 se exponen las conclusiones extraídas del trabajo y las posibles ampliaciones sobre el trabajo desarrollado. Capı́tulo 2 Preliminares Antes de entrar en detalle en la descripción del trabajo desarrollado, es necesario intro- ducir los conceptos sobre los que se sustenta la propuesta. En esta sección se introducen específicamente la técnica de mutation testing, los algoritmos genéticos y los algoritmos multiobjetivo. 2.1. Mutation Testing El principio general en el que se basa la técnica de mutation testing es la inyección de fallos en los programas originales mediante simples cambios sintácticos para crear un conjunto de programas defectuosos llamados mutantes, cada uno de los cuales contiene una única mutación. Estos fallos se basan en lo que se conoce como la hipótesis del pro- gramador competente (DeMillo et al., 1978), es decir, corresponden a pequeños errores que programadores experimentados pueden cometer. Dado que el número de fallos potenciales es muy elevado, la generación de los mutantes se basa en un subconjunto de fallos. Las mutaciones a aplicar se describen mediante los operadores de mutación. Para evaluar la calidad de un conjunto de tests, se ejecutan los tests contra el sistema bajo prueba y los mutantes. Si el resultado de la ejecución de un mutante difiere del resultado de la ejecución del programa original para alguno de los tests, el fallo que ha sido introducido en el mutante habrá sido detectado. Cuando esto ocurre, se dice que el mutante está muerto. Un mutante se llama equivalente si es semánticamente equivalente al programa original. Los mutantes duplicados son equivalentes entre sí pero no al programa 5 6 Capítulo 2. Preliminares original. La idea es que si un conjunto de tests es capaz de distinguir el comportamiento de los mutantes y del programa original, también será bueno detectando errores. La calidad del conjunto de tests viene determinada tradicionalmente por su mutation score, que corresponde a la ratio del número de mutantes que mata y el número total de mutantes no equivalentes o duplicados. Intuitivamente, los buenos conjuntos de tests son los que matan a la mayoría de los mutantes. Definición 1 Sea T un conjunto de tests para un programa p y sea Mp un conjunto de mutantes de p. El mutation score de T para Mp se define como: mscore(T,Mp) = Mk p Mneq p donde Mk p es el número de mutantes matados por algún test de T y Mneq p es el conjunto de mutantes no equivalentes. Recientemente, se ha propuesto una nueva medida más exigente para determinar la adecuación de un conjunto de tests denominada distinguishing mutation score (Shin et al., 2018) que tiene en cuenta la diversidad de los mutantes. Esta métrica no solo considera el número de mutantes matados sino también la capacidad de los tests para distinguir los mutantes, favoreciendo los conjuntos con un mayor número de tests distinguiendo mutantes e incrementando con ello la posibilidad de incrementar la detección de fallos. Los conjuntos de tests evaluados en base al distinguishing mutation score presentan una mayor calidad en términos de efectividad a la hora de detectar fallos que la de aquellos basados en el criterio tradicional (Shin et al., 2019). En este trabajo se utilizará esta nueva medida en el proceso de selección de casos de tests para determinar la capacidad de detección de errores. Definición 2 Sea P un conjunto de programas que incluye el programa bajo test, po, y sus mutantes. Sea T un conjunto de casos de tests. Un diferenciador de test, d : T ×P ×P → {0, 1}, es una función tal que para todo t ∈ T, px, py ∈ P se define como: d(t, px, py) =  1 si los comportamientos de px y py para t son diferentes 0 e.o.c. Un d-vector es una función dv : Tn × P × P → {0, 1}n tal que para todo px, py ∈ P , Ts = {t1, . . . , tn} ⊂ T se define como: 2.1. Mutation Testing 7 Tests dv(TS ,m1, po) dv(TS ,m2, po) dv(TS ,m3, po) dv(TS ,m4, po) t1 1 1 1 1 t2 0 1 1 0 t3 0 0 1 1 t4 0 1 1 0 Tabla 2.1: Ejemplo de diferenciadores y d-vectores dv(Ts, px, py) = 〈d(t1, px, py), . . . , d(tn, px, py)〉 Un mutante m ∈ P es matado por un caso de test t ∈ T si d(t, po,m) 6= 0 y es matado por un conjunto de tests Ts cuando se cumple dv(Ts, po,m) 6= 〈0, . . . , 0〉 Un test t ∈ T distingue a dos mutantes mx,my ∈ P cuando se cumple d(t, po,mx) 6= d(t, po,my) Del mismo modo, mx y my son distinguidos por Ts cuando se cumple dv(Ts, po,mx) 6= dv(Ts, po,my) Un diferenciador de test indica si los comportamientos de dos programas son o no diferentes cuando se ejecutan contra un mismo test. El d-vector de dos programas para un conjunto de tests devuelve un vector compuesto por los diferenciadores correspondientes a dichos programas y cada uno de los casos de test del conjunto. Ejemplo 1 Consideremos la Tabla 2.1. Cada celda indica si un test ti mata a un mutante mj y cada columna el d-vector correspondiente al conjunto de tests TS = {t1, t2, t3, t4}. Por ejemplo, dv(t1,m1, po) es 1, lo que indica que t1 mata al mutante m1 y el d-vector de m1 para TS es 〈1, 0, 0, 0〉. El test t1 distingue a todos los mutantes del programa original, mientras que t2 y t4 distinguen solo a los mutantes m2 y m3, y t3 a los mutantes m3 y m4. Si consideramos el conjunto de tests TS, se puede observar que distingue a todos los mutantes ya que ninguno de los d-vectores son iguales. 8 Capítulo 2. Preliminares Conjuntos de tests Conjuntos de mutantes indistinguibles mscore dscore TS1 = {t4} {po,m1,m4}, {m2,m3} 0,5 0,4 TS2 = {t3, t4} {po,m1}, {m2}, {m3}, {m4} 0,75 0,8 TS3 = {t1, t2} {po}, {m1,m4}, {m2,m3} 1 0,6 TS4 = {t1, t2, t3} {po}, {m1}, {m2}, {m3}, {m4} 1 1 Tabla 2.2: Comparativa de mutation scores Como ya hemos indicado, en base a este criterio de distinguibilidad de mutantes se ha definido un nuevo mutation score. Dos mutantes se distinguen por un conjunto de tests cuando sus d-vectores son diferentes, mientras que los mutantes que tienen idénticos d- vectores no pueden distinguirse con el correspondiente conjunto de tests. Por tanto, el número de d-vectores distintos corresponde al número de mutantes que son distinguibles por el conjunto de tests. En base a este número se define el distinguishing mutation score. Definición 3 Sea po un programa original, Mp0 un conjunto de mutantes de po y T un conjunto de tests. Se define el distinguishing mutation score de T para Mp0 como: dscore(T,Mp0) = |{dv(T, po,m) : m ∈M ′p0}| |M ′p0 | donde M ′p0 = Mp0 ∪ {po}. Ejemplo 2 La Tabla 2.2 presenta una comparativa de la aplicación del mutation score tradicional y el distinguishing mutation score. La segunda columna presenta los conjuntos de mutantes indistinguibles por los conjuntos de tests correspondientes en base a los resultados reflejados en la Tabla 2.1. Por ejemplo, si consideramos TS3 tenemos tres conjuntos. Por una parte, los mutantes m1 y m4 son indistinguibles entre sí ya que presentan el mismo d-vector, 〈1, 0〉. Lo mismo ocurre con los mutantes m2 y m3 que tienen asociado el d- vector 〈1, 1〉. Por último, el programa original po puede distinguirse de cualquier mutante, por lo que aparece en un conjunto diferente. Sin embargo, si consideramos el conjunto de tests TS2 = {t3, t4}, este conjunto de tests permite distinguir los mutantes m2, m3 y m4, mientras que el mutante m1 no se puede distinguir de po con este conjunto de tests. En lo referente a la efectividad de los conjuntos de tests vemos como el distinguishing mutation score es más estricto que el mutation score tradicional a la hora de realizar una 2.2. Algoritmos genéticos 9 valoración. Los conjuntos de tests TS3 y TS4 alcanzan un mscore de 1. TS1 separa los mutantes en dos conjuntos, los mutantes que son matados y los que no, por lo que el dscore correspondiente es 2 5 = 0,4. Los conjuntos de tests TS2, TS3 and TS4 incrementan este valor por la inclusión de casos de tests que distinguen más mutantes. El conjunto TS4 distingue todos los mutantes del programa original, permitiendo alcanzar un dscore de 5 5 = 1. 2.2. Algoritmos genéticos Los algoritmos genéticos son métodos estocásticos de búsqueda heurística adaptativa basada en la genética de poblaciones y en la selección natural (Goldberg, 1989; Sivanan- dam y Deepa, 2008). Es un método que destaca cuando se busca una aproximación lo suficientemente buena a la solución de problemas cuya solución óptima necesita un enfo- que combinatorio para calcular todos los posibles candidatos. Al estar basado en la biología, los términos que se utilizan para referirse a ellos son también extraídos de esta rama de la ciencia. En primer lugar, los algoritmos genéticos trabajan sobre un conjunto de soluciones a las que se denomina cromosomas o individuos. Este conjunto de cromosomas se conoce como población, y su tamaño no varía a lo largo de toda la ejecución. La idea de los algo- ritmos genéticos es realizar cambios en ciertos cromosomas, que provoquen la evolución de la población, obteniendo finalmente un individuo que aproxime lo suficientemente bien la solución óptima (Mirjalili, 2019). Una iteración completa de un algoritmo genético se conoce como generación. En cada generación, se utiliza el fitness o aptitud de cada cromosoma como heurística que guía la evolución del algoritmo genético. Con la evaluación del fitness, se puede determinar cuán bueno es un individuo con respecto al objetivo. A continuación, describimos el funciona- miento general de un algoritmo genético, siguiendo el flujo de la Figura 2.1. La primera fase en un algoritmo genético es la inicialización de la población, donde se genera la semilla que evolucionará las generaciones marcadas. Es importante que esta población inicial sea lo suficientemente diversa para que los elementos puedan explorar adecuadamente el espacio de soluciones. Una inicialización muy focalizada puede provocar que las soluciones obtenidas estén sesgadas y varíen cerca de un óptimo local en vez del mejor global. Posteriormente, se seleccionan los cromosomas para la generación siguiente de forma 10 Capítulo 2. Preliminares Figura 2.1: Esquema principal algoritmo genético probabilística en función del fitness. En general, para la fase de selección, los métodos que se pueden implementar no dependen del problema, y son más conocidos. El objetivo es muestrear en la población los mejores elementos, lo que se consigue premiando a los mejores cromosomas con más relevancia en sus apariciones de cada evolución a la vez que se penaliza a los peores incluso evitando cualquier aparición. Para la elección de un subconjunto de individuos de una población podemos clasificar los métodos según el grado de aleatoriedad: Muestreo directo: se toma un subconjunto de individuos de la población siguiendo un criterio fijo, como por ejemplo los mejores, los peores, unos cromosomas concretos, etc. Muestreo aleatorio simple o equiprobable: se asigna la misma probabilidad de formar parte de la muestra a todos los elementos de la población y se hace una selección aleatoria. Muestreos estocásticos: se asignan probabilidades de selección o puntuaciones a los elementos de la población base en función (directa o indirecta) de su aptitud. A continuación, en la fase de cruce, dos individuos (padres) se emparejan generando un nuevo par de individuos (hijos) con información genética combinada de los primeros. El objetivo es que con dicha información de ambos padres, los hijos sean más aptos y por lo tanto representen una solución mejor. No obstante, también se podría obtener una descendencia menos apta, que es interesante considerar en próximas generaciones, ya que 2.3. Algoritmos Multiobjetivo 11 puede aumentar la diversidad y evitar una concentración de individuos en un espacio alejado del óptimo. Principalmente, durante las fases de cruce y la siguiente, de mutación, se produce la evolución del algoritmo genético, realizando la mayor parte de cambios en la población. Estos cambios son los que conllevan una mayor exploración de las soluciones, lo que en general permite obtener una aproximación lo suficientemente buena. Por ello, la fase de mutación, se centra en realizar pequeños cambios sobre un individuo de forma esporádica. Esta mutación puede ayudar a la población global a ampliar la búsqueda de soluciones, ya que añade información genética adicional no contemplada en la semilla inicial. En proble- mas complicados, es común que la población inicial no contenga información genética que la solución óptima necesite. Es por ello que estos pequeños cambios, que no deben alterar en grandes cantidades la evolución del algoritmo genético, son importantes para no acotar la solución a un óptimo local. Finalmente, se produce la fase de reemplazo, que fija los cambios producidos, y actualiza la población con los hijos, con frecuencia manteniendo a algún individuo padre. El proceso de evolución se repite hasta que se cumpla la condición final. 2.3. Algoritmos Multiobjetivo Tradicionalmente, los algoritmos genéticos se han utilizado en problemas de optimi- zación de un solo objetivo. Sin embargo, son muchos los problemas que tienen múltiples funciones objetivo, como es el caso de este trabajo. Para resolver estos problemas multiobje- tivo se ha tenido que buscar una transformación válida que permita que sean tratados como problemas un único objetivo a optimizar, lo cual en ocasiones distorsiona los resultados. El propósito de los problemas de optimización multiobjetivo es encontrar la solución más compensada entre las posibles (Abraham y Jain, 2005), ya que la optimización de todos los objetivos involucrados suele estar en conflicto y en otro caso podrían optimizarse uno a uno. Habitualmente estos problemas no tienen una única solución, sino un conjunto de soluciones que presentan diferentes nivles de compensación entra los distintos objetivos. Una técnica frecuente es considerar como solución un conjunto Pareto optimal de solu- ciones (Pareto, 1964). A continuación, definimos las nociones principales de dominancia, solución Pareto óptima y frontera de Pareto. 12 Capítulo 2. Preliminares Figura 2.2: Regiones de dominancia Definición 4 Sea P un problema de optimización de n objetivos, S el conjunto de solu- ciones posibles para P , x, y ∈ S y χ = (χ1, χ2, . . . , χn), γ = (γ1, γ2, . . . , γn) los valores de los objetivos para las soluciones x e y, respectivamente. Se dice que la solución x domina a y denotado por x ≺ y si se cumplen las siguientes condiciones: 1. χi ≤ γi, ∀i ∈ {1, 2, ..., n} 2. ∃i ∈ {1, 2, ..., n} tal que χi < γi Una vez se aplica a una solución el concepto de dominancia de Pareto, se definen cuatro regiones del plano (ver Figura 2.2) con las cuales se relaciona de manera diferente la solución: x domina todas las soluciones y contenidas en la región 1 ya que se cumplen ambas condiciones de dominancia. x es dominada por todas las soluciones y de la región 3, ya que se cumplen las dos condiciones de dominancia de forma inversa, todo y domina a x. x es incomparable con las soluciones y contenidas en las regiones 2 y 4, ya que no se cumplen las dos condiciones de dominancia en ningún sentido x no domina a ningún y ni ningún y domina a x. Definición 5 Sea S un conjunto de soluciones y x ∈ S. Decimos que x es Pareto óptima 2.3. Algoritmos Multiobjetivo 13 Figura 2.3: Frontera de Pareto si y sólo si no existe una solución y ∈ S tal que y domine a x. Llamamos conjunto de Pareto a X = {xi | xi es Pareto óptima} ⊂ S. Definición 6 Sea X = {x1, . . . , xk} un conjunto de Pareto. Llamamos frontera de Pareto al conjunto Ψ = {χ1, . . . , χk} de los valores de los objetivos para las soluciones de X. La Figura 2.3 muestra los puntos de frontera de Pareto en un problema de minimización de dos objetivos. En ella, además de los puntos no dominados entre sí en la frontera, se puede observar que los puntos no pertenecientes a ésta no son dominados necesariamente por todos los puntos de la frontera, sino que son dominados por al menos uno. NSGA-II A lo largo de los años, especialmente durante la última década, se han propuesto una gran variedad de algoritmos evolutivos para problemas de optimización multiobjetivo (Zitz- ler et al., 2004; Coello, 2006). La principal ventaja de utilizar estos algoritmos para los problemas multi-objetivo es su capacidad para encontrar soluciones Pareto óptimas des- de la primera iteración. Ya que los algoritmos evolutivos trabajan con una población de soluciones, éstos se pueden adaptar para avanzar mejorando las soluciones Pareto óptimas. El algoritmo NSGA (por sus siglas en inglés - Nondominated Sorting Genetic Al- gorithm) fue una de las primeras propuestas de algoritmo genético de ordenación no- dominante (Srinivas y Deb, 1994). No obstante, desde su aparición, se encontraron una 14 Capítulo 2. Preliminares serie de problemas relacionados con la complejidad computacional del algoritmo de orde- nación para conjuntos de gran tamaño; la ausencia de elitismo, que provoca una ejecución menos eficiente y una solución menos óptima; y la necesidad de adaptar el algoritmo espe- cíficamente a cada problema. En este trabajo se ha utilizado una versión mejorada de este algoritmo denominada NSGA-II (Deb et al., 2002), que soluciona en parte los problemas de la primera versión. A continuación se explicarán los conceptos principales del algoritmo NSGA-II que se han aplicado en este trabajo. Fast non-dominated sort El Algoritmo 1 detalla el pseudocódigo necesario para llevar a cabo esta clasificación en fronteras de un conjunto de soluciones S. En primer lugar se estudian todas las soluciones, S, para determinar los diferentes nive- les de dominancia o fronteras. Inicialmente, para cada solución p se calculan dos variables (lineas 3-11): Un contador de dominancia np, que almacena el número de soluciones que dominan a la solución p. Un conjunto Sp de soluciones que son dominadas por p. Todas las soluciones que se encuentren en la primera frontera de no-dominancia (F1) tendrán un valor np = 0 (lineas 12-15). Para determinar la siguiente frontera, se recorre el conjunto de soluciones de la primera frontera, F1. Para cada solución p de la frontera, se recorre su conjunto de soluciones dominadas, Sp, y para cada solución q se reduce el valor de su contador de dominancia en 1. Si en este punto el valor de nq es 0, entonces la solución q se incluye en el conjunto Q, que almacena la siguiente frontera de no-dominancia. Este proceso se repite después para todos los elementos en Q para identificar la tercera frontera, y continúa hasta que todas las fronteras hayan sido identificadas (lineas 18-30). Esta generación de fronteras nos permite diferenciar y ordenar valores de los objetivos en distintos niveles. Sin embargo, en el caso de los elementos no dominados entre sí, es decir 2.3. Algoritmos Multiobjetivo 15 Figura 2.4: Cálculo de la distancia de concentración aquellos que pertenecen a una misma frontera, necesitamos utilizar el concepto de distancia de concentración y un operador de comparación de soluciones basado en las fronteras y dichas distancias. Crowding distance Para calcular la concentración de las soluciones que rodean a un individuo de la po- blación se calcula la distancia normalizada de los puntos vecinos de este individuo en cada objetivo. Este valor de distancia de concentración idistance, llamado crowding distance, sir- ve como estimación del perímetro de un cuboide formado por los vecinos más cercanos (ver Figura 2.4). La idea es poder ordenar los puntos clave del conjunto para aumentar la información que las soluciones contienen. Para realizar el cálculo de la distancia de concentración para los elementos de una frontera F , mostrado en el Algoritmo 2, primero es necesario ordenar las soluciones en base a cada uno de los objetivos (linea 6). Una vez ordenados, a las soluciones extremas (la primera y la última) se les asigna una distancia infinita, ya que tienen únicamente un vecino, y son puntos críticos a considerar (lineas 7-8). Para el resto de soluciones intermedias, el cómputo de la distancia se hace tomando el valor absoluto de la diferencia de los valores en el objetivo actual de dos soluciones adyacentes normalizada entre el espacio total que ocupa el objetivo (lineas 9-11). Este cálculo se ejecuta para todos los objetivos, y la distancia final asignada a la solución es la suma de todas las distancias independientes de cada objetivo. 16 Capítulo 2. Preliminares Crowded comparison operator Para conseguir que el resultado del algoritmo sea una frontera Pareto-óptima unifor- memente distribuida, se define un operador de comparación (≺n), el crowded-comparison operator, que se utilizará como criterio de selección. Asumimos que cada individuo i de la población tiene los siguientes atributos: 1. rango de no-dominancia, irank, obtenido tras ejecutar el algoritmo de ordenación, y 2. distancia de concentración, idistance, obtenida al calcular la estimación de concentra- ción. Usando ambos atributos, se define el orden parcial ≺n como i ≺n j si (irank < jrank ∨ (irank = jrank ∧ idistance > jdistance)) Esto es, entre dos soluciones con un rango de no-dominancia (frontera) diferente, se selecciona la que tiene un menor rango. Si ambas soluciones se encuentran en la misma frontera, se selecciona la que está en una zona de menor concentración. De este modo, podemos ordenar y comparar los elementos del conjunto de soluciones que consideremos sin necesidad de una transformación de los múltiples objetivos a un único valor, con la consecuente pérdida de expresión de algún objetivo. 2.3. Algoritmos Multiobjetivo 17 Algoritmo 1: Fast-non-dominated-sort Input: S 1 F1 := ∅; 2 foreach p ∈ S do 3 Sp := ∅; 4 np := 0; 5 foreach q ∈ S do 6 if p ≺ q then 7 Sp := Sp ∪ {q}; 8 else if q ≺ p then 9 np := np + 1; 10 end 11 end 12 if np = 0 then 13 prank := 1; 14 F1 := F1 ∪ {p}; 15 end 16 end 17 i := 1; 18 while Fi 6= ∅ do 19 Q := ∅; 20 foreach p ∈ Fi do 21 foreach q ∈ Sp do 22 nq := nq − 1; 23 if nq = 0 then 24 qrank := i+ 1; 25 Q := Q ∪ {q}; 26 end 27 end 28 end 29 i := i+ 1; 30 Fi := Q; 31 end 18 Capítulo 2. Preliminares Algoritmo 2: Crowding-distance-assignment Input: F 1 l := |F |; 2 foreach i ∈ F do 3 I[i]distance := 0; 4 end 5 foreach objective m do 6 I := sort(I,m); 7 I[1]distance :=∞; 8 I[l]distance :=∞; 9 for i := 2 to (l − 1) do 10 I[i]distance := I[i]distance + (I[i+ 1].m− I[i− 1].m)/(fmax m − fmin m ); 11 end 12 end Capı́tulo 3 Diseño del algoritmo Una vez introducidos los conceptos teóricos en los que se va a basar el presente trabajo, en este capítulo se detalla el marco de selección de casos de tests que se propone. En esta propuesta se considera que se dispone de una representación de la especificación del sistema bajo prueba junto con un conjunto de mutantes de la misma y un conjunto de tests que podríamos aplicar a este sistema. El objetivo es seleccionar un subconjunto de tests que detecte el mayor número de mutantes distintos a la vez que se minimiza el número de entradas que deben ser aplicadas para su ejecución. Para ello se ha diseñado un algoritmo genético multiobjetivo basado en los conceptos del algoritmo NSGA-II y el criterio de distinción de mutantes previamente introducido. 3.1. Especificaciones, Mutantes y Tests Antes de entrar en detalle en el diseño e implementación de la solución, se introducen tanto las máquinas de estados finitos como los operadores de mutación y tests que se han considerado en este trabajo. Máquinas de Estados Finitos En esta propuesta se considera que la especificación del sistema viene dada por una máquina de estados finitos. Una máquina de estados finitos (o FSM por sus siglas en inglés - Finite States Machine) 19 20 Capítulo 3. Diseño del algoritmo es un modelo computacional que se utiliza para simular lógica secuencial. Están compuestas por un conjunto de estados y transiciones entre ellos, que se ejecutan en función de las entradas que recibe la máquina en cada estado, produciendo una salida. Definición 7 Una máquina de estados finitos es una tuplaM = (S, I,O, Tr, sin) donde S es un conjunto finito de estados, I es el conjunto de acciones de entrada, O es el conjunto de acciones de salida, Tr es el conjunto de transiciones entre estados y sin ∈ S es el estado inicial. A su vez, una transición t ∈ Tr es una tupla (s, s′, i, o) donde s, s′ ∈ S son los estados inicial y final de la transición, respectivamente, i ∈ I es la acción de entrada y o ∈ O es la acción de salida. Una máquina de estados finitosM es completa si para todo s ∈ S e i ∈ I existen s′ ∈ S y o ∈ O tales que (s, s′, i, o) ∈ Tr; es decir, se especifica el comportamiento de la máquina para todas las posibles entradas. Asimismo,M es determinista si para todo s ∈ S e i ∈ I, existe una única transición (s, s′, i, o) que pertenece a Tr. Figura 3.1: Ejemplos de máquinas de estados finitos Gráficamente, las máquinas de estados finitos se suelen representar mediante un gra- fo dirigido en el que los nodos representan los estados y las aristas corresponden a las transiciones. Las aristas se etiquetan con las acciones de entrada y salida. Ejemplo 3 En la Figura 3.1 se presentan tres máquinas de estados finitos. La primera de ellas, Figura 3.1(a), es determinista y completa. Sin embargo, la que aparece en la Figura 3.1(b) no es determinista debido a que hay dos transiciones de salida desde el estado s0 etiquetadas con la entrada i. Por último, la máquina representada en la Figura 3.1(c) 3.1. Especificaciones, Mutantes y Tests 21 no es completa ya que s2 no tiene asociada ninguna transición de salida etiquetada con la entrada i2. En este trabajo sólo se considerarán máquinas de estados finitos deterministas y com- pletas. Es decir, en cada estado de la máquina todas las entradas son aceptadas y sólo existe una evolución posible. Esta restricción representa el comportamiento habitual de los programas ya que, normalmente, son deterministas y reaccionan a cualquier entrada. Las máquinas de estados finitos se utilizarán para representar tanto las especificaciones de los sistemas como los mutantes que se generen a partir de ellas. A continuación se definen formalmente las mutaciones que se consideran en este trabajo, así como el formato de los tests que se aplicarán. Operadores de mutación Los mutantes se generan alterando la especificación, para lo que existen una serie de reglas de transformación que definen cómo se pueden hacer estos cambios. Estas reglas se conocen como operadores de mutación. Tradicionalmente, para llevar a cabo estas modificaciones, se han considerado operado- res aritméticos, lógicos, relacionales o de inserción unitaria, entre otros. En nuestro caso, al trabajar con máquinas de estados finitos, es necesario definir un conjunto de operadores de mutación acorde con este formalismo. Tomando la definición de máquina de estados finitos que se ha hecho anteriormente, las variaciones de la especificación se pueden producir en dos puntos: las transiciones y las salidas. Una transición es mutada modificando el estado final de dicha transición. Las mutaciones de salida consisten en sustituir la salida asociada a una transición. Nótese que los mutantes obtenidos por la aplicación de estos operadores de mutación son deterministas y completos. Definición 8 Sea M = (S, I,O, Tr, sin) una FSM. Se dice que otra máquina de estados finitosM′ = (S, I,O, Tr′, sin) es mutante deM si los conjuntos de transiciones Tr y Tr′ son iguales salvo por una única transición. Esta mutación se puede producir cambiando una transición (s, s′, i, o) ∈ Tr por (s, s′, i, o′) ∈ Tr′, donde o′ ∈ O y o 6= o′, o bien (s, s′′, i, o) ∈ Tr′, donde s′′ ∈ S y s′ 6= s′′. 22 Capítulo 3. Diseño del algoritmo Se dice que un mutante es equivalente cuando semánticamente es igual a la especi- ficación. Un mutante duplicado es semánticamente equivalente a otro mutante pero no necesariamente a la especificación. Figura 3.2: Ejemplos de mutaciones de máquinas de estados finitos Ejemplo 4 Consideremos la máquina de estados finitos en la Figura 3.2 (a), en la que s0 es el estado inicial. En las Figuras 3.2 (b) y 3.2 (c) se muestran dos posibles mutantes: el cambio que introduce el primero es en el estado final de la transición (s1, s2, i, o2) que pasa a ser el estado s1, mientras que en el segundo la modificación se produce en la salida de dicha transición, sustituyendo o2 por o4. Tests Un test representa una secuencia de entradas a aplicar al sistema bajo prueba y las salidas que deberían ser observadas. Tras aplicar una entrada, se comprueba si la salida correspondiente es la esperada o no. Definición 9 SeaM = (S, I,O, Tr, sin) una máquina de estados finitos. Un test o prueba para M es una tupla σ = (σin, σout) donde σin ∈ I∗ es una secuencia de entradas y σout ∈ O∗ es la secuencia de salidas que produceM al aplicar σin. Sean t = (σin, σout) un test para M y M′ un mutante de M. Se dice que M′ pasa t si al aplicar σin a M′, este produce σout como salida; en caso contrario, decimos que M′ falla t, o de otra forma, que t mata aM′. Ejemplo 5 Consideremos los mutantes de las Figuras 3.2 (b) y (c), y los tests t1 = (i, o1), t2 = (ii, o1o2) y t3 = (iii, o1o2o3) para la especificación que aparece en la Figura 3.2 (a). 3.2. Objetivos considerados 23 El mutante que aparece en la Figura 3.2 (b) pasa t1 y t2, mientras que t3 lo mata. En el caso del mutante de la Figura 3.2 (c), pasa t1 y es matado por t2 y t3. 3.2. Objetivos considerados Como ya se ha indicado, en esta propuesta se considera la optimización de dos objeti- vos. En primer lugar la minimización del número de entradas que deben ser aplicadas para ejecutar el conjunto de tests seleccionado. En segundo lugar, la maximización del distin- gushing mutation score de dichos tests para el conjunto de mutantes considerado. Hay que indicar que para poder alinear ambos objetivos en el algoritmo propuesto, el segundo valor ha sido modificado, de modo que si un conjunto de tests tiene un mutation score ms, en la implementación se considera 1−ms. Una de las principales innovaciones de este trabajo ha sido la consideración de un criterio de evaluación mucho más estricto que el mutation score tradicional a la hora de determinar la calidad de cada posible solución, ya que éste que no considera la similitud entre los distintos mutantes. Con esta aproximación se ha pretendido conseguir una mejora significativa de la calidad de los resultados a la hora de aplicar los criterios de selección y reemplazo del algoritmo genético en la población de conjuntos de tests. El cálculo de la valoración asociada a cada solución potencial se basa en considerar los tests que conforman dicha solución, y comparar los resultados obtenidos de la aplicación de dichos tests al conjunto de mutantes considerado. Esta comparación tiene en cuenta dos factores: Los tests que matan a cada mutante. Los mutantes que son detectados o matados por exactamente los mismos tests. El Algoritmo 3 muestra el pseudocódigo del proceso de calculo del distinguishing mu- tation score para un conjunto de mutantes M de una especificaciónM y un conjunto de tests T . El array distV ec almacenará los d-vectores de la especificación y de cada uno de los mutantes (lineas 2-4). Después se procede al cálculo de conjuntos de mutantes distin- guibles. Para ello se comparan el d-vector de cada mutante con el del resto de los mutantes (lineas 6-12). 24 Capítulo 3. Diseño del algoritmo Algoritmo 3: Distinguishing-mutation-score Input:M,M, T 1 distV ec := [0, . . . , 0]; 2 foreach m ∈M ∪ {M} do 3 distV ec[m] := dv(T,M,m); 4 end 5 numDscore := 1; 6 Maux := ∅; 7 foreach m ∈M do 8 Maux := Maux ∪ {m}; 9 foreach m′ ∈M\Maux do 10 if distingV ec[m] 6= distV ec[m′] ∧ distV ec[m] 6= distV ec[M] then 11 numDscore+ +; 12 end 13 end 14 dscore := numDscore/(|M |+ 1); 3.3. Algoritmo genético multiobjetivo En esta sección se van a describir cada uno de los componentes considerados en el diseño del algoritmo genético propuesto. Población Los cromosomas o individuos representan una posible solución del problema a resol- ver. En nuestro caso, dicho problema es obtener un buen subconjunto de tests. Por ello, cada individuo está compuesto por un subconjunto del conjunto inicial de tests que se implementa como una lista. Inicialización Como primer paso en todo algoritmo genético, es necesario inicializar la población sobre la que se trabajará. En este caso se ha diseñado una incialización incremental, que 3.3. Algoritmo genético multiobjetivo 25 proporciona una gran variedad de cromosomas, cada uno con un número diferente de tests y entradas, lo cuál supone un alto grado de diversidad. Ya que cada cromosoma se genera de manera aleatoria, habrá algunos con un elevado número de entradas y otros con un número muy bajo, pero a lo largo de la ejecución del algoritmo genético se consigue una combinación de ellos para alcanzar un mejor resultado final, es decir, un conjunto de individuos cuyos tests tengan una relación entre el mutation score y el número de inputs más óptimo. Selección Con el fin de obtener los mejores resultados al final de la ejecución sin aumentar ex- ponencialmente en cada generación el tamaño de la población, es necesario determinar los individuos que se mantendrán de cara a las siguientes iteraciones. En este caso se se- leccionan los mejores individuos de la población en cuanto a los objetivos que se están considerando. Para determinar qué cromosomas son los seleccionados existe una gran variedad de métodos (ruleta, torneo, rango lineal, truncamiento, restos, estocástico universal, etc.). A continuación se enumeran los criterios de selección que se han utilizado en esta propuesta: Truncamiento: se trata del método más elitista. Los individuos se ordenan en base a los objetivos a optimizar (en nuestro caso se busca minimizar tanto el mutation score como el número de entradas del conjunto de tests) y se seleccionan los mejores. El número de individuos seleccionados corresponde a un porcentaje, habitualmente entre el 10 % y el 50 %. Estos individuos se replicarán en la proporción indicada en la siguiente generación para que se mantenga el tamaño de la población original. De esta forma, si se selecciona el 25 % de los individuos, estos se replicarán cuatro veces, y, si es el 50 %, se duplicarán. Torneo: en esta técnica de selección se agrupan aleatoriamente los individuos, habi- tualmente en grupos de dos o tres cromosomas cada uno, y se elige uno de ellos para la próxima generación. Existen dos formas de determinar cuál de los individuos es finalmente seleccionado: determinista, que escoge siempre el que domina al resto en base a los objetivos que se utilizan, y probabilístico, que genera un número aleatorio entre 0 y 1 y, si es mayor que un parámetro fijado inicialmente para todo el proceso 26 Capítulo 3. Diseño del algoritmo Figura 3.3: Truncamiento en 25 % evolutivo, se escoge el mejor individuo, y en caso contrario se toma el menos apto. Cruce Para asegurar la evolución entre iteraciones de un algoritmo genético, combinamos los mejores cromosomas con el fin de obtener mejores resultados generales. Los operadores de cruce que usamos actúan sobre parejas de individuos y generan otro par de individuos que combinan características de ambos progenitores. En esta propuesta se utilizan los siguientes operadores: Cruce en un punto: se selecciona un punto de manera aleatoria que dividirá ambos individuos en dos partes. Los individuos resultantes se obtienen al intercambiar las segundas partes de ambos individuos. En el algoritmo propuesto el cruce se hace seleccionando un subconjunto de tests de cada cromosoma. Los nuevos individuos se obtienen intercambiando los subconjuntos de tests seleccionados. Figura 3.4: Cruce en un punto Cruce uniforme: cada test de un individuo es intercambiado con el correspondiente del otro individuo que participa en el cruce en función de una probabilidad preesta- 3.3. Algoritmo genético multiobjetivo 27 blecida. De esta forma, los subconjuntos de tests de los hijos son una combinación de aquellos de los padres. Figura 3.5: Cruce uniforme Mutación Con el fin de dar completitud a la población, y puesto que los cromosomas iniciales de la población pueden no haber contemplado todas las variaciones en los subconjuntos de tests, es conveniente modificar esta población con algunos ligeros cambios, de tal forma que se generen individuos nuevos potencialmente mejores a los existentes. Esta modificación se realiza sobre los individuos independientes, cambiando únicamente alguno de sus tests. En nuestro caso se pueden aplicar dos métodos para llevar a cabo la mutación: Agregación: está dirigida a conjuntos no completos, ya que se basa en incluir un nuevo gen al cromosoma original, en nuestro caso, un nuevo test aleatorio al subconjunto de tests. Figura 3.6: Mutación por agregación Sustitución: en este caso se produce una modificación de un test ya existente en el cromosoma por otro nuevo de manera aleatoria. Reemplazo El último paso en los algoritmos genéticos consiste en sustituir la población inicial por la nueva. En este caso se consideran dos métodos: 28 Capítulo 3. Diseño del algoritmo Figura 3.7: Mutación por sustitución Reemplazo directo: en este caso se sustituye la antigua población por nueva pobla- ción generada. Se trata del método más rápido ya que para su ejecución se reduce significativamente el número de operaciones necesarias. Reemplazo elitista con NSGA-II: en este caso, para determinar la calidad de cada una de las soluciones se realiza el análisis detallado en la Seccion 2.3 en relación a los dos objetivos del problema. Con ello se consigue ordenar todos los tests en función de los dos objetivos considerados, de tal forma que se mantienen aquellos individuos que obtienen una mejor puntuación conjunta. A continuación se detalla este proceso de reemplazo. Reemplazo elitista con NSGA-II en detalle Como ya hemos indicado, el algoritmo NSGA-II lo hemos aplicado a la fase de reemplazo dentro del algoritmo genético, concretamente adaptando el reemplazo elitista tradicional. Por medio del reemplazo elitista se permite mantener en la población la mejor solución parcial, sustituyendo la peor porción de la población inicial por el mejor conjunto de cromosomas de la nueva generación. Si bien el resultado es mejor que el obtenido por medio del reemplazo directo, esta opción requiere de más carga computacional al tener que ordenar tanto la población inicial como la de la nueva generación y necesitar comparar todos los individuos de cada una. En nuestro problema, se ha decidido aplicar las nociones del algoritmo NSGA-II en la fase de reemplazo del algoritmo genético, adaptando la versión tradicional de éste para aplicar las nociones del algoritmo multiobjetivo. De esta forma, se garantiza una evolución más rápida hacia un conjunto de soluciones buenas al remplazar el subconjunto de peores soluciones por uno que incluye las mejores una vez ejecutados los pasos de selección, cruce y mutación del algoritmo genético. Para llevar a cabo este tipo de reemplazo en el caso de nuestro algoritmo multiobjetivo 3.4. Consideraciones finales 29 Figura 3.8: Reemplazo elitista se consideran, conceptualmente, unos ejes de coordenadas en el que cada eje representa cada uno de los objetivos utilizados (distinguishing mutation score y número de entradas). Mediante esta representación se consigue identificar, dentro de la población total, cuándo un individuo domina a otro, ya que se encontrará más cerca de uno o ambos ejes de coor- denadas. De esta forma se identifican las fronteras de dominancia de todos los individuos. El Algoritmo 4 presenta esta técnica de reemplazo. En cada iteración, se consideran la población a ser reemplazada P y los descendientes considerados Q. En primer lugar se genera el conjunto de fronteras para la unión de ambas poblaciones, lo que asegura el elitismo. A continuación se va creando la nueva generación Pnext incluyendo los individuos que se encuentran en la fronteras más dominantes, comenzando por la mejor y continuando con las siguientes en base a su ranking, mientras no se supere el tamaño de la población establecido para cada generación. En el momento en el que no se puedan incluir todos los individuos de una frontera, se ordenan las soluciones de dicha frontera usando el crow- ded comparison operator y se eligen las mejores hasta completar el número máximo de individuos de la nueva generación. La Figura 3.9 muestra gráficamente este proceso. 3.4. Consideraciones finales Mediante la combinación de estas técnicas y conceptos, sa ha diseñado el marco de selección de casos de test propuesto en primera instancia. Se ha desarrollado una herra- mienta que implementa el algoritmo genético y todas las heurísticas aquí descritas, al igual que la computación del distinguishing mutation score que se aplica para la valoración de los conjuntos de tests. 30 Capítulo 3. Diseño del algoritmo Algoritmo 4: NSGA-elitist-replacement Input: P,Q 1 R := P ∪Q; 2 F :=Fast-non-dominated-sort(R); 3 Pnext := ∅; 4 i := 1; 5 while (|Pnext|+ |Fi| ≤ |P |) do 6 crowding-distance-assignment(Fi); 7 Pnext := Pnext ∪ Fi; 8 i = i+ 1; 9 end 10 Sort(Fi,≺n); 11 Pnext := Pnext ∪ Fi[1 : (|P | − |Pnext|]; A continuación, exponemos los resultados obtenidos de la aplicación de las diferentes heurísticas entre sí así como de los que se obtienen mediante la aplicación del algoritmo NSGA-II en el método de reemplazo. La propuesta ha sido completamente implementada para su automatización y evalua- ción. El código fuente se puede consultar en el siguiente repositorio en GitHub: https: //github.com/ctesti/TFM. https://github.com/ctesti/TFM https://github.com/ctesti/TFM 3.4. Consideraciones finales 31 Figura 3.9: Proceso NSGA-II Capı́tulo 4 Experimentos En este capítulo se presentan los resultados obtenidos de los experimentos llevados a cabo para evaluar la aplicabilidad de la propuesta. Por un lado, se comparará la evolución de los resultados del algoritmo genético utilizando el método de reemplazo elitista NSGA- II, con el fin de identificar la validez y efectividad de este nuevo método, con los obtenidos por medio del método de reemplazo directo sobre la misma población. Por otro lado, se compararán todas las combinaciones posibles de los métodos de los algoritmos genéticos implementados con el fin de determinar cual de ellas es la más adecuada para nuestro problema: encontrar un subconjunto de casos de test que, con el menor número de entradas, detecte el mayor número de fallos posible. 4.1. Descripción de los experimentos Los experimentos se han dividido en dos fases. En la primera fase se han llevado a cabo aquellos experimentos enfocados a comprobar la efectividad de la adaptación del algoritmo NSGA-II al método de reemplazo. En una segunda fase se han realizado los experimentos orientados a la identificación de la combinación de métodos que mejores resultados arroja. Ambas fases de experimentos se han llevado a cabo sobre las mismas especificaciones y conjuntos de mutantes. Hemos trabajado con 9 especificaciones, variando entre los 10 y 40 estados. En relación a los mutantes, se han generado todos los que se pueden obtener aplicando los operadores de mutación previamente definidos. Para la especificación más pequeña, con 10 transiciones y 4 entradas y salidas, se ha trabajado con 400 mutantes, 33 34 Capítulo 4. Experimentos mientras que para la especificación más grande, con 40 estados y 8 entradas y salidas, se han utilizado 12,800 mutantes. Adicionalmente, todos los experimentos ejecutados se han llevado a cabo utilizando la misma parametrización: Una población de 75 individuos. Un máximo de 15 generaciones. Un ratio de 0,8 para 3 participantes en la selección por torneo. Una probabilidad de cruce de 0,75. Una probabilidad de 0,1 para la mutación. Un ratio de elitismo de 0,2 para el reemplazo. Con respecto a las heurísticas utilizadas en el algoritmo genético, se han combinado las más frecuentes de cada método, centrándonos principalmente en las diferencias entre el reemplazo directo y el reemplazo elitista con NSGA-II. De este modo, se han realizado pruebas combinando cada uno de los dos métodos de selección (torneo y truncamiento), cruce (uniforme y en un punto) y mutación (agregación y sustitución), ejecutados todos ellos para ambos tipos de reemplazo. El objetivo del primer conjunto de experimentos es determinar si el uso del algoritmo NSGA-II en el método de reemplazo del algoritmo genético supone una mejora con respec- to al método trivial de reemplazo directo. Para ello se va a utilizar la misma semilla inicial para producir el mismo número de generaciones, con los mismos parámetros e iguales es- pecificaciones. La comparación se va a llevar a cabo modificando únicamente el método de reemplazo, de tal forma que los métodos restantes del algoritmo se mantienen. Especí- ficamente, estos métodos corresponden a torneo para selección, uniforme para el método de cruce y agregación para mutación. Además, debido a que en nuestra implementación la inicialización de la población se realiza de manera incremental y aleatoria, tanto en el caso del reemplazo directo como del reemplazo elitista con NSGA-II, se ha utilizado la misma semilla inicial de cromosomas. De esta manera conseguiremos comparar objetivamente los resultados entre un método de reemplazo y otro. 4.2. Evaluación 35 En relación al segundo conjunto de experimentos, el objetivo es detectar qué combina- ción de heurísticas en cada uno de los métodos del algoritmo genético es la más óptima. Para ello se han determinado todas las combinaciones posibles de heurísticas y se han ejecutado. De esta forma se obtienen los conjuntos de valores que permiten detectar qué combinación da mejores resultados, es decir, la que permite alcanzar el distinguishing mutation score más alto con el menor número de inputs posible. 4.2. Evaluación Cabe destacar que, en nuestro caso, estamos considerando dos objetivos en lugar de uno, por lo que determinar cuándo una solución es mejor que otra no es trivial. Esto se debe a que una solución puede comportarse mejor que otra en un objetivo, pero tener un peor resultado en el otro. Por este motivo, en lugar de obtener como solución al problema un único individuo, se obtiene un conjunto de soluciones. Estas soluciones son las que componen la primera frontera, ya que todas ellas son incomparables entre sí (al comportarse mejor en un objetivo y peor en otro), pero también son mejores que aquellas que están en otra frontera, ya que al menos la igualan en uno de los objetivos y la mejoran en el otro. No obstante, si bien el fin de este trabajo es encontrar soluciones que se comporten sufi- cientemente bien en ambos objetivos, sería posible determinar cuál de todas las soluciones de este conjunto es mejor que las demás. Para ello se podrían ponderar los objetivos, de tal forma que de la combinación de ambos se pudiese extraer un valor único que combinase ambos, pero esto debería hacerse en función de las necesidades del problema. Los resultados obtenidos se van a mostrar en una serie de gráficas en las cuáles se muestran las soluciones pertenecientes a las fronteras relevantes en cada caso. En estas gráficas, el eje vertical indicará el número de entradas que tienen los subconjuntos de tests de cada solución, y el eje horizontal indicará el distinguishing mutation score de cada subconjunto de tests. No obstante, se debe indicar que el valor del distinguishing mutation score se ha adaptado para maximizarlo, de tal forma que la visualización de los resultados sea más intuitiva. Por este motivo no hablaremos de fronteras refiriéndonos a las gráficas, sino de soluciones, ya que en caso de hablar de fronteras deberíamos mostrar las soluciones invertidas, con una pendiente negativa. Adicionalmente, en estas gráficas se incluye un individuo que contiene todos los tests 36 Capítulo 4. Experimentos Figura 4.1: Comparación NSGA-II vs. reeemplazo directo para Espc I. Torneo-Uniforme- Agregación posibles, lo cual supone que también tiene los máximos valores posibles en relación a ambos objetivos. Estos valores son deterministas, ya que dependen exclusivamente de los ficheros de prueba, por lo que en a su vez sirven para comparar entre distintas ejecuciones. Además, este individuo sirve de referencia ya que optimiza ambos objetivos, por lo que facilitará la evaluación a la hora de visualizar los resultados, al poder determinar los límites en cuanto a la minimización y maximización de cada uno de ellos. 4.2.1. Resultados para reemplazo elitista usando NSGA-II En primer lugar, con el primer conjunto de experimentos se ha comprobado si la adap- tación del algoritmo NSGA-II como heurística en el método de reemplazo en un algoritmo genético supone una mejora con respecto a otras heurísticas. Se ha podido observar que esto es así, ya que los resultados obtenidos mediante el uso de este método son efectiva- mente mejores que los obtenidos tanto por medio del método de reemplazo directo como utilizando el método de reemplazo elitista tradicional. En primer lugar, antes de entrar en el detalle de los resultados, indicar que se ha podido observar como las soluciones obtenidas aplicando el reemplazo directo y el reemplazo elitis- ta tradicional son muy similares. Si bien existe alguna mejora en relación al distinguishing mutation score, no es significativa. Por este motivo, se mostrarán únicamente los resultados 4.2. Evaluación 37 Figura 4.2: Comparación NSGA-II vs. reemplazo directo para Espc I. Truncamiento-Un punto-Sustitución obtenidos con el reemplazo directo para facilitar la interpretación de las gráficas, conside- rando siempre que las conclusiones realizadas aplican igualmente al método de reemplazo elitista tradicional. Para mostrar los resultados de este experimento nos vamos a apoyar en cuatro gráficas de dispersión, que se corresponden con dos ejecuciones para una especificación pequeña (10 transiciones, 202 tests y 400 mutantes), denotada con Espc I, y dos ejecuciones para una especificación grande (40 transiciones, 320 tests y 12.800 mutantes) denotada con Espc II. En estas gráficas se muestra el individuo con todos los tests posibles, la semilla inicial, la mejor solución de la semilla, la mejor solución obtenida aplicando el método de reemplazo con NSGA-II, la población total tras la última generación con reemplazo directo y la mejor solución de esta población. La Figura 4.1 muestra los resultados de la ejecución del algoritmo para la especificación Espc I aplicando los métodos de selección por torneo, cruce uniforme y mutación por agregación, mientras que en la Figura 4.2 se muestran los resultados tras ejecutar esta misma especificación con los métodos de selección por truncamiento, cruce en un punto y mutación por sustitución. Las Figuras 4.3 y 4.4 muestran los resultados de la ejecución sobre la especificación Espc II con las mismas combinaciones de heurísticas. Por un lado, se puede comprobar que los resultados obtenidos por medio del método 38 Capítulo 4. Experimentos Figura 4.3: Comparación NSGA-II vs. reemplazo directo para Espc II. Torneo-Uniforme- Agregación Figura 4.4: Comparación NSGA-II vs. reemplazo directo para Espc II. Truncamiento-Un punto-Sustitución de reemplazo elitista aplicando NSGA-II están más distribuidos en comparación tanto con la semilla inicial como con la población resultante de aplicar el reemplazo directo. Adicionalmente, se observa como la mejor solución de la última generación contiene casi todos los individuos de la población. Esto se debe a que, gracias a aplicar el reemplazo elitista con NSGA-II se generan soluciones que mejoran a las anteriores (es decir, las 4.2. Evaluación 39 dominan), y estas últimas desaparecen de la población. Por otro lado, el resultado obtenido aplicando el método de reemplazo directo se con- centra más cerca del origen, mejorando algunos individuos a la semilla, pero empeorando en otros casos. Esto destaca especialmente cuando el método de cruce es uniforme (ver Figuras 4.1 y 4.3), ya que combinar el reemplazo directo junto con el método de cruce uni- forme supone perder definitivamente a todos los padres en cada generación. No obstante, este fenómeno es igualmente observable con cualquier otro método de cruce, como se puede ver en las Figuras 4.2 y 4.4. Finalmente, se puede comprobar que mediante la aplicación del reemplazo elitista con NSGA-II todas las soluciones mejoran claramente tanto a la semilla inicial como a las obtenidas por medio del reemplazo directo. Estas soluciones están repartidas a lo largo de toda la gráfica, comenzando desde el origen y llegando generalmente muy cerca del máximo en todas las ejecuciones independientemente del tamaño de la especificación, pero como hemos visto, dependiendo de la combinación de heurísticas. 4.2.2. Comparación de heurísticas usando reemplazo elitista con NSGA- II En este caso vamos a comparar los resultados obtenidos aplicando el algoritmo NSGA- II en el método de reemplazo elitista combinado con diferentes heurísticas en el resto de métodos del algoritmo genético. Estas heurísticas son: selección por torneo o truncamiento, cruce uniforme o en un punto y mutación por agregación o sustitución. Para mostrar los resultados de este experimento vamos a mostrar dos gráficas, una para cada tamaño de especificación. Recordemos que la especificación denotada con Espc I cuenta con 10 transiciones, 202 tests y 400 mutantes, mientras que la denotada con Espc II la conforman 40 transiciones, 320 tests y 12.800 mutantes. En estas gráficas, se muestran las soluciones obtenidas tras ejecutar el algoritmo genético con cada posible combinación de heurísticas, cada una de de ellas en el color correspondiente indicado en la leyenda. Una vez ejecutados los experimentos, se puede comprobar que la diferencia en los resul- tados depende principalmente del método de cruce. Para ambas especificaciones, podemos observar que las ejecuciones utilizando el método de cruce en un punto reportan mejores resultados, ya que abarcan un mayor rango de soluciones, acercándose más al conjunto 40 Capítulo 4. Experimentos Figura 4.5: Comparación heurísticas NSGA-II para Espc I. total que contiene todos los tests posibles. Si observamos al detalle cada una de las gráficas, para Espc I la selección por trun- camiento ofrece ligeramente mejores resultados, mientras que en el caso de Espc II es la heurística de torneo en la selección la que produce mejores soluciones. Finalmente, se puede concluir que, considerando que el reemplazo elitista aplicando el algoritmo NSGA-II da mejores resultados que las heurísticas de reemplazo habituales, las soluciones más óptimas se consiguen combinándolo con el cruce en un punto. Adicional- mente, si estamos trabajando con especificaciones pequeñas, podemos añadir que utilizar el método de selección por truncamiento genera soluciones ligeramente superiores, mientras que para las especificaciones mayores esta mejora se da aplicando la selección por torneo. 4.2. Evaluación 41 Figura 4.6: Comparación heurísticas NSGA-II para Espc II. Capı́tulo 5 Conclusiones y Trabajo Futuro En este trabajo hemos diseñado un marco de selección de casos de test utilizando algo- ritmos genéticos y un nuevo concepto de mutation score aplicando el criterio de distinción de mutantes. Para realizar la selección de subconjuntos de casos de test hemos conside- rado dos objetivos a optimizar: el número de entradas que de los tests del subconjunto, y el distingushing mutation score de dicho subconjunto, calculado teniendo en cuenta los mutantes diferentes que mata cada test. En primer lugar, para calcular el criterio de distingushing mutation score, hemos di- señado una algoritmo que compara el comportamiento de cada test del subconjunto en relación a cada mutante. Hemos podido observar que el distingushing mutation score obte- nido es inferior al tradicional, pero esto se debe a que es más restrictivo a la hora de asignar una puntuación. De esta manera, nos aseguramos de que la solución obtenida será óptima también en cuanto a tamaño, ya que el subconjunto de tests que contenga no incluirá tests equivalentes. Por otro lado, para realizar esta selección de casos de test en base a los dos objetivos mencionados, hemos adaptado el algoritmo multiobjetivo NSGA-II para incluirlo en el flujo del algoritmo genético. Para ello, en el método de reemplazo de cada generación, hemos unido ambas poblaciones y definido las fronteras de Pareto con las soluciones que no se dominan entre sí en ninguno de los dos objetivos. Una vez definidas estas fronteras, hemos reemplazado la población inicial con las soluciones de las mejores fronteras. De esta forma hemos conseguido un reemplazo elitista considerando ambos objetivos. 43 44 Capítulo 5. Conclusiones y Trabajo Futuro Por último, para comprobar la validez de nuestro trabajo, hemos realizado dos fases de experimentos. En primera instancia hemos podido comprobar que la aplicación del reem- plazo elitista usando NSGA-II devuelve mejores resultados que la heurística de reemplazo directo. Estas soluciones son mejores porque al aplicar el reemplazo elitista con NSGA-II en cada generación, la población va formándose cada vez por soluciones que no se dominan entre ellas, por lo que al finalizar la ejecución se consigue un mayor número de soluciones posibles. Por otro lado, hemos realizado una comparación entre diferentes heurísticas de los métodos en el algoritmo genético, con el fin de determinar cuál es la combinación más idónea para nuestra línea de trabajo, siempre considerando el reemplazo elitista usando NSGA-II. Comparando los resultados, hemos determinado que los resultados dependen en primer lugar del método de cruce, ya que son mejores si se aplica cruce en un punto en lugar de uniforme. Adicionalmente, hemos podido comprobar que al trabajar con una población pequeña se han generado mejores soluciones al aplicar la heurística de truncamiento en la selección, mientras que en los casos en los que la especificación es mayor, se consigue un mejor resultado aplicando la selección por torneo. Como principal línea de trabajo futuro, se podría trabajar en la automatización de la ejecuciones para poder conseguir una comparación en tiempo real de las diferentes com- binaciones de heurísticas. Adicionalmente, se podría diseñar una interfaz de usuario desde la cual se pudiese definir el tamaño de la especificación y los métodos a utilizar, a la vez que se mostrasen los resultados directamente al usuario. También se podría contemplar la inclusión de nuevas heurísticas para los diferentes métodos del algoritmo genético. De esta forma se podría encontrar una combinación que mejorase los resultados obtenidos en este trabajo. Chapter 6 Introduction 6.1. Motivation Software testing is one of the main techniques used to validate the correctness of a system, i.e. to check it for bugs. Normally, the expected behaviour of systems is given in the form of tests, which are used to determine whether the system under test complies with the specification, or if on the contrary, it contains bugs. However, one of the main drawbacks of software testing is that the number of tests needed to check all the system’s behaviour can be infinite. Therefore, there is a need to select a sufficient number of tests to detect most of the errors based on a certain criterion. In order to reduce the number of test cases to be applied to check the validity of a system, a subset of all possible test cases must be selected. To determine this subset, it is necessary to establish a metric that allows us to determine the quality of each test, in order to filter out and keep only the best ones in the subset finally selected. In order to determine which sets of tests are the best, test case prioritisation techniques are used, which serve to order them based on a desirable property, such as their ability to detect errors (Catal y Mishra, 2013). In this line, the technique of mutation testing is interesting to evaluate the effectiveness of a set of tests (King y Offutt, 1991; Offutt et al., 1996; Hierons et al., 2010; Jia y Harman, 2011; Lou et al., 2015; Shin et al., 2019). For this purpose, systems similar to the system under test are created by applying small individual modifications to the system under test, such as removing code fragments, swapping arithmetic operators or swapping relational operators. By applying the tests to the mutants and the original 45 46 Chapter 6. Introduction system, it is possible to determine those with the highest error detection capability, i.e. those that reveal the most differences in the behaviour of the mutants compared to that of the original system. The idea is that if a set of tests distinguishes the system under test from other systems similar to it but with faults, then it can be a good set for determining errors in that system. In this way, an ordering of test cases can be carried out based on this error detection capability. The approach usually used in mutation testing to determine the quality of a test suite is based on how many errors it is capable of detecting. However, a new proposal has recently emerged which, in addition to the number of errors detected, also considers and promotes the diversity of test cases (Shin et al., 2018, 2019). In this case, the ability of the test suite to distinguish mutants is valued more than the ability to distinguish those mutants from the original programme. In this way, the tests that help to distinguish between all mutants first are prioritised. In this paper, a genetic algorithm is proposed to obtain a good subset of tests from an initial set of tests. Starting with a random population, this technique evolves towards optimal solutions. This work is an extension of a previous proposal for test case selection in the field of finite state machines (Benito-Parejo y Merayo, 2020). The aim of this work is to optimise the quality of the test cases based on their error detection capacity and their diversity when detecting errors, as well as the length of the test cases, i.e. the number of inputs to be applied for their execution. For this purpose, an advanced multi-objective optimisation algorithm (Deb et al., 2002) is applied that allows an optimal prioritisation of sets of test cases based on the two aforementioned objectives. This algorithm has been fully implemented and the results obtained from its application to different specifications and test sets are presented. 6.2. Objetives The main objective of this work is to apply and combine new mutation testing tech- niques and genetic algorithms for the design and implementation of a test case selection framework. This framework should guide the minimisation of the number of inputs needed by the subset of test cases while maximising the number of different mutants that the test cases kill. To this end, the following sub-objectives have been defined: 6.3. Work plan 47 The first step is to apply the technique of the mutant distinguishment criterion, in order to obtain a more optimal subset of tests than that achieved with the tradi- tional mutation score, which determines the quality of the set only by comparing the mutants with the specification. This determines that one subset of test cases is better than another, i.e. has a higher mutation score, the more different mutants it distinguishes. On the other hand, we will use thismutation score together with the number of inputs needed by the subset of test cases to determine the quality of this subset. To do so, we are going to apply the multi-objective algorithm NSGA-II in the replacement method of the genetic algorithm, in order to be able to order the partial solutions in each generation based on these objectives, in such a way that the ones that optimise these objectives the most are always maintained. Finally, we will compare the effectiveness of this new combination, determining whether the use of the mutant distinguishment criterion to determine the quality of a subset of tests, together with the application of the multi-objective NSGA-II ge- netic algorithm to obtain the best subset of test cases, reports more optimal solutions than traditional methods. 6.3. Work plan To achieve the main objective of the work, it has been necessary to manage the tasks to be performed in a convenient way. For this purpose, the work has been divided into different phases of design, development and debugging, and iterated cyclically through all of them, revisiting the necessary phases in order to achieve the best possible results. The phases that have been defined are: 1. Familiarization and understanding phase a) Familiarization with mutation testing. b) Familiarization with genetic algorithms. c) Familiarization with the mutant distinction criterion. d) Familiarization with the NSGA-II algorithm. 48 Chapter 6. Introduction 2. Design and implementation phase a) Design and implementation of the distinguishing mutation score. b) Design and implementation of the elitist replacement criteria using NSGA-II. c) Adaptation of the system structure to apply the new criteria. 3. Debugging phase a) Debugging and optimization of the distinguishing mutation score algorithm. b) Debugging and optimization of NSGA-II algorithms. c) Debugging and optimization of the overall system structure. 4. Tests and results a) Tests design. b) Tests execution and result evaluation. 6.4. Document structure This document is structured as follows: In chapter 2 there is an introduction to the theoretical concepts on which the work is based. In chapter 3 the proposal for the selection of test cases is described. In chapter 4 the results of the executed experiments are defined and shown. In chapter 7 the conclusions drawn from the work and possible extensions on the work developed are presented. Chapter 7 Conclusions and Future Work In this work we have designed a test case selection framework using genetic algorithms and a new concept of distinguishing mutation score applying the criterion of distinguishing mutants. To perform test case subset selection we have considered two objectives to be optimized: the number of inputs that the tests in the subset need, and the distinguishing mutation score of that subset, calculated by taking into account the different mutants killed by each test. First, to calculate the distingushing mutation score criterion, we have designed an algorithm that compares the behavior of each test in the subset in relation to each mutant. We have been able to observe that the distingushing mutation score obtained is lower than the traditional one, but this is because it is more restrictive when assigning a score. In this way, we ensure that the solution obtained will also be optimal in terms of size, since the subset of tests it contains will not include more than one test that has the same behaviour. On the other hand, to perform this test case selection based on the two mentioned objectives, we have adapted the NSGA-II multi-objective algorithm to include it in the sequence of the genetic algorithm. To do this, in the replacement method for each gener- ation, we have joined both populations and defined Pareto fronts with the solutions that do not dominate each other in either of the two objectives. Once these fronts have been defined, we have replaced the initial population with the solutions of the best fronts. In this way we have achieved an elitist replacement considering both objectives. Finally, to check the validity of our work, we have performed two phases of experi- 49 50 Chapter 7. Conclusions and Future Work ments. In the first instance we have been able to verify that the application of the elitist replacement using NSGA-II yields better results than the direct replacement heuristic. These solutions are better because when applying the elitist replacement with NSGA-II in each generation, the population is formed each time by solutions that do not dominate each other, so that at the end of the execution a greater number of possible solutions is obtained. On the other hand, we have made a comparison between different heuristics of the methods in the genetic algorithm, in order to determine which is the most suitable combination for our line of work, always considering the elitist replacement using NSGA-II. Comparing the results, we have determined that the results depend first of all on the crossover method, since they are better if crossover is applied at a point instead of uniformly. Additionally, we have been able to verify that, when working with a small population, better solutions have been generated by applying the truncation heuristic in the selection, while in cases where the specification is larger, a better result is achieved by applying tournament selection. As a main line of future work, we could work on the automation of the execution in order to achieve a real-time comparison of the different combinations of heuristics. Additionally, a user interface could be designed from which the size of the specification and the methods to be used could be defined, and the results could be shown directly to the user. The inclusion of new heuristics for the different methods of the genetic algorithm could also be contemplated. In this way, a combination could be found that would improve the results obtained in this work. Bibliografía Abraham, A. y Jain, L. Evolutionary Multiobjective Optimization, páginas 1–6. Springer London, London, 2005. ISBN 978-1-84628-137-2. Ammann, P. y Offutt, J. Introduction to Software Testing . Cambridge University Press, 2016. Benito-Parejo, M. y Merayo, M. G. An evolutionary algorithm for selection of test cases. En 2020 IEEE Congress on Evolutionary Computation (CEC), páginas 1–8. 2020. Catal, C. y Mishra, D. Test case prioritization: A systematic mapping study. Software Quality Journal , vol. 21(3), página 445–478, 2013. ISSN 0963-9314. Coello, C. C. Evolutionary multi-objective optimization: a historical view of the field. IEEE computational intelligence magazine, vol. 1(1), páginas 28–36, 2006. Deb, K., Pratap, A., Agarwal, S. y Meyarivan, T. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation, vol. 6(2), páginas 182–197, 2002. DeMillo, R. A., Lipton, R. J. y Sayward, F. G. Hints on test data selection: Help for the practicing programmer. Computer , vol. 11(4), páginas 34–41, 1978. ISSN 1558-0814. Goldberg, D. E. Genetic Algorithms in Search, Optimisation and Machine Learning . Addison-Wesley, 1989. Hierons, R. M., Merayo, M. G. y Núñez, M. Mutation testing. En Encyclopedia of Software Engineering (editado por P. A. Laplante), páginas 594–602. Taylor & Francis, 2010. 51 52 BIBLIOGRAFÍA Jia, Y. y Harman, M. An analysis and survey of the development of mutation testing. IEEE Transactions on Software Engineering , vol. 37(5), páginas 649–678, 2011. King, K. N. y Offutt, A. J. A Fortran language system for mutation-based software testing. Softw., Pract. Exper., vol. 21(7), páginas 685–718, 1991. Lou, Y., Hao, D. y Zhang, L. Mutation-based test-case prioritization in software evolu- tion. En 2015 IEEE 26th International Symposium on Software Reliability Engineering (ISSRE), páginas 46–57. 2015. Mirjalili, S. Genetic Algorithm, páginas 43–55. Springer International Publishing, Cham, 2019. ISBN 978-3-319-93025-1. Offutt, A. J., Voas, J. y Payne, J. Mutation operators for Ada. Informe técnico, Information and Software Systems Engineering, George Mason University, 1996. Pareto, V. Cours d’économie politique, vol. 1. Librairie Droz, 1964. Shin, D., Yoo, S. y Bae, D.-H. A theoretical and empirical study of diversity-aware mutation adequacy criterion. IEEE Transactions on Software Engineering , vol. 44(10), página 914–931, 2018. ISSN 0098-5589. Shin, D., Yoo, S., Papadakis, M. y Bae, D.-H. Empirical evaluation of mutation- based test case prioritization techniques. Software Testing, Verification and Reliability , vol. 29(1-2), página e1695, 2019. ISSN 0960-0833. Sivanandam, S. y Deepa, S. Genetic Algorithms, páginas 15–37. Springer Berlin Hei- delberg, Berlin, Heidelberg, 2008. ISBN 978-3-540-73190-0. Srinivas, N. y Deb, K. Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, vol. 2(3), páginas 221–248, 1994. Zitzler, E., Laumanns, M. y Bleuler, S. A tutorial on evolutionary multiobjective optimization. Metaheuristics for multiobjective optimisation, páginas 3–37, 2004. BIBLIOGRAFÍA 53 Change will not come if we wait for some other person or some other time. We are the ones we’ve been waiting for. We are the change that we seek. Barack Obama Página de Título Índices Tabla de Contenidos Índice de figuras Índice de tablas Introducción Motivación Objetivos Plan de trabajo Estructura del documento Preliminares Mutation Testing Algoritmos genéticos Algoritmos Multiobjetivo Diseño del algoritmo Especificaciones, Mutantes y Tests Objetivos considerados Algoritmo genético multiobjetivo Consideraciones finales Experimentos Descripción de los experimentos Evaluación Resultados para reemplazo elitista usando NSGA-II Comparación de heurísticas usando reemplazo elitista con NSGA-II Conclusiones y Trabajo Futuro Introduction Motivation Objetives Work plan Document structure Conclusions and Future Work Bibliografía