# «Using Java CSP Solvers in the Automated Analyses of Feature Models ⋆ David Benavides, Sergio Segura, Pablo Trinidad, and Antonio Ruiz-Cort´ s e ...»

GTTSE 2005

Using Java CSP Solvers in the Automated Analyses of

Feature Models ⋆

David Benavides, Sergio Segura, Pablo Trinidad, and Antonio Ruiz-Cort´ s

e

Dpto. de Lenguajes y Sistemas Inform´ ticos

a

University of Seville

Av. de la Reina Mercedes S/N, 41012 Seville, Spain

{benavides, sergio, trinidad, aruiz}@tdg.lsi.us.es

**Abstract**

Feature Models are used in different stages of software development

and are recognized to be an important asset in model transformation techniques

and software product line development. The automated analysis of feature mod- els is being recognized as one of the key challenges for automated software de- velopment in the context of Software Product Lines. In our previous work we explained how a feature model can be transformed into a constraint satisfaction problem. However cardinalities were not considered. In this paper we present how a cardinality-based feature model can be also translated into a constraint satisfaction problem. In that connection, it is possible to use off-the-shelf tools to automatically accomplish several tasks such as calculating the number of possible feature conﬁgurations and detecting possible conﬂicts. In addition, we present a performance test between two off-the-shelf Java constraint solvers. To the best of our knowledge, this is the ﬁrst time a performance test is presented using solvers for feature modelling proposes 1 Introduction Throughout the years, software reuse and quality have been two constants aims in soft- ware development. Although signiﬁcant progress has been made in programming lan- guages, methodologies and so forth, the problem seems to remain. Software Product Line (SPL) development [8] is an approach to develop software systems in a system- atic way that intends to solve these problems. Roughly speaking, an SPL can be de- ﬁned as a set of software products that share a common set of features. Therefore, an SPL approach could be useful for organizations that are product–oriented rather than project–oriented [7]. That is, organizations that operate in a particular market segment.

SPL engineering consists of two main activities: domain engineering (also called core asset development) and application engineering (also called product development).

These two activities are complementary and provide feedback to each other. Domain engineering deals with core assets production, that is, the pieces of the products to be shared by all SPL products. On the other hand, application engineering deals with individual system production.

⋆ This work was partially supported by the Spanish Science and Education Ministry (MEC) under contracts TIC2003-02737-C02-01 (AgilWeb) Feature Analysis [17] is an important task of domain engineering and is expected to produce a Feature Model (FM) as its main output. A FM can be deﬁned as a compact representation of all possible products of an SPL. Furthermore, it is commonly accepted that FMs can be used in different stages of an SPL effort in order to produce other assets such as requirements documents [15,16], portlets–based applications [11,12] or even pieces of code [3,9,20]. Hence, FM becomes an important focus of research in the ﬁeld of model transformation.

Automated analyses of FMs are an important challenge in SPL [1,2]. In a previous work [4,5] we presented how to transform a FM (without considering cardinalities) into a Constraint Satisfaction Problem (CSP). In that way, it is possible to use off–the– shelf constraint satisfaction solvers to automatically accomplish several tasks such as calculating the number of possible conﬁgurations and detecting possible conﬂicts. The contribution of this paper is twofold: i) to explain how a FM with cardinalities can be translated into a CSP and ii) to show the result of a performance test between two off the shelf Java constraint solvers: JaCoP and Choco. To the best of our knowledge, this is the ﬁrst test that measures the performance of constraint solvers in the context of feature analyses.

The remainder of the paper is structured as follows: in Section 2 we introduce feature models. In Section 3 constraint programming is outlined and details on how to translate a FM into a CSP are presented. Section 4 focuses on the results of the experiment. Finally we summarize our conclusions and describe our future work in Section 5.

**2 Feature Models**

A Feature Model (FM) is a compact representation of all possible products of an SPL.

FMs are used to model a set of software systems in terms of features and relations among them. Designing a software system in terms of features is more natural than doing it in terms of objects or classes. Consequently, a software system will be composed of a set of features.

Since FMs were ﬁrst presented in 1990 [17] there have been many publications and proposals to extend, improve and modify the original FM diagram. However, despite years of research, there is no consensus on a FM notation. Although it would be desirable to have a common notation, it is out of the scope of this paper to give yet another FM notation. Therefore, we use the one proposed by Czarnecki [10] that was formalized as a context free grammar and integrates some previous extensions.

A FM is basically a tree structure with dependencies between features. Figure 1 represents the general metamodel of a FM (this metamodel was presented in [6]). Likewise, Figure 2 represents a FM of the James Project [13]. James is a collaborative web based system that we modeled in terms of features and can be a clear example of an SPL.

Some products can be derived from the FM on Figure 2. Having a web service interface (WSInterface) is optional while it is mandatory to have user management (UserManagement), at least one module (Modules) and the core of the system (Core).

1 0..* Root FeatureModel Constraint

A FM is composed of a root (JAM ES in Figure 2) and an optional set of constraints (they refer to global constraints: depends and excludes; R9 and R10 in Figure 2).

A root is composed of an optional set of relations. Relations can be of two different types: binary relations which include mandatory (e.g. R1), optional (e.g. R2) and cardinality–based relations (e.g. R4) or set relations (e.g.R7).

A feature can be of two different types and is composed of zero or more relations. A binary relation is composed of one and only one solitary feature which is the child feature since the parent feature is the one that has this relation (Core or U serM anagement are examples of solitary features); A set relation is composed of at least two grouped features (Calendar,DB or P DA are examples of grouped features). In addition, a solitary feature and set relations comprise one or more cardinalities. Note that in the graphical representation it is possible not to represent a cardinality in set relations although in fact that means that the cardinality is 1-1. Likewise, there are graphical representations for commonly used cardinalities of solitary features like [1..1] and [0..1] (see Figure 2 notes).

3 Constraint Programming

that to solve a given problem by means of constraint programming, ﬁrst the problem has to be formulated as a CSP.

A CSP consist of a set of variables, domains for those variables and a set of constraints restricting the values of the variables.

Deﬁnition 1 (CSP). A CSP is a three–tuple of the form (V, D, C) where V = ∅ is a ﬁnite set of variables, D = ∅ is a ﬁnite set of domains (one for each variable) and C is a constraint deﬁned on V.

Once the problem is stated as a CSP, it is possible to use off–the-shelf CSP solvers that are able to provide the solutions to the problem. Internally the solvers will be implemented by using algorithms and heuristics that have been and are being investigated during several decades.

3.1 Mapping a FM into a CSP We presented in [4,5] how a FM with dependencies was translated into a CSP. However we did not provide a way to do the same with cardinality–based FMs [10]. In this Section we give details on how to transform a FM with cardinalities into a CSP which is a novel contribution.

Rules for translating FMs to constraints are listed in Figure 3. First, there is a variable for each feature in the CSP. The domain of each variable depends on the cardinality associated to each variable. By default the domain is {0,1} and if a feature is part of a cardinality relation, then the domain of the variable is added (e.g. Core ∈ {0, 4} in Figure 2). Then, a constraint selecting the root feature is added because all products have the root feature (e.g. root = 1). The ﬁnal CSP for a FM is the conjunction of the constraints following the rules of Figure 3.

validating a given FM to detect possible inconsistences, ﬁnding an optimum product on the basis of a given criteria (the cheapest, the one with fewest features and so forth) or calculating the commonality factor for a given feature and the variability factor of a given FM.

The main ideas concerning the use of constraint programming on FM analyses were stated in [4,5] but some experimental results were left for our future work. In this Section we present an experimental comparison of two Java CSP solvers that were used to automatically analyse FMs.

**4.1 The JaCoP and Choco Solvers**

There are several commercial tools to work with CSPs. One of the major commercial vendors is ILOG that has two versions of CSP Solvers in C++ and Java. Because it is a commercial solution, we declined to use ILOG solvers’ licenses in our empirical comparison.

To the best of our knowledge there is only one reliable and stable open source Java CSP Solver : Choco Constraint System [19]. We selected this solver because it seems to be one of the most popular within the research community and because it is the only one we know of that is available for free directly from the Internet. We selected JaCoP solver [18] because it offers a free license for academic purposes. Both solvers have similar characteristic in terms of the variables and constraints allowed, therefore the implementation of our mapping was done in a straightforward manner. For JaCoP we used FDV variables (FDV stands for Finite Domain Variables) to represent the features while IntVar variables were used in the Choco implementation.

**4.2 The Experiments**

With the following experiments we intend to demonstrate which solver provides the best performance in the automated analyses of FMs. In addition, we studied the robustness and the areas of vulnerability of each solver. In order to evaluate both solvers we used ﬁve FMs. Three of them represent small and medium size real systems, meanwhile the larger two were generated randomly for this experiment. After formulating each one as a CSP in both platforms, we proceeded with the execution. Table 1 summarizes the characteristics of the experiments. Experiment 1 is the FM that was presented in [4].

It is a simple FM representing a Home Integration System. Experiment 2 is the FM of Figure 2 which represents a collaborative web based system. Experiment 3 is a medium size FM of a ﬂight booking system based on the work done by [11,12]. Finally, we generated two larger FMs randomly (Experiments 4 and 5) with a double aim: representing more complex systems with a greater number of features and dependencies, and evaluating the solvers’ performance in limit situations. We considered it was necessary to compare the performance with small, medium and large FMs in order to evaluate solver performance results in different situations.

The process to generate a FM randomly is based on a recursive method that has ﬁve input parameters: height levels, maximum number of children relations for a node, maximum cardinality number, maximum number of elements in a set relation and number of dependencies. Firstly, features and their relations are generated using random values.

Secondly, the dependencies are created by taking pairs of features randomly and establishing a random dependency (includes or excludes) between them. We took care not to generate misconceptions (e.g. a child depends on a parent).

As exposed in [5], there are some operations that can be performed. For our experiments we performed two operations: i) ﬁnding one conﬁguration that would satisfy all the constraints, that is, a product and ii) ﬁnding the total number of conﬁgurations of a given FM. The ﬁrst is the simplest operation while the second is the most difﬁcult one in terms of performance because it is necessary to retrieve all possible combinations.

The comparison focused on the data obtained from several executions in order to avoid as much exogenous interferences as possible. The total number of executions to

**calculate the average time was ten. The data extracted from the tests was:**

– Number of features in the ﬁrst solution obtained by solver.

– Average execution time to obtain one solution (measured in milliseconds).

– Total number of solutions, that is, the potential number of products represented in the FM.

– Average execution time to obtain the number of solutions (measured in milliseconds).

In order to evaluate the implementation, we measured its performance and effectiveness. We implemented the solution using Java 1.5.0 04. We ran our tests on a WINDOWS XP PROFESSIONAL machine equipped with a 3.2Ghz Intel Pentium IV microprocessor and 1024 MB of DDR 166Mhz RAM memory.

4.3 The Results

Choco such as the number of backtracks of a search or the number of decisions taken to ﬁnd a solution. In second place, we found a worrying bug when working with big problems in Choco. In most cases, executions of CSPs representing big FMs generated an exception (choco.bool.BinConjunction) which imposes an important limitation to Choco.

5 Conclusion and Future Work