Compact Representation and Interleaved Solving for Scalable Constraint-Based Points-to Analysis

Abstract

Constraint-based points-to analysis using Andersen-style inclusion constraints is widely used for its convenience, generality, and precision in modeling complex program behaviors. Typically, such analyses generate constraints and resolve them by computing the transitive closure of a constraint graph. However, traditional constraint modeling often introduces redundancy during constraint generation, solving, or both. In the context of points-to analysis for object-oriented languages like Java, this redundancy primarily stems from the modeling of virtual calls and heap operations. As a result, the analysis produces redundant constraints and inflated constraint graphs, thereby increasing analysis time.

To address these limitations, we propose a novel constraint representation and solving system PInter, which extends the traditional inclusion constraint model. It presents a novel technique to represent the constraints in compact and expressive way. Further, it defers generation of constraints until relevant objects are discovered, enabling demand-driven and interleaved constraint generation and solving. We present a proof of correctness of PInter. We used PInter to implement two different Java points-to analyses, within the Soot framework, and evaluated it on 12 applications drawn from the DaCapo benchmark suite. As is standard, we used Tamiflex to handle dynamic features of Java benchmarks and performed a soundy evaluation. Our results show that, compared to traditional methods, PInter reduced the constraint count by 96% (geomean) and the analysis time by 78% (geomean). We also evaluated PInter against Soot’s Spark and the flow-, context- insensitive analysis in Doop, and found that PInter achieved significantly faster performance.