Feature models are a wide-spread approach to variability and commonality management in software product lines. Due to the increasing size and complexity of feature models, anomalies in terms of inconsistencies and redundancies can occur which lead to increased efforts related to feature model development and maintenance. In this paper we introduce knowledge representations which serve as a basis for the explanation of anomalies in feature models. On the basis of these representations we show how explanation algorithms can be applied. The results of a performance analysis show the applicability of these algorithms for anomaly detection in feature models. We conclude the paper with a discussion of future research issues.
Similar to component-oriented configuration models [Felfernig et al., 2000; Felfernig, 2007], Feature Models (FM) [Kang et al., 1990] are used to express variability properties of highly-variant items [Mendonca and Cowan, 2010]. Applications based on feature models help users to decide about relevant features and to learn about existing dependencies between features. Feature models can be distinguished with regard to the expressiveness of constraints defining the relationships between the different features contained in a feature model [Benavides et al., 2010]. So-called basic feature models [Kang et al., 1990] will be used as a basis for the discussions in this paper. Such models allow the definition of basic relationships between features, for example, a feature f1 requires the inclusion of a feature f2. Cardinality-based feature models [Czarnecki et al., 2005] extend basic ones by also allowing cardinalities with an upper bound > 1. Finally, extended feature models [Batory, 2005] allow the inclusion of additional information about features in terms of feature attributes. For presentation purposes we decided to use basic feature models (see Section 2). However, the presented concepts and algorithms can be applied to advanced feature model representations as well.
Developing and maintaining large and potentially complex feature models is an error-prone activity which can be explained by the cognitive overload of software engineers and domain experts [Trinidad et al., 2008; Benavides et al., 2013]. In order to tackle this challenge, feature model development and maintenance processes have to be supported by intelligent techniques and tools which help to identify anomalies which become manifest in different types of inconsistencies and redundancies [Batory et al., 2006; Benavides et al., 2010]. An approach to the identification of dead features (features not part of any configuration) is presented by Trinidad et al. [Trinidad et al., 2008]. The authors also introduce concepts to solve the problem of void feature models (no configuration exists that fulfills all the constraints in the feature model). For the identification of faulty relationships in the feature model (in these scenarios) the authors define a corresponding diagnosis task which is based on the concepts introduced by [Reiter, 1987]. As an alternative to the approach of [Trinidad et al., 2008], White et al. [White et al., 2010] show how to transform feature models into a corresponding representation of a constraint satisfaction problem (CSP) [Tsang, 1993]. On the basis of this representation, diagnoses are directly determined by the constraint solver without the support of an additional diagnostic engine. An overview of analysis operations (for the identification of different inconsistencies and redundancies) for feature models is provided in [Benavides et al., 2010; von der Massen and Lichter, 2004].
If we are interested in minimal explanations (diagnoses) for feature model anomalies, the performance of the underlying algorithms becomes a challenge. An example explanation in this context would be the minimal set of constraints which have to be adapted or deleted from an inconsistent feature model (the determination of a configuration is not possible) such that the remaining constraints allow the calculation of at least one configuration. Reiter [Reiter, 1987] introduced a hitting set based approach to the determination of minimal explanations (diagnoses) – these diagnoses are also of minimal cardinality since diagnosis search is performed on the basis of breadth-first search. The idea of applying the concepts of model-based diagnosis to inconsistent constraint sets has first been introduced by Bakker et al. [Bakker et al., 1993]. Felfernig et al. [Felfernig et al., 2004] continued this work by introducing an approach to the automated testing and debugging of configuration knowledge bases where test cases are used to induce conflicts in the knowledge base. These conflicts are then resolved on the basis of the hitting set algorithm [Reiter, 1987]. First experiences from the application of these testing and debugging approaches in industrial scenarios are reported by Fleischanderl [Fleischanderl, 2002]. Junker [Junker, 2004] introduced the QuickXPlain (QX) algorithm. QX is an efficient divide-and-conquer based approach to the determination of minimal conflicts which can then be exploited for the determination of diagnoses. In this paper we show how diagnosis and redundancy detection algorithms can be applied to support feature model analysis operations [Benavides et al., 2010]. In this context we show how to apply the diagnosis algorithm FASTDIAG [Felfernig et al., 2012] (an algorithm with no need of determining conflict sets) and introduce the FMCORE algorithm which allows the detection of redundancies in feature models.
The work presented here is in the line of research dedicated to the development of intelligent quality assurance mechanisms for configuration knowledge bases [Felfernig et al., 2004]. The major contributions of this paper are the following. First, we advance the state of the art in feature model anomaly detection by formalizing the anomaly types discussed in the feature modeling community on the basis of the concepts of inconsistency and redundancy. Second, we introduce the FMCORE algorithm for the detection of redundant constraints in feature models. Furthermore, we show how to apply the FASTDIAG algorithm [Felfernig et al., 2012] for explaining different types of inconsistencies in feature models. All anomaly types will be discussed in detail in Section 3 in combination with corresponding explanation approaches.
The remainder of this paper is organized as follows. In Section 2 we introduce a simple feature model (operating system configuration) which will be used as working example throughout the paper. Furthermore, we introduce the definitions of a feature model configuration task and a corresponding feature model configuration . In Section 3 we introduce different relevant forms of anomalies in feature models together with their formal definitions. The corresponding anomaly detection algorithms FASTDIAG and FMCORE are explained in Section 4. The performance of these algorithms is analyzed in Section 5 on the basis of selected feature models from the S.P.L.O.T.1 repository. A discussion of further research issues and a conclusion is provided in Section 6. 2
A feature model (FM) defines a set of possible products of a domain in terms of features and the relationships between them [Wang et al., 2010]. Features are arranged hierarchically (tree structure with one so-called root feature fr (fr = true)) [Benavides et al., 2010] where the nodes are the features and the edges are relationships (constraints) [Segura et al., 2010]. For a more detailed overview of different feature model representations we refer the reader to [Batory, 2005; Benavides et al., 2010].
is based on the notation introduced in [Benavides et al., 2010]. Relationships (constraints) in FMs are represented in terms of six different types of constraints [Batory, 2005; Benavides et al., 2010; Segura et al., 2010]: mandatory, optional, alternative, or, requires, and excludes. FMs are representing configurable products which can be formalized in the form of a constraint satisfaction problem (CSP) [Tsang, 1993] where each variable fi has the assigned domain di = {true, f alse}. We define a feature model configuration task as follows (see Definition 1).
Definition 1 (FM Configuration Task) . A feature model (FM) configuration task is defined by the triple (F,D,C) where F = {f1, f2, ..., fn} is a set of features fi, D = {dom(f1), dom(f2), ..., dom(fn)} (dom(fi) = {true, f alse}) is the set of corresponding feature domains, and C = CR ∪ CF is a set of constraints restricting the possible configurations which can be derived from the feature model. In this context, CR = {c1, c2, ..., ck} represents a set of requirements (of a specific user) and CF = {ck+1, ck+2, ..., cm} a set of feature model constraints.
On the basis of this definition of an feature model configuration task, we now introduce the definition of a configuration for a feature model (FM) configuration task (Definition 2).
configuration for a given FM configuration task is a complete assignment of the variables fi ∈ F . Such a configuration is consistent iff the constraints ci ∈ C are not contradicting with the variable assignment. Furthermore, an FM configuration is valid, if it is consistent and complete.
constraints can be included in CF [Benavides et al., 2010]. These constraint types are the following – their representation in a graphical feature model is shown in the example of Figure 1. In the following we introduce the semantics of these six types of constraints – this semantics is based on the definition given in [Benavides et al., 2010].
Mandatory: a feature f2 ∈ F is mandatory if it is in a mandatory relationship with another feature f1 ∈ F . This means, if f1 is part of the configuration, f2 must be part of the configuration as well (and vice-versa). The formalization of this constraint type (relationship) is realized on the basis of an equivalence: f1 ↔ f2. In Figure 1 the feature gui is a mandatory feature connected to the feature ubuntu.
Optional: a feature f2 ∈ F can (but must not) be included in the configuration in the case that feature f1 ∈ F is part of the configuration. This type of constraint can be formalized on the basis of an implication: f2 → f1. In Figure 1 the feature games is an optional feature connected to ubuntu.
Alternative: only one feature fb ∈ F = {f1, f2, ..., fk} can be selected if feature fa is selected. The property can be formalized as follows: f1 = true ↔ (f2 = f alse∧...∧fk = f alse ∧ fa = true) ∧ ... ∧ fk = true ↔ (f1 = f alse ∧ ... ∧ fk − 1 = f alse ∧ fa = true). In Figure 1 an example of a feature fa is games, the subfeatures are gnuchess and glchess.
Or: at least one feature fb ∈ F = {f1, f2, ..., fk} must be part of the configuration if feature fa is part of the configuration. This property can be formally defined with fa ↔ {f1, f2, ..., fk}. In Figure 1 an example of a feature fa is gui, the subfeatures are kde and gnome.
Requires: a feature f2 must be included in a configuration if feature f1 is included. This requires relationship can be defined with f1 → f2. In Figure 1 an example of a requires relationship is games → gui.
Excludes: it is not allowed to combine two features f1 and f2 in the same configuration, i.e., feature f1 excludes feature f2 and vice versa: ¬(f1 ∧ f2). In Figure 1 an example of an excludes relationship is ¬(bash ∧ gui). Note that this is a possible faulty constraint to be detected by diagnosis.
Requires and excludes constraints are also denoted as cross-tree constraints. Finally, the set CR (customer requirements) is an additional set of constraints to be taken into account when determining configurations (solutions). The set CR specifies a set of key features which have to be included in the FM configuration for a specific user (customer).
Example Feature Model. A simple example feature model (from the domain of operating systems) is depicted in Figure 1. This model specifies a set of features relevant for configuring an ubuntu operating system installation together with constraints between the features. Note that faulty elements (constraints) are contained in this model – our goal in the remainder of this paper will be to introduce algorithms which help to identify and explain such faulty constraints.
The CSP-based representation [Tsang, 1993] of the feature model shown in Figure 1 is the following - a representation as FM configuration task = (F,D,C= CR ∪ CF ).
• F = {ubuntu, texteditor, bash, gui, games, gedit, vi, kde, gnome, gnuchess, glchess} • D = {dom(ubuntu) = {true, f alse}, dom(text− editor) = {true, f alse}, dom(bash) = {true, f alse}, dom(gui) = {true, f alse}, dom(games) = {true, f alse}, dom(gedit) = {true, f alse}, dom(vi) = {true, f alse}, dom(kde) = {true, f alse}, dom(gnome) = {true, f alse}, dom(gnuchess) = {true, f alse}, dom(glchess) = {true, f alse} • CR = {c0: ubuntu = true} • CF = { c1 : ubuntu ↔ texteditor, c2 : ubuntu ↔ bash, c3: ubuntu ↔ gui, c4: games → ubuntu, c5: texteditor ↔ gedit ∨ vi, c6: ¬texteditor ∨ ¬bash, c7: ¬bash ∨ ¬gui, c8: gui ↔ kde ∨ gnome, c9: games → gui, c10: (gnuchess ↔ ¬glchess ∧ games) ∧ (glchess ↔ ¬gnuchess ∧ games)}
Anomalies can be defined as patterns in data that do not conform to a well defined notion of normal behavior [Chandola et al., 2009]. Trinidad et al. [Trinidad et al., 2008] are using the term error for incorrect definitions of relationships , i.e., the set of products described by a feature model does not match the SPL (software product line) it describes. We interpret anomalies in the sense of [Trinidad et al., 2008]: undesirable FM properties in terms of different facets of contradictory and redundant information contained in the FM.
Handling Inconsistencies. Inconsistent feature models include contradictory constraints ci ∈ C that can not be satisfied at the same time, leading to no valid instances derivable from FMs [Wang et al., 2010]. For a given FM configuration task this means that no solution can be identified. In our working example (the FM of Figure 1) no solution can be identified due to an inconsistent constraint set C={c1, c2, ..., c10}.2 Inconsistent sets of constraints can be defined on the basis of the concept of conflict sets [Junker, 2004] (see Definition 3).
Definition 3 (Conflict Set) A conflict set CS ⊆ C is a set of constraints s.t. CS is inconsistent. CS is minimal iff there does not exist a conflict set CS0 with (CS0 ⊂ CS).
Based on Definition 3, we can identify minimal sets of constraints CSi ⊆ C, such that CSi is inconsistent. As long as there are conflicts in a given constraint set of a feature model, no solutions for the underlying FM configuration task can be identified. Our example feature model (see Figure 1) includes two minimal conflict sets which are CS1 = {c1, c2, c6} and CS2 = {c2, c3, c7}. Each of these sets is a minimal set such that (1) no solution (configuration) can be identified and (2) none of the subsets of CSi is inconsistent. As a consequence (due to their minimality property) conflicts (represented by conflict sets) can be resolved by simply deleting one constraint from the set.
The resolution of all conflicts (represented by conflict sets)
can be based on the determination of the corresponding
hitting sets
agnosis task (FM diagnosis task) is a tuple (S, AC) where S ⊆ AC are constraints of the feature model. The task is to identify a minimal set of constraints which have to be deleted from S s.t. consistency can be restored in the feature model.
In this context, S helps us to focus our diagnostic activities, i.e., to focus on those model parts where we suspect faulty constraints. If no such suspects exist, S can be set to AC. An FM diagnosis, i.e., a solution to an FM diagnosis task can be defined as follows (see Definition 5).
(FM diagnosis) is a set of constraints Δ ⊆ S with AC − Δ is consistent. Δ is minimal iff there does not exist a set Δ’ with Δ’ ⊂ Δ and Δ’ has the diagnosis property as well.
2Note that we interpret the constraint c0 : ubuntu = true as element of the (customer) requirements CR.
The diagnoses for our example FM diagnosis task are Δ1 = {c1, c3}, Δ2 = {c1, c7}, Δ3 = {c2}, Δ4 = {c3, c6}, Δ5 = {c6, c7}. These represent vfie ways to delete (adapt) constraints from (in) the feature model such that at least one configuration can be determined. The calculation of all Δi is sketched in Figure 2. The underlying assumption in this example is that – conform to the algorithm introduced by Reiter [Reiter, 1987] – the search tree (hitting set directed acyclic graph – HSDAG) is expanded in breadth-first manner.
One possible approach to determine the complete set of diagnoses is based on the hitting set directed acyclic graph (HSDAG) algorithm introduced by Reiter [Reiter, 1987]. The basic idea of this algorithm is to determine a conflict (in the example CS1 : {c1, c2, c6}) and then to resolve this conflict. If this conflict is resolved (e.g., by deleting the constraint c1) the algorithm checks whether further conflicts exist in the feature model. In our example this is the case and the next determined conflict set is CS2 : {c2, c3, c7}. If we delete, for example c3 from CS2, we receive the diagnosis Δ1 = {c1, c3}. In a similar fashion all other diagnoses can be determined. Note that {c1, c2} is not a (minimal) diagnosis since {c2} is already a diagnosis. The HSDAG algorithm is a traditional way of determining diagnoses – more efficient approaches will be presented in Section 4.
in more detail different basic types of feature model anomalies. Ways to explain these anomalies and related algorithms will then be discussed in detail in Section 4. An overview of these anomalies and related property checks is shown in Table 1. The following types of anomalies are taken from Benavides et al. [Benavides et al., 2010].
Void feature model. If model constraints in CF are inconsistent (inconsistent(CF ∪ c0)), we are interested in solutions to the FM diagnosis task (S=CF, AC = CF ∪ c0). In this case we want to figure out which are the minimal sets of constraints that are responsible for the given inconsistency in the feature model. We do not include c0 (e.g., c0 : ubuntu = true) in the set S since we are not interested in changing this constraint. The feature model of our example (see Figure 1) is an example of a void feature model.
Note that for the following discussions we assume that Δ5 = {c6, c7} (see Figure 2) has been chosen by the engineer and {c6, c7} have been deleted from the feature model.
Dead feature fi. If a feature fi is not included in any of the possible configurations (i.e., inconsistent(CF ∪ fi = true)), we are interested in solutions to the FM diagnosis task (S = CF, AC = CF ∪ {c0} ∪ {fi = true}). This way we are able to figure out the minimal sets of constraints that are responsible for the non-acceptance of fi. In our working example, there is no such dead feature (assuming that the constraints in Δ5 have been deleted from the feature model). If we would substitute the constraint c9 : games → gui with c9 : ¬gui ∨ ¬games, the feature games would be a dead feature. If we then want to make games a feature which is included in at least one configuration, the diagnoses for (S = CF, AC = CF ∪ {c0} ∪ {games = true}) are Δ1 = {c3} and Δ2 = {c9}.
Conditionally dead feature fi. Such a feature fi is not included in all of the possible configurations, i.e., consistent (CF ∪ {c0} ∪ {fi=false}) and consistent (CF ∪ {c0} ∪ {fi=true}). If we want to have fi in each configuration, we have to add {fi = true} to the set CF. In our working example, games is a conditionally dead feature since there are also solutions with no inclusion of this feature. In order to make games part of every possible feature model configuration, we have to make this clear in the feature model. One way to achieve this would be to convert constraint c4 into a mandatory constraint – this would have the same effect as adding games = true as an additional constraint to CF.
Full mandatory feature fi. A feature fi is fully mandatory if it is included in every possible solution (configuration), i.e., inconsistent(CF ∪ {c0} ∪ {fi = f alse}). If we want to adapt the feature model in such a way that it also allows fi to be not included, we can determine the corresponding (minimal) sets of responsible constraints by solving the FM diagnosis task (S=CF, AC= CF ∪ {c0} ∪ {fi = f alse}). In our working example, the feature gui is a full mandatory feature since it is part of every possible configuration. If we want to allow configurations where gui is not included, the only diagnosis for (S=CF, AC= CF ∪ {c0} ∪ {gui = f alse}) is Δ1 = {c3}.
False optional feature fi. A false optional feature fi is included in all configurations (e.g., products of a product line) although it has not been modeled as mandatory. If we replace the constraint c9 : games → gui with c9 : gui → games, the feature games becomes a false optional feature since it is included in every possible configuration. An alternative interpretation of a false optional feature focuses on the optional relationship between a feature fpar and fopt. If the consistency check of (CF ∪ {c0} ∪ {fpar = true ∧ fopt = f alse}) returns false (and fpar = true), the feature fopt is not an option. In our example (under the assumption that c9 is adapted as mentioned), the diagnosis for (S = CF, AC = CF ∪ {c0} ∪ {ubuntu = true ∧ games = f alse}) is Δ1 = {c3}.
Redundant constraint ci. In our working example the constraint c9 : games → gui is redundant since gui is a full mandatory feature. If we check the consistency of {CF - {c9} ∪ ¬CF} we see that c9 is redundant since the expression is inconsistent. In other words, CF - {c9} |= c9, i.e., c9 logically follows from CF - {c9} – therefore it is redundant. The second redundant constraint in our working example is c4 since the feature ubuntu is a full mandatory feature as well. Con
Void feature model Dead (fi) Conditionally dead (fi) Full mandatory (fi) False optional (fopt)
Property Check inconsistent(CF ∪ {c0})? inconsistent(CF ∪ {c0} ∪ {fi=true})? consistent(CF ∪ {c0} ∪ {fi=false}) and consistent(CF ∪ {c0} ∪ {fi=true})? inconsistent(CF ∪ {c0} ∪ {fi=false})? inconsistent(CF ∪ {c0} ∪ {fpar=true ∧ fopt=false})? inconsistent((CF ∪ {c0} - {ci}) ∪ ¬(CF ∪ c0))?
FASTDIAG(CF,CF ∪ {c0}) FASTDIAG(CF,CF ∪ {c0} ∪ {fi = true}) CF ← CF ∪ {fi=true} FASTDIAG(CF,CF ∪ {c0} ∪ {fi = f alse}) FASTDIAG(CF, CF ∪ {c0} ∪
{fpar = true ∧ fopt = f alse}) ci ∈/ FMCORE(CF ∪ {c0}) sequently, the constraints {c4, c9} can be deleted from the feature model without changing the underlying semantics.3
In the following section we focus on the presentation of two algorithms which help to determine explanations for the different feature model anomaly patterns. 4
The two basic algorithms for determining diagnoses and redundancies are FASTDIAG and FMCORE. FASTDIAG [Felfernig et al., 2012] is a divide-and-conquer algorithm that supports the efficient determination of minimal diagnoses without the need of having conflict sets available. FMC ORE is an algorithm which focuses on the determination of minimal cores, i.e., redundancy-free subsets of a constraint set.
rithm 1), the set S represents the set of constraints where a diagnosis should be searched, The set AC contains all constraints of the feature model. For example, if we want to diagnose a void feature model (CF ∪ {c0} is inconsistent – see Table 1), we would activate the algorithm with FASTDIAG(CF,CF ∪ {c0}), i.e., S = CF and AC = CF ∪ {c0}. We do not include c0 in the set of diagnosable constraints since c0 (the root constraint) is assumed to be correct (e.g., c0 : ubuntu = true). First, the algorithm (see Algorithm 1) checks whether the considered constraint set can be diagnosed (if the set S is empty, no diagnosis will be found) and whether the constraints in AC-S are inconsistent (in this case no diagnosis can be determined).
if isEmpty(S) or inconsistent(AC − S) then return ∅; else
return DIAG(∅, S, AC) end if
The major idea of FASTDIAG (and its subfunction DIAG – see Algorithm 2) is to divide a set S of inconsistent constraints into two subsets S1 and S2. If the first part becomes 3Note that redundancies can also be intended to achieve goals such as improving understandability or increasing efficiency – a discussion of related issues is outside the scope of this paper. Algorithm 2 DIAG(D, S = {s1, ..., sr}, AC): Δ if D 6= ∅ and consistent(AC) then
return ∅; end if if singleton(S) then
return S; end if k ← d 2r e; S1 ← {s1, ..., sk}; S2 ← {sk+1, ..., sr}; Δ1 ← DIAG(S2, S1, AC − S2); Δ2 ← DIAG(Δ1, S2, AC − Δ1); return(Δ1 ∪ Δ2); consistent, the diagnosis is searched in the other part and the first part can be omitted (no constraints part of the diagnosis will be found there). If a singleton constraint of S triggers an inconsistency, this constraint is considered a part of the diagnosis. FASTDIAG determines exactly one diagnosis at a time. If we want to determine more than one or even the complete set of diagnoses, we need to combine FASTDIAG with a corresponding algorithm that supports the construction of HSDAGs. The discussion of this approach is outside the scope of this paper. We want to refer the reader to the work of Felfernig et al. [Felfernig et al., 2012]. Compared to traditional diagnosis approaches, FASTDIAG needs in the worst case 2d × log2( n ) + 2d consistency checks where d is d the number of constraints in the minimal diagnosis and n is the number of constraints in S [Felfernig et al., 2012]. The corresponding best case complexity in terms of the number of consistency checks is log2( nd +2d). A similar worst case (and best case) complexity in traditional diagnosis approaches can be expected for each determination of a conflict set (see, e.g., Figure 2) [Felfernig et al., 2012].
Determination of Redundancies. A constraint fi of a feature model (represented by the constraint set CF) is redundant if its deletion from the model does not change the set of possible solutions. More formally, CF - {fi} |= fi which means that fi logically follows from CF - {fi} and therefore is redundant. An algorithm for redundancy detection should definitely not check redundancy properties on the basis of concrete configurations since such an approach becomes comFeature Model: Car Selection # Diagnoses pletely inefficient even in the case of simple feature models. The basic idea of the FMCORE algorithm is to iterate over the given set of constraints (S) and for each constraint ci ∈ S to check whether the deletion of ci changes the semantics of S. The assumption is that if ci is non-redundant, its deletion from S will change the semantics of S, i.e., S − {ci} ∪ S becomes consistent. All these individual redundant constraints are deleted from Stemp (a temporal copy of S). Finally, the algorithm returns the set Stemp which represents a minimal core, i.e., the original set S without redundant constraints.
Note that – instead of checking the inconsistency of CS −
{ci} ∪ S
The number of consistency checks of FMCORE in the best case equals the number of consistency checks in the worst case – in both cases the number of consistency checks needed is exactly n (the number of constraints in S).
In order to analyze the performance of FASTDIAG and FMCORE we conducted a performance analysis for both al
{S: the (redundant constraint set)} {S: the complement of S} {Δ: set of redundant constraints} Stemp ← S; for all ci in Stemp do if isInconsistent((Stemp − {ci}) ∪ {¬cj }) then
Stemp ← Stemp − {ci}; end if end for return Stemp; gorithms on the basis of different feature models provided by the S.P.L.O.T. repository. The results of this analysis are presented in the following section. 5
For evaluation purposes we selected different feature models offered by the S.P.L.O.T. repository: Car Selection (Table 2), SmartHome V. 2.2. (Table 3), and Xerox (Table 4). In order to evaluate the performance of FASTDIAG, we randomly inserted additional cross-tree constraints in the feature models for inducing inconsistencies which could then be exploited for determining minimal diagnoses. For a systematic evaluation we generated different versions of the (inconsistent) feature models which differed in terms of their inconsistency
Feature Model: Xerox # Diagnoses rate (see Formula 1) which was categorized in {2%, 5%, 7%}. We used a random variable to control the degree of generated inconsistencies (the number of conflicts) in a feature model. As reasoning engine we used the CHOCO constraint solving library.4 In order to import feature models to our environment we implemented a parser that generated CHOCO knowledge bases from S.P.L.O.T. SXFM based feature models.
Inconsistency Rate =
#conf licts in F M #constraints in F M (1)
The performance tests were executed within a Java application running on a 64bit Windows 7 desktop PC using 8GB RAM and an Intel(R) Core(TM) i5-2320 CPU with 3.0GHz. Each run of the diagnosis algorithm for a specific setting has been repeated 10 times were in each run the ordering of the constraints was randomized. For each setting we evaluated the runtime (in ms) of both, the standard hitting set based approach to the termination of diagnoses [Reiter, 1987] (HSDAG) and FASTDIAG. As scenario we choose the diagnosis of void feature models where we induced different degrees of inconsistency (based on the inconsistency rate measure – see Formula 1). The upper bound for the evaluation time was set to 100.000 ms – in the case that this upper limit was exceeded, the search was stopped.
If one or a few diagnoses are required (which is typical for interactive settings) then FASTDIAG outperforms the standard HSDAG approach in most of the cases. If all diagnoses are required, for example, in situations where diagnoses are computed offline, the standard HSDAG approach seems to be the better choice. We want to emphasize that the presented diagnosis algorithms are independent of the underlying reasoning mechanisms, i.e., beside using a basic constraint-based approach for supporting the reasoning tasks (mainly consistency checking), description logics or SAT-based approaches can be applied as well. Finally, we also evaluated the performance of the redundancy detection algorithm FMCORE (see Table 5). Our goal was to figure out for the selected feature models to which extent the constraints in the feature models are redundant. We measured redundancy in the terms of the redundancy rate (see Formula 2).
#redundant constraints in F M
#constraints in F M Redundancy Rate = (2)
The outcome of this analysis was that all the investigated feature models showed quite different degrees of redundancy (see Table 5). However, we consider these as preliminary results and further analyses have to be conducted, for example, we are interested in intra-constraint redundancies and the share of redundancy in cross-tree constraints with regard to the overall number of constraints in the feature model.
Note that the FMCORE algorithm is especially useful in
situations where models are developed by one or a few
engineers. In this case the degree of redundant constraints in
the model is low. For scenarios with high redundancy rate,
alternative algorithms have already been developed
In this paper we presented a consistency-based approach to explaining anomalies in feature models. We introduced definitions which are useful for the explanation of anomalies and discussed the corresponding algorithms which help to determine minimal diagnoses (FASTDIAG) and minimal sets of non-redundant constraints (FMCORE). Our future work will focus on: (1) The definition of further anomaly patterns in alternative knowledge representations such as advanced feature models [Batory, 2005] and UML models [Felfernig et al., 2000]. Due to higher expressiveness, these representations include further anomaly patterns such as multiplicity bounds which can not represented by configurations, unsatisfiable preconditions in constraints, and unexplained incompatibilities. (2) The development of mechanisms for the automated generation of test cases for feature models. (3) Further algorithms that enable the determination of diagnoses and redundancies on an intra-constraint level. (4) Evaluation of the developed algorithms with further benchmarks. mass customization. IEEE Transactions on Engineering Management, 54:41–56, 2007.