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 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 ` ∈ 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 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 (` 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