Evaluation Metric for Multiple-Bug Localization with Simple and Complex Predicates

Statistical debugging is a technique that mines data obtained from software executions in order to identify the program statements that are relevant to program bugs. Specifically, program predicates are injected into the program during compilation and statistics about those predicates are collected during the program execution. When bugs are found but the developers have no clue where the bugs are, they may call such a statistical debugger for help. The debugger ranks the injected predicates according to their statistical relevancy to bugs and presents the suspicious ones to the developers. When a bug is found and fixed, but the updated program still contains (some other) bugs, the preceding procedure is iterated until all bugs are fixed. There are two types of predicate-based statistical debugger: one type returns only simple predicates, another type returns only complex predicates. We envision that the next wave of statistic debuggers should be able to return both, depending on the kinds of bugs manifested in the software. In this paper, we take the first step and study the metrics for evaluating the effectiveness of statistical debuggers that can return both types of predicate predictors (simple or complex).