Taint Analysis
오염 분석(taint analysis)이란 프로그램의 메모리에 오염(taint)이라는 특정 값을 삽입한 후, 이 데이터를 추적하여 그 값이 프로그램의 어느 위치에서 영향을 미치는지 관찰하는 것이다.
예를 들어 어떤 작업이 오염된 객체 X의 값을 사용해 다른 객체 Y에 대한 값을 파생하는 경우 Y가 오염되며, 객체 X가 객체 Y를 오염시켰다고 말한다.
정적 오염 분석(STA, Static Taint Analysis)은 동적 분석보다 코드 커버리지가 높다는 장점이 있다.
반면 동적 분석에 비해 정확하지 않다. 예를 들어 런타임 정보에 접근 할 수 없으므로 특정 시점에서 레지스터나 메모리 값을 검색할 수 없다. 게다가 소스 코드가 제공되어야만 사용 가능하다.
Dynamic Taint Analysis
동적 오염 분석(DTA, Dynamic Taint Analysis)은 종종 데이터 흐름 추적(DFT, Data Flow Tracking)으로도 불리고, 그냥 오염 추적(taint tracking)이나 오염 분석(taint analysis)으로도 불린다.
DTA는 프로그램 내의 특정 상태의 어떤 부분이 다른 프로그램 상태의 어떤 부분에 영향을 미치는지 확인할 수 있는 프로그램 분석 기법이다. 예를 들어 네트워크를 통해 수신한 데이터를 오염시킨 후 그 흐름을 추적하다가 PC(Program Counter)가 변조되는 것을 감지할 수 있다.
바이너리 분석 관점에서 DTA는 동적 바이너리 계측 플랫폼의 최상단에 구현된다.
데이터의 흐름을 추적하기 위해 해당 데이터가 메모리나 레지스터상에서 처리되도록 하는 모든 명령어를 계측한다. 이 때문에 계측 대상 프로그램에서 10배 이상의 성능 저하가 발생한다.
DTA는 프로그램의 버그를 찾거나, 데이터 유출을 방지하거나, 자동으로 코드를 최적화하거나, 디지털 포렌식을 수행하거나 하는 등 다양한 분야에서 활용할 수 있다. 이러한 각 분야에서 표시가 필요한 특이한 값을 '오염된 값'이라고 생각하면 된다. 이후 본 글에서 단순히 특정 값이 오염됐다고 말하는 것은 '공격자가 해당 값을 악용할 수 있다'라는 것으로 보겠다.
DTA in Three Steps
오염 분석은 오염원(taint source)을 정의하고, 오염 지역(taint sink)을 정의한 뒤, 오염 전파(propagation)를 추적하는 순서로 진행된다.
DTA 기반의 도구를 직접 구현할 것이라면 오염원과 오염 지역 정의만 하면 된다. 보통 오염 전파 추적은 libdft 등의 DTA 라이브러리가 지원해 주며, 세부 사항을 수정할 수 있도록 지원해 주기도 한다.
Defining Taint Sources
오염원(taint source)이란 추적하려는 특정 데이터의 프로그램 내 위치(program location)다.
예를 들어 시스템 콜, 함수 엔트리 포인트, 개별 명령어들 등을 오염원으로 설정할 수 있다.
오염원으로 설정하고 추적하려는 데이터에 따라 DTA 도구를 사용해 얻을 수 있는 결과물이 달라진다.
DTA 라이브러리에서 제공하는 API를 호출해 관찰하려는 데이터에 어떤 표기를 함으로써 오염시킬 수 있다. 이러한 API 호출은 레지스터나 메모리 주소를 오염을 나타내는 입력값으로 사용한다.
예를 들어 네트워크를 통해 수신하는 데이터를 추적해 공격인지 추정하기 위해 recv나 recvfrom 등 네트워크 관련 시스템 콜을 계측하는 상황을 고려해보자. 동적 계측 플랫폼에서 이런 종류의 시스템 콜마다 콜백 함수를 호출하는 방식을 사용한다. 이때 콜백 함수 내에서 수신한 데이터를 읽고 오염된 것으로 명시하는데, 이 경우 recv 및 recvfrom 함수가 오염원이다.
Defining Taint Sinks
오염 지역(taint sink)이란 오염된 데이터로부터 영향을 받았는지 확인하려는 프로그램 내의 위치(program location)다.
예를 들어 제어 흐름 탈취 공격을 탐지하기 위해 간접 호출, 간접 점프, return 명령어에 콜백 함수를 사용해 계측을 하는 상황을 고려해보자. 콜백 함수는 이러한 명령어들의 목적지 주소가 오염된 데이터의 영향을 받았는지를 살피면 되는데, 이때 대상 계측 명령어들이 오염 지역이다.
Tracking Taint Propagation
오염된 데이터는 오염원으로부터 시작해서 오염 지역을 향해 전파(propagation)된다.
오염된 데이터를 추적하려면 해당 데이터를 처리하는 모든 명령어를 계측해야 하므로 굉장히 복잡하다. 예를 들어, mov 명령어의 피연산자가 오염됐다고 할 때 계측 코드에서 그 명령어의 결과값도 오염됐다고 표기해야 한다. 하지만 연산자의 출력인 피연산자를 결정하는 것이 쉽지 않다.
오염 전파는 입력값 피연산자와 출력값 피연산자 사이의 오염 관계를 정의하는 오염 정책(taint policy)의 영향을 받는다.
DTA Design Factors
Taint Granularity
오염 단위(taint granularity)는 오염된 대상 정보에 대한 단위다.
단위를 비트로 설정했다면 메모리나 레지스터 내의 비트들이 오염됐는지로 판가름하겠다는 것이다. 바이트나 워드(word) 단위의 시스템의 경우 단 1비트라도 오염됐다면 해당 정보 전체가 오염된 것으로 간주한다.
비트 단위와 바이트 단위의 DTA 시스템의 예제를 살펴보자.
오염 전파는 AND 연산을 통해 이뤄지며, 1바이트 크기의 2개의 피연산자에 대해 AND가 수행되는 상황이다. 이때 하나의 피연산자(왼쪽)가 오염되었다. 즉 공격자가 왼쪽 피연산자를 조작할 수 있는 상황이다.
한 칸이 한 비트를 의미하고, 회색으로 표시된 부분이 오염된 부분이다. 이때 연산의 결과인 오른쪽을 보면서 오염 전파에 고려해보자.
두 번째 피연산자 중 한 비트가 1이고, 공격자는 이 비트만을 조작할 수 있다(오염된 피연산자의 같은 위치를 0 또는 1로 바꿔서 조작할 수 있다). 이는 오염되지 않은 두 번째 피연산자가 오염된 첫 번째 피연산자에 대해 필터링 역할을 했다고 볼 수 있다.
이번에는 바이트 단위의 DTA에서 동일한 상황을 고려해보자.
앞서 말했듯이 바이트 단위의 시스템에서는 단 한 비트라도 오염된다면 그 단위 전체(바이트)가 오염되었다고 판단한다. 따라서 공격자는 결과값에 영향을 미칠 수 있다.
이를 통해 알 수 있듯이 오염 단위는 정확도(accuracy)와 밀접한 관련이 있다.
비트 단위의 DTA 시스템은 입력값에 따라 정확도 측면에서는 뛰어나지만, 계측 코드가 매우 복잡하고 성능 측면에서도 부하를 유발할 것이다.
바이트 단위의 DTA 시스템은 오염 전파 규칙을 정의할 때 간단한 계측 코드만으로 구현할 수 있다. 대부분의 DTA 시스템은 바이트 단위를 채택해 정확성과 속도 사이에서 합리적인 결정을 내린다.
Taint Colors
지금까지는 오염되었는지 오염되지 않았는지 둘 중 하나로만 판단했다. 하지만 단순히 오염 여부뿐만 아니라 오염이 어디에서 시작된 것인지 추적하고 싶을 수도 있다. 이를 위해 오염원을 서로 다른 색깔(color)로 구분해서 추후 오염 지역에서 비교할 수 있다.
byte-granular DTA 시스템에서 오염 색깔을 하나만 사용할 것이라면 하나의 비트만으로 충분하다. 만약 둘 이상의 오염 색깔을 사용할 것이라면 바이트 내부에 더 많은 정보를 담을 수 있어야 한다.
예를 들어, 1바이트의 오염 정보를 사용하려면 8개의 오염 색깔을 사용할 수 있다. 1바이트인데 어째서 255개가 아닌지 궁금할 수도 있다. 1바이트 내에서 255개의 색을 사용할 경우 오염 색깔이 섞였을 때 이를 구분할 수 없다. 즉 한 데이터가 두 개 이상의 오염원에 의해 오염된 경우 그 결과값의 오염 정보에 오염 색깔을 구분해 표시할 수가 없다.
따라서 비트 자릿수마다 한 가지의 색상만을 지정해 줘야 한다. 예를 들어 1바이트 단위라면 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 총 8개의 오염 색깔을 사용할 수 있다. 만약 이 경우 0x01과 0x02 색깔에 의해 OR 비트 연산이라는 영향을 동시에 받았다면 0x03으로 두 정보가 모두 남아있게 된다.
Taint Propagation Policies
오염 정책(taint policy)이란 DTA 시스템에서의 오염 전파 과정을 설정하고, 중첩된 오염이 발생한 경우 색깔을 어떻게 병합해 표기할지를 결정하는 정책이다.
다음은 바이트 단위 DTA 시스템에서 오염 색깔인 빨강(R)과 파랑(B)에 대해 몇 가지 오염 전파 동작 연산과정을 나타내는 예시다. 참고로 이외에도 선형 변환이 아니라 더 복잡하게 연산 과정을 정의할 수도 있다.
- Taint Propagation Examples for a Byte-Granularity DTA System with Two Colors, Red (R) and Blue (B)
- ➊: 할당 연산. 변수 c에 변수 a의 값이 할당되는 경우다.
- ➋: XOR 연산. 로 표기한다. 이 경우 입력 피연산자들끼리 바이트 단위의 합집합() 연산을 수행하는 오염 정책을 사용할 수 있다. (위 그림에서 빨강과 파랑이 섞인 RB)
- ➌: 덧셈 연산. XOR 연산과 동일한 방식의 합집합 연산 정책을 적용할 수 있다. 다만 오버플로가 발생할 수 있는데, 이런 경우 주변에 있던 다른 바이트의 LSB(Least Siginficant Bit)를 훼손할 수도 있다. 공격자가 LSB를 조작하기 위해 값을 조작할 수도 있으니 주의해야 한다.
- ➍ 동일한 값에 대한 XOR 연산. 와 같은 연산을 수행하면 그 결과는 항상 0이다. 이 경우 공격자가 a 값을 조작하더라도 c에 영향을 줄 수 없다. 따라서 오염 정책은 결과값 바이트를 모두 초기화해야 하며, 이때 공집합() 연산을 수행한다.
- ➎ 상수만큼 left shift 연산. 로 표기한다. 두 번째 피연산자가 상수이므로 공격자는 a를 적절히 조절할 수는 있지만 결과값의 모든 바이트를 조작할 수는 없다. 이 경우 오염 정책은 입력 바이트에 의해 영향을 받는 결과값의 바이트를 오염 전파로 설정한다. 이 예시에서는 a의 하위 바이트만 오염되어 있고 6비트만 왼쪽으로 시프트되므로 하위 두 바이트에 오염이 전파되었다.
- ➏ 변수만큼 left shift 연산. 상수 대신 변수 b 값만큼 시프트를 연산을 수행한다. 이 경우 결과값의 모든 바이트에 영향을 미칠 수 있다.
DTA 라이브러리는 사전 정의된 오염 정책을 제공한다. 하지만 기본 정책이 적절하지 않은 경우 수정해야 한다. 예를 들어 정보 유출만을 탐지하려 한다면 인식의 범위를 벗어나는 데이터 변경 명령어에 대한 오염 전파는 비활성화해 성능을 높일 수 있다.
Overtainting and Undertainting
과잉 오염(overtainting)은 오염이 발생하지 않았는데 오염이 발생했다고 오탐(false positive)하는 경우를 말한다.
과소 오염(undertainting)이란 오염이 발생했지만 이름 탐지하지 못한 경우를 말한다. 지원되지 않은 명령어에 대해 오염 전파 처리 기능이 없는 경우에도 발생할 수 있다. 예를 들어, libdft는 x86의 MMX나 SSE 명령어에 대한 지원을 할 수 없어서 추적에 실패할 수 있다.
과잉/과소 오염은 오염 정책이 적절하게 설정되어 있지 않거나 제어 의존성(control dependency) 문제로 인해 발생한다.
현재의 DTA 시스템이 과잉/과소 오염에 대한 정확성을 높이면서도 그로 인한 성능 손실을 줄이기 위해 노력 중이나, 합리적인 대안을 찾는 것의 거의 불가능하다.
Control Dependencies
오염 추적(taint tracking)은 데이터 흐름(data flow)을 추적하는 것과 같다.
하지만 데이터 흐름은 암시적으로 제어 흐름의 구조에 영향을 받을 수밖에 없는데, 이를 보통 암시적 흐름(implicit flow)이라고 한다.
암시적 흐름에 대한 간단한 예시를 살펴보자.
var = 0;
while(cond--) var++;위 코드에서 공격자가 cond라는 값을 변경하면 결과값인 var에 영향을 미치게 된다. 공격자가 cond 변수를 이용해 var 값을 변조했음에도 두 변수 간의 묵시적인 데이터 흐름이 발생하지 않았다.
이런 경우를 제어 의존성(control dependency)이라고 한다.
DTA 시스템은 묵시적 데이터 흐름만을 추적할 수 있으므로 cond가 오염되었어도 var 값은 오염되지 않았다고 판단하는 과소 오염 문제가 발생한다.
이런 문제를 해결하기 위해 분기나 반복문 조건에서 발생하는 오염을 이후 관련 명령어들에도 전파하는 방식의 연구가 등장했다. 하지만 이는 오염된 조건 분기가 일반적으로 많이 발생하기 때문에 수많은 과잉 오염 문제를 유발하게 된다.
예를 들어 다음과 같은 경우를 생각해 보자.
if(is_safe(user_inpu)) funcptr = safe_handler;
else funcptr = error_handler;user_input에 대해 오염 분석을 수행할 경우 이 오염은 is_safe 함수의 결과값에 오염을 전파하고, 이 결과값은 조건 분기문에 사용된다. 따라서 funcptr의 결과값은 항상 오염된 것으로 판단될 것이다.
사용자 입력에 대해 조건 분기가 발생하는 상황은 자주 발생하지만 공격자가 암시적 흐름을 조작하는 상황은 드물기 때문에 대부분의 DTA 시스템은 제어 종속성에 대한 추적을 포기한다.
Shadow Memory
레지스터나 메모리 내에 어떤 부분이 어떤 색으로 오염되었는지 기록하기 위한 섀도 메모리(shadow memory)가 필요하다. 섀도 메모리란 대상 프로그램이 사용하는 메모리 공간의 오염 정보를 기록하고 추적하는 특수 목적의 메모리 공간이다. DTA 시스템은 일반적으로 레지스터의 오염 정보를 추적하기 위한 별도의 메모리 공간도 관리한다.
섀도 메모리의 구조는 오염 단위나 오염 색깔의 종류에 따라 다르다.
- Shadow memory with byte-granularity and 1, 8, or 32 colors per byte
왼쪽은 DTA를 사용했을 때의 가상 메모리 영역으로 4개의 메모리 바이트가 A, B, C, D 공간에 담겨있다. 공통적으로 A, B, D는 오염되어 있고, C는 오염되지 않았다.
오른쪽은 세 종류의 섀도 메모리 상황을 각각 나타내고 있고, 오염 정보가 A부터 D까지 어떻게 인코딩 되어있는지 보여준다.
Bitmap-Based Shadow Memory
먼저 비트맵(bitmap) 방식은 바이트 당 하나의 오염 정보를 기록할 비트를 저장하는 방식이다➊.
이 경우 오염 색깔은 단 한 가지이며, 각 메모리 바이트의 오염 여부만을 표현할 수 있다. 오염 비트는 1101로 표기한다.
비트맵 방식을 사용하면 오염 정보는 다양하지 않지만 메모리 공간을 절약할 수 있다. 하지만 64비트 시스템은 가상 메모리 공간에 대한 제약이 거의 없으므로 이런 장점이 큰 의미가 없다.
Multicolor Shadow Memory
두 번째는 가상 메모리의 각 바이트에 대해 1 바이트의 섀도 메모리를 사용하며 8개의 오염 색깔을 지원하는 경우다➋.
다수의 오염 색깔(multicolor)을 사용하려는 섀도 메모리를 구현할 때 더욱 복잡한 방식을 사용해야 한다. 이번에는 오염 색깔이 각각 0x01, 0x02, 0x20이다.
최적화를 수행하지 않는다면 프로세스의 모든 가상 메모리를 8개의 오염 색깔로 오염 내용을 저장하기 위해 섀도 메모리가 가상 메모리의 절반을 차지하게 된다.
이를 해결하기 위해 실제로 사용 중인 스택이나 힙과 같은 영역만 섀도 메모리를 동적으로 할당할 수 있다. 또한 쓰기 불가능한 영역은 오염될 수 없으므로 zeroed-out 섀도 메모리 페이지에 매핑하기도 한다.
세 번째는 메모리 바이트당 4바이트의 섀도 메모리를 사용하고, 32가지의 오염 색깔을 지원하는 구성이다➌. 오염 색깔은 각각 0x01000000, 0x00800000, 0x00000200이다.
섀도 메모리를 바이트 배열이나 정수형 배열로 구성할 수도 있다. 또는 임의의 오염 색깔 종류의 수를 사용하기 위해 복잡한 자료 구조를 사용하는 방법도 있다. 예를 들어 C++의 set을 이용해 각 오염 색깔을 저장하기 위한 섀도 메모리를 만들 수 있다. 하지만 이는 DTA 시스템의 복잡도와 실행 시 과부하를 크게 증가시킨다.
참고 및 인용
[1] https://practicalbinaryanalysis.com/
[2] http://www.acornpub.co.kr/book/binary-analysis
[3] https://hexterisk.github.io/blog/posts/
Uploaded by Notion2Tistory v1.1.0