Fault Localization Using Value Replacement

Jeffrey, Gupta, Gupta

fault localization debugging software engineering

@conference{jeffrey:ssta-2008,
  title={Fault Localization Using Value Replacement},
  author={Jeffrey, D. and Gupta, N. and Gupta, R.},
  booktitle={International Symposium on Software Testing and Analysis},
  pages={167--178},
  year={2008},
  organization={{ACM}}
}

Debugging is necessary since software development is so human intensive

• Looking to automate the debugging process

Tarantula: Previous statistical work

• Statements primarily executed by failing runs are more likely to have problems than statements primarily run by successful runs

This work looks for statements that can be shown to be modifiable to make the result correct

Statements map from used values (variables) and defined values (outcomes)

An Interesting Value Mapping Pair (IVMP) is a pair of such value maps, such that replacing the alternate with the original then the incorrect output of the run becomes correct

• Alternate values are taken from Value Profile, constructed from all values seen in all test runs, rather than near infinite selection
• Can also be done if output is not known but can be determined as being improved; e.g., if the system crashes, but swapping values makes it not crash, that is an improvement

Seems like many of the results could be very hard to decipher, particularly for indirect IVMPs such as for constant assignemnts

Complexity runs in time proportional to number of failing runs, number of statements, and elements in value profile

• Mostly dominated by length of execution run (number of statements)
• Value profile cut down by applying heuristics, reducing to constant number of span representatives
• Doesn't need large number of runs for good results

Bug could be elsewhere than the IVMP, so they have to be ranked

• Dependence cause
• Compensation cause

Rank statements according to notion that statements associated with IVMPs in more failing runs are more likely to be faulty

Cut cut down on number of alternates via simple heuristics

• Using min, max, average, etc

Demonstration run within valgrind infrastructure

Experimental process seems reasonable, particularly in that they accounted somewhat for potential biasing in the test case construction

• But results don't really present statistical significance, i.e., of outperforming Tarantula

Still talking about tens and hundreds of thousands of re-executions

Doesn't work very well on floating point values...

• Too difficult to make output come out correct

Should be combined with program slicing to only consider those aspects

• But this requires correlating particular elements of the output to a slice

Can speed up executions, checkpointing and skipping large sequences

Multiple faults diminishes the value of the approach!

Doesn't really help with memory related faults, as you can't just swap in random pointer values