Spectral debugging: how much better can we do?

This paper investigates software fault localization methods which are based on program spectra - data on execution profiles from passed and failed tests. We examine a standard method of spectral fault localization: for each statement we determine the number of passed and failed tests in which the statement was/wasn't executed and a function, or metric, of these four values is used to rank statements according to how likely they are to be buggy. Many different metrics have been used. Here our main focus is to determine how much improvement in performance could be achieved by finding better metrics. We define the cost of fault localization using a given metric and the unavoidable cost, which is independent of the choice of metric. We define a class of strictly rational metrics and argue that is reasonable to restrict attention to these metrics. We show that every single bug optimal metric performs as well as any strictly rational metric for single bug programs, and the resulting cost is the unavoidable cost. We also show how any metric can be adapted so it is single bug optimal, and give results of empirical experiments using single- and two-bug programs.