FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 |

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

-- [ Page 1 ] --

GTTSE 2005

Using Java CSP Solvers in the Automated Analyses of

Feature Models ⋆

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


Dpto. de Lenguajes y Sistemas Inform´ ticos


University of Seville

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

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


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 configurations and detecting possible conflicts. In addition, we present a performance test between two off-the-shelf Java constraint solvers. To the best of our knowledge, this is the first 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 significant 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- fined 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 defined 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 field 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 configurations and detecting possible conflicts. 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 first 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 first 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, first 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.

Definition 1 (CSP). A CSP is a three–tuple of the form (V, D, C) where V = ∅ is a finite set of variables, D = ∅ is a finite set of domains (one for each variable) and C is a constraint defined 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 final CSP for a FM is the conjunction of the constraints following the rules of Figure 3.

–  –  –

validating a given FM to detect possible inconsistences, finding 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 five 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 flight 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 five 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) finding one configuration that would satisfy all the constraints, that is, a product and ii) finding the total number of configurations of a given FM. The first is the simplest operation while the second is the most difficult 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 first 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 find 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

Pages:   || 2 |

Similar works:

«Department of Chemical and Biomolecular Engineering November, 2008 The mission of the Department is to provide the highest quality programs to educate students in the principles and applications of Chemical and Biomolecular Eengineering. The excellence of the program is ensured by the high regard for teaching, strong research activities and solid industrial ties. The program educates students to take leadership roles in industry, academia and government. The Graduate Program The Department of...»

«THE BULLETIN I 02 10 TH ULEI NEW ABSORBABLE HEMOSTATIC AGENTS* VIRGINIA KNEELAND FRANTZ Department of Surgery, College of Physicians and Surgeons, Columbia University, New York 2ITH the end of combat in World War II the new hemostatic agents developed in various research laboratories, developed under the pressure of the emergency, were almost ready for general surgical use. The preliminary 5isesesas~srsW experimental work had been done, clinical investigation had confirmed the laboratory...»

«Contract reference no.: ALA/95/21-B7-3010/37 Beneficiaries: LALITPUR SUB-METROPOLITAN CITY and KHOKANA VILLAGE DEVELOPMENT COMMITTEE Contractor: City of Chester Periodic Report 15 January 2002 – 14 January 2004 Urban Management and Economic Diversification Project Contents Abbreviations 1. Technical section (a) Project Particulars (b) Summary (c) Working conditions (d) Reporting Tables Table 4 Activity 1 Institutional development Activity 2 Orientation/training Seminar at Chester Activity 3...»

«ABOUT THE MECHANISM OF THE HAIL FORMATION Ismailov Sokhrab Akhmedovic Doctor. chem. Sciences, Senior Researcher, Institute of Petrochemical Processes, Academy of Sciences of Azerbaijan, Baku, E-mail: sokhrab@yahoo.com Abstract: The new hypothesis about the building mechanism of hail showers is made under atmosphere conditions. It is suggested, contrary to other famous theories that hail showers building is stipulated by the generation of high temperature in lightning strike in atmosphere. Quick...»

«Installation Manual Frameworx Gutter and Capping August 2012 / 84-900030-000 Frameworx Gutter and Capping Installation Manual © August 2012 by the Brunswick Bowling and Billiards Corporation. All rights reserved. A-2, BallWall, Frameworx, GS-Series, Pinball Wizard, and Tel-E-foul, and are registered trademarks of the Brunswick Bowling and Billiards Corporation. Reorder Part No. 84-900030-000 Notice: If available, updates to this manual can be found on-line at www.centermaster.com. All...»

«Solar Glare Hazard Analysis Tool (SGHAT) Technical Reference Manual Clifford K. Ho, Cianan A. Sims, Julius Yellowhair, and Evan Bush Sandia National Laboratories (505) 844-2384, ckho@sandia.gov SAND2014-18360 O September 2014 Contents 1. Requirements 2. Introduction 3. Assumptions and Limitations 4. Determination of Glare Occurrence 4.1 Sun Position 4.2 Reflected Sun Vector 4.3 Scattering and Subtended Beam Angle 4.4 Beam Projection onto PV Array Plane 4.5 PV Single-Axis Tracking 4.6 PV...»

«THE BEST SOFTWARE WRITING I Selected and Introduced by Joel Spolsky The Best Software Writing I: Selected and Introduced by Joel Spolsky Copyright © 2005 Edited by Joel Spolsky All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. ISBN (pbk): 1-59059-500-9...»

«Knowledge Management & E-Learning: An International Journal, Vol.m, No.n. 1 Defamiliarization: Flarf, Conceptual Writing, and Using Flawed Software Tools as Creative Partners Richard P. Gabriel IBM Research 3636 Altamont Way, Redwood City CA 94062 E-mail: rpg@dreamsongs.com & rpg@us.ibm.com Abstract: One form of creativity uses defamiliarization, a mechanism that frees the brain from its rational shackles and permits the abducing brain to run free. Mistakes and flaws in several software tools...»

«UMTRI-2001-3 FIELD MEASUREMENTS OF DIRECT A N D REARVIEW-MIRROR GLARE FROM LOW-BEAM HEADLAMPS Michael Sivak Michael J. Flannagan Brandon Schoettle Yoshihiro Nakata January 2001 FIELD MEASUREMENTS OF DIRECT AND REARVIEW-MIRROR GLARE FROM LOW-BEAM HEADLAMPS Michael Sivak Michael J. Flannagan Brandon Schoettle Yoshihiro Nakata The University of Michigan Transportation Research Institute Ann Arbor, Michigan 48109-2150 U.S.A. Report No. UMTRI-2001-3 January 2001 Technical Report Documentation Page...»

«CHAPTER 1 NANO-CMOS SCALING PROBLEMS AND IMPLICATIONS 1.1 DESIGN METHODOLOGY IN THE NANO-CMOS ERA As process technology scales beyond 100-nm feature sizes, for functional and high-yielding silicon the traditional design approach needs to be modified to cope with the increased process variation, interconnect processing difficulties, and other newly exacerbated physical effects. The scaling of gate oxide (Figure 1.1) in the nano-CMOS regime results in a significant increase in gate direct...»

«POLITECNICO DI MILANO DEPARTMENT OF CHEMISTRY, MATERIALS AND CHEMICAL ENGINEERING “GIULIO NATTA” DOCTORAL PROGRAMME IN INDUSTRIAL CHEMISTRY AND CHEMICAL ENGINEERING AMINOAND GUANIDINOGLYCOSIDE-BASED VECTORS FOR GENE AND DRUG DELIVERY Doctoral Dissertation of: Aurora Sganappa I.D. 802585 Supervisor: Prof. Alessandro Volonterio The Chair of the Doctoral Program: Prof. Frassoldati Alessio 2012-2015 XXVIII Cycle “Every time you decide, there is a loss, no matter how you decide. It is always a...»

«Behaviour 152 (2015) 335–357 brill.com/beh Non-reciprocal but peaceful fruit sharing in wild bonobos in Wamba Shinya Yamamoto a,b,∗ a Graduate School of Intercultural Studies, Kobe University, 1-2-1 Tsurukabuto, Nada-ku, 657-8501 Kobe, Japan b Wildlife Research Center, Kyoto University, Yoshida-honmachi, Sakyo-ku, 606-8501 Kyoto, Japan * Author’s e-mail address: shinyayamamoto1981@gmail.com Accepted 30 December 2014; published online 29 January 2015 Abstract Food sharing is considered to...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.