As software becomes more complex due to a number of complex software requirements, debugging program becomes very challenging. One of the most expensive task of debugging process is to locate the root cause of program failures (i.e., fault). This process, called fault localization, requires developers to understand complex internal logic of Program Under Test (PUT) to identify the location of fault while inspecting enormous program states.
To reduce the human efforts for fault localization, therefore, we propose two fault localization techniques that utilize dynamic program behaviors. Each of the proposed techniques automatically ranks statements of PUT according to their predicted risk of containing faults, which is essentially computed based on the dynamic information (e.g., a set statements executed by a test case) gathered from test case executions of PUT. Developers can effectively locate the fault by inspecting PUT while following the order of statements in the ranking generated by the proposed techniques. The key ideas of proposed techniques can be summarized as follows.
One of the proposed techniques, called FIESTA, utilizes correlation between failing executions and
each of executed program statements to identify the location of faults. The degree of the correlation indicates the degree of possibility that a statement contains faults, which is used to rank program statements. FIESTA strengthens the correlation between failing executions and faulty statements, by eliminating program structures that can weaken the correlation through the program transformation. It also assigns fault weight on a test case that indicates likelihood of the test case to execute a faulty statement. Thanks to the strengthened correlation, FIESTA can localize faulty statements more effectively than the previous fault localization techniques do.
The other one, called MUSE, utilizes mutation analysis to uniquely capture the relation between individual program statements and observed failures. The key idea of MUSE is to identify a faulty statement by utilizing different characteristics of two groups of mutants | one that mutates a faulty statement and the other that mutates a correct one. For example, MUSE prioritizes statements where modifications (i.e., mutants) on those statements make failing test cases become passing ones, since a faulty program is usually repaired by modifying (i.e., mutating) faulty statements.
In addition, we also propose an evaluation metric for fault localization techniques based on information theory, called Locality Information Loss (LIL). It enables to measure the aptitude of a fault localization technique for tools that automatically fix faults, which the existing evaluation metric cannot.
To evaluate the effectiveness of our techniques, we carried out experiments by applying the proposed techniques on 12 C-programs including 5 real-world programs. The experimental results showed that the proposed techniques are very effective for locating many faults. For example, MUSE ranks a faulty statement among the top 7.4 places on average, which is about 25 times more precise than the state-of-the-art fault localization technique, called Op2, on average. It implies that the proposed techniques can reduce the human efforts for fault localization significantly.
본 논문에서는, 먼저 이전 결함 위치추정 기법들의 근본적 접근방법과 한계에 대해서 조사하였다. 이 조사에서, 전도유망한 연구 방향 중 하나인 스펙트럼에 기반한 결함 위치추정 기법(Spectrum-based Fault Localization (SBFL))의 한계에 대해서 설명했다. 그 한계는, 우연히 성공한 테스트 케이스 (Coincidentally Correct Test Cases (CCTs))로 인한 부정적 효과와 SBFL 기법의 정제되지 않은 블락 단위 수준이었다. 두 번째로, 본 논문에서는 CCT의 부정적 효과를 감소시키는 결함 위치추정 기법인 FIESTA를 제안하였다. FIESTA 기법은 각 테스트 케이스가 결함을 실행했을 확률을 나타내는 ‘Fault weight’척도와 CCT의 수를 줄이는 ‘Debuggability transformation’기법을 이용하여 결함과 실패 실행간의 상관관계를 향상 시킨다. 결함과 실패 실행간의 향상된 상관관계는, FIESTA가 기존의 SBFL 기법에 비해 더 정확하게 결함의 위치를 추정하도록 만든다. 12개의 C 프로그램(173 ~ 12,653 LOC 로 구성)에 대한 실험을 통해 FIESTA가 대표적 SBFL 기법인 Tarantula에 비해 상대적으로 49% 더 정확하게 결함의 위치를 추정하는 것을 확인할 수 있었다. 세 번째로, 우리는 변형 분석을 활용하여 결함의 위치를 추정하는 새로운 종류의 결함 위치추정 기법인 MUSE를 제시했다. MUSE 기법은 본 논문에서 제시한 두 개의 가정에 기반하여 결함의 위치를 추정한다. 두 개의 가정은 기본적으로 결함 구문을 변형시킨 변형 프로그램들과 결함 구문이 아닌 구문을 변형시킨 변형 프로그램들을 실행한 테스트 케이스의 결과가 서로 다른 특성을 보임을 이용한다. 5개의 실제 C 프로그램들(6,576 ~ 12,653 LOC 로 구성)에 대한 MUSE의 성능평가 결과로부터 MUSE는 결함 구문의 순위를 평균적으로 상위 7.4등 이내로 매기는것을 확인할 수 있었다. 이 실험결과는 지금까지 알려진 가장 정확한 SBFL 기법인 Op2 보다 평균적으로 약 25배 더 정확한 결과다. 네 번째로, 결함 위치추정 기법의 성능을 평가하는 새로운 평가 척도인 LIL 척도를 제안하였다. LIL 은 정보 이론에 기반하여 이상적인 위치추정 결과와 어떤 결함 위치추정 기법에 의해 주어진 위치추정 결과 사이의 정보 손실을 측정한다. LIL을 이용한 다수의 결함 위치추정 기법에 대한 평가와 자동 프로그램 수리 도구를 이용한 사례 연구를 통해, LIL이 결함 위치추정 기법의 자동 프로그램 수리 도구에 대한 성능을 측정하는데 유용할 수 있다는 것을 확인하였다.
