Efficient points-to analysis based on CFL-reachability summarisation

Abstract

Points-to analysis plays a critical role in modern compilers and a wide range of program understanding and bug detection tools. Nevertheless, developing precise and scalable points-to analysis for large-scale object-oriented software remains a challenge, especially in the presence of different client requirements and frequent software modifications. In this thesis, we present two new techniques for achieving more efficient points-to analysis based on Context-Free Language (CFL)-reachability. In general, our techniques significantly improve the state-of-the-art points-to analysis for Java applications when handling demand-driven queries and small code changes. This thesis firstly presents an on-demand dynamic summary-based points-to analysis for Java, which provides a more scalable solution without affecting precision. Our second technique is an incremental summarisation framework designed for IDEs, which can efficiently handle frequent program edits, addressing a long-standing challenge in points-to analysis. For each technique, we describe the algorithms and evaluate the implementations with a set of Java applications and clients.