Refinement-based Context-Sensitive Points-to Analysis for Java
Manu Sridharan and Ras Bodik
National Science Foundation CCF-0085949, California MICRO, Okawa Research Grant, NDSEG Fellowship and Microsoft Graduate Fellowship
We present a scalable and precise context-sensitive points-to analysis with three key properties: (1) filtering out of unrealizable paths; (2) a context-sensitive heap abstraction; and (3) a context-sensitive call graph. Previous work has shown that all three properties are important for precisely analyzing large programs, e.g., to show the safety of downcasts. Existing analyses typically give up one or more of the properties for scalability. We have developed a refinement-based analysis that succeeds by simultaneously refining handling of method calls and heap accesses, allowing the analysis to precisely analyze important code while entirely skipping irrelevant code. The analysis is demand-driven and client-driven, facilitating refinement specific to each queried variable and increasing scalability. In our experimental evaluation, our analysis proved the safety of 61% more casts than one of the most precise existing analyses across a suite of large benchmarks. The analysis checked the casts in under 13 minutes per benchmark (taking less than 1 second per query) and required only 35 MB of memory, far less than previous approaches.