Thu 8 Nov 2018 13:52 - 14:15 at Studio 2 - Static Analysis Chair(s): Karim Ali

We present context tunneling, a new approach for performing precise and scalable context-sensitive points-to analysis. As context-sensitivity holds the key to the development of precise and scalable points-to analysis, a variety of techniques for context-sensitivity have been proposed. However, most existing approaches have a significant weakness that they blindly update the context of a method at every call-site, allowing important context elements to be overwritten by more recent, but not necessarily more important, ones. In this paper, we show that this is a key limiting factor in existing techniques, and demonstrate that remarkable increase in both precision and scalability can be gained by carefully maintaining important context elements only.

We attain context tunneling via a data-driven approach. The effectiveness of context tunneling is very sensitive to the choice of important context elements. Even worse, precision is not monotonically increasing with respect to the ordering of the choices. As a result, manually coming up with a good heuristic rule for context tunneling is extremely challenging and likely fails to maximize its potential. We address this challenge by developing a specialized data-driven algorithm, which is able to automatically search for high-quality heuristics over the non-monotonic space of context tunneling.

We implemented our approach in the Doop framework and applied it to four major flavors of context sensitivity: call-site-sensitivity, object-sensitivity, type-sensitivity, and hybrid context-sensitivity. In all cases, $1$-context-sensitive analysis with context tunneling far outperformed deeper context-sensitivity with $k=2$ in both precision and scalability.

Thu 8 Nov
Times are displayed in time zone: Guadalajara, Mexico City, Monterrey change

13:30 - 15:00: Static AnalysisOOPSLA at Studio 2
Chair(s): Karim AliUniversity of Alberta
13:30 - 13:52
Incrementalizing Lattice-Based Program Analyses in Datalog
Tamás Szabóitemis / TU Delft, Gábor BergmannBudapest University of Technology and Economics / MTA-BME Lendület Research Group on Cyber-Physical Systems, Hungary, Sebastian ErdwegTU Delft, Markus Völterindependent / itemis, Germany
13:52 - 14:15
Precise and Scalable Points-to Analysis via Data-Driven Context Tunneling
Minseok JeonKorea University, South Korea, Sehun JeongKorea University, Hakjoo OhKorea University
14:15 - 14:37
Precision-Guided Context Sensitivity for Pointer Analysis
Yue LiAarhus University, Denmark, Tian TanAarhus University, Denmark, Anders MøllerAarhus University, Yannis SmaragdakisUniversity of Athens
14:37 - 15:00
Refinement in object-sensitivity points-to analysis via slicing
Girish Maskeri RamaInfosys Limited, Raghavan KomondoorIndian Institute of Science, Bangalore, Himanshu SharmaIndian Institute of Science, Bangalore