Operations

In this section, we answer RQ1 : What operations of analysis on feature models have been proposed? For each operation, its definition, an example and possible practical applications are presented.


5.1
  Void feature model

This operation takes a feature model as input and returns a value informing whether such feature model is void or not. A feature model is void if it represents no products. The reasons that may make a feature model void are related with a wrong usage of cross-tree constraints, i.e. feature models without cross-tree constraints cannot be void.

As an example, Figure 5 depicts a void feature model. Constraint C-1 makes the selection of the mandatory features B and C not possible, adding a contradiction to the model because both features are mandatory.


Figure

Figure 5: A void feature model

The automation of this operation is especially helpful when debugging large scale feature models in which the manual detection of errors is recognized to be an error-prone and time-consuming task [5,43,76]. This operation is also referred to by some authors as "model validation", "model consistency checking", "model satisfiability checking", "model solvability checking" and "model constraints checking".


5.2
  Valid product

This operation takes a feature model and a product (i.e. set of features) as input and returns a value that determines whether the product belongs to the set of products represented by the feature model or not. For instance, consider the products P1 and P2, described below, and the feature model of Figure 1.

 P1={MobilePhone,Screen,Colour,Media,MP3}

 P2={MobilePhone,Calls,Screen,High resolution,GPS}

Product P1 is not valid since it does not include the mandatory feature Calls. On the other hand, product P2 does belong to the set of products represented by the model.

This operation may be helpful for software product line analysts and managers to determine whether a given product is available in a software product line. This operation is sometimes also referred to as "valid configuration checking","valid single system", "configuration consistency", "feature compatibility", "product checking" and "product specification completeness".


5.3
  Valid partial configuration

This operation takes a feature model and a partial configuration as input and returns a value informing whether the configuration is valid or not, i.e. a partial configuration is valid if it does not include any contradiction. Consider as an example the partial configurations C1 and C2, described below, and the feature model of Figure 1.

C1 = ({MobilePhone,Calls,Camera}, {GPS,High resolution})
C2 = ({MobilePhone,Calls,Camera}, {GPS})

C1 is not a valid partial configuration since it selects support for the camera and removes the high resolution screen that is explicitly required by the software product line. C2 does not include any contradiction and therefore could still be extended to a valid full configuration.

This operation results helpful during the product derivation stage to give the user an idea about the progress of the configuration. A tool implementing this operation could inform the user as soon as a configuration becomes invalid, thus saving time and effort.


5.4
  All products


This operation takes a feature model as input and returns all the products represented by the model. For instance, the set of all the products of the feature model presented in Figure 1 is detailed below:

P1 = {MobilePhone,Calls,Screen,Basic}
P2 = {MobilePhone,Calls,Screen,Basic,Media,MP3}
P3 = {MobilePhone,Calls,Screen,Colour}
P4 = {MobilePhone,Calls,Screen,Colour,GPS}
P5 = {MobilePhone,Calls,Screen,Colour,Media,MP3}
P6 = {MobilePhone,Calls,Screen,Colour,Media,MP3,GPS}
P7 = {MobilePhone,Calls,Screen,High resolution}
P8 = {MobilePhone,Calls,Screen,High resolution,Media,MP3}
P9 = {MobilePhone,Calls,Screen,High resolution,Media,MP3,Camera}
P10 = {MobilePhone,Calls,Screen,High resolution,Media,Camera}
P11 = {MobilePhone,Calls,Screen,High resolution,GPS}
P12 = {MobilePhone,Calls,Screen,High resolution,Media,MP3,GPS}
P13 = {MobilePhone,Calls,Screen,High resolution,Media,Camera,GPS}
P14 = {MobilePhone,Calls,Screen,High resolution,Media,Camera,MP3,GPS}

This operation may be helpful to identify new valid requirement combinations not considered in the initial scope of the product line. The set of products of a feature model is also referred to in the literature as "all valid configurations" and "list of products".


5.5
  Number of products

This operation returns the number of products represented by the feature model received as input. Note that a feature model is void iff the number of products represented by the model is zero. As an example, the number of products of the feature model presented in Figure 1 is 14.

This operation provides information about the flexibility and complexity of the software product line [11,30,88]. A big number of potential products may reveal a more flexible as well as more complex product line. The number of products of a feature model is also referred to in the literature as "variation degree".


5.6
  Filter

This operation takes as input a feature model and a configuration (potentially partial) and returns the set of products including the input configuration that can be derived from the model. Note that this operation does not modify the feature model but filters the features that are considered.

For instance, the set of products of the feature model in Figure 1 applying the partial configuration (S,R) = ({Calls,GPS},{Colour,Camera}), being S the set of features to be selected and R the set of features to be removed, is:

P1 = {MobilePhone,Calls,Screen,High resolution,GPS}
P2 = {MobilePhone,Calls,Screen,High resolution,Media,MP3,GPS}

Filtering may be helpful to assist users during the configuration process. Firstly, users can filter the set of products according to their key requirements. Then, the list of resultant products can be inspected to select the desired solution [30].


5.7
  Anomalies detection

A number of analysis operations address the detection of anomalies in feature models i.e. undesirable properties such as redundant or contradictory information. These operations take a feature model as input and return information about the anomalies detected. We identified five main types of anomalies in feature models reported in the literature. These are:

Dead features. A feature is dead if it cannot appear in any of the products of the software product line. Dead features are caused by a wrong usage of cross-tree constraints. These are clearly undesired since they give the user a wrong idea of the domain. Figure 6 depicts some typical situations that generate dead features.


Figure

Figure 6: Common cases of dead features. Grey features are dead

Conditionally dead features. A feature is conditionally dead if it becomes dead under certain circumstances (e.g. when selecting another feature) [41]. Both unconditional and conditional dead features are often referred to in the literature as "contradictions" or "inconsistencies". In Figure 7 feature B becomes dead whenever feature D is selected. Note that, with this definition, features in an alternative relationship are conditionally dead.


Figure

Figure 7: An example of a conditionally dead feature

False optional features. A feature is false optional if it is included in all the products of the product line despite not being modelled as mandatory. Figure 8 depicts some examples of false optional features.


Figure

Figure 8: Some examples of false optional features. Grey features are false optional

Wrong cardinalities. A group cardinality is wrong if it cannot be instantiated [80]. These appear in cardinality-based feature models where cross-tree constraints are involved. An example of wrong cardinality is provided in Figure 9. Notice that features B and D exclude each other and therefore the selection of three subfeatures, as stated by the group cardinality, is not possible.


Figure

Figure 9: An example of wrong cardinality

Redundancies. A feature model contains redundancies when some semantic information is modelled in multiple ways [89]. Generally, this is regarded as a negative aspect since it may decrease the maintainability of the model. Nevertheless, it may also be used as a means of improving readability and comprehensibility of the model. Figure 10 depicts some examples of redundant constraints in feature models.


Figure

Figure 10: Some examples of redundancies. Gray constraints are redundant


5.8
  Explanations

This operation takes a feature model and an analysis operation as inputs and returns information (so-called explanations) about the reasons of why or why not the corresponding response of the operation [80]. Causes are mainly described in terms of features and/or relationships involved in the operation and explanations are ofter related to anomalies. For instance, Figure 11 presents a feature model with a dead feature. A possible explanation for the problem would be "Feature D is dead because of the excludes constraint with feature B". We refer the reader to [80] for a detailed analysis of explanation operations.


Figure

Figure 11: Grey feature is dead because relationship C-1

Explanations are a challenging operation in the context of feature model error analysis, (a.k.a. feature model debugging) [7,76,80]. In order to provide an efficient tool support, explanations must be as accurate as possible when detecting the source of an error, i.e. it should be minimal. This becomes an even more challenging task when considering extended feature models and relationships between feature attributes.


5.9
  Corrective explanations

This operation takes a feature model and an analysis operation as inputs and returns a set of corrective explanations indicating changes to be made in the original inputs in order to change the output of the operation. In general, a corrective explanation provides suggestions to solve a problem, usually once this has been detected and explained.

For instance, some possible corrective explanations to remove the dead feature in Figure 11 would be "remove excludes constraint C-1" or "model feature B as optional". This operation is also referred to in the literature as "corrections".


5.10
  Feature model relations

These operations take two different feature models as inputs and returns a value informing how the models are related. The set of features in both models are not necessarily the same. These operations are useful for determining how a model has evolved over time. Thüm et al. [75] classify the possible relationships between two feature models as follows:

Refactoring. A feature model is a refactoring of another one if they represent the same set of products while having a different structure. For instance, model in Figure 12(b) is a refactoring of model in Figure 12(a) since they represent the same products i.e. {{A,B},{{A,B,C}, {A,B,D},{A,B,C,D}}. Refactorings are useful to restructure a feature model without changing its semantics. When this property is fulfilled the models are often referred to as "equivalent".

Generalization. A feature model, F, is a generalization of another one, G, if the set of products of F maintains and extends the set of products of G. For example, feature model in Figure 12(c) is a generalization of the model in Figure 12(a) because it adds a new product ({A}) without removing an existing one. Generalization occurs naturally while extending a software product line.

Specialization. A feature model, F, is a specialization of another one, G, if the set of products of F is a subset of the set of products of G. For example, Figure 12(d) depicts a specialization of the model in Figure 12(a) since it removes a product from the original model ({A,B,C,D}) and adds no new ones.

Arbitrary edit. There is no explicit relationship between the input models, i.e. there are non of the relationships defined above. Models in Figure 12(a) and Figure 12(e) illustrate an example of this. Thüm et al. [75] advise avoiding arbitrary edits and replacing these by a sequence of specialization, generalizations and refactorings edits for a better understanding of the evolution of a feature model.


Figure 12: Types of relationships between two feature models


5.11
  Optimization

This operation takes a feature model and a so-called objective function as inputs and returns the product fulfilling the criteria established by the function. An objective function is a function associated with an optimization problem that determines how good a solution is.

This operation is chiefly useful when dealing with extended feature models where attributes are added to features. In this context, optimization operations may be used to select a set of features maximizing or minimizing the value of a given feature attribute. For instance, mobile phones minimizing connectivity cost in Figure 2 should include support for USB connectivity exclusively, i.e. USB is the cheapest.

5.12  Core features

This operation takes a feature model as input and returns the set of features that are part of all the products in the software product line. For instance, the set of core features of the model presented in Figure 1 is {MobilePhone,Calls,Screen}.

Core features are the most relevant features of the software product line since they are supposed to appear in all products. Hence, this operation is useful to determine which features should be developed in first place [77] or to decide which features should be part of the core architecture of the software product line [61].


5.13
  Variant features

This operation takes a feature model as input and returns the set of variant features in the model [80]. Variant features are those that do not appear in all the products of the software product line. For instance, the set of variant features of the feature model presented in Figure 1 is {Basic,Colour,High resolution,Media,Camera, MP3,GPS}.


5.14
  Atomic sets


This operation takes a feature model as input and returns the set of atomic sets of the model. An atomic set is a group of features (at least one) that can be treated as a unit when performing certain analyses.
The intuitive idea behind atomic sets is that mandatory features and their parent features always appear together in products and therefore can be grouped without altering the result of certain operations. Once atomic sets are computed, these can be used to create a reduced version of the model simply by replacing each feature with the atomic set that contains it.

Figure 13 depicts an example of atomic sets computation. Four atomic sets are derived from the original model, reducing the number of features from 7 to 4. Note that the reduced model is equivalent to the original one since both represent the same set of products.


Figure

Figure 13: Atomic sets computation

Using this technique, mandatory features are safely removed from the model. This operation is used as an efficient preprocessing technique to reduce the size of feature models prior to their analysis [70,102].


5.15
  Dependency analysis

This operation takes a feature model and a partial configuration as input and returns a new configuration with the features that should be selected and/or removed as a result of the propagation of constraints in the model [55]. As an example, consider the input and output configurations described below and the model in Figure 1.

Input = ({MobilePhone,Calls,Camera}, {MP3})
Output = 
  ({MobilePhone,Calls,Camera,Media,Screen,High resolution},
   {MP3,Basic,Colour})

Features Screen and High resolution are added to the configuration to satisfy the requires constraint with Camera. Media is also included to satisfy the parental relationship with Camera. Similarly, features Basic and Colour are removed to fulfil the constraints imposed by the alternative relationship.

This operation is the basis for constraint propagation during the interactive configuration of feature models [55]


5.16
  Multi-step configuration

A multi-step configuration problem is defined as the process of producing a series of intermediate configurations, i.e. a configuration path, going from a feature model configuration to another [97]. An analysis operation solving a multi-step configuration problem takes as input a feature model, an initial configuration, a desired final configuration, a number of steps in the configuration path K, a global constraint that can not be violated (usually referred to feature attributes) and a function determining the cost to transition from one configuration in step T to another in step U. As a result, the operation provides an ordered list of K configurations that determines the possible steps that can be taken to go from the initial configuration to the desired final configuration without violating the feature model and global constraints. For a detailed example and a rigorous definition of the operation we refer the reader to [97].


5.17
  Other operations

In this section, we group those operations that perform some computation based on the values of previous operations. We also classify in this group those analysis operations proposed as part of other algorithms.

Homogeneity. This operation takes a feature model as input and returns a number that provides an indication of the degree to which a feature model is homogeneous [36]. A more homogeneous feature model would be one with few unique features in one product (i.e. a unique feature appears only in one product) while a less homogeneous one would be one with a lot of unique features. According to [36] it is calculated as follows:

Homogeneity = 1 −
#uf
#products

#uf is the number of unique features in one product and #products denotes the total number of products represented by the feature model. The range of this indicator is [0,1]. If all the products have unique features the indicator is 0 (lowest degree of homogeneity). If there are no unique features, the indicator is 1 (highest degree of homogeneity).

Commonality.This operation takes a feature model and a configuration as inputs and returns the percentage of products represented by the model including the input configuration. An as example, consider the partial configurations described below and the model in Figure 1:

C1 = {{Calls}, {}}
C2 = {{Calls},{MP3}}

The commonality of both configurations is calculated as follows:

Comm(C1) =
|filter(FM,{{Calls}, {}}) |
#products(FM)
=
14

14
= 1

Comm(C2) =
|filter(FM,{{Calls}, {MP3}}) |
#products(FM)

=
7
14
= 0.5

The range of this indicator is [0,1]. Configuration C1 appears in 100% of the products whereas C2 is included only in 50% of them.

This operation may be used to prioritize the order in which the features are going to be developed [77] or to decide which features should be part of the core architecture of the software product line [61].

Variability factor. This operation takes a feature model as input and returns the ratio between the number of products and 2n where n is the number of features considered. In particular, 2n is the potential number of products represented by a feature model assuming that any combination of features is allowed. The root and non-leaf features are often not considered. As an example, the variability of the feature model presented in Figure 1 taking into account only leaf features is:

N.Products
2n
=
14
27
= 0.0625

An extremely flexible feature model would be one where all its features are optionals. For instance, the feature model of Figure 14 has the following variability factor:

N.Products
2n

=
8
23
= 1


Figure

Figure 14: Sample feature model with three optional features

The range of this indicator would depend on the features considered to calculate the factor. The feature model variability can be used to measure the flexibility of the feature model. For instance, a small factor means that the number of combinations of features is very limited compared to the total number of potential products.

Degree of orthogonality. This operation takes a feature model and a subtree (represented by its root feature) as input and returns their degree of orthogonality. Czarnecki et al. [30] defines the degree of orthogonality as the ratio between the total number of products of the feature model and the number of products of the subtree. Only local constraints in the subtree are considered for counting the products. For instance, the formula below shows the degree of orthogonality for the subtree Screen in Figure 1.

Orthogonality(Screen) =
14
3
= 4.66

The range of this indicator is (0,∞). A high degree of orthogonality indicates that decisions can be taken locally without worrying about the influence in the configuration of other parts of the tree [30].

Extra Constraint Representativeness (ECR). This operation takes a feature model as input and returns the degree of representativeness of the cross-tree constraints in the tree. Mendonça et al. [57,56] defines the Extra Constraint Representativeness (ECR) as the ratio of the number of features involved in cross-tree constraints (repeated features counted once) to the number of features in the feature tree. For instance, ECR in Figure 1 is calculated as follows:

ECR =
4
10
= 0.4

The range of this indicator is [0,1]. This operation has been used successfully to design and evaluate heuristics for the automated analysis of feature models [57].

Lowest Common Ancestor (LCA). This operation takes a feature model and a set of features as input and returns a feature that is the lowest common ancestor of the input features. Mendonça et al. [57] defines the Lowest Common Ancestor (LCA) of a set of features, LCA(FM,{f1,...,fn}), as the shared ancestor that is located farthest from the root. In Figure 1, LCA(FM,{Basic,Camera})=Mobile Phone.

Root features. This operation takes a feature model and a set of features as inputs and returns a set of features that are the roots features in the model. Given l = LCA(FM,{f1,...,fn}), Mendonça et al. [57] defines the roots of a set of features, Roots(FM,{f1,...,fn}) as the subset of child features of l that are ancestors of f1,...,fn. In Figure 1, Roots(FM,{Basic,Camera})={Media,Screen}.