Supporting the Statistical Analysis of Variability Models by Processing Binary Decision Diagrams

Abstract

Cuando uno de los principales objetivos de la Ingeniera de Software es el ahorro en costes y tiempo, las lneas de productos de software juegan un papel fundamental. En este campo, la clave reside en la identi cacion de componentes reutilizables o caractersticas que puedan ser aplicados en futuros proyectos. La necesidad de proveer soluciones que se adapten a problemas espec cos, satisfaciendo una amplia variedad de requerimientos no funcionales, como la e ciencia en tiempo de ejecuci on, consumo de memoria del dispositivo en el que se ejecuta determinada aplicacion, requisitos a nivel de seguridad, etc. ha supuesto una ardua labor de investigacion. La personalizacion se logra a traves de un proceso de con guracion donde se seleccionan las caractersticas deseadas. El espacio esta restringido para evitar incompatibilidades entre caractersticas, garantizando que se satisfagan las dependencias de nidas entre ellas. Hay muchas preguntas interesantes acerca de este espacio restringido: >Estan todas las con guraciones libres de error? >Hay codigo muerto que no pueda ser ejecutado por las restricciones entre las caractersticas? >Cual es rango de reutilizacion de componentes? >Cual es el tama~no tpico de un producto nal en terminos de sus componentes? Etc. El tama~no del espacio de con guracion potencialmente puede ser 2n para n caracter sticas. As, procesar el conjunto completo de soluciones es imposible excepto para los casos mas triviales. Despues de eliminar las con guraciones no validas que no satisfacen las restricciones entre caractersticas, el espacio resultante se reduce sustancialmente. Sin embargo, normalmente sigue siendo demasiado grande como para poder trabajar con el. Una estrategia para abordar estas di cultades es seleccionar una muestra representativa del espacio y, una vez que los calculos se han realizado, extrapolar las conclusiones al conjunto completo. En este punto, el problema reside en la obtencion de una muestra aleatoria able para evitar interpretaciones erroneas. Esta tesis presenta un conjunto de algoritmos que permiten (i) trabajar con la totalidad de la poblacion de con guraciones validas usando una estructura Booleana altamente optimizada conocida como Diagrama de Decision Binario, y (ii) generar muestras aleatorias a partir del espacio de con guracion. Ademas, se aporta una completa infraestructura en dos lenguajes de programacion (C++ y R) con la que incorporar nuevos algoritmos sobre Diagramas de Decision Binarios sin apenas esfuerzo. Finalmente, esta tesis muestra la validacion emprica de nuestros algoritmos y marco de trabajo a traves de una prueba de rendimiento compuesta de modelos de variabilidad reales, cuyo numero de caractersticas va desde 45 a 17 365. Palabras clave: Lneas de productos de software, Modelos de caractersticas, Diagramas de decision binarios, Funciones Booleanas.