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; (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.
우리는 외부 오라클을 가지고 있을 때, 결함 위치 추정의 성능을 향상시키는 새로운 방식인 Flip 을 제시한다. 스펙트럼 기반 결함 위치 추정 기술은 테스트 오라클의 성공 및 실패 테스트 케이스의 실행 흐름에 기반하여 의심스러운 구문을 추정한다. 최신 기술은 유닛테스트와 선언문같이 프로그램의 내부적으로 존재하는 테스트 오라클에 의존하고 있다. 하지만 흔히 프로그램은 이러한 내부 오라클의 존재가 부족하고, 프로그램 바깥에서 관찰할 수 있는 외부 오라클을 가지고 있다. (예를 들어, 모범 프로그램 혹은 예상 출력 결과) 이러한 사실은 긴 프로그램 실행의 종료 이후에만 실행 결과를 관찰할 수 있도록 만들기 때문에, 의심스러운 구문에 대한 정확한 추정을 방해한다. 이 논문에서는반사실적 프로그램실행을 관찰함으로써, 자세한 내부 오라클이 없는 경우에서도 더 정확한 추정을 가능하는 것을 목표로 한다. 먼저, 우리는 성공 및 실패 테스트가 다른 분기를 실행하는 분기문들을 선정한다. 그리고 나서, 우리는 두 가지 반사실적 시나리오를 관찰한다: (1) 만약 분기 조건을 특정 불리언 상수로 설정하였을 때, 대부분의 성공 테스트케이스를 여전히 통과한다면, 우리는 분기문에서 새롭게 실행된 구문들이 결함과 관련이 적다고 간주한다; (2) 만약 분기 조건을 특정 불리언 상수로 설정하였을 때, 실패 테스트케이스가 여전히 실패한다면, 우리는 기존에 실행되던 구문이 결함과 관련이 적다고 간주한다. 우리는 이 아이디어를 Flip 에 구현하였고, 널리 사용되는 C와 Java 프로그램들에 대해 성능을 평가하였고, 그 결과는 최신 기술들을 뛰어넘는 결과를 보여주고 있다. Flip 은 결함 위치 추정 성능을 라인 수준에서 평균 23-24%, 함수 수준에서 평균 24% 으로 최신 SBFL 기술 보다 향상시킨 모습을 보여준다. 또, Java 프로그램에 대해서도 더 많은 Top-1, Top-3, Top-5, Top-10 등수의 결함을 발견하는 모습을 보여주고 있다.
