=Paper=
{{Paper
|id=Vol-557/paper-6
|storemode=property
|title=Integrated Modeling of Software Product Lines with Feature Models and Classification Trees
|pdfUrl=https://ceur-ws.org/Vol-557/paper6.pdf
|volume=Vol-557
|dblpUrl=https://dblp.org/rec/conf/splc/OsterMSM09
}}
==Integrated Modeling of Software Product Lines with Feature Models and Classification Trees==
https://ceur-ws.org/Vol-557/paper6.pdf
Integrated Modeling of Software Product Lines with
Feature Models and Classification Trees
Sebastian Oster Florian Markert Andy Schürr
Real-Time Systems Group Computer Systems Group Real-Time Systems Group
Technische Universität Darmstadt Technische Universität Darmstadt Technische Universität Darmstadt
Werner Müller
Global Systems Engineering Methods
Adam Opel GmbH
Abstract—Software Product Lines (SPLs) are an approach to together with semi-automatic procedures that allow one to
improve reusability of software in a large number of products select the appropriate test cases for a specific SPL instance.
that share a common set of features. In SPLs, Feature Models Examining more closely the state-of-the-art of SPL develop-
(FMs) are frequently used to model commonalities and variabil-
ities. However, according to the best of our knowledge, there are ment and software testing approaches in the automotive in-
no approaches to automatically generate test cases on the basis dustry we see that various kinds of feature modeling concepts
of a stand-alone FM. We introduce a method, which fills this and tools are used for the design of SPLs and the selection
gap. In single system software testing, Classification Trees (CTs) of needed instances [4], [21]. On the other hand, CTs and
are a proven approach for generating test cases derived from related tools such as CTE [1] are successfully used for black-
the original system specification. In this paper, we explore the
relations and similarities between FMs and CTs and integrate box testing of single product instances. We are not aware
both methods to a unified approach called Feature Model for of any proposal how to combine feature modeling concepts
Testing (FMT). used for the description and selection of features (parameters,
options, ... ) of SPLs with CT-concepts used for the description
I. I NTRODUCTION and selection of test case parameters of selected product
SPL-engineering is one of the most promising approaches instances—despite of the fact that the borderlines between
of the Software Engineering community to reduce the develop- feature selection at compile time and input parameter selection
ment costs, for as well as to increase the quality of families of at runtime are blurred, and the same parameter may either be
similar software product instances [4]. As a consequence, soft- instantiated at compile time or flash time, to unlock a specific
ware product line engineering is successfully used in various function or changed at runtime to activate a certain mode of
domains, including the domain of automotive software devel- operation.
opment. In this area, the combination of highly parametrized To overcome these problems we will first present in Section II
software of electronic control units (ECUs), together with of this paper the fundamentals of SPL description by means of
an abundance of configuration options of networks of ECUs FMs and the specification of parameter equivalence classes for
will soon lead to a situation, where (1) a single ECU may testing purposes by means of CTs. Furthermore, this section
be instantiated in at least 10.000 different ways and (2) the introduces our paper’s running example, a subset of a case
software of a network of more than 50 ECUs in a single car study provided by the Adam Opel GmbH which is a subsidiary
may exist in millions of different configurations. of GM (General Motors) Corp. Afterwards, we explain in more
As a matter of fact, we are, therefore, running into a situation detail the state-of-the-art of systematic testing approaches of
where each instance of a certain brand of car possesses a SPLs and black box testing with CTs in a related work section.
unique configuration of the embedded software of all its ECUs. Section IV then systematically compares the basic modeling
Testing all these millions of instances of an automotive SPL in elements of FMs, similar to the developed FMs in FODA [14]
the following traditional way is no longer feasible: create all and the classification approach as supported by the tool CTE
actually used instances of an SPL and then develop for each [1]. Based on this comparison, a tight integration of both
instance a separate suite of integration test cases. Hence, the modeling languages is proposed and the abstract syntax of
automotive industry as well as engineers from other domains the resulting feature and test parameter modeling language
are urgently looking for new methods how to systematically “FMT” is presented. In Section V we describe the derivation
generate sets of software product instances that represent of a product with corresponding test cases from the FMT.
equivalence classes of instances with a sufficiently similar Additionally, we discuss an approach of testing SPLs using
behavior from a system integration testing point of view. FMT. The conclusion summarizes the advantages of such an
Furthermore, model-based and more traditional black and integrated feature and parameter equivalence class modeling
white box testing approaches are adapted in such a way that approach and lists a number of ongoing and future research
families of test models and derived test cases can be developed, activities.
II. F UNDAMENTALS the original FODA with additional cardinality extension [7].
The contribution of this paper is to generate variants and Table I depicts the used notation. We do not want to discuss
corresponding test cases on the basis of one representation of
Graphical Notation Cardinality Formal description
the SPL.
Single features
edge with filled circle 1..1 feature is mandatory
A. Running Example edge with unfilled circle 0..1 feature is optional
Our running example is a very simple subset of hard- Group of features
ware and software components of the recently released Opel filled circles 1..n choose exactly
and connected edges one feature
Insignia. We restrain ourselves to four sensors, two actors unfilled circles n..m choose any combination of
(engines), and one software component. The sensors are rain and connected edges features, but at least one
light sensor (RLS), turn indicator sensor (TIS), steering angle TABLE I
sensor (SAS), and the vehicle speed sensor (VSS). The RLS N OTATION
detects rain and the TIS indicates the driver’s choice to turn
left or right. SAS senses the steering angle and the VSS
senses the speed of the car. Two different types of engines every FODA extension because our approach is not limited to
serve as hardware features: a 1.6 liter and a 2.0 liter turbo a certain FM. We also aim e.g. to support the Orthogonal
engine. Additionally, we use one feature of the (Adaptive Variability Model (OVM) proposed by Pohl et al. [21]. A
Forward Lighting) AFL+ technology. The bending light is a detailed description of the relation between FMs and OVMs is
functionality which belongs to AFL+ and realizes an adaptive given in [18]. We, therefore, assume that our unified approach
curve light. All parameters presented in this paper are provided using FMs may also use the OVM approach.
by the Adam Opel GmbH. We use the running example to The FM in Fig. 1 shows an excerpt of the Opel Insignia FM.
exemplify the differences and commonalties between FMs and All dependencies and constraints within the FM have to be
CTs and to motivate our approach of integrating both to a taken into account when deriving a product.
Feature Model for Testing (FMT).
B. Product Lines and Feature Models
SPLs provide a high level reuse of software in a spe-
cific problem domain [4], [21]. FMs are frequently used
to describe an explicit representation of the commonalities
and variabilities in an SPL. FMs consist of features each
representing “a system property that is relevant to some
stakeholder” as defined in [6]. One major advantage of using
FMs to model SPLs is that they offer a very intuitive way
to represent commonalities and variabilities. However, FMs
by themselves are insufficient for a complete modeling of
an SPL. Usually FMs are complemented by development Fig. 1. Feature Model of Opel Insignia
artifacts such as UML diagrams or code fragments that are
traced to the corresponding features. An FM provides a tree-
C. Software Testing with Classification Trees
like structure and incorporates different node notations and
cross-tree-constraints. The first feature model was introduced After extracting a variant from the FM, suitable test cases
by Kang et al. in [14] as part of FODA, in 1990. In the need to be built. For this purpose the CT-method was in-
FM of FODA node notations like, mandatory, optional, and troduced by Grochtmann and Grimm [11]. It provides an
alternative features can be modeled. It is also possible to use approach to black box testing. Test cases can be extracted
require and exclude constraints between features, which are by defining rules for valid input combinations. A CT consists
described textually. Since the introduction of FODA, further of classifications (boxes with bold lines), compositions (boxes
extensions of FMs were introduced to improve precision with thin lines), and equivalence classes (values in brackets).
and expressiveness, including amongst others cardinalities, Each equivalence class represents a disjoint subset of param-
probabilities, and weighting. We can employ cardinalities to eter values for a classification, while the composition splits
formulate the different notations of features and groups of complex input parameters into a number of subcomponents.
features [7]. The probabilities can be based on empirical To generate test cases from a specification using CTs the
data and/or system specifications and are used to state that following procedure needs to be applied:
a certain feature is more likely than another one [8]. Weights 1) evaluate the specification and identify all classifications
can be used to represent cost factors of features to help the with the corresponding equivalence classes
engineers to build products appropriate for a certain budget 2) build the CT
[13]. Czarnecki et al. summarize some existing extensions 3) fill the test case table with respect to the CT using
of the FODA FM [6]. However, our FM is very similar to parameter value combination heuristics
4) extract all possible test cases from the test case table by development process of SPLs:
identifying valid combinations of equivalence classes Product-by-product testing: In the majority of cases, each
omitting illegitimate samples out of the test set instance of an SPL is tested individually. This method is
called product-by-product testing. Each product instance may
Fig. 2 depicts a variant of the Insignia SPL and a correspond- be tested using the CT approach. However, this method is very
ing CT to test this instance. Sensors is a composition, while exhaustive and normally not practicable. For instance, in the
turn indicator is a classification of the equivalence classes automotive field a single ECU like the engine control unit may
representing test values. The model is extracted from the be instantiated in at least several 10.000 different ways. Since
specification of the product instance. Test cases can be derived a car may consist of up to 50 ECUs this results in millions of
easily by choosing a valid combination of equivalence classes. different configurations. An individual test of all configurations
This model can e.g. be used to check the output characteristics is feasible neither at the end of the assembly line nor during
of the AFL+ dependent upon the sensor intervals. The range of the development process. One method to improve product-by-
the intervals is defined by the designer. It depends on suitable product testing is to identify a minimal set of products which
test scenarios chosen by the designer or extracted from the is representative for all other products. However, finding a
specification. A test case table is built, which incorporates all minimal test set is an NP-complete problem [26]. Different
relevant test cases in an abstract way. heuristics are used to approximate a minimal test set. A very
promising procedure is mentioned in [26]. The author uses a
simplified version of the OVM approach. Members for the
representative set of products are selected on the basis of
requirements. That means that certain products are chosen so
that all requirements are verified at least once. Optimization
problems are formulated to produce a minimal test set.
In [20], an approach with a motivation similar to [26] was
published. It uses dependencies derived from architecture and
implementation to extend the FM of the SPL under test. Sub-
sequently, pairwise testing that considers these dependencies
is used to generate a representative set of products.
In both approaches the generation of test cases with appropri-
ate input parameter values is out of scope.
Incremental Testing: In this approach, the first product de-
rived from the SPL is tested individually, for instance by using
the CT-methodology. With respect to the commonalities be-
tween the different products, the following products are tested
using regression testing techniques [17]. The challenging part
of this approach is to identify those parts of a product which
stay unchanged and those which vary. The question arises
if only the modified and added parts have to be tested. In
addition, one has to find out if the modified parts can be
tested individually or if some of them have to be tested in
Fig. 2. Classification tree of selected product instance combination with unchanged components.
Reusable assets: The goal is to create reusable test assets.
In Fig. 2 three test cases for the CT of the running example To ensure reusability, these assets are created during domain
are given. Each test case consists of the equivalence classes engineering. For each product these assets are customized
marked by the black dots in a horizontal line. during application engineering. Pohl et al. apply model based
testing techniques. The authors use activity diagrams which
III. R ELATED W ORK are developed in domain engineering, based on requirements,
In this section we focus on SPL-testing and the role FMs and customized during application engineering to derive test
play in that context. We also present research activities related cases. The so called ScenTED approach focuses on the reuse
to software testing using the CT-method to generate test cases. of test cases [25], [24], [22]. It uses substitution in order
to derive configuration specific test cases. This is a very
A. Testing SPLs promising approach which we will take into account in our
Miscellaneous approaches exist dedicated to SPL testing. future work. However, test parametrization and the selection
Although there are no real FM-based testing approaches, many of proper values is still an open problem.
test methods partially use the FM of the SPL under test. A Division of responsibility: In [28], this method is described
summary of methods is given in [28]. The authors distinguish according to the levels of the development process, for instance
between the following approaches to integrate testing into the the V-model. For example, unit testing can be executed during
domain engineering and the other levels of the V-model could first subsection starts with the in-depth comparison of FM
be executed in the application engineering phase. and CT modeling constructs. Based on the results of this
All approaches confirm that testing is very challenging in comparison, the following subsection then selects a minimal
SPL-engineering due to the high level of variability. However, number of language constructs that correspond to a superset of
the fact that the parametrization within an SPL leads to an the concepts of both FM and CT. Finally, the last subsection
additional degree of variability is often neglected as well as introduces a metamodel that captures the essential design of
the fact that the borderlines between parameters that model the new integrated FMT modeling language from an abstract
variability at design time and parameters that are instantiated syntax point of view.
at runtime are often moving.
A. FMT Language Constructs
Furthermore, we are not aware of any SPL testing approach
that combines SPL variant selection strategies with parame- In this section we develop language constructs which
ter value selection strategies as supported by CT. The tool present a minimal list of abstract language concepts that is
pure::variants [23] offers e.g. the option to store parameter a superset of the concepts of FM and CT. Table II lists the
information in attributes of features, but gives no support constructs of FMs and CTs and the corresponding constructs
for the definition of equivalence classes etc. The approach for the unified approach: FMT. First, we have to define which
published in [19] is as far as we know the most similar kinds of nodes the FMT needs to support. CTs distinguish
SPL testing method to FMT. It uses one decision model to between compositions, classification, and equivalence classes.
represent the variability of an SPL as well as to document input Composition and classification (line 1 in Table II) in CTs
parameters of the regarded system. An integrated SPL variant are nodes with child elements and equivalence classes (line
and parameter value selection process is presented with rather 3 in Table II) are leafs in a CT. In FMs only compound
promising evaluation results. Compared to FMT presented here features contain child elements and leafs are always features.
the decision model is considerably less expressive and the To integrate CTs and FMs with regard to the different kinds
introduced selection process is considerably less expressive of nodes, we need to examine the differences. Compositions
than the algorithms for SPLs and the heuristics developed for are always mandatory and classifications are always optional
CT-based black box testing purposes. nodes. As a consequence, we can use the compound feature
known from FMs, and use cardinalities to state that the
B. Black-Box Testing Products with CT compound feature is either optional (0..1) or mandatory (1..1).
CTs are a widely used technique for test case generation. Therefore, we adopt the compound feature for the FMT
There are many publications related to this topic. A CT can approach. The leafs of CTs and FMs differ obviously. On the
be used to test a single product instance derived from the
Feature Model Classification Tree FMT
FM. The resulting product instance has specific actors and
1. compound composition, compound feature
sensors, which interact complying to the specification. A CT feature classification
splits the input domain of the sensors into relevant equivalence 2. Feature none Feature
classes. These classes can be used to test an actor that is 3. none equivalence atomic feature
class
part of the product instance. Several approaches to improve 4. mandatory composition mandatory feature
and extend CTs like the Classification Hierarchy Table [3], feature (1..1) (1..1)
the Classification Tree Transformer [27], Class Graphs [15], 5. optional classification optional feature
feature (0..1) (0..1)
adding attributes [16], and introducing a time line [5] have 6. (1..n) equivalence (1..n)
been discussed. There are tools like the Classification Tree features class features
Editor for Embedded Systems (CTE/ES) that support the 7. (n..m) none (n..m)
features features
designer when trying to build a CT and its test table. The
8. cross-tree- only between cross-tree-
CTE/ES provides a graphical user interface that enables the constraints equivalence classes constraints
designer to build a CT and the corresponding combination 9. feature none feature
table. attributes attributes
10. feature none feature
All CT-based testing approaches we are aware of share the types types
drawback that they deal with single product instances only
TABLE II
and thus are only compatible with a product-by-product SPL L ANGUAGE C ONSTRUCTS
testing approach.
IV. U NIFIED A PPROACH - FMT one hand, an equivalence class represents a value or range
As introduced in the preceding sections FMs and CTs of values of a parameter necessary for testing. On the other
have been used in software engineering for rather different hand a feature in FMs can be any feature or property of
purposes until now. An in-depth comparison of the modeling an SPL. To realize an integration we need a leaf, which is
language constructs of FMs and CTs in the sequel reveals capable to represent both information: a feature in general and
that both modeling approaches share a majority of their a representation of values of parameters. Another difference,
concepts. Therefore, this section is structured as follows: the which we have to take into account for the integration, are the
cardinalities. In FMs features and compound features may have in hardware or software. Additionally, we can apply constraints
four different types of cardinalities to describe commonalities between Features and, therefore, also between Compound
and variabilities. In CTs three of them are present: composition Features and Atomic Features. According to FMs we
(1..1), classification (0..1), and equivalence classes (1..n). We allow Require and Exclude constraints between all nodes.
adopt the missing cardinality of FM to ensure that the FMT is Since we want to adopt the cardinalities, describing the relation
as expressive as the original FM. Furthermore, all four types of features or groups of features to their parent node, we model
of cardinalities may be used on all levels of an FMT tree in a relation between Features and Compound Features
contrast to the much more restrictive approach of CT. by means of the class Dependency, which contains the
In addition, we allow cross-tree-constraints between all cardinality constraints as attributes (minimum and maximum
nodes of the FMT (line 8 in Table II). Finally, we adopt the cardinality).
node attributes and node types from feature modeling (line 9 Fig. 4 depicts an object diagram that shows how dependencies
and 10 in Table II). and cardinalities are used to distinguish between the four
different categories of subfeatures of Table II. A Feature is
B. Concept
We now describe the integration of FM and CT by means
of a metamodel depicted in Fig. 3. We developed this class
diagram on the basis of Table II. Please note that the depicted
class diagram is a small extract of the complete FMT meta-
model that illustrates the concept of the unified approach. It
does e.g. not contain any information concerning the test case
generation. The characteristics of the nodes of the FMT ap-
proach are described using the following classes: Compound Fig. 4. Object Diagram describing cardinality in FMT
Feature, Feature, and Atomic Feature. The last one
can either be a feature representing its property in form of always connected to its Compound Feature by a depen-
a literal or an interval. This is realized using the two classes dency. Therefore, Dependencies with different cardinalities
Literal and Interval. These classes may represent: can be placed beneath a Compound Feature.
• a value or a range of values of test parameters as known V. A PPLICATION
from equivalence classes in CTs In this section we briefly describe the application of our
• a value or a range of values of parameters needed for FMT approach by generating test cases for our running
product instantiation purposes example. Additionally, we discuss a tool, which is under
• the labels of features known from FMs. development in our research groups.
A. Generating a test case
We demonstrate the ability to derive products and test
cases on the basis of the FMT using our running example
depicted in Fig. 5. We now derive two different products
and present the handling of the parameters. The two products
differ because they use different types of engines which results
in different configurations. The 2.0 Turbo ECOTEC engine
allows a vehicle maximum speed of 240km/h and, therefore,
needs to be tested above 200km/h. The 1.6 ECOTEC engine
is limited to 192km/h and does not require the test instance
Fig. 3. Simplified metamodel of the unified approach for vehicle speeds above 200km/h. Therefore, when testing the
product containing the 1.6 ECOTEC engine, the equivalence
A node in the FMT can only be a Compound Feature or class representing a speed range between 201 and 250 km/h
a leaf node (Literal or Interval), because the classes has to be disregarded.
Feature and Atomic Feature are abstract. Compound For both instances we derived some example test cases, which
Feature, Literal, and Interval inherit properties from was done according to the well-known procedure described in
Feature. All nodes in the FMT may have a Type and an section II-C. In the following we will describe the FMT in
arbitrary number of Attributes. In a Type the information Fig. 5 which integrates the information of the FM of Fig.
of the data type of a feature is stored if existent. This is 1 and the CT of Fig. 2. Leaf nodes of the FMT, therefore,
important, for instance, to distinguish between parameters of either represent basic features of the Opel Insignia SPL or
an integer or real data type. Attributes can store any equivalence classes of (runtime) parameter values. All non-
information of the node. To obtain sufficient information to leaf nodes of the FMT are inherited from the FM of Fig. 1,
properly plan the test effort it is for example important for whereas leaf nodes are inherited from Fig. 1 and 2. The nodes
vehicle OEMs to embed information about realizing a feature of the new FMT have to be interpreted as follows:
Fig. 5. FMT of the running example
• All nodes below the sensors node represent optional The selection of a specific variant and associated test cases
or mandatory Opel Insignia sensors together with their is specified in a style adopted from CTs (due to lack of space
output parameter value definitions which are used as input the FMT metamodel of Fig. 3 does not cover these elements).
parameters for control function test cases. Different shapes on vertical lines are used to distinguish
• All nodes below the actors node represent available actors between the following three cases, when a certain feature or
(actuators) for the Opel Insignia such as different types parameter is selected:
of engines. Input parameters that control the behavior of
these actors have been omitted due to lack of space. These 1) square: selection at design time
missing parameters are output parameters of to be tested 2) circle: selection at installation time (flash time)
control functions. Specifications of their values can be 3) triangle: selection at runtime
used as oracles during the execution of test cases.
• A node like bending light represents a group of control
functions that shall be tested. Again due to lack of space The first two options correspond to the selection of a certain
we do assume that bending light consists of a single variant in an FM, whereas the third option corresponds to the
function only which consumes output values of a subset selection of test cases with parameter values in a CT.
of all sensors and produces input values for a subset of Regarding the bottom part of Fig. 5 we can see that the type
all actors defined in Fig. 6. of engine is of course selected at design time. The bending
Node attributes (which are not visualized in Fig. 5) are used light functionality can be added or removed by firmware
to distinguish these different categories of nodes of FMTs as updates as long as the optional rain light sensor is present.
well as for other purposes like the definition of additional node The fact that all presented variants with their associated test
selection constraints (cf. metamodel of Fig. 3). Furthermore, cases do contain the optional rain light sensor is implicitly
Fig. 5 shows that the optional bending light functionality still represented by the fact that all test cases possess a parameter
requires the optional rain light sensor (as well as all other value definition for this type of sensor (Wet or Dry). Black
mandatory sensors of our SPL). The fact that the bending triangles represent Wet and Dry values that are actually used
light control function also requires input values from the in a specific test case, whereas white triangles represent the
three other mandatory sensors is not visualized in Fig. 5. fact that the rain light sensor is present and computes output
A more realistic FMT splits the bending light functionality values that are not needed as input for the just regarded test
into a number of subfunctionalities such as curve light, rain cases. Finally, Fig. 5 shows that four of the six depicted test
light, city light, or highway light which have to be tested cases are related to the functionality of the bending light (black
separately. As a consequence we have to distinguish between bending light circles). In general, the distinction between black
features (functions, parameters, sensors, actors) that are part and white shapes related to other nodes of the FMT reflect the
of a regarded product instance, but irrelevant for a specific test information which features and parameter values are relevant
case, and features that are directly involved in a specific test for which test case. It consists of nodes describing the product
case. The test case specifications in the lower part of Fig. 5 line and nodes for the test cases. Test case values are depicted
use black and white shapes for these two different purposes. in brackets.
(graph transformations) can be used to implement automat-
ically executable FMT transformations. The last processing
step of Fig. 6 has been implemented by modifying an existing
Java implementation of a pairwise testing tool. The modified
implementation in addition takes all kinds of dependencies
between FMT nodes into account. The incorporation of CT-
parameter value selection heuristics dealing e.g. with illegal
or stress parameter equivalence classes (cf. Section II-C)
is subject of ongoing research activities. The same is true
for the first processing step depicted in Fig. 6. Right now
dependencies that capture the fact that certain features or
parameters interact from an implementation point of view
have to be added manually. The adaption of ideas how to
automatically derive this information from SPL architectures
or code is also subject to future research activities.
According to the approach described in [20] we use the
pairwise combination method to generate a representative set
of products. At this point the major advantages of the FMT
approach comes into play. We can generate the test cases
for the selected products semi-automatically as described in
Fig. 6. Using FMT for SPL testing
the previous section. To summarize, we benefit from several
advantages using FMT instead of FM. The FMT is more
precise than FM when it comes to parametrization and for each
B. Testing SPLs using FMT
product of the representative set we can derive the correspond-
In this subsection we describe in more detail how the FMT ing test cases semi-automatically. Likewise, the FMT describes
approach is used for SPL testing purposes, i.e. we sketch parameters explicitly, therefore, we can consider dependencies
a methodology how to generate the bottom part of Fig. 5 which only occur between certain values of parameters.
automatically. For this purpose we describe the current state
of development of our MoSo-PoLiTe project, which realizes VI. C ONCLUSION AND F UTURE W ORK
the test methodology described in [20], but use FMT instead Within this paper we have presented a new approach how
of FM. The generation of a representative set of products is to integrate SPL engineering with feature models (FMs) and
subdivided into three steps [20]. black-box testing of system functions with CTs. Our mo-
1) Adding dependencies derived from system architecture tivation for this line of research is based on the fact that
and code as additional edges in the FMT. both FM- and CT-based methods are, e.g., well established
2) Simplification of the FMT such that the resulting FMT in the automotive industry for embedded software system
uses a minimal set of modeling concepts. development purposes. On the one hand FMs are a suitable
3) Integrated selection of variants and runtime parameter modeling method to describe commonalities and variabilities
values using the pairwise combination approach of [20] of an SPL. CTs, on the other hand, support the generation of
Fig. 6 depicts the individual steps. We refer to [20] for further test cases, using equivalence classes of parameter values of a
details. To use the FMT approach we are currently developing regarded system function. We are not aware of any integrated
an FMT tool suite using MOFLON and GEF [10]. MOFLON approach that combines both methods for the generation of
is a meta-CASE tool for rapid development of CASE tools variants as test candidates and the associated test cases. Today,
and tool adapters [2] developed at the Technische Univer- FM-based methods are first used to select one variant after
sität Darmstadt. MOFLON supports model analysis, model the other; then for each of these variants a separate CT has
transformation, and model integration for standard modeling to be defined which is then used to guide the related test case
languages like UML or domain-specific modeling languages. selection process. The integration of FM and CT in the form of
The abstract syntax of the new FMT modeling language as the presented new FMT (Feature Model for Testing) method
well as its static semantics rules are described using the seems to be the perfect symbiosis of two very promising
OMG metamodeling approach supported by MOFLON, i.e. a and widely used techniques. The key advantages are: (1) we
combination of MOF 2.0 and OCL 2.0. Using this description use a single model for SPLs and test case generation, (2)
as input we can generate an FMT model repository imple- approaches known from FMs and CTs can still be applied,
mentation together with all specified static semantics rules and (3) generation algorithms of variants and test cases can
in Java. Furthermore, a generic text-oriented user interface be combined. We are currently working on different projects
for the definition of FMT instances is generated, too. The using FMT for SPL testing purposes including the BMBF
implementation of the user interface of a visual FMT editor project feasiPLe. Ongoing and future research activities will
on top of GEF is ongoing work. Model transformation rules address the following problems:
• Checking the consistency of the FMT with respect to [4] P. Clements and L. Northrop, Software product lines: practices and
an additionally available specification of the behavior of patterns. Boston, MA, USA: Addison-Wesley Longman Publishing
Co., Inc., 2001.
the studied system. The FMT needs to incorporate the [5] M. Conrad and A. Krupp, “An extension of the classification-tree method
complete functionality described in the specification. This for embedded systems for the description of events.” Electr. Notes Theor.
must be done before generating test cases. Comput. Sci., vol. 164, no. 4, pp. 3–11, 2006.
[6] K. Czarnecki, S. Helsen, and U. Eisenecker, “Staged configuration
• In embedded systems, our main application area, real- through specialization and multilevel configuration of feature models,”
time constraints play an important role. Furthermore, test Software Process: Improvement and Practice, vol. 10, no. 2, pp. 143–
cases often have to be executed in a specified order and 169, 2005.
[7] ——, “Formalizing cardinality-based feature models and their special-
continuous parameter values reflecting physical properties ization,” in Software Process: Improvement and Practice, 2005, pp. 7–
of a controlled system and its environment have to be 29.
synthesized from sequences of selected discrete parame- [8] K. Czarnecki, S. She, and A. Wasowski, “Sample spaces and feature
models: There and back again,” in SPLC ’08. Washington, DC, USA:
ter values using well-known interpolation methods. IEEE Computer Society, 2008, pp. 22–31.
• Defining a measure of completeness for the generated test [9] K. Czarnecki and A. Wasowski, “Feature diagrams and logics: There
scenarios with respect to an additionally available system and back again,” in SPLC ’07. Washington, DC, USA: IEEE Computer
Society, 2007, pp. 23–34.
behavior specification is challenging, too [26]. Complete- [10] G. E. F. (GEF). [Online]. Available: http://www.eclipse.org/gef/
ness checkers are useful to evaluate the generated test [11] M. Grochtmann and K. Grimm, “Classification trees for partition test-
cases and to find gaps and corner cases. ing,” Software Testing, Verification and Reliability, vol. 1993, pp. 63–82,
1993.
• The nodes of the FMT have to be extended to describe the [12] M. Janota and J. Kiniry, “Reasoning about feature models in higher-
cost of creating configurations and requirements priority order logic,” in SPLC ’07. Washington, DC, USA: IEEE Computer
which is essential for complex SPLs in the automotive Society, 2007, pp. 13–22.
[13] B. D. Jules White and D. C. Schmidt, “Selecting highly optimal
sector. architectural feature sets with filtered cartesian flattening,” Journal of
• We are currently applying our approach to several SPL Systems and Software to appear.
scenarios. These are real world examples and FMTs [14] K. C. Kang, S. G. Cohen, J. A. Hess, W. E. Novak, and A. S. Peterson,
“Feature-oriented domain analysis (foda) feasibility study,” Carnegie-
generated randomly. Mellon University Software Engineering Institute, Tech. Rep., November
• We apply the pairwise testing approach [20] to generate a 1990.
representative set of test cases and measure the coverage [15] K. R. P. H. Leung and W. Wong, “Towards a more efficient way of
generating test cases: Class graphs,” in APAQS ’00: Proceedings of
using appropriate and well known coverage metrics. the The First Asia-Pacific Conference on Quality Software (APAQS’00).
We focus on model checking techniques to address some of the Washington, DC, USA: IEEE Computer Society, 2000, pp. 285–293.
[16] S. Lützkendorf and K. Bothe, “Attributierte Klassifikationsbäume zur
problems stated above. Hence, another field of our research is Testdatenbestimmung,” Softwaretechnik-Trends, vol. 23, no. 1, 2003.
the use of model checkers for test case generation and FMT [17] J. D. McGregor, “Testing a software product line,” Tech. Rep. CMU/SEI-
validation. For this purpose, we need to develop a tool that 2001-TR-022, 2001.
[18] A. Metzger, K. Pohl, P. Heymans, P.-Y. Schobbens, and G. Saval,
is able to translate the FMT and the resulting test cases into “Disambiguating the documentation of variability in software product
boolean formulas, which can be evaluated by a model checker. lines: A separation of concerns, formalization and automated analysis,”
Methodologies to translate an FM into a boolean formula have in RE ’07. 15th IEEE International, 2007, pp. 243–253.
[19] E. M. Olimpiew and H. Gomaa, “Model-based testing for applications
already been introduced in [12], [9]. derived from software product lines,” in A-MOST ’05. New York, NY,
Finally, we have to address the problem that realistic complete USA: ACM, 2005, pp. 1–7.
FMT models cannot be displayed directly as depicted in [20] S. Oster and A. Schürr, “Architekturgetriebenes Pairwise-Testing für
Software-Produktlinien,” in Workshop SE ’09: Produkt-Variabilität im
this paper. Various methods have to be developed how to gesamten Lebenszyklus, March 2009.
collapse/hide irrelevant substructures efficiently. [21] K. Pohl, G. Böckle, and F. J. v. d. Linden, Software Product Line
Engineering: Foundations, Principles and Techniques. Secaucus, NJ,
ACKNOWLEDGMENT USA: Springer-Verlag New York, Inc., 2005.
[22] K. Pohl and A. Metzger, “Software product line testing,” Commun. ACM,
This work was partially funded by the feasiPLe project, vol. 49, no. 12, pp. 78–81, 2006.
[23] pure::systems. [Online]. Available: http://www.pure-systems.com
“Feature-driven, aspect-oriented and model-driven Software [24] S. Reis, A. Metzger, and K. Pohl, “Integration testing in software product
Product Line Development”, Federal Ministry of Education line engineering: A model-based technique,” in FASE, 2007, pp. 321–
and Research (BMBF), Germany. 335.
[25] A. Reuys, E. Kamsties, K. Pohl, and S. Reis, “Model-based system
testing of software product families,” in CAiSE, 2005, pp. 519–534.
R EFERENCES [26] K. Scheidemann, “Verifying families of system configurations,” Doctoral
[1] S. Alekseev, R. Tiede, and P. Tollkühn, “Systematic approach for using Thesis, vol. TU Munich, 2007.
the classification tree method for testing complex software-systems,” in [27] I. Stürmer, H. Dörr, H. Giese, U. Kelter, A. Schürr, and A. Zündorf, “Das
SE’07: Proceedings of the 25th conference on IASTED. Anaheim, CA, MATE Projekt visuelle Spezifikation von MATLAB Simulink/Stateflow
USA: ACTA Press, 2007, pp. 261–266. Analysen und Transformationen,” Dagstuhl Seminar Modellbasierte En-
[2] C. Amelunxen, A. Königs, T. Rötschke, and A. Schürr, “Adapting twicklung eingebetteter Systeme, Januar 2007.
FUJABA for Building a Meta Modelling Framework,” in Proc. 1st [28] A. Tevanlinna, J. Taina, and R. Kauppinen, “Product family testing: a
International Fujaba Days, H. Giese and A. Zündorf, Eds., vol. tr-ri- survey,” ACM SIGSOFT Software Engineering Notes., vol. 29, pp. 12–
04-247, 10 2003, pp. 29–34. 12, 2004.
[3] T. Y. Chen, P. L. Poon, and T. H. Tse, “A new restructuring algorithm for
the classification-tree method,” in STEP ’99. Washington, DC, USA:
IEEE Computer Society, 1999, pp. 105–114.