페이퍼요약 - 훼손된 메모리 위치 억제를 활용한 메모리 버그의 근본원인 식별 by Jeffrey

제목: 훼손된 메모리 위치 억제를 활용한 메모리 버그의 근본원인 식별(Identifying the Root Causes of Memory Bugs Using Corrupted Memory Location Suppression)

저자: Dennis Jeffrey 외 2인, 미국

문서유형: 컨퍼런스 페이퍼(총 10 페이지), 2008년

 

훼손된 메모리 위치 사용으로 인해 발생하는 메모리 관련 버그의 근본원인을 자동 식별하는 방법을 제안한 자료

---

소프트웨어 디버깅(Software Debugging)

• 디버깅은 아래의 일련의 단계들을 수반한다.
  1) 소스 코드에서 버그 위치를 찾아내고,
  2) 이 버그의 성질(the nature of the bugs)을 이해하고,
  3) 새로운 버그 생성 없이 해당 버그를 제거하도록 소스 코드를 수정한다.
• 대규모의 복잡한 소프트웨어 시스템에서는 디버깅이 쉽지 않기 때문에 디버깅 프로세스 자동화를 돕는 기법들을 활용하여 개발자가 더 효과적으로 버그를 제거할 수 있도록 함

소프트웨어에서 흔히 나타나는 메모리 관련 버그

• 버퍼 오버플로우(buffer overflows): 버퍼 경계 밖에 있는 메모리 위치가 접근되었을 때 발생. 이는 프로그램 데이터의 예상치 못한 훼손을 야기하고 잠재적으로 프로그램 크래시(a program crash)로 이어질 수 있다.
• 스택 스매싱(Stack smashing): 콜 스택(the call stack) 상에서 호출된 함수의 리턴 주소가 덮어써졌을 때(overwritten) 발생. 이 때 프로그램 컨트롤이 불법 주소로 점프를 시도하면 함수 리턴에서 프로그램이 크래시가 일어 날 수 있음. 더 위험한 예로 함수 리턴 주소를 훼손하는데 사용된 값이 공격자에 의해 주의 깊게 선택되는 경우 프로그램 컨트롤이 악성 코드에게로 넘어갈 수 있다.
• 초기화되지 않은 읽기(uninitialized reads): 어떤 메모리 위치가 해당 위치에 적절한 값이 저장되기에 앞서 로드(load)될 때 발생. 예상 못한 임의의 값이 로드되면서 메모리 훼손으로 이어질 수 있다.
• 이중 해제(double frees): 이전에 이미 자유롭게 된 위치에서 free 함수 호출이 일어날 때 발생. 할당된 메모리가 부적절하게 취급되는 상황을 나타내며, free 호출 내에서 실행 중 프로그램이 중지(abort)됨

메모리 관련 버그의 성격

• 대부분의 메모리 버그가 훼손된 메모리 위치(corrupted memory locations) 사용과 관계된다는 공통적 특징을 가짐
• 버그로 인한 하나의 훼손된 메모리 위치의 영향이 프로그램 실행 동안 다른 메모리 위치로 퍼져 나갈 수 있으며, 결국 이 훼손된 메모리 위치들 중 하나에서 관측 가능한 실패(예, 프로그램 크래시, 훼손되거나 예상 못한 결과 값)가 발생할 쯤에는 많은 다른 메모리 위치도 이미 훼손되었을 수 있다.
• 이 때 버그의 근본원인 지점과 버그가 관측된(모습을 드러낸) 지점이 매우 다를 수 있고 따라서 관측된 메모리 버그 증상으로부터 그 근본원인을 집어내기가(isolate) 쉽지 않다.

제안된 메모리 버그 근본원인 식별 방법

• 제안 방법은 프로그램 실행 중에 훼손된 메모리 위치와 관련된 것으로 보이는 코드문(인스트럭션)의 영향을 반복적으로 억제(즉, 무효화 시킴)하여 점차적으로 메모리 버그의 근본원인을 찾아낸다.
• 즉, 실패를 야기하는 동일한 입력 데이터(테스트케이스)로 프로그램을 반복적으로 실행시키고, 각 실행 마다 관측된 메모리 실패의 직접적 원인과 그것의 모든 직접, 간접 영향을 억제(무효화)하여 같은 프로그램 실패가 일어나지 않게 만든다. 이런 과정은 더 이상 메모리 관련 실패가 발생하지 않을 때까지 반복되며, 이 마지막 억제와 관련된 문장(statement)이 메모리 훼손의 근본원인일 가능성이 높다.
• 제안 방법이 메모리 누수 버그(memory leak bugs)에는 효과적이지 않음. 제안 방법은 메모리 버그가 프로그램 실행 중에 훼손된 메모리 위치 접근으로 인해 발생된다고 가정함. 하지만 메모리 누수는 단지 특정 메모리 위치가 자유롭게 되어야 할 시점에 그러지 못해서 문제가 될 뿐 메모리 위치는 실제 훼손되지 않았을 수도 있기 때문에 이 가정에 해당되지 않는다.

메모리 버그의 근본원인을 식별하는 예

아래 예는 어떻게 단일 버그로 인한 메모리 훼손이 여러 코드문을 거쳐 퍼져나가고 결국 프로그램 크래시로 이어지는지 보여준다.

[코드 예]

• 코드의 라인4에 에러가 존재함. 라인 1과 2를 복사하여 라인 3과 4에 붙이는 작업에서 개발자가 라인4의 변수 x를 y로 변경하는 것을 깜박하였고 그 결과 포인터 p2와 q2가 같은 메모리 위치를 참조하게 됨
• 라인8에서 *q2 위치에 어떤 값이 저장되면 애초에 라인6에서 저장되었던 값이 망가짐. 이후 코드문에서 *p2/*q2 위치의 값이 사용되면서(즉, 훼손된 메모리 위치가 사용됨) 다른 메모리 위치(라인9, 10, 11)들이 추가적으로 훼손됨
• 즉, 라인4에 있는 애초의 버그가 여러 위치로 퍼져 나가고 결국 프로그램 크래시 같은 관측 가능한 실패가 발생한다(잠재적으로 라인12, 13, 15에서 발생 가능).

아래 그림은 위 코드가 어떤 입력 데이터를 받아 실행되는 상황을 표현한 것으로 원래의 실행(original run)과 3번의 억제된 실행(suppression runs)을 나타내고 있음. 실선 원은 실행된 코드문(executed statements)을 점선 원은 억제된 코드문(suppressed statements)을 표현. 메모리 위치를 정의하는 코드문은 해당 위치가 훼손되었는지(û) 정상인지(ü) 알리는 표시가 붙여져 있음

[코드 예의 원래의 실행과 3차례의 억제된 실행]

(A) 오리지널 런: 라인4에서 부정확한 메모리 위치를 가리키는 포인터 q2가 훼손됨. 라인8에서 이 메모리 위치에 이전에 저장된 값이 덮어쓰기 되면서 해당 위치가 훼손됨. 라인9에서 위치 *p2/*q2의 훼손된 값을 사용하므로 위치 a의 정의(definition)가 훼손되고, 라인10에서 위치 b의 정의도 비슷하게 훼손됨. 이는 라인11에서 위치 c의 훼손을 낳음. 라인12에서 어레이 intArray의 경계 밖 불법 주소에 접근하는 훼손된 어레이 인덱스 c 때문에 프로그램 크래시가 나타남(즉, 버퍼 오버플로우 에러 발생) 

현실에서는 훼손된 모든 메모리 위치를 우리가 알지 못하므로 라인12에서 버퍼 오버플로우 에러가 관측될 때 라인4에 있는 근본원인을 찾아내기가 쉽지 않음. 단지 라인12에서 어레이 인덱스 c가 버퍼 intArray를 오버플로우하는 것만을 알고 있으며 그 근본원인으로 많은 가능성이 존재. 예를 들어, 라인12 자체가 에러일 수도 있고, 또는 변수 c가 훼손된(부정확한) 값을 가진다고 가정하면 라인12의 변수 c 값에 영향을 미친 더 앞쪽의 문장(라인9, 10, 또는 11)에 문제가 있을 수도 있다. 또는 변수 c는 정확한 값을 가지고 있지만 버퍼 intArray의 크기가 잘못된 것일 수도 있다. 즉, 이 예는 버그의 실패가 관측되기 전까지 여러 문장을 거쳐 메모리 훼손이 퍼질 수 있으며, 이 경우 메모리 관련 버그의 근본원인을 식별하는 것이 쉽지 않음을 보여줌

 

(B) 1차 억제 런: 라인12에서의 프로그램 크래시의 근본원인을 찾기 위한 첫 단계로 이 크래시를 직접 야기한 것으로 현재 알려진 메모리 훼손을 억제하면서 프로그램을 재실행함. 즉, 라인12에서 위치 c의 값이 사용되었고, 이 c가 라인11에서 마지막으로 정의되었으므로 라인11을 억제하여 프로그램을 재실행함. 당연히 이 c 정의에 직접, 간접적으로 영향을 받는 타 문장들도 억제됨. 즉, 라인11과 12가 억제되고 프로그램 실행이 라인13에 다다랐을 때 또 다른 크래시가 발생함(훼손된 위치 *p2가 struct 포인터 어레이의 인덱스로써 사용되었기 때문). structArray[*p2]가 NULL이므로 라인13에서 NULL이 역참조되면서 세그멘테이션 결함(segmentation fault)이 발생함. 이 결함의 근본원인은 여전히 라인4이지만 라인13에서 사용된 훼손된 위치 *p2가 라인4의 에러와 관련 있는 것이 아직은 확연하게 보이지 않음

 

(C) 2차 억제 런: 라인13에서의 크래시와 직접 관련된 메모리 훼손을 억제하여 프로그램을 다시 실행함. 라인8에 있는 위치 *p2의 마지막 정의를 억제하고(포인터 q2가 실제 p2와 동일한 위치를 참조하므로 라인8이 적절한 마지막 정의임), 또한 이 정의에 의해 직접, 간접적으로 영향을 받는 다른 코드문도 억제함. 즉, 라인8, 9, 10, 11, 12, 13이 억제된다. 라인14와 15가 억제되지 않는 이유는 라인8에 정의된 훼손된 위치가 라인 14와 15에서 사용된 포인터 p2와 q2의 위치 자체에는 실제 영향을 주지 않기 때문임. 하지만 이 새로운 실행에서도 프로그램 크래시가 발생한다(라인15에서 동일 메모리 위치의 이중 해제로 인해 프로그램이 중지됨).

 

(D) 3차 억제 런: 라인4에서의 포인터 q2의 정의를 억제하고 더불어 라인15에서 이 포인터의 사용도 억제한다. 통틀어 라인1, 2, 3, 5, 6, 7, 14만이 실행되고, 모든 훼손된 메모리 위치 사용이 억제되었기 때문에 크래시 없이 프로그램이 정상적으로 진행한다(즉, 오로지 비훼손 메모리 위치와 관련된 문장들만이 실행됨). 그 결과 가장 최근 억제된 문장인 라인4가 프로그램 크래시로 이어지는 모든 메모리 훼손의 근본원인이라고 결론짓게 된다.

제안 방법의 알고리즘

위의 예에서 설명한 메모리 버그의 근본 원인 식별 방법을 알고리즘으로 표현하면 아래와 같다.

[제안된 방법 알고리즘]

제안 방법의 구현

제안된 방법이 아래 그림과 같은 구조로 구현됨. 양방향 화살표는 시스템 컴포넌트들 간의 상호작용을 의미함

[제안 방법의 구현 – 상위 레벨 시스템 설계]

• Valgrind Core: Valgrind 인프라구조가 소프트웨어에 종합적인 CPU를 제공하고 실행가능한 프로그램의 동적 바이너리 인스트루멘테이션을 허용함. Valgrind가 특정 프로파일링과 디버깅 작업을 수행하는 도구 셋을 포함하지만 커스토마이징된 인스트루멘테이션 작업을 수행하기 위한 새로운 도구를 인프라구조로 추가할 수 있음
• Suppression Execution Tool: 본 논문에서 제안된 방법을 수행하기 위해 저자가 개발한 Valgrind의 새 도구. 이 도구는 실행 가능한 프로그램, 메모리 실패를 야기하는 테스트 케이스, 실행 중 억제해야 할 인스트럭션 인스턴스의 집합(이를 ‘억제지점’이라 부름)을 입력으로 받아서 추적(tracing)과 억제(suppression)를 동시에 수행하면서 프로그램을 실행한다. 추적은 어떤 메모리 위치가 언제 액세스되는지 보기 위해 필요하고, 억제는 훼손된 메모리와 관련된 인스트럭션의 영향을 실행 중에 무효화 하기 위해 필요함
• Memory Bug Root Cause Isolator: 제안된 방법을 위한 메인 드라이버 모듈로 억제된 재실행을 관리하고 억제지점(suppression points)을 식별한다. 프로그램과 이 프로그램에서 메모리 관련 실패를 야기하는 테스트케이스가 주어지면 이 모듈은 먼저 빈(empty) 억제지점 셋을 이용해 Suppression Execution Tool을 호출한다. 이 테스트 케이스 실행에서 메모리 액세스 추적 정보를 기록하며, 이로부터 첫 번째 억제지점이 식별되면 이것이 두 번째 Suppression Execution Tool 호출의 입력 데이터로 사용된다.