=Paper=
{{Paper
|id=Vol-1706/paper7
|storemode=property
|title=Heterogeneous Megamodel Slicing for Model Evolution
|pdfUrl=https://ceur-ws.org/Vol-1706/paper7.pdf
|volume=Vol-1706
|authors=Rick Salay,Sahar Kokaly,Marsha Chechik,Tom Maibaum
|dblpUrl=https://dblp.org/rec/conf/models/SalayKCM16
}}
==Heterogeneous Megamodel Slicing for Model Evolution==
https://ceur-ws.org/Vol-1706/paper7.pdf
Heterogeneous Megamodel Slicing for Model Evolution
Rick Salay Sahar Kokaly Marsha Chechik
Department of Computer McMaster Centre for Software Department of Computer
Science Certification Science
University of Toronto McMaster University University of Toronto
Toronto, Canada Hamilton, Canada Toronto, Canada
rsalay@cs.toronto.edu kokalys@mcmaster.ca chechik@cs.toronto.edu
Tom Maibaum
McMaster Centre for Software
Certification
McMaster University
Hamilton, Canada
maibaum@mcmaster.ca
ABSTRACT utilizing their corresponding type-specific model slicers; and
Slicing is a widely used technique for supporting comprehen- (3) it uses the widely adopted notion of traceability relations
sion and assessing change impact during software evolution to assess change impact between models. We then analyze
activities. While there has been substantial research into the proposed algorithm for termination, correctness, running
the slicing of particular model types, model-based software time and minimality.
development typically involves heterogeneous collections of The remainder of this paper is structured as follows. In
related models and there is little work addressing slicing in Sec. 2, we give a motivating example from the automotive
this context. In this paper, we propose a generic slicing ap- software domain. In Sec. 3, we recall the background needed
proach for “megamodels” – a well-known model management for the slicing approach and in Sec. 4, we describe the pro-
technique for representing and manipulating collections of posed slicing algorithm and its analysis. Then, in Sec. 5, we
models and relationships between them. Our approach ex- give a detailed illustration of the algorithm on the automo-
ploits existing model slicers for particular model types as tive example. In Sec. 6, we discuss related work and finally,
well as the traceability relationships between models to ad- in Sec. 7, we give our conclusions and report on future work.
dress the broader heterogeneous model slicing problem. We
illustrate our approach on an example of evolution in model-
based automotive software development. 2. MOTIVATING EXAMPLE
Consider an automotive subsystem that controls the be-
haviour of a power sliding door in a car. The system has an
Keywords Actuator that is triggered on demand by a Driver Switch.
Evolution, model slicing, model management, megamodels. This example is presented in Part 10 of the ISO 26262 stan-
dard [12]. Refer to Fig. 1 which shows the system models
comprised of a Class Diagram (to model its structure), a Se-
1. INTRODUCTION quence Diagram (to model its behaviour) and a relationship
Slicing is a widely used technique for supporting soft- between them. This can be visualized at a high-level as the
ware evolution activities [19]. Specifically, static slicing [26] megamodel (to be defined in Sec. 3) in Fig. 2.
can identify the subset of software that is semantically de- The Driver Switch input is read by a dedicated Electronic
pendent on a specific portion that has or is planned to be Control Unit (ECU), referred to as AC ECU, which powers
changed and hence is useful for assessing change impact due the Actuator through a dedicated power line. The vehicle
to evolution. In the MDE context, model slicing has been equipped with the item is also fitted with an ECU which is
studied for particular model types, e.g., State Machines [16, able to provide the vehicle speed (VS). This ECU is referred
18], Class Diagrams [13, 18], etc. However, large-scale soft- to as VS ECU. The system includes a safety element, namely,
ware systems are often described using heterogeneous col- a Redundant Switch. Including this element ensures a higher
lections of interrelated models, and change impact analysis level of integrity for the overall system.
requires a broader slicing approach that can address this. The VS ECU control unit provides the AC ECU with the vehi-
While some work has addressed slicing for heterogeneous cle speed. The AC ECU monitors the driver’s requests, tests if
model collections, these have been limited to a specific set of the vehicle speed is less than or equal to 15 km/h, and if so,
model types (e.g., [20]) or remain at a theoretical level (e.g., commands the Actuator. Thus, the sliding door can only
[7]). In this paper, we propose a general and pragmatic be opened or closed if the vehicle speed is no more than 15
static slicing algorithm for heterogeneous model collections. km/h. The Redundant Switch is located on the power line
Specifically, (1) it operates on “megamodels” – a general between the AC ECU and the Actuator as a secondary safety
modeling technique to represent collections of interrelated control. It switches on if the speed is less than or equal
models; (2) it can work with arbitrary model types (e.g., to 15 km/h, and off whenever the speed is greater than 15
conceptual, behavioural, goal models, test models, etc.) by km/h. It does this regardless of the state of the power line
50
PowerSlidingDoor: SD
!"#$%&'()*'+,-' .%#$%&(/,'+,-' .(/%0&.012' 3"'(425!$2'*650%7' "(8$3&93.90'*650%7'
par s.requestSpeed()
PowerSlidingDoor: CD
requestDoorOpen() getSpeed(sensed_speed) request Speed() [if s.sensed_speed<=15] s.closed else s.open
requestDoorClose() sensed_speed: Real closed: Boolean
sensed_speed: Real ds.requestDoorOpen()
R: CD-SD
communicatesWith ac_ecu.requestSpeed()
communicatesWith communicatesWith controls
ac_ecu.sensed_speed
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.openDoor()
requestSpeed() powers openDoor() controls
open:Boolean
sensed_speed: Real closeDoor()
powered: Boolean
ds.requestDoorClose()
activated: Boolean
ac_ecu.requestSpeed()
ac_ecu.sensed_speed
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.closeDoor()
Figure 1: Power sliding door system models.
than a slice operator for state machines.
CD-SD
!"#$%&'()(*+,""%-./,. !"#$%&'()(*+,""%-.&,.
Megamodels. To help visualize and work with collections
of models and their relationships, model management uses a
special type of model called a megamodel [3]. In this paper,
Figure 2: Power sliding door system megamodel. we define this and related concepts as follows.
Definition 1 (Megamodel). A megamodel is a model
(its power supply is independent). The Actuator operates
with elements representing models and links between ele-
only when it is powered.
ments representing relationships between the models.
Now, consider that the power sliding door system changes
and the redundant switch is removed. This could be due to
Fig 3 shows the simplified metamodel used for megamod-
the need to minimize cost and produce a cheaper vehicle.
els in this paper. A Megamodel consists of a graph of named
In the new system, only the AC ECU checks the vehicle speed
and typed Model elements with Relationship links connect-
before commanding Actuator. In this case, it would be de-
ing them. These refer to models and model relationships
sirable to provide a sliced megamodel of the system that
(defined below), respectively, and the types indicate their
reflects the parts of the original megamodel affected by this
metamodels. The well-formedness constraint requires that
change in order to help with system evolution activities. For
the models on either end of every relationship are distinct.
example, we shown that with safety-critical software, such
We have made the simplifying assumptions that (1) all rela-
as for automotive systems, a system megamodel slice is an
tionships are binary; and (2) megamodels cannot be nested
essential part of re-assessing the safety assurance of the sys-
or reference other megamodels. In Sec. 4.3, we discuss how
tem [15].
are these assumptions can be relaxed.
After presenting our slicing approach, we demonstrate it
Fig. 2 shows a megamodel for our power sliding door ex-
on the power sliding door example in Sec. 5.
ample. Here, PowerSlidingDoor : CD and PowerSliding−
Door : SM refer to the Class Diagram and Sequence Diagram,
3. BACKGROUND AND PRELIMINARIES respectively, while the line connecting them refers to the re-
lationship of type CD − SD for connecting these two types of
3.1 Megamodeling and Model Management models. Note that relationship names are optional.
A complexity problem in MDE arises due to the prolif-
eration of software models, and the area of Model Manage- Definition 2 (Model). A model is set of typed ele-
ment [2] has emerged to address this challenge. Model man- ments and links conforming to a metamodel. We use the
agement focuses on a high-level view in which entire mod- term atom to denote either an element or a link.
els and their relationships (i.e., mappings between models)
can be manipulated using operators (i.e., specialized model Definition 3 (Model relationship). A model rela-
transformations) to achieve useful outcomes. In this pa- tionship connecting models M and M ′ consists of a set of
per, we focus on one of the model management operators – typed links conforming to a metamodel. Each link connects
model slice [20]. Other model management operators that atoms of M to atoms of M ′ .
have been studied include match [2], diff [2], lift [23], and
merge [6]. Each of these model management operators can Definition 4 (Traceability relationship). A trace-
be viewed as an abstract transformation that defines a class ability relationship is a model relationship in which the links
of concrete transformations, i.e., the implementations that express a dependency relationship between the atoms it con-
refine the operator for particular model types. For example, nects. The dependency relationship can be unidirectional or
a slice operator for class diagrams is implemented differently bidirectional depending on the type of traceability link.
51
Megamodel In this paper, we focus on static forward slicing since it is
readily applicable to assessing the impact of changes due to
model evolution. We define this as follows.
*
Node Definition 7 (Static forward model slice). Given
name a model M and model fragment S[M ], the static forward
type slice of M with respect to the slicing criterion S[M ] is the
model fragment S ′ [M ] satisfying the following conditions:
1. (Correctness) S ′ [M ] contains all atoms of M that are
2 directly or indirectly dependent on atoms of S[M ].
Model end Relationship
2. (Minimality) Every atom of S ′ [M ] is either directly or
indirectly dependent on atoms of S[M ].
Well formedness constraint:
ܴ ڄ ݄݅ݏ݊݅ݐ݈ܴܽ݁ א ܴǤ ݁݊݀ ͳ ് ܴǤ ݁݊݀ሾʹሿ Note that since S[M ] is dependent on itself, these conditions
imply that S[M ] ⊆ S ′ [M ].
Figure 3: (Simplified) metamodel for megamodels.
4. MEGAMODEL SLICING
Note that the definition of traceability relationship used In this section, we propose a slicing approach for heteroge-
in this paper is broader than that typically used by require- neous megamodels. Intuitively, such a slicer should allow the
ments engineering [11] and narrower than what is sometimes criterion to be expressed as a megamodel fragment and the
used for general modeling [1]. We focus solely on traceability forward slice should expand this to the megamodel fragment
relationships and use them to determine cross-model depen- containing all dependent elements. We generalize Def. 7 to
dencies. In fact, we assume that the only relationships in the capture this intuition.
megamodels are the traceability relationships. In Sec. 4.3,
we discuss how this assumption can be relaxed. Definition 8 (Static forward megamodel slice).
Given a megamodel X and megamodel fragment S[X], the
Definition 5 (Model fragment). A model fragment static forward slice of X with respect to slicing criterion
S of a model M , denoted S[M ], is any subset of atoms of S[X] is the megamodel fragment S ′ [X] satisfying the follow-
M. ing conditions for all M ∈ X:
Definition 6 (Megamodel fragment). A megamodel 1. (Correctness) There exists a model fragment S ′ [M ] ∈
fragment S of a megamodel X, denoted S[X], is any set of S ′ [X] that contains all atoms of M that are directly or
model fragments of the models in X. We say that S[X] is indirectly dependent on the atoms of any model frag-
contained in S ′ [X], denoted S[X] ⊑ S ′ [X], iff the following ment in S[X].
condition holds:
2. (Minimality) If there exists a model fragment S ′ [M ] ∈
′
∀M ∈ X·∪{S[M ]|S[M ] ∈ S[X]} ⊆ ∪{S [M ]|S [M ] ∈ S [X]} ′ ′
S ′ [X], then every atom of S ′ [M ] is either directly or
indirectly dependent on the atoms of some model frag-
Thus, S[X] ⊑ S ′ [X] when, for each model M ∈ X, the ment in S[X].
combined model fragments of M in S[X] is contained in
the combined model fragments of M in S ′ [X]. Note that There are two levels of expansion in this slicing process:
a megamodel fragment is defined as containing only model (1) expansion within individual models to dependent ele-
fragments and no relationships between them. ments and, (2) expansion between models across relation-
ships to dependent elements in neighbouring models. This
3.2 Model slicing two-level process is repeated until it produces no further
Program slicing, and, correspondingly, model slicing ap- expansion. For (1), we leverage existing type-specific slicers
proaches, fall into four categories: static, dynamic, condi- that take the semantics of the individual model types into ac-
tional and amorphous [7]. In each case, we are given a count. For (2), we use the links in traceability relationships
model and a slicing criterion indicating some “aspect of in- to connect dependent elements. Here, no special relationship-
terest” in the model, and the slicing process produces a slice type specific slicers are needed since all relationship types
of the model that addresses the criterion. Static slicing uses are assumed to be sets of links and every link is assumed to
a model fragment as the criterion. A forward slice expands represent a dependency.
the criterion to all dependent atoms while a backward slice Note that this definition of slicing is a deep slicing since the
expands to all depending atoms. While static slicing uses process includes the content of the models and relationships
a subset of the syntax as a criterion, dynamic slicing uses referenced by the elements of the megamodel. In contrast,
a constraint from the semantic domain. For example, dy- a shallow megamodel slicing would be one that only con-
namic slicing can be used to identify the classes used in a sidered the elements of the megamodel and not what they
particular run of a program. Conditional slicing combines reference. Here, a subset of a megamodel (the criterion) is
both static and dynamic approaches by allowing a hybrid expanded to the subset that is connected directly or indi-
criterion. Finally, while the first three types of slicing pro- rectly via relationship links (the slice), i.e., the shallow slice
duce a slice that is a fragment of the model, amorphous is the largest subset contained in the transitive closure of the
slicing allows the slice to be a different model. For example, initial subset taken along relationship links. There may be
the approach used in [20] adds stuttering transitions to state some use cases in which shallow megamodel slicing is useful
machine slices in order to preserve behaviours. but in this paper we focus on the deep version.
52
4.1 Slicing algorithm
Algorithm: Forward Megamodel Slice
Fig. 4 gives the algorithm for forward slice. The input is
Input: megamodel X, criterion megamodel fragment Sc [X]
megamodel X with megamodel fragment Sc [X] given as the
Output: slice megamodel fragment S[X]
slicing criterion. The output is megamodel fragment S[X]
1: S[X] := Sc [X]
representing the forward slice. The algorithm makes the
2: do {
following assumptions:
3: S ′ [X] := S[X]
Assumption 1. For each model type T represented in X, 4: S1 [X] := ∅
we have a slicer SliceT for models of type T that satisfies 5: for (S[M ] ∈ S[X]) {
Def. 7. 6: T := M.type
7: S1 [M ] := SliceT (M, S[M ])
Assumption 2. The set of traceability relationships in X 8: S1 [X] := Union(S1 [X], {S1 [M ]})
express all and only the direct dependencies between atoms 9: }
of models in X. 10: S2 [X] := ∅
11: for (S1 [M ] ∈ S1 [X]) {
In addition, we require several simple supporting opera- 12: for (R ∈ M.end) {
tions. 13: M ′ := OppEnd(R, M )
14: S2 [M ′ ] := Trace(R, S1 [M ])
Definition 9 (Union). Given a pair of megamodel frag- 15: S2 [X] := Union(S2 [X], {S2 [M ′ ]})
ments S1 [X], S2 [X], the megamodel fragment union, de- 16: }
noted Union(S1 [X], S2 [X]), is defined with the following con- 17: }
dition. 18: S[X] := Union(S1 [X], S2 [X])
19: } until (S[X] ⊑ S ′ [X])
∀S[M ] ∈ Union(S1 [X], S2 [X])· 20: return S[X]
S[M ] = ∪{S ′ [M ]|S ′ [M ] ∈ S1 [X] ∪ S2 [X]} Figure 4: Algorithm for forward megamodel slice.
Thus, the Union(S1 [X], S2 [X]) can be constructed by first After the two levels of expansion, the combined result is
taking the set union S1 [X] ∪ S2 [X] and then unioning all computed in line 18 and checked to see if any actual expan-
model fragments of the same model within this. sion has occurred (line 19). If no expansion has occurred, a
fixed point has been reached and the main loop exits with
Definition 10 (Trace). Given a traceability relation-
the current slice returned as the final result in line 20; oth-
ship R with ends M and M ′ , and model fragment S[M ],
erwise, the main loop repeats.
the trace of S[M ] along R, denoted Trace(R, S[M ]) is the
model fragment S ′ [M ′ ] consisting of the subset of atoms in 4.2 Analysis
M ′ dependent on the atoms in M according to R.
We consider the issues of termination, complexity and cor-
We compute Trace(R, S[M ]) by following the links of R rectness for forward slice algorithm in Fig. 4.
from the atoms of M to the atoms of M ′ . Termination. We show that the slicing algorithm is guar-
anteed to terminate. After the level 1 expansion loop com-
Definition 11 (OppEnd). Given a traceability relation- pletes (lines 5-9), it is clear that S ′ [X] ⊑ S1 [X] since S1 [X]
ship R with ends M and M ′ , we define OppEnd(R, M ) = M ′ is constructed by expanding each model fragment in the cur-
and OppEnd(R, M ′ ) = M . rent slice S[X] using type-specific slicers (see Assumption 1)
and doing Union (see Def. 9). Furthermore, S ′ [X] = S[X]
In line 1 of the algorithm, the current slice is initialized (line 3). Then, in line 18, when the new slice is computed,
to the criterion. The two levels of expansion are in lines 4-9 S1 [X] ⊑ S[X] since Union cannot produce a result smaller
and lines 10-17, respectively, inside the main loop of lines than its arguments. Therefore, S ′ [X] ⊑ S[X]. Thus, on line
2-19. For level 1, the temporary result S1 [X] is initialized in 19, either no expansion has occurred (S[X] ⊑ S ′ [X]) and
line 3 to the empty set and then lines 5-9 iterate through the the algorithm terminates or some expansion has occurred
model fragments in the current slice. In line 7, the model and the loop iterates again. Thus, in each iteration, the
type-specific slice is computed using the model fragment as current slice can only get larger and since this process is
the criterion and the result is accumulated in S1 [X] (line 8). bounded by X, the algorithm must terminate.
The level 2 expansion temporary result S2 [X] initialized
on line 10. The outer iteration (lines 11-17) is over the model Time Complexity. The level 1 loop (lines 5-9) can iterate
2
fragments from the level 1 expansion, and the inner iteration NM times and the level 2 loop (lines 11-17) can iterate NM
(lines 12-16) is over each relationship connected to the model times where NM is the number of models in X. The domi-
fragment. Note that the set of relationships connected to a nating operation in the level 1 loop is the type-specific slicer.
model fragment S1 [M ] is the set of relationships connected Since the time complexity varies according to the slicer used,
to M via the end property (see Fig. 3). For each such re- we represent it using a type-independent upper bound SL(n)
lationship R, we first determine the model M ′ on the other as a function of the number of elements n in the input model.
end of the relationship using supporting function OppEnd in Tracing along a relationship and union (lines 14-15) is O(Na )
line 13. Then in line 14, the model fragment S2 [M ′ ] is pro- in the worst case, where Na is the total number of atoms
duced by tracing the links in R from S1 [M ] to M ′ . Finally, across all models of X. Thus, in the worst case, one iter-
2
in line 15, this result is accumulated in S2 [X]. ation of the main loop is O(NM × SL(Na ) + NM × Na ).
53
Finally, in the worst case, the size of the current slice can missing endpoint class will make it well-formed.
increase by one in each iteration of the main loop, for Na The problem with doing this expansion is that atoms can
iterations. Thus, the time complexity is given by: be added that are not dependent on the criterion since, if
2
they were dependent, then they would already be in the slice.
O(Na × NM × SL(Na ) + NM × Na2 ) In particular, if SliceT used in line 7 of the slicing algorithm
always included an expansion to well-formedness then in the
Correctness. We argue that the slicing algorithm satis- subsequent steps of the algorithm the atoms added for well-
fies the correctness condition in Def. 8. Assume that the formedness would be treated as though they were atoms
algorithm is at line 3 and there exists a non-empty set of added for dependency. This would result in a non-minimal
atoms not in the current slice S[X] that are dependent on megamodel slice. As a result, we view the expansion to well-
atoms of model fragments in S[X]. Note that if some atom formedness as an optional post-processing step that could be
a is indirectly dependent on an atom a′ , then there must be applied after the megamodel slice is computed.
a sequence of directly dependent atoms a, a1 , ..., an , a′ con- A similar argument can be made about the issue of refer-
necting them. Thus, there must also be a non-empty set of ential integrity. Assume that one atom references another,
atoms not in S[X] that are directly dependent on atoms of e.g., a lifeline in a sequence diagram references the class of
model fragments in S[X]. Let us choose one such atom a′ in the object that the lifeline represents. The referenced class
some model M ′ in X that is directly dependent on an atom is not dependent on the referencing lifeline; thus, if the for-
a in some model fragment S[M ] in S[X]. We consider the ward slice includes the lifeline, it need not contain the class.
two cases: M ′ = M and M ′ 6= M . However, it may be desirable to expand the slice to include
Case 1). If M ′ = M , then by Assumption 1, the slicer the class to provide relevant contextual information for the
used in line 7 satisfies the correctness condition in Def. 7 and lifeline. As with well-formedness, this referential integrity
thus, atom a′ will be added to a model fragment in S1 [X] expansion can introduce atoms that are not dependent on
in an iteration of the level 1 loop (lines 5-9). the criterion and thus such an expansion should only be done
Case 2). If M ′ 6= M , then by Assumption 2, there is a as a post-processing step on the slice.
traceability relationship R in X with a link that connects a
Generalizing the slicing algorithm. In Sec. 3, we made
to a′ and thus, line 14 will cause a′ to be added to a model
several simplifying assumptions in order to focus on the core
fragment in S2 [X] in an iteration of the level 2 loop (lines
aspects of the slicing algorithm. We now briefly discuss how
11-17).
to relax these assumptions.
In either case, the atom a′ will enter the next iteration
• N-ary Relationships. We have assumed that all re-
of the slice in line 18. Furthermore, since the addition of a′
lationships in the megamodel are binary but it is straight-
expands the slice, the main loop will iterate again and will
forward to extend the algorithm to handle N-ary relation-
capture the next set of directly dependent atoms, and so
ships. Specifically, the iteration through the relationships
on. When the set of directly dependent atoms not in S[X]
(lines 12-16) must be generalized to handle the case where a
is empty, no further level 1 or level 2 expansion is possible,
traceability link holds between atoms in models on multiple
and the algorithm terminates.
ends, and the supporting operations OppEnd and Trace must
Minimality. We show that the slicing algorithm satisfies be adapted to address this.
the minimality condition in Def. 8. To do this, we must • Nested megamodels. In the general case, a meg-
show that the slice produced by the algorithm contains no amodel can contain other megamodels. Such a megamodel
atom that is not dependent on the criterion. Assume that could be viewed as a tree with models as leaves and nested
there is an atom a′ in the final slice that is not dependent on megamodels as intermediate nodes. A megamodel fragment
the criterion. In this case, a′ must have been added to the is a tree with the same structure but with model fragments
slice on line 7 or line 14 in some iteration of the main loop. as leaves. Thus, the algorithm follows a similar approach as
However, by Assumption 1 and Def. 7, SliceT can only currently but in addition it must preserve the megamodel
produce minimal model slices in line 7 and so a′ could not tree structure in the final slice.
have been added there. Also, by Assumption 2, traceability • Arbitrary relationships. We have assumed that all
relationships only contain links between true dependencies relationships are traceability relationships since these are
and in line 14, Trace is applied from the current slice to the only ones that matter to the slicing algorithm. In gen-
these dependent atoms. Thus, a′ could not have been added eral, however, there may be other types of relationships in
at line 14. Therefore, we have a contradiction and so the the megamodel, e.g., refinement, overlap, etc. The simplest
megamodel slice must be minimal. way to allow these relationship types is to ignore all non-
traceability relationships in the loop in lines 12-16.
4.3 Discussion
5. POWER SLIDING DOOR EXAMPLE
Well-formedness and referential integrity. Def. 7 does In this section, we demonstrate our slicing approach on
not require that a slice be a well-formed model. However, the power sliding door example presented in Sec. 2.
in practice, ensuring that a slice is well-formed may be de-
sirable because the slice can be used directly by tools such 5.1 Megamodels of class and sequence diagrams
as editors, analyzers and transformations. Making a model For the purpose of the example presented here, we instan-
fragment into a well-formed model requires it to be expanded tiate our general framework such that its input is a system
by a minimum number of atoms in order to satisfy the well- megamodel X given by a class diagram CD, a sequence di-
formedness constraints. For example, if a CD fragment con- agram SD, and a relationship CD − SD between them. Note
tains an association without one of its endpoints, adding the that, although these are both UML diagrams, we are treat-
54
Table 1: Dependency relations for CD and SD slicers.
Rule Component under assessment Dependant parts potentially impacted
Owned attributes and methods.
Associations connected to class.
CD1 Class
Attributes/methods in other classes using types introduced in this class.
Subclasses.
SD1 Term (portion of an expression) Associated expression.
SD2 Expression (guard/action) Associated message.
SD3 Message Associated arrow (from source to target lifeline).
Arrows directly after the arrow in the sequence.
SD4 Arrow
Message on the arrow.
Arrows connected to the lifeline.
SD5 Lifeline
Messages on arrows connected to the lifeline.
ing them separately for the sake of this example. In general, the Redundant Switch class from the CD. This change repre-
not all models in a megamodel have to be UML diagrams. sents our slicing criterion given by the megamodel fragment
Assume we are given some known change on the meg- with detail shown in Fig. 5. Note that only the class itself is
amodel, which represents the slicing criterion Sc [X] used as considered for the impact assessment and not its methods,
input to our algorithm. As stated in Sec. 4, we also as- attributes and associations linked to it.
sume that we are provided with correct class diagram and We now demonstrate the application of the forward meg-
sequence diagram model slicers similar to those presented in amodel slice algorithm presented in Fig. 4 on the megamodel
[18] and [21], respectively. PSD and the criterion megamodel fragment Sc [PSD].
For simplicity, we define our own CD and SD slicers for this
example as follows: Line 1 (Initialization): The current slice is initialized to
• CD slicer works with the dependency rule shown as CD1 in the criterion Sc [PSD] shown as the highlighted parts of Fig. 5.
Table 1: If a class is being considered for impact assessment, 1st iteration of the outer loop (lines 2-19):
then all of its attributes, methods, associations linked to it
and its subclasses are considered dependant on it and could Lines 4-9 (Expansion Level 1): The temporary result
potentially be impacted. They are therefore to be added in S1 [PSD] is initialized to the empty set. Then in lines 5-9,
the slice. we iterate through the model fragments in the current slice
• SD slicer works with the dependency rules shown as shown in Fig. 5. The CD is considered first and the CD slicer
SD1 − SD5 in Table 1: If a term, i.e., any portion of an ex- is used. Based on the dependency rule CD1 in Table 1,
pression (e.g., a guard or an action) in a message, is being since the Redundant Switch class is being impacted, all
considered for impact assessment, then its associated expres- of its attributes and methods are added to the slice and
sion could be impacted. Similarly, if an expression (e.g., a stored in S1 [PSD] on line 8. Since there are no other model
guard or an action) is being considered, its associated mes- fragments to consider on line 5, the loop exits with S1 [PSD]
sage should be included in the slice. Other rules for impact as shown by the highlighted parts in Fig. 6.
assessment of messages, arrows and lifelines are shown in
the table. Lines 10-17 (Expansion Level 2): Up to this point,
Note that both slicers satisfy Def. 7, i.e., they are correct R : CD − SD has not been considered in the slicing. In this
and minimal. We also assume that the set of traceability expansion level, we do use it. First, the level 2 expan-
relationships in CD − SD expresses all and only the depen- sion temporary result S2 [PSD] is initialized on line 10 to
dencies between the CD and SD in our system megamodel. the empty set. The outer iteration (lines 11-17) is over
the model fragments from the level 1 expansion. We first
5.2 Slicing of Power Sliding Door megamodel consider the CD. On the opposite end of R : CD − SD is the
Recall the Power Sliding Door megamodel presented in PowerSlidingDoor : SD (which is M ′ in the algorithm on
Fig. 2 which we refer to as PSD. The models represented by line 13). On line 14, we trace through R : CD − SD and add
PSD are in Fig. 1. to S2 [M ′ ] all the atoms related to those highlighted in the
There are three threads running in parallel in the se- CD. This includes the Redundant Switch object and lifeline
quence diagram: the top thread describes the behaviour of and all messages (or parts of them) that are traced back to
the Redundant Switch; the middle thread describes the be- attributes/methods of the Redundant Switch class in the
haviour when the driver requests to open the door, and the CD. The result is added to S2 [PSD] on line 15 and can be
bottom thread describes the behaviour when the driver re- seen in the highlighted parts of the SD in Fig. 7. Since no
quests to close the door. The relationship R : CD − SD is a other model fragments exist in S1 [PSD] on line 11, the loop
unidirectional traceability relationship (refer to Sec. 3) that exits.
goes from SD to CD, since the objects and terms of SD are Line 18: The combined result S[PSD] is computed by com-
dependent on classes, attributes and methods in CD. The puting the union of the results of the level 1 and level 2
traceability between the two models is given implicitly by slices, and can be seen as the result of the 1st iteration of
the SD referencing parts of the CD. the algorithm in the highlighted parts of Fig. 7.
As described in Sec. 2, let us consider a scenario where the
system changes, and the redundancy is removed by deleting
55
PowerSlidingDoor: SD
$45%*16,'&-./& 2*5%*160.&-./& 260*)12)3"& 746!"#$%"&'(#)*+& 468%719729)&'(#)*+&
par s.requestSpeed()
PowerSlidingDoor: CD
!"#$%"&'(#)*+& ,'&-./& !"#$%#&%'()*+',-(
requestDoorOpen() getSpeed(sensed_speed) request Speed() [if s.sensed_speed<=15] s.closed else s.open
requestDoorClose() sensed_speed: Real closed: Boolean
sensed_speed: Real ds.requestDoorOpen()
R:CD-SD
communicatesWith ac_ecu.requestSpeed()
communicatesWith communicatesWith controls
ac_ecu.sensed_speed
0.&-./& 0*)12)3"& !33"&
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.openDoor()
requestSpeed() powers openDoor() controls
open:Boolean
sensed_speed: Real closeDoor()
powered: Boolean ds.requestDoorClose()
activated: Boolean ac_ecu.requestSpeed()
ac_ecu.sensed_speed
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.closeDoor()
Figure 5: Slicing criterion Sc [PSD].
PowerSlidingDoor: SD
$45%*16,'&-./& 2*5%*160.&-./& 260*)12)3"& 746!"#$%"&'(#)*+& 468%719729)&'(#)*+&
par s.requestSpeed()
PowerSlidingDoor: CD
!"#$%"&'(#)*+& ,'&-./& !"#$%#&%'()*+',-(
requestDoorOpen() getSpeed(sensed_speed) request Speed() [if s.sensed_speed<=15] s.closed else s.open
requestDoorClose() sensed_speed: Real closed: Boolean
sensed_speed: Real ds.requestDoorOpen()
R:CD-SD
communicatesWith ac_ecu.requestSpeed()
communicatesWith communicatesWith controls
ac_ecu.sensed_speed
0.&-./& 0*)12)3"& !33"&
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.openDoor()
requestSpeed() powers openDoor() controls
open:Boolean
sensed_speed: Real closeDoor()
powered: Boolean ds.requestDoorClose()
activated: Boolean ac_ecu.requestSpeed()
ac_ecu.sensed_speed
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.closeDoor()
Figure 6: Result of level 1 slicing in 1st iteration.
PowerSlidingDoor: SD
$45%*16,'&-./& 2*5%*160.&-./& 260*)12)3"& 746!"#$%"&'(#)*+& ./!"#$%#&%'()*+',-(
par s.requestSpeed()
PowerSlidingDoor: CD
!"#$%"&'(#)*+& ,'&-./& !"#$%#&%'()*+',-(
requestDoorOpen() getSpeed(sensed_speed) request Speed() [if s.sensed_speed<=15] s.closed else s.open
requestDoorClose() sensed_speed: Real closed: Boolean
sensed_speed: Real ds.requestDoorOpen()
R:CD-SD
communicatesWith ac_ecu.requestSpeed()
communicatesWith communicatesWith controls
ac_ecu.sensed_speed
0.&-./& 0*)12)3"& !33"&
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.openDoor()
requestSpeed() powers openDoor() controls
open:Boolean
sensed_speed: Real closeDoor()
powered: Boolean ds.requestDoorClose()
activated: Boolean ac_ecu.requestSpeed()
ac_ecu.sensed_speed
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.closeDoor()
Figure 7: Result of the 1st iteration.
56
Line 19: In this line, we check to see if any actual expan- bar on the leftmost lifeline is included, as both of its input
sion has occurred. Since the condition is not met (i.e., the and output arrows are included in the result of the slicing.
result of the 1st iteration did indeed expand on the initial Finally, all the methods and attributes of the Actuator
criterion) we iterate one more time. class, as well as the sensed speed attribute of the AC ECU
class and the AC ECU class itself are added to satisfy the ref-
erential integrity condition between the SD and the CD (they
2nd iteration of the outer loop (lines 2-19): are all referenced in the SD).
The slicing criterion S[PSD] in this iteration is the result The detail of the final megamodel fragment produced af-
of the previous iteration shown in Fig. 7. S1 [PSD] is reset ter the slicing and post-processing is shown in the high-
again to the empty set. lighted parts of Fig. 9. This can now be used to more ef-
ficiently complete the model evolution process by focusing
Lines 4-9 (Expansion Level 1): First the CD is selected only on the model parts impacted by the original deletion
on line 5. Since none of the slicing dependency rules given of Redundant Switch in the CD.
in Table 1 apply, nothing is added to S1 [PSD] on line 8.
Next, the SD is selected on line 5. Now, SD1 − SD3 rules
for the SD slicer in Table 1 apply, and the SD slice is ex- 6. RELATED WORK
panded to include the arrows of the top two messages and We identify three main categories of related work: work
the entire expressions (and therefore messages and arrows) on model evolution, work on megamodeling operators, and
that the term s.closed appears in. This is seen in the finally, work on model slicing. We describe them below.
highlighted parts of the SD portion of Fig. 81 .
Model evolution. A survey on supporting the evolution of
Lines 10-17 (Expansion Level 2): In this level, trac- UML models in model-driven software development is pre-
ing across the R : CD − SD relationship from the CD to the sented in [14]. The scenarios that cause a model to change
SD (recall this is a unidirectional traceability relationship), are discussed; these form the basis for megamodel evolution
since no new elements are introduced in the CD slice, noth- in our approach. In [22], the authors discuss some of the key
ing is traced to them in the SD. The result is an empty problems of evolution in MDE, summarize the key state-of-
set. the-art, and present some new challenges in research in this
area. The problem of model evolution with respect to meg-
Line 18: The results of the level 1 and the level 2 expan- amodels is stated as a “dependency heterogeneity” challenge.
sions are unioned and are reflected in the highlighted parts The authors express the need for a sound, precise theory of
of Fig. 8. heterogeneous dependencies between MDE artefacts, as well
Line 19: Since an expansion (w.r.t. the initial slice for as compliant and pragmatic tool support, both of which are
this iteration) has occurred, the condition does not hold, complimentary to and/or are part of our current work.
and we iterate one more time on the outer loop. Megamodeling operators. A formal approach to meg-
3rd iteration of the outer loop (lines 2-19): amodeling, called Mapping-Aware Megamodeling, is presented
in [9]. Our notion of a megamodel is consistent with it. The
In this iteration, neither the CD nor the SD are expanded in approach also describes category theory-based operations on
the first level expansion as none of the dependency rules the mapping-aware megamodels, but does not address meg-
for their respective slicers holds. Similarly, no new ele- amodel slicing. In previous work [24], we presented a set of
ments are added, and therefore going through the trace operators (Map, Filter, Reduce) that can be applied at the
links does not identify any other elements to be added to megamodel level. We are not aware of any other work in
the expansion in level 2. The condition on line 19 now the area of applying operators at the megamodel level, and
holds (no expansion has occurred), and the main loop of specifically, we have not seen any work addressing slicing of
the algorithm exits. megamodels.
Line 20 (Return): The current slice, S[PSD], which is Model Slicing. We divide this area into work on specific
shown in the highlighted parts of Fig. 8, is returned as the model slicers, work on generic model slicers and work on
final result of the algorithm. slicing multiple models.
Specific Model Slicers. Numerous approaches have appeared
5.3 Post-processing in the literature describing slicers for specific model types.
As suggested in Sec. 4, we perform a post-processing step, For example, [13] defines context-free model slicing and presents
we expand the result of slicing algorithm shown in Fig. 8 to an algorithm for computing slices on UML class models. [18]
ensure the model fragments are well-formed and contextual also considers UML models, namely, class diagrams, indi-
information for referential integrity is included. vidual state machines, and communicating sets of state ma-
For the CD, the VS ECU and Actuator classes are included chines. The approach achieves slicing of these models using
since both endpoints of associations communicatesWith and model transformations. An approach for slicing state-based
controls are needed for well-formedness. models, in particular, EFSM (extended finite state machine)
For the SD, the VS ECU, AC ECU and Actuator objects and models, is discussed in [16]. Finally, [17] proposes a slicing
their lifelines are included to satisfy the well-formedness con- technique for UML architectural models, and demonstrates
straint of arrows requiring their lifelines. Also, the execution the uses of slicing for different purposes such as regression
1
Due to space limits, we have skipped visualizing the result testing and understanding large architectures. Many other
at each step of the 2nd iteration and have shown the final approaches (e.g., [21], [18]) are presented in the literature
result of the union only. and can all be used as part of our framework as specific
57
PowerSlidingDoor: SD
$45%*16,'&-./& 2*5%*160.&-./& 260*)12)3"& 746!"#$%"&'(#)*+& ./!"#$%#&%'()*+',-(
par s.requestSpeed()
PowerSlidingDoor: CD
!"#$%"&'(#)*+& ,'&-./& !"#$%#&%'()*+',-(
requestDoorOpen() getSpeed(sensed_speed) request Speed() [if s.sensed_speed<=15] s.closed else s.open
requestDoorClose() sensed_speed: Real closed: Boolean
sensed_speed: Real ds.requestDoorOpen()
R:CD-SD
communicatesWith ac_ecu.requestSpeed()
communicatesWith communicatesWith controls
ac_ecu.sensed_speed
0.&-./& 0*)12)3"& !33"&
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.openDoor()
requestSpeed() powers openDoor() controls
open:Boolean
sensed_speed: Real closeDoor()
powered: Boolean ds.requestDoorClose()
activated: Boolean ac_ecu.requestSpeed()
ac_ecu.sensed_speed
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.closeDoor()
Figure 8: Result of 2nd iteration.
PowerSlidingDoor: SD
567/(*8!"#$%&# +(7/(*8'%#$%&# +8'()*+),-# -./!"#$%"&'(#)*+& 68./0*10+1)#"23)(4#
par s.requestSpeed()
PowerSlidingDoor: CD
!"#$%"&'(#)*+& !"#$%&# ./0*10+1)#"23)(4#
requestDoorOpen() getSpeed(sensed_speed) request Speed() [if s.sensed_speed<=15] s.closed else s.open
requestDoorClose() sensed_speed: Real closed: Boolean
sensed_speed: Real ds.requestDoorOpen()
R:CD-SD
communicatesWith ac_ecu.requestSpeed()
communicatesWith communicatesWith controls
ac_ecu.sensed_speed
'%#$%&# '()*+),-# !,,"&
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.openDoor()
requestSpeed() powers openDoor() controls
open:Boolean
sensed_speed: Real closeDoor()
powered: Boolean ds.requestDoorClose()
activated: Boolean ac_ecu.requestSpeed()
ac_ecu.sensed_speed
[if ac_ecu.sensed_speed<=15 and a.powered and s.closed] a.activated = True, a.closeDoor()
Figure 9: Output of algorithm after post-processing.
model type slicers for each of the model types in our hetero- discusses heterogeneous slicing as the union of individual
geneous megamodels. slicers. A slicing theory is presented at a high level and
Generic Model Slicers. Generic model slicing has also been does not go into the details of implementing a megamodel
studied in the MDE community. For example, the major slicing algorithm. From the modeling and safety community,
contribution of [4, 5] is the Kompren language, which pro- [20] proposes a batch model slicer for slicing SysML models
vides a generic approach to define a model slicer for a any related to safety requirements. [10] presents a prototype tool
domain-specific metamodel. The approach permits develop- called SafeSlice which performs the slicing needed in [20].
ers to either use “strict slicers” that output models which This line of work performs slicing on specific model types,
conform to their expected metamodel, or to define “soft whereas our work is a generic slicing approach. Also, the
slicers” that can output nonconforming models or even out- presented approach is amorphous slicing, where the result
puts that are not models. Although Kompren can be used of the slice is not a model fragment of the original system.
for identifying specific type slicers in our framework, it is not For example, transitions are added to sliced state-machines
applicable for megamodel slicing, where a megamodel slicer in order to preserve their behaviour. Our current approach
has to carefully invoke the specific type slicers. The work only considers slices to be fragments of the original model
in [7] defines slicing at a theoretical level, whereas we focus (non-amorphous); however, we do plan to look at amorphous
on a more pragmatic approach. Also, the same work focuses slicing in future work.
on dynamic slicing, as does the transformation slicing work
in [25], whereas our approach is considered a static slicing 7. CONCLUSION
approach. As far as we know, none of the approaches in
this category directly address megamodel slicing (whether Model slicing is a useful technique for assessing change
the megamodels are heterogeneous or not). impact during model evolution activities. Although slicing
of individual models has been investigated, slicing of het-
Slicing Multiple Models. Although the work presented in erogeneous model collections has received much less atten-
[7] does not primarily focus on megamodel slicing, it briefly tion. In this paper, we have proposed a general algorithm for
58
slicing of heterogeneous model collections represented using [13] H. Kagdi, J. I. Maletic, and A. Sutton. Context-Free
megamodels and illustrated the algorithm on an automotive Slicing of UML Class Models. In Proc. of ICSM’05,
example. We analyzed the algorithm and showed that it pages 635–638. IEEE, 2005.
behaves as expected with respect to termination, correct- [14] A. Khalil and J. Dingel. Supporting the Evolution of
ness, time complexity and minimality. Finally, we discussed UML Models in Model Driven Software Development:
the issues concerning slice well-formedness and referential a Survey. Technical Report 602, School of Computing,
integrity as well as how to generalize the algorithm to sup- Queen’s University, Ontario, Canada, 2013.
port arbitrary relationship types, N-ary relationship and [15] S. Kokaly, R. Salay, V. Cassano, T. Maibaum, and
nested megamodels. We are currently developing tooling M. Chechik. A Model Management Approach for
for the algorithm using the Model Management INTeractive Assurance Case Reuse due to System Evolution. In
(MMINT) framework [8] and plan to use it to conduct more Proc. of MODELS’16, 2016. (to appear).
extensive case studies to better understand the strengths [16] B. Korel, I. Singh, L. Tahat, and B. Vaysburg. Slicing
and weaknesses of the approach. of State-Based Models. In Proc. of ICSM’03, pages
34–43. IEEE, 2003.
8. ACKNOWLEDGMENTS [17] J. T. Lallchandani and R. Mall. A Dynamic Slicing
Technique for UML Architectural Models. IEEE TSE,
This work is being done as part of the NECSIS project 37(6):737–771, 2011.
(www.necsis.ca), funded by Automotive Partnership Canada
[18] K. Lano and S. Kolahdouz-Rahimi. Slicing of UML
and NSERC.
Models Using Model Transformations. In Proc. of
MODELS’10, pages 228–242. Springer, 2010.
9. REFERENCES [19] B. Li, X. Sun, H. Leung, and S. Zhang. A Survey of
Code-Based Change Impact Analysis Techniques. J.
[1] N. Aizenbud-Reshef, B. T. Nolan, J. Rubin, and Software Testing, Verification and Reliability,
Y. Shaham-Gafni. Model traceability. IBM Systems 23(8):613–646, 2013.
Journal, 45(3):515–526, 2006. [20] S. Nejati, M. Sabetzadeh, D. Falessi, L. Briand, and
[2] P. A. Bernstein. Applying Model Management to T. Coq. A SysML-based Approach to Traceability
Classical Meta Data Problems. In Proc. of CIDR’03, Management and Design Slicing in Support of Safety
volume 2003, pages 209–220, 2003. Certification: Framework, Tool Support, and Case
[3] J. Bézivin, F. Jouault, and P. Valduriez. On the Need Studies. Information and Software Technology,
for Megamodels. In Proc. of OOPSLA/GPCE 54(6):569–590, 2012.
Workshops, 2004. [21] K. Noda, T. Kobayashi, K. Agusa, and S. Yamamoto.
[4] A. Blouin, B. Combemale, B. Baudry, and Sequence Diagram Slicing. In Proc. of APSEC’09,
O. Beaudoux. Modeling Model Slicers. In Proc. of pages 291–298. IEEE, 2009.
MODELS’11, pages 62–76. Springer, 2011. [22] R. F. Paige, N. Matragkas, and L. M. Rose. Evolving
[5] A. Blouin, B. Combemale, B. Baudry, and Models in Model-Driven Engineering: State-of-the-art
O. Beaudoux. Kompren: Modeling and Generating and Future Challenges. J. of Systems and Software,
Model Slicers. SoSyM, 14(1):321–337, 2015. 111:272–280, 2016.
[6] G. Brunet, M. Chechik, S. Easterbrook, S. Nejati, [23] R. Salay, M. Famelis, J. Rubin, A. Di Sandro, and
N. Niu, and M. Sabetzadeh. A Manifesto for Model M. Chechik. Lifting Model Transformations to
Merging. In Proc. of GAMMA@ICSE’06, pages 5–12. Product Lines. In Proc. of ICSE’14, pages 117–128.
ACM, 2006. ACM, 2014.
[7] T. Clark. A General Model-Based Slicing Framework. [24] R. Salay, S. Kokaly, A. Di Sandro, and M. Chechik.
In Proc. of Wrksp on Composition and Evolution of Enriching Megamodel Management with
Model Transformations, 2011. Collection-Based Operators. In Proc. of MODELS’15,
[8] A. Di Sandro, R. Salay, M. Famelis, S. Kokaly, and pages 236–245, 2015.
M. Chechik. MMINT: A Graphical Tool for [25] Z. Ujhelyi, Á. Horváth, and D. Varró. Towards
Interactive Model Management. In Proc. of dynamic backward slicing of model transformations.
MODELS’15 (demo track), 2015. In Automated Software Engineering (ASE), 2011 26th
[9] Z. Diskin, S. Kokaly, and T. Maibaum. IEEE/ACM International Conference on, pages
Mapping-Aware Megamodeling: Design Patterns and 404–407. IEEE, 2011.
Laws. In Proc. of SLE’13, pages 322–343, 2013. [26] M. Weiser. Program Slicing. In Proc. of ICSE’81,
[10] D. Falessi, S. Nejati, M. Sabetzadeh, L. Briand, and pages 439–449. IEEE Press, 1981.
A. Messina. SafeSlice: A Model Slicing and Design
Safety Inspection Tool for SysML. In Proc. of
ESEC/FSE’11, pages 460–463. ACM, 2011.
[11] O. Gotel and A. Finkelstein. Contribution structures.
In Requirements Engineering, 1995., Proceedings of
the Second IEEE International Symposium on, pages
100–107. IEEE, 1995.
[12] International Organization for Standardization. ISO
26262: Road Vehicles – Functional Safety, 2011. 1st
version.
59