Automated reasoning on feature models

Automated Reasoning on Feature Models  David Benavides, Pablo Trinidad, and Antonio Ruiz-Cort´es Dpto. de Lenguajes y Sistemas Inform´aticos University of Seville Av. de la Reina Mercedes S/N, 41012 Seville, Spain  benavides, trinidad, aruiz  @tdg.lsi.us.es Abstract Software Product Line (SPL) Engineering has proved to be an effective method for software production. However, in the SPL community it is well recognized that variability in SPLs is increasing by the thousands. Hence, an automatic support is needed to deal with variability in SPL. Most of the current proposals for automatic reasoning on SPL are not devised to cope with extra– functional features. In this paper we introduce a proposal to model and reason on an SPL using constraint programming. We take into account functional and extra–functional features, improve current proposals and present a running, yet feasible implementation. Keywords: Product Lines,Feature Models, Extra–functional Features, Automated Reasoning. 1 Introduction and Motivation Research on SPLs is thriving. Unlike other approaches reuse in SPL has to become systematic instead of ad–hoc. In order to achieve such a goal, SPL practices guide organizations towards the development of products from existing assets rather than the development of separated products one by one from scratch. Thus, features that are shared by all SPL products are reused in every single product. Most of the existing methods [3,6] for SPL engineering agree that a way for modelling SPL is needed. In this context feature models [7,9,11,13,22] have been quoted as one of the most important contributions to SPL modelling [7, pag.82]. As in other cases, first applications in routine productionare stimulating the developmentof a supporting science for improving the production methods [17]. Feature models are used to model SPL in terms of features and relations amongst them. In this type of models, the number of potential products of an SPL increases with the number of features. Consequently, a large number of features lead to SPLs with a largenumberof potentialproducts. Inan extremelyflexibleSPL, whereall featuresmay or may not appear in all potential products, the numberof potential products is equal to 2  , being  the number of features. Moreover, current feature models are only focused on modelling functional features and in the most quoted proposals [7,9,11,13,22] there is a lack of modelling artifacts that deal with extra–functional features (features related  A preliminary version of this paper was presented at [4]. This work was partially funded by the Spanish Ministry of Science and Technology under grant TIC2003-02737-C02-01 (AgilWeb) and PRO-45-2003 (FAMILIES) CAISE 2005 to so–called quality or non–functional features). If extra–functional features are taken into account the number of potential products increases even further. Although it is accepted that in an SPL it is necessary to deal with these extra–functional features [5,11,12], there is no consensus about how to deal with them. Automated reasoning is an ever challenging field in SPL engineering [18,23]. It should be considered specially when the number of features increases due to the increase in the number of potential products. To the best of our knowledge, there are only a couple of limited attempts by Van Deursen et al. and Mannion [8,14] that treat automatic manipulation of feature models. Although those proposals only consider functional features, leaving out extra–functional features. Van Deursen et al. [8] explore automated manipulation of feature descriptions providing an algebra to operate on the feature diagrams proposed in [7]. Mannion’s proposal [14] uses first–order logic for product line reasoning. However it only providesa model based on propositional–logic using   ,  and  logical operators to model SPLs. Both attempts have several limitations: 1. They do not allow to deal with extra–functional features (both attempts leave this work pending). 2. They basically answer to the single question of how many products a model has. 3. As far as we know, they have no available an implementation. In addition, Mannion’s model uses the  (  ) operator to model alternative relations, which is either a mistake or a limitation because the model becomes invalid if more than two features are involved in an alternative relation. The contribution of this paper is threefold. First, we extend existing feature models to deal with extra–functional features. Secondly, we deal with automatic reasoning on extended feature models answering five generic questions, namely   how many potential products a model has   which is the resulting model after applying a filter (e.g. users constraint) to a model,   which are the products of a model,   is it a valid model, and   which is the best product of a model according to a criterion and finally giving an accessible, running implementation. The remainder of this paper is structured as follows. In Section 2, we propose an extension to deal with extra–functional features. In Section 3, we present a mapping to transform an extended feature model into a Constraint Satisfaction Problem (CSP) in order to formalize extended feature models using constraint programming [15]. In Section4,we improvecurrentreasoningonfeaturemodelsand we givesome definitions to be able to automatically answer several questions on extended feature models. In Section 5, we show how our model can be applied to other important activities such as obtaining commonality and variability information. In Section 6, we briefly present a runningprototypeimplementation.Finally, we summarizeour conclusionsand describe our future work in Section 7. 2 Extending Feature Models with Extra–Functional Features 2.1 Feature Models The main goal of feature modellingis to identify commonalitiesand differences among all products of a SPL. The output of this activity is a compact representation of all potential products of an SPL, hereinafter called ”feature model”. Feature models are used to model SPL in terms of features and relations among them. Roughly speaking, a feature is a distinctive characteristic of a product. Dependingon the stage of development, it may refer to a requirement [10], a component in an architecture [2] or even to pieces of code [16] (feature oriented programming)of a SPL. There are several notations to design feature models [7,9,11,13,22]. We found that the one proposedby Czarnecki is the most comprehensibleand flexible as well as being one of the most quoted. Figure 1 depicts a possible feature model of an SPL for the domain of Home Integration Systems (HIS) using Czarneky’s notation. This example is partially inspired by [13]. HIS Supervision systems Control Services fire intrusion flood light control temperature appliances control Video on Demand Internet Conection ADSL Wireless Mandatory Feature Optional Feature Alternative Feature Or Feature Power Line Figure1. Feature model of an SPL in the HIS domain Czarnecki’s notation proposes four relations, namely: mandatory, optional, alternative and or–relation. In these relations, there is always a parent feature and one (in the case of mandatory and optional relations) or more (in the case of alternative and or–relation) child features. – Mandatory:the childfeature inthis relationis always presentin the SPL’s products when its parent feature is present. For example, Every HIS is equipped with   fire and intrusion supervision systems and   light and temperature control. – Optional: the child feature in an optional relation may or may not be present in a product when its parent feature is present. For Example, there are HISs with services and others without them. – Alternative: a child feature in an alternative relation may be present in a product if its parent feature is included. In this case, only one feature of the set of children is present. For example, in a HIS product if an Internet connection is included, then the customer has to choose between an ADSL, powerline or wireless connection, but only one. – Or–relation: the child feature in an or–relation may be present in a product if its parent feature is included. Then, at least one feature of the set of children may be present. For example, in a HIS the products may have Video or Internet or both at the same time. This model includes 32 potential products (you can check this on http://www.tdgseville.info/topics/spl). Examples of them are:   Basic product: consisting of a fire and intrusionsupervisionsystems andlight andtemperaturecontrol.   Fullproduct:a product with all supervision and control features as well as a power line, ADSL or wireless Internet connection. 2.2 Extended Feature Models Current proposals only deal with characteristics related to the functionality offered by an SPL (functional features). Thus, there exists no solid proposal for dealing with the remaining characteristics, also called extra-functional features. There are several concepts that we would like to clarify before analyzing current proposals and framing our contribution: –Feature: a prominent characteristic of a product. Depending on the stage of development,it may refer to a requirement[10] (if productsare requirementdocuments), acomponentin anarchitecture[2] (if productsare componentarchitectures)or even to pieces of code [16] (if products are binary code in a feature oriented programming approach) of an SPL. –Attribute: the attribute of a feature is any characteristic of a feature that can be measured. Availability and cost are examples of attributes of the Service feature of figure 1. Latency and bandwidth may be examples of attributes of an Internet connection. –Attribute domain: the space of possible values where the attribute takes its values. Every attribute belongs to a domain. It is possible to have discrete domains (e.g:integers, booleans, enumerated) or continuous domains (e.g.:real). –Extra–functionalfeature: a relation between one or more attributes of a feature. For instance: bandwidth    Latency  Availability   and so on. These relations are associated to a feature. In figure 1, every feature refers to functional features of the HIS product line so that every product differs because of its functional features. However, every feature of figure 1 may have associated extra–functional features. For instance, considering the services feature, it is possible to identify extra–functional features related to it, such as relations among attributes like availability,reliability, development time, cost and so forth. Likewise the Internet Connection feature can have extra–functional features such as relations among latency or bandwidth. Furthermore, the attributes’ values of extra–functionalfeaturescan differfromoneproductto another.It means, everyproduct not only differs because of its functional features, but because of its extra–functional features too. Consider the full product of the HIS product line example presented formerly with the same functional features. It is possible to offer several products with the same functional features but different extra–functional features, for instance:   High quality full product: a product with full functionality and high quality: high availability and reliability and high cost too.   Basic quality full product: a product with full functionality but lower quality: lower availability and reliability and lower cost too. To date, we havenotfoundanyproposaldealing with functionaland extra–functional features in the same model. However, there are some works in the literature that suggest the need of dealing with extra–functionalfeatures: Kang et. al have been suggesting the need to take into account extra–functional features since 1990 [11, pag. 38] when they depicted a classification of features, although they did not provide a way to do it. Later, in 1998 Kang et. al [12] made an explicit referenceto what they called ’non–functional’ features(a possible type of what wecall extra–functionalfeatures).Howeverthe authors still did not propose a way to solve it. In 2001 Kang et. al [5], proposed some guidelines for feature modelling: in [5, pag. 19], the authors once again made the distinction between functional and quality features and pointed out the need of a specific method to include extra–functional features, but they did not provide this specific method on this occasion either. 2.3 A Notation for Extended Feature Models We propose to extend Czarneki’s feature models with extra–functional features and improve previous vague notations proposed in [20] by allowing relations amongst attributes. Using the HIS example,everyfeature mayhave oneor more attribute relations, for example, the price (  ) and development time (expressed in hours) (     ) taking a range of values in both a discrete or continuous domain (integer or real for example). Thus, it would be possible to decorate the graphical feature model with this kind of information. Figure 2 illustrates a piece of the feature model of figure 1 with extra–functional features with our own notation inspired by [20]. Services Video on Demand Internet Conection ADSL WirelessPower Line DTIME in {1000..2000} DTIME in {1500..2500} DTIME in {3000..4000} PRICE in {100..200} PRICE in {100..200} PRICE in {150..250} DTIME in {18000..25000} PRICE in {80..100} DTIME = POWERLINE.DTIME + ADSL.DTIME + WIRELESS.DTIME PRICE = 20 + POWERLINE.PRICE + ADSL.PRICE + WIRELESS.PRICE DTIME = VIDEO.DTIME + INTERNET.DTIME PRICE = VIDEO.PRICE + INTERNET.PRICE Figure2. Extended feature model for an SPL in the HIS domain In this example, every sub feature of the Service feature has two attributes:  and     . Each of the attributes of leaf features are in a domain of values. For instance, the price of an ADSL connection can range from 100 to 200 1. In the case of parent features, the values of the attributes are the addition of their children values. For example, the price of an Internet connection is the sum of the prices of the possible Internet connections. 3 Mapping Extended Feature Models onto CSP 3.1 Preliminaries Constraint Satisfaction Problems [21] have been object of research in Artificial Intelligence in the last few decades. A Constraint Satisfaction Problem (CSP) is defined as a set of variables, each ranging on a finite domain, and a set of constraints restricting all the values that variables can take simultaneously. A solution to a CSP is an assignment of a value from its domain to every variable, in such a way that all constraints are satisfied simultaneously. We may want to find:   just one solution, with no preference as to which one,   all solutions,   an optimal solution by means of an objective function defined in terms of one or more variables. Solutions to a CSP can be found by searching (systematically) through all possible value assignments to variables. In many real-life applications, we do not want to find any solution but a good solution. The quality of a solution is usually measured by an application dependentfunction called objective function. The goal is to find a solution that satisfies all the constraints and minimize or maximize the objective function, respectively. Such problems are referred to as Constraint Satisfaction Optimization Problems (CSOP), which consist of a standardCSP and an optimizationfunction thatmaps everysolution (completelabelling of variables) to a numerical value. These are some basic definitions of what a CSP is. Definition 1 (CSP). A CSP is a three–tuple of the form      where     is a finite set of variables,     is a finite set of domains (one for each variable) and  is a constraint defined on  . Consider, for instance, the CSP:                        Definition 2 (Solution). Let  be a CSP, a solution of  is whatever valid assignment of all elements in  as satisfies  . In the previous example, a possible solution is    since it verifies that    . Definition 3 (Solution space).Let  be a CSP of the form      , its solution space denoted as     is made up of all its possible solutions. A CSP is satisfiable if its solution space is not empty.                        1these values are just illustrative, they may have nothing to do with real values Inthe previousexample,there are eightsolutions.The only assignment that doesnot satisfy     is    . Nevertheless, if we replace the constraint with      , then the CSP is not satisfiable. Definition 4 (CSOP). A CSOP is a four–tuple of the form       where  ,  and  stand for a CSP and  is a real function defined on D. Consider, for instance, the CSOP:                         Definition 5 (Optimum space). Let  be a CSOP of the form       , its optimum space denoted as      is made up of all solutions that maximize or minimize  .                                                                     In the previous example,               . 3.2 The Mapping In [1] we presented an algorithm to transform an extended feature model into a CSP. The mapping between a feature model and a CSP has the following general form:   the features make up the set of variables,   the domain of each variable is the same:       ,   extra–functionalfeatures are expressed as constraints and   every relation of the feature model becomes a constraint among its features in the following way: –Mandatory relation: Let  be the parent and   the child in a mandatory relation , then the equivalent constraint is:     –Optional relation: Let  be the parent and   the child in an optional relation, then the equivalent constraint is:     –Or–relation: Let  be the parent in an or–relation and         the set of children, then the equivalent constraint is:           . –Alternative relation: Let  be the parent of an alternative relation and and         the set of children, then the equivalent constraint is:                                                       There may be several different algorithms to map extendedfeature models. The one presented in [1] is a possible one. Hereinafter, we refer to the equivalent CSP resulting from the mapping as   . Using this mapping, constraints for functional and extra– functional features can be handled together. Thus, table 1 shows the equivalent constraints for figure 1 with the extra–functional features of figure 2. Constraints of extra– functional features are denoted by an asterisk.            and       extra–functional features are not shown for lack of space as they are very similar to the  .ones. Relation   HIS 1        HIS 2           HIS 3         SUPERVISION 1              SUPERVISION 2         SUPERVISION 3        CONTROL 1             CONTROL 2           CONTROL 3              SERVICES 1             SERVICES *                                                            VIDEO *                                                    INTERNET 1                                                                        INTERNET *                                                                                                         Table 1. A trace of the algorithm presented in [1] for HIS example 4 Automated Reasoning on Extended Feature Models Since we go toward automated reasoning on feature models, a formal model of SPL becomes necessary. We propose to use Constraint Programming to reason on extended features models. Our model is able to answer the following questions: 4.1 Number of products One of the questions to be answered is how many potential products a FM contains. This is a key question in SPL engineering because if the number of products increases the SPL becomes more flexible as well as more complex. Definition 6 (Cardinal). Let  be an extended feature model, the number of potential products of  , hereinafter cardinal, is equal to the solution number of its equivalent CSP   .             In the HIS example of figure 1    !"  , simply by adding for example a new service like Radio Streaming, the number of potential products raises to 64. Likewise adding the attributes of figure 2    !"    4.2 Filter There should be a way to apply filters to the model. These filters can be imposed by the users. A filter acts as a limitation for the potential products of the model. A typical application of this operation occurs when customers are looking for a product with a specific set of characteristics, that is, they are not interested in all potential productsbut in some of them only (those passing the filter). Definition 7 (Filter). Let  be an extended feature model and # a constraint representing a filter, the filtered model of   , hereinafter filter, is equal to   adding the constraint # .    #     #  A possible filter for the HIS example would be to ask for all products with video on demand, making the number of potential products decrease from 32 to 16. It is also possible to apply filters to attributes. For example, it would be possible to ask for all products whose prices are lower than 200, 12then                       (when any filter is imposed, it decreases from 260 to 44). 4.3 Products Once   is defined, there should be a way to get the solutions of the model, that is the products of   . Definition 8 (Products). Let  be an extended feature model, the potential products of the model  , hereinafter products, is equal to the solutions of the equivalent CSP   . $               In the HIS example we would want to get all the possible products of the model or even apply a filter and then get the products. Thus     HIS,VIDEO = true  and $              VIDEO=true   . 4.4 Validation A valid extended feature model is a model where at least one product can be selected. That is, a model where   has at least one solution. Definition 9 (Valid model). A feature model  is valid if its equivalent CSP is satisfiable.      $        