Manu Sridharan

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-125

October 23, 2007

http://www2.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.

Advisors: 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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-125.html
%F Sridharan:EECS-2007-125