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 local-ization: for each statement we determine the num-ber 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 accord-ing to how likely they are to be buggy. Many differ-ent metrics have been used. Here our main focus is to determine how much improvement in performance could be achieved by finding better metrics. We de-fine 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 atten-tion to these metrics. We show that every single bug optimal metric performs as well as any strictly ratio-nal 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.