Finite Models
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 1
Learning objectives
• Understand goals and implications of finite state abstraction
• Learn how to model program control flow with graphs
• Learn how to model the software system structure with call graphs
• Learn how to model finite state behavior with finite state machines
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 2
Properties of Models
• Compact: representable and manipulable in a reasonably compact form
– What is reasonably compact depends largely on how the model will be used
• Predictive: must represent some salient characteristics of the modeled artifact well enough to distinguish between good and bad outcomes of analysis
– no single model represents all characteristics well enough to be useful for all kinds of analysis
• Semantically meaningful: it is usually necessary to interpret analysis results in a way that permits diagnosis of the causes of failure
• Sufficiently general: models intended for analysis of some important characteristic must be general enough for practical use in the intended domain of application
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 3
Purposes of models
• Models for design vs models for analysis
• Models for human communication vs models with semantically meaningful abstraction
• http://www.uml.org/ – Universal Modelling Language; for human communication
• models for analysis: used to guide test selection
use case diagram
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 4
Graph Representations: directed graphs
• Directed graph:
– N (set of nodes)
– E (relation on the set of nodes ) edges
Nodes: {a, b, c} a Edges: {(a,b), (a, c), (c, a)}
bc
(c) 2007 Mauro Pezzè & Michal Young
Ch 5, slide 5
Graph Representations: labels and code
• We can label nodes with the names or descriptions of the entities they represent.
– If nodes a and b represent program regions containing assignment statements, we might draw the two nodes and an edge (a,b) connecting them in this way:
x = y + z; a = f(x);
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 6
•
(Intraprocedural) Control Flow Graph
nodes = regions of source code (basic blocks)
– Basic block = maximal program region with a single entry and single exit point
– Often statements are grouped in single regions to get a compact model
• usually when there is no branching
– Sometime single statements are broken into more than one node to model control flow within the statement
• when a statement is a shorthand for multiple atomic actions
directed edges = possibility that program execution proceeds from the end of one region directly to the beginning of another
•
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 7
Building blocks of intraprocedural CFG
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 8
Example of Control Flow Graph
public static String collapseNewlines(String argStr) {
char last = argStr.charAt(0);
StringBuffer argBuf = new StringBuffer();
for (int cIdx = 0 ; cIdx < argStr.length(); cIdx++) {
char ch = argStr.charAt(cIdx); if (ch != '\n' || last != '\n')
{
argBuf.append(ch);
last = ch; }
}
return argBuf.toString(); }
public static String collapseNewlines(String argStr)
{
char last = argStr.charAt(0);
StringBuffer argBuf = new StringBuffer();
for (int cIdx = 0 ;
b2
cIdx < argStr.length();
b3
False True
False
True
{
charch =argStr.charAt(cIdx); if (ch != '\n'
b4
|| last != '\n')
b5
True
False
{
argBuf .append(ch);
last = ch; }
b6
}
cIdx++)
b7
return argBuf.toString(); }
b8
2001 Apache Software Foundation
(c) 2007 Mauro Pezzè & Michal Young
Ch 5, slide 9
Interprocedural control flow graph
• Call graphs
– Nodes represent procedures • Methods
• C functions • ...
– Edges represent calls relation
(c) 2007 Mauro Pezzè & Michal Young
Ch 5, slide 10
Overestimating the calls relation
The static call graph includes calls through dynamic bindings that never occur in execution.
public class C {
public static C cFactory(String kind) {
if (kind == "C") return new C();
if (kind == "S") return new S();
return null;
}
void foo() {
System.out.println("You called the parent's method");
}
public static void main(String args[]) {
(new A()).check();
} }
class S extends C {
void foo() {
System.out.println("You called the child's method");
}
}
class A {
void check() {
C myC = C.cFactory("S");
myC.foo();
} }
A.check()
C.foo()
S.foo()
CcFactory(string)
(c) 2007 Mauro Pezzè & Michal Young
Ch 5, slide 11
Contex Insensitive Call graphs
public class Context {
public static void main(String args[]) {
Context c = new Context(); c.foo(3);
c.bar(17);
}
void foo(int n) {
int[] myArray = new int[ n ]; depends( myArray, 2) ;
}
void bar(int n) {
int[] myArray = new int[ n ]; depends( myArray, 16) ;
}
void depends( int[] a, int n ) { a[n] = 42;
} }
main
C.foo
C.bar
C.depends
(c) 2007 Mauro Pezzè & Michal Young
Ch 5, slide 12
Contex Sensitive Call graphs
public class Context {
public static void main(String args[]) {
Context c = new Context(); c.foo(3);
c.bar(17);
}
void foo(int n) {
int[] myArray = new int[ n ]; depends( myArray, 2) ;
}
void bar(int n) {
int[] myArray = new int[ n ]; depends( myArray, 16) ;
}
void depends( int[] a, int n ) { a[n] = 42;
} }
C.foo(3)
main
C.bar(17)
C.depends(int(3),a,2)
C.depends (int(3),a,2)
(c) 2007 Mauro Pezzè & Michal Young
Ch 5, slide 13
Context Sensitive CFG exponential growth
1 context A
2 contexts AB AC
4 contexts ABD ABE ACD ACE 8 contexts ...
16 calling contexts ...
A
B
C
D
E
F
G
H
I
J
(c) 2007 Mauro Pezzè & Michal Young
Ch 5, slide 14
Context Sensitive CFG exponential growth – a simple example
B
(c) 2007 Mauro Pezzè & Michal Young
Ch 5, slide 15
A:if (x>5)
D:if (y>10)
how many states will a context-sensitive CFG have?
the number of states in context-sensitive CFG doubles with each decision node
the number of paths in the program is exponential – doubles with each decision node
C
E
F
G
Finite state machines studied in detail separately
• finite set of states (nodes)
• set of transitions among states (edges)
Graph representation of line end converter
LF_ emit
Emty buffer
CR_ emit
LF_ emit
Other char append
Other char append
Other char apend
e
LF
EOF emit
w
Within line
l
CR_ emit
EOF
d
Looking for optional DOS LF
EOF
Done
(c) 2007 Mauro Pezzè & Michal Young
Ch 5, slide 16
Using Models to Reason about System Properties
The model is syntactically well-formed, consistent, and complete
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 17
Summary
• Models must be much simpler than the artifact they describe to be understandable and analyzable
• Must also be sufficiently detailed to be useful
• CFG are built from software
• FSM can be built before software to document intended behavior
• CFG are used for white-box testing – next week(s)
• FSM are used for black-box testing
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 18
Home reading
• Chapter 5 of the book Software Testing and Analysis, by Mauro Pezze and Michal Young
– Finite Models
(c) 2007 Mauro Pezzè & Michal Young Ch 1, slide 19