## 3 Background in Feature Models and Validation Mechanisms  
The use of feature models is a broadly used technique for analysing SPLs. Feature Models (FMs) involve a model that defines the features and their relationships. There exist various notations to design FMs [11], although the most widely used is that proposed by [PERSON] [17], exemplified in Figure 1. FM diagrams enable six types of relations between a parent feature and its child features:  
* _Mandatory_, child feature is required. (cf. in the figure, PS2 is mandatory sub-feature of A, PS2 \(\leftrightarrow\) A). * _Optional_, child feature is optional (cf. in the figure, PS2 optional sub-feature of B, PS2 \(\rightarrow\) B). * _Alternative_, one of the sub-features must be selected (i.e., in general \(a_{1},a_{2},\cdots,a_{n}\) alternative sub-feature of b, \(a_{1}\lor a_{2}\wedge\cdots\wedge a_{n}\leftrightarrow\forall_{i<j}(a_{i}\lor \cdots\lor a_{j})\)). * _Or-relation_, at least one of the sub-features must be selected (i.e., in general \(a_{1},a_{2},\cdots,a_{n}\) or sub-feature of b, \(a_{1}\wedge a_{2}\wedge\cdots\wedge a_{n}\leftrightarrow b\), in the figure \(C\leftrightarrow C1\wedge C2\) ). * _Require relation_, a feature requires the existence of other features with non-direct family relation (cf., in the figure A2 \(\rightarrow\) C1). * _Exclude relation_, a feature excludes the existence of other features with non-direct family relation (cf. in the figure, \(\
eg(\)D \(\wedge\) E))  
**Definition 1**. : _Feature Model. Let \(FM\) be a feature model which consists of a tuple (F,R), where \(F\) is a set of \(n\) features \(\{f_{1},f_{2},\cdots,f_{n}\}\), and \(R\) is a set of relations \(\{r_{1},r_{2},\cdots,r_{m}\}\)._  
There exist extensions to the classical FM representations for the inclusion of attributes and extra-functionalities for features, such as _Cost_ attribute attached to feature B in Figure 1.  
The model in Figure 1 can represent all possible configurations of a software product or system that meet a certain policies. In this example, features \(PS2\) and \(A\) are mandatory for the product or system, since \(PS2\) is the root, and there is a mandatory relation with \(A\). In spite of that, \(B\) and \(C\) are optional, therefore, they may or may not appear in the configurations. Optionality can also be expressed, for example, \(A1\), or \(A2\), or both, may appear whether \(A\) is part of the configurations. Other dependencies express cross-constraints between features, for example, if the feature \(A2\) appears it implies that the feature \(C1\) must also appear. The model also can contain extra properties that include additional information for the model. For example, in Figure 1, the model has three attributes \(Cost\), \(Benefit\), and \(Risk\) associated with feature \(B\). These attributes have an integer domain. If the feature \(B\) appears in a configuration, these attributes must be associated with a tuple of value in the range defined in the model. For the automated analysis of these models, formal methods are proposed [17], based on propositional logic, description logic or constraint programming. In the literature, tools as FAMA [16; 49] enables making direct transformations from the feature models to Constraint Satisfaction Problem (CSP) or Constraint Optimisation Problem (COP) [50]. When the domains of the variables are only Boolean type (i.e., \(true\) and \(false\) values), SAT (propositional satisfiability problem) solvers can be  
Figure 1: An example of feature model. applied to improve the efficiency of the resolution algorithm [51]. In this work, feature models can be formalised by constraint satisfaction problems. **Definition 2**. : _Formalised Feature Model_.