BDD algorithms to perform hard analysis operations on variability models

Résumé

Como consecuencia de la globalización de los mercados, los fabricantes necesitan adaptar sus productos a las necesidades específicas de cada cliente. Alcanzar este objetivo requiere de las mismas un cambio en sus modelos de producción, pasando de la producción en masa a la producción personalizada de productos. En el contexto del desarrollo de software, la ingeniería de líneas de productos software ha emergido como un enfoque efectivo en costes que se centra en el desarrollo de familias de productos similares, soportando al mismo tiempo un alto grado de personalización. Los modelos de variabilidad son utilizados para especificar las características comunes y variables a la familia de productos. Además, permiten modelar las restricciones entre características que todo producto debe satisfacer para ser considerado válido. A pesar de los beneficios de los modelos de variabilidad, construir y mantener dichos modelos puede ser una tarea compleja y laboriosa, especialmente para aquellos con un gran número de características y restricciones. Como resultado, el estudio de técnicas de razonamiento automático sobre modelos de variabilidad ha pasado a ser uno de los temas de investigación más importantes para la comunidad de las líneas de productos. Las técnicas automáticas de análisis puede ser clasificadas en dos grupos atendiendo al objetivo para el que han sido diseñadas: aquellas que se encargan de garantizar la corrección del modelo y aquellas que se encargan de dar soporte a la configuración de los distintos productos. Las primeras son generalmente llevadas a la práctica por medio de operaciones de análisis, las cuales son realizadas por medio de funciones predefinidas en motores lógicos, tales como SAT-solvers o librerías de diagramas de decisión binarios. El principal problema de esta estrategia consiste en que tal tipo de reutilización implica el consumo de grandes cantidades de tiempo. Este hecho unido al hecho de que algunas de estas operaciones requieren de múltiples llamadas a dichas funciones deriva en que esta estrategia presente graves problemas de escalabilidad. Con el fin de dar respuesta a este problema, en esta tesis proponemos nuevos algoritmos que directamente interactúan con la estructura de datos interna del diagrama de decisión binario utilizado para codificar el modelo de variabilidad. En concreto, nuestros algoritmos están específicamente diseñados para detectar aquellas características que son incluidas en todos lo productos válidos, aquellas otras que no pertenecen a ningún producto válido, el número de productos que incluyen una determinada característica, así como los conjuntos de características que una característica particular necesita incluir o excluir para ser incluida en algún producto válido. El segundo problema que abordamos en esta tesis tiene que ver con la configuración de productos. La configuración de productos en modelos de variabilidad no es una tarea trivial ya que requiere de una gran cantidad de decisiones acerca de qué características deben ser incluidas y cuales no, teniendo en cuenta que estas se encuentra interrelacionadas. Con el fin de acelerar este proceso, en esta tesis proponemos un nueva estrategia que trata de minimizar el numero de decisiones a tomar en promedio para configurar un producto. Esta estrategia, basada en el concepto de entropía de la teoría de la información, aprovecha el hecho de que ciertas decisiones pueden ser automáticamente derivadas de las decisiones tomadas previamente.