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.