Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Refinement-Based Program Analysis Tools

Manu Sridharan

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2007-125
October 23, 2007

http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-125.pdf

Program analysis tools are starting to change how software is developed. Verifiers can now eliminate certain complex bugs in large code bases, and automatic refactoring tools can greatly simplify code cleanup. Nevertheless, writing robust large-scale software remains a challenge, as greater use of component frameworks complicates debugging and program understanding. Developers need more powerful programming tools to combat this complexity and produce reliable code. This dissertation presents two techniques for more powerful debugging and program understanding tools based on refinement. In general, refinement-based techniques aim to discover interesting properties of a large program by only reasoning about the most important parts of the program (typically a small amount of code) precisely, abstracting away the behavior of much of the program. Our key contribution is the first framework for effective refinement-based handling of object-oriented data structures; pervasive use of such data structures thwarts the effectiveness of most existing analyses and tools. Our two refinement-based techniques significantly advance the state-of-the-art in program analyses and tools for object-oriented languages. The first technique is a refinement-based points-to analysis that can compute precise answers in interactive time. This analysis enables precise reasoning about data structure behavior in clients that require interactive performance, e.g., just-in-time compilers and interactive development environment (IDE) tools. Our second technique is thin slicing, which gives usable answers to code relevance questions---e.g., "What code might have caused this crash?"---addressing a long-standing challenge for analysis tools. In this dissertation, we describe the design and implementation of these techniques and present experimental evaluations that validate their key properties.

Advisor: Ras Bodik


BibTeX citation:

@phdthesis{Sridharan:EECS-2007-125,
    Author = {Sridharan, Manu},
    Title = {Refinement-Based Program Analysis Tools},
    School = {EECS Department, University of California, Berkeley},
    Year = {2007},
    Month = {Oct},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-125.html},
    Number = {UCB/EECS-2007-125},
    Abstract = {Program analysis tools are starting to change how software is developed.  Verifiers can now eliminate certain complex bugs in large code bases, and automatic refactoring tools can greatly simplify code cleanup.  Nevertheless, writing robust large-scale software remains a challenge, as greater use of component frameworks complicates debugging and program understanding.  Developers need more powerful programming tools to combat this complexity and produce reliable code.

This dissertation presents two techniques for more powerful debugging and program understanding tools based on refinement.  In general, refinement-based techniques aim to discover interesting properties of a large program by only reasoning about the most important parts of the program (typically a small amount of code) precisely, abstracting away the behavior of much of the program.  Our key contribution is the first framework for effective refinement-based handling of object-oriented data structures; pervasive use of such data structures thwarts the effectiveness of most existing analyses and tools.

Our two refinement-based techniques significantly advance the state-of-the-art in program analyses and tools for object-oriented languages.  The first technique is a refinement-based points-to analysis that can compute precise answers in interactive time.  This analysis enables precise reasoning about data structure behavior in clients that require interactive performance, e.g., just-in-time compilers and interactive development environment (IDE) tools.  Our second technique is thin slicing, which gives usable answers to code relevance questions---e.g., "What code might have caused this crash?"---addressing a long-standing challenge for analysis tools.  In
this dissertation, we describe the design and implementation of these techniques and present experimental evaluations that validate their key properties.}
}

EndNote citation:

%0 Thesis
%A Sridharan, Manu
%T Refinement-Based Program Analysis Tools
%I EECS Department, University of California, Berkeley
%D 2007
%8 October 23
%@ UCB/EECS-2007-125
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-125.html
%F Sridharan:EECS-2007-125