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