Model-driven Con guration of Function Net Families in Automotive Software Engineering

Abstract

Recent e orts in the automotive domain to initiate a paradigm-shift from a traditional hardware-driven to a function-driven development process create new challenges to tackle. A hardware-driven variant handling mechanism will get more and more inappropriate. Instead, new concepts and methods are necessary to model and con gure concrete systems. A software document which is used in the early phase of development is the so called function net model. Variability in function nets is captured implicitly and is strongly dependent on the hardware infrastructure, constraints are collected with informal annotations, and variants are generated manually. This results in a situation where function nets get too complex, time consuming and unsuitable for future standards. In this paper, we will present a model-driven approach for function nets to capture variability explicitly, to express formal constraints, and to generate concrete variants with the support of an automated con guration process. By this, it is possible to use the generated variants as skeletons for virtual prototyping, so that requirement speci cations can be veri ed e ciently.

-

Variability in automotive software engineering has achieved a degree of complexity which can no longer be handled with traditional hardware-driven methodologies [1{3]. Function net models are software documents which are used in an early phase of such a development process to describe the rst virtual realization of the system structure [ 4 ]. Typically, it consists of functional modules that interact via signals.

Variation points and their variants are captured implicitly by modeling a so called maximal function net model. The idea behind that is to capture every functional module, e.g., a sensor, an actuator, a control algorithm etc. In this way, a function net corresponds to an Electronic Control Unit (ECU) together with all its physical connections to bus systems, sensors, and actuators. Figure 1 illustrates two forms of a maximal function net model. Figure 1(a) represents a function net model speci ed in an Excel sheet, while Figure 1(b) is a visualization of this Excel sheet as graph. In both forms, it is very di cult or nearly impossible to extract useful information manually out of it. (a) Function net model as Excel sheet (cutout).

(b) Function net model as graph.

Communication dependencies between function nets, i.e., communication dependencies between ECUs, which have an in uence on variability are handled by using informal annotations. Variants are then generated manually by removing speci c parts of the function net with the help of these annotations. In a hardware-driven process, this can be regarded equally to removing hardware components such as ECUs, sensors, or actuators and the appropriate software portions. Any implications to other hardware and software components have to be solved manually.

Regarding the current trend in automotive software engineering, we can observe a paradigm-shift from a hardware-driven process to a function-driven process [ 5 ]. Therefore, a hardware-driven variant handling mechanism will get more and more inappropriate, because it gets too complex and is not suitable for future standards: it completely depends on the underlying hardware infrastructure, consistency has to be ensured manually, i.e., there is no formalization to express dependencies, and there is also no automated support to con gure and validate concrete variants.

In a research project at our department, we are providing new concepts, methods, and tools for handling complexity and variability in software documents for automotive software engineering [6{9]. We have developed a formal language to model function nets, and a formal language to model variation points and variants. Furthermore, we have integrated these two modeling languages in order to reduce synchronization overhead. Modeling guidelines, some of which can be checked on syntactical level and others which completely rely on behalf of the function net architect, are also provided. Moreover, methodology rules for the usage of such an integrated modeling language are also speci ed. What is still missing is the possibility to express constraints between functional modules or its signals inside one or many function net models. Furthermore, there is also a need to have an automated support to con gure concrete variants out of the family which also ensures the consistency. Because we are not only dealing with function net models but with several software documents, we need a con guration engine which is independent from the input language.

Including the missing concepts will enhance the development process in a way, that out of the family of function net models, we can generate skeleton variants for virtual prototypes (i.e., behavioral simulation on a PC). This allows an early and e cient veri cation of requirement speci cations.

In this paper, we will introduce an approach to express constraints in and between function net models. Furthermore, a con guration process is integrated which is coupled with an independent back-end inference engine. The output of the con guration process is a concrete variant of a function net.

The paper is structured as follows: Section 2 describes and motivates the problems in more detail. Here, we also illustrate an example which is used continuously in the whole paper. Section 3 and 4 include the main contribution of this paper. Here, we explain the language to express constraints and the whole con guration process. Section 5 describes related work and nally Section 6 concludes this paper. 2

Problem Description by Example

This section describes the initial situation of our approach that is relevant to explain the problems we are going to tackle and the contribution of this paper. Nevertheless, we will not describe the conceptual background but illustrate an example and refer to them appropriately.

Figure 2 shows an example of a function net model integrated with a variability model [ 6, 8 ]. It illustrates a part of a Central Locking System (CLS), with a Vehicle Access Controller (VAC), a Data Transceiver (DT), and a Central Locking Master (CLM). A VAC can lock (l) or unlock (ul) the vehicle. For this, it has to authorize itself with some authentication data (ad). To communicate between functional modules we use ports. Thereby, we distinguish between data ports, i.e., signals with a data storage characteristic, and control ports, i.e., signals initiating a functionality. In Figure 2 data ports are visualized with a rectangular shape, while control ports are visualized with a circle shape. Furthermore, these two types of ports are distinguished between provided and required ports. In Figure 2 provided ports are marked black, while required ports are marked white.

Variation points and their variants are captured in the variability model [ 6, 8 ]. For example, a VAC is a variation point, which has two variants, i.e., a Remote Control (RC) and an Identification Transmitter (IDT) for a more comfortable access. In the same way, a DT is also a point of variation which has for example Antennas (At) as variants. A further variant could be a key slot (not shown in Figure 2). Variation points have group cardinalities and variants have variant cardinalities in the same way as Czarnecki et al. have introduced [ 10 ]. For example, in Figure 2 the group cardinality [1..2] of VAC expresses that out of the captured variants at least one but at most two variants are needed for

VAC ad l ul

Function Net Model

a valid CLS. The variant cardinality [1..4] of At expresses that a valid CLS can have at least one but at most four instances of the variant. By using group and variant cardinalities it is possible to restrict valid systems. In the subsequent sections, we will see that this is not enough to express constraints.

Finally, variants can be speci ed more ne-grained (depicted with the dots in Figure 2). For example, ports and their connections can di er depending on the variant. For our explanations in this paper, we will not need them and therefore, they are neglected here.

As explained before, currently we cannot express more complex constraints between functional modules or its signals inside one or many function nets. Furthermore, an automated support to con gure concrete variants is also not possible. The next two subsections will describe the mentioned problems in more detail. 2.1

Expressing Constraints

In Figure 2, we have denoted two constraints for IDT (solid black line with arrow), i.e., the exclusion of RC if it is selected and the necessity of exactly four Ats. Please note that the exclusion can also be modeled with the expression of group cardinalities. This kind of constraints and obviously more complex constraints are often needed when modeling a family of function nets. As mentioned before, in our current prototype it is not possible to express more complex constraints which is a strong limitation of our integrated concept. Therefore, there is a need for an appropriate constraint language in order to express dependencies between variants.

An important requirement is that the language has su cient expressiveness. It should be possible to combine multiple variants and to formulate nested statements. It should also be possible to de ne constraints between di erent variability models. Another important requirement is that constraints should be reusable. Having gained experience in often used constraints, it should be possible to prede ne standard constraints and reuse them. Furthermore, the constraint language should not cause that much time-consuming training e ort for the con guration process. This minimizes error-proneness and enhance usability. 2.2

Con guration of Concrete Variants

Consider again Figure 2. We have depicted check boxes for the variability model to illustrate the con guration process. In the example, IDT is selected which requires exactly 4 Ats. Obviously, this is a valid con guration from which a concrete variant can be derived. The variant can then be used as skeleton for virtual prototypes to verify the requirements speci cation. Such a virtual prototype can for example be modeled with tools such as Matlab R Simulink R and State ow R [ 11 ]. In our current implementation such a con guration process is not supported.

There is a need for back-end con guration engine which infers valid variants. The con guration engine should be independent from the input language. This means, that it should be possible to handle di erent kind of models, such as function net models, Simulink models, and even source code. Furthermore, it should be possible to combine di erent models and process them as input. For this, the con guration process should be easily extendable and highly performant. 3

Design of Function Net Families with Constraints Because we do not plan to design a new constraint language, we have investigated literature to nd a suitable one that ful lls our requirements and is adaptable to our prototype. As one important requirement, we have identi ed that the constraint language should not cause additional expenses. Therefore, the selection of our language depends on the input language of the underlying con guration engine. As we will see in Section 4, we will use smodels as con guration engine which requires Weight Constraint Rule Language (WCRL) as input language [ 12 ]. Soininen et. al. have shown that WCRL has su cient expressiveness. It is also possible to reuse rules. Therefore, WCRL is a language that is suitable for our purposes. In this paper, we do not show the complete de nition of WCRL but limit it to a portion that is enough for the variability and function net model. For the complete de nition, please refer to the authors of WCRL [ 12 ].

A weight constraint rule is of the form (1) (2) C0

C1; : : : ; Cn; where Ci is a weight constraint which in turn is of the form

Ci = L fa1 = w1; : : : ; an = wng

U; where L; U 2 Z are lower and upper bounds, ai is a literal (atomic formula or predicate), and wi 2 N0 is a weight. where and A weight constraint Ci is satis ed for a set S i

L

X wi ai2S

U; (3) where S is a set of literals.

To illustrate WCRL consider again Figure 2. To express the exclusion of RC if IDT is selected, we can de ne a weight constraint rule as follows: ExcludeRC

IsSelectedIDT; ExcludeRC = 1 fInstOfType(X, RC) : InstDomain(X)g 0; IsSelectedIDT = 1 fInstOfType(X, IDT) : InstDomain(X)g 1:

The expression InstOfType(X, RC) : InstDomain(X) returns, out of the whole set of instances, i.e., the selected variants, a subset of a literals X which are of type RC (and a have default weight of 1). The same holds for IDT.

To express that exactly 4 Ats are needed if IDT is selected, we can de ne another weight constraint rule:

Exactly4Ats

IsSelectedIDT; where IsSelectedIDT is de ned as above, and

Exactly4Ats = 4 fInstOfType(Y, At) : InstDomain(Y)g 4:

In this way, it is possible to express formal constraints which are also processable by the con guration process which is presented next. 4

Con guration of Function Net Families A constraint language allows the restriction or precision of the con guration domain. We are now able to model a family of function nets and to express constraints across variants. What is still missing is a methodology and appropriate concepts to con gure a concrete variant out of the family. In this section, we will provide such a con guration process and explain the steps relevant for it.

Figure 3 gives an overview of the whole con guration process. The input document will be a function net family as shown in Figure 2 and the output document after con guration will be a comletely con gured function net. The con guration steps are (1) the selection of the variants in the variability model. This is done with the help of the integrated prototype [ 8 ]. The result of this step will be a function net family plus selected variants. Because WCRL is the input .fnf

Function Net Family

variant selection .fnf Function Net Family + selected variants

transformation n o it ifraug ssce.wcrl Function Net Family in WCRL con lrpo inference a n r te.wcrl configured Function Net in WCRL n i .fn

transformation configured Function Net Function Net Family Editor openArchitecureWare

smodels openArchitecureWare language for the back-end inference engine, we need (2) a transformation from the language of function net families to an equivalent model in WCRL which is the result of this step. The transformation rules are de ned with support of openArchitectureWare (oAW) [ 13 ]. The function net model in WCRL is the input for the inference engine smodels which (3) infers a con gured function net in WCRL. In order to visualize the result we (4) transform it back to the function net model. Note that steps (2)-(4) are internally processed so that a user does not notice them.

In the following subsections, we will explain the above outlined steps in more detail by illustrating them with the example of Section 2. We will start with step (2), i.e., a function net family plus selected variants which are transformed to a model in WCRL. Consider Figure 4. We have a family of function nets where WCRL constraints can be expressed (see Section 3) and in addition variants can be selected. In the example, we want to con gure an IDT and four Ats. As explained above, we rst have to transform the function net family to a model in WCRL.

The bottom part of the gure shows the result after transformation, i.e., a model in WCRL. For example, the functional module VAC is transformed to Function(VAC) <-. This is a short notation for a weight constraint rule where the right part is always true (and therefore empty). Such a rule is also called a fact. The information that VAC is also a variation point is captured in the next line. Furthermore, we need the association information between VAC as a

VAC ad l ul .wcrl

Function(VAC) <FunctionVP(VP.VAC) <FunctionIsVP(VAC, VP.VAC) <Variant(IDT) <FunctionVPHasVariant(VP.VAC, IDT) <-∞ ≤ {InstOfType(Y, RC): InstDomain(Y)} ≤ 0 <- 1 ≤ {InstOfType(X, IDT): InstDomain(X)} ≤ ∞ 4 ≤ {InstOfType(Y, At): InstDomain(Y)} ≤ 4 <- 1 ≤ {InstOfType(X, IDT): InstDomain(X)} ≤ ∞ 0 ≤ {InstOfType(X, IDT): InstDomain(X)} ≤ 1 <1 ≤ {InstOfType(X, IDT): InstDomain(X)} ≤ 1 <… Variant(At) <0 ≤ {InstOfType(X, At): InstDomain(X)} ≤ 4 <4 ≤ {InstOfType(X, At): InstDomain(X)} ≤ 4 <functional module and variation point. This is expressed in the third line. In the same way, variants of variation points, constraints, cardinalities, and selections are all transformed to WCRL.

To implement transformation rules, we have used the oAW framework, more precisely the component Xpand. Xpand is a template-based language to generate code based on EMF (Eclipse Modeling Framework) models [ 14 ]. Figure 5 illustrates an Xpand template that processes all variation points and variants of our integrated models (which are also based on EMF) and generates the appropriate WCRL code. Having now the model in WCRL, we can use the inference engine smodels to generate a valid con guration.

4.2 The Inference Engine: smodels

We have decided to use an independent inference engine, which is able to process combined models and has a reasonable performance. We will not present in this paper our classi cation and evaluation method for our decision, because it is still work in progress. But among all evaluated possibilities, smodels seems to be a good candidate [ 15 ]. In Section 5 we will give some arguments for our decision. 1. «DEFINE processVariationPoint FOR FunctionVariationPoint» 2. 3. 4. 5. 6. «FOREACH vcard.variants AS vars» 7. 8. 9. 10.

Variant(«vars.getId()») <FunctionVPHasVariant(«this.getId()», «vars.getId()») <«vcard.getLowerBound()» {InstOfType(X, «vars.getId()») :

InstDomain(X)} «vcard.getUpperBound()» <FunctionVP(«this.getId()») <

FunctionIsVP(«this.variableFunction.getId()», «this.getId()») <11. 12. 13. 14. «ENDDEFINE»

«ENDFOREACH»

Using smodels as back-end inference engine, a WCRL model is taken as input which then infers a con gured WCRL model as output (for the input from Figure 4). Figure 6 shows an example of the output. We have one instance IDT 1 of type IDT (line 1 and 2), and four instances of type At. Furthermore, all instances for ports and their connections are inferred. 4.3

Transformation to a Function Net Model

Finally, the result of smodels has to be transformed back to the function net model. Therefore, we again specify our transformation rules using oAW. We do not describe this in detail, because it is analogous as described in Subsection 4.1. Figure 7 illustrates the result of this step. The function net has now one instance of IDT and four instances of At, which all are connected appropriately. Note that in this model the complete variability is bind (there is no green colored functional module) and therefore it is a variant that can be used as a skeleton for virtual prototyping.

IDT_1 ad l ul

Function Net Model Variability Model

In terms of expressing constraints, two di erent approaches exist: structural/ graphical de nition and textual de nition. The former is usually adopted by con guration systems involving feature trees [ 16 ], and the possible relations include simple 'requires' and 'excludes' relations and cardinality constraints [ 10 ], and relations like 'recommends' or 'discourages' in some cases [ 17 ].The latter requires the use of a constraint language/logic, including OCL [ 18 ], WCRL [ 12 ], or Prolog [ 17 ] to express arbitrary logic formulas constraining the model, allowing less user-friendly yet much more expressive constraints. Among di erent languages, OCL has the advantage as the most well-known language since de ning complex constraints requires a considerable amount of pro ciency in the relevant language.

In [ 19 ] and [ 20 ], di erent methods for product con guration are summarized. Some are rule-based, logic-based and constraint-based con guration; the strengths and weaknesses of tools adopting di erent approaches are discussed in [ 21 ]. Answer Set Programming (ASP) [ 22 ] emerges to be an important and widely accepted means for product con guration, and is suitable for the representation of con guration knowledge [ 23 ]. Since the con guration task is NP-complete, performance of the inference engine seems to be important for medium to large scale models. There exist several solvers including pure ASP solvers such as smodels [ 15 ], DLV [ 24 ], and hybrid approaches integrated with SAT solvers such as ASSAT [ 25 ]. A theoretical comparison can be found in [ 26 ] and comparison of their performance in relevant sections of each paper and in [ 27 ].

Regarding the di erent ASP solvers, there exist considerable amount of data on using smodels, which has a long history of development and wide acceptance. It allows a direct integration into our con guration process with the use of WCRL as input language. In contrast, OCL requires an extra model transformation. However, we plan to integrate OCL into our con guration process in order to compare both in more detail. The disadvantage in performance and lack of advanced concepts (such as non-monotonic reasoning, learning, powerful heuristics) may be neglected considering the current scope of our work; and it is easy to migrate later to di erent engines with the same interface (WCRL I/O) for better performance. 6

Conclusion

In this paper, we have illustrated a model-driven approach to con gure an integrated variability and function net model. First, we have explained the need for a constraint language in order to restrict the con guration domain. Therefore, we have included WCRL as an appropriate language. Second, we have motivated the necessity for an independent back-end inference engine. Here, smodels seems to be a tool which is adaptable, extendable, and with high performance. We plan to start a benchmark where this can be evaluated more precisely.

The possibility to con gure concrete variants of function nets allow the generation of skeleton variants for virtual prototyping. For example, in this way, variants of Simulink models can be simulated in order to verify e ciently requirement speci cations in an early phase of a model-driven development process.

References

1. M. Broy , I. H. Kru ger, A . Pretschner, and C. Salzmann: Engineering Automotive Software . In Proceedings of the IEEE , pages 356 { 373 , 2007 .

2. K. Czarnecki and U.W. Eisenecker: Generative programming: methods, tools, and applications . Addison-Wesley, NY , USA, 2000 .

3. K. Pohl , G. Bockle, and F. J. van der Linden : Software Product Line Engineering: Foundations, Principles and Techniques. Springer, 2005 .

4. H. Wallentowitz and K. Reif (eds.): Handbuch Kraftfahrzeugelektronik: Grundlagen, Komponenten, Systeme, Anwendungen. Vieweg, Wiesbaden, 2006 .

5. AUTOSAR (AUTomotive Open System ARchitecture) Development Partnership . http://www.autosar.org. Last request: March 30 . 2010 .

6. C. Mengi and I. Armac: Functional Variant Modeling for Adaptable Functional Networks . In VaMoS 2009: Proceedings of the 3rd International Workshop on Variability Modelling of Software-Intensive Systems , pages 83 { 92 , Seville , Spain, 2009 .

7. C. Mengi and I. Armac: Ein Klassi kationsansatz zur Variabilita tsmodellierung in E/E-Entwicklungsprozessen. In Software Engineering 2009 Workshop: ProduktVariabilitat im gesamten Lebenszyklus (PVLZ 2009 ), KL, Germany, 2009 .

8. C. Mengi , A. Navarro Perez , and C. Fu : Modellierung variantenreicher Funktionsnetze im Automotive Software Engineering . In Proceedings of the 7th Workshop Automotive Software Engineering (ASE 2009 ), Lubeck, Germany, 2009 .

9. C. Mengi , C. Fu , R. Zimmermann , and I. Aktas: Model-driven Support for Source Code Variability in Automotive Software Engineering . In Proceedings of the 1st International Workshop on Model-driven Approaches in Software Product Line Engineering (MAPLE 2009 ), San Francisco, California, USA, 2009 .

10. K. Czarnecki , S. Helsen , and U. W. Eisenecker: Formalizing cardinality-based feature models and their specialization . In Software Process: Improvement and Practice , pages 7 { 29 , Vol. 10 , 2005 .

11. The Mathworks. http://www.mathworks.com/. Last request: March 30 . 2010 .

12. T. Soininen , I. Niemela, J. Tiihonen , and R. Sulonen : Representing Con guration Knowledge with Weight Constraint Rules . AAAI Technical Report SS-01-01 , 2001 .

13. openArchitectureware. http://www.openArchitectureware.org/. Last request: March 30 . 2010 .

14. Eclipse Modeling Framework. http://www.eclipse.org/modeling/emf/. Last request: March 30 . 2010 .

15. I. Niemela and P. Simons : Smodels - An Implementation of the Stable Model and Well-Founded Semantics for Normal LP . In LPNMR '97: Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning , pages 421 { 430 , London, UK, Springer-Verlag, 1997 .

16. K. C. Kang , S. G. Cohen , J. A. Hess , W. E. Novak and A. S. Peterson: FeatureOriented Domain Analysis (FODA) Feasibility Study . Technical Report: CarnegieMellon University Software Engineering Institute, 1990 .

17. pure::systems. http://www.pure-systems.com/. Last request: 30th March 2010 .

18. Object Constraint Language Speci cation Version 2.0 . http://www.omg.org/ technology/documents/formal/ocl.htm. Last request: March 30 . 2010 .

19. D. Sabin and R. Weigel : Product Con guration Frameworks - A Survey . IEEE Intelligent Systems , Vol. 13 , pages 42 { 49 , IEEE Educational Activities Department , NJ, USA, 1998 .

20. L. Hotz and T. Krebs: Con guration - State of the Art and New Challenges . In Proceedings of the 17th Workshop Planen , Scheduling und Kon gurieren, Entwerfen (PuK 2003 ), KI 2003 Workshop , pages 145 { 157 , 2003 .

21. M. Sinnema , and S. Deelstra: Classifying variability modeling techniques . Inf. Softw. Technol. , pages 717 { 739 , 7 , Newton, MA, USA, 2006 .

22. C. Anger , K. Konczak , T. Linke , and T. Schaub: A Glimpse of Answer Set Programming . Kunstliche Intelligenz , Vol. 19 , pages 12 { 17 , 1 , 2005 .

23. T. Soininen and I. Niemela: Developing a Declarative Rule Language for Applications in Product Con guration . In PADL '99: Proceedings of the First International Workshop on Practical Aspects of Declarative Languages , pages 305 { 319 , London, UK, Springer-Verlag, 1998 .

24. N. Leone , G. Pfeifer, W. Faber , T. Eiter , G. Gottlob, S. Perri , and F. Scarcello: The DLV system for knowledge representation and reasoning . ACM Trans. Comput. Logic Vol. 7 , pages 499 { 562 , 3 , New York, NY, USA, ACM, 2006 .

25. F. Lin and Y. Zhao: ASSAT: Computing Answer Sets of a Logic Program by SAT Solvers . Artif. Intell., Vol. 157 , Nonmonotonic Reasoning , pages 115 { 137 , 2002 .

26. E. Giunchiglia, N. Leone , and M. Maratea: On the relation among answer set solvers . Annals of Mathematics and Arti cial Intelligence Vol. 53 . pages 169 { 204 , 1 - 4 , Hingham, MA, USA, Kluwer Academic Publishers, 2008 .

27. T. Mancini , D. Micaletto , F. Patrizi , and M. Cadoli: Evaluating ASP and Commercial Solvers on the CSPLib . Constraints , Vol. 13 , pages 407 { 436 , 4 , Hingham, MA, USA, Kluwer Academic Publishers, 2008 .