Aplicando programación lineal entera a la búsqueda de conjuntos de productos de prueba priorizados para líneas de productos software

Aplicando programaci´on lineal entera a la b´usqueda de conjuntos de productos de prueba priorizados para l´ıneas de productos software Javier Ferrer1, Francisco Chicano1, Roberto E. Lopez-Herrejon2y Enrique Alba1 1Universidad de M´alaga, M´alaga, Spain {ferrer, chicano, eat}@lcc.uma.es 2Systems Engineering and Automation Johannes Kepler University, Linz, Austria roberto.lop[email protected] Resumen Las l´ıneas de productos software son familias de productos que est´an ´ıntimamente relacionados entre s´ı, normalmente formados por combinaciones de un conjunto de caracter´ısticas software. Generalmente no es factible testar todos los productos de la familia, ya que el n´umero de productos es muy elevado debido a la explosi´on combinatoria de caracter´ısticas. Por este motivo, se han propuesto criterios de cobertura que pretenden probar al menos todas las interacciones entre caracter´ısticas sin necesidad de probar todos los productos, por ejemplo todos los pares de caracter´ısticas (pairwise coverage). Adem´as, es deseable testar primero los productos compuestos por un conjunto de caracter´ısticas prioritarias. Este problema es conocido como Prioritized Pairwise Test Data Generation. En este trabajo proponemos una t´ecnica basada en programaci´on lineal entera para generar este conjunto de pruebas priorizado. Nuestro estudio revela que la propuesta basada en programaci´on lineal entera consigue mejores resultados estad´ısticamente tanto en calidad como en tiempo de computaci´on con respecto a las t´ecnicas existentes para este problema. Palabras clave Pruebas de interacci´on combinatoria, l´ıneas de productos software, prioridades, programaci´on lineal entera 1. Introducci´on Las l´ıneas de productos software (SPL) son familias de sistemas software relacionados, las cuales poseen diferentes combinaciones de caracter´ısticas [1]. La gesti´on efectiva de la variabilidad es crucial para obtener beneficios de las SPLs como el incremento en la reutilizaci´on, la personalizaci´on r´apida, y la reducci´on del tiempo de llegada al mercado. Debido al gran n´umero de combinaciones de caracter´ısticas que es t´ıpico en las SPLs, los modelos con alta variabilidad suponen un desaf´ıo para el campo de las pruebas de programas. Recientemente se han propuesto muchos enfoques de pruebas [2–5]), sin embargo, todav´ıa hay potencial de mejora ya que la mayor´ıa de enfoques ya propuestos son aproximados y no suelen conseguir la soluci´on ´optima. Por contra, nosotros proponemos un enfoque basado en Programaci´on Lineal Entera (en ingl´es Integer Linear Programming - ILP) para la generaci´on del conjunto m´ınimo de productos de prueba en SPLs. Aunque la resoluci´on de programas lineales enteros es un problema NPdif´ıcil en general, con un coste computacional exponencial en el peor caso, los resolutores actuales, como CPLEX3o Gurobi4, incluyen sofisticadas estrategias de b´usqueda que les permiten resolver una gran cantidad de instancias de ILP en pocos segundos. Hasta donde llega nuestro conocimiento, esta t´ecnica no se ha aplicado anteriormente a este problema. En este art´ıculo presentamos un algoritmo ´ Avido basado en Programaci´on Lineal Entera (APLE) que genera un conjunto priorizado de pruebas para SPLs usando el criterio de cobertura pairwise, en el cual se deben cubrir todos los pares de caracter´ısticas existentes en la SPL. APLE recibe como entrada un modelo de caracter´ısticas (en ingl´es Feature Model - FM) y un conjunto de productos ponderados. Su objetivo es generar un conjunto de productos que cubren los pares de caracter´ısticas deseados siguiendo diferentes esquemas de asignaci´on de prioridades, con los que se van a generar diferentes ponderaciones para las caracter´ısticas. Este esquema ha sido propuesto en [3] y ha sido recientemente aplicado de forma satisfactoria en la industria. En nuestra experimentaci´on validamos nuestra propuesta frente a dos algoritmos del estado del arte, un algoritmo ´avido que genera soluciones competitivas en poco tiempo, llamado prioritized-ICPL (pICPL) [3] y un algoritmo gen´etico llamado Prioritized Pairwise Genetic Solver (PPGS) [6] que obtiene soluciones de mejor calidad que pICPL pero generalmente usando un tiempo mayor. Nuestra comparativa abarca un total de 235 FMs con un amplio rango de caracter´ısticas y productos, usando tres m´etodos de asignaci´on de prioridades a los productos y cinco estrategias de selecci´on de productos. Nuestro estudio ha revelado que APLE obtiene conjuntos de pruebas priorizadas m´as peque˜nos en un tiempo menor para diferentes porcentajes de cobertura ponderada, con respecto a los resultados obtenidos con PPGS y pICPL. Estos resultados muestran que el uso de t´ecnicas exactas en combinaci´on con algoritmos ´avidos constituye una estrategia muy efectiva para la generaci´on de conjuntos de productos de prueba para SPLs. Nuestras principales contribuciones en este art´ıculo son las siguientes: Propuesta de un algoritmo constructivo ´avido basado en ILP. Evaluaci´on del rendimiento de APLE en comparaci´on con PPGS e pICPL. El resto del art´ıculo se organiza de la siguiente manera. En la Secci´on 2 presentamos los modelos de caracter´ısticas. En la Secci´on 3 se formaliza el problema de la generaci´on de conjuntos de productos de prueba priorizados en SPL. La Secci´on 4 describe nuestra propuesta algor´ıtmica. En la Secci´on 5 presentamos los dem´as algoritmos objeto de la comparaci´on, los m´etodos de asignaci´on de 3http://www-03.ibm.com/software/products/es/ibmilogcpleoptistud 4https://www.gurobi.com prioridades y las instancias usadas en la experimentaci´on. La Secci´on 6 est´a dedicada al an´alisis estad´ıstico de los resultados y la Secci´on 7 a describir las amenazas a la validez del estudio. Por ´ultimo, en la Secci´on 8 ofrecemos las conclusiones obtenidas y los siguientes pasos de nuestra investigaci´on. 2. Modelos de Caracter´ısticas Los modelos de caracter´ısticas son un est´andar de facto para modelar las caracter´ısticas comunes y variables de un sistema (representadas por cajas etiquetadas) y sus relaciones (representadas con l´ıneas) formando una estructura de tipo ´arbol, especificando as´ı un conjunto de combinaciones de caracter´ısticas que dan lugar a m´ultiples configuraciones diferentes [7]. Cada caracter´ıstica distinta de la ra´ız tiene una sola caracter´ıstica padre y puede tener un conjunto de caracter´ısticas hijas. N´otese que una caracter´ıstica hija s´olo puede ser incluida en una configuraci´on si y s´olo si, su padre es incluido tambi´en. Para ilustrar estos conceptos vamos a usar un FM (Figura 1) extra´ıdo del repositorio SPLOT [8]. Hay cuatro tipos de relaciones jer´arquicas entre caracter´ısticas: Caracter´ısticas opcionales: son representadas con un c´ırculo vac´ıo e indica que esta caracter´ıstica puede o no ser seleccionada si su padre es seleccionado. En nuestra instancia de ejemplo ser´ıa la caracter´ıstica Engine. Caracter´ısticas obligatorias: son representadas con un c´ırculo relleno, y deben ser seleccionadas si su padre es seleccionado. En nuestra instancia de ejemplo ser´ıan obligatorias: Wing yMaterials. Relaciones Or-inclusivas: son representadas como arcos independientes rellenos que abarcan un conjunto de l´ıneas que conectan la caracter´ıstica padre con las caracter´ısticas hijas. Indican que al menos una caracter´ıstica debe ser seleccionada si el padre es seleccionado. En nuestra instancia de ejemplo, la relaci´on de Wing oMaterials con sus hijos es de este tipo. Relaciones Or-exclusivas: son representadas como arcos independientes vac´ıos que abarcan un conjunto de l´ıneas que conectan la caracter´ıstica padre con las caracter´ısticas hijas. Indican que exactamente una caracter´ıstica debe ser seleccionada si el padre es seleccionado. En nuestra instancia de ejemplo la relaciones de Engine con sus respectivos hijos son Or-exclusivas. Adem´as de las relaciones padre-hijo, las caracter´ısticas se pueden relacionar tambi´en con otras ramas del modelo de caracter´ısticas, son las restricciones conocidas como Cross-Tree Constraints (CTC) [9]. Estas restricciones, as´ı como las impuestas por las relaciones jer´arquicas entre caracter´ısticas, son expresadas y comprobadas usando l´ogica proposicional (para m´as detalles consultar [9]). 3. Formalizaci´on del Problema: Prioritized Pairwise Test Data Generation En esta secci´on proporcionamos una descripci´on formal del problema de la generaci´on de conjunto de pruebas priorizados por pares y del esquema de prioridades implementado por las propuestas algor´ıtmicas estudiadas en este trabajo. Figura 1. Modelo de caracter´ısticas de Aircraft Definici´on 1. Lista de Caracter´ısticas (LC) es la lista de caracter´ıstica del modelo de caracter´ısticas. Definici´on 2. Conjunto de Caracter´ısticas (CC) es un par (sel, sel)donde sel ysel son respectivamente los conjuntos de caracter´ısticas seleccionadas y no seleccionadas de un producto. Sea LC una lista de caracter´ısticas, entonces sel, sel ⊆LC,sel ∩sel =∅, y sel ∪sel =LC. Si pes un producto, los t´erminos p.sel yp.sel son el conjunto de caracter´ısticas seleccionadas y no seleccionadas del producto p, respectivamente. Definici´on 3. Un conjunto de caracter´ısticas cc es v´alido en un modelo de caracter´ısticas fm, es decir, valido(cc, fm)es verdadero, si y solo si cc no contradice ninguna restricci´on introducida por fm. Las pruebas de interacci´on combinatorias son un enfoque que construye conjuntos de pruebas (test suites) que nos llevan a probar de forma sistem´atica todas las configuraciones de un sistema [10]. En este trabajo vamos a utilizar el enfoque pairwise, que es el m´as utilizado en pruebas combinatorias y est´a basado en la suposici´on de que la mayor´ıa de errores originados en un par´ametro es causado por la interacci´on de dos valores [11]. Este criterio se satisface si para cada par de caracter´ısticas f1yf2, podemos encontrar cuatro productos en el conjunto generado que contengan las cuatro posibles combinaciones de presencia/ausencia de dichas caracter´ısticas: (f1, f2),(f1, f2),(f1, f2) y (f1, f2). Cuando se aplica esta t´ecnica a FMs, la idea es generar un conjunto de productos v´alidos, donde los errores posibles se manifiestan con alta probabilidad, sin tener que probar de forma exhaustiva todas las posibles configuraciones. Adem´as, gracias a la priorizaci´on, vamos a testar en primer lugar los productos con aquellas caracter´ısticas que son m´as frecuentes o importantes en nuestros sistemas. Definici´on 4. Un producto priorizado pp es un par (cc, w), donde cc representa un conjunto de caracter´ısticas v´alido en un modelo e caracter´ısticas fm yw∈R representa su peso. Sean ppiyppjdos productos priorizados. Decimos que ppi tiene prioridad m´as alta que ppjcuando el peso de ppies m´as alto que el peso de ppj, es decir, ppi.w > ppj.w. Definici´on 5. Una configuraci´on por pares pc es un par (sel, sel)que representa un producto parcialmente configurado, definidos por la selecci´on de dos caracter´ısticas de LC, es decir, pc.sel ∪pc.sel ⊆LC,pc.sel ∩pc.sel =∅y |pc.sel ∪pc.sel|= 2. Decimos que pc se cubre con un conjunto de caracter´ısticas cc cuando pc.sel ⊆cc.sel ypc.sel ⊆cc.sel. Definici´on 6. Una configuraci´on por pares ponderada wpc es un par (pc, w) donde pc es una configuraci´on por pares y w∈Rrepresenta su peso calculado de la siguiente manera. Sea P P un conjunto de productos priorizados y P Ppc ⊆P P , tal que P Ppc contiene todos los productos priorizados de P P que cubren wpc.pc, es decir, P Ppc ={pp ∈P P |pp.cc cubre wpc.pc}. Entonces w=Pp∈P Ppc p.w. Dada una colecci´on de conjuntos de caracter´ısticas ppCA y un conjunto de configuraciones por pares ponderadas WPC, definimos la cobertura de ppCA, denotada por cob(ppCA), como la suma de los pesos de las configuraciones por pares ponderadas de WPC cubiertas por alguna configuraci´on de ppCA dividida entre la suma de todos los pesos de las configuraciones en WPC, esto es: cob(ppCA) = Pwpc∈W P C ∃cc∈ppCA,cc cubre wpc.pc wpc.w Pwpc∈WPC wpc.w .(1) El problema de optimizaci´on en el que estamos interesados consiste en encontrar una colecci´on de conjuntos de caracter´ısticas v´alidos, ppCA, que minimice el n´umero de conjuntos de caracter´ısticas |ppCA|y maximice la cobertura cob(ppCA). Este es un problema de optimizaci´on bi-objetivo con objetivos contrapuestos. Por tanto, la soluci´on no ser´a ´unica, nuestro objetivo ser´a encontrar un conjunto de soluciones eficientes (no dominadas). 4. Algoritmo ´ Avido basado en Programaci´on Lineal Entera Para resolver el problema proponemos usar un algoritmo ´avido que, en cada iteraci´on, busca un producto que maximice la cobertura con respecto a la actual. Una vez encontrado, a˜nade dicho producto al conjunto soluci´on, elimina los pares de caracter´ısticas cubiertos por el producto y contin´ua su b´usqueda de un nuevo producto. El algoritmo se detiene cuando no es posible aumentar la cobertura, lo cual sucede cuando todos los pares de caracter´ısticas con peso mayor que cero han sido cubiertos. Antes de presentar el algoritmo, describiremos el programa lineal entero que se utiliza como base en cada iteraci´on de APLE. Sea fel n´umero de caracter´ısticas de nuestro modelo fm. Usaremos las variables de decisi´on xj∈ {0,1}con j∈ {1,2, . . . , f}para indicar si debemos incluir la caracter´ıstica jen el siguiente producto (xj= 1 o no (xj= 0). No todas las combinaciones de caracter´ısticas forman productos v´alidos. Siguiendo a Benavides et al. [9], podemos utilizar una f´ormula de l´ogica proposicional para expresar la validez de un producto en un determinado FM. Para poder incluir esas restricciones en nuestro programa lineal, esta f´ormula se expresar´a en forma normal conjuntiva (CNF) y se transformar´an en desigualdades que se a˜naden al programa lineal. A continuaci´on veremos c´omo se transforma cada cl´ausula de la f´ormula. Definamos los vectores binarios vyucomo sigue: vj=1 si la caracter´ıstica japarece en la cl´ausula, 0 en otro caso, uj=1 si la caracter´ıstica japarece negada en la cl´ausula, 0 en otro caso. Con la ayuda de uyvpodemos escribir transformar la cl´ausula en la siguiente desigualdad para nuestro programa lineal: f X j=1 vj(uj(1 −xj) + (1 −uj)xj)≥1.(2) Por otro lado, necesitaremos variables de decisi´on para modelar las configuraciones por pares que se cubren con un producto. Las variables las denotaremos con cj,k,cj,k,cj,k ocj,k, dependiendo de la combinaci´on de presencia/ausencia de caracter´ısticas en la configuraci´on, y tomar´an valor 1 si el producto cubre la configuraci´on y 0 en caso contrario. Los valores de las variables cdependen de los valores de las variables x. Para reflejar esta dependencia en nuestro programa lineal, necesitamos a˜nadir las siguientes restricciones para todos los pares de caracter´ısticas 1 ≤j < k ≤f: 2cj,k ≤(1 −xj) + (1 −xk),(3) 2cj,k ≤(1 −xj) + xk,(4) 2cj,k ≤xj+ (1 −xk),(5) 2cj,k ≤xj+xk.(6) En realidad no es necesario a˜nadir todas las variables cposibles, sino solo aquellas que se correspondan con una configuraci´on que no haya sido cubierta anteriormente. Llamemos al conjunto de configuraciones no cubiertas U. Entonces, la funci´on objetivo (a maximizar) de nuestro programa lineal, que es la cobertura conseguida con el producto, tiene como expresi´on: f(c) = X (j,k)∈U wj,kcj,k,(7) donde, abusando de notaci´on, usado jykpara representar caracter´ısticas del modelo y su presencia/ausencia, y hemos expresado el peso de las configuraci´on (j, k) con wj,k. En el Algoritmo 1 presentamos nuestra propuesta APLE. En la l´ınea 1 inicializa la lista de productos ppCA, que por el momento est´a vac´ıa. A continuaci´on entra en un bucle en el que busca el producto que maximiza la cobertura con Algoritmo 1. Algoritmo ´ Avido basado en Programaci´on Lineal Entera (APLE) Entrada: U//conjunto de configuraciones con peso mayor que cero Salida: ppCA // lista de productos 1: ppCA ←[] 2: while U6=∅do 3: z←resolver (m´ın f(x) sujeto a (2)-(6)) 4: ppCA ←ppCA +z 5: U←U/cob(z) // Elimina las configuraciones cubiertas por z 6: end while respecto a las configuraciones que quedan por cubrir, U(l´ınea 2). El nuevo producto es a˜nadido a la lista de productos y las configuraciones cubiertas por el producto son eliminadas de U. 5. Evaluaci´on Esta secci´on describe como fue llevada a cabo nuestra evaluaci´on. Empezamos describiendo los algoritmos PPGS y pICPL objeto de la comparaci´on, seguido de los m´etodos usados para asignar prioridades, los modelos de caracter´ısticas usados como instancias y la configuraci´on de los experimentos. 5.1. Algoritmo PPGS El algoritmo llamado Prioritized Pairwise Genetic Solver (PPGS) es un algoritmo gen´etico constructivo que sigue un modelo maestro-esclavo para paralelizar la evaluaci´on de los individuos. En cada iteraci´on, el algoritmo a˜nade un nuevo producto al conjunto de pruebas en construcci´on hasta que todas las combinaciones de caracter´ısticas se hayan cubierto. Este algoritmo considera como mejor producto para ser a˜nadido aquel que cubra un conjunto de pares de caracter´ısticas (a´un por cubrir) que aporten mayor cobertura al conjunto de productos priorizados. La configuraci´on de par´ametros utilizada para PPGS es la siguiente: torneo binario como operador de selecci´on, cruce de un punto con probabilidad 0,8, mutaci´on con probabilidad 0,1, poblaci´on de 10 individuos y condici´on de parada 1000 evaluaciones de fitness para la generaci´on del siguiente mejor producto. La condici´on de parada del algoritmo es conseguir cobertura total. Para m´as detalles consultar [6]. 5.2. Algoritmo pICPL pICPL es un algoritmo ´avido que genera matrices de cobertura con fortaleza n(n-wise covering arrays) desarrollado por Johansen et al. [3]. Este algoritmo no genera covering arrays con cobertura total sino que cubre s´olo aquellas combinaciones que aparecen en al menos un producto priorizado. El resultado obtenido con este enfoque es equivalente al que se persigue resolviendo este problema, ya que el conjunto de pares por cubrir va a ser el mismo en todos los algoritmos utilizados en este art´ıculo. Debemos destacar que pICPL usa ejecuci´on paralela a nivel de datos. Este paralelismo viene de las operaciones realizadas sobre un conjunto amplio de datos. Para m´as detalles consultar [3]. Queremos remarcar que existe una versi´on muy conocida de este algoritmo para testar SPLs, desarrollado por los mismos autores, llamado ICPL [12]. Sin embargo, esa versi´on no contempla prioridades en la computaci´on del conjunto de pruebas. 5.3. M´etodos de Asignaci´on de Prioridades Consideraremos tres m´etodos de asignaci´on de pesos a productos: Valores Medidos Los pesos est´an derivados de propiedades no funcionales obtenidas de 16 sistemas SPL reales. Estos modelos pertenecen a dominios de problema diferentes, estando implementados usando diferentes tecnolog´ıas, y fueron medidos utilizando SPL Conqueror [13]. El resultado son estimaciones reales de propiedades medibles no funcionales como consumo de memoria o rendimiento. Se calculan mediciones para un conjunto de productos, usualmente un subconjunto de aquellos que denota el FM. Esta opci´on de asignaci´on de pesos nos permite emular escenarios de pruebas m´as realistas donde los ingenieros de pruebas deben realizar mayor esfuerzo en los productos que demuestran m´as rendimiento, por ejemplo. Para nuestro trabajo tomamos los valores reales de los productos considerando las interacciones de pares de caracter´ısticas. La Tabla 1 resume los sistemas SPL evaluados, su propiedad medida (Prop), el n´umero de caracter´ısticas o features (NF), el n´umero de productos (NP), n´umero de configuraciones medidas (NC), y el porcentaje de productos priorizados (PP %) usados en nuestra comparativa, como explicaremos en breve. Valores Basados en Rango Para esta asignaci´on de pesos seleccionamos los productos a priorizar basados en c´omo de diferentes son comparados con otros productos de la SPL y se les asigna un peso basado en su rango de valores. La intuici´on bajo esta estrategia de asignaci´on es dar un peso similar a dos productos muy diferentes. De esta manera los pesos altos est´an esparcidos entre un n´umero alto de pares de caracter´ısticas haciendo que el conjunto de pruebas priorizado sea m´as dif´ıcil de computar. Adem´as, esto nos da la posibilidad de seleccionar diferentes porcentajes de productos usados en el c´alculo final de los pesos de las caracter´ısticas, como explicaremos a continuaci´on. Valores Aleatorios Esta asignaci´on de pesos se consigue generando valores aleatorios dentro del rango obtenido en el enfoque anteriormente explicado (Valores Basados en Rango). Vamos a seleccionar los productos para priorizar bas´andonos en los m´etodos de asignaci´on. Para el m´etodo de Valores Medidos, todos los productos medidos SPL Name Prop NF NP NC PP % Prevayler F 6 32 24 75.0 LinkedList F 26 1440 204 14.1 ZipMe F 8 64 64 100.0 PKJab F 12 72 72 100.0 SensorNetwork F 27 16704 3240 19.4 BerkeleyDBF F 9 256 256 100.0 Violet F 101 ≈1E20 101 ≈0.0 Linux subset F 25 ≈3E24 100 ≈0.0 LLVM M 12 1024 53 5.1 Curl M 14 1024 68 6.6 x264 M 17 2048 77 3.7 Wget M 17 8192 94 1.15 BerkeleyDBM M 19 3840 1280 33.3 SQLite M 40 ≈5E7 418 ≈0.0 BerkeleyDBP P 27 1440 180 12.50 Apache P 10 256 192 75.0 Tabla 1. Resumen de los Valores Medidos para los Casos de Estudio fueron usados como productos priorizados. Para los m´etodos Basados en Rango y Aleatorio, s´olo un porcentaje de los productos denotados por cada FM fue usado como producto priorizado. Los porcentajes usados fueron: 5 %, 10 %, 20 %, 30 % y 50 %. 5.4. Casos de Estudio Vamos a usar tres grupos de instancias basados en el n´umero de productos denotados por el FM y como fueron asignadas las prioridades, como se muestra en la Tabla 2. El grupo G1 est´a compuesto por 160 FMs, cuyo n´umero de productos oscila entre 16 y 1000 productos, y fueron evaluados usando los m´etodos Basados en Rango yAleatorio. El grupo G2 est´a compuesto por 59 FMs con rango de productos entre 1000 y 80000 productos, y fueron evaluados usando estos mismos dos m´etodos de asignaci´on. El grupo G3 est´a formado por 16 FMs reales, con un n´umero de productos entre 16 y ≈3E24, que fueron evaluados usando el m´etodo de valores medidos. En este estudio analizamos un total de 235 FMs que fueron extra´ıdos de varias fuentes: SPL Conqueror, Johansen et al. [3], y el repositorio SPLOT [8]. Para G1 y G2 las instancias son calculadas usando para cada FM dos m´etodos de asignaci´on de prioridades a los productos y tres porcentajes diferentes de selecci´on de productos priorizados. Mientras que en G3, s´olo usamos el m´etodo de asignaci´on de valores medidos. Esto hace un total de 1330 instancias analizadas para cada uno de los tres algoritmos de la comparaci´on.