IDEal: Efficient and Precise Alias-Aware Dataflow Analysis
Program analyses frequently track objects throughout a program, which requires reasoning about aliases. Most dataflow analysis frameworks, however, delegate the task of handling aliases to the analysis clients, which causes a number of problems. For instance, custom-made extensions for alias analysis are complex and cannot easily be reused. On the other hand, due to the complex interfaces involved, off-the-shelf alias analyses are hard to integrate precisely into clients. Lastly, for precision many clients require strong updates, and alias abstractions supporting strong updates are often relatively inefficient.
In this paper, we present IDEal, an alias-aware extension to the framework for Interprocedural Distributive Environment (IDE) problems. IDEal relieves static-analysis authors completely of the burden of handling aliases by automatically resolving alias queries on-demand, both efficiently and precisely. IDEal supports a highly precise analysis using strong updates by resorting to an on-demand, flow-sensitive, and context-sensitive all-alias analysis. Yet, it achieves previously unseen efficiency by propagating aliases individually, creating highly reusable per-pointer summaries.
We empirically evaluate IDEal by comparing TSf, a state-of-the-art typestate analysis, to TSal, an IDEal-based typestate analysis. Our experiments show that the individual propagation of aliases within IDEal enables TSal to propagate 10.4x fewer dataflow facts and analyze 10.3x fewer methods when compared to TSf. On the DaCapo benchmark suite, TSal is able to efficiently compute precise results.
Fri 27 OctDisplayed time zone: Tijuana, Baja California change
10:30 - 12:00
Static AnalysisOOPSLA at Regency C
Chair(s): Christian Hammer University of Potsdam
|IDEal: Efficient and Precise Alias-Aware Dataflow Analysis|
Johannes Späth Fraunhofer IEM, Karim Ali University of Alberta, Eric Bodden Heinz Nixdorf Institut, Paderborn University and Fraunhofer IEMDOI
|P/Taint: Unified Points-to and Taint Analysis|
Neville Grech , Yannis Smaragdakis University of AthensDOI
|Data-Driven Context-Sensitivity for Points-to Analysis|
Sehun Jeong Korea University, South Korea, Minseok Jeon Korea University, South Korea, Sungdeok (Steve) Cha Korea University, South Korea, Hakjoo Oh Korea UniversityDOI
|Automatically Generating Features for Learning Program Analysis Heuristics for C-Like Languages|
Kwonsoo Chae Korea University, Hakjoo Oh Korea University, Kihong Heo University of Pennsylvania, USA, Hongseok Yang University of OxfordDOI