Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Thin Slicing

Manu Sridharan, Stephen J. Fink and Ras Bodik

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-184
December 18, 2006

http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-184.pdf

Program slicing provides a systematic technique to identify parts of a program relevant to a particular seed. Unfortunately, slices of modern programs often grow too large for human consumption in program understanding or browsing tools. We argue that unwieldy slices arise primarily from an overly broad definition of relevance, rather than from analysis imprecision. While a traditional slice includes all statements that may affect a value of interest, not all such statements appear equally relevant to a human. As an improved method of finding statements relevant to a human, we propose thin slicing, a technique based on value-flow relevance. A thin slice consists of statements that may ``copy-propagate'' a value to the seed, and excludes statements that may indirectly affect value flow. For example, for a seed that reads a value from a container object, a thin slice includes statements that store a value into the container, but excludes statements that manipulate pointers to the container itself. We also show how a tool can support incremental thin slice expansion to explain aliasing and control dependence, yielding a traditional slice in the limit. Experimental results show that thin slices usually include the most relevant statements for a set of debugging and program understanding tasks. Furthermore, using breadth-first inspection to simulate realistic use of a slicing tool, thin slices reveal interesting target statements after inspecting up to 4.52X fewer statements than traditional slicing for debugging tasks, and up to 34.2X fewer for program understanding tasks. Finally, experimental results show that an effective thin slicing algorithm scales well to relatively large Java benchmarks, suggesting that thin slicing represents an attractive option for practical tools.


BibTeX citation:

@techreport{Sridharan:EECS-2006-184,
    Author = {Sridharan, Manu and Fink, Stephen J. and Bodik, Ras},
    Title = {Thin Slicing},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-184.html},
    Number = {UCB/EECS-2006-184},
    Abstract = {Program slicing provides a systematic technique to identify parts of a program relevant to a particular seed.  Unfortunately, slices of modern programs often grow too large for human consumption in program understanding or browsing tools. We argue that unwieldy slices arise primarily from an overly broad definition of relevance, rather than from analysis imprecision.  While a traditional slice includes all statements that may affect a value of interest, not all such statements appear equally relevant to a human.  

As an improved method of finding statements relevant to a human, we propose thin slicing, a technique based on value-flow relevance. A thin slice consists of statements that may ``copy-propagate'' a value to the seed, and excludes statements that may indirectly affect value flow.  For example, for a seed that reads a value from a container object, a thin slice includes statements that store a value into the container, but excludes statements that manipulate pointers to the container itself. We also show how a tool can support incremental thin slice expansion to explain aliasing and control dependence, yielding a traditional slice in the limit.

Experimental results show that thin slices usually include the most relevant statements for a set of debugging and program understanding tasks.  Furthermore, using breadth-first inspection to simulate realistic use of a slicing tool, thin slices reveal interesting target statements after inspecting up to 4.52X fewer statements than traditional slicing for debugging tasks, and up to 34.2X fewer for program understanding tasks.  Finally, experimental results show that an effective thin slicing algorithm scales well to relatively large Java benchmarks, suggesting that thin slicing represents an attractive option for practical tools.}
}

EndNote citation:

%0 Report
%A Sridharan, Manu
%A Fink, Stephen J.
%A Bodik, Ras
%T Thin Slicing
%I EECS Department, University of California, Berkeley
%D 2006
%8 December 18
%@ UCB/EECS-2006-184
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-184.html
%F Sridharan:EECS-2006-184