Precision-Preserving Acceleration of Object-Sensitive Pointer Analysis with CFL-Reachability

Object-sensitivity is widely used as a context abstraction for computing the points-to information context-sensitively for object-oriented languages like Java. Due to the combinatorial explosion of contexts in large programs, k-object-sensitive pointer analysis (under k-limiting), k-obj, is scalable only for small values of k, where k≤2 typically. A few recent solutions attempt to improve its efficiency by instructing k-obj to analyse only some methods in the program context-sensitively, determined heuristically by a pre-analysis. While already effective, these heuristics-based pre-analyses do not provide precision guarantees, and consequently, are limited in the efficiency gains achieved. This thesis introduces a radically different approach, EAGLE, that makes k-obj run significantly faster than the prior art while maintaining its precision. The novelty of EAGLE is to enable k-obj to analyse a method with partial context-sensitivity, i.e., context-sensitively for only some of its selected variables/allocation sites. EAGLE makes these selections during a lightweight pre-analysis by reasoning about context-free-language (CFL) reachability at the level of variables/objects in the program, based on a new CFL-reachability formulation of k-obj. This thesis demonstrates the advances made by EAGLE by comparing it with the prior art in terms of a set of popular Java benchmarks and applications.