Reverse Engineering Feature Models with Evolutionary Algorithms: An Exploratory Study

Reverse Engineering Feature Models With Evolutionary Algorithms: An Exploratory Study Roberto E. Lopez-Herrejon 1 , José A. Galindo 2 , David Benavides 2 , Sergio Segura 2 , and Alexander Egyed 1 1 Institute for Systems Engineering and Automation Johannes Kepler University Linz, Austria [email protected], [email protected] 2 Department of Computer Languages and Systems University of Seville, Spain [email protected], [email protected], [email protected] Abstract. Successful software evolves, more and more commonly, from a single system to a set of system variants tailored to meet the similiar and yet dierent functionality required by the distinct clients and users. Software Product Line Engineering (SPLE) is a software development paradigm that has proven eective for coping with this scenario. At the core of SPLE is variability modeling which employs Feature Models (FMs) as the de facto standard to represent the combinations of features that distinguish the systems variants. Reverse engineering FMs consist in constructing a feature model from a set of products descriptions. This research area is becoming increasingly active within the SPLE community, where the problem has been addressed with dierent perspectives and approaches ranging from analysis of conguration scripts, use of propositional logic or natural language techniques, to ad hoc algorithms. In this paper, we explore the feasibility of using Evolutionary Algorithms (EAs) to synthesize FMs from the feature sets that describe the system variants. We analyzed 59 representative case studies of dierent characteristics and complexity. Our exploratory study found that FMs that denote proper supersets of the desired feature sets can be obtained with a small number of generations. However, reducing the dierences between these two sets with an eective and scalable tness function remains an open question. We believe that this work is a rst step towards leveraging the extensive wealth of Search-Based Software Engineering techniques to address this and other variability management challenges. 1 Introduction Successful software evolves not only to adapt to emerging development technologies but also to meet the clients and users functionality demands. For instance, it is not uncommon to nd academic, professional, or community variants of commercial and open source applications such as editing, modelling, programming or many other development tools, where each variant provides dierent functionality. Thus the distinction between variants is described in terms of their features , that we dene as increments in program functionality [1]. In practice, the most common scenario starts with a rst system and forks a new independent development branch everytime a new variant with dierent feature combinations is required. Unfortunately, this approach does not scale as the number of features and their combinations increases even slightly [2]. Software Product Line Engineering (SPLE) is an emerging software development paradigm that advocates a disciplined yet exible approach to maximize reuse and customization in all the software artifacts used throughout the entire development cycle [25]. The driving goal of SPLE is to create Software Product Lines (SPLs) that realize the dierent software system variants in an eective and ecient manner. However, evolving SPLs from existing and invidividuallydeveloped system variants is not an easy endeavor. A crucial requirement is accurately capturing the variability present in SPLs and representing it with Feature Models (FMs) [3,6], the de facto standard for variability modeling. Current research has focused on extracting FMs from conguration scripts [7], propositional logic expressions [8], natural language [9], and ad hoc algorithms [10,11]. Previous work from some of the authors has shown Evolutionary Algorithms (EAs) as an attractive alternative to synthesize FMs that are hard to analyze [1214]. In this paper, we explore the feasibility of using EAs to reverse engineer FMs from the feature sets that describe the system variants and thus help coping with the evolution scenario  from system variants to SPLs  described above. Our study analyzed 59 representative feature sets from publicly available case studies of dierent sizes and complexity. For the implementation of our approach, we used a specic instantiation of the evolutionary algorithm ETHOM [13], integrated into the open source tool BeTTy [12]. We devised two tness functions. With them we identied a trade-o between accuracy of the obtained feature model (the required feature sets vs of the obtained feature sets) and number of generations. That is, proper supersets of the desired feature sets can be obtained with a small number of generations. However, these supersets contain a large surplus of feature sets. In contrast, to reduce such surplus does require more generations. We believe our work is a rst step towards leveraging the extensive wealth of Search-Based Software Engineering techniques to address many pressing variability management challenges. 2 Feature Models and Running Example Feature models are the de facto standard to model the common and variable features of an SPL and their relationships [6], and thus represent the set of feature combinations that the products of the SPL can have. Features are depicted as labeled boxes and are connected with lines to other features with which they relate, collectively forming a tree-like structure. A feature can be classied as: mandatory if it is part of a program whenever its parent feature is also part, and optional if it may or may not be part of a program whenever its parent feature is part. Mandatory features are denoted with lled circles while optional features are denoted with empty circles both at the child end of the feature relations. Features can be grouped into: or relation Fig.1: Video On Demand SPL Feature Model whereby one or more features of the group can be selected, and alternative relation where exactly one feature can be selected. These relations are depicted as lled arcs and empty arcs respectively. Besides the parent-child relations, features can also relate across dierent branches of the feature model in the so called Cross-Tree Constraints (CTC) [15]. The typical examples of this kind of relations are: i) requires relation whereby if a feature A is selected a feature B must also be selected, and ii) excludes relation whereby if a feature A is selected then feature B must not be selected. In a feature model, these latter relations are depicted with doted singlearrow lines and doted double-arrow lines respectively. Additionally, more general cross-tree constraints can be expressed using propositional logic [15]. Figure 1 shows the feature model of our running example, a hypothetical SPL of Video On Demand systems. The root feature of a SPL is always included in all programs, in this case the root feature is VOD . Our SPL also has feature Play which is mandatory, in this case it is included in all programs because its parent feature VOD is always included. Feature Record is optional, thus it may be present or not in our product line members, the same holds for feature PPV (Pay Per View). Feature Display is also mandatory and like features Play and OS (Operating System) they are included in all our programs because their parent, the root, is always included. Features TV and Mobile constitute an alternative relation, meaning that our programs can have either one of them but only one. Similarly, features Aerial and Cable , and features Std (Standard) and Smart are respectively in alternative relations. Notice as well, requires relations between features Smart and Advanced , meaning that if a product contains feature Smart it must also contain feature Advanced . The same is the case between Smart and PPV , and between Cable and PPV . Finally, features Aerial and PPV are in an excludes relation meaning that both cannot be present in the same product. Next we provide a more formal denition of feature sets and their relation with products 3 . 3 Adapted from [15] where feature sets are referred to as congurations. Denition 1. A feature set is a 2-tuple [ sel , sel ] where sel and sel are respectively the set of selected and not-selected features of a product. Let FL be the list of features of a feature model, such that sel , sel ⊆ FL , sel ∩sel = ∅ , and sel ∪sel = FL . Denition 2. A product is valid if the selected and not-selected features adhere to all the contraints imposed by the feature model. For example, the feature set fs=[{VOD, Play, Display, TV, Aerial, OS, Kernel}, {Record, Cable, Mobile, Std, Smart, Advanced, PPV}] is valid. As another example, a feature set with features TV and Mobile is not valid because it violates the constraint of the or relation which establishes that these two features cannot appear selected together in the same conguration. Table 1 depicts the feature sets of our running example VOD SPL of Figure 1. The ticks represent the selected features whereas empty entries represent not selected features. The column headers are abbreviations of the feature names. We reiterate that in this paper we address the problem of reverse engineering feature models out of a lists of feature sets such as that in Table 1. It should be stressed though that a list of feature sets can be denoted by dierent feature models. In other words, the mapping from feature sets to feature models is one- to-many. This characteristic makes EAs specially attractive as dierent potential feature models can be analyzed and ranked according to distinct criteria. Next we present a short description the EAs infrastructure we employed. Table 1: Feature Sets of VOD Software Product Line FSet VOD Play Rec Disp OS TV Mob Sm Std Ker Adv Aer Cab PPV FS1 X X X X X X X X X FS2 X X X X X X X X FS3 X X X X X X X X FS4 X X X X X X X FS5 X X X X X X X X X FS6 X X X X X X X X FS7 X X X X X X X FS8 X X X X X X X X FS9 X X X X X X X X X X FS10 X X X X X X X X X FS11 X X X X X X X X X FS12 X X X X X X X X FS13 X X X X X X X X X X FS14 X X X X X X X X X FS15 X X X X X X X X X FS16 X X X X X X X X FS17 X X X X X X X X X X FS18 X X X X X X X X X 3 Evolutionary Algorithms with ETHOM We relied on the EA tool ETHOM (Evolutionary algoriTHm for Optimized feature Models) to implement our approach [13]. In this section, we present a basic overview of the main characteristics of ETHOM, and in next section we describe how it was applied for reverse engineering feature models. 3.1 Encoding One of the most salient characteristics of ETHOM is its encoding of individuals (i.e chromosomes) which is specically tailored to represent feature models. A feature model is thus represented as an array divided in two parts, one for the tree structure of the feature model and one for its cross-tree constraints. The enconding of the feature model of our running example in Figure 1 is shown in Figure 2. The chromosomes of the structural part of the tree are tuples of the form <PR,CN> where:  PR denotes the type of relationship a feature has with its parent. It can be M for mandatory, Op for optional, Alt for alternative, and Or for or relation.  CN denotes the number of children of the feature. In addition, the order of these tuples is determined by a Depth-First Traversal (DFT) starting from the root. It should also be noted that the root of the feature model is not encoded. For example, the chromosome at entry with DFT value 6, corresponds to feature Mobile that is an alternative ( PR value is Alt ) feature of its parent (feature Display ), and has two children ( CN value is 2), namely Std and Smart . As another example, chromosome at entry with DFT value 11. This chromosome encodes feature Advanced , with an optional relation with its parent feature OS ( PR value is Op ), and with no children ( CN value is 0). The chromosomes of the cross-tree constraints are tuples of the form <TC,O,D> where:  TC encodes the type of cross-tree constraint. An R value denotes a requires constraint whereas an E value denotes an excludes constraint.  O encodes the origin feature of the cross-tree constraint represented with the corresponding DFT value.  D encodes the destination feature of the cross-tree constraint represented with the corresponding DFT value. For example, the tuple <E,4,12> encodes the excludes cross-tree constraint between features Aerial (DFT value 4) and PPV (DFT value 12). As another example, the tuple <R,8,11> encode a requires cross-tree constraint between features Smart (DFT value 8) and Advanced (DFT value 11). Fig.2: ETHOM Encoding of Video On Demand feature model 3.2 Initial Population and Selection There are dierent alternatives in the literature to randomly generate feature models [12,16]. ETHOM uses the following conguration parameters:  Population size.  Number of features.  Percentage of cross-tree constraints.  Maximum branching factor, dened as the maximum number of subfeatures of a feature, considering all the types of relationships.  Percentage of mandatory relations.  Percentage of optional relations.  Percentage of Alternative relations.  Percentage of Or relations. There are multiple alternatives to implement selection in the EA literature [17]. The current version of ETHOM provides roulette wheel and tournament selection [13]. 3.3 Crossover. There are multiple alternatives to implement crossover in the EA literature [17]. The current version of ETHOM provides one-point and uniform crossover [13]. Fig. 3 depicts an example of the application of one-point crossover in ETHOM. The process starts by selecting two parent chromosomes to be combined. For each array in the chromosomes, the tree and CTC arrays, a random point is chosen (so-called crossover point). Finally, the ospring is created by copying the content of the arrays from the beginning to the crossover point from one parent and the rest from the other one. Notice that the characteristics of this encoding guarantee a xed size for the individuals. 3.4 Mutation. ETHOM denes four mutation operators that are applied with the probability set in the conguration. The mutation operators available are: Fig.3: Example of one-point crossover in ETHOM [13].  Operator 1. Changes randomly a relation between two features from one kind to any other kind. For example, from mandatory ( M ) to optional ( Op ) or from Op to Alternative ( Alt ).  Operator 2. Changes the number of children CN , to a number selected from 0 to a maximum branching factor parameter set up in ETHOM.  Operator 3. Changes the type of cross-tree constraint, from excludes to requires and vice versa.  Operator 4. Changes either the origin or destination feature (with equal probability) of a cross-tree constraint. It is checked that the resulting CTC does not have the same origin and destination values. It should be noted that with application of cross-over and mutation operators there is possibility of creating feature models that are not semantically correct. ETHOM provides mechanisms for their identication and repair. For further details, please consult [13]. 4 Applying ETHOM for Extracting Feature Models In this section, we describe the concrete instantiation of ETHOM developed for reverse engineering feature models and how it was used in the experimental setting of our exploratory study. 4.1 ETHOM Conguration Parameters and Fitness Functions Based on our previous experience using ETHOM to generate hard-to-analyze feature models, we set up ETHOM remaining conguration parameters as shown in Table 2. Notice that, as mentioned in Section 3.4, infeasible individuals (i.e. semantically incorrect feature models), are replaced. A crucial decision in our study was selecting an adequate tness function. Overall, our goal is to obtain features models that produce exactly the set of products desired. Unfortunately, existing work on formal analysis of feature models indicates that nding the relations between feature models and their related product specications (e.g. logic representation) can be a hard and expensive computational task [8,15,16]. For this reason, we decided to analyze two tness Table 2: ETHOM conguration parameters Parameter Value selected Selection strategy Roulette-wheel Crossover strategy One-point Crossover probability 0.7 Mutation probability 0.01 Initial population size 100 Infeasible individuals Replace Maximum generations 25 functions, one that focuses on obtaining the desired feature sets disregarding any surplus of feature sets and one that does penalize surplus. We argue that studying both alternatives could provide some insights as to whether the extra cost of computing the penalty would yield a faster (i.e. less number of generations) and more accurate result. Relaxed Fitness Function. The relaxed tness function FFRelaxed maximizes the number of desired feature sets contained in a feature model disregarding any surplus feature sets that the model could denote. FFRelaxed is dened as follows: FFRelaxed(sfs, fm) = |{fs :sfs |validFor(fs, fm)}| Where sfs is the set of desired feature sets, fs is an individual feature set in sfs , fm a feature model, and validFor(fs,fm) is a function that receives a feature model and determines if a given feature set is contained in the set of feature sets represented by the feature model fm 4 . FFRelaxed is maximized to have as many feature sets from sfs as possible. Thus its maximum is the size of the set of desired feature sets sfs . However this function has a shortcomming, namely, that a feature model can contain more feature sets besides those in sfs . An ideal solution would then include all the feature sets in sfs and no more additional feature sets. However, reaching the maximum would not guarantee this. For instance, consider the feature sets of Table 1 and the feature model shown in Figure 1. If we apply FFRelaxed , we will get a value of 18 which is the maximum in this case since this is the number of feature sets we want the feature model to include and in this case this is exactly the set of feature sets represented by the feature model. However, if we change, for instance, the relationship between the root feature ( VOD ) and the feature Play from mandatory to optional, the number of feature sets represented by the feature model quickly raises from 18 to 36 but the value of the tness function would remain the same since all the 18 desired feature sets are included but more 4 For more details on the implementation of function valid please refer to [15]. are also included. The opposite could also eventually happen, i.e. that the feature model includes less feature sets than the ones expected. For instance, imagine that we add an excludes relationship between features Record and Mobile in the feature model of Figure 1. The total number of feature sets represented by the model will be reduced from 18 to 13 (feature sets FS5, FS6, FS13, FS14, and FS17 would not be included). If we apply now FFRelaxed , the result will be 13 not reaching the maximum of the tness function in this case. Strict Fitness Function. The strict tness function FFStrict penalizes having more feature sets than those desired. FFStrict is maximized and its values can range from 0 up to the concrete number of feature sets we want the feature model to have. It is dened as follows: FFStrict(sfs, fm) == 0 : #products(fm)6=|sfs| FFRelaxed(sfs, fm) : #products(fm) = |sfs| Where sfs is the set of desired feature sets and #products(fm) is a function that receives a feature model and returns the number of feature sets it represents 5 . FFStrict returns 0 in the case the number of feature sets represented by the feature model is not equal to the number of desired feature sets and the value of applying FFRelaxed otherwise. A potential shortcomming of this function is that it equally penalizes all feature models that have more feature sets than the number desired, irrespective of how big the dierences are. 4.2 Experimental Setting In order to assess our approach we analyzed case studies from the SPLOT website [18], a publicly available repository of feature models that contains both academic and real-life examples. We selected 59 representative feature models based on their number of features and number of products. The number of products ranged from 1 to 896 and the number of features from 9 to 27. We chose these thresholds so that the tness functions analysed yield results within a reasonable amount of time using the available tooling support. Figure 4 sketches the overall control ow for each selected feature model. First, we used FAMA [19], a tool for the analysis of feature models, to generate the feature sets represented by a given feature model. ETHOM follows a standard EA control ow. Using information gathered from FAMA (e.g. number of features and feature names) the initial population is created. The evaluation takes into account the feature sets of the products we are looking for and a tness function, either FFRelaxed or FFStrict . If the EA nds an individual with the feature sets desired, it records the number of generations along with time elapsed to obtain them and stops. Otherwise, ETHOM then proceeds with the standard selection, crossover and mutation steps before continuing with the evaluation of the new generation. As shown in Table 2, there is also a stop criteria according to the maximum number of generations, 25 generations in our study. 5 Implemented based on function number of products dened in [15].