Cardinality-Based Feature Modeling and Constraints:
A Progress Report
Krzysztof Czarnecki, Chang Hwan Peter Kim
University of Waterloo
200 University Ave. West
Waterloo, ON N2L 3G1, Canada{kczarnec,chpkim}@swen.uwaterloo.ca

ABSTRACT

platforms, generators, documentation, etc., that are created within a separate product-line development process.
Generative approaches aim at automating the product development part of product-line engineering by means of awide range of static and dynamic technologies, including
metaprogramming, reﬂection, program and model analysis,
constraint-based conﬁguration, and aspect-oriented techniques.
Software Factories [16] can be viewed as a comprehensive and integrative approach to generative software development, as they both share the same goal of automatingproduct development in the context of software product line
engineering. A particular strength of the Software Factory
approach is its support for diﬀerent degrees of automation in
product development. The approach recognizes that domain
knowledge may exist at diﬀerent maturity levels and thus
a wide range of concepts, such as patterns, architectures,
frameworks, components, aspects, and domain-speciﬁc languages, etc., may be required for adequately packaging theknowledge as reusable assets.
Feature modeling is a technique for managing commonalities and variabilities within a product line. The technique
has numerous applications in the context of generative approaches. Among others, it can be used toSoftware factories have been proposed as a comprehensive
and integrative approach to generative software development. Feature modeling has several applications in generative software development, including domain analysis,
product-line scoping, and feature-based product speciﬁcation. This paper reports on our recent progress in cardinalitybased feature modeling and its support for expressing additional constraints. We show that the Object-Constraint
Language (OCL) can adequately capture such constraints.
Furthermore, we identify a set of facilities based on constraint satisfaction that can be provided by feature modelingand feature-based conﬁguration tools and present a prototype implementing some of these facilities. We report on our
experience with the prototype and give directions for future
work.

Categories and Subject Descriptors
D.2.1 [Software Engineering]: Requirements / Speciﬁcations—Tools; D.2.2 [Software Engineering]: Design Tools
and Techniques—Computer-aided software engineering (CASE); D.2.13 [Software Engineering]: Reusable Software—
Domain engineering, Reuse models• capture the results of domain analysis;

General Terms• facilitate scoping of product lines, domain-speciﬁc language families, components, platforms, and other reusable assets; andDesign, Documentation

Keywords• provide a basis for automated conﬁguration of concrete
products, languages, components, platforms, etc.

Feature modeling, model-driven development, product conﬁguration, constraint satisfaction, software-product lines, variability management

There has been a signiﬁcant amount of progress on the notation, processes and techniques, tools, and applications offeature modeling since feature modeling was ﬁrst proposedby Kang et al. [17] (see [13, Section 2] for an extensive setof bibliographic references related to feature modeling).
In this paper we report on our recent progress on a particular form of feature modeling, which is referred to as
cardinality-based [12], the means of expressing additional
constraints for cardinality-based feature modeling, and constraint-satisfaction facilities for feature modeling and featurebased conﬁguration tools.
The main contributions of this paper are the following.

1. INTRODUCTION
Generative software development [10, 4, 11] aims at automating product development in the context of software
product line engineering. Software product line engineering [8, 26] eases the development of products within an application domain by leveraging the commonalities among
these products while managing the diﬀerences among themin a systematic way. As a result, individual products canbe created by reusing assets, such as models, components,
Copyright is held by the author/owner.
OOPSLA’05 Workshop on Software Factories, October 17, 2005, San Diego,
California, USA.
ACM 1-59593-193-7/05/0010.

1. We analyze what is required from a notation for expressing additional constraints on cardinality-based fea1

EShop[1..∗]StoreFront

Catalog

SFPayment[1..∗]

Payment
MethodRef(ref)

BackOﬃce

SFShipping

Payment[1..∗]

Shipping
MethodRef(ref)

Shipping[1..∗][1..∗]

PaymentMethod(String)

GatewayRef(ref)

Fraud
Detection

Payment
Gateways

Shipping
Method(String)

PaymentType
Cyber
SourceCredit
Card

Debit
Card

Purchase
Order

Verisign

Link
Point

Rate
(Float)Figure 1: A sample feature modelture models. We argue that Object Constraint Language (OCL) [20] is adequate for expressing such constraints and support our claim with a number of sample constraints.

(with its entire subtree) can be included as children of thefeature’s parent when specifying a concrete conﬁguration.
Note that we allow a feature cardinality to have as an upper bound the Kleene star *. Such an upper bound denotes
the possibility to take a feature an unbounded number oftimes. Features with the cardinality [1..1] are referred to as
mandatory, whereas features with the cardinality [0..1] arecalled optional. For example, Payment is a mandatory feature, whereas Shipping is an optional feature. Features witha cardinality having an upper bound larger than one can becloned during conﬁguration. Features under a cloned feature can still be conﬁgured if they have variability. Cloning
is useful if a conﬁguration needs to include multiple copies
of a part, where each part may be diﬀerently conﬁgured.
For example, the conﬁguration of an electronic shop may
include multiple store fronts that may be conﬁgured diﬀerently, for example, by having diﬀerent selections of payments
and shipping methods, if any.
Additionally, features can be arranged into feature groups,
where each feature group has a group cardinality. A groupcardinality is an interval of the form m– n, where m, n ∈Z ∧ 0 ≤ m ≤ n ≤ k, where k is the number of features in thegroup. Group cardinality denotes how many group members
can be selected. For example, at least and at most one of thefeatures CreditCard, DebitCard, and PurchaseOrder must
be selected as a subfeature of PaymentType.
A feature can have an attribute type, indicating that an
attribute value can be speciﬁed during conﬁguration (unless the value is already present). We allow at most one
attribute per feature. If several attributes are needed, aset of subfeatures, where each subfeature has an attribute,
can be introduced. The attribute type can be a basic type,such as String or Integer, or FRef, which denotes the set of
all references to features in a given conﬁguration. We also
refer to an attribute with the type FRef as a feature reference attribute. For example, our sample feature model in
Figure 1 uses string attributes to represent names of payment methods and shipping methods, and a ﬂoat attributeto represent the rate of a shipping method. Furthermore,feature reference attributes are used in PaymentMethodRef
and ShippingMethodRef to point to predeﬁned payment andshipping methods in the back oﬃce, i.e., clones of PaymentMethod and ShippingMethod. Although a feature reference
can point to any feature in a conﬁguration, we will latershow how to restrict the attributes to point to any of the

2. We identify a set of facilities based on constraint satisfaction that can be provided by feature modeling andfeature-based conﬁguration tools.
3. We describe a prototype supporting several of such
facilities based on Binary Decision Diagrams (BDDs)
and report on our experience with the prototype. Of
particular notice is the user interface of the prototype
conﬁgurator, which visually distinguishes between user
and machine conﬁguration choices.
The remainder of the paper is organized as follows. Section 2 gives the necessary background information on cardinality-based feature models, including some recent changes
to the notation. The special requirements of cardinalitybased feature modeling on expressing additional constraints
are discussed in Section 3. Section 4 give examples of additional constraints on cardinality-based feature models andshows that they can be adequately expressed in OCL. Section 5 classiﬁes constraint satisfaction algorithms and feature modeling and feature-based conﬁguration facilities basedon such algorithms. A prototype implementing some ofthese facilities and our experience with the prototype aredescribed in Section 6. Related work is discussed Section 7,
and Section 8 closes with conclusions and direction for futurework.

2. BACKGROUND: CARDINALITY-BASEDFEATURE MODELING
Cardinality-based feature modeling integrates a numberof extensions to the original FODA notation. An example
of a cardinality-based feature model describing a family ofelectronic shops is given in Figure 1. The notation is summarized in Table 1. A brief explanation of the notation
follows.
A cardinality-based feature model is a hierarchy of features, where each feature has a feature cardinality. A feature cardinality is an interval of the form [m..n], wherem ∈ Z ∧ n ∈ Z ∪ {∗} ∧ 0 ≤ m ∧ (m ≤ n ∨ n = ∗).
Feature cardinality denotes how many clones of the feature2

Table 1: Symbols used in cardinality-based featuremodeling

A
B

SymbolExplanation

F

Solitary feature with cardinality [1..1], i.e.,
mandatory feature

F

Solitary feature with cardinality [0..1], i.e.,
optional feature

F

F

Grouped feature with cardinality [1..1]

F

Feature F with attribute of type T andvalue of value

F(value:T)

Feature model reference F

F 

Feature group with cardinality 1– 1, i.e.
xor -group
Feature group with cardinality 1– k, where
k is the group size, i.e. or -groupi– j

Feature group with cardinality i– j

A
B

C
C2 

D

E

A

≡

C1 

C1
D

1

3.

C2

B
D2
E

cat-

C

D

(b) New notation

extensive discussion on the applicability of cardinality-based
feature modeling is given elsewhere [13, Section 6].
It is interesting to note that, in contrast to our previous
work [12], we now also associate feature cardinalities withgrouped features [18]. However, the only possible values are[0..0], [0..1], and [1..1]. Normally, a grouped feature has [0..1]
as its default cardinality. The cardinalities [1..1] and [0..0]
are used for features that were selected or eliminated, respectively, from a group during specialization. Furthermore, we
use squares instead of circles for grouped feature cardinalities in order to avoid confusion with the earlier notation
described in the “cat book” [11]. In the book, group cardinalities and grouped feature cardinalities were interpreted insequence, but now, group cardinalities can be thought of as
additional constraints. Figure 3 illustrates this diﬀerence byshowing an example in the original cat-book notation andits equivalent in the current notation.

Grouped feature with cardinality [0..1]

F

B

A

Figure 3: A group of alternative features in the catbook and the new notation

Solitary feature with cardinality [n..m],n > 0 ∧ m > 1, i.e., mandatory clonablefeature[n..m]

D(a) Original
book notation

Solitary feature with cardinality [0..m],
m > 1, i.e., optional clonable feature[0..m]

C

0– 1

E2

CARDINALITY-BASED FEATURE MODELING WITH CONSTRAINTS

Not all kinds of constraints within a feature model canbe expressed using its tree structure and cardinalities. Such
constraints need to be captured as additional constraints.
Probably the best known examples of such constraints are
implies and excludes constraints. Also, the addition of attributes prompts the need to deﬁne constraints over attribute values. Finally, cloning requires the notion of a context for scoping purposes and leads to constraints over setsof features.
Let us ﬁrst explain how cloning inﬂuences the set of facilities necessary for expressing additional constraints. For that
purpose, consider the simple feature model in Figure 4(a).
The constraint stating that feature D implies feature E
could be simply expressed as

1

Figure 2: Unfolding of feature model referencesclones of PaymentMethod or ShippingMethod using an additional constraint. Thus, feature reference attribute areparticularly useful in the context of cloning.
Finally, a node in a feature model can also be a featuremodel reference. A feature model M with a reference toanother feature model is semantically equivalent to a copy of
M in which the reference has been unfolded, i.e., substitutedby the feature model to which the reference points. Featuremodel references allow us to split large feature models into
smaller modules. Also, a feature model can contain several
references to the same sub-model, which is illustrated in
Figure 2. We use subscripts in order to distinguish among
the diﬀerent feature copies created through unfolding. Our
sample feature model in Figure 1 has one feature model
reference, which is Catalog. For brevity, the feature modelthat the reference points to is not shown.
The example in Figure 1 shows the full repertoire of cardinality-based feature modeling. However, practical applications
may depend on a subset of the notation. In particular, feature models describing high-level characteristics of productlines usually do not need feature cloning. Feature cloning
is often useful in deﬁning conﬁgurations of runtime components, policy proﬁles, and platform conﬁgurations. More

D implies E
Unfortunately, this constraint would not make much sense
for the feature model in Figure 4(b). This is because thefeatures B and C are now clonable, and a conﬁguration conforming to this model may now contain multiple clones ofthe features D and E (since a feature is cloned with its
entire subtree). An example of a constraint for the modelin Figure 4(b) would be “the non-emptiness of the set of
all D clones implies the non-emptiness of the set of all E
clones”. Furthermore, practical constraints (as we will see
later) may require collecting clones of a given feature notin the entire feature model, but in the scope of a context
feature (i.e., clones that are direct or indirect subfeatures ofthat feature).
3

A

For example, Figure 6 shows a UML class model corresponding to the feature model in Figure 1. The multiplicity at theaggregate end of every composition in that model is assumed
to be 1. The multiplicities at the other ends are the same as
the corresponding cardinalities in the feature model. Furthermore, FRef is an interface that every class representing
a feature realizes. The group cardinalities from the featuremodel can be expressed as additional OCL constraints on
the class model. Semantically, the class model represents a
set of object structures which obey the multiplicities and the
additional OCL constraints. Each of these object structures
corresponds to a conﬁguration of the feature model.1
Let us take a look at a number of sample additional constraints on the feature model in Figure 1 expressed in OCL.
The ﬁrst example is a simple implies constraint that does
not involve any clonable features.

A[0..∗][0..∗]

B

C

B

C

D

E

D

E

(a) No clonable features(b) Two clonable features (B and C)

Figure 4: Sample feature models without and withclonable features
A

A[0..∗]BCD(a) Feature modelwith a local constraint: C implies D
in the context of B

B1
C1

D1

B2

context Payment inv:
FraudDetection.isSelected() implies PaymentGateways.isSelected()

B3

The constraint states that selecting FraudDetection implies that PaymentGateways is also selected. The constraint
is stated as an OCL invariant in the context of Payment.
The occurrences of FraudDetection and PaymentGateways
denote navigation. According to an OCL convention, thenames of the classes being the targets of the navigation canbe used instead of role names if the latter are not available(which is the case in Figure 6). Furthermore, we assume
that isSelected() is provided as a synonym for the standard OCL operation isDefined(). Please note that thesame constraint can also be expressed using EShop as thecontext:

D2(b) Sample conﬁguration

Figure 5: Sample feature model with a local constraint and its configuration
The notion of a context feature is illustrated in Figure 5.
The constraint that we would like to express for the featuremodel in Figure 5(a) is that for every clone of B it is guaranteed that if the clone has C as a subfeature, it also has D
as a subfeature. In other words, the constraint is expressedin the context of B:

context EShop inv:
BackOffice.Payment.FraudDetection.isSelected() implies
BackOffice.Payment.PaymentGateways.isSelected()

As a second example, we would like to express that thereference attribute of GatewayRef should refer only to a payment gateway, i.e., any of the subfeatures ofPaymentGateways:

context B:
C implies D

context GatewayRef inv:
EShop.BackOffice.Payment.PaymentGateways.sub()->includes(att)

Figure 5(b) shows a conﬁguration conforming to the featuremodel in Figure 5(a) that also satisﬁes the above constraint.
Subscripts were applied to the names of clones in Figure 5(b)in order to uniquely identify them.
Interestingly, additional constraints for cardinality-based
feature models can be adequately expressed using Object
Constraint Language (OCL) [20] or XPath [27]. Examplesof additional constraints expressed using XPath are given
elsewhere [2]. In this paper, we explore using OCL for thispurpose. An important advantage of OCL over XPath isthat modelers are more likely to be familiar with OCL than
XPath. Other advantages include the fact that OCL has
formally deﬁned semantics [20, Appendix A] and that the
template interpretation of OCL described in a previous paper [14] can be used to give formal semantics to OCL in thecontext of cardinality-based feature modeling.

The above constraint is stated in the context of GatewayRef,meanig that the body of the constraint must hold for any instance of GatewayRef. In our case, the body must hold only
if GatewayRef has been selected (i.e., an instance of it exists in the object structure). We assume that the operation
sub() returns all subfeatures of a feature (i.e., all objects
1
At this point, the reader may wonder about the diﬀerences
between feature models and class models. There are at least
three main diﬀerences. Firstly, feature models can be seen asa restricted form of class models. In particular, features do
not have operations, composition has always the multiplicityof 1 at the aggregate end, and relationships such as inheritance and associations are not available. Secondly, featuremodeling oﬀers syntactic sugar. In particular, feature modeling has convenience mechanisms such as feature groups,
which would have to be expressed as OCL constraints in aclass model, and a more concise concrete syntax. The tree
structure can also be exploited by tools to provide automaticlayout and outlining. Thirdly, feature modeling comes with
its own modeling philosophy. Feature models represent hierarchies of properties, which is rather unusual for class modeling.

4. OCL AS A CONSTRAINT LANGUAGE
FOR CARDINALITY-BASED FEATURE
MODELS
OCL can be adopted for feature modeling by interpretingfeature models as class models with a containment hierarchy.
4

EShop1..*

1StoreFront

BackOﬃce

1

1

0..1

1

0..1

Catalog

SFPayment

SFShipping

Payment

Shipping

1..*

1..*

1..*

0..1

0..1

..
.

Payment
MethodRef
att : FRef

Shipping
MethodRef
att : FRef

PaymentMethod
att : String

Payment
Gateways

Fraud
Detection

0..1

1

0..1

0..1

0..1

GatewayRef
att : FRef

PaymentType

Cyber
SourceVerisign

Link
Point

0..1

0..1

Credit
Card

Debit
Card

0..1

1..*

Shipping
Methodatt : String1

Rate
att : Float

Purchase
Order

Figure 6: UML class model corresponding to the feature model in Figure 1
contained in the target of the operation). The right arrowis used in OCL to invoke operations on collections. In ourcase, we check whether the value of GatewayRef’s attribute
att is included in the subfeatures of P aymentGateways.
Similarly, we want to enforce that payment methods available in a given store front are a subset of the payment methods provided by the back oﬃce:

context Shipping inv:
ShippingMethod.Rate.att->exists(x| x>0)

Now we are ready to look at how the group cardinalities
from the feature model can be expressed as additional OCL
constraints on the class model. For example, the or-group
under PaymentGateways can be represented by the following
constraint:

context PaymentMethodRef inv:
EShop.BackOffice.Payment.PaymentMethod->includes(att)context PaymentGateways inv:
letnumOfSelectedFeatures =CyberSource->union(Verisign->union(LinkPoint))->size()innumOfSelectedFeatures >= 1 andnumOfSelectedFeatures <= 3

The above constraint assumes that the root feature EShop
can be used as a constant denoting the sole instance ofEShop, i.e., it is a syntactic sugar for EShop.allInstances().
Since the upper bound of the cardinality of PaymentMethod
is higher than one, the result of the navigation EShop.BackOffice.Payment.PaymentMethod is a collection.
An analogous constraint is needed for shipping methods:

5.

TOOL SUPPORT FOR FEATURE MODELING WITH CONSTRAINTS

A feature model with additional constraints can be translated into a set of variables and set of constraints over thesevariables. The variables represent the possible individual
choices, such as feature selections and attribute value assignments, and the set of constraints includes both the constraints implied by the feature hierarchy and the additional
constraints. A value assignment that satisﬁes the constraints
corresponds to a correct conﬁguration. A value assignmentthat assigns a value to every variable in the variable set corresponds to a full conﬁguration. A partial assignment corresponds to a partial specialization [12], which is sometimes
also referred to as a partial conﬁguration.
The area of Constraint Satisfaction oﬀers numerous algorithms that are of interest to feature modeling and featurebased conﬁguration tools. The main algorithm classes ofinterest include:

context ShippingMethodRef inv:
EShop.BackOffice.Shipping.ShippingMethod->includes(att)

The next constraint is an example of an implies constraint
within the context of a clonable feature (similar to the example in Figure 5). It states that every payment method of
the type debit or credit card must have a speciﬁed gateway:
context PaymentMethod inv:
(PaymentType.CreditCard.isSelected() orPaymentType.DebitCard.isSelected()) implies
GatewayRef.isSelected()

As an example of a constraint on the size of a set, let us
restrict the number of payment methods that are available
in a store front to 3:
context StoreFront inv:
SFPayment.PaymentMethodRef->size() <= 3

• Constraint checking: Checking whether a particular(complete or partial) variable assignment satisﬁes theconstraints.

Finally, we give two examples of constraints involving numeric attribute values. The ﬁrst constraint states that ashipping rate cannot be a negative number:• Constraint propagation: Infering the values of undecided variables from the values of decided variables.

context Rate inv:
att>=0• Constraint satisfiability: Checking whether a set of
constraints has at least one solution.

The second constraint states that if an electronic shop has
shipping, at least one shipping method has a rate which isa positive number (i.e., at least one shipping method is notfree):• Constraint solving: Computing solutions for a set of
constraints.
5• Computing the number of solutions: Computing thenumber of complete solutions for a set of constraints.

• Auto-completion of configurations: Constraint solving
can be used for computing solutions (including completing partial solutions) that can be presented to theuser.

A feature modeling tool can oﬀer facilities based on constraint satisfaction algorithms to help the developer create
correct feature models. Examples of such facilities are• Debugging incorrect configurations: In some cases, theuser may wish to quickly make several choices without verifying the number of remaining conﬁgurations
along the way. This is particularly the case for an
expert user. The resulting conﬁguration may not becorrect, in which case it needs to be ﬁxed. While someof the user choices will have to be revised, the user
may care about keeping some choices more than keeping some other choices. Thus, we need eﬃcient ways of
conﬁguration ﬁxing, which takes user preferences into
account.

• Model consistency checking: Constraint satisﬁability
allows determining that the feature model has at least
one correct conﬁguration.
• Detecting anomalies: Anomalies such as “dead features”, i.e., features that are not part of any correct
conﬁguration and thus cannot be selected [24], can also
be detected through constraint satisﬁability. A feature
is dead if the conjunction of the variable corresponding to the feature and the constraints implied by thefeature model is not satisﬁable.

Auto-completion and debugging are probably the mostchallenging facilities to provide. Adequate solutions may
require weak constraints, heuristics, and custom solution
procedures.

• Computing metrics: The number of correct conﬁgurations is a useful metric indicating the degree of variability embodied in a feature model [15, 25]. It canbe computed by calculating the number of solutions
to the set of constraints implied by the feature model(including the additional constraints). Another example is degree of orthogonality, which is the ratio between the number of solutions to the set of constraints
implied by the feature model (including all additional
constraints) and the number of solutions to the set of
constraints implied by the feature hierarchy and additional constraints that are local (i.e., involve just one
feature). A high degree of orthogonality means thatdecisions about feature selections can be done locally,i.e., without worrying about their inﬂuence on choices
in other parts of the feature hierarchy.

6.

TOOL PROTOTYPE

We have created a prototype extending fmp [2] with someof the facilities based on constraint satisfaction discussed in
the previous section. fmp is an Eclipse plug-in for featuremodeling and feature-based conﬁguration. In particular, wehave extended fmp with the following facilities.
• Computing the number of configurations represented bya feature model : This facility allows the user to verify that a model has at least one conﬁguration, and it
also gives the user an idea about the degree of variability embodied in the feature model. Figure 7 showsa sample feature model with the number of concrete
conﬁgurations it represents.
• Propagating configuration choices: Figure 8 shows ascreen shot of the conﬁguration interface, which renders the feature hierarchy with a check box for every variable feature. The check box can have one ofﬁve states: undecided, user-selected, machine-selected,user-eliminated, and machine-eliminated. Undecided
is rendered as an empty check box and means that theuser has not decided whether this feature should beselected or eliminated. The user can explicitly selector eliminate a feature, which is rendered by a dark
check or cross, respectively. A user choice may trigger machine choices by means of propagation. Features selected or eliminated by the machine are rendered as light checks or crosses, respectively. For example, Figure 8 shows the result of the user selecting
feature FraudDetection in a conﬁguration where allcheck boxes were initially empty. Since FraudDetection
implies PaymentGateways, choice propagation has theeﬀect of placing a light check on PaymentGateways.
The user then decided to select CyberSource and eliminate LinkPoint, while leaving Verisign still undecided. Using a diﬀerent rendering for machine choices
allows the user to better understand the eﬀect of choicepropagation.

Constraint satisfaction algorithms are particularly of interest for feature-based conﬁguration tools. Examples offacilities based on constraint satisfaction in feature-based
conﬁguration are• Configuration checking: Checking that a complete conﬁguration satisﬁes a set of constraints is a relatively
simple and inexpensive operation amounting to expression evaluation. Checking a partial conﬁguration ismore expensive: it means checking to see whether thepartial conﬁguration is implied by the feature model,i.e., it requires checking constraint satisﬁability.
• Showing the number of remaining configurations: Computing the number of conﬁgurations after every conﬁguration step gives the user a better idea about the
progress of the conﬁguration process. If the number isone, the user arrived at a complete conﬁguration. If
the number is zero, the user has just created an incorrect conﬁguration and will need to revise some of the
conﬁguration steps.
• Propagating configuration choices: Selecting a particular feature may require selecting some other feature(s),in which case the latter selection(s) can be inferred automatically from the ﬁrst one using constraint propagation. In general, a conﬁguration choice that assignsa particular value to a variable may restrict the domains of available values for other variables.

• Computing the number of remaining configurations during the configuration process: The number of remaining conﬁgurations is the number of concrete conﬁgurations represented by the current (potentially partial)
6

The performance aﬀorded by the underlying BDD algorithms is excellent: the time required for counting solutions,propagating choices, and computing solutions is hardly noticeable by the user. We have tested our prototype withmodels containing up to several hundred features. However,since the number of features equals the number of variablesof the corresponding constraint satisﬁability problem andcurrent BDD packages are known to handle problems withtens of thousands of features eﬃciently, we do not expect
any scalability problems in terms of performance.
Although the visual distinction between user and machinechoices has shown to be useful, our initial experiments haveshown that better facilities for reviewing the eﬀect of choicepropagation are needed. We are currently working on a userinterface that allows the user to browse through the eﬀects
of propagating a user choice and to revoke the choice if desired. Also, the auto-completion facility needs further development. In particular, we want to allow the feature model
designer to deﬁne weak constraints which can compute appropriate default completions based on the user choices at
a given point during the conﬁguration process.

Figure 7: Sample feature model in fmp with constraint support

7.

RELATED WORK

Related work for cardinality-based feature modeling canbe found in an earlier paper [13]. Here we only focus on expressing constraints for cardinality-based feature modelingand constraint-based tool support for feature modeling andfeature-based conﬁguration.
The use of XPath for expressing constraints for cardinalitybased feature modeling has been proposed in the context of
two feature modeling tools, namely XFeature [7] and an earlier version of fmp [2]. In terms of constraint satisfaction,
both of these tools can check whether a concrete conﬁguration is correct with respect to the XPath constraints,
which is done by simply invoking an XPath evaluator on an
XML representation of the conﬁguration. However, moresophisticated facilities such as choice propagation or autocompletion are not supported by these tools. While the paper by Cechticky et al. [7] gave one example of a constraint
involving clonable features, we are not aware of any previous
work analyzing the special needs of cardinality-based feature modeling in terms of expressing additional constraints
as given in Section 3. The use of OCL as a language for expressing additional constraints for feature models was previously explored in a Diploma thesis by Schilling [21] under thesupervision of the ﬁrst author and by Streitferdt et al. [22].
An example of work on feature-based conﬁguration supporting constraint satisfaction facilities beyond simple conﬁguration checking is that of Batory [3]. Batory discusses
the use of SAT solvers for checking consistency of a featuremodel and the use of constraint propagation algorithms topropagate conﬁguration choices. Benavides et al. present
similar ideas [5]. Certain versions of the feature modeling and conﬁguration tool pure::variants [6] also support
choice propagation. Similar to our prototype described in
Section 6, the constraint satisfaction facilities in the above
works do not consider clonable features.
Von der Maßen and Lichter [25] proposed a way to calculate a rough approximation of the number of correct complete conﬁgurations. We use SAT count, an existing BDDbased algorithm [1], which can compute the exact number ofsuch conﬁgurations for large feature models within a fractionof a second. Also, we are not aware of any other feature-

Figure 8: Sample configuration in fmp with constraint support

conﬁguration. This number may give the user an idea
about the progress of the conﬁguration process. For
example, the partial conﬁguration in Figure 8 represents two concrete conﬁgurations, meaning that further conﬁguration choices are needed if the user wishes
to arrive at a single complete conﬁguration. The number also informs the user when the partial or complete
conﬁguration being constructed becomes incorrect, inwhich case the number of remaining conﬁgurations becomes zero.
• Auto-completion of configurations: After making zeroor more choices, the user may request the tool to complete the conﬁguration such that the conﬁguration conforms to the feature model with its additional constraints. The user may ask the tool to show up toa user-speciﬁed number of correct solutions. The listof alternative solutions can be inspected in a solution
browser and the desired solution can be selected.
The current prototype supports constraints only in theform of propositional formulas over features, and it assumes
feature models without clonable features. The feature hierarchy is translated into a propositional formula according to
the approach given by Batory [3].
The required constraint satisfaction machinery, namely
computing the number of solutions, constraint propagation,and constraint solving, is based on Binary Decision Diagrams (BDD) [1]. The particular BDD package used in thecurrent prototype is from Conﬁgit Software [9].
7

Information Systems Engineering (CAiSE’05), Porto,
Portugal, 2005, LNCS. Springer, 2005.
[6] D. Beuche. pure::variants Eclipse Plugin. User Guide.
pure-systems GmbH. Available fromhttp://web.pure-systems.com/fileadmin/
downloads/pv_userguide.pdf, 2004.
[7] V. Cechticky, A. Pasetti, O. Rohlik, and
W. Schaufelberger. XML-based feature modelling. In
J. Bosch and C. Krueger, editors, Software Reuse:
Methods, Techniques and Tools: 8th International
Conference, ICSR 2004, Madrid, Spain, July 5-9,
2009. Proceedings, volume 3107 of Lecture Notes in
Computer Science, pages 101–114, Heidelberg,
Germany, 2004. Springer-Verlag.
[8] P. Clements and L. Northrop. Software Product Lines:
Practices and Patterns. Addison-Wesley, Boston, MA,
2001.
[9] Conﬁgit Software. Configit—Product Configuration
Engine, 2005. http://www.configit-software.com/.
[10] K. Czarnecki. Overview of Generative Software
Development. In Proceedings of Unconventional
Programming Paradigms (UPP) 2004, 15-17
September, Mont Saint-Michel, France, Revised
Papers, volume 3566 of Lecture Notes in Computer
Science, pages 313–328. Springer-Verlag, 2004.
http://www.swen.uwaterloo.ca/~kczarnec/
gsdoverview.pdf.
[11] K. Czarnecki and U. W. Eisenecker. Generative
Programming: Methods, Tools, and Applications.
Addison-Wesley, Boston, MA, 2000.
[12] K. Czarnecki, S. Helsen, and U. Eisenecker. Staged
conﬁguration using feature models. In R. L. Nord,
editor, Software Product Lines: Third International
Conference, SPLC 2004, Boston, MA, USA, August30-September 2, 2004. Proceedings, volume 3154 of
Lecture Notes in Computer Science, pages 266–283,
Heidelberg, Germany, 2004. Springer-Verlag.
[13] K. Czarnecki, S. Helsen, and U. Eisenecker. Staged
conﬁguration through specialization and multi-level
conﬁguration of feature models. Software Process
Improvement and Practice, 10(2):143–169, 2005.
http://swen.uwaterloo.ca/~kczarnec/spip05b.pdf.
[14] K. Czarnecki and K. Pietroszek. Verifying
feature-based model templates against well-formedness
OCL constriants. Submitted for publication, 2005.
[15] U. Eisenecker, M. Selbig, F. Blinn, and K. Czarnecki.
Feature modeling for software system families.
OBJEKTspektrum, (5):23–30, 2001. special issue on
product families (in German).
[16] J. Greenﬁeld and K. Short. Software Factories:
Assembling Applications with Patterns, Models,Frameworks, and Tools. Wiley, Indianapolis, IN, 2004.
[17] K. Kang, S. Cohen, J. Hess, W. Nowak, and
S. Peterson. Feature-oriented domain analysis(FODA) feasibility study. Technical Report
CMU/SEI-90-TR-21, Software Engineering Institute,Carnegie Mellon University, Pittsburgh, PA, Nov.
1990.
[18] C. H. P. Kim and K. Czarnecki. Synchronizing
cardinality-based feature models and their
specializations. In Proceedings of ECMDA’05, 2005.
swen.uwaterloo.ca/~kczarnec/ecmda05.pdf.

based conﬁguration tools showing the number of remaining
conﬁgurations.
The use of a BDD package as constraint satisfaction engine for feature modeling and conﬁguration is not new. An
example of such approach is that by van der Storm [23]. A
related approach using BDDs, although not directly basedon feature modeling, is DESERT [19].
A large body of work dealing with constraint-based conﬁguration exists in the area of Artiﬁcial Intelligence. We
already discussed the related approaches from that are in aprevious paper [13, Section 6]. Although these approaches
are usually concerned with the conﬁguration of physical products, many ideas can certainly be transported into the realmof software product lines. We expect more of such crossdisciplinary eﬀorts in the future.
We are not aware of any other classiﬁcation of constraintsatisfaction-based facilities for feature modeling comparable
to the one given in Section 5.

8. CONCLUSIONS AND FUTURE WORKIn this paper, we analyzed the needs of cardinality-based
feature modeling with respect to expressing additional constraints and demonstrated how these needs are satisﬁed by
OCL. Furthermore, we classiﬁed the facilities that a feature modeling tool and a feature-based conﬁgurator can offer based on constraint satisfaction algorithms. Finally, we
described a prototype implementation of some of these facilities and shared our experience with the prototype.
For future work, we plan to extend the constraint satisfaction facilities in our tool prototype to handle OCL constraints over the full cardinality-based feature modeling notation. This will be done by adapting our OCL templateinterpretation [14] for the purpose of feature modeling. Furthermore, we plan to improve the user interaction modeland the user interface for feature-based conﬁguration in order to allow the user to deal with large feature models more
eﬀectively.

9. REFERENCES[1] H. R. Andersen. Binary Decision Diagrams.
Department of Information Technology, Technical
University of Denmark, Lyngby, Denmark, 1997.
Lecture notes for 49285 Advanced Algorithms E97,
http://www.itu.dk/people/hra/notes-index.html.
[2] M. Antkiewicz and K. Czarnecki. FeaturePlugin:
Feature modeling plug-in for Eclipse. In OOPSLA’04
Eclipse Technology eXchange (ETX) Workshop, 2004.
Paper available from http://www.swen.uwaterloo.ca/~kczarnec/etx04.pdf.
Software available from gp.uwaterloo.ca/fmp.
[3] D. Batory. Feature Models, Grammars, andPropositional Formulas. Technical Report TR-05-14,
University of Texas at Austin, Texas, Mar. 2005.
[4] D. Batory, R. Lopez-Herrejon, and J.-P. Martin.
Generating product-lines of product-families. In
Automated Software Engineering, 2002. Proceedings.
ASE 2002. 17th IEEE International Conference, pages
81–92, 2002.
[5] D. Benavides, P. Trinidad, and A. Ruiz-Cortés.
Automated reasoning on feature models. In
Proceedings of the 17th Conference on Advanced
8

[19] S. Neema, J. Sztipanovits, and G. Karsai.
Constraint-based design-space exploration and model
synthesis. In Proceedings of EMSOFT’03, volume 2855
of LNCS, pages 290–305. Springer, 2003.
[20] OMG. UML 2.0 OCL Specification, 2003.
http://www.omg.org/docs/ptc/03-10-14.pdf.
[21] D. Schilling. Konﬁguration von komponenten in
produktlinien. Diplomarbeit, DaimlerChrysler
Research and Technology, Ulm, and Universität
Paderborn, Paderborn, Germany, Sept. 2002. (inGerman).
[22] D. Streitferdt, M. Riebisch, and I. Philippow. Detailsof formalized relations in feature models using OCL.
In ECBS, pages 297–304, 2003.
[23] T. van der Storm. Variability and component
composition. In Proceedings of ICSR8, LNCS.
Springer, 2004.
[24] T. von der Maßen and H. Lichter. Deﬁciencies infeature models. In Proceedings of SPLC’04 Workshop
on Software Variability Management for ProductDerivation - Towards Tool Support, 2004.
[25] T. von der Maßen and H. Lichter. Instantiating valid
products from feature models. In Proceedings of 9th
International Software Product Line Conference(SPLC), LNCS. Springer, 2005.
[26] D. M. Weiss and C. T. R. Lai. Software Product-LineEngineering: A Family-Based Software Development
Process. Addison-Wesley, Boston, MA, 1999.
[27] World Wide Web Consortium. XML Path Language(XPath) 2.0, 2005. http://www.w3.org/TR/xpath20/.

9