Companies often develop in a non-disciplined manner a set of software variants that share some features and di er in others to meet variant-speci c requirements. To exploit existing software variants and manage them coherently as a software product line, a feature model must be built as a rst step. To do so, it is necessary to extract mandatory and optional features from the code of the variants in addition to associate each feature implementation with its name. In previous work, we automatically extracted a set of feature implementations as a set of source code elements of software variants and documented the mined feature implementations based on the use-case diagrams of these variants. In this paper, we propose an automatic approach to organize the mined documented features into a feature model. The feature model is a tree which highlights mandatory features, optional features and feature groups (and, or, xor groups). The feature model is completed with requirement and mutual exclusion constraints. We rely on Formal Concept Analysis and software con gurations to mine a unique and consistent feature model. To validate our approach, we apply it on several case studies. The results of this evaluation validate the relevance and performance of our proposal as most of the features and their associated constraints are correctly identi ed.
To exploit existing software variants and build a software product line (SPL),
a feature model (FM) must be built as a rst step. To do so, it is necessary to
extract mandatory and optional features in addition to associate each feature
with its name. In our previous work [
Dependencies between features need to be expressed via a FM which is a
de facto standard formalism [
P-1
P-2
P-3
P-4
P-5
P-6
P-7
P-8
P-9
P-10
P-11
P-12
P-13
P-14
P-15
P-16
t
n
e
n
o
e lreay lreay lppO
lleohnPC lirsseeW fIrreadn ltteoohuB lleccuCA trogSn ieudmM eakW lisaypD seaGm iltuPM ilegnSP iiifrtcaA
cepts from a dataset, called a formal context, composed of objects described by
attributes. In our approach, we consider the AOC-poset (for
Attribute-ObjectConcept poset) [
Manual construction of a FM is both time-consuming and error-prone [
The remainder of this paper is structured as follows: Section 2 presents the reverse engineering FM process step-by-step. Next, Section 3 presents the way that we propose to evaluate the obtained FMs. Section ?? describes the experimentation and threats to the validity. Section 4 discusses the related work. Finally, in Section 5, we conclude this paper. 2
This section presents step-by-step the FM reverse engineering process. According to our approach, we identify the FM in seven steps as detailed in the following, using strong properties of FCA to group features among product con gurations. The AOC-poset is built from a set of known products, and thus does not represent all possible products. Thus, the FM structure has to be considered only as a candidate feature organization that can be proposed to an expert. The algorithm is designed such that all existing products (used for construction of candidate FM) are covered by the FM. Besides, it allows to de ne possible unused close variants.
The rst step of our FM extraction process is the identi cation of the
AOCposet. First, a formal context, where objects are software product variants and
attributes are features (cf. Figure 1), is de ned. The corresponding AOC-poset
is then calculated. The intent of each concept represents features common to
two or more products or unique to one product. As AOC-posets are ordered, the
intent of the most general (i.e., top) concept gathers mandatory features that
are common to all products. The intents of all the remaining concepts represent
the optional features. The extent of each of these concepts is the set of products
sharing these features (cf. Figure 2). In the following algorithms, for a Concept C,
we call intent(C), extent(C), simplif ied intent(C), and simplif ied extent(C)
its associated sets. E cient algorithms can be found in [
The other steps are presented in the next sections. 2 The eRCA : http://code.google.com/p/erca/ Algorithm 1 is a simple algorithm for building the Base node (cf. Figure 3). Features in the top concept of the AOC-poset (Concept 16) are used in every product con guration. The Cell Phone feature is the root feature of the cell phone FM (line 5). Then a mandatory Base node is created (lines 8,9). It is linked to nodes created to represent all the other features in the top concept, i.e., Accu Cell, Display and Games (lines 12-16).
Extracting atomic set of features (AND-group) Algorithm 2 is a simple algorithm for building AND-groups of features (excluding all the mandatory features, line 3). An AND-group of features is created (line 8) to group optional features that appear in the same simpli ed intent (test line 6), meaning that these features are always used together in all the product congurations where they appear. Lines 12-16, nodes are created for every feature of the AND-group and they are attached to an And node. For instance, Concept 23 in Figure 2 has a simpli ed intent with two features, Single Player and Arti cial Opponent, leading to the And node of Figure 3. 2.3
Extracting exclusive-or relation
Features that form exclusive-or relation can be identi ed in the concept lattice
using the meet (denoted by u) lattice operation [
Algorithm 3 is a simple algorithm for building the single Xor group of features. The principle is to traverse the set of super-concepts of each minimum elements of the AOC-poset and to keep the concepts that are the super-concepts of only one minimum concept. Only features that are not used in the previous steps are considered in FL" (line 2). Lines 6-10, in our example, we consider the three minimum concepts Concept 11, Concept 12 and Concept 15. The many SSC sets are the sets of super-concepts for Concept 11, Concept 12 and Concept 15. Cxor is the set of all concepts, except Concept 11, Concept 12 and Concept 15. Lines 11-15 only keep in Cxor concepts that do not appear in two SSC sets. Cxor contains concepts number 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14, 19, 20 and 21. Line 16 eliminates Concept 19 which is not a maximum. As there are three features (Medium, Strong, Weak, from Concept 21, Concept 20, and Concept 2 respectively) that are in FL" and in the simpli ed intent of concepts of Cxor (line 18), an Xor node is created and linked to the root (lines 19-26). Then, on lines 27-33, nodes are created for the features and linked to the Xor node. Figure 3 shows this Xor node. 2.4
Extracting inclusive-or relation Optional features are features that are used in some (but not all) product congurations. There are many ways of nding and organizing them. Algorithm 4 is a simple algorithm for building the Or group of features. In our approach, we pruned the AOC-poset by removing the top concept, concepts that correspond to AND groups of features, and concepts that correspond to features that form an exclusive-or relation. The remaining concepts de ne features that are grouped (lines 8-12) into an Or node (created and linked to the root on lines 4-7). In the AOC-poset of Figure 2, the Wireless, Infrared, Bluetooth, and Multi Player features form an inclusive-or relation (cf. Figure 3). 2.5
Extracting require constraints Algorithm 5 is a simple algorithm for identifying require constraints. A require constraint, e.g., saying "variable feature A always requires variable feature B", can be extracted from the lattice via implications. We say that A implies B (written A ! B). The require constraints can be identi ed in the AOC-poset: when a feature F1 is introduced in a subconcept of the concept that introduces another feature F2, there is an implication F1 ! F2. We only consider the transitive reduction of the AOC-poset limited to Attribute-concepts (line 2) and features that are in simpli ed intents (line 3-4). In the AOC-poset of Figure 2, we nd 6 require constraints from the transitive reduction of the AOC-poset to Algorithm 3: ComputeExclusive-or Relation (Xor)
Result: part of the FM with XOR group of features 1 // Compute exclusive-or relation 2 FL00 FL0 n AsFs 3 Cxor ; 4 SSCS ; // set of super-concept sets 5 Minimum-set ; 6 for each minimum of AOCK denoted by m do 7 Let SSC the set of super-concepts of m (except >) 8 SSCS SSCS [ fSSCg 9 Minimum-set Minimum-set [ fmg 10 Cxor Cxor [ SSC 11 while SSCS 6= ; do 12 SSC-1 any element in (SSCS) 13 SSCS SSCS n SSC-1 14 for each SSC-2 in SSCS do 15 Cxor Cxor n (SSC-1 \ SSC-2) 16 Cxor Max(Cxor) 17 XFS ; 18 if jCxorj > 1 and jF L00 \ [C2Cxorsimplif ied intent(C)j > 1 then 19 Create node xor with label (xor ) "XOR" 20 type (xor ) abstract 21 create edge e = (root, xor ) 22 // if all products are covered by Cxor 23 if [C2Cxorextent(C) = O then 24 type (e) mandatory attribute-concepts (cf. Figure 3). Remark that implications ending to mandatory features are useless because they are represented in the FM by the Base node. In our current proposal, we compute binary exclude constraints :(A ^ B) under the condition that A and B are not both linked to the Or group. To mine Algorithm 4: ComputeInclusive-orRelation (Or)
Result: part of the FM with OR group of features 1 // Compute inclusive-or relation 2 FL000 FL00 n XFS 3 if FL000 6= ; then 4 Create node or with label (or ) "OR" 5 type (or ) abstract 6 create edge e = (root, or )
8 for each F in FL000 do
Algorithm 5: ComputeRequireConstraint (Requires)
Result: Require - the set of require constraints 1 Require ; 2 for each edge (C1, C2) = e in transitive reduction of AC-poset do 3 for all f1, f2 with f1 2 simpli ed intent(C1) and f2 2 simpli ed intent(C2) do 4 Require Require [ ff1 ! f2g exclude constraints from an AOC-poset, we use the meet3 of the introducers of the two involved features. For example, the meet of Concept 2 which introduces Weak and Concept 22 which introduces Multi Player is the bottom (in the whole lattice). In the AOC-poset they don't have a common lower bound. We can thus deduce :(W eak ^ M ulti P layer). In the AOC-poset of Figure 2, there are three exclude constraints (cf. Figure 3). Algorithm 6 is a simple algorithm for identifying exclude constraints. It compares features that are below the OR group with each set of features in the intent of a minimum (line 4), in order to determine which are incompatible: this is the case for a pair (f1, f2) where f1 is in the OR group and not in the minimum intent, and f2 is in the minimum intent but not in the OR group (lines 6-10). Figure 3 shows the resulting FM based on the product con gurations of Figure 1.
Algorithm 6: ComputeExcludeConstraint (Excludes)
Result: Exclude - the set of exclude constraints. 1 // Minimum-set from Algorithm 3 2 // FL000 from Algorithm 4 3 Exclude ; 4 for each P 2 Minimum-set do 5 P intent intent(P ) n intent(>) 6 Opt-feat-set FL000 n (FL000 \ P intent) 7 Super-feat-set P intent n (FL000 \ P intent) 8 if Opt-feat-set 6= ; and Super-feat-set 6= ; then 9 for each f1 2 Opt-feat-set, f2 2 Super-feat-set do 10 Exclude Exclude [ f:(f1 ^ f2)g 3
In order to evaluate the mined FM we rely on the SPLOT homepage4 and the
FAMA Tool5. Our implementation6 converts the FM that has been drawn
using SPLOT homepage into the format of FAMA. Then, we can easily generate
a le containing all valid product con gurations [
To validate our approach7, we ran experiments on 7 case studies:
ArgoUMLSPL [
Results show that precision appears to be not very high for all case studies. This means that many of the identi ed product con gurations of the mined FM are extra con gurations (not in the initial set that is de ned by the original FM). Considering the recall metric, its value is 1 for all case studies. This means that product con gurations de ned by the initial FM are included in the product con gurations derived from the mined FM. Experiments show that if the generated AOC-poset has only one bottom concept there is no exclusive-or relation or exclude constraints from the given product con gurations. In our work, the mined FM de nes more con gurations than the initial FM. The reason behind this limitation is that some feature selection constraints are not detected. Nevertheless, the AOC-poset contains information for going beyond this limitation. We plan to enhance our algorithm to deal with that issue, at the price of an increase of complexity. 4
For the sake of brevity, we describe only the work that most closely relates to
ours. The majority of existing approaches are designed to reverse engineer FM
7 Source code: https://code.google.com/p/refmfpc/
8 http://www.ic.unicamp.br/~tizzei/phc/
from high level models (e.g., product descriptions) [
In this paper, we proposed an automatic approach to extract FMs from software variants con gurations. We rely on FCA to extract FMs including con guration constraints. We have implemented our approach and evaluated its produced results on several case studies. The results of this evaluation showed that the resulting FMs exactly describe the given product con guration set. The FMs are generated in very short time, because our FCA tool (based on traversals of the AOC-poset) scales signi cantly better than the standard FCA approaches to calculate and traverse the lattices. The current work extracts a FM with two levels of hierarchy. As a perspective of this work, we plan to enhance the extracted FM by increasing the levels of hierarchy based on AOC-poset structure and to avoid allowing the FM to represent extra con gurations.
Acknowledgment The authors would like to thank the reviewers for their valuable remarks that helped improve the paper. This work has been supported by the CUTTER ANR-10-BLAN-0219 project.