[lab intern] AddressSanitizer Paper Review

저번주에 읽었던 "SoK: Santizing for Security" 논문은 지금껏 연구됐던 세니타이저들에 대한 리뷰 논문이었다. 이 논문에서 상용화된 기술로 가장 많이 언급되는 새니타이저가 AddressSanitizer(이하 ASan)이다. 그래서 이 도구의 구체적인 부분이 궁금해져 ASan 논문을 찾아 읽게 되었다.

ASan 알고리즘 및 구현을 위주로 정리하였다.

Introduction

"coverage와 performance는 trade-off 하다"

이전까지 연구됐던 모든 새니터이저들이 직면했던 문제이다. 즉, 높은 커버지리를 보이는 새니타이저는 느리고, 반대로 빠른 새니타이저는 커버지리가 빈약하다. 그래서 이러한 트레이드오프를 극복하고자 나온 새로운 새니타이저가 ASan이다.

ASan의 가장 기본적인 아이디어는 레드존 삽입(red-zone insertion)이다. 할당된 메모리 영역 앞, 뒤의 일정한 크기의 레드존을 삽입하여, 접근 가능한 영역과 불가능한 영역을 구분한다.

한편으론, UAF(use-after-free) 버그를 감지하기 위해 메모리가 해제된 힙 영역의 재사용을 연기(delay)하는 기법을 사용한다.

Algorithm

ASan은 구현에 있어 2가지 파트로 나뉜다. 하나는 계측(insrumentation)이고 나머지는 특별한 할당자(spetial allocator)이다.

1. 계측 (instrumentation)

기본적으로 계측은 쉐도우 메모리(shadow memory)에 저장된 메타데이터를 기반으로 작동한다. 그렇다면 2가지 측면을 생각해야 하는데, 하나는 메타데이에 어떤 데이터를 저장하고 매핑할 것인가 이고, 나머지 하나는 매핑한 데이터로 어떻게 메모리 에러를 계측할 것인가 이다.

설명하기 앞서, ASan은 모든 메모리 할당 및 접근이 8바이트 기반(8 bytes align)으로 이뤄지다고 가정한다. 실제 보통의 경우 거의 8바이트 기반으로 일어난다.

먼저, 메타데이터의 저장할 데이터는 몇 바이트가 접근가능한(addressable) 영역이냐이다. 예를 들어 8 바이트 중 앞의 5바이트가 접근 가능하면 '5'를 저장한다. 즉, 8바이트 당 쉐도우메모리에 들어갈 수 있는 데이터의 경우는 9가지(0~8)이므로 1바이트면 충분하다. 8바이트당 1바이트로 매핑되므로, 아래 식 처럼 표현할 수 있다.

ShadowAddr = (Addr >> 3) + Offset

오프셋(offset)의 경우, 하드웨어의 따라 정적으로 결정된다.

메모리 접근이 발생할때마다, 매핑된 쉐도우메모리의 값을 읽어와 메모리 에러를 탐지하면된다.

8바이트 기반으로 읽었다고 했을때는 읽은 부분 중 1바이트라도 접근 불가능한 영역이라면 에러를 탐지한 것이다. 코드로 보면 아래와 같다.

ShadowAddr = (Addr >> 3) + Offset;
if (*ShadowAddr != 0) { /* report error! */ }

만약에 1,2,4바이트 기반으로 접근할 경우, 조금 복잡해지지만 큰 문제는 없다. 먼저 위와 마찬가지로 쉐도우 메모리의 값을 확인 후, 0보다 크면 접근한 메모리의 영역이 접근 불가능한 영역을 포함하는지 검사한다.

ShadowAddr = (Addr >> 3) + Offset;
k = *ShadowAddr
if (k != 0 && (Addr & 0b111) + AccessSize > k) {
	/* reports error! */
}

예외를 보고하는 방식은 한번만 보고해야 하므로 하드웨어 예외(hardware exception) 같은 방식이 합리적이다.

c.f. in case of no 8-align

만약에 8의 배수 기반이 아닌 경우, 어떻게 될까? 이 경우 ASan은 감지하지 못한다. 이는 여전히 존재하는 성능과 정확도 사이의 트레이드-오프 상황에서 정확도를 포기하고 성능을 선택했기 때문이다. 만약에 8-Align 하지 않는 경우를 모두 탐지하기 위해서는 추가적인 작업이 너무 많이 요구돼 성능을 급격히 떨어뜨린다.

2. Spetial Allocator

런타임 라이브러리를 구현하여, 기존의 'molloc', 'free'를 새로운 특별한 할당자로 변환해야 한다. 이 특별한 할당자는 기존의 할당자가 반환한 영역을 둘러싸는 레드존(red-zone)을 추가로 할당한다. 이 영역은 접근 불가능(unaddressable)한 영역으로 접근 시, 예외를 발생시킨다.

위쪽(혹은 왼쪽) 레드존에는 할당자의 내부 데이터(할당 크기, 스레드 아이디 등)을 저장한다. 이를 언더플로우(underflow)에 의해 손상될 수 있을 것 같지만, 언더플로우는 이미 런타인 계측(instrumentation)에 의해 탐지되므로 그러한 우려는 없다. 레드존의 이러한 값을 저장하기 위해서는 최소 32바이트의 레드존 크기가 요구된다.

"free"가 호출되면 메모리가 해제된 영역 전체를 접근 불가능한 영역으로 하기 위해 쿼런틴(qurantine; 격리소)에 넣어버린다. 쿼런틴은 크기가 고정된 FIFO로 구현되어, 가장 최근에 해제된 순서대로 메모리 영역을 저장한다. 쿼런틴에 소속된 메모리 영역은 할당자(malloc)에 의해 할당될 수 없다.

Implementation Red-Zone

Original Code

void foo() {
    char a[10];
    <function body>
}

Optimized by ASan(LLVM Pass)

void foo() {
    char rz1[32];
    char arr[10];
    char rz2[32-10+32];
    
    unsigned *shadow = (unsigned*) ((long)rz1 >> 8 + Offset);
    shadow[0] = 0xffffffff;	// rz1
    shadow[1] = 0xffff0200;	// arr and rz2;
    shadow[2] = 0xffffffff; 	// rz2;
    
    <function body>
    
    shadow[0] = shadow[1] = shadow[2] = 0;
}

기본적은 레드존은 32바이트이지만, 할당 받은 a의 크기가 10바이트이므로 8-align에 맞게 패딩을 해주기 위해, rz2는 32바이트보다 크게 할당받게 된다.

그리고 8-Align마다 접근 가능한 바이트 수 만큼을 값으로 저장한다. 그림으로 보면 아래와 같다.

글로벌(global)로 할당 받은 경우는 컴파일 타임에 생성을 하고, 스택에 할당 받은 경우는 런타임에 생성한다.

False Negative

ASan을 할당된 영역의 둘러싸는 "일부" 영역만을 접근 불가능한 영역으로 탐지하므로, 특정한 경우 실제 메모리 오버플로우(또는 언더플로우)임에도 불구하고 감지하지 못한다.

가장 흔한 경우는, 할당받은 메모리 영역으로 부터 아주 먼 영역으로 접근하여, 우연히 다른 객체가 할당받은 영역에 침범하는 것이다. 이는 명백한 에러이지만, ASan은 해당 영역을 접근 가능한 영역으로 판단하므로, 예외를 감지하지 못한다.

또한 레드존은 삽입하는 것만으로는 UAF(use-after-free)를 감지할 수는 없다.

False Positive

기본적으로 ASan은 거짓 양성(False Positive)이 존재 하지 않는다. 하지만 다른 최적화기(Optimizer)와의 상호작용 과정이나, 특이한 프로세스 환경에 의해 거짓 양성이 발생할 수 있다. 이러한 경우, 해당 최적화기를 ASan과 함께 사용할 수 없도록 하거나, 또는 일정한 태그를 집어넣어 특정한 경우, ASan이 작동하지 않을 수 있도록 할 수 있다. 하지만 이러한 경우는 매우 특이한 상황으로 빈번하게 일어나는 일은 아니다.

Evaluation 파트는 생략.

(Memroy usage는 3.74, 속도의 경우 73%의 저하로 기존의 방식에 비해 매우 좋다~)

Future Work

1. Compile-time Optimization

기존의 ASan은 모든 메모리 읽기/쓰기에 대해서 테스트를 하게 되는데, 이 중에서는 경우에 따라 불필요한 검증이 매우 많다. 그러므로 불필요한 탐지를 제거하여 Compile-Time Instrumentation을 최적화할 필요성이 있다.

2. 외부 라이브러리를 다루는 문제

현재의 ASan은 컴파일 타임 계측을 기반으로 하기 때문에 시스템 라이브러리에 적용하기 어렵다. 오픈 소스 라이브러리의 경우 특별한 빌드시스템을 쓰면되지만 이 역시, 클로즈드 소스 라이브러리에는 적용하기 어렵다. 이 경우에는 계측과 함깨 바이러니 코드 해석 시스템(binary translation system)을 함께 사용하면 되지만, 이는 엄청난 속도저하를 일으켜 근본적인 해결책은 아니다.

3. 하드웨어 서포트

보관함