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⩽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.
Wed 23 Oct Times are displayed in time zone: Beirut change
16:00 - 16:22 Talk | Precision-Preserving Yet Fast Object-Sensitive Pointer Analysis with Partial Context Sensitivity OOPSLA DOI | ||
16:22 - 16:45 Talk | Precise Reasoning with Structured Time, Structured Heaps, and Collective Operations OOPSLA DOI | ||
16:45 - 17:07 Talk | I/O Dependent Idempotence Bugs in Intermittent Systems OOPSLA Milijana SurbatovichCarnegie Mellon University, Limin JiaCarnegie Mellon University, Brandon LuciaCarnegie Mellon University DOI | ||
17:07 - 17:30 Talk | PlanAlyzer: Assessing Threats to the Validity of Online Experiments OOPSLA Emma ToschUniversity of Massachusetts Amherst, Eytan BakshyFacebook, Inc., Emery D. BergerUniversity of Massachusetts Amherst, David JensenUniversity of Massachusetts Amherst, Eliot MossUniversity of Massachusetts Amherst DOI |