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:
