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 OctDisplayed time zone: Beirut change
16:00 - 17:30 | |||
16:00 22mTalk | Precision-Preserving Yet Fast Object-Sensitive Pointer Analysis with Partial Context Sensitivity OOPSLA DOI | ||
16:22 22mTalk | Precise Reasoning with Structured Time, Structured Heaps, and Collective Operations OOPSLA DOI | ||
16:45 22mTalk | I/O Dependent Idempotence Bugs in Intermittent Systems OOPSLA Milijana Surbatovich Carnegie Mellon University, Limin Jia Carnegie Mellon University, Brandon Lucia Carnegie Mellon University DOI | ||
17:07 22mTalk | PlanAlyzer: Assessing Threats to the Validity of Online Experiments OOPSLA Emma Tosch University of Massachusetts Amherst, Eytan Bakshy Facebook, Inc., Emery D. Berger University of Massachusetts Amherst, David Jensen University of Massachusetts Amherst, Eliot Moss University of Massachusetts Amherst DOI |