Return of CFA: Call-Site Sensitivity Can Be Superior to Object Sensitivity Even for Object-Oriented ProgramsInPerson
In this paper, we challenge the commonly-accepted wisdom in static analysis that object sensitivity is superior to call-site sensitivity for object-oriented programs. In static analysis of object-oriented programs, object sensitivity has been established as the dominant flavor of context sensitivity thanks to its outstanding precision. On the other hand, call-site sensitivity has been regarded as unsuitable and its use in practice has been constantly discouraged for object-oriented programs. In this paper, however, we claim that call-site sensitivity is generally a superior context abstraction because it is practically possible to transform object sensitivity into more precise call-site sensitivity. Our key insight is that the previously known superiority of object sensitivity holds only in the traditional $k$-limited setting, where the analysis is enforced to keep the most recent $k$ context elements. However, it no longer holds in a recently-proposed, more general setting with context tunneling. With context tunneling, where the analysis is free to choose an arbitrary $k$-length subsequence of context strings, we show that call-site sensitivity can simulate object sensitivity almost completely, but not vice versa. To support the claim, we present a technique, called Obj2Cfa, for transforming arbitrary context-tunneled object sensitivity into more precise, context-tunneled call-site-sensitivity. We implemented Obj2Cfa in Doop and used it to derive a new call-site-sensitive analysis from a state-of-the-art object-sensitive pointer analysis. Experimental results confirm that the resulting call-site sensitivity outperforms object sensitivity in precision and scalability for real-world Java programs. Remarkably, our results show that even 1-call-site sensitivity can be more precise than the conventional 3-object-sensitive analysis.
Wed 19 JanDisplayed time zone: Eastern Time (US & Canada) change
13:30 - 14:45 | Program AnalysisPOPL at Salon I Chair(s): Gagandeep Singh University of Illinois at Urbana-Champaign; VMware | ||
13:30 25mResearch paper | Property-Directed Reachability as Abstract Interpretation in the Monotone TheoryRemote POPL Yotam M. Y. Feldman Tel Aviv University, Mooly Sagiv Tel Aviv University, Sharon Shoham Tel Aviv University, James R. Wilcox Certora DOI Media Attached | ||
13:55 25mResearch paper | Partial (In)Completeness in Abstract Interpretation: Limiting the Imprecision in Program AnalysisInPerson POPL Marco Campion University of Verona, Mila Dalla Preda University of Verona, Roberto Giacobazzi University of Verona DOI Media Attached | ||
14:20 25mResearch paper | Return of CFA: Call-Site Sensitivity Can Be Superior to Object Sensitivity Even for Object-Oriented ProgramsInPerson POPL DOI Media Attached |