Finally,BEAN is expected to be more precise than k-obj in general,with a precision that is guaranteed to be as good as k-obj in the worst case. 4 Formalism Without loss of generality,we formalise BEAN as a k-object-sensitive pointer analysis with a(k-1)-context-sensitive heap (with respect to allocation sites), as in [14].Thus,the depth of its method (heap)contexts is k(k-1). 4.1 Notations We will use the notations in Fig.5.The variable r,yeV top section lists the domains used.As we heap objecto,o;∈H method m∈M focus on object-sensitive analysis,a con- field fEF text is a sequence of objects.The mid- context c∈C=H°UHUH2. dle section gives the five key relations pt:C×V+P(C×H) used.pt and fpt store the analysis results: fpt:C×HxF→P(C×H) pt(c,r)represents the points-to set of vari- mtdCtrSelector:Cx HC able x under context c and fpt(c,oi,f) heapC'trSelector:CxHC contertsOf:M→P(C) represents the points-to set of the field f of an abstract object oi under con- OAG G=(N,E) text c.mtdCtrSelector and heapCtrSelector odoi,oj∈NsH choose the method contexts for method edge o→o∈EsN×N calls and heap contexts for allocation sites, Fig.5:Notations. respectively.contertsOf maps a method to its contexts.The last section defines the OAG used for a program:oioj means that oi is an allocator object of oj,i.e.,the receiver object of the method that made the allocation of oj. 4.2 Object Allocation Graph Figure 6 gives the rules for building the OAG,G=(N,E),for a program, based on the points-to sets computed by a pre-analysis,which may or may not be context-sensitive.As G is (currently)context-insensitive,the context information that appears in a points-to set (if any)is simply ignored.[OAG-NODE] and [OAG-DUMMYNODE]build N.[OAG-EDGE]and [OAG-DUMMYEDGE]build E. By [OAG-NoDEl,we add to N all the pointed-to target objects found during the pre-analysis.By [OAG-DUMMYNoDEl,we add a dummy node oroot to N. By [OAG-EDGEl,we add to E an edge oioj if oi is an allocator object of oj. Here,mthis,where m is the name of a method,represents the this variable of method m,which points to the receiver object of method m.By [OAG-DUvEDGEl, we add an edge from oroot to every object oi without any incoming edge yet,to indicate that oroot is now a pseudo allocator object of o.Note that an object allocated in main()or a static initialiser does not have an allocator object.Due to oroot,every object has at least one allocator object.Finally, Bean is expected to be more precise than k-obj in general, with a precision that is guaranteed to be as good as k-obj in the worst case. 4 Formalism Without loss of generality, we formalise Bean as a k-object-sensitive pointer analysis with a (k − 1)-context-sensitive heap (with respect to allocation sites), as in [14]. Thus, the depth of its method (heap) contexts is k (k − 1). 4.1 Notations variable x, y ∈ V heap object oi , oj ∈ H method m ∈ M field f ∈ F context c ∈ C = H0 ∪ H1 ∪ H2 ... pt : C × V → P(C × H) fpt : C × H × F → P(C × H) mtdCtxSelector : C × H → C heapCtxSelector : C × H → C contextsOf : M → P(C) OAG G = (N, E) node oi , oj ∈ N ⊆ H edge oi → oj ∈ E ⊆ N × N Fig. 5: Notations. We will use the notations in Fig. 5. The top section lists the domains used. As we focus on object-sensitive analysis, a con￾text is a sequence of objects. The mid￾dle section gives the five key relations used. pt and fpt store the analysis results: pt(c, x) represents the points-to set of vari￾able x under context c and fpt(c, oi , f) represents the points-to set of the field f of an abstract object oi under con￾text c. mtdCtxSelector and heapCtxSelector choose the method contexts for method calls and heap contexts for allocation sites, respectively. contextsOf maps a method to its contexts. The last section defines the OAG used for a program: oi → oj means that oi is an allocator object of oj , i.e., the receiver object of the method that made the allocation of oj . 4.2 Object Allocation Graph Figure 6 gives the rules for building the OAG, G = (N, E), for a program, based on the points-to sets computed by a pre-analysis, which may or may not be context-sensitive. As G is (currently) context-insensitive, the context information that appears in a points-to set (if any) is simply ignored. [OAG-Node] and [OAG-DummyNode] build N. [OAG-Edge] and [OAG-DummyEdge] build E. By [OAG-Node], we add to N all the pointed-to target objects found during the pre-analysis. By [OAG-DummyNode], we add a dummy node oroot to N. By [OAG-Edge], we add to E an edge oi → oj if oi is an allocator object of oj . Here, mthis, where m is the name of a method, represents the this variable of method m, which points to the receiver object of method m. By [OAG-DummyEdge], we add an edge from oroot to every object oi without any incoming edge yet, to indicate that oroot is now a pseudo allocator object of oi . Note that an object allocated in main() or a static initialiser does not have an allocator object. Due to oroot, every object has at least one allocator object