Refinement-based context-sensitive points-to analysis for Java
Citations Over TimeTop 1% of 2006 papers
Abstract
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 [21] has shown that all three properties are important for precisely analyzing large programs, e.g., to show 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 demanddriven 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 35MB of memory, far less than previous approaches.
Related Papers
- → Bug Finder Evaluation Guided Program Analysis Improvement(2019)3 cited
- → Static Control Flow Analysis of Binary Codes(2010)2 cited
- → Wok: Statistical Program Slicing in Production(2019)2 cited
- Method for Static Function Call Analysis with Control Flow(2011)
- Pointer analysis for java programs: novel techniques and applications(2006)