1Class Analysis, conclusion
1
Announcements
n Quiz 2
n HW2
n Post question on Submitty
n I’m assuming you all have framework set locally
n Starter code, class analysis framework and worklist
algorithm
n Soot
n There are already many useful posts
CSCI 4450/6450, A Milanova 2
2
2Outline of Today’s Class
n Rapid Type Analysis (RTA), last time
n HW2, Class analysis framework questions?
n The XTA analysis family
n 0-CFA
n Points-to analysis (PTA)
CSCI 4450/6450, A Milanova 3
3
n Problem statement: What are the classes
of objects that a (Java) reference variable
may refer to?
n Applications
n Call graph construction
n Nodes are method
n Edges represent calls
n Notion of methods reachable from main
n Virtual call resolution
Class Analysis
CSCI 4450/6450, A Milanova
4
3RTA, A Declarative Specification
R is the set of reachable methods
I is the set of instantiated types
1. { main } R // Algo: initialize R with main
2. for each method m R and
each new site new C in m
{ C } I // Algo: add C to I; schedule
// “successor” constraints
5
∈
CSCI 4450/6450, A Milanova
5
RTA, A Declarative Specification
3. for each method m R,
each virtual call y.n(z) in m,
each class C in SubTypes(StaticType(y)) I,
and n’, where n’ = resolve(C,n)
{ n’ } R // Algo: add target n’ to R, if not already
// there. Schedule “successors”
6
∈
∩
CSCI 4450/6450, A Milanova
6
4Worklist Algorithm for Flow-
Insensitive Analysis
n Flow-insensitive, context-insensitive analysis
S = … /* initialize S, typically to empty, which is 0 of lattice */
W = { f1, … fn } /* initialize W with transfer functions in main */
while W ≠ Ø do {
remove fj from W
S = fj(S) /* fj never “kills” */
if S changed
W = W U Successors
/* Successors includes all affected transfer functions; easy safe
approximation for us: include all fj’s in reachable methods */
}
7
7
n Due to Tip and Palsberg
n Frank Tip and Jens Palsberg, “Scalable
Propagation-Based Call Graph Construction
Algorithms”, OOPSLA ’00
n Generalizes RTA
n Improves on RTA by keeping more info
n What if we kept sets per method and per field
rather than a “blob” I?
XTA Analysis Family
CSCI 4450/6450, A Milanova 8
8
5XTA
R is the set of reachable methods
Sm is the set of types that flow to method m
Sf is the set of types that flow to field f
1. { main } R
2. for each method m R and
each new site new C in m
{ C } Sm 9
∈
9
XTA
3. for each method m R,
each virtual call y.n(z) in m,
each class C in SubTypes(StaticType(y)) Sm
and n’, where n’ = resolve(C,n)
{ n’ } R // add n’ to R if not already there
{ C } Sn’ // add C to Sn’ if not already there
Sm SubTypes(StaticType(p)) Sn’
Sn’ SubTypes(StaticType(ret)) Sm
(p denotes the parameter of n’, and ret
denotes the return of n’) 10
∈
∩
∩
∩
10
6XTA
4. for each method m R,
each field read x = y.f in m
Sf Sm
5. for each method m R,
each field write x.f = y in m
Sm SubTypes(StaticType(f)) Sf
11
∈
∩
∈
CSCI 4450/6450, A Milanova
11
Practical Concerns
n Multiple parameters
n Direct calls
n either static invoke calls or
n special invoke calls
n Array reads and writes!
n Static fields
n See Tip and Palsberg for more
CSCI 4450/6450, A Milanova 12
12
7Example: RTA vs. XTA
public class Main {
public static void main() {
n1();
n2();
}
static void n1() {
A a1 = new B();
a1.m();
}
static void n2() {
A a2 = new C();
a2.m();
}
}CSCI 4450/6450, A Milanova 13
m()
A
B C
G D E
m()
m()
m()
13
public class AndExp extends BoolExp {
private BoolExp left;
private BoolExp right;
public AndExp(BoolExp left, BoolExp right) {
this.left = left;
this.right = right;
}
public boolean evaluate(Context c) {
private BoolExp l = this.left;
private BoolExp r = this.right;
return l.evaluate(c) && r.evaluate(c);
}
} 14
Boolean Expression Hierarchy:
RTA vs. XTA vs. “Ground Truth”
14
8public class OrExp extends BoolExp {
private BoolExp left;
private BoolExp right;
public OrExp(BoolExp left, BoolExp right) {
this.left = left;
this.right = right;
}
public boolean evaluate(Context c) {
private BoolExp l = this.left;
private BoolExp r = this.right;
return l.evaluate(c) || r.evaluate(c);
}
} 15
Boolean Expression Hierarchy:
RTA vs. XTA vs. “Ground Truth”
15
main() {
Context theContext = new Context();
BoolExp x = new VarExp(“X”);
BoolExp y = new VarExp(“Y”);
BoolExp exp = new AndExp(
new Constant(true), new OrExp(x, y) );
theContext.assign(x, true);
theContext.assign(y, false);
boolean result = exp.evaluate(theContext);
}
Boolean Expression Hierarchy:
RTA vs. XTA vs. “Ground Truth”
CSCI 4450/6450, A Milanova 16
16
9Outline of Today’s Class
n Rapid Type Analysis (RTA), last time
n HW2, Class analysis framework questions?
n The XTA analysis family
n 0-CFA
n Points-to analysis (PTA)
CSCI 4450/6450, A Milanova 17
17
n Described in Tip and Palsbserg’s paper
n 0-CFA stands for 0-level Control Flow
Analysis, where “0-level” stands for
context-insensitive analysis
n Will see 1-CFA, 2-CFA, … k-CFA later
n Improves on XTA by storing even more
information about flow of class types
0-CFA
CSCI 4450/6450, A Milanova 18
18
10
0-CFA
R is the set of reachable methods
Sv is the set of types that flow to variable v
Sf is the set of types that flow to field f
1. { main } R
2. for each method m R and
each new site x = new C in m
{ C } Sx 19
∈
19
0-CFA
3. for each method m R,
each virtual call x = y.n(z) in m,
each class C in Sy
and n’, where n’ = resolve(C,n)
{ n’ } R
{ C } Sthis
Sz SubTypes(StaticType(p)) Sp
Sret SubTypes(StaticType(x)) Sx
(this is the implicit parameter of n’, p is the
parameter of n’, and ret is the return of n’) 20
∈
∩
∩
20
11
0-CFA
4. for each method m R,
each field read x = y.f in m
Sf SubTypes(StaticType(x)) Sx
5. for each method m R,
each field write x.f = y in m
Sy SubTypes(StaticType(f)) Sf
21
∈
∩
∈
CSCI 4450/6450, A Milanova
∩
21
0-CFA
6. for each method m R,
each assignment x = y in m
Sy SubTypes(StaticType(x)) Sx
22
∈
CSCI 4450/6450, A Milanova
∩
22
12
Example: XTA vs. 0-CFA
public class Main {
public static void main() {
A a1 = new B();
a1.m();
A a2 = new C();
a2.m();
}
}
CSCI 4450/6450, A Milanova 23
m()
A
B C
G D E
m()
m()
m()
23
public class AndExp extends BoolExp {
private BoolExp left;
private BoolExp right;
public AndExp(BoolExp left, BoolExp right) {
this.left = left;
this.right = right;
}
public boolean evaluate(Context c) {
private BoolExp l = this.left;
private BoolExp r = this.right;
return l.evaluate(c) && r.evaluate(c);
}
} 24CSCI 4450/6450, A Milanova
Boolean Expression Hierarchy:
XTA vs. 0-CFA
24
13
public class OrExp extends BoolExp {
private BoolExp left;
private BoolExp right;
public OrExp(BoolExp left, BoolExp right) {
this.left = left;
this.right = right;
}
public boolean evaluate(Context c) {
private BoolExp l = this.left;
private BoolExp r = this.right;
return l.evaluate(c) || r.evaluate(c);
}
}CSCI 4450/6450, A Milanova 25
Boolean Expression Hierarchy:
XTA vs. 0-CFA
25
main() {
Context theContext = new Context();
BoolExp x = new VarExp(“X”);
BoolExp y = new VarExp(“Y”);
BoolExp exp = new AndExp(
new Constant(true), new OrExp(x, y) );
theContext.assign(x, true);
theContext.assign(y, false);
boolean result = exp.evaluate(theContext);
}
Boolean Expression Hierarchy:
XTA vs. 0-CFA
CSCI 4450/6450, A Milanova 26
26
14
Outline of Today’s Class
n Rapid Type Analysis (RTA), last time
n HW2, Class analysis framework questions?
n The XTA analysis family
n 0-CFA
n Points-to analysis (PTA)
CSCI 4450/6450, A Milanova 27
27
n Widely referred to as Andersen’s points-to
analysis for Java
n Improves on 0-CFA by storing information
about objects, not classes
n A a1 = new A(); // o1
n A a2 = new A(); // o2
PTA
CSCI 4450/6450, A Milanova 28
28
15
PTA
R is the set of reachable methods
Pt(v) is the set of objects that v may point to
Pt(o.f) is the set of objects that field f of object
o may point to
1. { main } R
2. for each method m R and
each new site i: x = new C in m
{ oi } Pt(x) // instead of C, we have oi
29
∈
29
PTA
3. for each method m R,
each virtual call x = y.n(z) in m,
each class oi in Pt(y)
and n’, where n’ = resolve(class_of(oi),n)
{ n’ } R
{ oi } Pt(this)
Pt(z) SubTypes(StaticType(p)) Pt(p)
Pt(ret) SubTypes(StaticType(x)) Pt(x)
(this is the implicit parameter of n’, p is the
parameter of n’, and ret is the return of n’) 30
∈
∩
∩
class_of(o) returns the
class of object o
30
16
PTA
4. for each method m R,
each field read x = y.f in m
for each object o Pt(y)
Pt(o.f) SubTypes(StaticType(x)) Pt(x)
5. for each method m R,
each field write x.f = y in m
for each object o Pt(x)
Pt(y) SubTypes(StaticType(f)) Pt(o.f)
31
∈
∩
∈
∩
∈
∈
31
PTA
6. for each method m R,
each assignment stmt x = y in m
Pt(y) SubTypes(StaticType(x)) Pt(x)
32
∈
CSCI 4450/6450, A Milanova
∩
32
17
Example: 0-CFA vs. PTA
public class Main {
public static void main() {
X x1 = new X(); // o1
A a1 = new B(); // o2
x1.f = a1; // o1.f points to o2
A a2 = x1.f; // a2 points to o2
a2.m();
X x2 = new X(); // o3
A a3 = new C(); // o4
x2.f = a3; // o3.f points to o4
A a4 = x2.f; // a4 points to o4
a4.m();
}
}
33
m()
A
B C
G D E
m()
m()
m()
33
CSCI 4450/6450, A Milanova 34
34
18
Big Picture
n All fit into our monotone dataflow framework!
n Flow-insensitive, context-insensitive
n Compute single solution S
n Algorithms differ mainly in “size” of S
n RTA: only 2 kinds of statements; Lattice?
n XTA: expands to all statements; Lattice?
n 0-CFA: all statements; Lattice?
n PTA (Points-to analysis): all statements; Lattice
elements are points-to graphs
CSCI 4450/6450, A Milanova 35
35
The Big Picture
CSCI 4450/6450, A Milanova 36
Types: A B C D
I
A B C D …
Sm1 Sm2 … Smk Sf1 … Sfk
A B C D …
v1, v2, … vn v1, v2, … vn
o1:A o2:A o3:B o4:B o5:C o6:D …
RTA: XTA:
0-CFA: PTA: