Precision-Preserving Yet Fast Object-Sensitive Pointer Analysis with Partial Context Sensitivity
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), denoted $k$-obj, is scalable only for small values of $k$, where $k \leqslant 2$ typically. A few recent solutions attempt to improve its efficiency by instructing $k$-obj to analyze 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. We introduce 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 analyze 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. We demonstrate the advances made by Eagle by comparing it with the prior art in terms of a set of popular Java benchmarks and applications.
This program is tentative and subject to change.
Wed 23 Oct
|16:00 - 16:22|
|16:22 - 16:45|
|16:45 - 17:07|
|17:07 - 17:30|