Manu Sridharan and Ras Bodik

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-31

March 31, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-31.pdf

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 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 35MB of memory, far less than previous approaches.

---

BibTeX citation:

@techreport{Sridharan:EECS-2006-31,
    Author= {Sridharan, Manu and Bodik, Ras},
    Title= {Refinement-Based Context-Sensitive Points-To Analysis for Java},
    Year= {2006},
    Month= {Mar},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-31.html},
    Number= {UCB/EECS-2006-31},
    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 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 35MB of memory, far less than previous approaches.},
}

EndNote citation:

%0 Report
%A Sridharan, Manu 
%A Bodik, Ras 
%T Refinement-Based Context-Sensitive Points-To Analysis for Java
%I EECS Department, University of California, Berkeley
%D 2006
%8 March 31
%@ UCB/EECS-2006-31
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-31.html
%F Sridharan:EECS-2006-31