Guillaume Bécan

Mathieu Acher

Benoit Baudry

Sana Ben Nasr

Breathing Ontological Knowledge Into Feature Model Synthesis: An Empirical Study

Keywords: Software Product Lines, Feature Model, Variability, Model Management, Reverse Engineering, Refactoring Postgre SQL Programming EQ = { Programming Language, PHP => Programming Language

Feature Models (FMs) are a popular formalism for modeling and reasoning about the configurations of a software product line. As the manual construction of an FM is time-consuming and error-prone, management operations have been developed for reverse engineering, merging, slicing, or refactoring FMs from a set of configurations/dependencies. Yet the synthesis of meaningless ontological relations in the FM -as defined by its feature hierarchy and feature groups -may arise and cause severe difficulties when reading, maintaining or exploiting it. Numerous synthesis techniques and tools have been proposed, but only a few consider both configuration and ontological semantics of an FM. There are also few empirical studies investigating ontological aspects when synthesizing FMs.

In this article, we define a generic, ontologic-aware synthesis procedure that computes the likely siblings or parent candidates for a given feature. We develop six heuristics for clustering and weighting the logical, syntactical and semantical relationships between feature names. We then perform an empirical evaluation on hundreds of FMs, coming from the SPLOT repository and Wikipedia. We provide evidence that a fully automated synthesis (i.e., without any user intervention) is likely to produce FMs far from the ground truths. As the role of the user is crucial, we empirically analyze the strengths and weaknesses of heuristics for computing ranking lists and different kinds of clusters. We show that a hybrid approach mixing logical and ontological techniques outperforms state-of-the-art solutions. We believe our approach, environment, and empirical results support researchers and practitioners working on reverse engineering and management of FMs.

Introduction

Real world success stories of Software Product Lines (SPLs) show that the effective management of a large set of products is possible [START_REF]SEI's Software Product Line Hall of Fame[END_REF][START_REF] Linden | Software Product Lines in Action: The Best Industrial Practice in Product Line Engineering[END_REF]. The factorization and exploitation of common features of the products as well as the handling of their variability [START_REF] Apel | Feature-Oriented Software Product Lines: Concepts and Implementation[END_REF][START_REF] Apel | An overview of feature-oriented software development[END_REF][START_REF] Mussbacher | Aourn-based modeling and analysis of software product lines[END_REF][START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF] is an essential step for these stories. Large scale open source or industrial SPLs contain thousands of features and many logical dependencies among them [START_REF] Berger | A study of variability models and languages in the systems software domain[END_REF][START_REF] Berger | A survey of variability modeling in industrial practice[END_REF]. This complexity poses a challenge for both developers and users of SPLs.

Feature Models (FMs) are by far the most popular notation for modeling and reasoning about an SPL [START_REF] Berger | A survey of variability modeling in industrial practice[END_REF][START_REF] Hubaux | Separation of concerns in feature diagram languages: A systematic survey[END_REF]. FMs offer a simple yet expressive way to define a set of legal configurations (i.e., combinations of features) each corresponding to a product of an SPL [START_REF] Acher | Familiar: A domain-specific language for large scale management of feature models[END_REF][START_REF] Bagheri | Assessing the maintainability of software product line feature models using structural metrics[END_REF][START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF][START_REF] Kang | Feature-oriented product line engineering[END_REF][START_REF] Pohl | A performance comparison of contemporary algorithmic approaches for automated analysis operations on feature models[END_REF][START_REF] Pohl | Measuring the structural complexity of feature models[END_REF][START_REF] Sayyad | On the value of user preferences in search-based software engineering: a case study in software product lines[END_REF][START_REF] Thüm | Reasoning about edits to feature models[END_REF]. Another important and dual aspect of an FM is the way features are conceptually related. A treelike hierarchy and feature groups are notably used to organize features into multiple levels of increasing detail and define the ontological semantics [START_REF] Czarnecki | Feature models are views on ontologies[END_REF] of an FM.

A manual elaboration of an FM is not realistic for large projects or for legacy systems. Many procedures propose to reverse engineer dependencies and features' sets from existing software artefacts -being source code, configuration files, spreadsheets or requirements [START_REF] Acher | Extraction and evolution of architectural variability models in plugin-based systems[END_REF][START_REF] Acher | On extracting feature models from product descriptions[END_REF][START_REF] Dietrich | A robust approach for variability extraction from the linux build system[END_REF][START_REF] Ferrari | Mining commonalities and variabilities from natural language documents[END_REF][START_REF] Kästner | Variability mining: Consistent semiautomatic detection of product-line features[END_REF][START_REF] Nadi | Mining configuration constraints: Static analyses and empirical results[END_REF][START_REF] Rabkin | Static extraction of program configuration options[END_REF][START_REF] Rubin | Locating distinguishing features using diff sets[END_REF][START_REF] Rubin | Domain Engineering: Product Lines, Conceptual Models, and Languages, chap. A Survey of Feature Location Techniques[END_REF][START_REF] Ryssel | Extraction of feature models from formal contexts[END_REF][START_REF] She | Reverse engineering feature models[END_REF][START_REF] Vacchi | Automating Variability Model Inference for Component-Based Language Implementations[END_REF][START_REF] Valente | A semi-automatic approach for extracting software product lines[END_REF][START_REF] Weston | A framework for constructing semantically composable feature models from natural language requirements[END_REF]. From these logical dependencies (typically formalized and encoded as a propositional formula in conjunctive or disjunctive normal form), numerous FMs can represent the exact same set of configurations, out of which numerous candidates are obviously not maintainable since the retained hierarchy is not adequate [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] She | Reverse engineering feature models[END_REF]. An example of such an FM is given in Figure 1a.

Both configuration and ontological aspects are important when managing FMs. First, the proper handling of configuration semantics is unquestionable. Otherwise the FM may expose to customers configurations that actually do not correspond to any existing product [START_REF] Apel | Strategies for productline verification: Case studies and experiments[END_REF][START_REF] Classen | Symbolic model checking of software product lines[END_REF][START_REF] Classen | Model checking lots of systems: efficient verification of temporal properties in software product lines[END_REF][START_REF] Czarnecki | Verifying feature-based model templates against wellformedness ocl constraints[END_REF][START_REF] Thaker | Safe composition of product lines[END_REF]. Second, a doubtful feature hierarchy may pose severe problems for a further exploitation by automated transformation tools or by stakeholders (humans) that need to understand, maintain and exploit an FM -as it is the case in many FM-based approaches [START_REF] Acher | Extraction and evolution of architectural variability models in plugin-based systems[END_REF][START_REF] Apel | An overview of feature-oriented software development[END_REF][START_REF] Classen | Model checking lots of systems: efficient verification of temporal properties in software product lines[END_REF][START_REF] Czarnecki | Generative Programming: Methods, Tools, and Applications[END_REF][START_REF] Czarnecki | Verifying feature-based model templates against wellformedness ocl constraints[END_REF][START_REF] Heidenreich | Relating feature models to other models of a software product line: A comparative study of featuremapper and vml*[END_REF][START_REF] Hubaux | Separation of concerns in feature diagram languages: A systematic survey[END_REF][START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF]. Figure 1b depicts a highly questionable user interface of a configurator that could have been generated from the FM of Figure 1a and illustrates the consequence of an inappropriate treatment of the ontological semantics.

The problem addressed in this article can be formulated as follows: How to automate the synthesis of an FM from a set of dependencies while both addressing the configuration and ontological semantics? Is it feasible to fully synthesize an FM? Can we compute the likely siblings or parent candidates for a given feature? Given a set of dependencies, we challenge synthesis techniques to assist in selecting a feature hierarchy as close as possible to a ground truth -without an a priori knowledge of the ground truth.

Several synthesis techniques for FMs have been proposed, mostly in the context of reverse engineering FMs, but they neglected either configuration or Fig. 1: What practitioners do not want. At the bottom, a non intuitive user interface of a configurator that could have been generated from f m u due to its doubtful ontological semantics. ontological semantics of an FM [START_REF] Acher | Extraction and evolution of architectural variability models in plugin-based systems[END_REF][START_REF] Acher | On extracting feature models from product descriptions[END_REF][START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF][START_REF] Haslinger | Reverse engineering feature models from programs' feature sets[END_REF][START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF][START_REF] Janota | Model construction with external constraints: An interactive journey from semantics to syntax[END_REF][START_REF] Lopez-Herrejon | Reverse engineering feature models with evolutionary algorithms: An exploratory study[END_REF][START_REF] Lopez-Herrejon | An assessment of search-based techniques for reverse engineering feature models[END_REF][START_REF] Ryssel | Extraction of feature models from formal contexts[END_REF][START_REF] Weston | A framework for constructing semantically composable feature models from natural language requirements[END_REF][START_REF] Yi | Mining binary constraints in the construction of feature models[END_REF]. There are also few empirical studies investigating how the synthesis techniques behave when ontological aspects of FMs do matter [START_REF] Ahnassay | Empirical evaluation in software product line engineering[END_REF].

In previous work [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF], we proposed some basic support to guide the synthesis process, but users have to manually choose a relevant hierarchy among thousands of possibilities. It is time-consuming, error-prone, and non realistic for large projects with hundreds or thousands of features. A notable exception is She et al. [START_REF] She | Reverse engineering feature models[END_REF] who proposed a procedure to rank the correct parent features in order to reduce the task of a user. However they assume the existence of textual artefacts describing features, only consider possible parent-child relationships, and the experimented heuristics have been evaluated only in the operating system domain.

In this article we describe a generic ontologic-aware FM synthesis procedure. The heuristics rely on general ontologies, e.g. from Wordnet or Wikipedia. They are sound, applicable without prior knowledge or artefacts, and can be used either to fully synthesize an FM or guide the users during an interactive process. We also propose a hybrid solution combining both ontological and logical techniques.

We perform an empirical evaluation on 156 sets of dependencies for which we have a ground truth FM. We use two data sets: [START_REF]SEI's Software Product Line Hall of Fame[END_REF] the SPLOT repository [START_REF]SPLOT: Software Product Line Online Tools[END_REF] and (2) large FMs extracted from product comparison matrices (PCMs) found in Wikipedia [START_REF] Sannier | From Comparison Matrix to Variability Model: The Wikipedia Case Study[END_REF]. FMs come from different domains and their complexity vary. In average, there are 18 features per FM of SPLOT, 72 features per FM of PCMs, and about 7 parent candidates per features to consider. We empirically characterize the strengths and limits of state-of-the-art automated techniques in the quest of breathing ontological knowledge into FM synthesis. The experiments also show that a hybrid approach provides the best support for fully synthesizing an FM and computing ranking lists.

Specifically, we make the following contributions:

-We develop six heuristics for clustering and ranking the syntactic/semantic relationships between feature names. We also adapt logical heuristics so that they can be applied before "breathing ontological knowledge" into FM synthesis; -We develop WebFML [START_REF] Bécan | WebFML: Synthesizing Feature Models Everywhere[END_REF], an environment that integrates all the techniques and supports practitioners in synthesizing sound and meaningful FMs from various kinds of artefacts (e.g. propositional formula, dependency graph, FMs or product comparison matrices). We are unaware of such an environment despite the availability of a wide range of academic or industrial feature modeling tools [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF][START_REF] Krueger | Biglever software Gears and the 3-tiered spl methodology[END_REF][START_REF] Mendonca | software product lines online tools[END_REF][START_REF] Pleuss | Visualization of variability and configuration options[END_REF]74,[START_REF] Thüm | Featureide: An extensible framework for feature-oriented software development[END_REF][START_REF] Weston | A framework for constructing semantically composable feature models from natural language requirements[END_REF]; -The empirical evaluation shows that the hybrid approach can retrieve, in average, 37.8% of parent-child relationships of the SPLOT FMs (44.4% for the PCM dataset) in one step and without any user intervention. Although the hybrid approach constitutes the state-of-the-art heuristic, the results show that a fully automated synthesis is likely to produce FMs far from the ground truths. We provide empirical evidence that the role of the user remains crucial and we highlight the interactive nature of the synthesis process; -The hybrid approach ranks the correct parent among the 2 first results for 58.9% of the features (for the SPLOT dataset) and 56.3% of the features (for the PCM dataset). The clusters retrieved by the hybrid approach are correct in more than half of the time while the number of clusters to review remains rather low (4.1 for the SPLOT dataset, 17.6 for the PCM dataset);

Refactoring

!

Fig. 2: A key issue for automated operations: numerous FMs conformant to the configuration semantics of φ exist but are likely to have an inappropriate ontological semantics.

-We compare our method with an existing technique [START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF] and logical-based heuristics. Based on empirical results, we analyze the strengths, weaknesses and possible synergies between logical and ontological-based techniquesleading to the design of a hybrid approach.

The contributions not only advance the state-of-the-art of reverse engineering FMs. Important management operations of FMs (slicing, merging, diff, refactoring) also benefit from ontological capabilities since all are based on the synthesis procedure (see Fig. 2). Our approach, environment and empirical results open avenues for practical reverse engineering or maintenance of software product lines more and more reported in the industry or observed in the open source community.

The remainder of the article is as follows. In Section 2, we introduce the syntax and the two kinds of semantics (configuration and ontological) of FMs. In Section 3, we motivate and define the ontologic-aware FM synthesis problem. In Section 4, we present generic, automated techniques for breathing ontological knowledge into FM synthesis. In Section 5, we describe and illustrate the integration of the synthesis techniques into the WebFML environment. In Section 6, we perform an empirical evaluation, analyze the results and discuss the key findings. In Section 7, we discuss threats to internal and external validity. In Section 8 we point out the differences and synergies between existing works and our proposal. In Section 9 we summarize the article and present future research directions.

Background

Feature Models (FMs) aim at characterizing the valid combinations of features (a.k.a. configurations) of a system under study. A feature hierarchy (a tree) is used to facilitate the organization and understanding of a potentially large number of concepts (features).

Syntax of Feature Models

Different syntactic constructions are offered to attach variability information to features organized in the hierarchy (see Definition 1). As an example, the FM of Figure 3b describes a family of Wiki engines. The FM states that Wiki has three mandatory features, Storage, Hosting and License and one optional feature Programming Language. There are two alternatives for Hosting: Hosted Service and Local features form an Xor -group (i.e., at least and at most one feature must be selected). Similarly, the features Open Source and Proprietary License form an Xorgroup of License. Cross-tree constraints over features can be specified to restrict their valid combinations. Any kinds of constraints expressed in Boolean logic, including predefined forms of Boolean constraints (equals, requires, excludes), can be used. For instance, the feature PostgreSQL is logically related to Proprietary License and Domain. A similar abstract syntax is used in [START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF][START_REF] She | Reverse engineering feature models[END_REF] while other dialects slightly differ [START_REF] Schobbens | Generic semantics of feature diagrams[END_REF].

Definition 1 (Feature Model) A feature diagram is a 8-tuple G, E M , G M T X , G XOR , G OR , EQ, RE, EX : G = (F, E) is a rooted tree where F is a finite set of features, E ⊆ F × F is a set of directed child-parent edges ; E M ⊆ E
is a set of edges that define mandatory features with their parents ; G M T X , G XOR , G OR ⊆ 2 F are non-overlapping sets of edges participating in feature groups. EQ (resp. RE, EX) is a set of equals (resp. requires, excludes) constraints whose form is A ⇔ B (resp. A ⇒ B, A ⇒ ¬B) with A ∈ F and B ∈ F. The following well-formedness rule holds: a feature can have only one parent and can belong to only one feature group. A feature model is a pair F D, ψ where FD is a feature diagram, and ψ is a Boolean formula over F.

In this article, we employ the construction of Mutex-groups. (Techniques presented in [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] She | Reverse engineering feature models[END_REF]] also rely on this construction.) Three examples are given in Figure 1a, page 3. As an illustration, PHP and Java form a Mutexgroup: these features are mutually exclusive while it is not obliged to select one feature if the parent MySQL is selected. Therefore Mutex-groups differ from optional relations and Xor-groups (see next section).

Configuration and Ontological Semantics

The essence of an FM is its configuration semantics (see Definition 2). The syntactical constructs are used to restrict the combinations of features authorised by an FM. For example, at most one feature can be selected in a Mutex-group. As such Mutex-groups semantically differ from optional relations. Mutex-groups also semantically differ from Xor-group -none of the features can be selected if the parent of a Mutex-group is selected. Formally, the cardinality of a feature group is a pair (i, j) (with i ≤ j) and denotes that at least i and at most j of its k arguments are true. G M T X (resp. G XOR , G OR ) are sets of Mutex-groups (resp. Xor-groups, Or-groups) whose cardinality is (0, 1) (resp. [START_REF]SEI's Software Product Line Hall of Fame[END_REF][START_REF]SEI's Software Product Line Hall of Fame[END_REF], (1, m): m being the number of features in the Or-group). The ! "#$ (c) The corresponding formula of f mg Fig. 3: Another FM with same configuration semantics than f m u ( f m g = f m u ) and the product comparison matrix of Fig. 3a but with a more appropriate ontological semantics configuration semantics can be specified via translation to Boolean logic [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF].

P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 PostgreSQL ✓ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ MySQL ✕ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ License ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ Domain ✓ ✕ ✕ ✕ ✕ ✓ ✕ ✓ ✓ ✕ Proprietary License ✓ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ Local ✕ ✕ ✓ ✕ ✓ ✕ ✕ ✕ ✕ ✓ Programming Language ✕ ✓ ✕ ✕ ✓ ✓ ✓ ✓ ✕ ✓ Java ✕ ✓ ✕ ✕ ✕ ✓ ✕ ✕ ✕ ✓ Storage ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ PHP ✕ ✕ ✕ ✕ ✓ ✕ ✓ ✓ ✕ ✕ Open Source ✕ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ Wiki ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ Hosting ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ Hosted Service ✓ ✓ ✕ ✓ ✕ ✓ ✓ ✓ ✓ ✕ (
As an example, the formula φ g (see Figure 3c) defines the legal configurations of f m g . In particular, the configuration semantics states that a feature cannot be selected without its parent, i.e., all features, except the root, logically imply their parent. As a consequence, the feature hierarchy also contributes to the definition of the configuration semantics.

Definition 2 (Configuration Semantics) A configuration of a feature model g is defined as a set of selected features. g denotes the set of valid configurations of g.

Another crucial and dual aspect of an FM is its ontological semantics (see Definition 3). Intuitively the ontological semantics of an FM defines the way features are conceptually related.

Obviously, the feature hierarchy is part of the ontological definition. The parent-child relationships are typically used to decompose a concept into subconcepts or to specialize a concept. There are also other kinds of implicit semantics of the parent-child relationships, e.g., to denote that a feature is "implemented by" another feature [START_REF] Kang | Feature-oriented product line engineering[END_REF]. Looking at Fig. 3b, the concept of Wiki is composed of different properties like Hosting, License, or Programming Language ; License can be either specialized as an Open source or a Proprietary License, etc. Feature groups are part of the ontological semantics (see Definition 3) since there exists FMs with the same configuration semantics, the same hierarchy but having different groups [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] She | Reverse engineering feature models[END_REF].

Definition 3 (Ontological Semantics)

The hierarchy G = (F, E) and feature groups (G M T X , G XOR , G OR ) of a feature model define the semantics of features' relationships including their structural relationships and conceptual proximity.

We choose to use ontological semantics in line with the terminology employed in previous papers [START_REF] Czarnecki | Feature models are views on ontologies[END_REF][START_REF] She | Reverse engineering feature models[END_REF]. In knowledge engineering, an ontology represents the semantics of concepts and their relationships using some description language (e.g., based on description logic) [START_REF] Baader | The description logic handbook. chap. Basic Description Logics[END_REF][START_REF] Gruber | A translation approach to portable ontology specifications[END_REF]. Feature modeling shares the same goal and is also a concept description technique -less rich and powerful than ontology languages 1 . We concur with the argument that "feature models are views on ontologies" [START_REF] Czarnecki | Feature models are views on ontologies[END_REF], the hierarchy and feature groups being central to the conceptualization of a domain.

Ontologic-aware Synthesis

We now explain the impact of ontological semantics w.r.t. to the FM synthesis, a problem at the heart of many reverse engineering and FM management procedures (see Figure 2). 1 As feature modeling is a notational subset of ontologies, feature models can be translated into description logics [START_REF] Fan | Feature model based on description logics[END_REF] and ontology languages like OWL [START_REF] Wang | Verifying feature models using owl[END_REF]. The purpose of the translation is to reuse existing description logic solvers and automatically reason about feature models (e.g., for checking consistency) [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF]. It should be noted that we do not rely on these techniques (as our goal differs).

The Importance of Ontological Semantics

Let us consider the following re-engineering scenario (see [START_REF] Boucher | Towards more reliable configurators: A re-engineering perspective[END_REF] for more details). After having reverse engineered an FM, a practitioner aims to generate a graphical interface (like in Figure 1b) for assisting users in customizing the product that best fits his/her needs. Unfortunately, the ontological semantics of the FM is highly questionable (see Figure 1a) and poses two kinds of problems.

Automated exploitation. Transformation tools that operate over the FM will naturally exploit its ontological semantics. Figure 1 gives an example of a possible transformation from an FM to a user interface (UI). The generated UI (see Figure 1b) is as unintuitive as the ontological semantics of the FM is: features PHP and Java are below MySQL, instead of being below Programming Language ; Programming Language itself is badly located below Hosting ; Open Source is below Storage whereas the intended meanings was to state that a Wiki engine has different alternatives of a License. All in all, the series of questions and the organization of the elements in the UI are clearly non exploitable for a customer willing to choose a Wiki.

Human exploitation. One could argue that an automated transformation is not adequate and a developer is more likely to write or tune the transformation. In this case, the developer faces different problems.

First, there are evident readability issues when the developer has to understand and operate over the model. For example, PHP and Java are misplaced below MySQL in the FM of Figure 1a. A developer might understand that the MySQL database is implemented either in Java or PHP whereas the intended meaning was to state that the Wiki engine is developed in one of these two programming languages. This fictive example illustrates that an incorrect ontological semantics might induce a developer in error when exploiting an FM. Second, when writing the transformation, the ontological semantics cannot be exploited as such and the developer has to get around the issue, complicating her task. A solution could be to refactor the FM, but the operation is an instance of the synthesis problem (see below). Third, a developer can hardly rely on default transformation rules in case the ontological semantics of the FM is incorrect. Default rules typically organize siblings in a same UI block. In the example of Figure 1b (see page 3) the application of transformation rules leads to a discussable layout in the UI (Programming Language and PostgreSQL, Local and Proprietary License are grouped together). As a result, a developer has to override transformation rules, increasing the effort. Another option is to correct the ontological semantics (to enable the application of default transformation rules) and thus refactor the original FM. The refactoring of an FM is an instance of the synthesis problem, see below.

This scenario illustrates the importance of having FMs with an appropriate ontological semantics for a further exploitation in a forward engineering process. This need is also observed in other FM-based activities such as understanding a domain or a system [START_REF] Acher | Extraction and evolution of architectural variability models in plugin-based systems[END_REF][START_REF] Apel | Language-independent and automated software composition: The featurehouse experience[END_REF], communicating with other stakehold-ers [START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF], composing or slicing FMs [START_REF] Acher | Familiar: A domain-specific language for large scale management of feature models[END_REF][START_REF] Hubaux | Domain Engineering: Product Lines, Conceptual Models, and Languages, chap. Separating Concerns in Feature Models: Retrospective and Multi-View Support[END_REF][START_REF] Hubaux | Separation of concerns in feature diagram languages: A systematic survey[END_REF], relating FMs to other artefacts (e.g., models) [START_REF] Classen | Symbolic model checking of software product lines[END_REF][START_REF] Classen | Model checking lots of systems: efficient verification of temporal properties in software product lines[END_REF][START_REF] Czarnecki | Verifying feature-based model templates against wellformedness ocl constraints[END_REF][START_REF] Heidenreich | Relating feature models to other models of a software product line: A comparative study of featuremapper and vml*[END_REF], or simply generating other artefacts from FMs [START_REF] Czarnecki | Generative Programming: Methods, Tools, and Applications[END_REF].

Ontologic-aware FM Synthesis Problem

The development of an ontologic-aware FM synthesis procedure raises new challenges that have been overlooked so far.

FM synthesis problem. Given a set of features' names and boolean dependencies among features, the problem is to synthesize a maximal and sound FM conforming to the configuration semantics. Formally, let φ be a propositional formula in conjunctive or disjunctive normal form. A synthesis function takes as input φ and computes an FM such that F is equal to the boolean variables of φ and F M ≡ φ . There are cases in which the diagrammatic part of an FM is not sufficient to express φ (i.e., F D ⊂ φ ). It is thus required that the diagrammatic part is maximal (a comprehensive formalization is given in [START_REF] Andersen | Efficient synthesis of feature models[END_REF]). Intuitively, as much logical information as possible is represented in the diagram itself, without resorting to the constraints.

Ontologic-aware FM synthesis. The problem tackled in this article is a generalization of the FM synthesis problem. Numerous FMs, yet maximal, can actually represent the exact same set of configurations, out of which numerous present a naive hierarchical or grouping organization that mislead the ontological semantics of features and their relationships (e.g., see Figure 1a versus Figure 3b). We seek to develop an automated procedure that computes a well-formed FM both i) conformant to the configuration semantics (as expressed by the logical dependencies of a formula φ) and ii) exhibiting an appropriate ontological semantics.

The ontologic-aware synthesis problem not only arises when reverse engineering FMs. It is also apparent when refactoring an FM, i.e., producing an FM with the same configuration semantics but with a different ontological semantics. For example, the FM of Figure 1a could be refactored to enhance its quality and make it exploitable. The operation of slicing an FM has numerous practical applications (decomposition of a configuration process in multi-steps, reduction of the variability space to test an SPL, reconciliation of variability views, etc.) [START_REF] Acher | Familiar: A domain-specific language for large scale management of feature models[END_REF]. Despite some basic heuristics, we observed that the retained hierarchy and feature groups can be inappropriate [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF] (the same observation applies for the merge and diff operators). The ontological aspect of an FM impacts all these automated operations since they are instances of the FM synthesis problem (see Figure 2, page 5).

Automated Techniques for Feature Hierarchy Selection

In [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF], we empirically showed that once the feature hierarchy is defined, the variability information of the FM can be fully synthesized in the vast ma-jority of cases. That is, given the knowledge of the hierarchy, synthesis techniques [START_REF] Andersen | Efficient synthesis of feature models[END_REF] can produce feature groups (Mutex-, Xor-, Or-groups), mandatory and optional relationships, as well as equals, implies, excludes constraints. We thus focus on the challenge of selecting a hierarchy in the remainder of this section. For this purpose, three types of techniques can be considered: logical, ontological and hybrid (a combination thereof).

Before going into details, we first introduce a central structure -the socalled binary implication graph -all kinds of techniques exploit for selecting a sound hierarchy (see Section 4.1).

We present how logical heuristics can further exploit the input formula and we highlight their limits (see Section 4.2).

We then describe our ontologic-aware FM synthesis procedure which essentially relies on a series of heuristics to rank parent-child relationships (see Section 4.3.1) and compute clusters of conceptually similar features (see Section 4.3.2). The ranking lists and clusters can be interactively reviewed and exploited by a user, and if needs be, an optimum branching algorithm can extract a complete hierarchy (see Figure 6, page 17).

The ontological heuristics can be combined with logical heuristics, resulting in an hybrid solution (see Section 4.4).

Sound Selection of a Hierarchy

The feature hierarchy of an FM defines how features are ontologically related and also participate to the configuration semantics, since each feature logically implies its parent:

∀(f 1 , f 2 ) ∈ E, f 1 ⇒ f 2 .
As a result, the candidate hierarchies, whose parent-child relationships violate the original constraints expressed by φ, can be eliminated upfront.

Example. The feature Local cannot be a child feature of PostgreSQL since no configuration expressed in Figure 3a authorizes such an implication.

We rely on the Binary Implication Graph2 (BIG) of a formula (see Definition 4) to guide the selection of legal hierarchies. The BIG represents every implication between two variables (resp. features) of a formula (resp. FM), thus representing every possible parent-child relationships a legal hierarchy can have. As an illustration, Figure 4 depicts the BIG of the formula φ g of Figure 3c.

Selecting a hierarchy now consists in selecting a set of the BIG's edges forming a rooted tree that contains all its vertices. Such a tree represents a branching of the graph (the counterpart of a spanning tree for undirected graphs). The selection over the BIG is sound and complete since every branching of the BIG is a possible hierarchy of the FM and every hierarchy is a branching of the BIG.

Local

Programming Language Java PHP Fig. 4: Binary implicationg graph of the formula in Figure 3b Definition 4 (Binary Implication Graph (BIG)) A binary implication graph of a Boolean formula φ over F is a directed graph (V imp , E imp ) where

V imp = F and E imp = {(f i , f j ) | φ ∧ f i ⇒ f j }.
Now that we have a convenient data structure, which captures every possible hierarchy, the whole challenge consists in selecting the most meaningful one. The following sections present different types of techniques (logical, ontological and hybrid) for selecting the desired hierarchy.

Logical Heuristics

From logical constraints expressed by the input formula φ, we can compute three interesting logical structures (cliques, logical feature groups, reduced BIG). Heuristics can then operate over these structures for selecting a feature hierarchy.

Cliques

A first logical heuristic is to consider that features that always logically cooccur are likely to denote mandatory parent-child relationships. Co-occurring features are identified as cliques in the BIG and can be efficiently computed [START_REF] Andersen | Efficient synthesis of feature models[END_REF].

Example. The BIG of Figure 4 contains 3 cliques: {Wiki, Storage, License}, {PostreSQL, Proprietary License} and {MySQL, Open Source}. The first clique contain a feature (Wiki) which is indeed the parent of Storage and License (see Figure 3b).

Logical feature groups

All possible feature groups of φ can be automatically computed [START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF]. The computation of feature groups can be performed over the BIG or the reduced BIG that we present below.

Example. 30 Mutex groups, 21 Xor groups and 1 Or group can be extracted from the formula in Figure 3c. Among these 52 groups, 4 represent the Xor groups contained in the reference FM of Figure 3b. If we promote these groups as parent-child relations in the hierarchy, it would remain only 5 out of 13 features without parents. At first glance, these groups seem promising. However, selecting these 4 groups among the 52 that are computed is challenging.

Reduced BIG

Because of the transitivity of implication, a BIG is likely to have a large number of edges, out of which many candidates are not parent-child relationships. It is thus tempting to remove some edges of the BIG for reducing the complexity of the problem. A so-called reduced BIG is a subgraph of a BIG (see Definition 4) containing at least one tree that connects all the BIG's vertices, i.e., containing at least one valid hierarchy.

Different strategies can be developed to select the edges that can be removed from the BIG to get a reduced BIG. In our synthesis procedure, we adopted the following strategy. First, we contract each clique in one node, resulting in an acyclic graph. Then, we perform a transitive reduction. Finally, we expand the cliques.

The first step results in an acyclic graph in which the nodes are sets of features. Having an acyclic graph allows to compute a unique transitive reduction that is a subgraph of the BIG [START_REF] Aho | The transitive reduction of a directed graph[END_REF]. The transitive reduction maintains the reachability in the graph while removing edges.

Example. In Figure 4, Java is connected to MySQL with two path: Java → MySQL and Java → Programming Language → MySQL. The edge Java → MySQL can be removed as the implication is already represented by the path through Programming Language.

The last step is necessary to get back to a graph with features as nodes. This ensures the compatibility with our algorithm on the complete BIG.

Example. After the transitive reduction, the clique {PostreSQL, Proprietary License} is connected to Domain. To expand the clique, we create a node for A reduced BIG can be used as a support for a sound synthesis, i.e., all represented hierarchies of the reduced BIG are conforming to the configuration semantics. However, a reduced BIG loses the property of completeness as it arbitrarily removes some hierarchies. Overall, it may be an efficient heuristic for reducing the complexity of the synthesis problem.

Potential Limits of Logical Techniques

We now present three techniques of the state-of-the-art that exploit the previous logical structures (BIG, reduced BIG, cliques and feature groups) to select an appropriate hierarchy. Then, we highlight their potential3 limits regarding the ontologic-aware FM synthesis problem defined in Section 3.2.

A first basic approach, denoted FMRAND BIG , is to randomly select a branching of the BIG. As stated in Section 4.1, every branching of the BIG is a possible hierarchy of the FM and conversely. Therefore, FMRAND BIG randomly select one of the possible hierarchies for the FM. A second approach, denoted FMRAND RBIG , is to randomly select a branching over the reduced BIG instead of the complete BIG.

A third approach is proposed in [START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF]. Haslinger et al. proposed a technique (referred as FMFASE in the remainder of the article) that takes as input a set of products and fully generates an FM. The algorithm is iterative and essentially relies on logical structures exposed above: cliques are randomly unfolded, a reduced BIG is used to select parents, and feature groups (if any) are promoted.

FMFASE has three major drawbacks: (1) as reported in [START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF], the generated FM may not conform to the input configurations in the case of arbitrary constraints ; (2) the operations for computing logical structures assume the enumeration of the complete set of product. It leads to an exponential blowup ; (3) feature names and ontological semantics are not considered during the synthesis.

The two first drawbacks -the lack of soundness and the performance issues -prompted us to re-develop their algorithm based this time on state-of-the-art satisfiability techniques [START_REF] Andersen | Efficient synthesis of feature models[END_REF]. We consider that the algorithm, called FMFASE SAT hereafter, is representative of a pure logical-based technique for fully synthesizing an FM.

Unawareness of Ontological Meaning. All these logical techniques share the third major drawback: ontological semantics is not considered during the synthesis. FMRAND BIG and FMRAND RBIG are simply ignoring any information about the features which can results in inappropriate hierarchies such as the one in Figure 1a. FMFASE and FMFASE SAT base their hierarchy selection on logical information which may not reflect actual ontological relations between features. Example. The features Programming Language and PostgreSQL can form a mutex group according to the formula in Figure 3c. Promoting this group as part of the hierarchy is valid from a logical point of view but it does not correspond to the desired hierarchy presented in Figure 3b.

Without exploiting ontological knowledge, it is unlikely that the synthesized FM will correspond to an appropriate ontological semantics. This third drawback is a motivation for the development of ontological heuristics which do consider the relations between the features.

Ontological Heuristics

As a reminder, the objective is to select the most appropriate hierarchy from the BIG which is a compact representation of all possible hierarchies of an FM. A first natural strategy is to add a weight on every edge (f 1 , f 2 ) of the BIG, defining the probability of f 2 to be the parent of f 1 . The weights are computed by ontological heuristics that directly evaluate the probability of a relationship between a feature and a parent candidate. A ranking list of parent candidates for each feature can be extracted from the weighted BIG. From a user perspective, the ranking lists can be consulted and exploited to select or ignore a parent. In addition, we perform hierarchical clustering based on the similarity of the features to compute groups of features. The intuitive idea is that clusters can be exploited to identify siblings in the tree since members of the clusters are likely to share a common parent feature. For example, clusters can help tuning the previously computed weights, thus increasing the quality of the previous ranking lists. Moreover, users can operate over the clusters to define the parent of a group of features (instead of choosing a parent for every feature of a group).

Once we get the two pieces of information, we select the branching that has the maximum total weight. To compute an optimum branching, we use Tarjan's algorithm [START_REF] Camerini | A note on finding optimum branchings[END_REF][START_REF] Tarjan | Finding optimum branchings[END_REF] whose complexity is O(m log n) with n the number of vertices and m the number of edges. The hierarchy is then fed to syntesize a complete FM. The synthesis process is likely to be incremental and interactive ; users can validate and modify the ranking list and the set of clusters. The overall synthesis process is described in Figure 6.

Heuristics for Parent Candidates

The design of the ontological heuristics is guided by a simple observation: parent-child relations in a hierarchy often represent a specialization or a composition of a concept (feature).

Example. Java is a specialization of a Programming language while a Wiki is composed of a License, a Storage and a Programming Language.

As siblings are specializations or parts of the more general concept of their parent, they share the same context. Different kinds of relations (e.g., extension of the behavior of a parent feature) can be considered. The intuitive idea is that sharing the same context tends to make a feature semantically close to its parent and its siblings.

Example. Open source and Proprietary License are both referring to permissive rights about the use of a product.

From these observations, we developed several heuristics that exploit the feature names in order to compute the edges' weights of the BIG. We can divide the heuristics in two categories: syntactical heuristics and semantical heuristics. Example. In Figure 3b, License is closer to Proprietary License than Storage because the two first features contains the same substring: License.

We used Smith-Waterman [START_REF] Smith | Identification of common molecular subsequences[END_REF] algorithm that looks for similar regions between two strings to determine their distance. We also used the so-called Levenshtein edit distance [START_REF] Wagner | The string-to-string correction problem[END_REF] that computes the minimal edit operations (renaming, deleting or inserting a symbol) required to transform the first string into the second one.

Semantical heuristics. Syntactical heuristics have some limits: feature names that are not syntactically close but semantically close (in the sense of meaning) are not identified, for example, Java and PHP. Thus, we need to add some semantical knowledge to improve our technique. We explored two general ontologies out of which we built semantical metrics.

First, we explored WordNet [START_REF] Miller | Wordnet: a lexical database for english[END_REF]. This is a structured English dictionary that provides hyperonymy (specialization) and meronymy (composition) relations between word senses. As we are exclusively using the features' names, we could not use the most efficient metrics based on a text corpus [START_REF] Budanitsky | Evaluating wordnet-based measures of lexical semantic relatedness[END_REF]. Such metrics would require more than the few words contained in the features' names. Therefore, we selected two metrics named PathLength and Wu&Palmer that are only based on WordNet's structure. The PathLength metric gives the inverse of the length of the shortest path between two words in WordNet considering only hyperonymy relations. Wu and Palmer described a metric based on the depth of the words and their lowest common ancestor in the tree formed by hyperonymy relations [START_REF] Wu | Verbs semantics and lexical selection[END_REF].

These two metrics compute the similarity of two words, however features' name may contain several words. Wulf-Hadash et al. also used the Wu&Palmer metric in order to compute feature similarity [START_REF] Wulf-Hadash | Cross product line analysis[END_REF]. We used the same formula for combining word similarity into sentence similarity:

Sim(f 1, f 2) = m i=1 max j=1..n wsim i,j + n j=1 max i=1..m wsim i,j m + n
where m and n are respectively the number of words in f 1 and f 2 and wsim i,j is the similiarity between the i-th word of f 1 and the j-th word of f 2.

WordNet contains few technical words, thus we explored Wikipedia to increase the number of recognized words. The well known encyclopedia offers a large database containing text articles and links between them. Associating a set of articles to a feature enables the use of techniques that compute semantic similarity of texts.

Example. We can associate the features Java and Programming language of the FM in Figure 3b to their respective articles in Wikipedia.

To search articles on Wikipedia and compare them, we use the work of Milne et al. [START_REF] Medelyan | Mining meaning from wikipedia[END_REF][START_REF] Milne | An open-source toolkit for mining wikipedia[END_REF]. The authors provide a tool, called WikipediaMiner, that can extract a database from an offline dump of Wikipedia, search Wikipedia articles from the database and compare articles based on their hyperlinks 4 .

WikipediaMiner provides a model based on the hyperlink structure of Wikipedia that serves as a basis to compute the semantic similarity of two articles. In this model, an article is represented by a vector containing the occurrence of each link found in the article weighted by the probability of the link occurring in the entire Wikipedia database.

Our heuristics exploit WikipediaMiner API and databases to search articles with the closest title to a feature's name 5 . Then, it computes the semantic similarity of the features based on the similarity of the articles. The scores computed by WikipediaMiner are directly assigned to the relevant edges in the BIG. If no article is found, the heuristics simply assigns the minimal weight (i.e., 0) to the edges connected to the feature. It is important to note that the process is fully automated: users of such heuristic never have to manually search or compare Wikipedia articles.

Detecting Siblings with Hierarchical Clustering

Defining weights on the BIG's edges and computing the optimum branching can be summarized as choosing the best parent for a feature. However, it is sometimes easier to detect that a group of features are siblings. To detect such siblings we reuse the heuristics of the previous section (Smith-Waterman, Levenshtein, PathLength, Wu&Palmer, Wikipedia and Wiktionary).

We first compute the similarity between features without considering the BIG structure. Then, we perform agglomerative hierarchical clustering on these values. Agglomerative hierarchical clustering consists in putting each feature in a different cluster and merge the closest clusters according to their similarity. The merge operation is repeated until the distance between two clusters falls below a user specified threshold.

Finally, we use the BIG to determine if the clusters belongs to one of the two categories below. In the following, C represents a cluster and possibleP arents gives the parent candidates according to the BIG.

-∃f p ∈ F, ∀f c ∈ C, f p ∈ possibleP arents(f c), i.e., all the features can be siblings. It remains to find a common parent of the cluster among the other features.

-∃P ⊂ C, ∀f p ∈ P, ∀f c ∈ C, f p = f c , f p ∈ possibleP arents(f c), i.e., some
features are parent of the others. It remains to find the parent among the features within the cluster.

In the two cases, the best parent is chosen according to heuristics for parent candidates.

Example. In Figure 3b, we determine with the Wikipedia heuristic that Java and PHP are semantically close, thus being in a same cluster. It corresponds to the first category exposed above. The key benefit is that we can now solely focus on their common parents -we can automatically compute them using the BIG. The best parent among the common parents corresponds here to Programming Language.

Clusters and Optimum Branching. Once we have defined the parents of the clusters, we modify the edges' weights of the BIG to consider this new information during the optimum branching algorithm. This modification consists in setting the maximal weight to each edge between a child and its chosen parent. The rationale is that features of the clusters are likely to share the same parent, thus the idea of augmenting the weights.

Example. We assign the maximum weight (i.e., 1) for the following BIG's edges: Java → Programming Language and PHP → Programming Language.

Logic + Ontologic = Hybrid

Ontological heuristics allows to synthesize a FM that have both a correct configuration semantics and an appropriate ontological semantics. However, the complexity of the BIG may disturb this type of heuristics and limit their benefits. Instead of operating over the BIG, other logical structures obtained from φ can be considered when applying ontological heuristics (see left part of Figure 6). This mix of ontological and logical heuristics is what we call a hybrid heuristic. It exploits logical information to reduce the complexity of the problem and then select an appropriate hierarchy based on ontological information.

We propose a hybrid approach called FMONTO LOGIC in the remainder. The ontological heuristics we develop in Section 5.1 operate this time over the reduced BIG (instead of the BIG itself). As explained in Section 4.2, this structure significantly reduces the number of parent candidates and clusters; the drawback is that some hierarchies are no longer represented.

Example. In the complete BIG (see Figure 4), the feature Java has 7 parent candidates. In the reduced BIG (see Figure 5), the same feature Java is this time directly in relation with the correct parent Programming Language. On the other hand, the loss of completeness can prevent the selection of some desired hierarchies, e.g., PostgreSQL is not anymore in relation with its parent Storage after the reduction of the BIG (see Figure 5).

Tool Support

We implement and integrate all previous automated techniques into WebFML, a Web-based environment for managing FMs [START_REF] Bécan | WebFML: Synthesizing Feature Models Everywhere[END_REF]. A unique feature of WebFML is its interactive support for choosing a sound and meaningful hierarchy. Ranking lists, clusters, cliques, and other facilities (graphical preview, undo/redo, etc.) are all integrated into WebFML to guide users in the choice of a relevant hierarchy among the numerous possibilities.

WebFML is built on top of FAMILIAR [START_REF]FAMILIAR: FeAture Model scrIpt Language for manIpulation and Automatic Reasonning[END_REF] and provides FM management operations all based on the synthesis procedure. Likewise practitioners can envision the use of WebFML in practical scenarios: the merging of multiple product lines [START_REF] Acher | Composing your compositions of variability models[END_REF]; the slicing of a configuration process into different steps or tasks [START_REF] Hubaux | Domain Engineering: Product Lines, Conceptual Models, and Languages, chap. Separating Concerns in Feature Models: Retrospective and Multi-View Support[END_REF]; the sound refactoring of FMs [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF], especially when fully automated techniques produce incorrect FMs; the reverse engineering of configurable systems through the combined use of composition, decomposition and refactoring operators [START_REF] Abbasi | Reverse engineering web configurators[END_REF][START_REF] Acher | Reverse engineering architectural feature models[END_REF].

WebFML also aims to ease the mechanical translation of artefacts with variability into FMs. It enables practitioners (e.g., product line managers, software developers) to reduce their effort and avoid accidental complexity when (re)-engineering or maintaining their variability models. In a nutshell, WebFML is a comprehensive environment for synthesizing FMs from various kinds of artefacts:

-product comparison matrices: specific form of spreadsheets documenting the features of products under comparison. By giving a specific interpretation of their semantics, these matrices can be interpreted as FMs [START_REF] Sannier | From Comparison Matrix to Variability Model: The Wikipedia Case Study[END_REF]; -dependency graph which can be extracted from configuration files of build systems (e.g. pom.xml files in Maven) [START_REF] Abbasi | Reverse engineering web configurators[END_REF][START_REF] Acher | Reverse engineering architectural feature models[END_REF]; -compilation directives and source code in which features and their dependencies can be mined in order to synthesize an FM [START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] She | Reverse engineering feature models[END_REF]. -propositional formula in conjunctive or disjunctive normal form [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] She | Feature Model Synthesis[END_REF]; -a (set of ) FMs: slicing, merging or refactoring existing FMs are instances of the synthesis problem we are addressing with WebFML [START_REF] Acher | Composing your compositions of variability models[END_REF][START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] Hubaux | Domain Engineering: Product Lines, Conceptual Models, and Languages, chap. Separating Concerns in Feature Models: Retrospective and Multi-View Support[END_REF].

Implementation of Ontological Heuristics

As part of WebFML we implemented six ontological heuristics (see Section 4) based on specialized libraries:

-The syntactical heuristics, Smith-Waterman (SW) and Levenshtein (L), come from the Simmetrics library6 ; -PathLength (PL) and Wu&Palmer (WP) rely on extJWNL 7 which handles the communication between WordNet and our tool. -Wikipedia Miner [START_REF] Milne | An open-source toolkit for mining wikipedia[END_REF] offers an API to browse Wikipedia's articles offline and compute their relatedness [START_REF] Milne | Computing semantic relatedness using wikipedia link structure[END_REF]. We used this tool on the english version of Wikipedia (Wiki) and Wiktionary (Wikt) which form the last two heuristics.

Features of the environment

WebFML offers an interactive mode where the user can import a formula (e.g., in DIMACS format), synthesizes a complete FM and export the result in different formats. During the FM synthesis, the graphical user interface displays a ranking list of parent candidates for every feature, a list of clusters, a list of cliques and a graphical preview of the FM under construction (see Figure 7, E , F , G and H ).

During the interactive process, users can:

-select or ignore a parent candidate in the ranking lists (see Figure 7, F ); -select a parent for a cluster within the cluster's features or any potential parent feature outside the cluster (see Figure 7, G ). The user can also consider a subset of a cluster when selecting the parent; -select a parent for a clique with the same interaction as clusters (see Fig-

ure 7,H ). -undo a previous choice (see Figure 7,C ); -define the different heuristics and parameters of the synthesis (see Figure 7, B ); -automatically generate a complete FM according to previous choices and selected heuristics (see Figure 7, C ); -use FAMILIAR capabilities within an integrated console (see Figure 7, I ); -manage FAMILIAR script files and previously computed variables (see Figure 7, A and D ).

A typical usage is to perform some choices, generate a complete FM with the heuristics and reiterate until having a satisfactory model. At any moment, the optimum branching algorithm can synthesize a complete FM.

Interactive edits of parent candidates and clusters

The ranking lists of parent candidates and the clusters form the main information during the synthesis. As the amount of information can be overwhelming, we propose a tree explorer view for manipulating and visualizing both parent candidates and clusters (see Figure 7, F , G and H ). A tree explorer view is scalable: it allows to focus on specific features or clusters while the other information in the explorer can be hidden. During the synthesis, the user interacts almost exclusively by clicking on the elements of these explorers. Clicking on a feature in parent candidate lists allows to select or ignore a parent candidate. Users can also click on a cluster to choose a parent among the common parent candidates of the sibling features (see Figure 7,G ). If the cluster contains the desired parent, the user can click on the feature and select the children within the cluster. In both cases, the user can deselect some features to consider only a subset of the cluster. The same behaviour applies to cliques. We also propose a graphical preview of the FM based on Dagre8 and D39 javascript libraries. It allows to summarize the previous choices and have a global view of the current result (see Figure 7,E ).

Evaluation

So far, we have presented a sound procedure and various automated techniques, integrated into the WebFML environment, for synthesizing FMs. In this section we empirically investigate which heuristics presented in Section 4 are the best for breathing ontological knowledge. We conduct a series of experiments on 156 realistic FMs (see Section 6.1 for more details). Given an encoding of a FM f m t as a formula, we evaluate the ability of the different synthesis techniques at selecting a feature hierarchy as close as possible to the original hierarchy of f m t . Specifically we aim at answering the following research questions: Fig. 7: Interface of the environment during synthesis -RQ1: How effective are the techniques to fully synthesize an FM? Is a fully automated synthesis feasible? The effectiveness corresponds to the percentage of parent-child relations that are correctly synthesized with respect to the ground truth. When the whole synthesis process is performed in a single step, without any user intervention, the resulting FM may be far from the ground truth. This question aims at quantifying this potential effect. -RQ2: How effective are techniques to compute ranking lists and clusters?

For ranking lists, the effectiveness corresponds to the percentage of parents from the ground truth that are in the top 2 positions of the lists. For clusters, it corresponds to the percentage of correct clusters (i.e. clusters that exist in the ground truth) and the percentage of features that correct clusters represent in the ground truth FM. Selecting the most likely parents and siblings of a given feature can significantly reduce the number of choices a user has to perform during the interactive selection of a feature hierarchy.

Is the reduction of the BIG a good heuristic? Are logical structures like cliques and feature groups good clusters? Do ontological heuristics help?

For each of the research question, we compare logical, ontological and hybrid-based techniques exposed in Section 4. We explore the possible role of the reduced BIG, cliques and logical feature groups for improving the synthesis -"as such" or as a complement to ontological techniques.

Experimental Settings

FM synthesis techniques under evaluation

Table 1 summarizes the available techniques and when they can be applied (e.g., FMFASE does not compute ranking lists or clusters and thus cannot address RQ2). FMONTO denotes the synthesis technique that relies on one of the six ontological heuristics over the BIG for computing the full FM, the ranking lists and clusters. As a reminder, the abbreviations used in the evaluation for the different ontological heuristics of FMONTO and FMONTO LOGIC are mentioned in Section 5.1.

For FMFASE, we use the binary provided by the authors [11]. To reduce fluctuations caused by random generation [START_REF] Arcuri | A practical guide for using statistical tests to assess randomized algorithms in software engineering[END_REF], we run 1000 iterations for FMRAND BIG and FMRAND RBIG each time these heuristics are involved. The results are reported as the mean value over 1000 iterations.

Data

Our experiments operate over two data sets. We translate the configuration semantics of each FM of the data sets into a Boolean formula φ. The formula serves as input for our empirical evaluation procedure. The original hierarchy and feature groups of the FMs constitute the ground truth to evaluate the ontological quality of the different algorithms and heuristics. The SPLOT [START_REF]SPLOT: Software Product Line Online Tools[END_REF] public repository offers a large set of FMs from different domains created by academics or practitioners. From this repository, we manually selected FMs that are written in English and contain meaningful feature names 10 . This resulted in 201 FMs with a total of 5023 features. Due to memory consumption issues [START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF] and technical issues, 75 FMs from the SPLOT data set could not be handled by FMFASE. Therefore, we performed the experiment on the remaining 126 FMs that represent 2214 features.

Overall, the dataset is similar to the one used in [START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF] which was also extracted from SPLOT, authorizing a fair comparison with FMFASE.

PCM dataset. Product Comparison Matrices (PCMs) compare features of domain specific products and now abound on the internet and in particular in Wikipedia [START_REF] Bécan | Automating the formalization of product comparison matrices[END_REF][START_REF] Sannier | From Comparison Matrix to Variability Model: The Wikipedia Case Study[END_REF]. We gathered 30 FMs with an automated extraction process -in the same vein as the one described in [START_REF] Acher | On extracting feature models from product descriptions[END_REF]. Each configuration of the extracted FM corresponds to at least one product of the PCM. The structure of the matrix and the Wikipedia pages (sections, headers, etc.) is exploited to produce hierarchies. Cell values (plain text values, "yes" value, "no" value, etc.) are interpreted in terms of variability.

We exploit the structure of the matrices as follows. In a PCM, there are values in each column and headers for characterizing a column. For example, the values MacOS X, Windows 7, or Ubuntu are values of a column whose header name is Operating System. We use the following strategy for deriving a hierarchy: values and headers are features; values are located below the header. In the example, MacOS X, Windows 7, or Ubuntu would be features of Operating System in a feature hierarchy. The overall structure of a Wikipedia page was created by domain experts (Wikipedia contributors) for organizing features of a set of product. The dataset is challenging for the synthesis procedures since the number of cross-tree constraints and the number of features are rather important, feature names are disparate, and the depth of the hierarchies is 4 in average.

Table 2 presents some statistics about the FMs. As an indication of the complexity of the synthesis process, we compute the number of parent candidates for each feature from the BIG of an FM. We have an average of 6.3 (from 0 to 36) parent candidates in SPLOT FMs and 8.3 (from 1 to 86) for PCM FMs. We also compute the average number of character contained in 10 Essentially we remove FMs with nonsense feature names like F1 or FT22 or written in Spanish. We did not discard FMs containing feature names not recognized by our ontologies. feature names of the input formula. The average is 11 characters per name for SPLOT FMs and 18 for PCM FMs. With so little information for the ontological heuristics used in FMONTO and FMONTO LOGIC , the datasets are challenging and longer feature descriptions may improve the following results.

Dataset

Method for Comparing the Evaluated Techniques

To answer our research questions, we compare the presented techniques according to a set of metrics that will be defined throughout the evaluation.

To perform this comparison, we compute the average and the median of the metrics over the datasets. We also run statistical tests to assess the significance of a difference between two techniques. When comparing two techniques, we measure the same metric on the same FMs, thus having paired samples. In this case, the most suitable tests are paired tests. A classic paired test is the t-test. However, this particular test requires that the data follows a normal distribution. To verify this assumption, we used the Shapiro-Wilk test. Most of these tests rejected (according to a threshold of 0.05 for the p-value) the hypothesis that the data is normal. Therefore, our experiments rely on the Wilcoxon rank-sum test, which does not assume a normal distribution of data. In our evaluation, the null hypothesis states that the two compared techniques have the same mean.

The alternate hypothesis states that the means are different. Therefore, if we reject the null hypothesis, the difference between two techniques is significant but the direction of this difference is still unknown.

To complete the results of our tests, we also compute the effect size (i.e. how different are the results). In our case, we measure the effect size as the difference of the means of the two compared techniques. Using this definition allows an easy interpretation of the effect size in terms of the metric used. It also allows to know the direction of the difference between two heuristics.

In the following sections, the results of the statistical tests are reported according to a threshold of 0.05 for the p-value. For further details, all the p-values and effect sizes are reported in Appendix A.

RQ1: Fully Automated Synthesis

Our goal is to evaluate the effectiveness of a fully automated synthesis technique. The resulting synthesized FM should exhibit a feature hierarchy as close as possible to the original hierarchy of the ground truth. We consider that the more the number of common edges between the two hierarchies is, the more effective the technique is (see Definition 5).

Definition 5 (Effectiveness for a fully automated synthesis)

The effectiveness of an FM synthesis algorithm in a fully automated process is computed as follows: effectiveness = commonEdges(synthesized FM, ground truth) |F | -1 commonEdges(synthesized FM, ground truth) represents the number of edges that are common between the hierarchy synthesized by the algorithm and the hierarchy from the ground truth. It corresponds to the number of correct parentchild relations according to the ground truth. |F | is the number of features in the ground truth FM. As an FM hierarchy is a tree, |F | -1 is the total number of parent-child relations.

For each input formula/set of configurations of the two data sets, we challenge all the techniques of Table 1 to fully synthesize an FM. In this experiment, we only use the ranking lists computed by the different techniques and we do not consider ontological or logical clusters.

Table 3 reports the percentage of common edges with the ground truth. We split the table in two, clearly separating (1) techniques that operate over the BIG (see Table 3a) from ( 2) techniques that apply a logical heuristic and operate over the reduced BIG (see Table 3b). There are two hypotheses behind this separation.

(H1) Ontological techniques are superior to random or logical heuristics when operating over the same logical structure.

H1 Results. In Table 3a all ontological heuristics (FMONTO) outperform FMRAND BIG . For SPLOT, the best heuristic PathLength improves by 9.5% (average) and 10.6% (median) the effectiveness of FMRAND BIG . Similar observations are made for the PCM dataset: the best heuristic Wikipedia improves by 10.4% (average) and 13.1% (median) the effectiveness of FMRAND BIG .

Table 3b shows that almost all ontological heuristics (FMONTO) outperform FMFASE, FMFASE SAT or FMRAND RBIG being on SPLOT or PCM dataset. Only the Levenshtein heuristic is outperformed by FMFASE on SPLOT dataset and by FMRAND RBIG on PCM dataset. However the improvement gained by ontological heuristics is less significant than in Table 3a. A possible reason is the use of the reduced BIG (see H2 below).

Statistical tests confirm that FMONTO significantly outperforms FMRAND BIG , except for the Wu&Palmer heuristic on the PCM dataset and the Levenshtein heuristic on both datasets. For the results of FMONTO LOGIC , 6 out of 30 statistical tests shows that it outperforms pure logical techniques (FMRAND RBIG , FMFASE and FMFASE SAT ). The other tests cannot conclude that there is a significant difference with the results of the pure logical techniques.

Overall, we conclude that the hypothesis H1 is verified for the ontological techniques of FMONTO. We also note an improvement of hybrid techniques of FMONTO LOGIC compared to pure logical techniques (FMRAND RBIG , FMFASE and FMFASE SAT ). However, the tests cannot confirm that this difference is significant. This may be explained by the use of the reduced BIG. The next hypothesis address this question.

(H2) The reduced BIG can improve the effectiveness. The reduction of the BIG significantly decreases the number of edges, thus favouring a random selection. For the SPLOT dataset, 56.1% (in average, 59.1% for the median) of the parent-child relations from the ground truth are kept after reduction of the BIG while more than half of the edges are removed. For PCM dataset, 83.8% (in average, 88.1% for the median) of the parent-child relations from the ground truth are kept after reduction of the BIG while almost half of the edges are removed. In practice the tradeoff between a reduction of the problem space and a less accurate representation clearly favours both FMONTO LOGIC and FMRAND RBIG .

H2 Results. Results in

If we compare the score of FMONTO in Table 3a with the scores of FMRAND RBIG , FMFASE and FMFASE SAT in Table 3b, we note that the purely logical techniques on the reduced BIG outperform ontological techniques on the complete BIG. This is another important observation in favour of H2. Without the use of the reduced BIG, ontological heuristics are beat by randomized or logical-based heuristics, highlighting the prior importance of the logical structure. Finally, all the statistical tests confirm that H2 is verified.

Key findings for RQ1.

-A fully automated synthesis produces FMs far from the ground truth.

At best, the percentage of correct parent-child relationships in the synthesized FM is 37.8% (for SPLOT) and 44.4% (for PCM); In practice the hybrid approach could provide a "by-default" visualisation of the FM but numerous faulty parent-child relationships (more than a half) need to be reviewed and corrected. Therefore it remains crucial to guide the users when refactoring the faulty FM or interactively selecting a feature hierarchy during the synthesis process. -The experiment demonstrates that a hybrid approach provides the best support for fully synthesizing an FM. A key aspect is that the reduced BIG significantly improves the effectiveness of all techniques.

RQ2: Quality of ranking lists and clusters

Our goal is to evaluate the quality of the ranking lists and the clusters. We also evaluate the use of cliques and feature groups during the synthesis for selecting the hierarchy of an FM. In this experiment we do not consider FMFASE and FMFASE SAT techniques as they do not provide such information.

Ranking lists

We consider that the ranking lists should place the original parent of the ground truth as close as possible to the top of the list. Specifically, we look at the Top 2 positions of the lists and evaluate the effectiveness of a technique at computing ranking lists as defined in Definition 6. With an average of 6.3 parent candidates per feature in the SPLOT dataset, we chose to restrict our evaluation to the top 2 positions in order to reduce the impact of random choices. Indeed, it already allows a probability of almost 32% (in average) of having a correct parent for randomized approaches.

Definition 6 (Effectiveness for computing ranking lists) The effectiveness of an FM synthesis algorithm for computing ranking lists is computed as follows:

effectiveness = # parents in top 2 positions |F | -1
To compute the # parents in top 2 positions, we check that the parent of each feature (as it appears in the ground thuth) appears in the top 2 positions of the ranking list. |F | -1 represents the number of features that have a parent in the ground truth ( i.e. all the features except the root).

Table 4 reports the percentage of correct parents in the Top 2 positions of the ranking lists. As in the previous experiment, we separate the techniques that operate over the BIG from the techniques that operate over the reduced BIG and pose the same two hypotheses as in RQ1.

(H3) Ontological techniques are superior to random heuristics when operating over the same logical structure.

H3 Results. In Table 4a, FMONTO outperforms FMRAND BIG . For SPLOT FMs, the best heuristic PathLength improves by 10.2% (average) and 11.7% (median) the effectiveness of FMRAND BIG . For the other dataset, the Wikipedia heuristic improves by 9.4% (average) and 10.6% (median) the effectivness of FMRAND BIG . The statistical tests confirm these results for the SPLOT dataset and for the Wikipedia heuristic on the PCM dataset. For the other heuristics, the tests cannot confirm that there is a significant difference between FMONTO and FMRAND BIG .

Table 4b also shows that FMONTO LOGIC outperforms FMRAND RBIG on both data sets but the scores are significantly closer. The tests reflect this observation as they cannot confirm that a difference exists between FMONTO LOGIC and FMRAND RBIG , except for the PathLength heuristic on the SPLOT dataset.

Overall, we cannot conclude that the hypothesis H3 is verified in all cases but the average and median scores indicate at least a slight improvement of the effectiveness of FMONTO (resp. FMONTO LOGIC ) compared to FMRAND BIG (resp. FMRAND RBIG ).

(H4) The reduced BIG improves the quality of ranking lists.

H4 Results. The SPLOT dataset (resp. PCM dataset) results in a 5.7% (average) and 6.3% (median) (resp. 16.5% and 15%) improvement of the effectiveness of our best heuristic PathLength. FMRAND RBIG also clearly benefits from the reduction of the BIG as it improves the effectiveness of FMRAND BIG by 8.6% for SPLOT and 19.9% for PCM.

The statistical test confirms the results on the PCM dataset. However, on the SPLOT dataset, the difference is not significant for most of the heuristics. This may be explained by the 43.9% of correct parents brutally removed by the reduction in the SPLOT dataset. For the PCM dataset, the reduction of the BIG removes only 16.2% of correct parents.

As a result, the hypothesis H4 is verified for the PCM dataset but the results for SPLOT shows that the reduced BIG may have a limited effect.

Clusters

We consider that the computed clusters should contain either sibling features from the ground truth or siblings with their corresponding parent -in line with the two cases identified in Section 4.3.2, page 19. For example in Figure 3b, page 7, {Hosted Service, Local} is a correct cluster because the two features are siblings. {Hosted Service, Local, Hosting} is also a correct cluster because Hosting is the parent of Hosted Service and Local. The effectiveness of a technique corresponds to the number of correct clusters and the percentage of features that these clusters represent (see Definition 7 for further details). # clusters represents the number of clusters that are generated by the algorithm. # correct clusters is the number of clusters that contain either sibling features from the ground truth or siblings with their corresponding parent. # features in correct clusters is the sum of the correct clusters' sizes. Finally, |F | represents the number of features in the ground truth.

Table 5 reports for each dataset, the number of clusters, the clusters' sizes, the percentage of correct clusters computed by the techniques, and the number of features in a correct cluster (in average and for the median). For each heuristic, we optimized11 the thresholds for the clustering in order to produce the largest number of features in a correct cluster. Intuitively, clusters allow the user to choose only one parent for a set of features. Maximizing the number of features in correct clusters potentially reduces the user effort. As previously, we separate our evaluation in two hypotheses.

(H5) Ontological techniques are superior to random heuristics when computing clusters over the same logical structure.

H5 Results. Table 5a shows that FMONTO generates less clusters per FM than FMRAND BIG . However, FMONTO produces clusters that are slightly bigger and more accurate. For SPLOT, our best heuristic PathLength generates 67.6% (average) and 75% (median) of correct clusters while FMRAND BIG reaches 27.7% (average) and 25% (median). The percentage of features in correct clusters is also significantly better than FMRAND BIG . For the PCM dataset, the difference is greater with 79.2% (average) and 77.7% (median) of correct clusters for PathLength comparted to only 14.9% (average) and 12.8% (median) for FMRAND BIG . Table 5b also shows that FMONTO LOGIC outperforms FMRAND RBIG for all the results. We observe that PathLength is the best heuristic according to the percentage correct clusters whereas Levenshtein is the best one according to the percentage of features in a correct cluster. We also note that the Levenshtein heuristic produces more and bigger clusters than PathLength. These differences show that there is a tradeoff between the number of features contained in clusters and their accuracy. It corresponds to the classical tradeoff between precision and recall that will be further illustrated with the use of the reduced BIG in H6.

Statistical tests that FMONTO (resp. FMONTO LOGIC ) outperforms FMRAND BIG (reps. FMRAND RBIG ) on both datasets, except for Wu&Palmer and PathLength heuristics. It confirms the usefulness of ontological-based heuristics, whether they operate over a reduced BIG or a BIG and validates the hypothesis H5.

(H6) The reduced BIG improves the quality of the clusters.

H6 Results. Table 5b shows that the reduced BIG allows to produce less clusters per FM compared to the techniques operating over the complete BIG. The clusters are also slightly smaller. For SPLOT, 74.8% (average) and 100% (median) of clusters are correct with our best heuristic Wiktionary. For PCM, the PathLength heuristic produces 89.2% (average) and 89.6% (median) of correct clusters. Therefore, and for every ontological-based heuristics, the accuracy of the generated clusters increases when we reduce the BIG. The statistical tests confirm these results except for Wu&Palmer and PathLength heuristics on the SPLOT dataset despite their improvements.

However, the percentage of features in a correct cluster is slightly inferior compared to the results with a complete BIG. On a complete BIG (see Table 5a), our best heuristic Levenshtein produces 31% (average) and 30% (median) of correct clusters for SPLOT (resp. 41.4% and 41.2% for PCM). On a reduced BIG, Levenshtein produces 29.2% (average) and 29% (median) for SPLOT (reps. 41% and 41.2% for PCM). All the statistical tests are consistent with these observations as they cannot state that the difference is significant.

The results show that there is no clear superiority of an approach. The use of the reduced BIG or the use of the complete BIG when computing clusters have both pros and cons. On the one hand, the reduced BIG supports the identification of more accurate but less clusters with less features. On the other hand, the complete BIG provides more false positives but a user can consult and manipulate larger clusters. From a practical and tooling point of view, there is a classical tradeoff to find between precision and recall.

Using Cliques in FM Hierarchy Selection

Features that co-occur in configurations (i.e., cliques) can be efficiently computed using standard logical techniques [START_REF] Andersen | Efficient synthesis of feature models[END_REF]. We want to further understand how an FM synthesis algorithm can benefit from the use of cliques as a logical heuristic. A first step is to identify the type of relations contained in cliques. For the SPLOT dataset (resp. the PCM dataset), we report that 93.8% (average) and 100% (median) of the cliques (resp. 98.9% and 100%) contain features that are connected to others by parent-child relationships. The remaining cliques are not subtrees of the hierarchy and contain at least one bi-implication cross-tree constraint. Therefore, cliques almost always represent parent-child relations between features.

From this observation, we consider cliques as a special kind of cluster. For example, FMFASE uses cliques as a cluster. It chooses one feature of a clique and places it as the parent of the others. This pattern is what we call a simple unfolding: users just have to select one feature in the clique that will play the role of parent feature of the others. For instance, the clique {Wiki, Storage, License, Hosting} is transformed through a simple unfolding in Figure 8a: Wiki is the parent of Storage, License and Hosting.

However, more complex unfolding may arise. Let us take a fictive example and consider that the feature Storage is below Hosting (and not Wiki as in the running example). In that case, the clique requires a complex unfolding that consists in defining several levels of features in the hierarchy (see Figure 8b for an example).

We evaluate the use of cliques as clusters with the same metrics used in Section 6.3.2. Table 6a presents the results. We observe that simple unfolding (i.e. a correct cluster) is required in 50% (average) and 50% (median) of the cliques of SPLOT FMs. For PCM FMs, this pattern represents 31.1% (average) and 0% (median) of the cliques. In at least half of the cases, cliques require more user effort than a traditional cluster in which only one parent should be selected (i.e. it requires a complex unfolding). Therefore, a simple unfolding can be used as a default heuristic for selecting parent-child relations in a clique but not as a reliable heuristic in a fully automated synthesis.

Using Logical Feature Groups in FM Hierarchy Selection

In addition to cliques, logical feature groups can be exploited during the selection of the FM hierarchy. All possible logical feature groups of a formula can be computed either using the reduced BIG [START_REF] Andersen | Efficient synthesis of feature models[END_REF] or the BIG. A logical feature group consists in a set of sibling features and a parent feature. It is in line with the definition of cluster given in Section 4.3.2. We study here how the so-called logical feature groups are interesting structures for representing clusters.

Computing feature groups from a formula may lead to numerous groups containing the same set of sibling features but with different parents. This is due to feature groups in which the parent is logically bi-implied by another feature (i.e., the parent feature belongs to a clique). An example is given in Figure 9. To avoid this combinatorial explosion, we omit the parents and consider only the sibling features. We introduce a place-holder that can be one of the parent of the siblings (see right of Figure 9). This factoring strategy has For the experiment, we verified whether logical feature groups are correct clusters -in line with the definition of Section 6.3.2, page 30.

Table 6a shows the results. For SPLOT FMs, 69.3% (average) and 75% (median) of logical feature groups are correct clusters. These results are slightly superior to the 67.6% (average) and 75% (median) of correct clusters generated by our best heuristic PathLength (see Table 5a).

For PCM FMs, 92.2% (average) and 100% (median) of feature groups are correct clusters. It outperforms the 79.2% (average) and 77.7% (median) of correct clusters from our best heuristic PathLength. However, we note that 473 Xor-groups were generated from a unique FM and 36 only were correct clusters. This extreme example shows that, in some cases, logical feature groups may challenge an automated technique or overwhelm a user with numerous incorrect clusters.

(H7) The reduced BIG can improve the quality of logical feature groups.

H7 Results. Table 6b shows the same metrics than Table 6a but for feature groups computed from the reduced BIG of the FM. We note that reducing the BIG significantly reduces the number of computed feature groups. Also, their accuracy increases compared to the groups in Table 6a but the correct groups often involve less features. Statistical tests show that the percentage of correct clusters is significantly better when using a reduced BIG. However, the difference in the percentage of features in a correct cluster is not stated as significant. Moreover, the test for the Mutex groups on the SPLOT dataset shows a significant decrease of the metric. Therefore, the test cannot verify H7 but they illustrate the tradeoff between precision and recall when computing clusters which is consistent with the results of H6. Key findings for RQ2.

-The experiment demonstrates that an approach based on ontological heuristics provides the best support for producing ranking lists. At best, the user has to review only 2 parent candidates for 58.9% of the features (for SPLOT) and 56.3% (for PCM); -An approach based on the reduced BIG does not necessarily improve the quality of the ranking lists or clusters; -Ontological heuristics are beneficial to ranking lists. Ontological heuristics also generate less clusters than FMRAND BIG but they are far more accurate; -Among the ontological heuristics, there is no clear winner -even if all are beneficial for breathing ontological knowledge; -In 93.8% (resp. 98.9%) of the cases, all features of the cliques are connected by parent-child relationships to at least one feature. Nevertheless cliques require complex unfolding in more than 50% of the cases; -Logical feature groups form accurate clusters especially when they are computed over the reduced BIG. The place-holder for factoring out similar feature groups makes the difference. Yet there are extreme cases in which lots of logical feature groups do not correspond to clusters.

Summary and Discussion

Eventually a combined use of techniques, that is, a hybrid approach empirically emerges:

-Ontological heuristics with reduced BIG are the best suited for a one-step full synthesis of FM (see RQ1); -Ontological heuristics over the reduced BIG are the best suited for computing ranking lists (see RQ2); -Logical feature groups with place-holders and computed over the reduced BIG are the most accurate clusters (see RQ2); -Cliques and clusters obtained with ontological heuristics can complete the information presented to users (see RQ2).

The empirical results impact feature modeling tools (e.g., WebFML) and call for more investigations in terms of user experience.

As part of WebFML we have integrated default synthesis heuristics for (1) one-step full synthesis, (2) ranking lists and (3) clusters. We choose the most suited heuristics according to the empirical results. We now discuss our choices, some tradeoffs, and practical implications of the experiments.

For one-step full synthesis, we select PathLength with the reduced BIG as the default heuristic (PathLength gives the best results for the SPLOT dataset). All heuristics operating over the BIG are inferior to PathLength and are not included in WebFML. Statistical tests show no clear superiority of PathLength over other ontological heuristics with the reduced BIG or FMFASE. The choice of PathLength can thus be replaced by another heuristic (WebFML allows users to choose a specific heuristic).

More importantly, the empirical results show that one-step full synthesis is far from the ground truth. Two attitudes are possible for a user. The first is to refactor the synthesized FM and fix the erroneous relations between features. The second is to not use a one-step full synthesis. In any case, a crucial feature of WebFML is the ability to provide an interactive support for users (see hereafter).

For the computation of ranking lists, PathLength and Wikipedia heuristics outperform the other heuristics of FMONTO and FMONTO LOGIC . The two heuristics have very similar results. In WebFML, we choose PathLength as the default heuristic. The reason of this choice instead of Wikipedia is only technical. The Wikipedia heuristic requires a large database (40GB) which makes the deployment harder than with a WordNet based heuristic.

For the computation of clusters, two ontological heuristics stand out and have interesting properties: PathLength and Levenshtein. Yet the choice of a default heuristic requires to consider some tradeoffs. On the one hand, Path-Length is the most accurate heuristic. On the other hand, the correct clusters produced by Levenshtein cover more features. In practice, a user of WebFML needs to review less clusters with PathLength but the part of the hierarchy that could be synthesized from these clusters is smaller. Conversely, using Lev-enshtein forces the user to review more clusters but the induced benefit can be more important.

The tradeoff between the number of clusters to review and the accuracy of the heuristics needs to be addressed in a usability study. Currently, Levenshtein is the default heuristic retained for computing clusters in WebFML. WebFML does not present logical feature groups by default, considering they may overwhelm users with lots of false clusters. Nevertheless users can depict them on demand, typically when choices have already been made and the number of clusters is becoming lower. More generally, users can change heuristics for clusters if needs be and WebFML provides facilities to manage clusters (e.g., non relevant clusters can be removed).

Summary. Ranking lists, logical feature groups, cliques, clusters with ontological heuristics: all are potentially useful for the synthesis; and the better they are, the better it is for users. Based on empirical results, WebFML integrates state-of-the-art techniques and provides advanced facilities for manipulating the information (e.g., unfolding of cliques). Now the overall challenge is to make all these structures visible into an environment -without overwhelming and distracting the user with extraneous or redundant information. The usability aspects of an FM synthesis environment like WebFML deserve a focused and careful attention. We leave it as future work.

Threats to Validity

Threats to external validity are conditions that limit our ability to generalize the synthesis results to other forms of dependencies or feature names. A first concern is whether FMs are representative of practice. We use the SPLOT public repository [START_REF]SPLOT: Software Product Line Online Tools[END_REF]. SPLOT is a common benchmark for the FM community (see, e.g., [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] Haslinger | Reverse engineering feature models from programs' feature sets[END_REF][START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF][START_REF] Mendonca | SAT-based analysis of feature models is easy[END_REF][START_REF] Pohl | A performance comparison of contemporary algorithmic approaches for automated analysis operations on feature models[END_REF][START_REF] Pohl | Measuring the structural complexity of feature models[END_REF][START_REF] Sayyad | On the value of user preferences in search-based software engineering: a case study in software product lines[END_REF][START_REF] Yi | Mining binary constraints in the construction of feature models[END_REF]) and is considered to manage "realistic" examples by several authors. We also diversify the dataset with the use of PCMs.

Our major concern is whether FMs (from SPLOT or PCMs) are good ground truths w.r.t ontological semantics. Indeed, a unique characteristic of our work is that we do consider the ontological semantics of the FMs. From this respect, it is hard to certify that the chosen FMs are of good quality. The fact that FMs of SPLOT come from academic publications and practitioners is certainly a good point, but not a guarantee. A possible improvement is a manual review of the FMs, at least to discard FMs with nonsense feature names, at best to possibly improve FMs. The ontological semantics of FMs we extract from PCMs is aligned with the structure of Wikipedia pages and the matrix itself but would also benefit from an external review, e.g., by another pool of researchers.

Another external threat is that we hypothesize that the user effort is reduced thanks to the branching algorithm, the computation of clusters and ranking lists, and the interactive support. We have not run user experiments to validate this claim. Such experiments involve usability of WebFML while we focus on the automated techniques. This evaluation is future work.

A first internal threat is that the manual selection of the SPLOT FMs was done by the authors. To avoid subjective choices, we clearly defined criteria for rejecting a FM before doing the selection. Moreover, the selection was performed separately by two of the authors and their results were cross-checked.

Another internal threat is that the extraction of FMs from PCMs is a mix between automated techniques and manual directives. This creates a threat of potential bias, since the author knew the procedures that were to be evaluated against this model. We take care of retaining the original structure of the PCMs. The manual intervention essentially consists in removing unnecessary columns (like the version number, website or developer name of a product). Importantly, our interpretation of variability remains fixed for all the PCMs (e.g., we interpret a "No" value in a cell as an absence of a feature). Another interpretation of variability can lead to a different set of dependencies and may disturb some heuristics (e.g., the use of the reduced BIG). We plan to further investigate this hypothesis in the future. Moreover, as we apply part of our procedures to Wikipedia PCMs dataset, one might perceive that some of the heuristics, based also on Wikipedia, are biased. However the heuristics do not operate over Wikipedia pages where we extracted the PCM. We exploit Wikipedia as a general ontology.

Another internal threat comes from the manual optimization of the clustering thresholds for the evaluation of the heuristics. Another set of thresholds could generate less favourable results. It is unclear whether this difference would be significant.

The statistical tests performed in the evaluation form another internal threat. Performing a different test or interpreting differently the results could change the conclusions about the effectiveness of our algorithms and heuristics. However, the Wilcoxon test and the 0.05 threshold for the p-values are classical setups for this kind of evaluation. Moreover, we provide all the p-values in Appendix A so that the reader can make her own interpretation of the results.

Finally we implement various heuristics and procedures for synthesizing FMs or collecting statistics. Their implementation may be incorrect. We thoroughly tested our infrastructure using test cases and reuse as much as possible existing codes [START_REF] Acher | Familiar: A domain-specific language for large scale management of feature models[END_REF][START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF]. We replicated numerous times the empirical study, on different datasets (see, e.g., our technical report using an older SPLOT dataset [START_REF] Bécan | Breathing Ontological Knowledge Into Feature Model Management[END_REF]). Besides the collection of results and statistics is fully automated with R scripts.

Related Work

We discuss the differences and synergies between existing works and our proposal.

FM synthesis

Techniques for synthesising an FM from a set of dependencies (e.g., encoded as a propositional formula) or from a set of configurations (e.g., encoded in a product comparison matrix) have been proposed [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF][START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] Czarnecki | Sample spaces and feature models: There and back again[END_REF][START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF][START_REF] Haslinger | Reverse engineering feature models from programs' feature sets[END_REF][START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF][START_REF] Janota | Model construction with external constraints: An interactive journey from semantics to syntax[END_REF][START_REF] Lopez-Herrejon | Reverse engineering feature models with evolutionary algorithms: An exploratory study[END_REF][START_REF] Lopez-Herrejon | An assessment of search-based techniques for reverse engineering feature models[END_REF][START_REF] She | Reverse engineering feature models[END_REF]. An important limitation of prior works is the identification of the feature hierarchy when synthesizing the FM, that is, the user support is either absent or limited.

In [START_REF] Andersen | Efficient synthesis of feature models[END_REF][START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF], the authors calculate a diagrammatic representation of all possible FMs, leaving open the selection of the hierarchy and feature groups. Janota et al. [START_REF] Janota | Model construction with external constraints: An interactive journey from semantics to syntax[END_REF] developed an interactive editor, based on logical techniques, to guide users in synthesizing an FM. The algorithms proposed in [START_REF] Haslinger | Reverse engineering feature models from programs' feature sets[END_REF][START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF][START_REF] Lopez-Herrejon | Reverse engineering feature models with evolutionary algorithms: An exploratory study[END_REF] do not control the way the feature hierarchy is synthesized either. We demonstrated in Section 6.2 that the ontological semantics of the resulting FMs significantly deviates from the ground truths while a hybrid approach provides better results. In addition no user support is provided in [START_REF] Haslinger | Reverse engineering feature models from programs' feature sets[END_REF][START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF][START_REF] Lopez-Herrejon | Reverse engineering feature models with evolutionary algorithms: An exploratory study[END_REF][START_REF] Lopez-Herrejon | An assessment of search-based techniques for reverse engineering feature models[END_REF] to interactively synthesize or refactor the resulting FM. In [START_REF] Acher | Support for reverse engineering and maintaining feature models[END_REF], we proposed a synthesis procedure that processes user-specified knowledge for organizing the hierarchy of features. The effort may be substantial since users have to review numerous potential parent features (6.3 in average for the FMs of the SPLOT repository and 8.3 for the PCM dataset, see Section 6).

Our study provides empirical evidence that a one step synthesis is unlikely, highlighting the need to interactively support users in synthesizing FMs. The results also further the understanding of strengths and weaknesses of logical components (cliques, feature groups, BIG) computed by some of these approaches.

She et al. [START_REF] She | Reverse engineering feature models[END_REF] proposed an heuristic to rank the correct parent features in order to reduce the task of a user. Though the synthesis procedure is generic and similar to ours, they assume the existence of feature descriptions in the software projects Linux, eCos, and FreeBSD. In this article we develop a series of alternative techniques for computing ranking lists and also clusters, applicable to any domain. We also perform an empirical study in other domains than the operating system domain.

She et al. reported in Section 7 of [START_REF] She | Reverse engineering feature models[END_REF] that their attempts to fully synthesize an FM did not lead to a desirable hierarchy -such as the one from reference FMs used in their evaluation -coming to the conclusion that an additional expert input is needed. Our empirical study confirms that a full synthesis is not adequate either and that the user support is highly needed.

Davril et al. [START_REF] Davril | Feature model extraction from large collections of informal product descriptions[END_REF] presented a fully automated approach, based on prior work [START_REF] Hariri | Supporting domain analysis through mining and recommending features from online product listings[END_REF], for constructing FMs from publicly available product descriptions found in online product repositories and marketing websites such as SoftPedia and CNET. The proposal is evaluated in the anti-virus domain.

A key difference is the presence of textual documents to mine and organize features. Our techniques operate over a predefined set of features and dependencies. We do not assume any additional inputs for selecting the feature hierarchy (see next section for a discussion). Moreover no user support is provided to refactor the resulting FM or breath ontological knowledge during the synthesis procedure. It could help users to improve the quality of FMs, i.e., closer to the quality of reference FMs manually specified by participants of the experiment [START_REF] Davril | Feature model extraction from large collections of informal product descriptions[END_REF].

FM extraction

Nadi et al. [START_REF] Nadi | Mining configuration constraints: Static analyses and empirical results[END_REF] developed a comprehensive infrastructure to automatically extract configuration constraints from C code. Their mining procedure can serve as input of our techniques to eventually synthesize a feature model.

In [START_REF] Acher | On extracting feature models from product descriptions[END_REF], a semi-automated procedure to support the transition from product descriptions (expressed in a tabular format) to FMs is proposed. In [START_REF] Acher | Extraction and evolution of architectural variability models in plugin-based systems[END_REF], architectural knowledge, plugins dependencies and the slicing operator are combined to obtain an exploitable and maintainable FM ; in particular the feature hierarchy reflects the hierarchical structure of the system. Ryssel et al. developed methods based on Formal Concept Analysis and analyzed incidence matrices containing matching relations [START_REF] Ryssel | Extraction of feature models from formal contexts[END_REF].

The procedures exposed in [START_REF] Acher | Extraction and evolution of architectural variability models in plugin-based systems[END_REF][START_REF] Acher | On extracting feature models from product descriptions[END_REF][START_REF] Davril | Feature model extraction from large collections of informal product descriptions[END_REF][START_REF] Ryssel | Extraction of feature models from formal contexts[END_REF][START_REF] She | Reverse engineering feature models[END_REF] are specific to a project or a domain and assume the existence of a certain structure or artefacts (e.g., textual corpus, hierarchical model of the architecture) to organize the features. We cannot make similar assumptions in the general case. First, there are sometimes no opportunity to exploit artefacts or knowledge. In the case of the SPLOT repository, there are no artefacts (e.g., feature descriptions) associated to FMs. Another example is when the list of features is flattened and no prior ontological knowledge can be inferred as it is the case in the matrix of Fig. 3a (cf page 7). Ontological knowledge is also missing when extracting conditional compilation directives from source code and build files [START_REF] Dietrich | A robust approach for variability extraction from the linux build system[END_REF]. Second, procedures to extract ontological knowledge are specifically developed or customized to a project, requiring a substantial effort.

Our solution can be seen as an agnostic, lightweight method to breath ontological knowledge into FM synthesis, reusable in every projects or domains.

Yi et al. [START_REF] Yi | Mining binary constraints in the construction of feature models[END_REF] proposed to apply support vector machine and genetic techniques to mine binary constraints (requires and excludes) from Wikipedia. This scenario is particularly relevant when dealing with incomplete dependencies. They evaluated their approach on two FMs of SPLOT. Our techniques might be used to suggest logical relationships in case strong ontological relations between features are inferred. Yet the idea of passing "from ontology to logic" (rather than "from logic to ontology" as we do in this article) needs to be empirically evaluated.

Vacchi et al. [START_REF] Vacchi | Automating Variability Model Inference for Component-Based Language Implementations[END_REF] proposed an approach to automatically infer a feature model from a collection of already implemented language components. The goal is to automate the configuration of families of (domain-specific) programming languages. The evaluation showed that a substantial effort is needed to incorporate domain (or ontological) knowledge. Given the specific application domain, there are three notable differences: (1) the mined implication graph is a rough over-approximation of the configuration set; (2) the complete list of features is not a priori known; (3) feature names are quite technical and specific, so that users have to build their own semantic network. Bagheri et al. [START_REF] Bagheri | Decision support for the software product line domain engineering lifecycle[END_REF] proposed a collaborative process to mine and organize features using a combination of natural language processing techniques and Wordnet. Ferrari et al. [START_REF] Ferrari | Mining commonalities and variabilities from natural language documents[END_REF] applied natural language processing techniques to mine commonalities and variabilities from brochures.

Alves et al. [START_REF] Alves | An exploratory study of information retrieval techniques in domain analysis[END_REF], Niu et al. [START_REF] Niu | Concept analysis for product line requirements[END_REF], Weston et al. [START_REF] Weston | A framework for constructing semantically composable feature models from natural language requirements[END_REF], and Chen et al. [START_REF] Chen | An approach to constructing feature models based on requirements clustering[END_REF] applied information retrieval techniques to abstract requirements from existing specifications, typically expressed in natural language. These works do not consider precise logical dependencies and solely focus on ontological semantics. As a result users have to manually set the variability information. Moreover a risk is to build an FM in contradiction with the actual dependencies of a system.

The techniques exposed in this section are complementary to our proposals, since they compute ontological knowledge that can be incorporated into our FM synthesis support.

Tool Support

There are numerous existing academic or industrial tools for specifying and reasoning about FMs. FeatureIDE [START_REF] Thüm | Reasoning about edits to feature models[END_REF][START_REF] Thüm | Featureide: An extensible framework for feature-oriented software development[END_REF] is an Eclipse-based IDE that supports all phases of feature-oriented software development for the development of product lines (domain analysis, domain implementation, requirements analysis and software generation). FAMA (Feature Model Analyser) [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF] is a framework for the automated analysis of FMs integrating some of the most commonly used logic representations and solvers. SPLOT [START_REF] Mendonca | software product lines online tools[END_REF] provides a Webbased environment for editing and configuring FMs. S2T2 [START_REF] Pleuss | Visualization of variability and configuration options[END_REF] is a tool for the configuration of large FMs. Weston et al. [START_REF] Weston | A framework for constructing semantically composable feature models from natural language requirements[END_REF] provided a tool framework ArborCraft which automatically processes natural-language requirements documents into a candidate FM, which can be refined by the requirements engineers. Commercial solutions (pure::variants [74] and Gears [START_REF] Krueger | Biglever software Gears and the 3-tiered spl methodology[END_REF]) also provide a comprehensive support for product lines (from FMs to model/source code derivation). Our environment is compatible with some of these tools. However none of the existing tools propose support for synthesizing, merging, slicing, or refactoring FMs.

Conclusion

In this article, we addressed the problem of synthesising a feature model (FM) conformant to a set of dependencies and also exhibiting an appropriate ontological semantics as defined by its hierarchy and feature groups. This problem is crucial for software product line (re-)engineering scenarios involving reverse engineering, slicing, or refactoring of FMs.

We developed and evaluated a series of automated techniques, applicable without prior knowledge or artefacts, to breath ontological knowledge into FM synthesis. Our empirical evaluation on 156 FMs, coming from various domains, demonstrated that a hybrid approach, mixing ontological and logical techniques, provides the best support -either for fully synthesizing FMs or for assisting users through ranking lists and clusters.

The data, code, and instructions for reproducing the results are available online http://tinyurl.com/OntoFMExperiments and act as a baseline for comparison. Based on our findings, we developed an ontologic-aware synthesis environment, called WebFML, that equips important automated operations for FMs with ontological capabilities. More details can be found in http: //tinyurl.com/WebFMLDemo.

As future work, we plan to investigate usability aspects of WebFML in practical reverse engineering or maintenance settings. Another research direction is to exploit specific information sources and artefacts that may be present in software projects to automatically capture and breath ontological knowledge. Meanwhile, we can hope that generic ontologies (like Wordnet) and open, collaborative-based initiatives (like Wikipedia) will be enriched to cover more and more technical domains. Future work could also generalize our ontological-aware synthesis to FMs with attributes and multi-features [START_REF] Cordy | Beyond boolean product-line model checking: dealing with feature attributes and multi-features[END_REF] or formalisms close to FMs [START_REF] Berger | A study of variability models and languages in the systems software domain[END_REF].

A Detailed Results of Statistical Tests

Numerous statistical tests were performed to evaluate our FM synthesis algorithm and heuristics (see Section 6 for further details). In this appendix, we present the comprehensive results of the tests. In particular, we report all the p-values and effect sizes that were computed.

There are two kinds of tables in this appendix. The first kind compares ontological techniques (displayed on top of the table) to purely logical techniques (displayed on the left of the table). The p-value corresponds to the comparison of an ontological technique with a logical one. The effect size is the difference between the mean score of the ontological technique and the mean score of the logical one. It means that if the effect size is positive, the ontological technique outperforms the logical one whereas if the effect size is negative, it is the opposite relation.

The second kind of tables compares each heuristic performing on the complete BIG with the same heuristic on the reduced BIG. The p-value corresponds to this comparison and the effect size is the difference between the mean score of the heuristic on the reduced BIG and the mean score on the complete BIG. It means that if the effect size is positive, the same heuristic performs better on the reduced BIG than on the complete BIG. If the effect size is negative, the reduced BIG has a negative impact on the heuristic.

Each table is related as follows to an hypothesis in Section 6:

H1

  a) Product comparison matrix (✓ feature is in the product ; ✕ feature is not in the product) PostgreSQL ! Proprietary License } RE = { PostgreSQL => Domain } EX = { Proprietary License => !Programming Language, Local => !Proprietary License } Ѱ = {∅} (b) f mg // root and mandatory relationships Wiki ∧ (Wiki ! Storage) ∧ (Wiki ! License) ∧ (Wiki ! Hosting) // parent-child relationships ∧ (Programming Language ⇒ Wiki) ∧ (Java ⇒ Programming Language) ∧ (PHP ⇒ Programming Language) ∧ (MySQL ⇒ Storage) ∧ ; ∧ (Domain ⇒ Hosted Service) // mutual exclusions: at least 1 and at most 1 (Xor-groups) ∧ (Java ⇒ !PHP) ∧ (Programming Language ⇒ (Java ∨ PHP)) ∧ … ∧ (Local ⇒ !Hosted Service) ∧ (Hosting ⇒ (Local ∨ Hosted Service)) // cross-tree constraints (EQ, RE, EX) ∧ (PostgreSQL ! Proprietary License) ∧ ... ∧ (Local => !Proprietary License)

Fig. 5 :

 5 Fig. 5: Reduced binary implicationg graph of the graph in Figure 4

Fig. 6 :

 6 Fig. 6: Ontologic-aware feature model synthesis

Fig. 8 :

 8 Fig. 8: Clique unfolding: simple versus complex

Fig. 9 :

 9 Fig. 9: Logical feature groups: bi-implied features, clique contraction, parent place-holder

Table 1 :

 1 Synthesis techniques used for the experiments SPLOT dataset.

Table 2 :

 2 Properties of FMs (average per FM)

		# features	# edges in the BIG	# edges in the reduced BIG	Depth of hierarchy
	SPLOT (126 FMs)	17.6 (min 10, max 56)	131.7	54.8	3.8
	PCM (30 FMs)	72.4 (min 23, max 177)	580.5	316.6	4.0

  Table 3a and Table 3b indicate that all techniques benefit from the reduction of the BIG. However the improvement is more apparent for FMRAND BIG . Specifically FMRAND RBIG increases by 24.1% (resp. 10.4%) the effectiveness of FMRAND BIG in PCM dataset (resp. SPLOT dataset). Comparatively, the best improvement of FMONTO LOGIC w.r.t. FMONTO is 21.8% (resp. 8.2%) in PCM dataset (resp. SPLOT dataset).

Table 3 :

 3 Effectiveness of full synthesis (percentage of common edges)

				(a) Full synthesis with BIG
	Data set	Pure logical techniques FMRAND BIG	SW	L	Ontological techniques (FMONTO) WP PL Wiki	Wikt
	SPLOT	average median	20.9 16.7		28.8 24.0	26.9 21.8	29.1 27.3	30.4 27.3	29.4 26.5	28.5 27.3
	PCM	average median	15.9 14.0		24.0 19.9	19.4 18.0	20.8 19.0		23.2 22.4	26.3 27.1	22.7 19.0
	(b) Full synthesis with a reduced BIG ( means that the approach cannot be applied due to
	performance issues)
	Data set	Pure logical techniques FMFASE FMFASE SAT FMRAND RBIG	Hybrid techniques (FMONTO LOGIC ) SW L WP PL Wiki Wikt
	SPLOT	average median	36.1 35.8	31.9 25.0	31.3 27.3			36.9 32.7	34.9 30.8	36.5 32.2	37.8 36.2	37.4 33.9	36.7 33.3
	PCM	average median		39.9 32.9	40.0 32.8			43.1 35.9	39.8 34.2	42.6 34.1	43.6 35.2	44.4 37.4	42.2 35.5

Table 4 :

 4 Percentage of correct parents in the top 2 positions of the ranking lists (RQ2)

				(a) With BIG
	Data set	Pure logical technique FMRAND BIG	SW	L	Ontological techniques (FMONTO) WP PL Wiki	Wikt
	SPLOT	average median	43.0 38.3	50.0 48.8	49.5 46.3	51.6 50.0	53.2 50.0	51.4 55.4	50.2 50.0
	PCM	average median	32.3 28.9	39.9 37.2	37.3 35.8	37.0 34.5	39.8 40.0	41.7 39.5	38.0 34.0
			(b) With reduced BIG
	Data set	Pure logical technique FMRAND RBIG	SW	L		techniques (FMONTO LOGIC ) WP PL Wiki	Wikt
	SPLOT	average median	51.6 50.5	56.4 55.6	55.6 55.1	57.1 54.9	58.9 56.3	57.1 58.3	56.5 57.1
	PCM	average median	52.2 46.5	54.9 53.5	53.0 47.7	55.0 52.9	56.3 55.0	55.7 55.9	54.3 53.6
	Definition 7 The effectiveness of an FM synthesis algorithm for computing
	clusters is composed of two aspects:
		Percentage of correct clusters =	# correct clusters # clusters
	Percentage of features in a correct cluster =	# features in correct clusters |F |

Table 5 :

 5 Clusters generated by heuristics (RQ2)(a) Clusters generated by FMRAND BIG and FMONTO

	Metric	Data set	Pure logical technique FMRAND BIG	SW	Ontological techniques (FMONTO) L WP PL Wiki Wikt
	Number of clusters	SPLOT PCM	average median average median	6.2 5.0 29.7 25.0	4.1 4.0 16.8 15.5	4.0 3.5 17.6 14.5	2.7 2.0 5.8 5.0	2.5 2.0 8.7 7.0	3.3 3.0 9.8 8.0	2.9 3.0 12.3 9.5
	Clusters'size	SPLOT PCM	average median average median	2.2 2.1 2.3 2.3	2.9 2.7 3.3 3.1	2.8 2.5 2.8 2.8	2.5 2.3 2.6 2.5	2.3 2.2 2.6 2.4	2.9 2.7 5.8 5.1	2.3 2.0 3.0 2.8
	Percentage of	SPLOT	average median	27.7 25.0	50.4 50.0	55.3 50.0	57.3 50.0	67.6 75.0	54.7 50.0	66.8 69.0
	correct clusters	PCM	average median	14.9 12.8	49.6 47.3	62.6 65.5	60.8 64.6	79.2 77.7	53.7 57.1	71.0 66.7
	Percentage of features	SPLOT	average median	18.9 16.7	29.0 26.5	31.0 30.0	19.5 17.9	21.8 20.0	25.7 22.2	24.5 23.3
	in a correct cluster	PCM	average median	12.5 10.5	35.0 32.3	41.4 41.2	12.9 12.4	22.8 23.2	24.5 21.9	32.2 31.9
	(b) Clusters generated by FMRAND RBIG and FMONTO LOGIC
	Metric	Data set	Pure logical technique FMRAND RBIG	Ontological techniques (FMONTO LOGIC ) SW L WP PL Wiki Wikt
	Number of clusters	SPLOT PCM	average median average median	4.0 4.0 12.9 12.0	3.0 3.0 11.2 10.0	3.1 3.0 14.0 13.0	2.3 2.0 4.8 5.0	2.0 2.0 7.6 6.5	2.5 2.0 7.1 6.0	2.3 2.0 9.8 9.0
	Clusters'size	SPLOT PCM	average median average median	2.1 2.0 2.2 2.2	2.5 2.3 3.1 2.7	2.5 2.4 2.7 2.8	2.2 2.0 2.5 2.4	2.1 2.0 2.5 2.3	2.5 2.5 4.4 3.8	2.1 2.0 2.9 2.7
	Percentage of	SPLOT	average median	40.4 33.3	66.2 66.7	67.3 75.0	64.7 66.7	73.2 100.0	67.5 75.0	74.8 100.0
	correct clusters	PCM	average median	36.7 28.6	68.2 71.4	75.9 82.7	73.3 76.4	89.2 89.6	72.4 80.0	85.7 89.4
	Percentage of features	SPLOT	average median	17.9 15.4	26.6 23.1	29.2 29.0	18.7 16.7	19.8 17.0	23.8 20.0	22.4 20.0
	in a correct cluster	PCM	average median	12.3 10.5	34.6 32.3	41.0 41.2	12.8 12.4	22.7 23.2	24.2 21.4	32.2 31.9

Table 6 :

 6 Cliques and logical feature groups as clusters (a) With the BIG ( means that the clusters cannot be computed due to performance issues)

	Metric	Data set		Cliques	All groups	Feature groups Mutex Xor	Or
	Number of clusters	SPLOT PCM	average median average median	1.6 1.0 1.4 1.0	9.5 3.0 55.7 8.0		2.8 0.0 45.2 7.5	5.9 1.0 17.8 1.0	1.3 1.0
	Clusters'size	SPLOT PCM	average median average median	5.0 4.0 7.0 6.0	2.2 2.3 5.7 5.0		1.2 0.0 5.6 4.5	1.6 2.0 5.4 5.0	1.8 2.0
	Percentage of correct	SPLOT	average median	50.0 50.0	69.3 75.0		41.7 33.3	89.1 100.0	72.9 100.0
	clusters	PCM	average median	31.1 0.0	92.2 100.0		91.5 100.0	91.1 100.0
	Percentage of features	SPLOT	average median	17.5 15.4	36.3 35.0		5.8 0.0	21.9 16.0	13.2 8.9
	in a correct cluster	PCM	average median	3.3 0.0	60.7 60.7		53.2 53.1	15.6 12.2
	(b) With the feature graph (reduced BIG)
	Metric		Data set		All groups	Feature groups Mutex Xor	Or
	Number of clusters	SPLOT PCM	average median average median	3.7 2.0 10.4 8.0		0.4 0.0 8.4 5.0	2.0 1.0 2.0 1.0	1.3 1.0
	Clusters'size	SPLOT PCM	average median average median	2.2 2.3 5.9 5.0		0.5 0.0 5.3 3.9	1.4 2.0 5.8 5.0	1.8 2.0
	Percentage of correct	SPLOT	average median	80.0 100.0		69.0 100.0	92.1 100.0	72.9 100.0
	clusters	PCM	average median	100.0 100.0		100.0 100.0	100.0 100.0
	Percentage of features in a	SPLOT	average median	32.6 33.3		2.6 0.0	16.7 13.6	13.2 8.9
	correct cluster	PCM	average median	64.3 60.7		46.0 40.7	18.3 14.0

  Table 7a compares FMONTO with FMRAND BIG for automatically synthesizing an FM while Table 7b compares FMONTO LOGIC with FMRAND RBIG . H2 Table 8 compares FMRAND BIG and FMONTO with respectively FMRAND RBIG and FMONTO LOGIC on the fully automated synthesis. H3 Table 9a compares FMONTO with FMRAND BIG for computing ranking lists while Table 9b compares FMONTO LOGIC with FMRAND RBIG . H4 Table 10 compares FMRAND BIG and FMONTO with respectively FMRAND RBIG and FMONTO LOGIC on the computation of ranking lists. H5 Table 11a (resp. Table 11c) compares FMONTO with FMRAND BIG on the percentage of correct clusters (resp. percentage of features in a correct cluster) generated by the heuristics. Table 11b and 11d present the same results but for FMONTO LOGIC and FMRAND RBIG . H6 Table 12a compares FMRAND BIG and FMONTO with respectively FMRAND RBIG and FMONTO LOGIC on the percentage of generated correct clusters. Table 12b presents the same comparison but for the percentage of features in a correct cluster. H7 Table 13a compares the percentage of correct feature groups generated from the BIG with feature groups generated from the reduced BIG. Table 13b presents the same comparison but for the percentage of features in a correct group.

Definition 4 is exactly the definition of feature implication graph employed in[START_REF] She | Reverse engineering feature models[END_REF]. In another context (simplification of conjunctive normal form formula), it should be noted that Heule et al.[START_REF] Heule | Efficient cnf simplification based on binary implication graphs[END_REF] use a different definition of binary implication graph than ours.

The empirical study of the next section is precisely here to observe and quantify the limits in practical settings.

The extraction process is time-consuming (about 2 days on a single machine) and the extracted database contains approximatively 40GB of data. WikipediaMiner also provides an API to search and compare articles in the database.

The heuristics based on WikipediaMiner do not guarantee that the most relevant article is retrieved. For instance, searching Storage in Wikipedia leads to a disambiguation page linking to different types of storage. Our current strategy is to arbitrarily choose a given definition. Asking the user to choose the most appropriate article can raise this limitation and is an interesting perspective to further improve the effectiveness of our heuristic.

http://sourceforge.net/projects/simmetrics

http://extjwnl.sourceforge.net

https://github.com/cpettitt/dagre

http://d3js.org/

The threshold values were manually determined. For each heuristic, we changed the threshold value by steps of 0.1 (all our heuristics return a value between 0 and 1) to maximize the average number of features in a correct cluster.

MySQL <=> Open Source, PostgreSQL <=> Proprietary License } RE = { Java =>