문서요약 - 결함 위치 식별 기법에 대한 조사 by Perez

제목: 결함 위치 식별 기법에 대한 조사(A Survey on Fault Localization Techniques)

저자: Alexandre Perez 외 2인, 포르투갈

문서유형: 기술 문서(총 10페이지), 2014년

 

현재 가용한 여러 종류의 디버깅(특히, 소프트웨어 결함 위치 식별) 기법들을 분류하고 이들을 비교한 자료

---

디버깅

• 디버깅은 컴퓨터 프로그램에서 잘못된 문장(statements)을 발견하고(detecting), 정확한 위치를 찾고(locating), 수정하는(fixing) 프로세스와 관련됨
• 테스팅 뿐만 아니라 디버깅도 소프트웨어 개발 시 무시해서는 안 되는 중요한 단계임
• 디버깅에 많은 리소스가 소모됨에 따라 개발자들의 디버깅 작업을 돕는 방법들이 지속적으로 연구되어옴. 현재 소프트웨어 프로그램에서 결함의 근원일 가능성이 높은 부분을 자동/반자동으로 집어내는 일부 기법들이 존재함

용어 정의

• 실패(A failure): 전달된 서비스가 올바른 서비스에서 벗어날 때 발생하는 이벤트
• 에러(An error): 실패(a failure)를 야기할 수도 있는 시스템 상태
• 결함(A fault/defect/bug): 시스템에서 에러의 근원(the cause of an error)

 

본 논문에서는 위 용어들이 소프트웨어 프로그램에 적용됨. 즉, 결함(faults)은 프로그램 코드에 있는 버그이고, 실패(Failures)와 에러(errors)는 프로그램에 있는 결함에 의해 야기된 증상(symptoms)이다. 결함 위치 식별(fault localization)의 목적은 관측된 증상의 근본 원인(the root cause of observed symptoms)을 정확히 찾아내는 것이다.

전통적 디버깅(Traditional Debugging)

전통적 디버깅 방법들은 대부분의 프로그래밍 언어에서 가용하며 대개 통합 개발 환경(integrated development environments: IDEs)에 통합되어 있음

 

A. 프린트문(Print Statements)

• 프로그램이 비정상적인 동작을 보일 때 버그를 찾기 위해 임기응변으로 print 문을 입력하여 특정 변수의 값이 출력되도록 함
• 입력된 프린트문을 통해 보여지는 런타임 상태 및 제어 흐름에 대한 추가적인 정보는 개발자가 실패의 근본 원인을 식별하는걸 돕는다.

 

B. 어써션(Assertions)

• 어써션은 시스템이 무엇을 하도록 의도된 건지 명세하기 위해 개발자가 활용할 수 있는 정형적 제약(formal constraints)이다.
• 이 제약은 일반적으로 if 문으로 쓰여진(즉, 어써션 내의 표현식이 거짓으로 판명되면 실행을 중단) 사전 정의된 매크로이다.

 

C. 중단점(Breakpoints)

• 중단점(a breakpoint)은 어떤 명세된 인스트럭션에 도달했을 때 프로그램 실행의 제어를 사용자에게 넘겨주어야 함을 명세한다. 즉, 프로그램 실행이 중단되며 사용자가 프로그램 상태를 조사 및 조작할 수 있다(예, 사용자가 변수 값을 읽고 변경할 수 있음).
• 또한 중단점 후에 단계적 실행(a step-by-step execution)이 가능하다. 이게 버그의 진행 과정을 관측하고 그 근원으로 추적해 나가는데 특히 유용함

D. 프로파일링(Profiling)

• 프로파일링은 프로그램 실행으로부터 일부 메트릭(예, 메모리 사용, 함수 호출의 빈도와 지속 시간)을 수집하는 동적 분석이다.
• 프로파일링의 주된 사용은 프로그램 최적화를 돕는데 있지만, 아래와 같은 디버깅 목적으로도 유용함:
  - 함수가 예상보다 더 자주(또는 더 적게) 호출되는지 알 수 있음
  - 코드의 특정 부분이 예상 보다 더 느리게 실행되거나 또는 메모리 누수를 포함하고 있는지 알 수 있음
  - ‘게으른 평가 전략(프로그래밍 언어에서 표현식의 평가를 그 값이 필요 시 될 때까지 지연하는 전략)’의 동작을 조사할 수 있음
• 알려진 프로파일링 도구로 GNU의 gprof와 Eclipse 플러그인 TPTP가 있음

 

E. 코드 커버리지 분석(Code Coverage Analysis)

• 코드 커버리지는 시스템 테스트 런 동안에 테스트 대상 시스템의 어떤 부분이 실행되었는지(커버되었는지) 결정하는 분석 방법이다.
• 코드 커버리지를 테스트와 함께 사용하면 특정 테스트에서 코드의 어떤 라인/메쏘드/클래스가 커버되었는지 알 수 있으며, 이 정보를 가지면 어떤 시스템 실패에 어떤 컴포넌트가 관련되었는지 식별하는 것이 가능하다(테스트를 실패하게 만든 잘못된 컴포넌트를 찾기 위한 수색을 좁혀나갈 수 있음).
• 각 테스트 런에서 어떤 컴포넌트가 커버되었는지에 대한 정보를 얻기 위해서는 코드 커버리지 툴이 시스템 코드를 인스트루멘트(계측) 해야 함. 즉, 삽입된 인스트루멘테이션 코드가 각 컴포넌트를 모니터하고 그게 실행되면 이 사실을 기록함

프로그램 슬라이싱(Program Slicing)

• 정적 프로그램 슬라이싱(static program slicing)은 실패로부터 시작하여 이 결함 위치에 도달하기 위한 역방향 추론에 프로그램의 제어/데이터 흐름을 사용하는 방법이다. 즉, 실패를 발견하는데 책임이 있는 관심 변수와 데이터 의존 관계(또는 제어 의존 관계)가 없는 모든 문장들을 제거함으로써 소프트웨어 프로그램의 커버된 문장들을 좁혀 나감
• 슬라이스(a slice)는 주어진 관심 변수들 집합의 값에 직접/간접적으로 영향을 미치는 프로그램 문장들의 한 부분집합(a subset)으로 볼 수 있다. 디버깅이 전체 프로그램을 검토하는 대신에 이 슬라이스를 형성하는 문장들을 검사함
• 일부 문장들은 런타임 값들을 예측해야 비로소 제외될 수 있음. 그런 이유로 동적 프로그램 슬라이싱(dynamic program slicing)이 도입됨. 동적 프로그램 슬라이싱은 슬라이스에 어떤 문장들이 속하는지 결정하기 위해 실행 정보에 의존하며, 슬라이스의 크기를 현저하게 줄일 수 있다.

델타 디버깅(Delta Debugging)

• 델타 디버깅은 특정 프로그램을 실패에 이르게 하는 입력을 체계적으로 간소화하려는 기법이다. 즉, 실행이 실패하도록 만드는 최소화된 입력에 도달할 때까지 입력의 크기를 반복적으로 줄여나감
• 프로그램을 여전히 실패하게 만드는 가장 작은 입력이 원래 입력보다 더 적은 코드 라인을 커버한다는(그래서 디버깅 하기가 더 쉽다는) 가정에 기반함. 또한 입력이 분해되어 간소화될 수 있다는 가정에 기반하는데, 이게 항상 사실은 아님

 

아래 그림이 델타 디버깅 기법의 예를 묘사함. 이 예에서 프로그램이 1~8까지의 정수 집합을 입력으로 받는다고 가정

• 델타 디버깅을 사용하기 위해 집합 내 모든 가능한 요소들을 포함하는 초기 입력 값이 고안됨(아래 그림에서 Test Case 1)

• Test Case 1이 실패하므로 다음 테스트케이스들로부터 입력 값들을 제거함(Test Case 2와 3). 테스트 결과가 성공(ü)과 실패(û) 외에 Test Case 2처럼 미해결인 경우(? 표시)도 있는데, 보통 유효하지 않은 입력이 프로그램으로 전달될 때 발생함
• 델타 디버깅 알고리즘의 다음 단계는 실패로 이르는 테스트케이스를 위한 입력 크기를 계속 분할하는 것이다. 이 예에서는 Test Case 3이 Test Case 4와 5로 확장됨
• 이 후 Test Case 5가 Test Case 6과 7로 확장됨. 아래 그림에서 볼 수 있듯이 Test Case 6이 여전히 실패를 야기하는 최소 입력을 생성함. 따라서 이 기법의 결과로 요소 7을 포함하는 카디널리티 1의 집합이 나오게 됨

[델타 디버깅 예]

커버리지 기반 접근방법(Coverage-based Approaches)

A. 프로그램 스펙트럼(Program Spectra)

• 프로그램 스펙트럼은 프로그램의 실행 정보를 특정 측면에서 기록함(예, 조건 분기를 위한 실행 정보, 루프 프리 프로시져 내 경로 등)
• 프로그램 스펙트럼이 테스트 대상 시스템의 동적 행동에 대한 뷰를 제공한다(프로그램 동작을 추적하는데 사용될 수 있음).

 

B. 스펙트럼 기반 결함 위치 식별(Spectrum-based Fault Localization)

• 스펙트럼 기반 결함 위치 식별은 각 소프트웨어 컴포넌트에 대해 그게 잘못되었을 가능성을 계산하는 통계적 디버깅 기법이다. 성공한 시스템 런(정확하게 완료된 프로그램 실행)과 실패한 시스템 런(에러가 발견된 프로그램 실행)으로부터의 정보를 활용함
• 어떤 런이 성공인지 실패인지 결정하는 기준은 다양한 소스로부터 올 수 있음(즉, 테스트케이스 결과, 프로그램 어써션, 등). 각 런을 위해 수집된 실행 정보가 그것의 프로그램 스펙트럼이 됨
• ‘히트 스펙트럼(컴포넌트가 특정 실행 동안 커버되었는지 아닌지 기록한 바이너리 매트릭스)’가 각 소프트웨어 컴포넌트(예, 코드 라인)와 매 시스템 런을 위한 카운터/플래그로 구성됨. 결함 위치 식별은 어떤 컴포넌트가 성공한 런 그리고 실패한 런을 가장 많이 닮았는지 식별하는데 있다(similarity coefficient 계산). 모든 컴포넌트에 대해 버그를 포함하고 있을 가능성(likelihood)이 계산되고, 진단 보고서에 그 순위대로 정렬되어 개발자에게 제공됨. 즉, 관측된 실패의 근본 원인을 찾기 위해 개발자가 조사해야 할 소프트웨어 컴포넌트의 우선순위를 판단하는데 이 리스트가 도움이 됨

추론 접근방법(Reasoning Approaches)

추론 기반 접근방법은 시스템을 디버그하기 위해 시스템 모델과 런타임 관측을 사용한다.

 

A. 모델 기반 진단(Model-Based Diagnosis: MBD)

• 런타임 관측과 결합한 시스템의 정적 모델의 논리적 추론에 의해 진단을 함
• 전통적인 모델 기반 진단 시스템은 시스템 설계자가 모델을 제공할 것을 요구함. 반면 관측된 동작의 서술은 직접적인 측정을 통해 수집됨
• 모델에 의해 서술된 동작과 관측된 동작 간의 차이가 정상 동작으로부터의 일탈을 설명할 수도 있는 컴포넌트를 식별하는데 사용됨

 

B. 모델 기반 소프트웨어 디버깅(Model-Based Software Debugging: MBSD)

• 현실에서는 원하는 프로그램의 정형적 모델/서술이 가용하지 않거나 유지보수 문제(개발 동안 기능이 계속 변경되는데 이를 매번 반영하기 어려움) 등으로 인해 전통적인 MBD를 활용하기가 어려움
• 이런 이슈들을 일부 고려해서 모델 기반 소프트웨어 디버깅(MBSD)은 설계자가 의도된 동작을 정형적으로 명세하도록 요구하는 대신 실제 프로그램으로부터 모델을 자동으로 추론한다. 이 말은 모델이 프로그램에 존재하는 모든 결함들도 반영한다는 의미
• 이 기법에서는 올바른 동작 명세가 특정 입력에 대한 예상 출력을 명세한 테스트케이스에 의해 서술된다. 즉, 실제 프로그램으로부터 자동 도출된 모델의 동작을 시스템의 테스트케이스의 그것과 비교

디버깅 기법 비교

위에서 제시된 결함 위치 식별 기법들을 진단 품질(diagnostic quality), 계산 비용(computational overhead), 확장성(scalability)의 세 가지 측면에서 비교한 결과가 아래 표와 같다. 표에서 볼 수 있듯이 이 중 어느 기법도 다른 것보다 모든 측면에서 우월하거나 하지 않음. 따라서 가장 좋은 결함 위치 식별 기법은 각 상황에 따라 고려되어야 한다.

	진단 품질	계산 비용	확장성
전통적 디버깅	저(Low)	저(Low)	중(Medium)
프로그램 슬라이싱	중(Medium)	중(Medium)	중(Medium)
델타 디버깅	중(Medium)	중(Medium)	고(High)
커버리지 기반 접근방법	중(Medium)	저(Low)	고(High)
추론 기반 접근방법	고(High)	고(High)	저(Low)