Automating the analysis of stateful feature models

Abstract

El modelado de la variabilidad es una de las principales tareas en el desarrollo de l´ıneas de productos software (LPS). Los FMs son el modelo mas utilizado para ello. Los FMs representan el conjunto de decisiones que pueden tomar los usuarios para configurar su producto como una jerarqu´ıa de caracter´ısticas. Hasta la fecha, estas decisiones se limitan a elegir y descartar las características que se desean, impidiendo la toma de decisiones sobre otros elementos importantes como son las cardinalidades y los atributos. Por otro lado, la extraccion automática de información de los FMs, también conocida como an´alisis automático de FMs (AAFM) es un tema que ha sido objeto de investigacion en los últimos veinteaños. El AAFM ofrece un amplio catálogo de operaciones de análisis para distintos propósitos. El enfoque general para resolver estas operciones de analisis consiste en dar una semántica operacional en términos de lenguajes declarativos que permiten la extraccion de información por medio de resolutores lógicos. Siguiendo este enfoque se han propuesto hasta la fecha más de 30 operaciones de análisis. Un subconjunto de estas operaciones denominadas explicativas ofrecen la posibilidad de obtener explicaciones sobre las relaciones que provocan determinados errores o las decisiones de usuario conflictivas que deben repararse en una configuración. Sin embargo, de todas las operaciones explicativas propuestas hasta la fecha, solo un subconjunto de ellas dispone de una semantica formal. En este escenario encontramos tres problemas a los que esta tesis se enfrenta: en primer lugar, los FMs no son modelos completamente configurables al impedir la toma de decisiones sobre todos sus elementos. En segundo lugar, es necesario dotar a todas las operaciones explicativas de una semantica formal. En tercer lugar, existe un elevado número de operaciones y la incapacidad de algunas de ellas para trabajar con FMs completamente configurables plantea una necesidad de proponer un nuevo marco de trabajo formal que les de soporte. En este trabajo partimos de dos conjeturas: que existe una correlacion entre determinadas operaciones explicativas y otras no explicativas; y que es posible interpretar ambos tipos de operaciones como problemas de analisis abductivo y deductivo (DAP). Apoyandonos en estas conjeturas, en esta tesis presentamos tres principales contribuciones a fin de resolver los problemas planteados: (i) proponemos los SFMs como modelos completamente configurables, que permiten a los usuarios tomar decisiones sobre todos sus elementos, (ii) el uso de los SFMs y su interpretacion como DAPs nos permite dar una semantica formal al análisis explicativo de una manera compacta, interpretando todas las operaciones propuestas hasta la fecha como casos particulares de dos operaciones de analisis explicativo, (iii) al proponer un nuevo modelo para el análisis, vemos la oportunidad de revisar todo el catálogo de operaciones del AAFM, proponiendo un catalogo simplificado de operaciones y un conjunto de mecanismos de composición que otorga flexibilidad a la hora de definir nuevas operaciones de análisis. Con estas contribuciones, entendemos que este trabajo establece las bases del analisis automático de SFMs (AASFM) que resuelve las limitaciones identificadas en este trabajo para el AAFM y que simplifica el proceso de formalizacion, de implementación y de pruebas de los motores de analisis.

Modeling variability is a major task in developing Software Product Lines (SPLs). Feature Models (FMs) are the most widely used model for this purpose. A FM represents as a hierarchy of features, the set of decisions that users can take to configure their products. To date, these decisions are limited to select and remove features, preventing decisions on other important elements such as cardinalities and attributes. Moreover, the automated extraction of information from FMs, a.k.a Automated Analysis of Feature Models (AAFM) is a thriving topic that has caught the attention of researchers for the last twenty years. The AAFM offers a wide range of analysis operations for different purposes. The general approach to solve these analysis operations is to give an operational semantics in terms of declarative languages that allow the extraction of information by means of logic solvers. Following this approach over 30 operations analysis have been proposed to date. A subset of these transactions so-called explanatory operations offers the possibility of providing explanations for the relationships that cause certain errors or conflicting user decisions to be repaired in a configuration. However, of all proposed explanatory operations to date, only a subset of them has a formal semantics. In this scenario there are three problems that this thesis faces: first, FMs are not fully-configurable since they prevent decisions on any kind of element. Second, it is necessary to endow all the explanatory operations with a formal semantics. Third, there is a large number of analysis operations that do not support fully-configurable FMs. It raises a need to propose a new formal framework for their support. In this work we start from two conjectures: that there is a correlation between explanatory and non-explanatory operations, and it is possible to interpret both types of operations as Deductive and Abductive Problems (DAPs). Relying on these assumptions, in this thesis we present three main contributions in order to solve the raised problems: (i) we propose Stateful Feature Models (SFMs) as fully-configurable models that enable users to make decisions about all of its elements, (ii) the use of SFMs and its interpretation as DAPs allow us to give a formal semantics for explanatory analysis in a compact manner, performing all the operations proposed to date as special cases of two explanatory operations, (iii) as we propose a new model, we see the opportunity to review the entire catalogue AAFM operations, proposing a simplified catalogue operations and a set of composition mechanisms which give flexibility to define new analysis operations. With these contributions, we believe that this work sets the basis for the Automated Analysis of Stateful Feature Models (AASFM) that solves the limitations identified in this work for the AAFM and simplifies the formalisation process and the implementation and testing of the analysis engines.