Slicing, Dicing and Chopping: Little-Known Advanced Tools for Programmers

April 29, 2009

Slicing, Dicing, Chopping and other Mysteries

Most programmers have never heard of slicing, dicing or chopping applied to computer programs. They are simple ideas, and most advanced programmers have probably at least used slicing without knowing it. Unfortunately, the more powerful applications seemingly never made it out of academia.

In 1981 Mark Weiser published “Program Slicing.” Weiser was a phenomenal researcher—he was a chief scientist at the renowned Xerox Palo Alto Research Center and he is the academic father of ubiquitous computing. It’s a shame his other accomplishments overshadow this one.

Slicing is simple. Given a program behaviour, we can construct a new, smaller, simpler program that has the same behaviour: We just delete the irrelevant parts of the program that didn’t contribute. Given a bug, slicing removes the code that could never have contributed to the problem.

Most programmers do this mentally to some extent, and occasionally some will actually delete code during debugging. A few tools to do automatic slicing exist, but they’re rarely used.

Slicing: Show only code that contributed to bad behaviour.

Dicing extends the concept. If we have examples of code that runs correctly, under certain conditions we can assume that the code that contributes to the correct behaviour is correct. So we remove it, too. That leaves a much smaller program to examine.

Dicing: Show only code that contributed to bad behaviour and didn’t contribute to good behaviour.

Chopping is another related idea. If we insert some new code, and it reveals an incorrect behaviour later in the program, chopping shows us the code between the new code and bad behaviour that was affected by the inserted code.

Chopping: Show only code that contributes to bad behaviour and was affected by some given piece of code.

Static slicing does not use the values of program inputs.

Dynamic slicing works with specific values of program inputs.

Conditioned slicing works assuming a given logical condition.

Amorphous slicing works using semantics-preserving source transformations other than code deletion. All of the other techniques above only use deletion to simplify a program. Amorphous slicing permits more powerful techniques.

Harman and Herions have a good review of slicing literature as of 2001.

Tools

What would it take to use a dicing tool?

To find a bug, you gather a trace of all the code executed until the observable bug behaviour. That’s your slice.

Your slice could be large. Now you want to dice it, that is, eliminate known-good code. If only you had a large number of known-good executions of your program! You could use them to hone in on bugs, fast.

In the heyday of slicing research, the eighties and early nineties, it might have been hard to find a large library of known-good executions. These days, it would be easy. Automatic test suites are cool now. Everybody’s got one.

In fact, this is exactly the insight that Hsin Pan had at Purdue University. Pan invented a set of heuristics to combine test data with dicing. In fact, Pan wrote a PhD thesis on the subject and even built a whole debugging infrastructure called Spyder. Here’s a technical report and the dissertation.

Had you heard of Spyder before today?

Me neither.

Directions

In the first Empirical Studies of Programmers workshop, Bill Curtis published “By the way, did anyone study any real programmers?”, decrying the glut of empirical research on novices and lack thereof on professionals.

I propose a modern variant: By the way, did anyone study any real programs?

We have at our disposal the source code and version history of thousands of software projects. Some of them also track bugs thoroughly and link these bugs to test cases. Using such a project, it should be possible to retroactively test a dicing tool.

We have a version of a project that contains a bug. We eventually have a test case which exposes the bug. We use these with a dicing tool to produce suspect lines of code. To derive a perfectly quantitative measure of dicing tool quality, we compare these suspect lines of code with the code affected by the eventual patch for the bug.

I see another direction for dicing research: To my knowledge, no popular IDE supports dicing. We ought to be able to devise a good user interface for dicing. We wouldn’t even need to build a dicing-tool: We could make paper prototypes. I’d like to explore a dicing interface that highlights suspect code the same way Shark Code Browser highlights slow code in yellow.

Debugging and maintenance is a major part of software development. One might assume that as an industry so concerned with efficiency we would use every tool available to us. It’s clear though that opportunities abound for some innovation.

Advertisements

5 Responses to “Slicing, Dicing and Chopping: Little-Known Advanced Tools for Programmers”

  1. zak Says:

    GrammaTech (where I’ve done a couple of internships) has a tool that does static slicing and chopping (among other things). It’s neat.

    http://www.grammatech.com/products/codesurfer/

    Dynamic slicing/dicing/chopping is new to me, though. I think building a dynamic dicer would be feasible in a few months (assuming all it takes is combining standard profiling info. You could probably even use gprof or similar). Static slicing is… much harder.

    Anyway, this is interesting. My favorite of your thesis ideas.


  2. […] Would Dicing Help? A lot of ground has been covered but I think there’s room for more. [Blog post] […]

  3. Greg Wilson Says:

    Zeller’s book [1] talks a lot about using slicing for debugging (and about tool support); second edition is in the works, and he’ll be at ICSE.

    [1] http://www.amazon.com/Why-Programs-Fail-Systematic-Debugging/dp/1558608664 (I have it on my shelf)

  4. Soubhagya Says:

    Hello everybody,
    I am Soubhagya. I am doing research on program slicing. Can anybody help me please doing the simulation?


  5. “Empirical Evaluation of the Tarantula Automatic Fault-Localization Technique” by Jones and Harrold

    http://pleuma.cc.gatech.edu/aristotle/Publications/Papers/ase05.pdf


Comments are closed.

%d bloggers like this: