A family of code coverage-based heuristics for effective fault localization

Fault localization (which aims to reveal locations of faults in software in automatic or semi-automatic ways) has received considerable attention from academia and industry for the last two decades. Our paper, which was published in the prestigious Journal of Systems of Software right at the beginning of the last decade, focuses on spectrum-based fault localization, i.e., leveraging the useful data provided by test case execution and code coverage to narrow down the search domain when looking for faults in software. More specifically, we compare and contrast the code-coverage information (which portion of the code is covered and which is not) provided by successful and failed test cases to rank the portions of code (at the statement level) in terms of their likelihood (or suspiciousness) of containing faults. The general idea is that programmers can examine the code from most suspicious to least when locating faults, thereby providing order and direction to what would otherwise be an extremely large search domain.

In a period when many such papers were exploring the possibilities of applying different techniques (such as similarity coefficients, machine learning, etc.) to provide better rankings, and then demonstrating that the technique proposed was more effective than other proposed techniques by virtue of empirical evaluation, our paper was seminal in that it provided four crucial novelties:

1. It started out by boiling down the computation of a suspiciousness (of a piece of code) to its simplest intuition — generically, the more failed test cases that execute a statement the more likely it is to be faulty.
2. It then added on the intuition that the more successful test cases that execute a statement the less likely it is to be faulty.
3. Next, it posited that test case/code-coverage data should not be considered in isolation; rather, each additional test case provides additional information that should be taken into account in tandem with prior information such that the weight assigned to a piece of information (that is used to assign a suspiciousness score) is fluid and evolutionary.
4. Finally, it introduced the most important concept that not all the failed (or successful) test executions provide the same contribution towards fault localization. More precisely, with respect to a piece of code, the contribution introduced by the first failed test that executes it in computing its likelihood of containing a bug is larger than or equal to that of the second successful test that executes it, which is larger than or equal to that of the third successful test that executes it, etc. The same applies to the successful.

This is why our paper is titled as such — it evolves from simple intuition to more complex computations and in doing so provides ‘a family of heuristics’ to achieve fault localization. When our heuristics were compared to the state-of-the-art at the time across multiple types of programs, spanning multiple programming languages and faulty versions, they outperformed those fault localization techniques compared to. As a result, it became the state-of-the-art. This is one of the reasons for it being cited as much as it has been — it has represented/represents a benchmark that newly proposed techniques must assess themselves relative to (especially because of the comprehensive results we provided across multiple programs from varied sources). Additionally, our paper facilitated other research in the area because our heuristics offered extension points both in terms of manipulating weights as well as adding on to the basic intuitions.

To conclude, not only can this family of heuristics help programmers quickly (efficiently) locate bugs by examining a small percentage of code (effectively), but it also gives them the flexibilities to customize the heuristics that are appropriate for their projects in their working environments.

We are very grateful for the recognition that this paper has received over the last few years and are hopeful that this trend continues. In fact, we fully expect the general trend to continue given the advances that have been made lately in related areas, such as cloud computing and internet-of-things to name a few. Storage capacities have greatly increased and the speed at which data can be collected and processed has also increased, especially with ever-expanding global connectivity. Nevertheless, the fundamental problem still exists — given this wealth of data, how do we use it to pinpoint the faulty code when things go wrong? Our proposed heuristics offer a way of looking at things that is almost as fundamental as the very problem itself. That is why we believe this paper, and related works both published by us and by others, will continue to have a considerable impact in the years to come.

We thank very much the Journal of Systems and Software for publishing this paper and nominating it as one of the finalists for the 2020 Most Influential Paper.

Remark: A conference version of this paper, Effective Fault Localization using Code Coverage, with preliminary results was published at the 31st IEEE International Computer Software and Applications Conference in 2007 and received the Best Paper Award from the conference.

Vidroha and Eric