Chapter 2.Background:Context-Sensitive Points-to Analysis 9 in a similar fashion. Context-Sensitivity for Points-to Analysis Context-sensitivity is shown to be useful for improving the precision of points-to analysis for Java programs in practice [99,39,79,75,41,42,72,43].A traditional context-sensitive points-to analysis analyzes the same methods and heap objects that under different call- ing conterts separately.By this way,the analysis aims to avoid the precision loss caused by the conflation of the behaviors across different interprocedural dynamic execution paths.In theory,the calling context can be generalized as certain ab- straction of the program states regarding to the control flow at the call site.As a result,different variants of context-sensitivity are available and they are usually distinguished by the different context elements used. For object-oriented languages such as Java,three kinds of context-sensitivity are commonly used,i.e.,call-site-sensitivity [71,99,34,object-sensitivity [53,55] as well as type-sensitivity [75],and their contexts consist of sequences of call sites, abstract heap objects (allocation sites)and types,respectively.They will be ex- plained and formalized in Section 2.2 and used in Chapters 3 and 4. In a program,the calling contexts of its methods and heap objects can be infinite in the presence of recursive calls.Even without recursion,the space of calling contexts can be tremendous in the programs with numerous execution paths. To ensure termination and improve scalability,context-sensitive points-to analyses usually limit the length of contexts by a given parameter k and thus restrict the space of contexts during the analysis.As a result,a context-sensitive points-to analysis can be parameterized and tuned by k. When analyzing Java programs,there are two types of context,a method contert for local variables in methods and a heap contert for heap objects.The relationship between context parameter k and the two types of context must be clarified.In the
Chapter 2. Background: Context-Sensitive Points-to Analysis 9 in a similar fashion. Context-Sensitivity for Points-to Analysis Context-sensitivity is shown to be useful for improving the precision of points-to analysis for Java programs in practice [99, 39, 79, 75, 41, 42, 72, 43]. A traditional context-sensitive points-to analysis analyzes the same methods and heap objects that under different calling contexts separately. By this way, the analysis aims to avoid the precision loss caused by the conflation of the behaviors across different interprocedural dynamic execution paths. In theory, the calling context can be generalized as certain abstraction of the program states regarding to the control flow at the call site. As a result, different variants of context-sensitivity are available and they are usually distinguished by the different context elements used. For object-oriented languages such as Java, three kinds of context-sensitivity are commonly used, i.e., call-site-sensitivity [71, 99, 34], object-sensitivity [53, 55] as well as type-sensitivity [75], and their contexts consist of sequences of call sites, abstract heap objects (allocation sites) and types, respectively. They will be explained and formalized in Section 2.2 and used in Chapters 3 and 4. In a program, the calling contexts of its methods and heap objects can be infinite in the presence of recursive calls. Even without recursion, the space of calling contexts can be tremendous in the programs with numerous execution paths. To ensure termination and improve scalability, context-sensitive points-to analyses usually limit the length of contexts by a given parameter k and thus restrict the space of contexts during the analysis. As a result, a context-sensitive points-to analysis can be parameterized and tuned by k. When analyzing Java programs, there are two types of context, a method context for local variables in methods and a heap context for heap objects. The relationship between context parameter k and the two types of context must be clarified. In the
Chapter 2.Background:Context-Sensitive Points-to Analysis 10 rest of this thesis,we adopt the convention of points-to analysis as in [75],i.e.,a k-context-sensitive points-to analysis refers to the analysis whose method contexts consist of k context elements and its heap contexts consist of k-1 context elements. For example,in 2-call-site-sensitive points-to analysis,each method context consists of 2 call sites and each heap context consists of 1 call site. 2.2 Formalism This section gives a standard formulation of context-sensitive points-to analysis for Java.We present the notations used in Section 2.2.1.In Section 2.2.2,we introduce a generic formulation of context-sensitive points-to analysis.Finally,we formalize three specific kinds of context-sensitivity in Section 2.2.3. 2.2.1 Notations In Figure 2.1,the notations include three parts.The top part lists the basic domains of context-sensitive points-to analysis.The middle part gives two domains about context.As mentioned in Section 2.1,there are two types of context,i.e.,method context (C)and heap context (HC)for decorating local variables and heap objects respectively.These two domains are both the composition of the basic domains in the top part,and they vary with the different kinds of context-sensitivity used. The last part gives the five key relations in context-sensitive points-to analysis. pt and fpt store the analysis results:pt(c,x)represents the points-to set of variable x under context c and fpt(hc,oi,f)represents the points-to set of field access o:.f where oi's heap context is specified by hc. mtdCtrSelector and heapCtrSelector are the core of context-sensitivity.They choose the method contexts for the local variables in the methods and heap contexts
Chapter 2. Background: Context-Sensitive Points-to Analysis 10 rest of this thesis, we adopt the convention of points-to analysis as in [75], i.e., a k-context-sensitive points-to analysis refers to the analysis whose method contexts consist of k context elements and its heap contexts consist of k−1 context elements. For example, in 2-call-site-sensitive points-to analysis, each method context consists of 2 call sites and each heap context consists of 1 call site. 2.2 Formalism This section gives a standard formulation of context-sensitive points-to analysis for Java. We present the notations used in Section 2.2.1. In Section 2.2.2, we introduce a generic formulation of context-sensitive points-to analysis. Finally, we formalize three specific kinds of context-sensitivity in Section 2.2.3. 2.2.1 Notations In Figure 2.1, the notations include three parts. The top part lists the basic domains of context-sensitive points-to analysis. The middle part gives two domains about context. As mentioned in Section 2.1, there are two types of context, i.e., method context (C) and heap context (HC) for decorating local variables and heap objects respectively. These two domains are both the composition of the basic domains in the top part, and they vary with the different kinds of context-sensitivity used. The last part gives the five key relations in context-sensitive points-to analysis. pt and fpt store the analysis results: pt(c, x) represents the points-to set of variable x under context c and fpt(hc, oi , f) represents the points-to set of field access oi .f where oi ’s heap context is specified by hc. mtdCtxSelector and heapCtxSelector are the core of context-sensitivity. They choose the method contexts for the local variables in the methods and heap contexts
Chapter 2.Background:Context-Sensitive Points-to Analysis 11 class type t∈T variable x,y∈V heap object 0,0j∈H field f∈F method m∈M method invocation l∈I method context c∈C heap context hc∈HC pt:C×V→P(HC×H) fpt:HC×H×F→P(HC×H) mtdCtrSelector CXI×HC×H→C heapCtxSelector Cx H>HC contertsOf:M→P(C) Figure 2.1:Notations. for object allocations.Specifically,mtdCtrSelector uses the information available at a call site,i.e.,the method context for the method containing the call site (C), the label of the call site (I),the receiver object of the call site (H)and the heap context for the receiver object (HC),to select a new method context for the local variables in the callee of the call site. Which input elements are used to select a context by the selector depends on the specific context-sensitivity used.For example,the selector of call-site-sensitivity only uses the first two input elements,i.e.,a method context (C)and a label of the call site (I),to select a new context.But the selector of object-sensitivity only considers the last input elements to select contexts. heapCtrSelector uses the information available at an allocation site of a heap object (i.e.,the method context for the method containing the allocation site (C) and the heap object (H)allocated at the site)to select a new heap context for the heap object. Finally,contertsOf maps a method to its method contexts
Chapter 2. Background: Context-Sensitive Points-to Analysis 11 class type t ∈ T variable x, y ∈ V heap object oi , oj ∈ H field f ∈ F method m ∈ M method invocation l ∈ I method context c ∈ C heap context hc ∈ HC pt : C × V → P(HC × H) fpt : HC × H × F → P(HC × H) mtdCtxSelector : C × I × HC × H → C heapCtxSelector : C × H → HC contextsOf : M → P(C) Figure 2.1: Notations. for object allocations. Specifically, mtdCtxSelector uses the information available at a call site, i.e., the method context for the method containing the call site (C), the label of the call site (I), the receiver object of the call site (H) and the heap context for the receiver object (HC), to select a new method context for the local variables in the callee of the call site. Which input elements are used to select a context by the selector depends on the specific context-sensitivity used. For example, the selector of call-site-sensitivity only uses the first two input elements, i.e., a method context (C) and a label of the call site (I), to select a new context. But the selector of object-sensitivity only considers the last input elements to select contexts. heapCtxSelector uses the information available at an allocation site of a heap object (i.e., the method context for the method containing the allocation site (C) and the heap object (H) allocated at the site) to select a new heap context for the heap object. Finally, contextsOf maps a method to its method contexts
Chapter 2.Background:Context-Sensitive Points-to Analysis 12 2.2.2 Context-Sensitive Points-to Analysis Figure 2.2 gives a generic formulation of context-sensitive points-to analysis that is parameterized by the two context selectors,mtdCtrSelector and heapCtrSelector. If the two selectors are defined to always return a constant value,then the analysis will be reduced to a context-insensitive points-to analysis.We will see three sets of instances of mtdCtrSelector and heapCtrSelector in Section 2.2.3 that correspond to three kinds of context-sensitivity.Now let us go through the rules in Figure 2.2. m:the containing method for each statement being analysed i:x new T()cE contertsOf(m)hc=heapCtrSelector(c,oi) NEW] (hc,o〉∈pt(c,x) x=yc∈contertsOfm）[ASSIGN]] pt(c,y）Cpt(c,x) x=y.fc∈contertsOfm）(hco）∈t(c,》LoA可 fpt(hc,oi,f)pt(c,) x.f=yc∈contertsOf(m)(hc,o)∈pt(c,x) [STORE] pt(c,y）fpt(hc,o,f) 1:x=y.g(arg1,..,argn)c∈contertsOf(m)(hc,o〉∈pt(c,y） m'=dispatch(oi,g)d=mtdCtxSelector(c,1,he,oi) d∈contertsOf(m'）(hc,oi）∈pt(c,mhis) [CALL] Y1<k<n:pt(c,argk)Cpt(c,mpk)pt(d,mret)C pt(c,x) Figure 2.2:Context-sensitive points-to analysis. In [NEw],object creation is handled.This rule identifies uniquely the abstract object o:created as an instance of T at allocation site i,with heap context hc selected by heapCtrSelector and puts o:(with he)into the points-to set of the variable x under context c.Here,heapCtrSelector uses the context of the method m which contains the allocation site i and i itself to compound a heap context hc for o;.Then the abstract object o:will be analyzed under hc and distinguished
Chapter 2. Background: Context-Sensitive Points-to Analysis 12 2.2.2 Context-Sensitive Points-to Analysis Figure 2.2 gives a generic formulation of context-sensitive points-to analysis that is parameterized by the two context selectors, mtdCtxSelector and heapCtxSelector. If the two selectors are defined to always return a constant value, then the analysis will be reduced to a context-insensitive points-to analysis. We will see three sets of instances of mtdCtxSelector and heapCtxSelector in Section 2.2.3 that correspond to three kinds of context-sensitivity. Now let us go through the rules in Figure 2.2. m: the containing method for each statement being analysed i: x = new T() c ∈ contextsOf(m) hc = heapCtxSelector(c, oi) hhc, oii ∈ pt(c, x) [New] x = y c ∈ contextsOf(m) pt(c, y) ⊆ pt(c, x) [Assign] x = y.f c ∈ contextsOf(m) hhc, oii ∈ pt(c, y) fpt(hc, oi , f) ⊆ pt(c, x) [Load] x.f = y c ∈ contextsOf(m) hhc, oii ∈ pt(c, x) pt(c, y) ⊆ fpt(hc, oi , f) [Store] l: x = y.g(arg1,...,argn) c ∈ contextsOf(m) hhc, oii ∈ pt(c, y) m0 = dispatch(oi , g) c 0 = mtdCtxSelector(c, l, hc, oi) c 0 ∈ contextsOf(m0 ) hhc, oii ∈ pt(c 0 , m0 this) ∀ 1 ≤ k ≤ n : pt(c, argk) ⊆ pt(c 0 , m0 pk) pt(c 0 , m0 ret) ⊆ pt(c, x) [Call] Figure 2.2: Context-sensitive points-to analysis. In [New], object creation is handled. This rule identifies uniquely the abstract object oi created as an instance of T at allocation site i, with heap context hc selected by heapCtxSelector and puts oi (with hc) into the points-to set of the variable x under context c. Here, heapCtxSelector uses the context of the method m which contains the allocation site i and i itself to compound a heap context hc for oi . Then the abstract object oi will be analyzed under hc and distinguished
Chapter 2.Background:Context-Sensitive Points-to Analysis 13 from the other o;that are allocated at i but with different heap contexts. [AssIGN]deals with local assignment.It makes the points-to set of variable y as the subset of the points-to set of variable x under context c. In LOAD]and SToREl,field read and write are handled respectively.Note that we analyze an array object with its elements collapsed to one pseudo-field,denoted arr as in [80,42.Hence,x =y[i](x[i]y)is handled as x y.arr (x.arr y)by [LOAD]([STORE]). [CALL]handles method invocation.It uses function dispatch(oi,g)to resolve the virtual dispatch of method g on the receiver object o;to be m'.Here,mtdCtrSelector is used to leverage the information available at call site l,i.e.,the context c of the method m that contains l,the call site l itself,the receiver object o;and its heap context hc,to work out a context c'for the callee m',then m'will be analyzed under context c. [CALL]also deals with the context-sensitive interprocedural assignment between call site I and callee m'.We assume that m'has a formal parameter mihis for the receiver object and mpl,..,min for the remaining parameters,and a pseudo- variable m is used to hold the return value of m.[CALL]assigns the abstract objects pointed by arguments y and argl,...,argn at call site l (under context c) to the parameters of callee m',i.e.,ms and mp,.,m (under context c).In addition,[CALL]makes the points-to set of met(under context c)as the subset of the points-to set of return variable x (under context c). 2.2.3 Context-Sensitivity In this section,we present three mainstream variants of context-sensitivity and express them as the instances of mtdCtrSelector and heapCtrSelector. In each context-sensitivity,heapCtzSelector simply selects the context of the
Chapter 2. Background: Context-Sensitive Points-to Analysis 13 from the other oi that are allocated at i but with different heap contexts. [Assign] deals with local assignment. It makes the points-to set of variable y as the subset of the points-to set of variable x under context c. In [Load] and [Store], field read and write are handled respectively. Note that we analyze an array object with its elements collapsed to one pseudo-field, denoted arr as in [80, 42]. Hence, x = y[i] (x[i] = y) is handled as x = y.arr (x.arr = y) by [Load] ([Store]). [Call] handles method invocation. It uses function dispatch(oi , g) to resolve the virtual dispatch of method g on the receiver object oi to be m0 . Here, mtdCtxSelector is used to leverage the information available at call site l, i.e., the context c of the method m that contains l, the call site l itself, the receiver object oi and its heap context hc, to work out a context c 0 for the callee m0 , then m0 will be analyzed under context c 0 . [Call] also deals with the context-sensitive interprocedural assignment between call site l and callee m0 . We assume that m0 has a formal parameter m0 this for the receiver object and m0 p1 , ..., m0 pn for the remaining parameters, and a pseudovariable m0 ret is used to hold the return value of m0 . [Call] assigns the abstract objects pointed by arguments y and arg1, ..., argn at call site l (under context c) to the parameters of callee m0 , i.e., m0 this and m0 p1 , ..., m0 pn (under context c 0 ). In addition, [Call] makes the points-to set of m0 ret (under context c 0 ) as the subset of the points-to set of return variable x (under context c). 2.2.3 Context-Sensitivity In this section, we present three mainstream variants of context-sensitivity and express them as the instances of mtdCtxSelector and heapCtxSelector. In each context-sensitivity, heapCtxSelector simply selects the context of the