Tolerating Inconsistency in Feature Models Bo Wang Zhenjiang Hu Yingfei Xiong Key Laboratory of High GRACE Center Generative Software Confidence Software National Institute of Development Lab Technologies Informatics The University of Waterloo (Ministry of Education) Tokyo, Japan Waterloo, Canada Peking University, China hu@nii.ac.jp yingfei@swen.uwaterloo.ca wangbo07@sei.pku.edu.cn Haiyan Zhao Wei Zhang Hong Mei Key Laboratory of High Key Laboratory of High Key Laboratory of High Confidence Software Confidence Software Confidence Software Technologies Technologies Technologies (Ministry of Education) (Ministry of Education) (Ministry of Education) Peking University, China Peking University, China Peking University, China zhhy@sei.pku.edu.cn zhangw@sei.pku.edu.cn meih@pku.edu.cn ABSTRACT 1. INTRODUCTION Feature models have been widely adopted to reuse the re- Feature models [6, 7] have been widely adopted to reuse quirements of a set of similar products in a domain. When the requirements of a set of similar products in a domain. constructing feature models, it is difficult to always ensure During the process of products reuse, specific products that the consistency of feature models. Therefore, tolerating in- satisfy all the constraints are derived from feature mod- consistencies is important during the construction of feature els. Inconsistent feature models contain contradictory con- models. The usual way of tolerating inconsistencies is to straints that cannot be satisfied at the same time, leading to find the minimal unsatisfiable core. However, identifying no valid products derivable from them [13]. However, it is the minimal unsatisfiable core is time-consuming, which de- difficult to always ensure the consistency of feature models, creases itself the practicability. during the construction of feature models. Therefore, toler- In this paper, we propose a priority based approach to ating inconsistencies is important when constructing feature tolerating inconsistencies in feature models efficiently. The models. basic idea of our approach is to find the weaker unsatis- The usual way of tolerating inconsistencies is to find the fied constraints, while keeping the rest of the feature model minimal unsatisfiable core in inconsistent feature models. consistent. Our approach tolerates inconsistencies with the However, identifying the minimal unsatisfiable core is time- help of priority based operations while building feature mod- consuming [9], which decreases itself the practicability. els. To this end, we adopt the constraint hierarchy the- In this paper, we propose a priority based approach to ory to express the degree of domain analysts’ confidence on tolerating inconsistencies in feature models, and report an constraints (i.e. the priorities of constraints) and tolerate implementation of a system that not only automatically tol- inconsistencies in feature models. Experiments have been erates inconsistencies by identifying weaker unsatisfied con- conducted to demonstrate that our system can scale up to straints, but also supports domain analysts to handle the large feature models. tolerated inconsistencies, with the help of priority based op- erations. To this end, we adopt the constraint hierarchy the- ory [5], a known practical theory in user interface construc- Categories and Subject Descriptors tion, to express the degree of domain engineers’ confidence D.2.13 [Software Engineering]: Reusable Software—Do- on constraints (i.e. the priorities of constraints) and tolerate main engineering inconsistencies in feature models. The main contributions of our paper are summarized as follows: Keywords ∙ We show the importance of the constraint hierarchy Feature Model, Constraint Hierarchy, Tolerate Inconsistency theory in tolerating inconsistencies in feature models, and we adopt it to divide a feature model into the con- sistent feature model part and pending constraint set part, which will help tolerate inconsistencies in feature models. ∙ We make the first attempt of conducting a constraint hierarchy system1 for tolerating inconsistencies in fea- ture models, through adapting and extending an ex- isting incremental algorithm-SkyBlue [10, 11]. 1 See http://sei.pku.edu.cn/˜ wangbo07/ for more details. 15 ∙ We have conducted the experiments on our system, Based on the predicates, there are three kinds of com- which demonstrates that our approach scales up to posite constraints on two feature sets, composite-requires, very large feature models. composite-m-requires, and composite-excludes. For example, given All-Set(Media) composite requires Or-Set(Camera, MP3), The rest of this paper is organized as follows. Section if All-Set (Media) is true, Or-Set (Camera, MP3) must be 2 introduces some preliminary knowledge on feature mod- true. For the details of the composite constraints, see sub- els, constraint hierarchy and SkyBlue. Section 3 gives an section 4.1. overview of our approach. Section 4 amplifies our approach. Products are derived from a feature model by binding and Section 5 illustrates the scalability of our approach. Section unbinding constraints. A valid derived product must satisfy 6 discusses the related work, and Section 7 concludes the all the constraints in the feature model. A feature model paper and highlights the future work. contains inconsistencies if no valid products can be found to satisfy all the constraints in this feature model [13]. These inconsistencies are caused by the contradictory constraints 2. PRELIMINARIES in feature models. In this section, we first describe feature models, followed by the introduction to the constraint hierarchy theory and 2.2 Constraint Hierarchies and SkyBlue SkyBlue. All these three serve as the fundamental supports When a solver is used to check inconsistent models, it is for tolerating inconsistencies in feature models. not enough for the solver to just signal the detected inconsis- tencies. The constraint hierarchy theory [5] provides a way 2.1 Feature Model to handle the detected inconsistencies through maintaining A feature model organizes the requirements of the prod- constraint hierarchies. A constraint hierarchy contains a set ucts of a domain, in terms of features and the relationships of constraints, each assigned with a priority, indicating the between them. A simplified feature model of the mobile importance of the constraint. Given an inconsistent model, phone domain [3], which adopts our meta model of feature a constraint solver makes sure that stronger constraints are models [15], is shown in Fig. 1. satisfied, through unsatisfying the contradictory weaker con- straints. Legend SkyBlue is an incremental constraint solver that uses local Mobile Phone Mandatory Feature propagation to maintain the constraint hierarchies. It has Optional Feature Require been successfully applied in many GUI systems. SkyBlue Exclude requires that methods can be derived from constraints (ex- plained later in this sub-section), and thus is not applicable GPS Call Screen Media to some kinds of constraints. One important finding of our approach is that the constraints in feature models satisfy High the prerequisite of SkyBlue (with minor extension) and thus Basic Color Camera MP3 Resolution can enjoy the performance boost of SkyBlue (see Section 4). Composite Constraints: All-Set(Screen) composite-requires Single-Set(Basic, Color, High Resolution) C1 C2 C3 C4 All-Set(Media) composite-requires Or-Set(Camera, MP3) Weak A Strongest B Strong C Medium C1: A = 5 (Weak) C3: B+C = 7 (Strong) Methods: Methods: Figure 1: A simplified example of the mobile phone 1) A = 5 1) B = 7 – C 2) C = 7 – B Unenforced Unselected domain Constraint Method C2: A+B = 10 (Strongest) C4: C = 6 (Medium) C1 C2 C3 C4 Methods: Methods: Weak A Strongest B Strong C Medium 1) A = 10 – B 1) C = 6 A feature is a software characteristic with sufficient user 2) B = 10 – A or customer value, which essentially denotes a cohesive set of Legend Constraint C1 C2 C3 individual requirements [14]. In feature models, if a feature Weak A Strongest B Strong C Variable is bound (i.e. selected and implemented in a product), so Determine a Variable is its parent. A mandatory feature should be bound if its parent is bound. An optional feature can be unbound (i.e. deselected and not implemented in a product), even if its Figure 2: A simple example for SkyBlue parent is bound. There are three kinds of simple constraints on two fea- The input of SkyBlue is a set of variables and the con- tures, namely requires, m-requires, and excludes. If feature straints on these variables. The output of SkyBlue is a set A requires feature B, it indicates that B must be bound when of values that satisfy stronger constraints and leave the con- A is bound. If feature A m-requires feature B, it means that tradictory weaker constraints unsatisfied. A and B should be bound or unbound at the same time. If In SkyBlue, each constraint is equipped with one or more feature A excludes feature B, it indicates that they cannot methods. SkyBlue satisfies a constraint by selecting one be bound at the same time. of its methods and executing the selected method. Sky- There are three kinds of predicates on a set of features, Blue enforces a constraint by choosing one method for this namely All, Alternative and Or. Predicates All, Alternative, constraint and revoke a constraint by choosing no meth- and Or indicate these predicates are true only if all, only ods for this constraint. A constraint is enforced if it has one, and at least one features are bound in their feature a selected method, otherwise, it is unenforced. The vari- sets, respectively. For instance, Single-Set (Basic, Color, ables and the constraints form the constraint graph. The High Resolution) indicates that this predicate is true when constraint graph, together with the selected methods, forms only one kind of screens can be chosen in a product. the method graph. 16 The output of SkyBlue, the value set for variables, is cal- and the PCS consists of the unenforced constraints in the culated through constructing and executing a locally-graph- LGB method graph. After a new LGB method graph is better (called LGB) method graph. A method graph is LGB constructed, the CFM and the PCS are updated. if there are no method conflicts and there are no unen- 1. If the constructed LGB method graph does not contain forced constraints that could be enforced by revoking one any unenforced constraints, the PCS is empty and the or more weaker constraints (and possibly changing the se- CFM contains all the constraints in the feature model. lected methods for other enforced constraints with the same At this moment, the feature model is consistent. or stronger strength) [10]. As a simple example, the method graphs in Fig. 2 has 2. If the constructed LGB method graph contains one or four constraints C1, C2, C3 and C4 on three variables A, B more weaker unenforced constraints, the constraints in and C. Each constraint has one or more methods to make the PCS are replaced with these unenforced constraints the constraint hold (for instance, two methods are given to and the constraints in the CFM are replaced with the satisfy C3 by either calculating B from C or calculating C enforced constraints in the LGB method graph. At from B ). To satisfy every constraint, SkyBlue tries to se- this moment, the feature model is inconsistent. lect a method from each constraint, as shown in the upper Four kinds of operations on the CFM are provided to help right of Fig. 2, but there is a method conflict (inconsistency): domain analysts construct feature models. When construct- variable A is determined by two methods, namely, A=5 and ing feature models, domain analysts can add a constraint A=10-B. To resolve this conflict, we have to revoke some with priority into the CFM or delete a constraint from it. weaker constraint to enforce the stronger constraints. Sky- Domain analysts can change priorities of constraints when Blue finds the strong constraints that can be enforced, while constructing feature models. leaving the weaker constraints unenforced by constructing There are three conditions on which the enforced con- LGB method graph. The LGB method graph of this ex- straints in the CFM may become unenforced and thus are ample is shown in the middle right of Fig. 2, where C1 is put into the PCS: 1) their priorities are reduced; 2) the pri- revoked. After executing the selected methods in the LGB orities of their contradictory weaker constraints in the PCS method graph, A equals to 9, B equals to 1, and C equals to are raised; 3) some contradictory stronger constraints are 6, which satisfy the three stronger constraints, namely C2, added. When these conditions are met, we generate a new C3 and C4. C1 may be reenforced automatically when its LGB method graph to update the CFM and the PCS. contradictory constraints are deleted. For example, if C4 is Three kinds of operations on the PCS are provided to deleted, a new LGB method graph is constructed, in which help domain analysts handle the tolerated inconsistencies. constraint C1 is reenforced by selecting method “A equals If the domain analysts become more confident about a con- to 5”, as shown in the lower right of Fig. 2. straint in the PCS, he can raise its priority. The possibility of reenforcing this constraint become larger as its priority 3. APPROACH OVERVIEW rises. If the domain analysts become less confident about In this section, we first give an overview of our approach, a constraint, he can reduce its priority. The possibility of and then we use an example to illustrate how to tolerate enforcing this constraint becomes smaller as its priority de- inconsistencies in feature models. creases. If domain analysts believe some constraints do not represent the correct relationships among the features, they 3.1 Feature Model Inconsistency Tolerance can delete them from the in pending constraint set. In our approach, a feature model is divided into two parts, There are three conditions on which the unenforced con- namely the consistent feature model part (called CFM part) straints in the PCS can be re-enforced again, and thus are and the pending constraint set part (called PCS part). The put into the CFM: 1) their priorities are raised; 2) their con- PCS contains weaker constraints that conflict with some tradictory stronger constraints in the CFM are deleted; 3) stronger constraints in the CFM. If the PCS is empty, the the priorities of their contradictory stronger constraints in feature model is consistent. Domain analysts work on the the CFM are reduced. When these conditions are met, we CFM to construct the feature model and work on the PCS generate a new LGB method graph to update the CFM and to handle the tolerated inconsistencies. An overview of the the PCS. inconsistency tolerance is shown in Fig. 3. 3.2 An Example Add / Delete a Constraint To demonstrate how we tolerate inconsistencies in feature Consistent Check Generate & Update Pending models, let us see how to find the CFMs and the PCSs, and Feature Model Reduce the Inconsistency Priority of a Constraint Set handle the tolerated inconsistencies in the feature model in Constraint Feature Raise the Raise the Priority of a Fig. 4. Model Priority of a Constraint Constraint Automatic Step Suppose all the constraints have been added into the fea- Pending Reduce the Priority of a Operation ture model except “feature C excludes feature D” (the red Constraint Set Constraint Artifact part in Fig. 4). The feature model is consistent before Delete a adding “feature C excludes feature D”, since the LGB shown Constraint in Fig. 4(b) contains no unenforced constraints. At this mo- ment, the PCS is empty. Note that even some variables are Figure 3: Feature model inconsistency tolerance determined by more than one method in the LGB method graph, no conflict happens, because these variables are set We divide a feature models into the CFM and the PCS to the same value (see Section 4 for more detail). through constructing LGB method graphs. The CFM con- When the “exclude” constraint is added and enforced, a sists of the enforced constraints in the LGB method graph, LGB method graph, in which the constraints “Mandatory D” 17 Legend: Root Feature Priority 6 Priority: 1 3 6 Unbind a feature Table 1: Methods for constraints A Confidence : Low Medium High 6 A Bind a feature Number of Default Priority: 3 Relationship Methods Methods 5 3 3 4 5 3 3 4 Mandatory A {Bind(A), Bind(B)} or 4 5 4 B 4 4 2 B C D E B {Unbind(A), Unbind(B)} C D E 5 3 5 Optional A {Bind(A)} or F G Add excludes between C and D 5 3 2 {Unbind(B)} 4 B Add excludes Composite Constraint: between C Composite-Requires All-Set(B) c-requires Single(F,G) Priority: 4 F G and D Predicate {Predicate(Set-A) = False} or Predicate 2 {Predicate(Set-B ) = True} (a) (b) Set-A Set-B Composite-M-requires {Predicate(Set-A) = False, Predicate(Set-B) = False} or Predicate Predicate 2 {Predicate(Set-A) = True, Figure 4: An example of feature model inconsistency Set-A Set-B Predicate(Set-B) = True} tolerance Composite-Excludes Predicate Predicate {Predicate(Set-A)= False} or 2 {Predicate(Set-B)= False} Set-A Set-B and “feature E requires feature D” are revoked, is generated. The PCS consists of these two revoked constraints. Domain analysts can delete the constraint “feature D re- quires feature E ” if they believe the “require” constraint Table 2: Methods for predicates dose not represents the correct relationship between fea- Predicate Value Number Methods Of Methods ture D and E. If domain analysts have more confidence on All the “Mandatory D” than before, they raise its priority to 5. True 1 {Bind(A1),Bind(A2) …Bind(An)} Set-A {Unbind(A1)} or {Unbind(A2)} or … Then our approach will try to enforce it by constructing a {A1,A2…An} False n {Unbind(An)} new LGB. In the new LGB method graph, only “feature B {Bind(A1),Unbind(A2),Unbind(A3)…Unbind(An)} requires feature C” is revoked. The PCS is updated, and it Alternative True n {Bind(A2),Unbind(A1),Unbind(A3)…Unbind(An)} or … Set-A {Bind(An),Unbind(A1),Unbind(A2)…Unbind(An-1)} only contains the “require” constraint. {A1,A2…An} {Unbind(A1),Unbind(A2)…Unbind(An)} or False 1+(n2-n)/2 Any two of the features in the group are bound Or 4. TOLERATE INCONSISTENCIES IN FEA- Set-A True n {Bind(A1)} or {Bind(A2)} or … {Bind(An)} TURE MODELS {A1,A2…An} False 1 {Unbind(A1), Unbind(A2) …Unbind(An)} In this section, we will describe how we adopt the con- straint hierarchy theory by revising and extending SkyBlue to tolerate inconsistencies in feature models. posite constraint to an SBC. For example, given a compos- ite constraint “All-Set(A,B) composite-excludes Alternative- 4.1 Map Feature Models to Constraint Graphs Set(C,D)”, methods are generated through combination of To use SkyBlue to detect and tolerate inconsistencies, the the states of the features in the two sets. The four derived first thing is to map the elements of feature models to the methods are {Unbind(A)},{Unbind(B)}, {Unbind(C), Un- elements of SkyBlue constraint graphs. bind(D)}, and {Bind(C), Bind(D)}. The mapping consists of two steps: 1) each feature of the feature model is mapped to a variable of the SkyBlue 4.2 Construct LGB Method Graphs constraint graph; 2) each constraint of the feature model is In our approach, we divide a feature model into the CFM mapped to a SkyBlue constraint (called SBC) that is repre- and the PCS, and provide priority-based operations through sented by a set of methods. constructing LGB method graphs. To construct LGB method SkyBlue cannot be generalized to derive methods from graphs for feature models’ tolerance, we have to extend and some “inequality-like” constraints. But feature models are revise SkyBlue through: 1) redefining method conflicts; 2) different from this general case. In feature models, each specializing the execution process. feature can have only two states: 1) bound; 2) unbound. An LGB method graph is constructed under the follow- Therefore, it is possible to derive methods for constraints in ing conditions: 1) a new constraint is added/deleted to the feature models, through combinations of the states of “cer- CFM; 2) the priority of a constraint in the CFM/PCS is tain” features. Concrete rules for the mapping from feature changed. The pseudo codes are shown below. models to constraint graphs are listed in Tables 1 and 2. Binding a feature (Bind(feature)) sets the bind state of Add/delete a constraint in CFM the feature bound. Unbinding a feature (Unbind(feature)) ConstructCFM ( Constraint SBC , Boolean isAdd ) { sets the bind state of the feature unbound. Predicate on a If ( isAdd ) { feature set represents the value of the predicate of a fea- ConstructLGB ( Constraint SBC ) ture set. In our approach, simple constraints can be repre- } Else { sented by a composite constraint. For example, “feature U ne n fo r ce d Cn s Se t = A excludes feature B ” can be represented as “All-Set(A) c o l l e c t U n e n f o r c e d C o n s t r a i n t s () ; composite-excludes All-Set(B)”. While ( U ne n fo rc e dC n sS e t != null ) { unenforcedCn = U ne n fo r ce d Cn s Se t . get () ; In Table 2, each kind of group predicates is associated ConstructLGB ( SBC ) ; with a set of methods that can be executed to set the pred- } icate True or False. These predicate methods, together } with the composite constraint methods, can map a com- 18 Changing a constraint’s priority in the constraint graph can only be bound and unbound. ChangePriority ( Constraint SBC , Priority p ) { Therefore, even if a variable is determined by more than oldPriority = SBC . priority ; one method, it may not cause a conflict (e.g. see variable B SBC . priority = p ; in Fig. 4). A conflict happens only when this variable is set If ( oldPriority < p ) { If ( SBC . selectedMethod == null ) to different value by different methods. ConstructLGB ( SBC ) ; In SkyBlue, if an LGB method graph contains directed } cycles, it is not possible to find an execution sort to satisfy Else If ( oldPriority > p ) { If ( SBC . selectedMethod != null ) all the variables in the LGB method graph. However, our ConstructLGB ( SBC ) ; approach can just execute all the methods to satisfy all the } constraints, because all the methods set a variable to a fixed } value. Constructing an LGB method graph involves enforcing the constraints in the constraint graph. To enforce a con- 5. PERFORMANCE straint, we select a method for it, change the methods of the In this section, we investigate whether our approach can constraints with the same or stronger priorities, or revoke scale up to large feature models. To evaluate the scalability, one or more weaker constraints. This process is called con- we randomly generate feature models2 and tolerate the in- structing a method vine or mvine. When an mvine for the consistencies in the generated feature models. We choose to newly-added SBC is built, the SBC is successfully enforced. use generated models because none of the large models are Note that each time a constraint is successfully enforced publicly available. The generated feature model contains a (i.e. an mvine is constructed), one or more weaker con- root feature. We can specify the number of the subtrees that straints may be revoked. To construct an LGB method are connected to the root feature, the height of the subtrees, graph, these revoked constraints are added to the unenforced the number of the chid feature for each non-leaf feature in constraint set. Then our algorithm repeatedly tries to en- the subtrees, the number of the constraints. The percentage force all the constraints in the unenforced constraint set by of the the variability of features are: Mandatory (25%) and constructing mvines for these constraints, until none of the Optional (75%). The priorities of constraints are randomly constraints can be enforced. This process terminates be- set between 1 to 5. cause of the finite number of constraints. The pseudo code of constructing an LGB method is shown below. Time (Seconds) 70 Construct an LGB method graph 60 ConstructLGB ( Constraint SBC ) { 50 // clean the unenforced constraint 40 // set before enforce the newly - added SBC } 30 With different Priorities c l e a r U n e n f o r c e d C nS e t () ; 20 a d d T o U n e n f o r c e d C nS e t ( SBC ) ; 10 While ( U ne n fo rcedCntSet != null ) { 400 800 1200 1600 2000 2400 2800 3200 3600 4000 4400 unenforcedCn = UnenforcedCnSet . get () ; 242 425 605 765 1023 1364 1705 2046 2387 2728 3069 3410 3751 4092 4433 Number /30 /50 /70 /110 /130 /150 /170 /190 /210 /230 /250 /270 /290 /310 /330 of Features buildMvine ( unenforcedCn , unenforcedCnS et ) ; /Constraints } } Figure 5: Experiments results for randomly gener- SkyBlue uses a backtracking depth-first search to build ated feature models mvines. The pseudo code of building a mvine is shown as follows: The environment for our experiments is a Win 7 PC with a 2.66 GHz CPU, 2GB memory and the result is shown Build a Mvine for a unenforced constraint in Fig. 5. A mandatory feature or optional feature brings buildMvine ( Constraint root ) { constraints with their parents, m-requires and requires, re- While ( root has methods ) { Method m = getMethod () ; spectively. The constraints showed in the results are the If (! checkConflicts () ) { constraints explicitly modeled into the feature models, they return true ; do not contain the simple constraints that are brought with } Else { Constrint cn = g e t C o n f l i c t s C o n s t r a i n t () ; the Mandatory and Optional feature. If ( cn weaker than root ) { In our approach, we check inconsistency and generate the revokeConstring ( cn ) ; PCS incrementally. For example, in the second case, 425 return true ; mandatory or optional features are added (each bring a con- } Else { If ( buildMvine ( cn ) ) straint), and 50 constraints are explicitly modeled, we gen- return true ; erate the PCS 475 times in total and cost 1.2s in all. The } results indicate that our approach can scale up to large fea- } } ture models. return false ; // start backtrack } 6. RELATED WORK To apply the SkyBlue to detect and tolerate inconsisten- Feature models are first proposed by Kang et al. [7] in the cies in feature models,our algorithm redefines method con- feature-oriented domain analysis (FODA) method. Since flict and revises the SkyBlue algorithm for building mvines. In SkyBlue, a conflict happens when a variable is determined 2 See http://sei.pku.edu.cn/˜ wangbo07/ for our system and by more than one method. In our approach, the variables the feature model random generation algorithm. 19 then many researches focus on the detection of inconsisten- [5] A. Borning, B. N. Freeman-Benson, and M. Wilson. cies in feature models [3]. Maßen and Lichter [13] proposed a Constraint hierarchies. Lisp and Symbolic deficiency framework of feature model. They point out that Computation, 5(3):223–270, 1992. inconsistency is one of the most severe deficiencies in feature [6] K. Czarnecki, S. Helsen, and U. W. Eisenecker. models. Mannion et al. [8] was the first to use propositional Formalizing cardinality-based feature models and their formulas to find inconsistencies. Batory [2] proposed an ap- specialization. Software Process: Improvement and proach to detecting deficiencies with SAT Solver. Benavides Practice, 10(1):7–29, 2005. et al. [4] were the first to use constraint programming for [7] K. C. Kang, S. G. Cohen, J. A. Hess, W. E. Novak, analysis on feature models. Our previous work [16] focused and A. S. Peterson. Feature-oriented domain analysis on how to analyze feature models using BDD. (FODA) feasibility study. Technical report, CMU-SEI, However, these approaches do not focus on how to find November 1990. the unsatisfied constraints and tolerate inconsistencies in [8] M. Mannion. Using first-order logic for product line feature models. Balzer [1] pointed out the importance of model validation. In SPLC, pages 176–187, 2002. tolerating inconsistencies, when the inconsistencies cannot [9] S. Nakajima. Semi-automated diagnosis of foda be fixed. Trinidad et al. [12] focus on the explanation of feature diagram. In SAC ’10, pages 2191–2197, New inconsistencies in feature models, which helps find unsatis- York, NY, USA, 2010. ACM. fied constraints. Nakajima et al. [9] propose some heuristics [10] M. Sannella. The skyblue constraint solver and its rules to find the unsatisfied core. However, these approaches applications. In PPCP, pages 258–268, 1993. do not provide explicit support to handle the tolerated in- consistencies and the scalability of these approaches is also [11] M. Sannella. Skyblue: A multi-way local propagation not clear. Zowghi et al. [17] propose an approach to han- constraint solver for user interface construction. In dling inconsistencies as a consequence of evolution changes ACM Symposium on User Interface Software and performed on requirements specification, while our approach Technology, pages 137–146, 1994. focuses on the inconsistencies in feature models. [12] P. Trinidad, D. Benavides, A. Durán, A. Ruiz-Cortés, and M. Toro. Automated error analysis for the agilization of feature modeling. Journal of Systems 7. CONCLUSION AND FUTURE WORK and Software, 81(6):883 – 896, 2008. Agile Product In this paper, we adopt the constraint hierarchy theory Line Engineering. and extend the constraint solver–SkyBlue to implement a [13] T. von der Maßen and H. Lichter. Deficiencies in system that can effectively tolerate inconsistencies in feature feature models. In Workshop on Software Variability models. The feature model is divided into two parts, consis- Management for Product Derivation, in Conjunction tent feature model part and the pending constraint set part, with SPLC, 2004. through building LGB method graphs. Domain analysts can [14] B. Wang, W. Zhang, H. Zhao, Z. Jin, and H. Mei. A construct the feature model by working on the CFM while use case based approach to feature models’ handling the tolerated inconsistencies that are expressed ex- construction. IEEE International Conference on plicitly by the PCS. Three operations are defined and sup- Requirements Engineering, 0:121–130, 2009. ported by our system, with the purpose of helping domain [15] W. Zhang, H. Mei, and H. Zhao. Feature-driven analysts handle the tolerated inconsistencies. Our future requirement dependency analysis and high-level work will focus on investigating the applicability of our ap- software design. Requir. Eng., 11(3):205–220, 2006. proach. [16] W. Zhang, H. Yan, H. Zhao, and Z. Jin. A bdd-based approach to verifying clone-enabled feature models’ 8. ACKNOWLEDGMENTS constraints and customization. In ICSR, pages The authors would like to thank Hiroshi Hosobe (NII, 186–199. Springer, 2008. Japan) for introducing Delta/Skyblue to us. This work is [17] D. Zowghi and R. Offen. A logical framework for supported by the National Basic Research Program of China modeling and reasoning about the evolution of (973) under Grant No. 2009CB320701, the National High requirements. In RE, page 247. IEEE Computer Technology Research and Development Program of China Society, 1997. (863) under Grant No. 2009AA01Z139, the Natural Science Foundation of China under Grant No. 60703065, 60873059, and the National Institute of Informatics (Japan) Internship Program. 9. REFERENCES [1] R. Balzer. Tolerating inconsistency. In ICSE, pages 158–165, 1991. [2] D. S. Batory. Feature models, grammars, and propositional formulas. In SPLC, pages 7–20, 2005. [3] D. Benavides, S. Segura, and A. R.-R. Cort?s. Automated analysis of feature models 20 years later: a literature review. Information Systems, 2010. [4] D. Benavides, P. Trinidad, and A. R. Cortés. Using constraint programming to reason on feature models. In SEKE, pages 677–682, 2005. 20