Consistency maintenance for evolving feature models

Consistency maintenance for evolving feature models Jianmei Guo a, ⇑ , Yinglin Wang a , Pablo Trinidad b , David Benavides b a Department of Computer Science and Engineering, Shanghai Jiao Tong University, 800 Dong Chuan Road, Minhang, Shanghai 200240, China b Department of Languages and Computer Systems, University of Seville, Av. Reina Mercedes s/n, 41012 Seville, Spain Keywords: Software product lines Feature models Evolution Consistency maintenance Ontology Semantics abstract Software product line (SPL) techniques handle the construction of customized systems. One of the most common representations of the decisions a customer can make in SPLs is feature models (FMs). An FM represents the relationships among common and variable features in an SPL. Features are a representation of the characteristics in a system that are relevant to customers. FMs are subject to change since the set of features and their relationships can change along an SPL lifecycle. Due to this evolution, the consistency of FMs may be compromised. There exist some approaches to detect and explain inconsistencies in FMs, however this process can take a long time for large FMs. In this paper we present a complementary approach to dealing with inconsistencies in FM evolution scenarios that improves the performance for existing approaches reducing the impact of change to the smallest part of an FM that changes. To achieve our goal, we formalize FMs from an ontological perspective and define constraints that must be satisfied in FMs to be consistent. We define a set of primitive operations that modify FMs and which are responsible for the FM evolution, analyzing their impact on the FM consistency. We propose a set of predefined strategies to keep the consistency for error-prone operations. As a proof-of-concept we present the results of our experiments, where we check for the effectiveness and efficiency of our approach in FMs with thousands of features. Although our approach is limited by the kinds of consistency constraints and the primitive operations we define, the experiments present a significant improvement in performance results in those cases where they are applicable. 1. Introduction Software product line (SPL) engineering has emerged as one of the most promising software development paradigms for reducing development costs, enhancing quality, and shortening time to market (Clements & Northrop, 2001; Pohl, Bockle, & van der Linden, 2005; Sugumaran, Park, & Kang, 2006). An SPL is ‘‘a set of software-intensive systems that share a common, managed set of features satisfying the specific needs of a particular market segment or mission and that are developed from a common set of core assets in a prescribed way’’ (Clements & Northrop, 2001). Features are essential abstractions of product characteristics relevant to customers and are typically increments in product functionality (Benavides, Segura, & Cortes, 2010; Kang, Lee, & Donohoe, 2002). Every product or system of an SPL is represented by a unique combination of features. All the products in an SPL are usually captured in feature models (FMs) which describe the commonalities and variabilities of systems in terms of features (Kang, Cohen, Hess, Novak, & Peterson, 1990; Kang et al., 2002). An FM is a tree-like structure that contains the relationships among features in a hierarchical manner. Relationships can be of different kinds to remark which are the choices a customer can make to build a customized product. As any other software systems, SPLs are subject to changes and evolution along their lifecycle. Those changes can affect FMs (Sugumaran et al., 2006). Even small changes to an FM could unintentionally break its consistency (Guo & Wang, 2010; Thum, Batory, & Kastner, 2009). Here, the consistency of an FM means that it remains well-formed (syntactic consistency) and it defines at least a valid product (semantic consistency). For example, the removal of a single feature from an FM, although could be valid from the point of view of FM syntax, could invalidate other related features, which must also be removed to make the resulting FM consistent. Inconsistency usually comes from contradictory constraints which impede producing any valid product (von der MaBen & Lichter, 2004). Consistent FMs are needed to any further steps in SPL engineering such as verifying product derivation (Lutz, 2008) or checking for the consistency of product requirements (Lauenroth & Pohl, 2008). Therefore, guaranteeing the FM consistency is a mandatory task in SPL development. Many approaches have been proposed to automate the detection of inconsistencies in FMs (Benavides et al., 2010). They mostly ⇑ Corresponding author. Tel.: +86 21 34204415; fax: +86 21 34204728. E-mail addresses: guojianm[email protected].cn (J. Guo), [email protected] (Y. Wang), [email protected] (P. Trinidad), [email protected] (D. Benavides). use SAT (Batory, 2005; Thum et al., 2009), BDD (Czarnecki & Wasowski, 2007), or CSP solvers (Benavides, Martin-Arroyo, & Cortes, 2005; Trinidad, Benavides, Duran, Ruiz-Cortes, & Toro, 2008) to automate the checking process. However, these approaches suffer from an NP-hard problem of feature combinatorics and take a long time to perform with large FMs (Batory, Benavides, & Ruiz-Cortes, 2006). Reports from industry have shown that practical FMs could have hundreds or thousands of features (Loesch & Ploedereder, 2007; Steger et al., 2004), so existing approaches can take hours or days to detect inconsistencies. Moreover the information obtained from these detection mechanisms hardly assists domain analysts to resolve inconsistencies in FMs. Existing approaches delegate the reparation of inconsistent FMs to domain analysts who must use their experience to find the best way to repair those FMs. The impact of performance and manual reparation gets worse since FMs frequently change during their evolution processes and the consistency of the resulting FMs has to be checked after every change. This paper approaches the problem of consistency maintenance in FMs focusing on the changes since last version of an FM rather than checking the overall consistency of the resulting FM. We assume that the initial FM is consistent and study if a requested change affects the consistency or not. In case an inconsistency is detected, a set of additional operations are executed to restore the consistency of the FM. For example, the removal of a single feature Xfrom an FM initially only affects those features that are directly connected to it. To restore the consistency, the surrounding relations of feature Xare removed. What if the removal of a relationship generates a new inconsistency? In the worst case, the operation derivation could propagate to the whole FM; but in most cases it only affects a limited range, that is where the main improvement in performance comes. Our approach relies on ontology, which is a formal and explicit specification of a shared conceptualization of a domain of interest (Gruber, 1993). In our case we formalize FMs in Section 3, defining the primitive elements of FMs and the syntactical and semantic consistency constraints as the well-formedness rules of FMs. From this formalization, in Section 4we obtain a set of primitive operations (Guo & Wang, 2010) which can represent any modification of an FM. In Section 5we apply and extend techniques from ontology evolution (Haase & Stojanovic, 2005; Stojanovic, 2004) to propose a systematical approach to consistency maintenance for evolving FMs. A dependency matrix, indicating the cause and effect relationships between changes, is built for supporting the derivation of additional operations from the requested change. Then we analyze the possible evolution strategies for all the primitive operations on FMs and propose a sequence of interdependent operations derived from the requested change to produce a unique consistent FM. To demonstrate the realization of our approach, Section 6presents the implementation of our approach based on FeatureIDE. 1 Section 7evaluates our approach by experiments on randomly generated FMs with thousands of features. Section 9briefly analyses the pros and cons of our approach and presents some future extensions of our work. In order to introduce the readers in the context of our work, we complement our work with a brief definition of FMs in Section 2 and a discussion about the related work in Section 8. 2. Feature models background In 1990, Kang et al. (1990) first proposed the original FMs (a.k.a. FODA FMs). An FM is organized hierarchically and is graphically depicted as an AND-OR feature diagram (Kang et al., 1990). Cross-tree constraints are used to represent non-hierarchical composition rules comprising mutual dependency (requires) and mutual exclusion (excludes) relationships (Kang et al., 1990). Czarnecki, Helsen, and Eisenecker (2005) proposed cardinality-based FMs where cardinalities (a.k.a. multiplicities) were introduced. Batory (2005) and Thum et al. (2009) distinguished among terminal (or concrete) and non-terminal (or compound or abstract) features. By integrating former definitions of FMs (Batory, 2005; Czarnecki et al., 2005; Kang et al., 1990; Thum et al., 2009), we adopt the notation as shown in Fig. 1, which is a partial FM for the Home Integration Systems (HIS) SPL inspired from (Benavides et al., 2005; Kang et al., 2002). An FM is a tree of features. Every node in the tree has one parent except the root feature (‘r: HIS’). A terminal feature (e.g., ‘f4’) is a leaf and a non-terminal feature (e.g., ‘f1’) is an interior node of a feature diagram (Batory, 2005; Thum et al., 2009). Connections between a feature and its group of children are classified as And- (e.g., ‘f1’, ‘f2’, and ‘f3’), Or- (e.g., ‘f10’ and ‘f11’), and Alternative-groups (e.g., ‘f12’, ‘f13’, and ‘f14’). The members of And-groups can be either mandatory (e.g. ‘f1’) or optional (e.g. ‘f3’). Or-groups and Alternative-groups have their own cardinalities (Czarnecki & Wasowski, 2007). Cross-tree constraints comprise requires and excludes relationships (Kang et al., 1990), e.g., ‘f4 requires f7’. Table 1 summarizes the semantics of FMs in propositional formulas. Prepresents a non-terminal feature and C 1 ,...,C n are its child features. If the child features forms an And-group, then M#{1,...,n} denotes the mandatory features by their index. If a feature is selected, so too is its parent. If the parent is selected, all of its mandatory children of an And-group are selected; in Or-groups, at least one child must be selected, and in Alternative-groups, exactly one child is selected. Using the rules given in Table 1, an FM can be easily translated into a propositional formula with a variable for each feature. 3. Ontology-based formalization and consistency constraints 3.1. An ontology-based formalization of FMs The representational primitives defined in ontology (Gruber, 2008) are typically concepts (classes) and properties. Each property must have at least one domain concept, while its range may either be a literal (attributes), or a set of at least one concept (relations). The definitions of the representational primitives include information about their meaning and constraints on their logically consistent application, which makes ontology work at the semantic level. Based on the ontology structure and the application context of FMs, we formalize FMs as follows. Definition 1. An FM is defined as a 5-tuple: FM ¼ðC;R;A;Domain;RangeÞ where: C(–;) is the set of concepts in the FM. C=F[FG.F(–;) is the set of features in the FM. FG (–;) is the set of feature groups. FG =FG AN [FG AL [FG OR .FG AN is the set of And-groups; fg AN is an element of FG AN , i.e., an And-group. FG AL is the set of Alternative-groups. FG OR is the set of Or-groups. (1) F={root}[NF [TF. root is the root feature. NF (–;) is the set of non-terminal features. TF (–;) is the set of terminal features. (2) F={root}[F AN [F AL [ F OR .F AN ,F AL , and F OR denote the set of features in all And-groups, in all Alternative-groups, and in all Or-groups respectively. Take the FM shown in Fig. 1 for example, root =‘‘r’’; ‘‘f1’’ 2NF;‘‘f4’’ 2TF;fg AN 1 = {‘‘f1’’,‘‘f2’’,‘‘f3’’}, fg AN 12FG AN ;FG AL = {‘‘fg AL 1’’},fg AL 1 = {‘‘f12’’,‘‘f13’’,‘‘f14’’}. F OR =fg OR 1 = {‘‘f10’’,‘‘f11’’}. 1 http://wwwiti.cs.uni-magdeburg.de/iti_db/research/featureide. Ris the set of relations in the FM. R=Parent [Req [Excl.Parent #FFreturns the parent of a given feature. It also forms an acyclic relation called feature hierarchy.If(f1,f2) 2Parent, then f1 is a child of f2, f2 is the parent of f1. Parent ⁄ is the reflexive, antisymmetric, and transitive closure of Parent.Req #FFencodes the F–F requires constrains; Excl #FFencodes the F–F excludes constrains. For example, (‘‘f1’’,‘‘root’’) 2Parent; (‘‘f4’’,‘‘f7’’) 2Req. Ais the set of attributes in the FM. A=Opt [Mincard [Maxcard. Opt :F AN !Bdenotes the optionality of a given feature in an And-group, B¼ftrue;falseg.IfOpt(f) returns true, fis optional, otherwise mandatory. For example, Opt(‘‘f3’’) = ‘‘true’’. Mincard : FG AL [FG OR !N 0 and Maxcard :FG AL [FG OR !N 0 [f1g return the cardinality for a given Oror Alternative-group. For example, Mincard(‘‘fg OR 1’’) = ‘‘1’’,Maxcard(‘‘fg OR 1’’) = ‘‘2’’. Domain:R[A?2 C and Range:R[A?2 C [Lgive the set of domain (2 C ) or range (2 C [L) for some relation r(2R) or some attribute a(2A). Here, Ldenotes literal values of attributes. For example, Domain(Req(f4,f7)) = {f4}, Range(Req(f4,f7)) = {f7}; Domain(Opt(f3)) = {f3}, Range(Opt(f3)) = {true}. 3.2. Consistency constraints of FMs We summarize 13 consistency constraints of FMs in terms of the syntax and semantics of FMs. These consistency constraints form a feature consistency model (FCM): FCM ¼fCC i ;16i613g: The following set of constraints is by no means an exhaustive list of consistency constraints for FMs, but it lays a foundation for constructing and maintaining a consistent FM. We can define a decision function consistency(FM) to judge whether a given FM is consistent or not. consistencyðFMÞ¼ true;if an FM conforms to the FCM false;otherwise  3.2.1. Syntactical consistency constraints Schobbens, Heymans, and Trigaux (2006), Schobbens, Heymans, Trigaux, and Bontemps (2007), Metzger, Heymans, Pohl, and Saval (2007) defined a formal semantics of FMs and several well-formedness rules of FMs based on Free Feature Diagrams (FFD). We extend their well-formedness rules and summarize 10 syntactical consistency constraints (CC 1 –CC 10 ) based on the ontology-based formalization of FMs. CC 1 (Distinct Identity Constraint). Every concept has a distinct identity: ðNF \TF \frootg¼;Þ^ðFG AN \FG AL \FG OR \frootg ¼;Þ^ðF AN \F AL \F OR \frootg¼;Þ: CC 2 (Feature Hierarchy Constraint). The feature hierarchy is a directed acyclic graph: :9f2Fðf;fÞ2Parent  : CC 3 (Root Constraint). There is a unique feature root 2Fthat is the direct or indirect parent of all other feature in F. 9root 2Fð8f12Fnfrootgðf1;rootÞ2Parent  Þ ^ ð:9f2 2Fðroot;f2Þ2Parent  Þ: CC 4 (Feature-Closure Constraint). Every feature except root has one parent feature: 8f12Fnfrootg9f22Fðf1;f2Þ2Parent: The constraint CC 4 prevents the existence of the orphaned features. For example, the removal of the Parent relationship between the feature ‘‘f1’’ and the feature ‘‘r’’ in Fig. 1 would cause no parent feature to be defined for the feature ‘‘f1’’ any longer, which has to be prevented or resolved. CC 5 (Relation-Closure Constraint). Any relation (2R) must be built between two legal features: 8f18f2ðf1;f2Þ2R!f12F^f22F: r: HIS f1: Detection (Det) f2: Monitor (Mon) f3: Service f4: Fire Det f5: Intrusion Det f6: Flood Det f7: Smoke Mon f8: Motion Mon f9: Moisture Mon f11: Video on demand f10: Internet connection f13: ADSL f14: Wirelessf12: Power Line Mandatory feature Alternative-group Or-group f4 requires f7. f5 requires f8. f6 requires f9. Constraints: And-groupNon-terminal feature Terminal feature Optional feature [1..n] Cardinality [1..1] [1..2] Fig. 1. A partial FM for the HIS SPL. Table 1 FM Semantics in propositional formulas. FM primitives Semantics Optional child C 1 ?P Mandatory child C 1 MP And-group (P?V i2M C i )^(W 16i6n C i ?P) Or-group PMW 16i6n C i Alternative-group P$W 16i6n C i  ^V i<j ð:C i _:C j Þ f1 requires f2f1?f2 f1 excludes f2:ðf1^f2Þ CC 6 (Attribute-Closure Constraint). Any attribute (2A) must be built between a legal features and a literal value (2L): 8f18lðf1;lÞ2A!f12F^l2L: The constraints CC 5 and CC 6 demand that any relation (2R)or any attribute (2A) must be established only between two right objects. For example, the addition of the Req relationship between the features ‘‘f8: Motion Monitor’’ and ‘‘Camera Surveillance’’ would provoke an inconsistency because the latter is not yet defined as a legal feature (2F). CC 7 (Domain-Closure Constraint). The Domain concept can be established between a relation and a concept or between an attribute and a concept: 8c8ra c2DomainðraÞ!c2C^ðra 2R[AÞ: CC 8 (Range-Closure Constraint). The Range concept can be established between a relation and a concept or between an attribute and a literal: 8cl 8ra cl 2RangeðraÞ!ðcl 2C^ra 2RÞ_ðcl 2L^ra 2AÞ: CC 9 (Cardinality-Closure Constraint). Cardinality must be specified for Alternativeor Or-groups: 8fg MincardðfgÞ_MaxcardðfgÞ!fg 2FG AL [FG OR ; CC 10 (Cardinality Constraint). Cardinality must be well-formed: 8fg 2FG AL MincardðfgÞ¼1^MaxcardðfgÞ¼1; 8fg 2FG OR MincardðfgÞP1^MincardðfgÞ6MaxcardðfgÞ 6kfgk: The constraints CC 9 and CC 10 reflect cardinality-based feature modeling (Czarnecki et al., 2005). They formulate the Alternative-group and Or-group relationships through a set of wellformed rules about cardinality. 3.2.2. Semantic consistency constraints von der MaBen and Lichter (2004) presented four situations that lead to semantic inconsistencies in FMs: (1) exclusion between full-mandatory features; (2) exclusion between relativefull-mandatory features; (3) implication between alternative child features; (4) exclusion and implication. We extend their work and introduce two concepts. Definition 2 (Mandatory path). We define a path between a mandatory feature Xand the root feature in an FM as a mandatory path MandPath (X) where every intermediate node (feature) is either a mandatory feature in an And-group or the sole child in an Alternativeor an Or-group. Definition 3 (Requires chain). Due to the transitivity of the Req relationship, we define a chain from the start node (feature) Sto the end node Tas a requires chain ReqChain(S,T) where all nodes are connected by the Req relationship to each other. Thus the first two inconsistent situations presented by von der MaBen and Lichter (2004) are merged and extended to the exclusion between any two features in one same or two different mandatory paths. Their fourth inconsistent situation (von der MaBen & Lichter, 2004) is extended to the exclusion between any two features in a requires chain. Examples of extended inconsistencies of FMs are shown in Fig. 2. Correspondingly, we summarize three semantic consistency constraints (CC 11 –CC 13 ) as follows. CC 11 (Excl-MandPathConstraint). Any twofeatures in one same or two different mandatory paths of an FM cannot have the Excl relationship. Counter examples are shown in Fig. 2(a). 8 f1;f2;X;Y2F :9ðExclðf1;f2Þ^ðf12MandPathðXÞ^ðf22 MandPathðXÞ_f22MandPathðYÞÞÞÞ. CC 12 (Req-Alternative Constraint). Any two child features in an Alternative-group cannot have the Req relationship. A counter example is shown in Fig. 2(b). 8 fg AL 2FG AL  8 f1;f22fg AL  :9ðReqðf1;f2Þ_Reqðf2;f1ÞÞ. CC 13 (Excl-ReqChain Constraint). Any two features in a requires chain cannot have the Excl relationship. A counter example is shown in Fig. 2(c). 8 f1;f22F :9ðReqChainðf1;f2Þ^ ðExclðf1;f2ÞÞÞ. 4. Changes to feature models Based on the above formalization of FMs, we can easily obtain the primitive elements of FMs, which include concepts (non-terminal features,terminal features,feature groups), relations (parent,requires,excludes) and attributes (name,group type,optionality, cardinality) of FMs. Since each primitive element of FMs can be changed by one of the meta-change transformations (Huersch, 1997; Rundensteiner, Leem, & Ra, 1998), we suggest a set of primitive operations on FMs in Table 2 (Guo & Wang, 2010). These operations are defined by the cross product of the set of FM primitive elements and the set of meta-changes (‘Add’, ‘Remove’, and ‘Set’). They represent the changes to FMs at the lowest level of complexity and can compose various complex change operations such as the 16 operations for refactorings and generalizations of FMs (Alves et al., 2006) and the 5 operations for arbitrary edits to FMs (Thum et al., 2009). Further, we formalize changes to FMs as follows. Definition 4. A change to FMs Ch is a 4-tuple: Ch ¼ðname;args;preconditions;postconditionsÞ where: name is the identifier of a change. Table 2 lists all the names of primitive operations. In the following chapters, we simplify the notation of changes as name (args). args 2(C[R[A[L) n ,1 6n63, is a list of one or more change arguments. A change could have one, two, or three arguments. Take the FM shown in Fig. 1 for example, to remove the non-terminal feature ‘‘f1’’ from the FM, the change RevNF has only one argument ‘‘f1’’. To modify the name of the node ‘‘r’’, the change SetName(‘‘r’’, ‘‘Home Integration Systems’’) is applied. The change AddRL(‘‘rl4–7’’, ‘‘f4’’, ‘‘f7’’) is applied to add a requires link ‘‘rl4–7’’ between the features ‘‘f4’’ and ‘‘f7’’. Preconditions of a change comprise a set of assertions that must be true to be able to apply the change. If a precondition fails, a change is never performed. For example, the precondition for RevNF(‘‘nf’’) is nf 2NF. (a) (b) (c) Fig. 2. Examples of semantic inconsistencies of FMs. Postconditions of a change comprise a set of assertions that must be true after applying a change. They describe the effect of a change. For example, the postcondition for RevNF(‘‘nf’’) is nf RNF. For example, a full definition of the change RevNF can be as follows: Change Remove non-terminal feature Syntax RevNF(‘‘nf’’) Semantics Remove a non-terminal feature ‘‘nf’’ from an FM Preconditions nf 2NF Postconditions nf RNF Similarly, the preconditions and postconditions for other changes can also be deduced according to general logical constraints and the consistency constraints defined above. Two decision functions are defined as follows: preconditionsðFM;ChÞ¼ true;if an FM satisfies the preconditions of a Ch false;otherwise 8 > < > : postconditionsðFM;ChÞ¼ true;if an FM satisfies the postconditions of a Ch false;otherwise 8 > < > : 5. Semantics of change The evolution of FMs can be seen as a sequence of interdependent changes to FMs (Guo & Wang, 2010). Such changes are composed of a set of primitive operations defined in Table 2.A change to FMs can be seen as a mapping between FMs. As shown in Fig. 3, given an FM and a requested change Ch, the application of the change Ch to the FM results in another FM 0 , i.e., FM 0 =Ch(FM), under preconditions(FM,Ch)=true ^postconditions(FM 0 ,Ch)=true. Since the application of a single change will not always leave an FM in a consistent state, it often derives a series of additional changes. Hence, the resolution of the requested change requires obtaining and executing these derived changes to maintain the consistency of the FM. Thus: Definition 5. Given an FM and a requested change Ch, the semantics of change to FM is defined as: SemanticsOfChangeðFM;ChÞ¼ðCh 1 ;...;Ch i ;Ch iþ1 ;...;Ch n1 Þ where: FM is a given consistent FM, i.e., consistency(FM)= true; Ch is a requested change that can be applied to the FM, i.e., preconditions(FM,Ch)=true; FM 1 =Ch(FM) is an FM representing the result of applying the requested change Ch to the FM, i.e., postconditions(FM 1 ,Ch)=true; Ch i ,16i6n1, is a derived change that satisfies the following set of conditions: –FM i+1 =Ch i (FM i ), which implies that preconditions(FM i ,Ch i )= true and postconditions(FM i+1 ,Ch i )=true; –consistency(FM i )=false,16i6n1, and consistency(FM n )= true. Thus, as shown in Fig. 4, the final result of applying and resolving the requested change Ch to the FM is the FM 0 : FM 0 ¼FM n ¼Ch n1 ð...Ch iþ1 ðCh i ð...Ch 1 ðChðFMÞÞÞÞÞ: Next, how to find and organize these derived changes that resolve the requested change and maintain the consistency of the FM? It is impractical to demand for domain analysts to track down and keep in mind all the changes that are pending. Hence, we adopt the procedural approach (Stojanovic, 2004) to realize the task automatically. The procedural approach comprises five steps (Stojanovic, 2004): first, a request is represented as a series of primitive operations defined in Table 2; second, the illegal operations are prohibited by checking the preconditions of each Table 2 Primitive operations on FMs. Fig. 3. Applying a change Ch to an FM. operation; third, additional operations are derived from the requested operations for keeping consistency; fourth, the execution order of the requested and derived operations is determined; fifth, all the confirmed operations are applied to the FM. Among the above steps, the third and the fourth steps are the key to consistency maintenance of FMs, other steps are straightforward. Hence, we explain how to implement the two steps as follows. 5.1. Dependency matrix We analyze the cause and effect relationship between primitive operations on FMs and build the dependency matrix to conduct the derivation of additional operations from a requested operation. As shown in Table 3, the rows and columns of the matrix list all the primitive operations defined in Table 2. If an element of the matrix Table 3 The dependency matrix Dependency[i][j]. Fig. 4. The semantics of change to an FM. (a) (b) Fig. 5. Operation templates generated by the dependency matrix. (a) The general operation template for resolving the change RevNF. (b) A concrete template for resolving the change RevNF(‘‘f10’’) in the FM shown in Fig. 1. Dependency[Ch i ][Ch j ] is blank, it means that the operation Ch i that is assigned to the row ican never induce the operation Ch j denoting the column j. Otherwise, the operation Ch i could generate the operation Ch j when their necessary preconditions and postconditions are fulfilled. The symbol ‘‘X’’ is used as the replacement for all the conditions. Most of the cause and effect relationships between primitive operations are deduced in terms of the consistency constraints defined in the FCM. The principles for generating the dependency matrix are as follows. First, an operation on a concept would affect the related attributes and relations of the concept. For example, since the RevNF operation causes the removal of all ‘‘edges’’ pointing to the feature or from it, the operations ‘‘RevPL’’,‘‘RevRL’’, and ‘‘RevEL’’ are triggered. Second, an operation on an attribute such as the operations ‘‘SetName’’, ‘‘SetOpt’’, and ‘‘SetCard’’ do not initiate additional operations because they do not affect other elements but their own literal values. However, the operation ‘‘SetGT’’ is a special case because it would affect the logical structure of some feature group and thus could cause the operations ‘‘SetOpt’’ and ‘‘SetCard’’. According to the dependency matrix, an operation would cause a set of additional operations. Further, each of these derived operations would cause another set of operations. Such operation derivation continues to propagate until there is no more new derived operations. All of these derived operations can form a general operation template for resolving a certain operation. Fig. 5(a) shows a general multilevel operation template for resolving the change RevNF. The general template would be trimmed as a concrete template when applying to a practical scenario and its operations would be parameterized. Fig. 5(b) demonstrates a concrete operation template for resolving the change RevNF (‘‘f10’’) in the FM shown in Fig. 1. The execution order indicated by the sequence number does not matter very much, but we often handle the operations from outer level to inner and aggregate similar operations. 5.2. Evolution strategy Most of the primitive operations on FMs can be directly resolved based on the operation templates generated by the dependency matrix. For example, all of the ‘‘Add’’ and ‘‘Set’’ operations defined in Table 2 can be executed straightforwardly once domain analysts determine right parameters. The operations ‘‘RevRL’’ and ‘‘RevEL’’ can also be executed directly. However, the other four ‘‘Remove’’ operations cannot be resolved automatically by the dependency matrix and often need extra decision making by domain analysts. For example, after executing the operations ‘‘RevFG’’ or ‘‘RevTF’’, domain analysts must determine how to handle those non-terminal features at leaf position. Executing the operations ‘‘RevNF’’ or ‘‘RevPL’’ is more complex because domain analysts must determine how to handle the remaining orphaned part of the resulting FM. For these four operations, the operation templates often provide multiple choices, e.g., the step 7 in Fig. 5(a) and the step 5 in Fig. 5(b). Therefore, evolution strategies are introduced to direct how to execute these operation and their derived operations resulting not in an arbitrary consistent state. An evolution strategy unambiguously defines the way in which a change will be resolved. It generally formulates an ordered sequence for the requested change and its derived changes, i.e., the sequence ‘‘Ch,Ch 1 ,...,Ch i1 ,Ch i ,...,Ch n1 ’’ shown in Fig. 4. Take the operation ‘‘RevNF’’ for example, there are three evolution strategies: removing all children, reconnecting all children to its parent, reconnecting all children to another non-terminal feature. Fig. 6 demonstrates the three evolution strategies for resolving the change RevNF (‘‘f10’’) in the FM shown in Fig. 1. Domain analysts can choose a particular evolution strategy in order to tailor the evolution of FMs to suit their needs. Resolving the operation ‘‘RevPL’’ can also apply these three evolution strategies. Resolving the operations ‘‘RevFG’’ and ‘‘RevTF’’ often needs adding additional features as terminal features. In addition, two evolution strategies are used for resolving the ‘‘RevTF’’ or ‘‘RevNF’’ operations on the Req links. As shown in Fig. 7, for the situation (b), i.e., ‘‘f1requires f2’’, ‘‘f2’’ cannot be removed arbitrarily. In this case, domain analysts would be warned that the requested change could be an illegal operation. If domain analysts confirm the requested change, then they can first remove the link ‘‘Req(f1,f2)’’ and then remove the feature ‘‘f2’’. 6. Implementation We implemented our approach 2 based on FeatureIDE, which is an open-source Eclipse-based IDE that supports building program (a) (b) (c) (d) Fig. 6. Three evolution strategies for resolving the operation ‘‘RevNF’’. (a) Applying the RevNF(‘‘f10’’) alone to the FM shown in Fig. 1. (b) All children are removed. (c) All children are reconnected to the parent. (d) All children are reconnected to another non-terminal feature. (a) (b) Fig. 7. Two evolution strategies for removing a feature in a Req link. (a) Remove the domain. (b) Remove the range. 2 An implementation of our approach is available in http://code.google.com/p/ fmconmain/. J. Guo et al. / Expert Systems with Applications 39 (2012) 4987–4998 4993 families following the AHEAD 3 architecture model and provides tools for the feature oriented design process and the implementation of SPLs. An extended FM editor based on FeatureIDE is shown in Fig. 8. It provides users with two views of FMs: tree view and hierarchy view. Users can input the keyword of some feature and then locate it. Attributes of features and feature groups, defined in Table 2, can be easily edited. Constraints also have a separate view and an edit area. Evolution strategies are implemented by an interactive manner. For example, if the change RevNF (‘‘f10: InternetConnection’’) is applied in the FM shown in Fig. 1, a dialog box (as shown in Fig. 9(a)) is displayed for users to choose an evolution strategy. Users can choose to remove all children of the feature ‘‘f10’’ (the evolution strategy defined in Fig. 6(b)) or to reconnect these children to another non-terminal feature (the evolution strategies defined in Fig. 6(c) and (d)). If the latter is chosen, the dialog box is extended to prompt users to input the target feature, as shown in Fig. 9(b). Note that the target feature group and the children group of the removed feature could have different group type, Fig. 8. Extended FM editor based on FeatureIDE. Fig. 9. Evolution strategies implementation. 3 http://userweb.cs.utexas.edu/users/schwartz/. so users must confirm a certain group type to merge the two feature groups. 7. Evaluation According to Stojanovic (2004), the computation complexity of resolving a change to FMs (e.g., RevNF) is about O(n m ) where mis the average depth of the feature hierarchy starting from the considering feature and nthe average number of child features. Generally, mand nare not large numbers because FMs usually contain limited layers and limited children for one feature. Thus, we make a preliminary evaluation that our approach accomplishes the consistency maintenance of evolving FMs in an acceptable time. Further, we give more comprehensive evaluation by experimental studies. Although industries reported FMs with hundreds or thousands of features (Loesch & Ploedereder, 2007; Steger et al., 2004), authors typically published only a small excerpt of their FMs. Large FMs are difficult to find for a thorough evaluation. Thus, we adopt Thum’s method (Thum et al., 2009) to perform experiments using randomly generated FMs with different characteristics. 7.1. Experimental setup We first generated FMs randomly and then performed a set of primitive operations (defined in Table 2) randomly on the generated FMs. Based on the dependency matrix, a set of additional operations are derived automatically from the requested operations. Further, according to predefined evolution strategies, the derived operations are executed automatically to maintain the consistency of those changed FMs. During the above process, we parametrically control the size of FMs, the number and kind of operations, and the kind of evolution strategies for a thorough runtime evaluation. Independent parameters in our experiment are (a) the number of features in an FM, (b) number of operations, (c) kind of operations, (d) kind of evolution strategies. The time needed to perform the requested and derived operations is measured as a dependent variable. To reduce the fluctuations in the dependent variable caused by the random generation, we performed 200 repetitions for each configuration of independent parameters, i.e., we generated 200 random FMs with the same parameters and each performed the same number of random operations of the same kind. All measurements were performed on the same Windows 7 PC with Intel Core Duo CPU 1.5 GHz and 3 GB RAM. 7.1.1. Feature models generation The algorithm to randomly generate FMs of size nis as follows (Thum et al., 2009): starting with a single root node, it runs several iterations. In each iteration, an existing node without children is randomly selected, and one to ten (random amount) of child nodes are added. Those child nodes are connected either by And- (50% probability), Or- (25% probability) or Alternative-group (25% probability). Children in an And-group are optional by a 50% probability. This iteration is continued until the FM has nfeatures. All features with children are considered non-terminal. Moreover, we also generate cross-tree constraints (requires and excludes). For every 10 features, one constraint is generated by the following algorithm: two different features are randomly selected, and then are connected randomly by requires (50% probability) or excludes (50% probability) link. The above generated FMs can be easily translated into propositional formulas according to the rules give in Table 1. We use the SAT solver sat4J 4 to validate these FMs and discard all FMs that do not have a single valid configurations (mostly by unfortunate choice of cross-tree constraints). We repeat the entire process until the appropriate number of valid FMs are generated. We fixed the following parameters: maximum number of children = 10; type of child group = (50%,25%,25%); optional child = 50%; number of cross-tree constraints = 0.1 ⁄n; variables in cross-tree constrains = 2. According to Thum’s survey (Thum et al., 2009), these parameters are backed up by most of the surveyed FMs and represent a rough average. Thus, these generated FMs basically reflect the characteristics of realistic FMs. 7.1.2. Operation generation We randomly generated operations on an FM as well. Our generator takes an FM and the number of operations as input. The 20 primitive operations defined in Table 2 are implemented. They are classified as three main types: ‘add’, ‘remove’, and ‘set’. Our generator can limit the kind of input operations to ‘add’, ‘remove’, ‘set’, or ‘arbitrary’. For a fixed number of input operations, ‘arbitrary’ operations are composed of ‘add’ (33% probability), ‘remove’ (33% probability), and ‘set’ (33% probability) operations. 7.2. Experimental results and discussion 7.2.1. Effectiveness We first verify whether our approach can ensure the consistency of the resulting FMs after the requested changes are resolved. We varied the size of the generated FMs between 10 and 10,000 features. For each FM, we performed 10 random arbitrary operations. 200 repetitions are performed for each model size. Each resulting FM is checked by Sat4j and Guidsl. Guidsl 5 is a tool developed by Batory (2005) that relies on grammars definition and propositional logic to support feature modularizations and their compositions. Results show that all the resulting FMs generated by our approach are validated by Guidsl and Sat4j. Therefore, our approach can effectively maintain the consistency of evolving FMs. 7.2.2. Number of features In the same experimental setting as the above experiment, we also measured how calculation time scales as FMs increase in size. We also perform 10 random arbitrary operations on each FM Fig. 10. Calculation time in milliseconds for different scales of FMs using consistency checking (Sat4j and Guidsl) and consistency maintenance (our approach). 4 http://www.sat4j.org. 5 http://userweb.cs.utexas.edu/schwartz/ATS/fopdocs/guidsl.html.