指针分析(Pointso-to Analysis)

1、 XXX 2012.05.18 Determines information about the set of objects to which a reference variable or field may point during program execution Also called alias analysis or pointer analysis Focus on precision and efficiency Call graph construction Dependence analysis and optimization Cast check eliminati

2、on Side effect analysis Escape analysis Slicing Parallelization . Precision Type filtering Field sensitivity Directionality Context-sensitivity Flow-sensitivity Efficiency Client-driven and Demand-driven Analysis Refinement demand-driven analysis BDD-based Analysis Tool Definition lContext-insensiti

3、ve analysis computes, for each method, a single analysis result that holds for all executions of the method; lContext-sensitive analysis produces different analysis results for different invocations. Approach lCall string approach (strings of call sites, k-CFA) lFunctional approach (method arguments

4、, object- sensitivity) lComparision Heap abstraction static void main() A: x,y,w,z; L1: D d1 = new D(); L2: x = new A(); L3: y = new A(); L4: w = d1.f(x); L5: z = d1.f(y); public class D public A f(A a)return a; public class A 1-CFA 1-CFA static void main() A: x,y,w,z; L1: D d1 = new D(); L2: x = ne

5、w A(); L3: y = new A(); L4: w = d1.f(x); L5: z = d1.f(y); public class D public A f(A a)return a; public class A Object sensitivity Object sensitivity public class B Object xx; Void set1 (Object o )L9: set2(o); Void set2 (Object o ) this.xx=o; public Object f() return this.xx; static void main() Obj

6、ect x1,x2,x,y; B: b1, b2; L1: x1 = new Object(); L2: b1 = new B; L3: b1.set1(x1); L4: x2 = new Object(); L5: b2 = new B; L6: b2.set1(x2); L7: x = b1.f(); L8: y = b2.f(); 1-CFA 1-CFA public class B Object xx; Void set1 (Object o )L9: set2(o); Void set2 (Object o ) this.xx=o; public Object f() return

7、this.xx; static void main() Object x1,x2,x,y; B: b1, b2; L1: x1 = new Object(); L2: b1 = new B; L3: b1.set1(x1); L4: x2 = new Object(); L5: b2 = new B; L6: b2.set1(x2); L7: x = b1.f(); L8: y = b2.f(); 1-CFA 1-CFA public class B Object xx; Void set1 (Object o )L9: set2(o); Void set2 (Object o ) this.

8、xx=o; public Object f() return this.xx; static void main() Object x1,x2,x,y; B: b1, b2; L1: x1 = new Object(); L2: b1 = new B; L3: b1.set1(x1); L4: x2 = new Object(); L5: b2 = new B; L6: b2.set1(x2); L7: x = b1.f(); L8: y = b2.f(); Object sensitivity Object sensitivity public class B Object xx; Void

9、 set1 (Object o )L9: set2(o); Void set2 (Object o ) this.xx=o; public Object f() return this.xx; static void main() Object x1,x2,x,y; B: b1, b2; L1: x1 = new Object(); L2: b1 = new B; L3: b1.set1(x1); L4: x2 = new Object(); L5: b2 = new B; L6: b2.set1(x2); L7: x = b1.f(); L8: y = b2.f(); Object sens

10、itivity Object sensitivity The call string and functional approaches to context sensitivity are incomparable! Neither is more powerful than the other In practice, for OO programs, object sensitivity more precise than call-site sensitivity for the same context string length A points-to analysis that

11、takes into account the order in which statements may be executed . Generally provides more precise information than a flow- insensitive analysis. However, flow-sensitive analyses are considerably more costly in terms of time and/or space than flow-insensitive analyses. SSA-based program representati

12、on uEach variable x has exactly one definition site. uEach use of a variable x is reached by exactly one definition. (1): a = 1, b = 2, c = 3; (2): b = 2, c = 3, d = 2; (3): b = 2, d = 2; (1): a0 = 1, b0 = 2, c0 = 3; (2): a0 = 1, b0 = 2, c0 = 3, c0 = 3, a1 = 3, d0 = 2; (3): a0 = 1, b0 = 2, c0 = 3, c

13、0 = 3, a1 = 3, d0 = 2; Unfortunately: This approach will not work! Unfortunately: This approach will not work! (1): pt(a) = w; (1): pt(a0) = w0; (2): pt(p) = a; (2): pt(p0) = a0; (3): pt(a) = x; (3): pt(a1) = x0; (4): pt(c) = x; (4): pt(c) = x; (4): pt(c0) = w0; (4): pt(c0) = w0; Line (6) is a indir

14、ectly definition to variable a, but naive conversion to SSA form does not take this into account! Given: a CFG G Do flow-insensitive pointer analysis on G Annotate the dereferences in G Repeat: step 1: Create the intermediate form (IM) from G step 2: Convert IM to SSA form creating IMSSA step 3: Do

15、flow-insensitive pointer analysis on IMSSA step 4: Update the annotations in G using IMSSA and the pointer analysis results until there are no changes in the annotations Original CFGOriginal CFG (with annotations) Intermediate (Normalized) FormIntermediate (Normalized) Form (*t replaced by s, and *s

16、 replaced by p and q ) Problem Problem 2 is solved2 is solved To SSA Form Phase 1To SSA Form Phase 1 Final SSA FormFinal SSA Form s0 - p; s0 - p; s1- s1- q; q; t0 - s t0 - s Problem Problem 1 is solved1 is solved s0 - p; s0 - p; s1- s1- q; q; t0 - s t0 - s A client-driven analysis adjusts its cost a

17、nd the achieved precision according to the needs of the client analyses (or programs). Subset-based analysis? Context-sensitive? Flow-sensitive? A client-driven points-to analysis, like a regular points- to analysis, is exhaustive; i.e., it computes the points-to sets for all the pointers in a progr

18、am. A demand-driven points-to analysis computes only the required amount of points-to answer a particular query of the client. CFL-reachability: Context-free language reachability Define a graph representation G of a Java program P, with nodes for variables and abstract locations, edges for the diff

19、erent pointer-manipulating statements of P. Use CFL-reachability to match field read and write parentheses. Context-free language LFT: if a heap object represented by abstract location o can flow to variable x, then x will be LFT -reachable from o in G. LFT reachable Points-to relation 1 x = new Obj

20、(); / o1 2 z = new Obj(); / o2 3 w = x; 4 y = x; 5 y.f = z; 6 v = w.f; To make determining LFT-reachability less costly, we assume alias-paths between matched parentheses always exists. 1: P = new O();/ O4 2: q = new O();/O3 3: w = new O();/O2 4: z = new O();/O1 5: v = p.g; 6: q.g = w; 7: y = v.f; 8

21、: w.f = z; 9: x = y; Instead of searching for alias-paths, we refine a match edge by looking for aliasReg-paths. An aliasReg-path may itself contain match edges, and could therefore connect two nodes that are not connected by analias-path. refine the match edge z-y, search for an aliasReg-path from

22、w to v refine the match edge w-v, search for an aliasReg-path from q to p A key problem in developing efficient solvers for the subset-based points-to analysis is that for large programs there are many points-to sets, and each points-to set can be come very large. BDDs have been shown to be effectiv

23、e for compactly representing large sets and for solving large state space problems like those generated in model checking. A: a = new O(); B: b = new O(); C: c = new O(); a = b; b = a; c = b; (a;A); (a;B); (b;A); (b;B); (c;A); (c;B); (c;C) a, A: 00; b, B: 01; C, C: 10; 0000;0001;0100;0101;1000;1001;

24、1010 a, b, c are encoded at BDD node levels V0 and V1; A, B, C are encoded at the H0 and H1 levels. Domain V to represent variables, and H to represent pointed-to heap locations. Relational product: Replace operation A: a = new O(); B: b = new O(); C: c = new O(); a = b; b = a; c = b; the points-to

25、set after one step of propagation SPARK Paddle Chord P2SSA Proposed and implemented by literature SPARK: A FLEXIBLE POINTS-TO ANALYSIS FRAMEWORK FOR JAVA in 2002; Integrated into Soot Field sensitive, context-insensitive, flow- insensitive; Proposed and implemented by literature Program Analysis usi

26、ng Binary Decision Diagrams in 2006; BDD-based points-to analysis Integrated into Soot Paddle supports several variations of context sensitive analysis, including using strings of call sites and of abstract receiver objects as the context abstraction. Static and dynamic program analysis framework fo

27、r Java Started in 2006 as static Checker of races and deadlocks Key goals: uversatile: applies to various analyses, domains, platforms uextensible: users can build own analyses atop given ones uproductive: facilitates rapid prototyping of analyses urobust: deterministic, handles partial programs, et

28、c. Many standard static and dynamic analyses uvarious points-to and call-graph analyses uthread-escape analysis ustatic slicing analysis ustatic and dynamic concurrency analyses for finding races, deadlocks, and atomicity violations Allows users to express a broad range of analyses usummary-based an

29、d cloning-based inter-procedural context-sensitive analyses uIterative refinement-based analyses uClient-driven analyses uCombined static/dynamic analyses. Writing/solving analyses using Datalog/BDDs uDatalog: a declarative logic-programming language uBDD: are a data structure central to executing Datalog analyses Execute analyses in a demand-driven fashion As precise as a flow-sensitive analysis Operate on an SSA form of the