Mathieu Acher
email: macher@fundp.ac.be

Philippe Collet
email: collet@i3s.unice.fr

Philippe Lahire
email: lahire@i3s.unice.fr

Robert B France
email: france@cs.colostate.edu

Separation of Concerns in Feature Modeling: Support and Applications

Keywords: D.2.2 [Software Engineering]: Design Tools and Techniques, Languages, Theory

Feature models (FMs) are a popular formalism for describing the commonality and variability of software product lines (SPLs) in terms of features. SPL development increasingly involves manipulating many large FMs, and thus scalable modular techniques that support compositional development of complex SPLs are required. In this paper, we describe how a set of complementary operators (aggregate, merge, slice) provides practical support for separation of concerns in feature modeling. We show how the combination of these operators can assist in tedious and error prone tasks such as automated correction of FM anomalies, update and extraction of FM views, reconciliation of FMs and reasoning about properties of FMs. For each task, we report on practical applications in different domains. We also present a technique that can efficiently decompose FMs with thousands of features and report our experimental results.

Introduction

The goal of software product line (SPL) engineering is to produce a family of related program variants for a domain [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF]. SPL development starts with an analysis of the domain to identify commonalities and differences between the members of the product line. A common way is to describe variabilities of an SPL in terms of features which are domain abstractions relevant to stakeholders and are typically increments in program functionality [START_REF] Apel | An overview of feature-oriented software development[END_REF]. A Feature Model (FM) is used to compactly define all features in an [Copyright notice will appear here once 'preprint' option is removed.] SPL and their valid combinations; it is basically an AND-OR graph with propositional constraints [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF][START_REF] Schobbens | Generic semantics of feature diagrams[END_REF][START_REF] Thüm | Reasoning about edits to feature models[END_REF].

FMs are becoming increasingly large and complex. A contributing factor to their growing complexity is that FMs are being used not only to describe variability in software designs, but also variability in wider system contexts, at different times in the development and in different parts of the system structures [START_REF] Hartmann | Using feature diagrams with context variability to model multiple product lines for software supply chains[END_REF][START_REF] Kang | Form: A feature-oriented reuse method with domain-specific reference architectures[END_REF][START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF][START_REF] Reiser | Multi-level feature trees: A pragmatic approach to managing highly complex product families[END_REF][START_REF] Tun | Relating requirements and feature configurations: A systematic approach[END_REF]. As a result, the list of concerns that may be considered in an FM is very comprehensive [START_REF] Apel | An overview of feature-oriented software development[END_REF][START_REF] Tun | Concerns and their separation in feature diagram languages -an informal survey[END_REF] ranging from hardware description [START_REF] Kang | Form: A feature-oriented reuse method with domain-specific reference architectures[END_REF], organizational structure [START_REF] Reiser | Multi-level feature trees: A pragmatic approach to managing highly complex product families[END_REF], business or implementation details [START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF]. In practice, the concerns are related in a variety of ways and there can be hundreds of features whose legal combinations are governed by many and often complex rules. The automated extraction of FMs from large implemented software systems now produces very large FMs. As an extreme case, the variability model of Linux exhibits more than 6000 features [START_REF] She | Reverse engineering feature models[END_REF].

It has been observed that maintaining a single large FM for the entire system may not be feasible [START_REF] Dhungana | Structuring the modeling space and supporting evolution in software product line engineering[END_REF][START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF]. On the one hand, several FMs may be originally separated and combined: It is the case when one describes the variability of (sub-)systems that are by nature modular entities (e.g., software components or services [START_REF] Acher | Composing multiple variability artifacts to assemble coherent workflows[END_REF]), when independent suppliers describe the variability of their different products in software supply chains [START_REF] Czarnecki | Staged configuration through specialization and multilevel configuration of feature models[END_REF][START_REF] Hartmann | Supplier independent feature modelling[END_REF], or when a multiplicity of SPLs should be integrated [START_REF] Dhungana | Structuring the modeling space and supporting evolution in software product line engineering[END_REF][START_REF] Hartmann | Using feature diagrams with context variability to model multiple product lines for software supply chains[END_REF]. On the other hand, it can be the intention of an SPL practitioner to modularize the variability description of the system according to different criteria or concerns. It is the case when external variability is distinguished from internal variability [START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF][START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF], when FMs are organized in layers [START_REF] Kang | Form: A feature-oriented reuse method with domain-specific reference architectures[END_REF], or when a simplified representation of an FM (a view) has been tailored for a specific stakeholder, role, task [START_REF] Hubaux | Supporting multiple perspectives in feature-based configuration[END_REF]. With FMs being increasingly complex, describing various concerns of an SPL and handled by several stakeholders (or even different organizations), managing them with a large number of features that are related in a variety of ways is intuitively a problem of Separation of Concerns (SoC) [START_REF] Batory | Refinements and multidimensional separation of concerns[END_REF][START_REF] Tarr | N degrees of separation: multi-dimensional separation of concerns[END_REF]. First, composing support is needed to group and evolve a set of similar FMs, or to manage a set of inter-related FMs [START_REF] Acher | Comparing approaches to implement feature model composition[END_REF]. Second, some complementary decomposing support is as important to reason about local properties or to support multi-perspectives of a typically large FM [START_REF] Acher | Slicing feature models[END_REF]. Due to the complexity of FMs, SoC support should be soundly defined and automated as much as possible. In previous work, we designed a set of composition (insertion, merging, aggregation) [START_REF] Acher | Comparing approaches to implement feature model composition[END_REF] and decomposition (slice) [START_REF] Acher | Slicing feature models[END_REF] operators.Their semantic properties were precisely defined in terms of configuration set and feature hierarchy, and fully automated techniques were developed to synthesize FMs. Using these operators separately has practical but limited interests. In many scenarios and case studies, an SPL practitioner rather needs to combine both techniques and perform sequences of composition and decomposition, while reasoning about intermediate results.

In this paper, we show how the combined use of composition and decomposition operators forms a consistent and powerful support for SoC in feature modeling. We describe several novel applications of the operators, detailing the obtained benefits. These applications comprise i) the corrective capabilities of the operators themselves, ii) view extractions and updates on FMs, with the benefit of handling cross-tree constraints, iii) reconciling FMs that come from different stakeholders or organizations, and iv) reasoning about two kinds of variability to check important properties (realizability, usefulness) of an SPL. For each application, we report on practical use in different case studies. We revisit and implement some existing works with our operators and we report better results either in terms of capability or scalability. Furthermore, we present a technique that can efficiently decompose FMs with thousands of features and outperforms our previous implementation based on binary decision diagrams.

Background: Feature Models

FMs were first introduced in the FODA method [START_REF] Kang | Form: A feature-oriented reuse method with domain-specific reference architectures[END_REF], which also provided a graphical representation through Feature Diagrams. FMs are now widely adopted with support of formal semantics, reasoning techniques and tooling [START_REF] Apel | An overview of feature-oriented software development[END_REF][START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF][START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF][START_REF] Schobbens | Generic semantics of feature diagrams[END_REF]]. An FM defines both a hierarchy, which structures features into levels of increasing detail, and some variability aspects expressed through several mechanisms. When decomposing a feature into subfeatures, the subfeatures may be optional or mandatory or may form Xor or Or-groups. In addition, any propositional constraints (e.g., implies or excludes) can be specified to express more complex dependencies between features. We consider that an FM is composed of a feature diagram coupled with a set of constraints expressed in propositional logic. Figure 1a shows an example of an FM. The feature diagram is depicted using a FODA-like graphical notation used throughout the paper.

The hierarchy of an FM is represented by a rooted tree G = (F, E, r) where F is a finite set of features and E ⊆ F × F is a finite set of edges (edges represent topdown hierarchical decomposition of features, i.e., parentchild relations between them) ; r ∈ F being the root feature.

An FM defines a set of valid feature configurations. A valid configuration is obtained by selecting features so that i) if a feature is selected, its parent is also selected; ii) if a parent is selected, all the mandatory subfeatures, exactly one subfeature in each of its Xor-groups, and at least one of its Or groups are selected; iii) propositional constraints hold. For example, in Figure 1a, { A, B, C, F, P, S, T, W} is a valid configuration, the features D and F cannot be selected at the same time and E cannot be selected without C due to the parent-child relation between E and C.

DEFINITION 1 (Configuration Semantics).

A configuration of an FM g is defined as a set of selected features. g denotes the set of valid configurations of the FM g and is thus a set of sets of features.

FMs have been semantically related to propositional logic [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF]. The set of configurations represented by an FM can be described by a propositional formula φ defined over a set of Boolean variables, where each variable corresponds to a feature (see Figure 1c for the formula corresponding to the FM of Figure 1a). The translation of FMs into logic representations allows one, as we will see in the next sections, to use reasoning techniques for automated FM analysis [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF].

Composition and Decomposition Support

In previous work [START_REF] Acher | Comparing approaches to implement feature model composition[END_REF][START_REF] Acher | Slicing feature models[END_REF], we designed a set of composition and decomposition operators that produce a new FM from one or more than one input FMs. We have defined the semantics of these operators in terms of: configuration semantics We consider that the primary meaning of an FM, known as its configuration semantics, is a set of legal configurations -sets of selected features that respect the dependencies entailed by the diagram and the cross-tree constraints. We thus define the semantics of each operator in terms of the relationship between the configuration sets of the input FMs and the resulting FM.

feature hierarchy Another important property of an FM is the way features are organized -reflected in the feature hierarchy. We recall that two FMs can have identical configuration semantics, yet different hierarchies and thus ontological meaning [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF][START_REF] She | Reverse engineering feature models[END_REF][START_REF] Thüm | Reasoning about edits to feature models[END_REF]. As a result, we consider that the feature hierarchy should also be part of the semantics of the operators.

Aggregate

The aggregate operator supports cross-tree constraints between features so that separated FMs can be inter-related. The input FMs are aggregated under a synthetic root synthetic f t so that the root features of input FMs are childmandatory features of synthetic f t . In addition, the propositional constraints are added in the resulting FM. For example, the aggregate operator can be used to compose four FMs together with constraints (see Figure 5, page 6). The properties of the aggregated FM heavily depends on the set of propositional constraints used during the aggre- ). We consider that the aggregate operator is purely syntactical. As we will see, other complementary techniques can be applied in case an SPL practitioner may want to simplify the aggregated FM or to reason about its properties.

φ f m1 = W // root ∧ W ⇔ P ∧ W ⇔ T ∧ U ⇒ W // optional ∧ V ⇒ T ∧ A ⇔ T // mandatory ∧ A ⇔ B ∧ A ⇔ C ∧ D ⇒ A ∧ E ⇒ C ∧ F ⇒ C // Or-group ∧ P ⇒ R ∨ S ∧ R ⇒ P ∧ S ⇒ P // constraints ∧ E ⇒ D ∧ R ⇒ E ∧ D ⇒ ¬F ∧ S ⇒ (F ∧ ¬E) (c) corresponding propositional formula

Merge

The merge operator is dedicated to the composition of FMs that exhibit similar features (i.e., features with the same name). In this case, the merge operator can be used to merge the overlapping parts of the FMs and then to obtain an integrated FM. The merge uses name-based matching: two features match if and only if they have the same name.

Configuration Semantics. The properties of a merged FM produced by an application of the merge operator are formalized in terms of the sets of configurations of input FMs. Several modes are defined for the merge operator. We only describe here the modes that we will use in the remainder of the paper. The intersection mode is the most restrictive option: the merged FM, F M r , expresses the common valid configurations of F M 1 and F M 2 . The merge operator in the intersection mode is denoted as follows:

F M 1 ⊕ ∩ F M 2 = Result.
The relationship between a merged FM Result in intersection mode and two input FMs F M 1 and F M 2 can be expressed as follows:

F M 1 ∩ F M 2 = Result Another merge operator, called diff, is denoted as F M 1 ⊕ \ F M 2 = Result.
The following defines the semantics of this operator:

F M 1 \ F M 2 = {x ∈ F M 1 | x / ∈ F M 2 } = Result
Hierarchy. Several FMs, with different hierarchies, can represent the same set of configurations [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF][START_REF] She | Reverse engineering feature models[END_REF][START_REF] Thüm | Reasoning about edits to feature models[END_REF]. So in particular several merged FMs can be produced and consistently represent the expected set of configurations while having different hierarchies. Intuitively, the more a parent-child relation occurs in the input FMs, the more an edge in the merged hierarchy should be retained. The problem of choosing a hierarchy from amongst a set of hierarchies can be formulated as a minimum spanning tree problem (see details in [START_REF] Acher | Managing Multiple Feature Models: Foundations, Language and Applications[END_REF]). An example of merge operation in intersection mode is given in Figure 8, page 7.

Slice Operator

The slice operator aims at simplifying or abstracting FMs by focusing on selected aspects of semantics. The overall idea behind FM slicing is similar to program slicing [START_REF] Weiser | Program slicing[END_REF].

Program slicing techniques proceed in two steps: the subset of elements of interest (e.g., a set of variables of interest and a program location), called the slicing criterion, is first identified; then, a slice (e.g., a subset of the source code) is computed. In the context of FMs, we define the slicing criterion as a set of features considered to be pertinent by an SPL practitioner while the slice is a new FM.

A B C D E F constraints E implies D D implies E (a) [[fm2]] = {{A, B, C, D, E},{A, B, C, F}} W constraints E implies D R implies E P R S A V T U B C D E F (b) [[fmAll]] = [[fm1]]
Figure 2. Two slice operations on fm1 (see Figure 1a)

Configuration Semantics. We define slicing as a unary operation on FM, denoted Π F slice (F M ) where

F slice = {f t 1 , f t 2 , ..., f t n } ⊆ F is a set of features.
The result of the slicing operation is a new FM, F M slice , such that:

F M slice = {x ∩ F slice | x ∈ F M } (called the projected set of configurations).
Hierarchy. Intuitively, the hierarchy of F M slice is such that features are connected to their closest ancestor if their parent is not part of the slicing criterion. A formal definition can be found in [START_REF] Acher | Managing Multiple Feature Models: Foundations, Language and Applications[END_REF]. Two examples of slice operation are given in Figure 2.

3 2012/3/2
Case study Concerns Complexity Composing Multiple Variability Artifacts (domain: medical imaging, grid computing ; stakeholders: medical imaging/grid experts) [START_REF] Acher | Composing multiple variability artifacts to assemble coherent workflows[END_REF] the variability is described at different places of the workflow, describing various concerns of connected services dozens of FMs (up to 30), hundreds of inter-related features (up to 400) Modeling Variability From Requirements to Runtime (domain: video surveillance (VS) systems ; stakeholders: VS expert, software engineer) [START_REF] Acher | Modeling variability from requirements to runtime[END_REF] the modeling of requirements and software variability is explicitly separated in two FMs, VSAR and PC 2 FMs, 77 features and 10 8 configurations in VSAR, 51 features and 10 6 configurations in PC, 39 constraints. Management of Product Line and Software Variability (domain: any ; stakeholders: products manager, software engineer) [START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF] two kinds of variability (software and product line) are specified and maintained in two separated FMs f m P L and f m sof tware 2 FMs, 25 features in f m P L , 11 features in f m sof tware , 13 constraints ; Reverse Engineering FMs (domain: component and plugin based systems, stakeholder: software architect) [START_REF] Acher | Reverse engineering architectural feature models[END_REF] multiple variability sources (including architect knowledge) are combined to construct semi-automatically an FM 92 features and 158 constraints ; the number of valid configurations varies from ≈ 10 11 to ≈ 10

Applying Separation of Concerns

Given these composition and decomposition mechanisms, we now argue that these operators, together with other reasoning and editing operators, form a consistent and powerful support for SoC in feature modeling.

Several usage scenarios can be envisaged:

• When an FM is decomposed into smaller FMs (using the slice operator), one may need to reason about the different sets of configurations or simply modify the smaller FMs. The composition operators can be applied afterwards to recompose the smaller FMs ; • When some FMs are composed with constraints (using the aggregate operator), one may need to simplify, redecompose or check the satisfiability of the resulting composed FM ; • Before merging two FMs, one may need to reconcile (or align) the two FMs in case the hierarchy and the vocabulary used in the two FMs differs ; Beyond these simple examples, we now show that though the sole use of the composition / decomposition operators has practical interests, the area of applications grows when these operators are combined together 1 .

The following sections will demonstrate either new capabilities in feature modeling or better scalability in representative scenarios of the field. Each presented technique has been validated on experimental or real-world case studies. Figure 4 gives an overview of the contribution. It charac-terizes each technique, reports the operators involved in the realization of the technique as well as the practical use in case studies. The numbers correspond to the different case studies described in Figure 3, including the application domain, the stakeholders involved, the concerns considered as well as the complexity of FMs.

Corrective Capabilities

Manual or automatic creation of FMs may generate anomalies in them. Generally, these anomalies are regarded as a negative property of an FM since it can easily decrease its maintainability or understandability. DEFINITION 2 (Dead and Core features). A feature f of an FM is dead if it cannot be part of any of the valid configurations. A feature f of an FM is a core feature if it is part of all valid configurations.

Error-free FMs. Benavides et al. identify different kinds of FM anomalies [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF]: i) dead features (see Definition 2) ; ii) false optional features are core features (see Definition 2), despite not being modeled as mandatory ; iii) wrong feature group: For example, features may form an Or-group while being mutually exclusive (see features R and S in the FM of Figure 1a) ; iv) or redundancies [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF] (e.g., cross-tree constraints may be redundant). Despite the need of automatic support for anomaly analysis in FMs, there is a lack of proposals that focus on producing error-free FMs, i.e., FMs that do not contain anomalies as the ones mentioned above.

A form of corrective explanations has been developed in [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF]. It indicates changes (or edits) to be made in the original FM so that it does not contain anomalies anymore. These changes are suggestions, usually once anomalies have been detected and explained, to be applied to the original FM. In this case, the set of configurations of the original FM may be altered (e.g., a dead feature may no longer be dead once changes have been applied). This approach is more appropriate for handling human errors, for example, when an SPL practitioner elaborates an FM and unintentionally introduces errors. On the contrary automatic correction (or simplification) aims at removing anomalies from the original FM while the set of configurations remains exactly the same. Our contribution here takes place in this category, as automatic correction pursues a different objective: anomalies are not necessary errors but an intentional, controlled and/or temporary properties of an FM, for example, when automatic operations are conducted on FMs. As we will see in the next section, it usually happens when two (or more than two) FMs are inter-related by constraints. In this case, features may become dead or core features.

Automatic simplification using the slice. The slicing implementation we propose ensures, by construction, that there is no dead feature, correctly detects core features (thereby false optional features) and avoids redundancy in the representation (e.g., we add an implies/excludes constraint only if it is not already induced by the FM) [START_REF] Acher | Slicing feature models[END_REF]. Hence, we guarantee that the sliced FM does not contain anomalies. As a result, the slice operator can be used as an automated technique to correct anomalies of FMs while preserving the original set of configurations and hierarchy. Moreover, the corrective modifications applied to the original FM can be detected and reported to an SPL practitioner. For example, the slice operation is performed on the FM of Figure 1a, f m1, using all features of f m1 as a slicing criterion. The resulting FM is f mAll (see Figure 2b). Obviously the set of configurations represented by f mAll is the same as the set of configurations represented by f m1, while their feature hierarchies are equal. We can notice that i) the features R and S form an Xor-group in f mAll (and no longer form an Or-group as in f m1) ; ii) the features E and F form an Xor-group (and are no longer optional as in f m1) ; iii) some constraints are no longer present in f mAll to avoid redundancy.

As an application, we directly used this correction technique to automatically remove anomalies in the randomly generated FMs that served as inputs for our experimentations (see Section 5.1 and 7). Both configuration sets and hierarchies were maintained while correcting anomalies.

Managing Different FM Views

We illustrate the need to manage several FMs, possibly interrelated, using an example in the medical imaging domain. In this domain, medical imaging services (e.g., algorithms) are assembled to form complex processing chains (also called workflows). Variability affects different concerns or views of a medical imaging service. In Figure 5, the service is described through different views: information about the deployment on the grid, internal algorithms, the supported communication protocols and the type of handled medical images. As multiple sources of variation are present within a service, several FMs are used where each FM focuses on a specific view of a service. As shown in [START_REF] Acher | Composing multiple variability artifacts to assemble coherent workflows[END_REF], these FMs can then be used to check consistency between composed services and to facilitate their coherent configurations.

Updating FM views

In practice, the different FM views of a service are not independent. The workflow designer has to add constraints to enforce interactions between the FM views. In our example, we consider the following constraints:

M IServiceconstraints = { (c1) F M grid .Kerberos ⇒ F Mproto.KDC (c2) F M grid .SSLAuth ⇔ F Mproto.SSL (c3) F MMIsupport.M RI ⇒ F M algo .P AM (c4) F MMIsupport.CT ∨ F MMIsupport.SP EC ⇒ F M algo .BAM (c5) F MMIsupport.Anonymized ⇒ F Mproto.HeaderEncoding (c6) ¬F M grid .GP U ∨ ¬F M algo .Interactive (c7) F M algo .Interactive ⇒ F M grid ..Linux (c8) F MMIsupport.DICOM ⇒ F Mproto.Rotation ∧ F Mproto.P AM (c9) F M algo .Interactive ⇒ F Mproto.HeaderEncoding }
Determining the impact of these constraints on each FM view cannot be done manually or even automatically with current techniques and tools [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF]. We rely on the corrective capabilities developed in Section 4.1 to perform the update of the different FM views.

Using the slice operator, it simply consists in i) aggregating the four feature models into a single one (fmService) with constraints mapped on it, ii) invoking slice four times producing as much sliced FMs, the slicing criterion being respectively the features of each of the four feature models. As a result, Figure 6a and Figure 6b correspond to the sliced FM with respectively the features of the FMs F M M Isupport and F M algo . The two other FMs are not impacted by the constraints mapped on fmService.

Supporting multiple perspectives

On the same example, the slice operator can be used to extract other views (or perspectives) of a service. In Figure 7, we capture expertises related to security features or to the medical imaging domain. Two slice operations are applied and compute two FM views, stored into fmViewMI

Practical applications

Reverse Engineering Architectural FMs. Besides the above application, the slicing technique was also extensively used in a tool-supported approach to reverse engineer software variability from an architectural perspective [START_REF] Acher | Reverse engineering architectural feature models[END_REF]. The proposed approach was evaluated when applied to FraSCAti, a large and highly configurable component and plugin-based system. Using the slicing technique an accurate view (i.e., an FM) of the software architecture was obtained. The idea was that the software architecture FM, originally produced by an extraction procedure, represents only an over approximation in terms of sets of valid configurations. Hence several sources of information were combined, namely software architecture, plugin dependencies and the correspondences between software elements and plugins. When combined through aggregation, slicing is used to update the view corresponding to the software architecture part. The aggregated FM resulting from the combination of different variability sources and the bidirectional mapping contains 92 features and 158 cross-tree constraints (CTCR 2 =84%). The slicing technique significantly reduced the over approximation of the original architectural FM (from ≈ 10 11 to ≈ 106 ).

Variability in video surveillance. In the development of a video surveillance SPL, we represented the variability of the context and the variability of the software platform as two separated FMs [START_REF] Acher | Modeling variability from requirements to runtime[END_REF]. 77 features and 10 8 configurations were present in the context FM while 51 features and 10 6 configurations were present in the software platform FM. The relationships between the two FMs were described as 39 rules (propositional constraints) relating features across models. Then, in line with specific requirements, we stepwise specialized the FM representing the context by removing some features, by modifying some feature groups, etc. After the specialization of the context FM, we needed to update the software platform FM. To do so, we aggregated the specialized context FM and the software platform FM together with rules. We used the slice operator on the aggregated FM by only including the set of features related to the software platform. We observed that from a specification of a context, the possible configurations in the software platform can be highly reduced. We applied the techniques on different scenarios: the average number of features to con-2 CTCR is the ratio of the number of features in the constraints to the number of features in the feature hierarchy.

Reconciling Feature Models

When managing a set of FMs, the different stakeholders involved in the SPL development may have to put together very similar variability information but with a different structure. For example, in the medical imaging domain, different suppliers (scientists, research teams, companies, etc.) provide imaging services and may use different hierarchies, concepts, vocabulary, etc. when elaborating the FMs.

Technique and example

Let us consider two FMs, f mM I1 and f mM I2, in Figure 8. The two FMs differ. In particular, features Open, Proprietary, NiftiI, NiftiII are present in f mM I1 but not in f mM I2. Intuitively, more structure and details are modeled in f mM I1. As a result, a comparison (see Definition 3) or a merging (see Section 3.2) of the two FMs leads to counter intuitive results, i.e., the intersection of the two configuration sets is empty (see line 4 and 5 of the FAMILIAR script below). Looking at the two FMs, some configurations seem to correspond, for example, the valid configuration {M edicalImage, DICOM } of f mM I2 with the configuration {M edicalImage, Open, DICOM } of f mM I1. We thus need to reconcile (or align) the two FMs and allow an SPL practitioner to align in a coherent way information from f mM I1 and f mM I2. DEFINITION 3 (Kind of edits and Comparison). Let f and g be two FMs. f is a specialization of g if f ⊂ g . f is a generalization of g if g ⊂ f . f is a refactoring of g if g = f . f is an arbitrary edit of g if f is neither a specialization, a generalization nor a refactoring of g. A comparison computes the relationship between two FMs. Using the slice operator, we simply remove features of f mM I1 i) that structure the feature model (i.e., features Open, Proprietary) and ii) that can be abstracted by a single feature (i.e., Nifti abstracts features NiftiI and NiftiII). Then, the comparison can be computed or the merge operator can be used as in Figure 8.

Practical application

Besides the medical imaging domain, we also used the techniques described above for the reverse engineering of FraS-CAti architectural FM. The architectural FM resulting from the automatic extraction (see Section 4.2.3) was compared with another architectural FM, this time manually designed by the software architect (SA) of FraSCAti. Unfortunately, the direct comparison yields to unexploitable results, mainly due to the difference of granularity (i.e., some features in one FM are not present in the other). Basic manual edits of FMs were unpractical as we needed to safely remove features involved in several constraints or that were in the middle of the hierarchy. The slicing operator was extensively applied to remove unnecessary details in both FMs. Once the FMs have been reconciled, the two FMs can be compared so that the differences between them can be identified. This encourages the SA to correct his initial model [START_REF] Acher | Reverse engineering architectural feature models[END_REF].

Reasoning about Two Kinds of Variability

In SPL engineering, two kinds of variability are usually distinguished [START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF][START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF]: software (or internal) variability, hidden from customers, as opposed to product line (PL) (or external) variability, visible to them. Software variability and PL variability can be seen as two concerns of an SPL. Metzger et al. proposed a formal and concise approach for separating PL variability and software variability and enabling automatic analysis [START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF]. The two concerns are modeled as two FMs and inter-related by constraints. The authors mention several properties that should be checked when reasoning about the two kinds of variability. We now revisit here the approach defended in [START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF] and show how the operators can be combined to support SoC in this context.

Realized-by property

An important property of an SPL is realizability, i.e., whether the set of products that the PL management decides to offer is fully covered by the set of products that the software platform allows building. In Figure 9, we want to ensure that for each valid selection/deselection of features of f m P L performed by a customer, there exists at least one corresponding software product described by f m sof tware . The PL variability is documented using f m P L , the software variability is documented using another FM (see f m sof tware ) and the two FMs are related through constraints (see map Sof tP L ). Note that the mapping between features of f m P L and f m sof tware is not necessarily one-to-one. To this end we first reason about the relationship between f m sof tware and f m P L . We compute f m G , the aggregation of f m P L and f m sof tware and add the constraints map Sof tP L .

In terms of FMs, the realizability property can be formally expressed (F P L the set of features of f m P L ):

∀cp ∈ f m P L , cp ∈ Π F P L (f m G ) (1)
f m P L P rime = Π F P L (f m G )
Then, we compare the resulting FM, f m P L P rime , with the original PL model, f m P L . If f m P L P rime is not a refactoring of f m P L , the realizability property is violated since some existing products of f m P L are removed in f m P L P rime and no product is added. Finally, we can compute the set of products that are in f m P L but not in f m P L P rime using the merge operator in diff mode. The merge operator produces f m P LDif f . Back to the example of Figure 9, we obtain that the realizability property does not hold and that three products proposed to customers cannot be realized by the platform:

f mP L ⊕ \ f mP L P rime = f m P LDif f = {{V 1, V 3, V 2, V P 1}, {V 1, V P 1}, {V 3, V P 1}}
Only the following two products can be realized:

f mP L ⊕∩ f mP L P rime = f mP LInter = {{V 1, V 3, V P 1}, {V 2, V 3, V P 1}}

Non useful products

A product is useful if it is a possible realization of a PL member. As argued in [START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF], the list of non-useful products is a symptom of unused flexibility of the software platform. It can be on purpose, for example, justified by future marketing extensions. The usefulness property can be seen as the "symmetric" of the realized-by property. Formally, all products are useful if the following relation holds:

∀cp ∈ f m sof tware , cp ∈ Π F sof tware (f m G )
Hence, similar techniques involving aggregate, slice and merge can be used to check the property.

Practical applications

Reasoning about two concerns. We apply the techniques using the larger example described in [START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF]. We successfully retrieved the same results, but our approach is more efficient since we do not enumerate configurations/products as they do. Moreover, high-level operators (slice, aggregate, compare, merge) facilitate the reasoning realization and offer a systematic solution for SPL practitioners when understanding and maintaining the two FMs. It should be noted that the technique for updating views (see Section 6) can be applied in such contexts, for example, to remove dead features in the PL or software model.

Reasoning about variability properties. In the development of video surveillance systems, a key issue is to ensure that, given a valid configuration of the context, a software configuration can always be obtained. This property is similar to the realized-by property and can be checked using the same techniques. We successfully scale for this case study, whereas it was clearly not the case with the enumerative technique proposed in [START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF].

Towards Scalable Technique to Separate Concerns

Central to the support for SoC in feature modeling is the ability to decompose (i.e., slice) FMs. All applications described in the previous section make extensive use of the slicing technique. It is thus crucial to provide a scalable implementation of the slice operator. A syntactical technique is not adequate, especially in the presence of cross-tree constraints. A technique based on the enumeration of configurations is not scalable, since the number of configurations is exponential to the number of features. To avoid these limitations, we developed a dedicated technique that consists in first computing the propositional formula representing the projected (see Section 3.3) set of configurations. The computation of the propositional formula is essential for reasoning about the projected set of configurations but also for synthesizing the FM. As detailed in [START_REF] Acher | Slicing feature models[END_REF], propositional logic techniques [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF][START_REF] She | Reverse engineering feature models[END_REF] can be applied to construct an FM (including its hierarchy, variability information and cross-tree constraints) from the formula. In this section, we focus on the computation of the propositional formula. We report on the practical limits of an implementation based on binary decision diagrams (BDDs). We describe a symbolic technique that outperforms a BDD-based implementation and that can efficiently decompose FMs with thousands of features. Propositional Formula Encoding. First, we describe the encoding of the projected set of configurations as propositional formula For a slicing F M slice = Π f t1,f t2,...,f tn (F M ), the propositional formula φ slice corresponding to F M slice can be defined as follows:

φ slice ≡ ∃ f tx 1 , f tx 2 , . . . f tx m φ where f tx 1 , f tx 2 , . . . f tx m ∈ (F \ F slice ) = F removed .
Intuitively, all occurrences of features that are not present in any configuration of F M slice are removed by existential quantification in φ. φ slice is obtained from φ by existentially quantifying out variables in F removed . DEFINITION 4 (Existential Quantification). Let v be a Boolean variable occurring in φ. φ |v (resp. φ |v ) is φ where variable v is assigned the value True (resp. False). Existential quantification is then defined as ∃v φ = def φ |v ∨ φ |v .

BDD-based Implementation

In previous work [START_REF] Acher | Slicing feature models[END_REF], we rely on BDDs [START_REF] Brace | Efficient implementation of a bdd package[END_REF] to compute the propositional formula. A BDD is a compact representation of a Boolean function (e.g., a propositional formula). BDDs can be efficiently used to compute the propositional formula described above since computing the existential quantification can be performed in at most polynomial time with respect to the sizes of the BDDs involved [START_REF] Brace | Efficient implementation of a bdd package[END_REF]. Furthermore, BDDs can be used to synthesize an FM in polynomial time regarding the size of the BDD representing the input propositional formula [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF]. A major drawback of BDDs is that finding an optimal variable ordering during BDD construction is NP-hard [START_REF] Brace | Efficient implementation of a bdd package[END_REF]. Some heuristics have been developed and successfully compile FMs to BDDs for a number of features up to 2000 [START_REF] Mendonca | Efficient compilation techniques for large scale feature models[END_REF].

The goal of our experiment was to determine the scalability of the BDD-based implementation w.r.t. the size of the input FMs (i.e., number of features) and the size of the slicing criterion (i.e., number of features to include). For the experiment, we reuse the heuristics (i.e., Pre-CL-MinSpan) developed in [START_REF] Mendonca | Efficient compilation techniques for large scale feature models[END_REF] to reduce the size of BDDs. For a first evaluation, we used several small and medium-sized FMs that were publicly available from SPLOT [START_REF] Mendonca | SAT-based analysis of feature models is easy[END_REF] repository as well as FMs from our case studies. We performed our experiments on more than 100 FMs, the bigger one having 290 features. We found that computing the slice is almost instantaneous in all cases. To go further, we randomly generated FMs with several hundreds of features. We varied i) the number of features, noted #f eatures, from 100 to 2000 features (the known practical limits of BDD) ; ii) CT CR from 10% to 100%. We used the publicly available procedure described in [START_REF] Mendonca | SAT-based analysis of feature models is easy[END_REF] to randomly generate the FMs. In each generated model, each type of mandatory, optional, Xor and Or-groups was added with equal probability. For each FM, we randomly generated a slicing criterion. We varied the percentage of features to slice between 100% (no existential quantification is performed) and 1% (almost all features are existentially quantified). The main results show that:

• The synthesis of the feature diagram has practical limits (up to 800 features 3 ). This limit also applies in our context. We observed that the slicing technique can scale even for an FM with 2000 features if the percentage of features to slice is ≤ 35%. The reason is that the size of a BDD will always be smaller or at least unchanged after existential quantification ;

• The primary limit of the BDD-based implementation lies in the difficulties to construct BDD from the original FM.

In particular, the total number of features in the input FM should not be more than 2000 features, otherwise it is impossible to having a BDD-representation of the formula. It should be noted that whenever an FM can be represented as a BDD, φ slice can be computed. Hence the encoding of φ slice can scale up to 2000 features with a CTCR of 10, whatever the slicing criterion is ;

SAT-based Implementation

She et al. proposed techniques to reverse engineer very large FMs (i.e., with more than 5000 features) [START_REF] She | Reverse engineering feature models[END_REF]. As shown above BDDs do not scale for this order of complexity and therefore the slicing operator cannot process such FMs. She et al. adapted their previous techniques and now rely on satisfiability (SAT) solvers (rather than BDDs as in [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF]). They reported that the use of SAT solvers is significantly more scalable. Hence a SAT-based implementation of slicing is an interesting perspective that motivates our work. We identify two main issues. First, the size of the formula exponentially increases when existential quantification is performed many times, i.e., the number of clauses doubles at each iteration. It may become an issue when the size of F removed is important, even for small FMs. Second, SAT solvers require a formula to be in conjunctive normal form (CNF). It is straightforward to translate the propositional formula of an FM into CNF. However, when existential quantification is performed, the resulting formula is not in CNF (see Definition 4). To tackle the first issue, we substitue each feature of F removed only in those clauses that contain the feature. More formally, let f t be a feature of F removed , φ a formula in CNF decomposed as follows: φ = p(f t, φ) ∧ c(f t, φ) where c(f t, φ) denotes the conjunction of the clauses that do not contain the feature f t and p(f t, φ) denotes the conjunction of the clauses that do contain the feature f t. The existential quantification of f t in φ produces a new formula φ defined as follows:

φ = φ | f t ∨ φ | f t = (p(f t, φ) | f t ∨ p(f t, φ) f t ) ∧ c(f t, φ)
Example. We consider f m1 of Figure 1a (see page 3). We slice f m1 using as slicing criterion all features except T and V (i.e., F removed = {T, V }). It should be noted that the existential quantification of T and V can performed in any order. In this example, we first perform the existential quantification of T, producing the following propositional formula:

φ f m1 = ((W ⇔ T rue ∧ V ⇒ T rue ∧ A ⇔ T rue) ∨ (W ⇔ F alse ∧ V ⇒ F alse ∧ A ⇔ F alse)) ∧ c(V, φ) ∧ T rue ∧ ¬F alse.
Then we iterate by performing the existential quantification of V in φ f m1 . We can observe that at each iteration the formula can be symbolically simplified in many ways. For instance, T cannot be evaluated to False in φ f m1 and therefore the disjunctive clause can be removed. We can also observe that A ⇔ T rue ≡ T rue but we do not consider this kind of simplification since features included in the slicing criterion, like A, must not be removed. However we can sim-plify φ f m1 considering that V ⇒ T rue ≡ T rue since V is included in the slicing criterion. An additional optimisation, related to symbolic simplification, is the order in which the features are existentially quantified. Indeed, we observe that some features are likely to be simplified. We use an heuristic that existentially quantifies in priority features that are at the bottom of the feature hierarchy. To tackle the second issue, we transform the resulting propositional formula into CNF at each iteration (i.e., for each existential quantification of a feature f t). It should be noted that we only need to consider the transformation of (p(f t, φ)

| f t ∨ p(f t, φ) f t ) into CNF since c(f t, φ) is already in CNF.
Generated FMs. For the evaluation of the technique, we used the same FMs as with the experiments conducted for the BDD-based implementation. We also generated FMs with 2000 ≥ #f eatures ≥ 10000 with the same parameters as previously described (10000 features is the practical limit admitted in the literature [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF][START_REF] Mendonca | SAT-based analysis of feature models is easy[END_REF][START_REF] Thüm | Reasoning about edits to feature models[END_REF]). We first verified that the techniques described above are necessary since a naive substitution strategy that does not compute c(f t, φ) is not scalable (scalability issues are observed for #f eatures ≥ 50). Using our technique, we found that: i) computing the propositional formula is almost instantaneous for all FMs of SPLOT (less than one second, whatever the size of the slicing criterion is); ii) the SAT-based implementation scales for #f eatures ≤ 10000 whatever the size of the slicing criterion is; iii) the order in which the features are existentially quantified is of prior importance: we begin to observe scalability issues when quantifying first the features that are in top of the feature hierarchy for #f eatures ≥ 2000 ; iv) for very large FMs (#f eatures ≥ 5000), the computation time is inadequate for an interactive use of the slice operator (up to 20 minutes).

Real world FMs. As stated early, automated extraction techniques now produce very large FMs from existing software systems. We applied our technique to three independent systems relating to the operating system domain (Linux, eCos, and FreeBSD). Linux and eCos have FMs whereas FreeBSD has not. She et al. reverse engineer the propositional formula of FreeBSD and develop techniques to interactively specify the hierarchy [START_REF] She | Reverse engineering feature models[END_REF]. For the experiment, we directly applied the slicing technique on the formula of FreeBSD. It should be noted that, in this specific case, we cannot use the heuristic mentioned above since we do not have access to the hierarchy of FreeBSD. We randomly generated the order in which features are existentially quantified. The technique succeeded almost instantaneously (FreeBSD has 1203 features). We also succeeded on eCos that has over 1200 features.

Finally, we applied our technique to the FM of Linux which exhibits 6300 features. Contrary to the results obtained from the two other operating systems or from the experimental study described above, we scaled only for less than 60% of features included in the slicing criterion (whereas this percentage drops to 1% in the other cases). In order to understand the reasons of this limitation, we need to compare the experimental conditions of the generated FMs with the properties of the Linux FM. The Linux model contains very small percentages of mandatory features (5%), grouped features (3%) -Linux features are mostly optional (92%). whereas in each generated model, each type of mandatory, optional, Xor and Or-groups was added with equal probability (25%). We can make the assumption that the slice operator is dependent on certain shapes of FMs, and/or certain kinds of constraints. We need to understand the impact of FM properties regarding the scalability of the slice operator. As future work, we plan to characterize more precisely the lack of scalability w.r.t. the Linux FM and develop new heuristics or specific techniques.

Comparison with Other Solutions

We now review existing approaches that have been developed to support SoC in FMs. We point out their relations to the SoC techniques that have been identified (see Figure 4) and illustrated by different case studies in Section 4. To this end, we rely on the numbers used in Figure 3, each corresponding to a case study. The general conclusion is that without the new capabilities brought by our solution (i.e., the combined use of composition and decomposition operators), some analysis and reasoning operations would not be made possible in the different case studies.

Composition. A few works consider some forms of composition for FMs and suggest the use of a merge operator [START_REF] Alves | Refactoring product lines[END_REF][START_REF] Hartmann | Using feature diagrams with context variability to model multiple product lines for software supply chains[END_REF][START_REF] Schobbens | Generic semantics of feature diagrams[END_REF][START_REF] Segura | Automated merging of feature models using graph transformations[END_REF]]. An in-depth comparison of implementation approaches is performed in [START_REF] Acher | Comparing approaches to implement feature model composition[END_REF]. Our proposal goes further since we clarified the semantics of the merge and showed that the merge alone is not sufficient to realize complex management tasks in the case studies and . It rather has to be combined with decomposition and reasoning mechanisms. Several approaches use several and interrelated FMs and views [START_REF] Hartmann | Using feature diagrams with context variability to model multiple product lines for software supply chains[END_REF][START_REF] Kang | Form: A feature-oriented reuse method with domain-specific reference architectures[END_REF][START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF][START_REF] Reiser | Multi-level feature trees: A pragmatic approach to managing highly complex product families[END_REF][START_REF] Tun | Relating requirements and feature configurations: A systematic approach[END_REF]. As shown, the aggregate operator combined with the slice can be used in such contexts to update the different views, to support multiple perspectives or to reason about properties of the FMs (see case studies , , and ). In [START_REF] Sanen | Mapping problem-space to solution-space features: a feature interaction approach[END_REF], the authors tackled the problem of mapping problem-space features into solutionspace features and proposed to use default logic. Our contributions rely on propositional logics and therefore are not applicable to this work. Thompson et al. proposed to specify a product family from n perspectives: one family-hierarchy per view such as software or hardware [START_REF] Thompson | Structuring product family requirements for n-dimensional and hierarchical product lines[END_REF]. It is a form of SoC that is particularly needed in the case studies or . A set-theoretic foundation is proposed: it can be expressed and realized using FMs and the presented techniques.

Decomposition. Thüm et al. [START_REF] Thüm | Reasoning about edits to feature models[END_REF] presented an automated and scalable technique to characterize the kinds of edit between two FMs. An original property of the technique is that they distinguish abstract features from concrete features when reasoning. Abstract features are, in their work, nonleaf features. We consider this is the role of an SPL practitioner to explicitly determine which features are abstract (as shown in the example of Section 4.3, abstract features are not necessary non-leaf features). Our technique is thus more general and realize the vision of [START_REF] Schobbens | Generic semantics of feature diagrams[END_REF] that makes the distinction between features that are of interest per se (i.e., that will influence the final product) and others. As we have shown, reasoning about the relationship of two FMs (and thus using the comparison operator developed in [START_REF] Thüm | Reasoning about edits to feature models[END_REF]) is inappropriate until FMs are not reconciled (see case studies and ). From our experience, tool supported techniques, such as the safe removal of a feature by slicing, are not desirable but mandatory (i.e., basic manual edits of FMs are not sufficient) in this context. Recently, Thüm et al. [START_REF] Thüm | Abstract features in feature modeling[END_REF] extend the work described in [START_REF] Thüm | Reasoning about edits to feature models[END_REF] and propose to make abstract features explicit in FMs. They show how a propositional formula can be retrieved describing the set of distinct "program variants", corresponding to combination of concrete features. Interestingly, Thüm et al. plan to apply their techniques to SPL testing. We see this work as an application of the slicing technique where all features but abstract features are part of the slicing criterion. Our technique for computing the propositional formula is similar to the technique described in [START_REF] Thüm | Abstract features in feature modeling[END_REF]. In addition we developed an heuristic that determines the order in which the features are existentially quantified. We also applied to very large FMs and reported scalability results. In the context of feature-based configuration, techniques have been proposed to separate the configuration process in different steps or stages [START_REF] Czarnecki | Staged configuration through specialization and multilevel configuration of feature models[END_REF]. Our work is complementary since we propose techniques to decompose FMs. Hubaux et al. provide view mechanisms decompose a large FM [START_REF] Hubaux | Supporting multiple perspectives in feature-based configuration[END_REF]. However they do not propose a comprehensive solution when dealing with cross-tree constraints. Furthermore we have shown that the decomposition of FMs has several other interesting applications beyond the support of multiple perspectives (see case studies , , and ). Benavides et al. survey the literature of automated reasoning about FMs [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF]. To the best of our knowledge, there is no existing work for correcting anomalies in FMs. Furthermore, existing approaches mentioned in [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF] and discussed above either focus on composition or decomposition, but they do not try to combine the two mechanisms for supporting SoC in feature modeling. The "tyranny of the dominant decomposition" is a general issue for aspect-oriented approaches [START_REF] Tarr | N degrees of separation: multi-dimensional separation of concerns[END_REF]. In [START_REF] Batory | Refinements and multidimensional separation of concerns[END_REF], Batory et al. introduced multi-dimensional SoC where a dimension is a set of features addressing a particular concern. We can see a dimension as a slicing criterion. The approach of Batory et al. does not generate views but rather composes features along each dimension. It is thus complementary and can be used to produce parts of a system, being services (case study ), components (case study ) or plugins (case study ). Rosenmüller et al. develop compositional support to manage different FMs, each focusing on a specific dimension [START_REF] Rosenmüller | Multidimensional variability modeling[END_REF]. They do not consider composition of FMs that introduce anomalies and do not propose automated decomposition (as needed in all case studies).

Threats to Validity

Threats to external validity are conditions that limit our ability to generalize the results of our operators and experiment to industrial practice. Our first concern is whether generated FMs or Linux FM used in the experiments (see Section 5) are representative of industrial usage. Our second concern is whether the composition and decomposition operators are expressive and intuitive enough to support activities of SPL practitioners. As summarized by Figure 4 and Figure 3, the operators have been applied to different domains for different purposes and by different people (external to our team). Moreover we identify several works in the literature that can benefit from the techniques (see Section 6).

A first internal threat concerns the correctness of the operators implementation. In particular, the slice operator is supposed to guarantee that some semantic properties are preserved. Our implementation is currently checked by a comprehensive set of unit tests, complemented by cross-checked testing with other operations. For instance, we compared the formulas produced by the BDD-based and SAT-based implementation of the slice operator. We also manually verified a large number of slice examples. Besides we observed that randomly generated FMs may contain a lot of anomalies (e.g., dead features or wrong feature group). We used this opportunity to gain further confidence in our implementation and applied our slicing technique to automatically correct anomalies in generated FMs (see Section 4.1). We automatically checked that the original FM and the slice (i.e., corrected) FM were equivalent in terms of sets of configurations, that the slice FM did not contain any anomaly, and that the hierarchy conforms to the original FM.

Conclusion

In this paper, we described how a set of complementary operators (aggregate, merge, slice) can be used to provide a powerful support for SoC in feature modeling. We showed how the operators can assist in tedious and error prone tasks such as automated correction of FM anomalies, update and extraction of FM views, reconciliation of FMs or reasoning about properties of FMs. The operators bring new capabilities to the FM users for supporting SoC in feature modeling and when we revisited and reimplemented existing approaches with them, we observed a better scalability. Both these new capabilities and scalability results enabled us to apply SoC in feature modeling to different domains (medical imaging, video surveillance) and for different purposes (scientific workflow design, variability modeling of context and software platform, reverse engineering). We also developed a technique to implement the slice operator that scales up to FMs with 10000 features in certain conditions. As future work, we plan to study practical usage and applicability of the proposed techniques.

  FM: FODA-like representation f m1 = { {A, B, C, D, E, P, R, T, U, W }, {A, B, C, F, P, S, T, U, W }, {A, B, C, D, E, P, R, T, W }, {A, B, C, F, P, S, T, V, W }, {A, B, C, F, P, S, T, U, V, W }, {A, B, C, F, P, S, T, W }, {A, B, C, D, E, P, R, T, V, W }, {A, B, C, D, E, P, R, T, U, V, W } } (b) corresponding set of configurations

Figure 1 .

 1 Figure1. FM, set of configurations and propositional logic encoding gate. It may lead to situations where the aggregated FM does not represent any valid configuration or includes dead or core features (see Definition 2). We consider that the aggregate operator is purely syntactical. As we will see, other complementary techniques can be applied in case an SPL practitioner may want to simplify the aggregated FM or to reason about its properties.

Figure 4 .

 4 Figure 4. SoC in feature modeling

Figure 6 .

 6 Figure 6. Updating FM views

Figure 5 .

 5 Figure 5. Variability and concerns within a medical imaging service and fmViewSecurity. The slicing criterion used to compute fmViewMI (resp. fmViewSecurity) contains features from the FMs F M M I , F M algo and F M grid (resp. F M M I , F M proto and F M grid ). The slice guarantees that all the interactions existing with other FM views are still enforced.

Figure 7 .

 7 Figure 7. Another decomposition strategy and set of FM views

Figure 8 .

 8 Figure 8. Slicing () to reconcile FMs and allow, e.g., comparison or merging ()

6 ;

 6 Figure 3. SoC in the case studies

	Technique		Description	Operators	Application
	Updating FM Views	several FM views are inter-related: The variability information is	aggregate,
			kept up-to-date in the different views, possibly by correcting some	slice
			anomalies introduced by some constraints
	Supporting Multiple
	Perspectives
				slice, merge
	Reasoning	about	two FMs describing two variability concerns are inter-related:	aggregate,
	Two Kinds of Vari-	Reasoning techniques are applied to reason about their relation-	slice, merge,
	ability		ships

given an FM or a set of FMs, a stakeholder wants to focus only on a specific concern related to its expertises, role, task aggregate, slice Reconciling FMs two (or more than two) FMs cannot be directly compared or merged: They are reconciled by removing unnecessary details

  Intuitively, if the restriction of the PL features to f m G is equivalent to the original f m P L , the constraints map Sof tP L has no effect on the PL part of f m G and thus the realizability property holds. Otherwise some products cannot be realized in the platform. Equation 1 implies to check if f m P L is a refactoring (see Definition 3) of Π F P L (f m

	fmSoftware
			r	Online Store
	f1	Debit Card Payment	Upon Voice Payment f2	f3	Payment Credit Card	Credit History Check of f4	V1 ó f1
								V2 ó f2
		fmPL						V3 ó f3
			VP1	Online Store
	V1	Debit Card Payment	Upon Voice Payment V2	V3	History Check of Credit
				V2 => V3
	Figure 9. Software and PL Variability (adapted from [22])
								7	2012/3/2

G ). Using the aggregate, slice and merge diff operators, we can automatically check this property. First, we slice the aggregated FM f m G by only including F P L , the set of features of f m P L . The slice produces a new FM, denoted f m P L P rime . Formally:

2012/3/2

The tooling and language support, FAMILIAR, is out of the scope of this paper. The interested reader can visit https://nyx.unice.fr/ projects/familiar/

2012/3/2

2012/3/2

2012/3/2

Janota et al. reported that the BDD-based algorithm proposed in[START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF] scales up only for FMs with 300/400 features[START_REF] Janota | Model construction with external constraints: An interactive journey from semantics to syntax[END_REF], but did not use the heuristics proposed in[START_REF] Mendonca | Efficient compilation techniques for large scale feature models[END_REF]

2012/3/2

2012/3/2

Acknowledgments. Dr. Acher's work is supported by the IAP Programme, the Belgian Science Policy under the MoVES project, the FNRS, and an FSR grant, co-funded by Marie-Curie actions of the European Commission. 11 2012/3/2


Sébastien Glaser

Maurice Cour

Lydie Nouveliere

Alain Lambert

Fawzi Nashashibi

Jean-Christophe Popieul

Benjamin Mourllion

Low Speed Automation, a French Initiative

Keywords: vehicle automation, shared control, environment sensing, data fusion ;"

Nowadays, vehicle safety is constantly increasing thanks to the improvement of vehicle passive and active safety. However, on a daily usage of the car, traffic jams remains a problem. With limited space for road infrastructure, automation of the driving task on specific situation seems to be a possible solution. The French project ABV, which stands for low speed automation, tries to demonstrate the feasibility of the concept and to prove the benefits. In this article, we describe the scientific background of the project and expected outputs.

Introduction

Vehicle safety and Traffic jams are recurring problems in all the major cities. The improvement of vehicle passive and active safety, of the infrastructure design and of driver behavior, makes it possible to reach very low number of car fatalities. Several driving assistances enhance the controllability of the vehicle as anti-lock brake system (ABS), electronic stability program (ESP) … can support the driver as Adaptive Cruise Control (ACC) and even can decide to brake in front of an obstacle that is not avoidable in the case of a collision mitigation brake system. However, even with improved public transportation systems, the traffic jams problem remains and increases because of an increased daily traveling, of a need of mobility… Previous works show that, with a limited space to increase the road possibility, the automation of the vehicle could be a solution. Several experiences were driven in the US, in Japan and in European countries during the 90's and in the beginning of 2000. They prove that the full automation is possible but at an expensive price. During the past five years, several challenges, as DARPA challenges, confirm the possibility of the automation. Automates are able to drive on road that ranges from highway to urban area. Moreover, recent developments in the automotive sensors, actuators and micro controllers, make the automation possible at a reasonable price. On recent cars, where driving assistances are available, plenty of sensors can detect objects in the surrounding, and controllable actuators are available at serial production level. But, some actuators, especially related with the steering column, are not usual as they are strongly limited by current legal issue.

However, the developed applications miss the link with the driver. They are mostly automates that take or not the control of the car. The relation with the driver is limited. European projects as SPARC (SPARC 2002) try to develop safe architecture to allow a fine tuning of the control between the driver and the driving assistance. More recently, the HAVEit project (HAVEit 2008) has developed a copilot architecture that is able to monitor the driving task and to interact with him to initiate the control by an automate. The French project PARTAGE (PARTAGE 2009) studies several scenarios to share the control between a driving assistance and the driver, from the warning to the full automation to provide a full scale of interaction.

In ABV, Low Speed Automation, a French initiative, we focus on the problem of traffic jam in urban area and we try to provide a solution for ring road, or interurban freeway under mixed traffic condition. We define a vehicle that is able to handle partly or totally the driving task on a secured road but taking into account interactions with others vehicles:

• Automation: The system will provide up to a full control of the driving task, managing also the transition between the driver and the automation. • Low speed: the full automation of the vehicle will only be available up to 50km/h. For a speed higher than 50km/h, the driver is still assisted but only for the longitudinal mode, providing functions like an ACC • Secured Road: a secured road is not a road available only for 'ABV' vehicles; the road allows a shared driving space between automated vehicle and normal vehicle. A secured road provides a high quality of services, as a good road marking, knowledge of the infrastructure geometry… To allow the shared control, the project uses copilot architecture in interaction with the driver and also monitors him to interact during transition phases (between the driver and the copilot).

ABV project is structured along three main tasks:

• Scientific development: it gathers the development of the perception, the path planning, the control and the cooperation between the human and the machine, • Integration in the vehicle: it aims at developing the specification and the architecture of the vehicle, at the evaluation of the modules before the integration and finally at the integration within two demonstrators, • Societal aspect: in order to evaluate the impact of the project at a larger scale than the vehicle and also to determine the legal evolution. ABV gathers 10 French partners with equipment supplier and large industry, sme, research units and university. The project starts two years ago and we present here the first results. We present here the first results.

After defining the basic scenario, we focus on the perception, data fusion and control of the vehicle in interaction with the driver. Two prototypes are developed and they allow this interaction based on bywire architecture. Moreover, the project also studies the impact on the traffic flow, on global consumption and the constraints in term of legal aspect.

Scenarios for ABV

In the frame of ABV, we make the following distinction for the available functions:

• Speed: a threshold on the speed is set at 50km/h. Below 50km/h the ABV functions could be fully available. For a speed higher than 50km/h, the driver is assisted only for the longitudinal mode.

• Road: if the road is a secured road, then the ABV functions could be fully available. On normal road, depending on the speed, the drivers could be assisted on longitudinal mode. The threshold on speed is set at 50km/h mainly for sensing purpose: from previous experience (DO30 and LOVE projects), we can ensure the obstacle detection using a camera based system up to 40m in front of the vehicle. At 50km/h, this distance allows a reaction time greater than 2s. The system can then safely warn the driver and/or decides on appropriate reaction within this time. Moreover, without any reaction from the driver, we can fully stop the vehicle.

Scenarios

From the previous limitation, we have defined six different behaviors for the ABV systems which are presented on the Figure 1.

These basic behaviors can be described as:

• "Driver" in this mode, the driver fully controls the vehicle • "Longi ADAS" mode is available both on secured road and on non secured road. In this mode, the system supports the driver for the longitudinal decision. • "Full system" mode is available only on Secured Road. The driver can fully delegate the control of the vehicle to the system. This mode is only available if the speed is below 50km/h. • "Emergency" mode aims at stopping the vehicle in a safe state if a failure is detected. On non secured road, the aim is to stop the vehicle on the lane, on secured road, the system tries to stop the vehicle on the emergency lane. Each mode can be disengaged by the driver and the driver, on Secured Road, can be proposed by the driving assistance to engage the system. The "Emergency" mode can be triggered autonomously. For instance, if the system is on "Full System" mode, and that the Secured Road ends, the driver will be asked to take the control back. If the monitoring system does not recognize any reaction from the driver, then the system switches to the "Emergency" mode.

From scenarios to architecture and functions

From the previous scenarios, the functions that must be achieved by the vehicle are the following ones:

•

Secured Road Concept

As in the SMART final report (SMART 2011), we clearly think that the vehicle alone cannot achieve a level of reliability that is sufficient to allow autonomous system on open road. These systems will need cooperation with, at least, the infrastructure and the other vehicles. This is the concept of a "Secured Road".

A "Secured Road" is a road that accepts mixed traffic: both ABV vehicles and conventional vehicles. This infrastructure primarily aims at easing the understanding of the environment. According to the described architecture, the sensing functions have to detect the road and the obstacle. The infrastructure can help in these two cases. For the road, the infrastructure may ensure that the road marks and the police sign could be easily detected (i.e. not deteriorated) or that an accurate local map is available for the vehicle with the data from the road and static objects. For the obstacle, even if solutions to detect obstacles from the infrastructure are available (i.e. laserscanners and V2I communication), the price may limit the development. However, it is interesting to have sensing capacities where a lot of interaction may occur, as in intersection.

Moreover a "Secured Road" is also able to supervise its use. Gathering information from vehicles and also static sensors, the infrastructure is able to have a global overview of its current status and distribute specific recommendation, as speed limit or dedicated trip to ABV vehicles in order to optimize the traffic.

Sensing the environment

This is the first functions block. It aims at providing a map of the surrounding of the vehicle. Both lanes and obstacle must be known. Multi-Lane detection is done using multi cameras architecture [START_REF] Pollard | /Road Marking Extraction with Combination Strategy and Comparative. Evaluation on Synthetic and Actual Images[END_REF]. Moreover, the road specific elements as arrows or pedestrian ways are detected in order to locally modify the behavior of the others functions as path planning and vehicle control. Some results are presented in the Figure 3. The object detection is actually done using fusion between laserscanner and camera [START_REF] Labayrade | Obstacle Detection in Outdoor Environments Based on Fusion Between Stereovision and Laser Scanner[END_REF][START_REF] Labayrade | Sensor Data Fusion for Road Obstacle Detection[END_REF].

Generating a set of trajectories

The core concept of the trajectory generation is that the vehicle must obey to the Vienna convention. Moreover, we make the assumption that the other drivers do not any actions that can endanger the surrounding vehicle [START_REF] Vanholme | A legal safety concept for highly Automated driving on highways[END_REF]. Then, the generation of the trajectories is done using several competitive methods:

• Polynomial trajectory definition under constraint (S. Glaser 2010). This method is fast and reliable. It is already implemented under simulator and also on car.. This method was partly developed during the HAVEit project. The Figure 4 shows what are the considered trajectories for the other vehicles while defining the ego vehicle trajectory) • Geometric with uncertainty and Bayesian approach with uncertainty are currently under development.

Controlling the vehicle

Once the environment sensed, and the trajectory generated, the control module aims at providing the motion vector (in term of steering angle and speed, see Figure 5) and also to optimize the consumption of the vehicle while following the trajectory (Nouveliere 2011).

The minimum risk state (emergency control while on "Secured Road") and the emergency trajectory are continuously evaluated. In order to ensure a good understanding from the driver, and a possible sharing of the control between the driver and the automate, we have specifically addressed this topic in the project. The steering wheel and column are transformed to be by-wire, and the driver feedback is defined to allow a safe feeling [START_REF] Sentouh | Toward a Shared Lateral Control Between Driver and Steering Assist Controller[END_REF], Soualmi 2010, Sentouh 2011). The main idea is that the driver feels a self aligning torque that brings the vehicle softly back to the trajectory when the control is shared. However, he can override the command and the torque is maintained at small values. The steering column is not the only way to share the control with the driver; the acceleration pedal is also designed to be able to generate a feedback to the driver. This modality is not yet explored. The Figure 6 presents these interfaces. Moreover, the driver is monitored to ensure that he is able to take the control back and that he is aware of the situation. The work is actually done under a simulator (Figure 7).

Cooperation between man and machine

Societal aspect

Beyond the technical aspects, the project also aims at evaluation the impact on societal aspect. On this part, the project aims at:

• Studying what are the legal limitations that forbid full autonomous systems on open road and design possible evolution, both on the system and on the legal aspect. • Evaluating the impact of the system on the traffic with a scaled introduction of the system in the traffic. Especially for this last part, the objectives are to evaluate the impact not only on the mobility, but also on the safety and on the consumption. For this last criterion, the model will be developed in collaboration with the control part of the project.

Conclusion and perspectives

In this paper, we have presented the structure and the first results of the ABV project. This project aims at proposing a solution that enhances both safety and mobility by developing two demonstrators of cars that are able to share the control between the driver and the automation up to the full automation on a "Secured Road" when traffic jams occur. The project aims at developing integrated demonstrators that promote the autonomous driving.

Moreover, we not only study the autonomous vehicle, but all the possible transitions that ranger from warning to highly assisted.

The main objective is to bring a solution on highway and urban road that are prone to traffic jams, by developing the concept of "Secrued Road", a road that provides a high quality of services and that allow and help the automation in the detection and understanding phases.

The project will end at the beginning of 2013, we are currently integrating and evaluating the functions.

  Perception and Data Fusion: Positioning of the vehicle, lane detection, • Path Planning • Driver Monitoring • Human Machine Interface • Vehicle control The architecture is summarized in the Figure 2.

Figure 1

 1 Figure 1 Behavior of the ABV system

Figure 2

 2 Figure 2 Description of the architecture

Figure 3

 3 Figure 3 Road detection

Figure 5

 5 Figure 5 Generation of the commands. Two trajectory and command associated are continuously evaluated : Minimum Risk State (MRS) and emergency

Figure 6

 6 Figure 6 By wire Steering wheel and active pedal

Acknowledgements

The authors would like to thanks the French National Research Agency (ANR) to fund the ABV project and allowing this research. ABV project leader is IFSTTAR and partnership includes : CONTINENTAL Automotive France, IBISC -UEVE, GM Conseil, IEF, INDUCT, INRIA, LAMIH, VIAMETRIS, MIPS and VERI.