Improving fault localization with external oracle by using counterfactual execution

Abstract

(2) if the branch condition is set to a boolean constant and the failing test case still fails, we also consider the originally executed statements as unrelated to the failure. We implemented this idea in a tool called Flip and evaluated the performance on a suite of widely used C and Java programs. The results show that Flip outperforms the state-of-the-art techniques. Flip improves the accuracy of state-of-the-art SBFL techniques on C programs, by 23-24% on average in line-level and by 24% on average in function-level fault localization. Flip also improves the accuracy of state-of-the-art techniques on Java programs by ranking more faulty statements within Top-1, Top-3, Top-5, and Top-10 entries in the ranked list.

We present Flip, a new approach to improve fault localization with external oracles. Spectrum-based fault localization techniques estimate suspicious statements based on the execution trace of the passing and failing test cases determined by test oracles. State-of-the-art techniques rely on test oracles that internally exist in the program under test in the form of assertions or unit tests. However, programs often lack such internal oracles but have external oracles that observe the behavior of the program from outside (e.g., existing reference programs or expected output files). This in turn hinders fine-grained and accurate estimation of suspicious statements in practice because the correctness of each execution can only be observed at termination after long execution. In this paper, we aim to address this problem by observing counterfactual execution traces, which enable fine-grained estimation even without precise internal oracles. Initially, we select a set of branch statements that discriminates the passing and failing test cases. Then, we observe two types of counterfactual scenarios: (1) if the branch condition is set to a boolean constant and most of the passing test cases still pass, we consider the newly executed statements in the branch statement as unrelated to the failure