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.
Conference DayFri 27 OctDisplayed time zone: Tijuana, Baja California change
10:30 - 12:00
|IDEal: Efficient and Precise Alias-Aware Dataflow Analysis|
Johannes SpäthFraunhofer IEM, Karim AliUniversity of Alberta, Eric BoddenHeinz Nixdorf Institut, Paderborn University and Fraunhofer IEMDOI
|P/Taint: Unified Points-to and Taint Analysis|
|Data-Driven Context-Sensitivity for Points-to Analysis|
Sehun JeongKorea University, South Korea, Minseok JeonKorea University, South Korea, Sungdeok (Steve) ChaKorea University, South Korea, Hakjoo OhKorea UniversityDOI
|Automatically Generating Features for Learning Program Analysis Heuristics for C-Like Languages|
Kwonsoo ChaeKorea University, Hakjoo OhKorea University, Kihong HeoUniversity of Pennsylvania, USA, Hongseok YangUniversity of OxfordDOI