Making Slicing Practical:
The Final Mile
William Griswold
University of California, San Diego
in collaboration with Leeann Bent (UCSD) &
Darren Atkinson (Santa Clara University)
special thanks to GrammaTech Inc.
PASTE 2001
The Conundrum
• Program slicing has been an archetype of SE
analysis for 20 years [Weiser 80]
– reveal hidden or dispersed program relationships
– assist in reasoning about and changing them
• Yet program slicers are not widely used
• Why not?
– Then: implementations were too slow and imprecise
– Now: inadequate attention to essential SE needs
Static Backward Program Slice
Set of expressions and statements that may
affect the value of a chosen variable reference
during execution. [Weiser 81]
void setg(int a1, int a2) {
int x = 1;
g = a1;
if (pred(a2)) {
initial slicing
g = x;
printf(“%d”, g);
Benefits & Applications of Slicing
Key value is its subsetting property: helps a
programmer focus on the parts of the system
relevant to current task
– Debugging: What subset of statements might have
helped produce the wrong value for g?
– Evolution: What components are inputs to the one
I’m evolving? Does this change break that feature?
– Testing: I changed this statement, what subset of
the tests do I need to rerun?
Underlying dependences are also of potential value
Freddie Krueger, Tool User
“Your tool can solve all sorts of problems for us.
But it’ll have to analyze our entire 1 MLOC
program, which is written in 4 languages and
doesn’t compile right now. I want the results as
fast as compilation, with an intuitive graphical
display linked to the source and integrated into
our IDE. I want to save the results, and have
them automatically updated as I change the
Our most recent
program. By the way, I use Windows,
but some
study involved a 500
of my colleagues use Unix. It’s OK
if the
tool app
misses stuff or returns lots of data,
as longonas
can post-process. We just need a net win.”
• Fast, scalable
• Slow, doesn’t scale
• Easy to use
• Easy to use
• Flexible (caps, words…)
• Forward, backward, chop
• Language independent
• C; Java coming
• Integrated in every env.
• Stand-alone
• Imprecise
• Precise, but slices large
– Allows iteration & filtering
• Used in many activities
– Allows iteration & filtering
• Several postulated uses
– Renaming, restructuring,
finding change points…
Our Experience on the Final Mile
• Several years designing Sprite, a fast, scalable
program slicer for C
• Comparative study [2000] with GrammaTech’s
CodeSurfer slicer for C, a commercial product
• Other tools: design, implementation, and
user studies
Sprite 1.2.2
Slicing Criterion
CodeSurfer 1.1p1
Why We’re Still on the Final Mile
Little understanding of programmers’ needs,
tasks, or how they would use a slicer
Slicers suffer from inflexibility & poor usability
User interfaces are in formative stages
Several opportunities insufficiently explored
Usability and Flexibility
Part 1
• Wrote few dozen “feature benchmarks”
– Unstructured c-flow, context sensitivity, pointers...
– Expose intervening, interacting algorithmic factors
• 5 small production-quality programs
– compress, wally, ispell, ed, diff
• A few larger programs using Sprite
– gcc, emacs, FEM app
• Varied slicer options, studied results
Uninitialized Pointers
int *p; // uninitialized
*p = x;
y = *p;
• Neither tool included x in the slice
• No warning
• Misleading (say, if you’re debugging)
Undefined Functions
x = f(&y,z);
• Sprite: included call, but did not propagate
• CodeSurfer: also propagated to &y and z
– No propagation to z if slicing on y
• Both printed warning to terminal (not GUI)
– Easy to not notice
– Easy to forget a library or have undefined function
Library Modeling
• Both modeled effects of libraries with skeletal
int write(int fd, char *s) {
return (*filesystem[fd]++ = *s);
• Only libc and libm, both incomplete
– Only a few undefined functions for our programs
– CodeSurfer’s noticeably better, more complex
• Missing could impact precision, effort, or perf.
– What if need Xlib???
Slicing into Callers
setg(a, b);
void setg(int a1, int a2) {
int x = 1;
• Sprite: could not slice into callers
• CodeSurfer: must slice into callers
Neither customizable to produce other’s results
(CodeSurfer did support single-step slicing and slicing on
just control- or data-dependences)
Control Dependence Sensitivity
= {&f1,
• “Spurious” dependence
slice &f2,
by x10
– Indirection
array of function
• Sprite’s “strongly typed function calls” feature fixed
gcc problems, not emacs
– Modelling of control dependences (CodeSurfer)
switch (ch) {
case ‘a’:
if (pred(e))
g = x + 1;
case ‘b’:
g = x + 2;
Statement Inclusion & Highlighting
• Sprite: no global decls, uninitialized locals,
control flow keywords
– Included goto’s only if option enabled
• CodeSurfer: “executable slice” highlighting
– Includes syntactic sugar
Right choice depends on user’s task
– Omitting a statement could lead to oversight
– Overwhelming with highlighting can, too
Understanding Slicing Results
• Hard: “Why is this statement in the slice?”
– Forgotten or incomplete libraries
– “Style” of slice (into callers, declarations)
– Real dependence or algorithmic artifact?
– Control, data, pointer, ...
– Gap betw. highlighting & underlying dependences
• Querying dependence edges, points-to sets unhelpful
• Answer critical to correct software change
• We modified: comment out pointer assignment
– Must rebuild, reslice, and compare results by hand
Summary - The Bad News
• Tools had “hidden” behaviors on erroneous or
incomplete programs
– Could mislead programmer, hampering use
• Tools had rigid notion of a slice
– Each suited for some tasks, but not others
• Tools required significant effort to use
– Completeness of libraries
– Understanding reasons for inclusion in slice
Implementations of algorithms, not full tools
Summary - The Good News
• Both tools supported (potentially) inaccurate
analyses to remove uninteresting information
– Sprite: user customization of pointer properties
– CodeSurfer: I/O functions that aren’t interdependent
– Suggests generalizing slicing as an SE analysis
– Unfortunately, manipulating analysis can be costly
• Variance between tools exposes tool options
– Suggests user-customizable features
– E.g., highlighting options: decls versus no-decls
The Human–Computer Interface
Part 2
• Good user interfaces are crucial to effectiveness
– Leverage & aid programmer’s cognitive processes
– A key difference between an algorithm and a tool
• Example for evolution (what I understand)
– Tremendous scale
– Wide dispersal of information: redundancy, many
references to an element
– Requirement for complete and consistent change
of the dispersed elements (e.g., rename)
– Invisibility of far-away information stresses recall
Example - grep & Company
• Easy to use and fast
– Takes a textual pattern and target for search
grep ”cursor” *.java
– Lists all matching lines and highlights in editor
– Next/Previous operations traverse the matches
• Scalability issues: limited visibility, inflexible
– Can see just a few matches in context of use
– One search at a time; cannot compare results
File strips
Maps Enhance Visibility
• Highly evolved artifact for coping with scale
Lines matched
by pattern
– Spatial
indices, folding, itineraries
cursors, insets,
• Idea: augment grep with Seesoft-like view
Lines with
or more
– Colored
symbols for matched lines in files
– Puts matches on an equal footing with modules
• See only portion of program, little of value
• Use map metaphor fully: Aspect Browser
“You are here”
Now extending with
Atlas metaphor to
accommodate vast
“Folding” cue
Views updatedthat files are
on save
CodeSurfer GUI
is half-way there
Traversal operations
One-file “Seesoft”
Cue of underlying hits
Part 3: Opportunities
• Slice explainer
– High-level analysis of why statement is in slice
• May/Must highlighting
– Overlay slice with highlighting dynamic slices or
execution coverage
– Uncovered stmts, dependences hint at imprecision
• Filtering w/ other analyses and customizations
– CodeSurfer has chopping; Sprite set operations
– grep, Ajax tools [O’Callahan]
– PIM-like customizations [Field]
• With small run-time impact
Emerging Challenges
• Multi-threading [Hatcliff et al.], exceptions
– intrinsically flow-sensitive, so flow-insensitive
pointer analysis is substantial loss [Rugina]
• What is a program? What is the program?
– Federated client-server apps
• Often multi-language
– Trend is to write component glue
• Less source code, but huge apps
• How treat vast, numerous packages? Sans source?
– Analysis via Java library byte codes costly [O’Callahan]
– Vast amount of stub code to write for libraries
Long-Standing Issues
• Robustness - incomplete or buggy programs
– Useful for developing and evolving systems
– Complicates the analysis
– Harder for programmer to interpret results
• Integration into IDE’s [Hayes 2000]
– Work with IDE’s GUI and AST, or else bloat
– Reuse analyses across IDE’s
• In principle not hard
• In practice, performance/precision tradeoffs can
require big rewrites for “small” language change
Recommendations & Future Work
• Explore non-algorithmic aspects of precision
• Attend to users’ tasks and habits
– Giving users what they need is “precision”
• Do an observational study of programmers
– Essential problems: complex tasks of programmers
– Accidental problems: kludgy user interfaces…
• Listen to Michael’s talk tomorrow ;)
• 20 years of slicing research
– Huge strides in algorithmic precision & performance
– Little adoption
• “Non-algorithmic” factors like libraries have
significant impact on precision
– Cannot ignore, now that libs dominate applications
• Remaining problem is usefulness of slicers
– Confusing behaviors, inflexibility, and need for
costly “programming” are barriers to adoption
– Understanding programmer’s use of dependences

Making Slicing Practical: The Final Mile