BDD algorithms to perform hard analysis operations on variability models
Pérez Morago, Héctor José · 2015
espanolComo consecuencia de la globalizacion de los mercados, los fabricantes necesitan adaptar sus productos a las necesidades especificas de cada cliente. Alcanzar este objetivo requiere de las mismas un cambio en sus modelos de produccion, pasando de la produccion en masa a la produccion personalizada de productos. En el contexto del desarrollo de software, la ingenieria de lineas 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 personalizacion. Los modelos de variabilidad son utilizados para especificar las caracteristicas comunes y variables a la familia de productos. Ademas, permiten modelar las restricciones entre caracteristicas que todo producto debe satisfacer para ser considerado valido. 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 numero de caracteristicas y restricciones. Como resultado, el estudio de tecnicas de razonamiento automatico sobre modelos de variabilidad ha pasado a ser uno de los temas de investigacion mas importantes para la comunidad de las lineas de productos. Las tecnicas automaticas de analisis puede ser clasificadas en dos grupos atendiendo al objetivo para el que han sido disenadas: aquellas que se encargan de garantizar la correccion del modelo y aquellas que se encargan de dar soporte a la configuracion de los distintos productos. Las primeras son generalmente llevadas a la practica por medio de operaciones de analisis, las cuales son realizadas por medio de funciones predefinidas en motores logicos, tales como SAT-solvers o librerias de diagramas de decision binarios. El principal problema de esta estrategia consiste en que tal tipo de reutilizacion implica el consumo de grandes cantidades de tiempo. Este hecho unido al hecho de que algunas de estas operaciones requieren de multiples 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 interactuan con la estructura de datos interna del diagrama de decision binario utilizado para codificar el modelo de variabilidad. En concreto, nuestros algoritmos estan especificamente disenados para detectar aquellas caracteristicas que son incluidas en todos lo productos validos, aquellas otras que no pertenecen a ningun producto valido, el numero de productos que incluyen una determinada caracteristica, asi como los conjuntos de caracteristicas que una caracteristica particular necesita incluir o excluir para ser incluida en algun producto valido. El segundo problema que abordamos en esta tesis tiene que ver con la configuracion de productos. La configuracion de productos en modelos de variabilidad no es una tarea trivial ya que requiere de una gran cantidad de decisiones acerca de que caracteristicas 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 entropia de la teoria de la informacion, aprovecha el hecho de que ciertas decisiones pueden ser automaticamente derivadas de las decisiones tomadas previamente. EnglishTo compete in the global marketplace, manufacturers try to differentiate their products by focusing on individual customer needs. Fulfilling this goal requires companies to shift from mass production to mass customization. In the context of software development, software product line engineering has emerged as a cost-effective approach to developing families of similar products by supporting high levels of mass customization. Variability models are often used to specify the common and variable features of the products in one such family. Moreover, they model the inter-feature constraints which must be satisfied to guarantee the validity of the derived products. Despite the benefits of variability models, constructing and maintaining them can be a laborious task, especially in product lines with a large number of features and constraints. As a consequence, the study of automated techniques to reason on variability models has become an important research topic for the product line community. The aim of most automated techniques can be grouped in two classes: (i) ensuring the correctness of variability models, and (ii) providing guidance to derive products from a variability model. The former is usually put in the practise by means of analysis operations, which can be performed by black box reusing logic engines, such as SAT-solvers and binary decision diagram libraries. Unfortunately, such kind of reuse implies long computation times, and for some operations that need calling the logic engine an excessive amount of times, the approach does not scale. To overcome this problem, this thesis proposes new algorithms that directly deal with the binary decision decision diagram data structure encoding a variability model. In particular, our algorithms are specifically designed to detect those features that need to be included in all legal products, those ones that do not belong to any legal product, the number of products that include a particular feature, as well as the set of features that a particular feature needs to include or exclude to be part in any legal product. The second problem this thesis faces is related to product derivation. In complex variability models, deriving a valid product is not trivial task at all, since a lot of constraints between the features must be taken into account. To speed up product derivation, this thesis proposes a new approach that tries to minimise the number of configuration steps required on average to derive a whole product. Our approach, based on the information theory concept of entropy, takes advantage of the fact that, due to the inter-feature constraints, some decisions may be automatically derived from other decisions previously made.