Precision-Guided Context Sensitivity for Pointer Analysis

TY - JOUR

T1 - Precision-Guided Context Sensitivity for Pointer Analysis

AU - Li, Yue

AU - Tan, Tian

AU - Møller, Anders

AU - Smaragdakis, Yannis

N1 - Conference code: 2018

PY - 2018/10/24

Y1 - 2018/10/24

N2 - Context sensitivity is an essential technique for ensuring high precision in Java pointer analyses. It has been observed that applying context sensitivity partially, only on a select subset of the methods, can improve the balance between analysis precision and speed. However, existing techniques are based on heuristics that do not provide much insight into what characterizes this method subset. In this work, we present a more principled approach for identifying precision-critical methods, based on general patterns of value flows that explain where most of the imprecision arises in context-insensitive pointer analysis. Accordingly, we provide an efficient algorithm to recognize these flow patterns in a given program and exploit them to yield good tradeoffs between analysis precision and speed. Our experimental results on standard benchmark and real-world programs show that a pointer analysis that applies context sensitivity partially, only on the identified precision-critical methods, preserves effectively all (98.8%) of the precision of a highly-precise conventional context-sensitive pointer analysis (2-object-sensitive with a context-sensitive heap), with a substantial speedup (on average 3.4X, and up to 9.2X).

AB - Context sensitivity is an essential technique for ensuring high precision in Java pointer analyses. It has been observed that applying context sensitivity partially, only on a select subset of the methods, can improve the balance between analysis precision and speed. However, existing techniques are based on heuristics that do not provide much insight into what characterizes this method subset. In this work, we present a more principled approach for identifying precision-critical methods, based on general patterns of value flows that explain where most of the imprecision arises in context-insensitive pointer analysis. Accordingly, we provide an efficient algorithm to recognize these flow patterns in a given program and exploit them to yield good tradeoffs between analysis precision and speed. Our experimental results on standard benchmark and real-world programs show that a pointer analysis that applies context sensitivity partially, only on the identified precision-critical methods, preserves effectively all (98.8%) of the precision of a highly-precise conventional context-sensitive pointer analysis (2-object-sensitive with a context-sensitive heap), with a substantial speedup (on average 3.4X, and up to 9.2X).

KW - Java

KW - Points-to analysis

KW - Static analysis

UR - http://www.scopus.com/inward/record.url?scp=85094324650&partnerID=8YFLogxK

U2 - 10.1145/3276511

DO - 10.1145/3276511

M3 - Journal article

SN - 2475-1421

VL - 2

SP - 141:1-141:29

JO - Proceedings of the ACM on Programming Languages

JF - Proceedings of the ACM on Programming Languages

IS - OOPSLA

M1 - 141

T2 - The ACM SIGPLAN conference on Systems, Programming, Languages and Applications: Software for Humanity

Y2 - 4 November 2018 through 9 November 2018

ER -