Strong Update for Object-Oriented Flow-Sensitive Points-To Analysis

Abstract

Points-to analysis is a static analysis that approximates which memory locations each program expression may refer to. Many client analyses use points-to information to optimize compilers or reason about program security. The effectiveness of the client analyses relies on the precision of the points-to analysis. Flow-sensitive points-to analyses compute points-to information per program point, providing additional precision over flow-insensitive points-to analyses.

We present a points-to analysis for object-oriented programs that is specifically designed to enable strong update, which is particularly useful in object-oriented languages as it can enable precise reasoning about object invariants established during object construction. We enable strong update by using the recency abstraction: each allocation site is represented by two abstract objects, the most-recently-allocated object and any non-most-recently allocated objects. By definition, the fields of a most-recently-allocated abstract object correspond to a single concrete memory location and can thus be strongly updated.

Our analysis is implemented for Java bytecode. It is scalable (130k lines of code can be analyzed in 92 seconds), and significantly improves the precision of some client analyses, including non-null analysis, interval analysis and cast-removal analysis, compared to of a flow-insensitive analysis.