131010 jim cordy - submodel pattern extraction for simulink models

Submodel
Pattern Extraction
for Simulink Models
James R. Cordy
Queen’s University
NECSIS Automotive Partnership Canada

MPE
near-miss clones

near-miss clone detection
Simone

analysis of GM models
pattern extraction

pattern evolution

Model Pattern Engineering
discover, catalogue and formalize
submodel patterns

emergent
domain-speciﬁc, client-speciﬁc

discovery

analysis, identiﬁcation
methodology, techniques
classiﬁcation

characterization, formalization
notation, tooling, catalogues
application

deployment, analysis
organization, documentation, use cases

why?
reuse in model development

standards/consistency analysis/enforcement
failure/change propagation in model maintenance

veriﬁcation/test optimization
deployment variation/optimization

model product lines

code clones
copy-paste programming

efﬁcient, widely used
problematic

code clones
type 1 - exact

bool ConfNextToken (char **p) {
// skip white space
while (1)
switch (**p) {
case 't' : // ignore
case ' ' :
(*p)++;
break;
case '0' :
return FALSE;
default :
return TRUE;
};
}

// skip white space
while (1)
switch (**p) {
case ' ' :
(*p)++;
break;
case '0' :
return FALSE;
default :
return TRUE;
};
}
[Roy, Cordy, Koschke SCP 2009]

code clones
type 1 - exact

// skip white space
while (1)
switch (**p) {
case ' ' :
(*p)++;
break;
case '0' :
return FALSE;
default :
return TRUE;
};
}

bool ConfNextToken (char **p)
{
while (1) switch (**p)
{
case 't': case ' ':
// just skip
(*p)++;
break;
case '0':
// eof
return FALSE;
default:
// something we want
return TRUE;
};
}

code clones
type 2 - renamed

// skip white space
while (1)
switch (**p) {
case ' ' :
(*p)++;
break;
case '0' :
return FALSE;
default :
return TRUE;
};
}

bool NextToken (char **bp)
{
while (1) // not really
switch (**bp)
{
case 't': case ' ':
// next
(*bp)++;
break;
case '0':
return 0;
default:
return 1;
};
}

code clones
type 3 - near miss

// skip white space
while (1)
switch (**p) {
case ' ' :
(*p)++;
break;
case '0' :
return FALSE;
default :
return TRUE;
};
}

bool NextToken (char **bp)
{
while (1) // not really
switch (**bp)
{
case 't':
(*bp)++
case ' ':
break;
case '0':
return 0;
default:
return 1;
}
}

1
Fn

2/3*R*muk

1
Tfmaxk

Torque
Conversion
mus/muk

2
Tfmaxs

Ratio of static
to kinetic

model clones
type 1 - exact
1
Fn

2/3*R*muk

1
Tfmaxk

Torque
Conversion
mus/muk

2
Tfmaxs

Ratio of static
to kinetic

[Alalﬁ, Cordy, Dean, Stephan, Stevenson ICSM 2012] [Störrle SSM 2013]

model clones
type 2 - renamed


model clones
type 3 - near miss


ConQAT
graph-based model
clone detection

[Deissenboeck et al. IWSC 2010]

graph ﬂattening ignores
hierarchical structure

problems with
near-miss

code-based near-miss works well
NiCad, iClones, others

mature, accurate, efﬁcient
handles unexpected differences

threshold-based, tunable
scalable

Parsing &
Potential Clone
Extraction

4

Original
Code Base

Original
Code Base

3

2

Parsing &
Potential Clone
Extraction
1

Pretty-printed
Potential Clones

Choose
(Repeat) Next
Potential Clone
as Exemplar

Choose Next
Potential Clone
as Exemplar

3

2

1

Normalized
Potential Clones

NiCad

Pretty-printed
Potential Clones

4

3

2

Renaming,
Filtering,
Normalization

4

1

Normalized
Potential Clones

3

2

1

Normalized
Potential Clones

1. Parse / Extract
2. Rename / Filter / Normalize
2. Rename / Filter / Normalize

1. Parse / Extract

4

Renaming,
4Filtering,
3
2
Normalization
1

Cluster
4
3
Comparable
2
1
Size PCs

(Repeat)

Pairwise
Cluster
Comparison
Comparable
with Exemplar
Size PCs

Comparable Size
Normalized
Potential Clone Cluster
Potential Clones

3. Clone Analysis

5.pc
12.pc
23.pc
17.pc
67.pc 15.pc
18.pc
. . . 22.pc 21.pc
63.pc
. . . 78.pc 37.pc
39.pc
. . . 97.pc
. . . 44.pc
...

5.pc
12.pc
23.pc
17.pc
67.pc 15.pc
18.pc
. . . 22.pc 21.pc
63.pc
. . . 78.pc 37.pc
39.pc
. . . 97.pc
. . . 44.pc
...

Pairwise
Comparison
with Exemplar

Comparable Size
Clone
Potential Clone Cluster
Classes

Clone
Classes

3. Clone Analysis

parse - extract - normalize - diff threshold
[Roy, Cordy ICPC 2008]

crazy idea:
can we use near-miss text code methods
on graphical models?

“Models are source code too”
Mark Harman, keynote at SCAM 2010

[Harman SCAM 2010]

Simone

Simulink near-miss clone detection
experiment

adapt NiCad near-miss code clone
detector to graphical models
validate vs. ConQAT

for types 1 & 2
hand validate type 3 (near-miss)
[Alalﬁ, Cordy,Dean, Stephan, Stevenson ICSM 2012]

Simulink

hybrid hardware/software models
widespread in industry
- automotive, aerospace, embedded systems

mature and interesting at GM

Simulink

hierarchical models


Challenge #1
code methods
require text

NiCad requires
a parser

...!
System {!
Name
"onoff"!
Location
[168, 385, 668, 686]!
Open
on!
ModelBrowserVisibility off!
ModelBrowserWidth
200!
ScreenColor
"automatic"!
PaperOrientationi
"landscape"!
PaperPositionMode
"auto"!
PaperType
"usletter"!
PaperUnits
"inches"!
ZoomFactor
"100"!
AutoZoom
on!
ReportName
"simulink-default.rpt"!
Block {!
BlockType
DiscretePulseGenerator!
Name
"Discrete PulsenGenerator"!
Position
[45, 25, 75, 55]!
Amplitude
"1"!
Period
"2"!
PulseWidth
"1"!
PhaseDelay
"0"!
SampleTime
"1"!
}!
Block {!
BlockType
Product!
Name
"Product"!
Ports
[2, 1, 0, 0, 0]!
Position
[145, 67, 175, 98]!
Inputs
"2"!
SaturateOnIntegerOverflow on!
}!
...!
}!
...!

Solution:
grammar inference

on Simulink’s
internal form

Challenge #2
what granularity?

NiCad requires
candidates for
comparison

...!
System {!
Name
"onoff"!
Location
[168, 385, 668, 686]!
Open
on!
ModelBrowserWidth
200!
ScreenColor
"automatic"!
PaperOrientationi
"landscape"!
PaperPositionMode
"auto"!
PaperType
"usletter"!
PaperUnits
"inches"!
ZoomFactor
"100"!
AutoZoom
on!
ReportName
Block {!
BlockType
Name
Position
[45, 25, 75, 55]!
Amplitude
"1"!
Period
"2"!
PulseWidth
"1"!
PhaseDelay
"0"!
SampleTime
"1"!
}!
Block {!
BlockType
Product!
Name
"Product"!
Ports
[2, 1, 0, 0, 0]!
Position
[145, 67, 175, 98]!
Inputs
"2"!
}!
...!
}!
...!

Simulink:
model (too big)
block (too small)
system (just right!)

powerwindow03/power_window_control_system/validate_driver

neutral

1
neutral

2
up


action
checked_action

up

validated_up

reset

[reset]
From2

3
down

1
neutral_up_down

action
down

validated_down

reset

[reset]
From1

2
up
[reset]

3
down

checked_action

From1

[reset]
Goto1

validated_up

1
neutral_up_down

check_up
action
checked_action

down

validated_down

check_down

mutually_exclusive
4
reset

up

reset

reset

[reset]
check_down

validated_neutral

action

From2

check_up

checked_action

neutral

1
neutral

validated_neutral

mutually_exclusive
4
reset

[reset]
Goto1

even with raw text, ﬁnd some subsystem clones

/Users/manaralalfi/Desktop/NiCad 3.2 Simulink/Simulink/Publicmodel/automotive/powerwindow03.mdl
printed 13 Apr 2012 14:56


page 1/1 13 Apr 2012 14:56
printed

but:
90% irrelevant Simulink internal “formatting” systems

some identical systems only 70% same
entirely missed exact copies displayed differently

page 1/1

Challenge #3
problems with
“noise”

solution:
“agile parsing” to
ﬁlter out irrelevant
elements

...!
System {!
Name
"onoff"!
Location
[168, 385, 668, 686]!
Open
on!
ModelBrowserWidth
200!
ScreenColor
"automatic"!
PaperOrientationi
"landscape"!
PaperPositionMode
"auto"!
PaperType
"usletter"!
PaperUnits
"inches"!
ZoomFactor
"100"!
AutoZoom
on!
ReportName
Block {!
BlockType
Name
Position
[45, 25, 75, 55]!
Amplitude
"1"!
Period
"2"!
PulseWidth
"1"!
PhaseDelay
"0"!
SampleTime
"1"!
}!
Block {!
BlockType
Product!
Name
"Product"!
Ports
[2, 1, 0, 0, 0]!
Position
[145, 67, 175, 98]!
Inputs
"2"!
}!
...!
}!
...!
[Dean, Cordy, Malton, Schneider JASE 2003]

ﬁltering

...!
System {!
Name
Block {!
BlockType
Name
Amplitude
Period
PulseWidth
PhaseDelay
SampleTime
}!
Block {!
BlockType
Name
Ports
Inputs
}!
...!
}!
...!

removes more
than 300 kinds
of irrelevant
elements and blocks

increases
signal-to-noise
ratio in text

"onoff”!
"Discrete PulsenGenerator”!
"1"!
"2"!
"1"!
"0"!
"1"!
Product!
"Product"!
[2, 1, 0, 0, 0]!
"2”!

ﬁltering signiﬁcantly improved performance
precision - 10x fewer false positives
hand validation of results

recall - many fewer false negatives
fewer missed clones
much larger clones

but:
some clones we could clearly see by hand
still not detected - why?

Challenge #4
no linear order of model elements

Challenge #4
solution: topological sort by block, line, port, branch

sorting
increases recall, to ﬁnd many more clones

neutral

1
neutral

2
up


[reset]

action
checked_action

3
down

2
up
[reset]

validated_neutral

validated_up

1
neutral_up_down

check_up
action
checked_action

down

validated_down

reset

[reset]
neutral

up

reset

From2

1
neutral

validated_neutral

From1

check_down
mutually_exclusive

4
reset

action
checked_action

up

validated_up

reset

From2

[reset]
Goto1

1
neutral_up_down

check_up

3
down

action
checked_action

down


validated_down

reset

[reset]
From1

check_down
mutually_exclusive

4
reset

[reset]
Goto1


page 1/1

page 1/1

sorting
increases recall, to ﬁnd many more clones

neutral

1
neutral

2
up


[reset]

3
down

action

validated_neutral

up

checked_action

From2

action
down

checked_action

From1

mutually_exclusive

[reset]

up

checked_action

validated_up

reset

From2

down

checked_action

From1


validated_down

check_down

neutral

1
neutral

validated_down


check_down

mutually_exclusive

page 1/1

mutually_exclusive
4
reset

down

checked_action

From1

action
reset

[reset]

Goto1

reset

[reset]

check_up

3
down

[reset]

4
reset

check_up

[reset]

4
reset

page 1/1

Goto1

validated_neutral

[reset]

Goto1

checked_action

From2

page 1/1
neutral

1
neutral

1
neutral_up_down

validated_up

page 1/1

checked_action

neutral

1
validated_down

down

validated_neutral

2
up

neutral

reset

check_down

checked_action

up

validated_up

reset

From2

[reset]

4
reset

1
neutral_up_down

Goto1

checked_action

From1

down

validated_down

check_down

down

page 1/1

Goto1
action

page 1/1
action
down

checked_action

validated_neutral

2
up
[reset]

check_down

checked_action

From2
2
up

3
down

checked_action

up

validated_up

reset

1
neutral_up_down

check_up

validated_up

[reset]

4
reset

1
neutral_up_down

From1

down

2
up
checked_action

down

validated_down

reset

neutral

1
neutral

validated_neutral

printed 13 Apr

check_down

[reset]
Goto1

[reset]

3
/Users/manaralalfi/Desktop/NiCad 3.2 Simulink/Simulink/Publicmodel/automotive/powerwindow03.mdl down
[reset]
From1

3
down

action

2
up

checked_action

up

validated_up

reset

[reset]
From2

Goto1

action
checked_action

up

validated_up

reset
/Users/manaralalfi/Desktop/NiCad [reset]
3.2 Simulink/Simulink/Publicmodel/automotive/powerwindow03.mdl
From2
check_up
2012 14:56

1
neutral_up_down

page 1/1

check_down

validated_down

4
reset

validated_neutral

check_up

mutually_exclusive
checked_action

neutral

1
neutral

Goto1

action

action

mutually_exclusive
4
reset

3
down
[reset]

reset

From1

up

action

From2

[reset]

mutually_exclusive

action
reset

validated_down

reset

[reset]

neutral

page 1/1

1
neutral_up_down

check_up

3
down

validated_neutral

up
validated_up

checked_action
reset

From1
1
neutral

Goto1

validated_neutral


neutral

[reset]

4
reset
neutral

1
neutral

From2

1
neutral

validated_down

check_down

validated_down

page 1/1

2
up


down

checked_action
reset

mutually_exclusive

[reset]

action

[reset]

4
reset


3
down
From1

mutually_exclusive

[reset]
Goto1

1
neutral_up_down

[reset]

mutually_exclusive
4
reset

validated_up

check_up

action
3
down
checked_action
reset
[reset]
From1
check_down

reset

[reset]

up

checked_action
reset

[reset]
From2

action

3
down

1
neutral_up_down

validated_up

check_up

action

2
up

check_up

up

checked_action

From2

mutually_exclusive
action

action
reset

[reset]

From1

[reset]

validated_neutral

action

[reset]

2
up

neutral

1
neutral

check_up

3
down

validated_neutral

up

reset



action

2
up
[reset]

[reset]

validated_down

mutually_exclusive

action

3
down


check_down
1
neutral_up_down

validated_up

reset

Goto1

1
neutral_up_down

up

down

checked_action
reset

From1
checked_action

From2

[reset]

4
reset

action

action

3
down
[reset]
action

2
up

1
neutral_up_down

validated_up

check_up

validated_neutral

validated_down

check_down

[reset]

2
up

neutral

1
neutral

up

checked_action
reset

[reset]

check_up

validated_neutral

action

2
up

1
neutral_up_down

validated_up

reset

neutral

1
neutral

reset

[reset]
neutral

validated_neutral


From2

1
neutral


1
neutral_up_down

action
checked_action

From1

validated_down

check_down
mutually_exclusive

check_up
4
reset

action
checked_action

down

reset

[reset]

down

validated_down

[reset]
Goto1

reset

page 1/1
check_down
mutually_exclusive


page 1/1

4
reset

[reset]

Goto1


page 1/1

page 1/1

Challenge #5
ﬁnding type 2
(renamed) requires
anonymization

...!
System {!
Name
Block {!
BlockType
Name
Amplitude
Period
PulseWidth
PhaseDelay
SampleTime
}!
Block {!
BlockType
Name
Ports
Inputs
}!
...!
}!
...!

names in Simulink
not like other
languages

solution:
context-dependent
anonymizer

"onoff”!
"Discrete PulsenGenerator”!
"1"!
"2"!
"1"!
"0"!
"1"!
Product!
"Product"!
[2, 1, 0, 0, 0]!
"2”!

validation - Simone vs. ConQAT
on Matlab Central public model systems

finds all type1(exact) and type 2 (renamed)
clones found by ConQAT

finds many new type 3 (near-miss)
clones not found by ConQAT

finds larger clones and larger clone classes

Simone near-miss clones
in Simulink public automotive model variants
Total nontrivial
subsystems
357

Extractor only

Filtered

Filtered & Sorted

Filtered, Sorted &
Renamed

Clone Type

Type 1

Type 3-1
@30%

Type 1

Type 3-1
@30%

Type 1

Type 3-1
@30%

Type 2

Type 3-2
@30%

Clone Pairs

116 / 10*

364 / 164*

204

204

303

181

279

1938

Clone Classes

8 / 4*

57 / 56*

44

55

45

52

48

24

Clone Coverage

8% / 3%

52% / 46%

37%

48%

42%

45%

49%

75%


Simone near-miss pattern mining
in Simulink models
!"#$%&%'()(*+&$%'(

,+-.".$%-$(/%-01"-2(

3#"-'(/%-01"-2(

*4.$%1.(
56$&07$%'(

,#+-%.(

,#0..%.(

,#+-%.(

,#0..%.(

,#+-%.(

,#0..%.(

!"#$"%&'()#*"$&

+,-&

,,.&

,+&

,/+&

,.&

-0,&

,1&

2345$3)6&7(48&

1/9:&

;0-&

.,&

,11&

.,&

1.;0&

--&

'8)<"#&=>"4?$(@&

--0&

1+.&

-0&

;;;&

-0&

-,.&

-,&

89('+$)::(

099&

;11&

;.&

;90&

;0&

/::&

;:&

89('+$):;(

099&

;11&

;/&

;.-&

;.&

/1.&

;1&

89('+$):<(

0./&

;1;&

;+&

;.-&

;/&

/;-&

;,&

89('+$):=(

1:01&

;/-&

,+&

,9;&

-1&

11-9&

,:&

Case study
GM fuel system models

SimGraph visualization
understanding Simulink model subsystem
similarity

GM Fuel System Models
Subsystem similarity overview
X models
(blue)

Small
subsystems

Y models
(green)

Large
subsystems
Z models
(red)

Midsize
subsystems

Subsystem similarity overview

Many subsystems unique not similar to any others in
these models

Remove unique subsystems

Similar subsystems
“near-miss clones”
both within and
between models

Connecting lines represent subsystem similarity thick lines, 90-100% similar
thin lines, 70-80% similar

Rearrange to cluster similar subsystems

Clusters reveal groups of
similar subsystems “clone classes”

Infer common subsystem patterns

Patterns characterize
common repeated similar
subsystem paradigms

Small groups of
relatively large
similar subsystems
both within and
across models

Large groups of small
to mid-sized similar
subsystems across
models

using patterns
SimNav
exemplar sets as patterns

SimPat
modeling variance

SimNav
presenting and integrating results in Simulink

exemplar sets as patterns

SimNav

&'()*'+,

&'(-/@
!"#$"%

&=!>-?
-'./0

&'()*'+,78*9+170131839:7
;(901*6<
#12345/61078*9+170131839:7
;69):8178901<

131010 jim cordy - submodel pattern extraction for simulink models

SimPat
characterizing and representing subsystem
patterns

modeling variance

!901*7.*9+17.*/66A7
B76)56C631(78*9+16

!901*7D/E1:+6

!901*7D/E1:+7FA

!1:G17#H:9E*177/+07
D:166):17?6I(/I9+

!901*7.*9+17.*/66A7
B76)56C631(78*9+16

!901*7D/E1:+6

!901*7D/E1:+7JA
777!1:G17/**73H:117
77777776)56C631(6
7

!901*7.*9+17.*/66A7
B76)56C631(78*9+16

!901*7D/E1:+6

!901*7D/E1:+7BA

.9((9+71*1(1+36
77777777777779+*C

%&$

near-miss clones

&($

%"$

MPE

&'$

&'$

!"#$

&($

&)$

&*$

%!$

&'$

!"#$

&($

&)$

&*$

near-miss clone detection
Simone

analysis of GM models
pattern extraction

pattern evolution

&)$

&*$

model pattern evolution
SimCCT

evolution of patterns
across versions

pattern variance in two dimensions
instance, time

[Stephan, Alalﬁ, Cordy, Stevenson ME 2013]

model pattern
MCC - model clone class

elements of a model pattern
MCI - model clone instance

migration of MCIs between MCCs across
versions of the system

1-1

pattern is stable across versions

1-1*

pattern exists, but loses or gains MCIs

1-many

pattern splits into multiple patterns

1-many*

pattern splits, losing or gaining MCIs

1-0

pattern uniﬁes or disappears

SimCCT - Power Window MCC 3
*'"

!"

#"

*)"

!"

$"

%"

&"

'("

'!"

'#"

*+"

!"

$"

%"

&"

'("

'!"

'#"

*,"-"*!"

)("

./01"2/3"405/26"3/"728"9::"
45"$6%78,
-!,9,

!"#"$#%&'()#*+,
-!,.,

!"#"$#%/0)#1$2",
-!,3,

SimCCT - Power Window MCC 2
!"#

$#

%#

&#

!$#

%#

&#

!%#

%#

&#

!&#

%#

&#

!'# ()*+#,)-#.*/),0#-)#1,2#344#

SimCCT - AVS MCC 7
%&$

&'$

&($

%"$

&'$

!"#$

&($

&)$

&*$

%!$

&'$

!"#$

&($

&)$

&*$

&)$

&*$

current work
Stateﬂow models

deployment at GM
analysis of more systems

Thank you!
Joseph d’Ambrosio
Cheryl Williams

Manar H. Alalﬁ
Thomas R. Dean
Matthew Stephan
Andrew Stevenson

131010 jim cordy - submodel pattern extraction for simulink models

Recommended

More Related Content

Similar to 131010 jim cordy - submodel pattern extraction for simulink models (20)

More from Ptidej Team (20)

Recently uploaded (20)

131010 jim cordy - submodel pattern extraction for simulink models