discovered,we construct an object allocation graph (OAG)to capture the ob- ject allocation relations in k-obj.Subsequently,we traverse the OAG to select method and heap contexts by avoiding redundant context elements that would otherwise be used by k-obj.In Stage 2,we refine k-obj by avoiding its redun- dant context elements.Essentially,we perform a k-object-sensitive analysis in the normal way,by using the contexts selected in the first stage,instead. 3.1 Object Allocation Graph The OAG of a program is a directed graph,G=(N,E).A node eE N represents a label of an (object)allocation site in the program.An edge 12E E represents an object allocation relation.As G is context-insensitive.a label eE G is also interchangeably referred to (in the literature)as the (unique)abstract heap object that models all the concrete objects created at the allocation site e. Given this,e1>2 signifies that e is the the receiver object of the method that made the allocation of 2.Therefore,e is called an allocator object of e2 [29]. (a)Fig.1 (b)Fig.2 (c)Example 2 Fig.4:The OAGs for the two motivating programs in Figs.1 and 2. Figure 4 gives the OAGs for the two programs in Figs.1 and 2,which are de- liberately designed to be isomorphic.In Fig.4(a),A/1 and A/2 are two allocators of B/1.In Fig.4(b),AL/1 is an allocator of Obj[]/1.Some objects,e.g.,those created in main()or static initialisers,have no allocators.For convenience,we assume the existence of a dummy node,Oroot,so that every object has at least one allocator.The isomorphic OAG in Fig.4(c)will be referred to in Example 2. The concept of allocator object captures the essence of object sensitivity.By definition [24,29],a context for an allocation site i.e.,an abstract object consists of its allocator object (e),the allocator object of e,and so on.The OAG provides a new perspective for object sensitivity,since a context for an object e is simply a path from Oroot to e.As a result,the problem of selecting contexts for e can be recast as one of solving a problem of distinguishing different paths from Oroot to l.Traditionally,a k-object-sensitive analysis selects blindly a suffix of a path from Oroot to e with length k
discovered, we construct an object allocation graph (OAG) to capture the object allocation relations in k-obj. Subsequently, we traverse the OAG to select method and heap contexts by avoiding redundant context elements that would otherwise be used by k-obj. In Stage 2, we refine k-obj by avoiding its redundant context elements. Essentially, we perform a k-object-sensitive analysis in the normal way, by using the contexts selected in the first stage, instead. 3.1 Object Allocation Graph The OAG of a program is a directed graph, G = (N, E). A node ` ∈ N represents a label of an (object) allocation site in the program. An edge `1 → `2 ∈ E represents an object allocation relation. As G is context-insensitive, a label ` ∈ G is also interchangeably referred to (in the literature) as the (unique) abstract heap object that models all the concrete objects created at the allocation site `. Given this, `1 → `2 signifies that `1 is the the receiver object of the method that made the allocation of `2. Therefore, `1 is called an allocator object of `2 [29]. O A/1 root A/2 B/1 C/1 O/1 O/2 O Co/1 root Co/2 AL/1 Obj[]/1 Emp/1 Emp/2 O O1 root O2 O3 O4 O5 O6 (a) Fig. 1 (b) Fig. 2 (c) Example 2 Fig. 4: The OAGs for the two motivating programs in Figs. 1 and 2. Figure 4 gives the OAGs for the two programs in Figs. 1 and 2, which are deliberately designed to be isomorphic. In Fig. 4(a), A/1 and A/2 are two allocators of B/1. In Fig. 4(b), AL/1 is an allocator of Obj[]/1. Some objects, e.g., those created in main() or static initialisers, have no allocators. For convenience, we assume the existence of a dummy node, Oroot, so that every object has at least one allocator. The isomorphic OAG in Fig. 4(c) will be referred to in Example 2. The concept of allocator object captures the essence of object sensitivity. By definition [24, 29], a context for an allocation site `, i.e., an abstract object ` consists of its allocator object (` 0 ), the allocator object of ` 0 , and so on. The OAG provides a new perspective for object sensitivity, since a context for an object ` is simply a path from Oroot to `. As a result, the problem of selecting contexts for ` can be recast as one of solving a problem of distinguishing different paths from Oroot to `. Traditionally, a k-object-sensitive analysis selects blindly a suffix of a path from Oroot to ` with length k
3.2 Context Selection Given an object e in G,BEAN selects its contexts in G as sequences of its direct or indirect allocators that are useful to distinguish different paths from Oroot to e while avoiding redundant ones that would otherwise be used in k-obj.The key insight is that in many cases,it is unnecessary to use all nodes of a path to distinguish the path from the other paths leading to the same node.In contrast, k-obj is not equipped with G and thus has to select blindly a suffix of each such path as a context,resulting in many redundant context elements being used. Method Contexts Figure 1 compares the method contexts used by 2obj+h and BEAN for the first example given.As shown in Figure 1(b),2obj+h analyses C.identity()under one context B/1,C/1],where B/1 is redundant,without being able to separate its two concrete calling contexts.In contrast,BEAN avoids using B/1 by examining the OAG of this example in Fig.4(a).There are two paths from0 root to C/1:0root→A/1→B/1→C/1and0root→A/2→B/1→ C/1.Note that 2obj+h has selected a suffix of the two paths,B/1-C/1,which happens to represent the same context [B/1,C/1]for C.identity().BEAN dis- tinguishes these two paths by ignoring the redundant node B/1,thereby settling with the method contexts shown in Figure 1(c).As a result,C.identity()is now analysed under two different contexts [A/1,C/1]and [A/2,C/1]more precisely. Heap Contexts Figure 2 compares the heap contexts used by 2objth and BEAN for the second example given.As shown in Figure 2(b),2obj+h fails to separate the two array objects created at the allocation site Obj[]/1 for two companies Co/1 and Co/2 by using one context [AL/1],where AL/1 is redundant. In contrast,BEAN avoids using AL/1 by examining the OAG of this example in Fig.4(b).There are two paths from Oroot to Obj[]/1:Oroot Co/1 AL/1→0bj[☐/1and0root→Co/2→AL/1→0bj[0/1.Note that2ob+hhas selected a suffix of the two paths,AL/1-Obj[]/1,which happens to represent the same heap context [AL/1]for Obj[]/1.BEAN distinguishes these two paths by ignoring the redundant node AL/1,thereby settling with the heap contexts shown in Figure 2(c).As a result,the two array objects created at Obj[]/1 are distinguished under two different contexts [Co/1]and [Co/2]more precisely. 3.3 Discussion BEAN,as shown in Fig.3,is designed to be a general-purpose technique for refining k-obj with three design goals,under the condition that its pre-analysis is sound.First,as the pre-analysis is usually less precise than k-obj,the OAG constructed for the program may contain some object allocation relations that are not visible in k-obj.Therefore,BEAN is not expected to be optimal in the sense that it can avoid all redundant context elements in k-obj.Second,if the pre-analysis is more precise than k-obj(e.g.,in some parts of the program),then the OAG may miss some object allocation relations that are visible in k-obj.This allows BEAN to avoid using context elements that are redundant with respect to the pre-analysis but not k-obj,making the resulting analysis even more precise
3.2 Context Selection Given an object ` in G, Bean selects its contexts in G as sequences of its direct or indirect allocators that are useful to distinguish different paths from Oroot to ` while avoiding redundant ones that would otherwise be used in k-obj. The key insight is that in many cases, it is unnecessary to use all nodes of a path to distinguish the path from the other paths leading to the same node. In contrast, k-obj is not equipped with G and thus has to select blindly a suffix of each such path as a context, resulting in many redundant context elements being used. Method Contexts Figure 1 compares the method contexts used by 2obj+h and Bean for the first example given. As shown in Figure 1(b), 2obj+h analyses C.identity() under one context [B/1,C/1], where B/1 is redundant, without being able to separate its two concrete calling contexts. In contrast, Bean avoids using B/1 by examining the OAG of this example in Fig. 4(a). There are two paths from Oroot to C/1: Oroot → A/1 → B/1 → C/1 and Oroot → A/2 → B/1 → C/1. Note that 2obj+h has selected a suffix of the two paths, B/1 → C/1, which happens to represent the same context [B/1,C/1] for C.identity(). Bean distinguishes these two paths by ignoring the redundant node B/1, thereby settling with the method contexts shown in Figure 1(c). As a result, C.identity() is now analysed under two different contexts [A/1,C/1] and [A/2,C/1] more precisely. Heap Contexts Figure 2 compares the heap contexts used by 2obj+h and Bean for the second example given. As shown in Figure 2(b), 2obj+h fails to separate the two array objects created at the allocation site Obj[]/1 for two companies Co/1 and Co/2 by using one context [AL/1], where AL/1 is redundant. In contrast, Bean avoids using AL/1 by examining the OAG of this example in Fig. 4(b). There are two paths from Oroot to Obj[]/1: Oroot → Co/1 → AL/1 → Obj[]/1 and Oroot → Co/2 → AL/1 → Obj[]/1. Note that 2obj+h has selected a suffix of the two paths, AL/1 → Obj[]/1, which happens to represent the same heap context [AL/1] for Obj[]/1. Bean distinguishes these two paths by ignoring the redundant node AL/1, thereby settling with the heap contexts shown in Figure 2(c). As a result, the two array objects created at Obj[]/1 are distinguished under two different contexts [Co/1] and [Co/2] more precisely. 3.3 Discussion Bean, as shown in Fig. 3, is designed to be a general-purpose technique for refining k-obj with three design goals, under the condition that its pre-analysis is sound. First, as the pre-analysis is usually less precise than k-obj, the OAG constructed for the program may contain some object allocation relations that are not visible in k-obj. Therefore, Bean is not expected to be optimal in the sense that it can avoid all redundant context elements in k-obj. Second, if the pre-analysis is more precise than k-obj (e.g., in some parts of the program), then the OAG may miss some object allocation relations that are visible in k-obj. This allows Bean to avoid using context elements that are redundant with respect to the pre-analysis but not k-obj, making the resulting analysis even more precise