Efficient and Precise Pointer Analysis with Fine-Grained Context Sensitivity

Abstract

Pointer analysis addresses a fundamental problem in program analysis: determining statically whether or not a given pointer may reference an object in the program. It underpins almost all forms of other static analysis, including program understanding, program verification, bug detection, security analysis, compiler optimization, and symbolic execution. However, existing pointer analysis techniques suffer from efficiency and scalability issues for large programs. Improving their efficiency while still maintaining their precision is a long-standing hard problem. This thesis aims to improve the efficiency and scalability of pointer analysis for object-oriented programming languages such as Java by exploring fine-grained context sensitivity. Unlike traditional approaches, which apply context-sensitivity either uniformly to all methods or selectively to a subset of methods in a program, we go one step further by applying context-sensitivity only to a subset of precision-critical variables and objects so that we can reduce significantly the scale of Pointer Assignment Graph (PAG). Conducting pointer analysis on a smaller PAG enables the pointer analysis to run significantly faster while preserving most of its precision. This thesis makes its contributions by introducing three different fine-grained pointer analysis approaches for Java programs. The first approach, called TURNER, can accelerate k-object-sensitive pointer analysis (i.e., kOBJ) for Java significantly with negligible precision loss by exploiting object containment and reachability. The second approach, called context debloating, can accelerate all existing object-sensitive pointer analysis algorithms for Java by eliminating the context explosion problem completely for context-independent objects. In addition, we have also developed the first supporting tool, named CONCH, for identifying context-independent objects. The last approach, called P3CTX, represents the first precision-preserving technique for accelerating k-callsite-sensitive pointer analysis (kCFA) for Java based on a complete CFL-reachability formulation of kCFA for Java with built-in on-the-fly call graph construction (for the first time).