Making k-Object-Sensitive Pointer Analysis More Precise with Still k-Limiting

Making k-Object-Sensitive Pointer Analysis More Precise with Still k-Limiting Tian Tan1,Yue Lil,and Jingling Xuel.2 1 School of Computer Science and Engineering,UNSW Australia 2 Advanced Innovation Center for Imaging Technology,CNU,China Abstract.Object-sensitivity is regarded as arguably the best context abstraction for pointer analysis in object-oriented languages.However,a k-object-sensitive pointer analysis,which uses a sequence of k allocation sites (as k context elements)to represent a calling context of a method call,may end up using some context elements redundantly without in- ducing a finer partition of the space of(concrete)calling contexts for the method call.In this paper,we introduce BEAN,a general approach for improving the precision of any k-object-sensitive analysis,denoted k-obj. by still using a k-limiting context abstraction.The novelty is to identify allocation sites that are redundant context elements in k-obj from an Object Allocation Graph (OAG).which is built based on a pre-analysis (e.g.,a context-insensitive Andersen's analysis)performed initially on a program and then avoid them in the subsequent k-object-sensitive anal- ysis for the program.BEAN is generally more precise than k-obj,with a precision that is guaranteed to be as good as k-obj in the worst case.We have implemented BEAN as an open-source tool and applied it to refine two state-of-the-art whole-program pointer analyses in DooP.For two representative clients (may-alias and may-fail-cast)evaluated on a set of nine large Java programs from the DaCapo benchmark suite,BEAN has succeeded in making both analyses more precise for all these benchmarks under each client at only small increases in analysis cost. 1 Introduction Pointer analysis,as an enabling technology,plays a key role in a wide range of client applications,including bug detection [3,25,35,34],security analysis [1,13], compiler optimisation [6,33],and program understanding [12].Two major di- mensions of pointer analysis precision are flow-sensitivity and context-sensitivity. For C/C++programs,flow-sensitivity is needed by many clients [11,16,37,32]. For object-oriented programs,e.g.,Java programs,however,context-sensitivity is known to deliver trackable and useful precision [17,19-21,28-30],in general. There are two general approaches to achieving context-sensitivity for object- oriented programs,call-site-sensitivity (k-CFA)[27]and object-sensitivity [23. 24,29](among others).A k-CFA analysis represents a calling context of a method call by using a sequence of k call sites(i.e.,k labels with each denoting a call site).In contrast,a k-object-sensitive analysis uses k object allocation sites (i.e., k labels with each denoting a new statement)as context elements

Making k-Object-Sensitive Pointer Analysis More Precise with Still k-Limiting Tian Tan1 , Yue Li1 , and Jingling Xue1,2 1 School of Computer Science and Engineering, UNSW Australia 2 Advanced Innovation Center for Imaging Technology, CNU, China Abstract. Object-sensitivity is regarded as arguably the best context abstraction for pointer analysis in object-oriented languages. However, a k-object-sensitive pointer analysis, which uses a sequence of k allocation sites (as k context elements) to represent a calling context of a method call, may end up using some context elements redundantly without in￾ducing a finer partition of the space of (concrete) calling contexts for the method call. In this paper, we introduce Bean, a general approach for improving the precision of any k-object-sensitive analysis, denoted k-obj, by still using a k-limiting context abstraction. The novelty is to identify allocation sites that are redundant context elements in k-obj from an Object Allocation Graph (OAG), which is built based on a pre-analysis (e.g., a context-insensitive Andersen’s analysis) performed initially on a program and then avoid them in the subsequent k-object-sensitive anal￾ysis for the program. Bean is generally more precise than k-obj, with a precision that is guaranteed to be as good as k-obj in the worst case. We have implemented Bean as an open-source tool and applied it to refine two state-of-the-art whole-program pointer analyses in Doop. For two representative clients (may-alias and may-fail-cast) evaluated on a set of nine large Java programs from the DaCapo benchmark suite, Bean has succeeded in making both analyses more precise for all these benchmarks under each client at only small increases in analysis cost. 1 Introduction Pointer analysis, as an enabling technology, plays a key role in a wide range of client applications, including bug detection [3, 25, 35, 34], security analysis [1, 13], compiler optimisation [6, 33], and program understanding [12]. Two major di￾mensions of pointer analysis precision are flow-sensitivity and context-sensitivity. For C/C++ programs, flow-sensitivity is needed by many clients [11, 16, 37, 32]. For object-oriented programs, e.g., Java programs, however, context-sensitivity is known to deliver trackable and useful precision [17, 19–21, 28–30], in general. There are two general approaches to achieving context-sensitivity for object￾oriented programs, call-site-sensitivity (k-CFA) [27] and object-sensitivity [23, 24, 29] (among others). A k-CFA analysis represents a calling context of a method call by using a sequence of k call sites (i.e., k labels with each denoting a call site). In contrast, a k-object-sensitive analysis uses k object allocation sites (i.e., k labels with each denoting a new statement) as context elements

Among all the context abstractions (including k-CFA)proposed,object- sensitivity is regarded as arguably the best for pointer analysis in object-oriented languages [14,17,29].This can be seen from its widespread adoption in a num- ber of pointer analysis frameworks for Java,such as Doop [7,4],CHORD [5] and WALA [36].In addition,object-sensitivity has also been embraced by many other program analysis tasks,including typestate verification [9,38],data race detection [25],information flow analysis [1,10,22],and program slicing [21]. Despite its success,a k-object-sensitive pointer analysis,which uses a se- quence of k allocation sites (as k context elements)to represent a calling context of a method call,may end up using some context elements redundantly in the sense that these redundant context elements fail to induce a finer partition of the space of(concrete)calling contexts for the method call.As a result,many opportunities for making further precision improvements are missed. In this paper,we introduce BEAN,a general approach for improving the precision of a k-object-sensitive pointer analysis,denoted k-obj,for Java.by avoiding redundant context elements in k-obj while still maintaining a k-limiting context abstraction.The novelty lies in identifying redundant context elements by solving a graph problem on an OAG (Object Allocation Graph),which is built based on a pre-analysis (e.g.,a context-insensitive Andersen's analysis) performed initially on a program,and then avoid them in the subsequent k- object-sensitive analysis.By construction,BEAN is generally more precise than k-obj,with a precision that is guaranteed to be as good as k-obj in the worst case. We have implemented BEAN and applied it to refine two state-of-the-art (whole-program)pointer analyses,2obj+h and S-2obj+h [14],provided in Doop [7],resulting in two BEAN-directed pointer analyses,B-2obj+h and B-S-2obj+h, respectively.We have considered may-alias and may-fail-cast,two representative clients used elsewhere [8,29,30]for measuring the precision of a pointer analysis on a set of nine large Java programs from the DaCapo benchmark suite.Our re- sults show that B-2obj+h (B-S-2obj+h)is more precise than 2obj+h(S-2obj+h) for every evaluated benchmark under each client,at some small increases in analysis cost. This paper presents and validates a new idea on improving the precision of object-sensitive pointer analysis by exploiting an object allocation graph.Con- sidering the broad applications of object-sensitivity in analysing Java programs, we expect more clients to benefit from the BEAN approach,in practice.Specifi- cally,this paper makes the following contributions: -We introduce a new approach,BEAN,for improving the precision of any k- object-sensitive pointer analysis.k-obj.for Java.by avoiding its redundant context elements while maintaining still a k-limiting context abstraction. We introduce a new kind of graph,called an OAG(object allocation graph), constructed from a pre-analysis for the program,as a general mechanism to identify redundant context elements used in k-obj. We have implemented BEAN as a soon-to-be released open-source tool,which is expected to work well with various object-sensitive analyses for Java

Among all the context abstractions (including k-CFA) proposed, object￾sensitivity is regarded as arguably the best for pointer analysis in object-oriented languages [14, 17, 29]. This can be seen from its widespread adoption in a num￾ber of pointer analysis frameworks for Java, such as Doop [7, 4], Chord [5] and Wala [36]. In addition, object-sensitivity has also been embraced by many other program analysis tasks, including typestate verification [9, 38], data race detection [25], information flow analysis [1, 10, 22], and program slicing [21]. Despite its success, a k-object-sensitive pointer analysis, which uses a se￾quence of k allocation sites (as k context elements) to represent a calling context of a method call, may end up using some context elements redundantly in the sense that these redundant context elements fail to induce a finer partition of the space of (concrete) calling contexts for the method call. As a result, many opportunities for making further precision improvements are missed. In this paper, we introduce Bean, a general approach for improving the precision of a k-object-sensitive pointer analysis, denoted k-obj, for Java, by avoiding redundant context elements in k-obj while still maintaining a k-limiting context abstraction. The novelty lies in identifying redundant context elements by solving a graph problem on an OAG (Object Allocation Graph), which is built based on a pre-analysis (e.g., a context-insensitive Andersen’s analysis) performed initially on a program, and then avoid them in the subsequent k￾object-sensitive analysis. By construction, Bean is generally more precise than k-obj, with a precision that is guaranteed to be as good as k-obj in the worst case. We have implemented Bean and applied it to refine two state-of-the-art (whole-program) pointer analyses, 2obj+h and S-2obj+h [14], provided in Doop [7], resulting in two Bean-directed pointer analyses, B-2obj+h and B-S-2obj+h, respectively. We have considered may-alias and may-fail-cast, two representative clients used elsewhere [8, 29, 30] for measuring the precision of a pointer analysis on a set of nine large Java programs from the DaCapo benchmark suite. Our re￾sults show that B-2obj+h (B-S-2obj+h) is more precise than 2obj+h (S-2obj+h) for every evaluated benchmark under each client, at some small increases in analysis cost. This paper presents and validates a new idea on improving the precision of object-sensitive pointer analysis by exploiting an object allocation graph. Con￾sidering the broad applications of object-sensitivity in analysing Java programs, we expect more clients to benefit from the Bean approach, in practice. Specifi- cally, this paper makes the following contributions: – We introduce a new approach, Bean, for improving the precision of any k￾object-sensitive pointer analysis, k-obj, for Java, by avoiding its redundant context elements while maintaining still a k-limiting context abstraction. – We introduce a new kind of graph, called an OAG (object allocation graph), constructed from a pre-analysis for the program, as a general mechanism to identify redundant context elements used in k-obj. – We have implemented Bean as a soon-to-be released open-source tool, which is expected to work well with various object-sensitive analyses for Java

We have applied BEAN to refine two state-of-the-art object-sensitive pointer analyses for Java.BEAN improves their precision for two representative clients on a set of nine Java programs in DaCapo at small time increases. 2 Motivation When analysing Java programs,there are two types of context,a method contert for local variables and a heap contert for object fields.In k-obj,a k-object- sensitive analysis [24,29],a method context is a sequence of k allocation sites and a heap context is typically a sequence of k-1 allocation sites.Given an allocation site at label e.e is also referred to as an abstract object for the site. Currently,k-obj,where k=2,represents a 2-object-sensitive analysis with a 1-context-sensitive heap (with respect to allocation sites),denoted 2obj+h[14], which usually achieves the best tradeoff between precision and scalability and has thus been widely adopted in pointer analysis for Java [8,21,29].In 2obj+h, a heap context for an abstract object e is a receiver object of the method that made the allocation of e(known as an allocator object).A method context for a method call is a receiver object of the method plus its allocator object. Below we examine the presence of redundant context elements in 2obj+h, with two examples,one for method contexts and one for heap contexts.This serves to motivate the BEAN approach proposed for avoiding such redundancy. 2.1 Redundant Elements in Method Contexts We use an example in Fig.1 to illustrate how 2obj+h analyses it imprecisely due to its use of a redundant context element in method contexts and how BEAN avoids the imprecision by avoiding this redundancy.We consider a may-alias client that queries for the alias relation between variables v1 and v2. In Fig.1(a),we identify the six allocation sites by their labels given in their end-of-line comments (in green),i.e.,A/1,A/2,0/1,0/2,B/1,and C/1. In Fig.1(b),we give the context-sensitive call graph computed by 2obj+h, where each method is analysed separately for each different calling context,de- noted by [...(in red).C.identify()has two concrete calling contexts but analysed only once under [B/1,C/1].We can see that B/1 is redundant (rela- tive to C/1)since adding B/1 to C/1 fails to separate the two concrete calling contexts.As a result,variables vi and v2 are made to point to both 0/1 and 0/2 at the same time,causing may-alias to report a spurious alias.During any program execution,v1 and v2 can only point to 0/1 and 0/2,respectively. In Fig.1(c),we give the context-sensitive call graph computed by BEAN, where C.identify()is now analysed separately under two different contexts, [A/1,C/1]and [A/2,C/1].Due to the improved precision,v1 (v2)now points to 0/1(0/2)only,causing may-alias to conclude that both are no longer aliases

– We have applied Bean to refine two state-of-the-art object-sensitive pointer analyses for Java. Bean improves their precision for two representative clients on a set of nine Java programs in DaCapo at small time increases. 2 Motivation When analysing Java programs, there are two types of context, a method context for local variables and a heap context for object fields. In k-obj, a k-object￾sensitive analysis [24, 29], a method context is a sequence of k allocation sites and a heap context is typically a sequence of k − 1 allocation sites. Given an allocation site at label `, ` is also referred to as an abstract object for the site. Currently, k-obj, where k = 2, represents a 2-object-sensitive analysis with a 1-context-sensitive heap (with respect to allocation sites), denoted 2obj+h [14], which usually achieves the best tradeoff between precision and scalability and has thus been widely adopted in pointer analysis for Java [8, 21, 29]. In 2obj+h, a heap context for an abstract object ` is a receiver object of the method that made the allocation of ` (known as an allocator object). A method context for a method call is a receiver object of the method plus its allocator object. Below we examine the presence of redundant context elements in 2obj+h, with two examples, one for method contexts and one for heap contexts. This serves to motivate the Bean approach proposed for avoiding such redundancy. 2.1 Redundant Elements in Method Contexts We use an example in Fig. 1 to illustrate how 2obj+h analyses it imprecisely due to its use of a redundant context element in method contexts and how Bean avoids the imprecision by avoiding this redundancy. We consider a may-alias client that queries for the alias relation between variables v1 and v2. In Fig. 1(a), we identify the six allocation sites by their labels given in their end-of-line comments (in green), i.e., A/1, A/2, O/1, O/2, B/1, and C/1. In Fig. 1(b), we give the context-sensitive call graph computed by 2obj+h, where each method is analysed separately for each different calling context, de￾noted by [...] (in red). C.identify() has two concrete calling contexts but analysed only once under [B/1,C/1]. We can see that B/1 is redundant (rela￾tive to C/1) since adding B/1 to [C/1] fails to separate the two concrete calling contexts. As a result, variables v1 and v2 are made to point to both O/1 and O/2 at the same time, causing may-alias to report a spurious alias. During any program execution, v1 and v2 can only point to O/1 and O/2, respectively. In Fig. 1(c), we give the context-sensitive call graph computed by Bean, where C.identify() is now analysed separately under two different contexts, [A/1, C/1] and [A/2, C/1]. Due to the improved precision, v1 (v2) now points to O/1 (O/2) only, causing may-alias to conclude that both are no longer aliases

1 void main(Object[]args){ 23 A al nev A()/A/1 A/1 A/1,B1] Object v1 a1.foo(nev Object());/0/1 A.foo0 B.bar( 4 B/1,C11 A a2 ney A(:/A/2 main0 A/2] 1A2,B/1 C.identity( Object v2 a2.foo(nev Object());/0/2 7) Afoo0 B.bar() 8 class A Object foo(Object v） Bb B() /B/1 (b)Context-sensitive call graph by 2obj+h return b.bar(v）; 131 14 class B AM] A/1,B/1 A/1,C/1 Object bar(Object v){ cc nev C();/C/1 A.foo() B.bar0 Cidentity0 17 return c.identity(v); 1 A/2 A2,B1] A2,C/1 191 20 class C{ A.foo() B.bar0 C.identity 21 Object identity(Object v)return v;} 22 (a)Program (c)Context-sensitive call graph by BEAN Fig.1:Method contexts for 2objth and BEAN. 2.2 Redundant Elements in Heap Contexts We now use an example in Fig.2 to illustrate how 2obj+h analyses it imprecisely due to its use of a redundant element in heap contexts and how BEAN avoids the imprecision by avoiding this redundancy.Our may-alias client now issues an alias query for variables emp1 and emp2.In Fig.2(a),we identify again its six allocation sites by their labels given at their end-of-line comments(in green). Fig.2(b)shows the context-sensitive field points-to graph computed by 2obj+h, where each node represents an abstract heap object created under the corre- sponding context,denoted [...],(in red),and each edge represents a field points- to relation with the corresponding field name being labeled on the edge.An array object is analysed with its elements collapsed to one pseudo-field,denoted arr Hence,x[i]=y (y x[i])is handled as x.arr y (y x.arr). In this example,two companies,Co/1 and Co/2,maintain their employee information by using two different ArrayLists,with each implemented internally by a distinct array of type Object [at line 22.However,2obj+h has modelled the two array objects imprecisely by using one abstract object Obj[]/1 under [AL/1].Note that AL/1 is redundant since adding it to [makes no difference to the handling of Obj[]/1.As a result,emp1 and emp2 will both point to Emp/1 and Emp/2,causing may-alias to regard both as aliases conservatively. Fig.2(c)shows the context-sensitive field points-to graph computed by BEAN. This time,the Object [arrays used by two companies Co/1 and Co/2 are dis- tinguished under two distinct heap contexts Co/1 and Co/2.As a result,our may-alias client will no longer report emp1 and emp2 to be aliases. 2.3 Discussion As illustrated above,k-obj selects blindly a sequence of k-most-recent allocation sites as a context.To analyse large-scale software scalably,k is small,which is 2

A/1 main() A.foo() A.foo() B.bar() B.bar() C.identity()
A/2 A/1, B/1 A/2, B/1 B/1, C/1 A/1 main() A.foo() A.foo() B.bar() B.bar() A/2 A/1, B/1 A/2, B/1 C.identity() A/1, C/1 C.identity() A/2, C/1 (a) (b) (c) Context-sensitive call graph by 2obj+h Program Context-sensitive call graph by BEAN 1 void main(Object[] args) { 2 A a1 = new A(); // A/1 3 Object v1 = a1.foo(new Object()); // O/1 4 5 A a2 = new A(); // A/2 6 Object v2 = a2.foo(new Object()); // O/2 7 } 8 class A { 9 Object foo(Object v) { 10 Bb= new B(); // B/1 11 return b.bar(v); 12 } 13 } 14 class B { 15 Object bar(Object v) { 16 Cc= new C(); // C/1 17 return c.identity(v); 18 } 19 } 20 class C { 21 Object identity(Object v) { return v; } 22 } Fig. 1: Method contexts for 2obj+h and Bean. 2.2 Redundant Elements in Heap Contexts We now use an example in Fig. 2 to illustrate how 2obj+h analyses it imprecisely due to its use of a redundant element in heap contexts and how Bean avoids the imprecision by avoiding this redundancy. Our may-alias client now issues an alias query for variables emp1 and emp2. In Fig. 2(a), we identify again its six allocation sites by their labels given at their end-of-line comments (in green). Fig. 2(b) shows the context-sensitive field points-to graph computed by 2obj+h, where each node represents an abstract heap object created under the corre￾sponding context, denoted [...], (in red), and each edge represents a field points￾to relation with the corresponding field name being labeled on the edge. An array object is analysed with its elements collapsed to one pseudo-field, denoted arr. Hence, x[i] = y (y = x[i]) is handled as x.arr = y (y = x.arr). In this example, two companies, Co/1 and Co/2, maintain their employee information by using two different ArrayLists, with each implemented internally by a distinct array of type Object[] at line 22. However, 2obj+h has modelled the two array objects imprecisely by using one abstract object Obj[]/1 under [AL/1]. Note that AL/1 is redundant since adding it to [ ] makes no difference to the handling of Obj[]/1. As a result, emp1 and emp2 will both point to Emp/1 and Emp/2, causing may-alias to regard both as aliases conservatively. Fig. 2(c) shows the context-sensitive field points-to graph computed by Bean. This time, the Object[] arrays used by two companies Co/1 and Co/2 are dis￾tinguished under two distinct heap contexts [Co/1] and [Co/2]. As a result, our may-alias client will no longer report emp1 and emp2 to be aliases. 2.3 Discussion As illustrated above, k-obj selects blindly a sequence of k-most-recent allocation sites as a context. To analyse large-scale software scalably, k is small, which is 2

void main(String args) any():/Co/1 ICo/1] p1.addEaployee(new Enplo e(O):∥Ep/ (Emp/1 56- obj[/1 pany(): Co/a 1Co/2 Eap/2 Emp/2 9 即1 oyee ep2 comp2.getEaployee(0) 10 class Employee (... 11C1a55C0mpan节 Context-sensitive fields points-to private rrayList emps: (b) graph by 2obj+h new ArrayList():/AL/1 15 emps.add(emp); Co/ JCon1 e) mps-get(i): 18】 Co/1 emps AL/1 elems (Emp/1 19 class ArrayList [ele ICo/21 ICo/2] List(elems nev Obiect[10]:}/Obj/1 Co/2emp elems (AL/1 (Ob0/1 arr Emp/2 23 void add(Object e){elems[size++]-e;} Object get(int i){return elens[i]; (c) Context-sensitive fields points-to (a)Program graph by BEAN Fig.2:Heap contexts for 2o6j+h and BEAN. for a method context and 1 for a heap context in 2obj+h.Therefore,redundant context elements,such as B/1 in [B/1,C/1]in Fig.1(b)and AL/1 in [AL/1]in Fig.2(b),should be avoided since they waste precious space in a context yet contribute nothing in separating the concrete calling contexts for a call site. This paper aims to address this problem in k-obj by excluding redundant elements from its contexts so that their limited context positions can be more profitably exploited to achieve better precision,as shown in Figs.1(c)and 2(c). 3 Methodology We introduce a new approach,BEAN, as illustrated in Fig.3,to improving Pownts-To the precision of a k-object-sensitive Pre-analysis OAG Set Construction pointer analysis,k-obj.The basic idea k-object-sensitive Selected Context is to refine k-obj by avoiding its re- pointer analysis (k-obj) Contexts Selection dundant context elements while main- taining still a k-limiting context ab- straction.An element e in a context Fig.3:Overview of BEAN c for a call or allocation site is redun- dant if c with e removed does not change the context represented by c.For example,B/1 in B/1,C/1]in Fig.1(b)and AL/1 in [AL/1]in Fig.2(b)are re- dundant. BEAN proceeds in two stages.In Stage 1,we aim to identify redundant con- text elements used in k-obj.To do so,we first perform usually a fast but im- precise pre-analysis,e.g.,a context-insensitive Andersen's pointer analysis on a program to obtain its points-to information.Based on the points-to information

Obj[]/1 AL/1
Co/1 Co/1 AL/1 emps elems elems Emp/1 1 void main(String[] args) { 2 Company comp1 = new Company(); // Co/1 3 comp1.addEmployee(new Employee()); // Emp/1 4 Employee emp1 = comp1.getEmployee(0); 5 6 Company comp2 = new Company(); // Co/2 7 comp2.addEmployee(new Employee()); // Emp/2 8 Employee emp2 = comp2.getEmployee(0); 9 } 10 class Employee {...} 11 class Company { 12 private ArrayList emps; 13 Company() { emps = new ArrayList(); } // AL/1 14 void addEmployee(Employee emp) { emps.add(emp); } 15 Employee getEmployee(int i) { 16 return (Employee) emps.get(i); 17 } 18 } 19 class ArrayList { 20 private Object[] elems; 21 private int size = 0; 22 ArrayList() { elems = new Object[10]; } // Obj[]/1 23 void add(Object e) { elems[size++] = e; } 24 Object get(int i) { return elems[i]; } 25 }
Co/2 Co/2 AL/1 emps Emp/2 arr arr


Co/1 Co/1 AL/1 emps
Co/2 Co/2 AL/1 emps elems Obj[]/1 elems Obj[]/1 Co/1 Co/2 arr arr Emp/1 Emp/2

(b) Context-sensitive fields points-to graph by 2obj+h (c) Context-sensitive fields points-to (a) Program graph by BEAN Fig. 2: Heap contexts for 2obj+h and Bean. for a method context and 1 for a heap context in 2obj+h. Therefore, redundant context elements, such as B/1 in [B/1,C/1] in Fig. 1(b) and AL/1 in [AL/1] in Fig. 2(b), should be avoided since they waste precious space in a context yet contribute nothing in separating the concrete calling contexts for a call site. This paper aims to address this problem in k-obj by excluding redundant elements from its contexts so that their limited context positions can be more profitably exploited to achieve better precision, as shown in Figs. 1(c) and 2(c). 3 Methodology Points-To OAG Construction Pre-analysis Context Selection Selected Set Contexts k-object-sensitive pointer analysis (k-obj) Fig. 3: Overview of Bean. We introduce a new approach, Bean, as illustrated in Fig. 3, to improving the precision of a k-object-sensitive pointer analysis, k-obj. The basic idea is to refine k-obj by avoiding its re￾dundant context elements while main￾taining still a k-limiting context ab￾straction. An element e in a context c for a call or allocation site is redun￾dant if c with e removed does not change the context represented by c. For example, B/1 in [B/1,C/1] in Fig. 1(b) and AL/1 in [AL/1] in Fig. 2(b) are re￾dundant. Bean proceeds in two stages. In Stage 1, we aim to identify redundant con￾text elements used in k-obj. To do so, we first perform usually a fast but im￾precise pre-analysis, e.g., a context-insensitive Andersen’s pointer analysis on a program to obtain its points-to information. Based on the points-to information