[논문 리뷰] All You Ever Wanted to Know About Dynamic Taint Analysis and Forward Symbolic Execution / Part 1. Dynamic Taint Analysis

오늘은 보안 탑티어 학회들 중 하나인 S&P에 등재된 All You Ever Wanted to Know About Dynamic Taint Analysis and Forward Symbolic Execution 논문에 대해 리뷰해보도록 하겠다.

 

이 논문은 SoK 논문인데, SoK 란 Systemization of Knowledge의 약자로 기존에 소개된 기술을 보다 체계적으로 정리하는 논문 형식이라고 보면 된다.

 

해당 논문은 크게 두 개의 주제로 나누어져 있는데, 첫번째 파트는 Dynamic Taint Analysis에 대해서이고, 두번째 파트는 Forward Symbolic Execution에 대해서이다.

 

동적 분석 기법, Dynamic Analysis는 프로그램을 실행하면서 취약점을 분석하는 것이라고 보면 되는데, 이 동적 분석에 속하는 대표적인 기법 두 가지가 Dynamic Taint Analysis 와 Forward Symbolic Execution 이므로, 해당 논문에서는 이 두 가지 기법에 대해 자세히 설명하고 있다.

 

이 포스팅은 Dynamic Taint Analysis 에 초점을 둔다.

 

Dynamic Taint Analysis

 

기본적인 아이디어는 sources (오염원) 과 sinks (오염 지역) 사이의 information flow를 추적해보는 것이다.

 

오염원이란 말 그대로 오염이 어디서 왔는지? 를 생각해보면 된다. 대표적으로, 사용자 입력을 생각할 수 있다.

 

sinks는 해당 오염원으로부터 전파된 오염이 어디에 도착하는지를 떠올리면 된다.

 

프로그램을 동적으로 실행시켜보면서, 오염원으로부터 시작된 오염이 의도한 지역까지 도달하게 되는지를 지켜볼 수 있을 것이다.

 

Taint Policy 라는 용어가 나오는데, 이는 프로그램이 실행되면서, 오염이 어떻게 전파되고 흐르는 지를 결정하고, 어떠한 종류의 연산들이 새로운 오염을 만들어낼 수 있는지, 그리고 오염된 값들에 대해 어떠한 확인을 할 지도 정의한다.

 

크게 세 가지를 Taint Policy에서 정의한다.

 

1. Taint Introduction : 어떤 것을 오염의 시작 지점으로 볼 지? 어떤 것을 오염으로 볼 지를 정의한다.

 

2. Taint Propagation : 어떻게 오염이 전파될 지 정의하는 것

 

3. Taint Checking : 프로그램 실행 중 오염 대상을 발견했을 때, runtime behavior 에 대한 정의라고 보면 된다. 

 

논문에서 소개하는 가장 전형적인 오염 정책은 tainted jump policy 이다. 

 

해당 정책의 semantics를 일일이 설명하는 것보다 핵심만 추려서 설명하도록 하겠다.

 

tainted jump policy 

 

1. Taint Introduction : 사용자 입력을 오염된 것으로 정의한다.

 

2. Taint Propagation : 이항 연산에서 피연산자 중 하나라도 오염이 된 값이 있다면, 이항 연산의 결과 값도 오염되었다고 판단하는 식으로 전파한다. 이 외에도 여러 전파 semantics가 논문에 정의되어 있으나 생략하겠다.

 

3. Taint Check : goto y 라는 명령이 있다고 하자, y는 program counter 가 가리키는 주소가 될 것이다. y 라는 주소가 오염되었다면, 프로그램을 비정상적으로 종료시킨다. (오염을 encounter 했을 때 behavior 정의)

 

+ 포인터의 오염 상태와 해당 주소가 가리키는 객체(값)의 오염 상태는 독립적이다. 

 

=> 메모리 주소와 값의 오염 상태를 독립적으로 보았을 때 문제점은 사용자가 준 입력은 오염된 값이지만, 사용자의 입력이 function pointer table의 index로 사용되고, 만약 그 index에 해당하는 주소가 오염되지 않았으면, 공격자가 untainted 된 해당 주소로 실행 흐름을 바꿀 수 있다. 

 

table lookup 시나리오

 

이에 대한 해결책으로 다른 taint policy를 소개하고 있는데, 이는 tainted addresses policy 이다. 

 

이 정책에서는 메모리 셀이 메모리 주소 혹은 값 둘 중 하나라도 오염되어 있으면, 해당 메모리 셀을 오염됐다고 판단하는 정책이라고 보면 된다.

 

 

출처: https://users.ece.cmu.edu/~aavgerin/papers/Oakland10.pdf

 

 

앞서 소개한 taint jump policy 에서는 tainted value 정책을 사용하고 있었고, 바뀐 정책은 아래 정책을 사용한다.

 

tainted value 정책의 substitution을 보면, P mem 의 두번째 인자, 즉 t v의 오염 유무만 따지는데, 설령 값은 오염되었다고 해도 메모리 주소가 오염되지 않았으면, 오염되지 않았다고 판단할 수 있다. 

 

하지만, tainted addresses 정책은 메모리 주소 혹은 값 둘 중 어느 하나라도 오염되었다면, 해당 메모리 셀이 오염됐다고 판단하므로, 앞서 설명한 function pointer table의 index가 오염되어 있으므로, 해당 메모리 셀은 오염되었다고 판단되고, 따라서 function pointer로 실행 흐름을 바꾸지 못한다. 

 

Challenges

 

이러한 Dynamic Taint Policy에도 몇가지 해결해야 할 도전 과제들이 있다.

 

1. Tainted Address : 앞서 설명한 주소 오염에 대해 어떻게 처리할 것인지에 대한 문제이다.

 

2. Overtainting : 위양성이랑 비슷한 개념으로, 실제 오염되지 않은 값을 오염되었다고 판단하는 문제이다. 앞의 tainted addresses policy는 이러한 overtainting 문제를 겪을 수 있다. (아무래도 메모리 셀이 오염되었다고 판단하는 기준이 tainted value policy보다 훨씬 느슨하다(?). 주소 혹은 값 둘 중 하나라도 오염되었으면, 오염되었다고 판단하기 때문이다.)

 

3. Undertainting : 위음성이랑 비슷한 개념으로, 실제 오염된 값인데, 오염되지 않았다고 판단하는 문제이다. taint value policy 가 앞서 언급한 function pointer 시나리오에서 메모리 셀이 오염되지 않았다고 판단하는 것과 유사하다. (실제로는 오염되었는데)

 

4. Time of Detection vs. Time of Attack : Dynamic Taint Analysis가 오염된 값을 불안전한 방법으로 사용하려고 할 때 알려주는 플래그로 사용되는데, 여기서 문제는 program integrity가 이러한 오염된 값을 사용하기 전에 violated되지 않았다는 보장이 없다는 것이다.

 

예를 들어, 가장 잘 알려진 return address overwrite exploit을 생각해보자. 공격자가 return address를 자기가 미리 설정해놓은 쉘 코드의 주소로 덮어씌웠다고 하면, 문제는 tainted jump policy가 이러한 공격을 공격자가 주소를 덮어씌웠을 때 에러를 report하는 것이 아니라, 실제로 프로그램을 실행시켜서 해당 주소로 넘어가는 연산이 실행될 때 알려준다는 것이다. 따라서, 함수가 리턴 되기 전에 취약한 함수 안에서 일어나는 여러 가지 calls 들에 대해서는 어떻게 할 수가 없다. 만약 이러한 calls 들이 file manipulation 이나, networking function 들이었다면, 프로그램은 비정상적으로 종료되더라도 해당 영향은 지속해서 남아있을 수 있다. 

 

Control-flow taint 

 

프로그램의 information flow가 control dependencies에 의해서도 일어날 수 있다.

 

정의 : 프로그램의 어떤 statement s2 는 statement s1 에 대해서 control dependent 하다고 할 수 있는데, 이는 s1 가 s2가 실행될지 말지를 control 하고 있을 때이다. 

 

예시를 들어보면, y 에 1을 대입하는 명령은 2번째 if 문에 control-dependent 한데, 이는 2번째 라인이 y 대입 연산을 control 하고 있기 때문이다. 반면에, 4번째 라인은 2번째 라인에 control-dependent 하지 않다. 

 

하지만, 이러한 control-dependencies를 추론해낸다는 것은 여러 가지의 실행 경로를 고려해야 한다는 점에서 하나의 실행 흐름을 따라가는 동적 분석은 이를 계산해낼 수 없다.

 

대안으로는 동적 분석과 결합하여 알아내는 것이고, 휴리스틱(overtaint 할 것인지, undertaint 할 것인지 특정한 상황에 정하는) 을 사용하는 것이다. 

 

Sanitization

 

Dynamic Taint Analysis의 또 다른 중요한 문제인데, 오염은 더 추가되기만 하고, 지워지지는 않는다는 것이다.

 

이를 taint sanitization problem 이라고 한다.

 

예를 들어, b = a ^ a 라는 자기 자신에 대해 xor 한 값을 대입하는 것은 오염될 리가 없다. 왜냐면, 값은 항상 0 을 반환할 것이기 때문에 이는 zero out 할 수 있는 것이다. (taint jump policy 의 규칙들에 의하면, a가 오염되었으니 당연히 이항 연산의 결과 값도 오염되었다고 판단했을 것인데 말이다.)

 

이와 같은 constant function을 사용할 때 우리는 sanitize 할 수 있다.

 

또 다른 예시로, hash function이 있다.

 

공격자가 암호학적으로 안전한 해시 함수에 공격자의 사용자 입력을 넣었다고 해도, 공격자가 원하는 값을 반환하도록 하는 것은 매우 어려운 일이다. 따라서, 해시 함수의 결과 값은 untainted 되었다고 sanitize 할 수 있는 것이다.

 

 

---

 

간략히 동적 오염 분석에 대해 리뷰해봤는데, 한 포스팅에 모든 내용을 담기는 양이 너무 방대해 최대한 요약하여 정리했다. 추후에 reference 용도로 적절할 정도로 정리한 것으로, 나중에 부족하다 싶으면 추가할 것이다.

 

 

 

Reference:

https://users.ece.cmu.edu/~aavgerin/papers/Oakland10.pdf

 

※ Any feedbacks and corrections are welcome. Feel free to comment down below.