Duals in Spectral Fault Localization

Lee Naish
Hua Jie (Jason) Lee

Numerous set similarity metrics have been used for ranking "suspiciousness" of code in spectral fault localization, which uses execution profiles of passed and failed test cases to help locate bugs. Research in data mining has identified several forms of possibly desirable symmetry in similarity metrics. Here we define several forms of "duals" of metrics, based on these forms of symmetries. Use of these duals, plus some other slight modifications, leads to several new similarity metrics. We show that versions of several previously proposed metrics are optimal, or nearly optimal, for locating single bugs. We also show that a form of duality exists between locating single bugs and locating "deterministic" bugs (execution of which always results in test case failure). Duals of the various single bug optimal metrics are optimal for locating such bugs. This more theoretical work leads to a conjecture about how different metrics could be chosen for different stages of software development.

Keywords: debugging, bug localization, program spectra, set similarity

An almost identical version of this paper will appear in the proceedings of ASWEC 2013 and you will be able to get from IEEE, for a price.