Address Sanitizer과 그 원리

Address Sanitizer이란?

메모리 코럽션과 이를 디버깅하는 것은 아주 오래전부터 개발자들의 숙명이었습니다. 그렇기에 이에 대한 여러 방법론들이 나오게 되었고, 그것들 중 잘 만들어진 예 중 하나가 바로 ASAN이 되겠습니다. 예전부터 이 주제에 대해서 쓰고 싶었는데, 시간이 없어서 계속 미루다가 이제서야 정리하네요.

아무튼... Address Sanitizer은 직역하면 “주소 소독제" 입니다. ...직역하면 별 의미가 없는 단어네요. 아무튼 잘못된 메모리 주소로의 접근 및 쓰기를 검출하는 것을 도와주는 도구입니다.

다만 이 도구는 valgrind와 같이 런타임에 binding하는 도구와는 달리, 컴파일 타임에 붙어 추가적인 코드를 삽입해주는 도구입니다.

gcc에서는 -fsanitizer=address 옵션을 주어서 쉽게 사용할 수 있습니다.

• -fsantizier=address : 런타임 시 메모리 참조를 검사하는 코드를 추가함. 계측되는 범위는 stack, malloc, code 등 다양합니다. C 최적화 수준과 상관없이 동작합니다. (-O3 과도 호환 가능)
• -fsanitizer=fuzzer : LibFuzzer을 포함하여 Fuzzing합니다.

Fuzzing은 또 뭐야?

무작위 값을 넣어서 함수의 취약점을 찾아주는 작업을 의미한다. 사용법도 간단하다.

extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
  DoSomethingWithData(Data, Size);
  return 0;
}

이런 식으로 특정 함수를 외부로 노출시켜주면, -fsanitize=address,fuzzer 포함하고 컴파일 시 알아서 fuzzing 작업이 수행되고, 문제가 발생 시 address sanitizer이 작동된다.

여기서 쓸 내용은 아니라서 깊이있게 다루지는 않고, 자세한 내용은 여기 참조.

간단한 예시

메모리를 침범하는 아주 간단한 프로그램을 만들어서 확인해 보았습니다.

#include <stdio.h>

static void letsmakebug(volatile int *arr, int limit) {
    for (int i = 0; i < limit; ++i) arr[i] = i;
}

int main(int, char**) {
    volatile int a, b[100], buf[100], *c, i;
    c = &a;
    a = 100;
    printf("Lets make memory dirty >:)\n");
    letsmakebug(b, 200);
    printf("Addr is: 0x%X\n", c);   // expected to print valid memory addr
    printf("Val is: %d\n", *c);     // expected to print '100'
    return 0;
}

실험을 위해 이 프로그램에서의 스택 메모리 구조를 강제시켰는데, volatile 때문에 강제로 a / b[100] / buf[100] / *c / i 형태로 고정이 되어 있도록 했습니다.

프로그램 자체는 프로시저 letsmakebug 가 변수 b부터 의도치 않은 buf 변수 지역까지 싹 밀어버리는 구조로 되어 있습니다. b ~ b+200 까지 값을 쓰도록 하면, stack rewinding 도중에서야 값이 잘못 덮어씌워진 것을 확인하고 프로그램이 멈추게 됩니다. 즉 값을 덮어씌우는 시점에 프로그램이 멈추지는 않습니다. (그마저도 최적화 상황에 따라서는 한참 나중에 프로그램이 멈출 수도 있고요)

address sanitizer을 사용하면 잘못된 지역에 값을 덮어씌우는 시점에 바로 프로그램이 멈추면서 추가로 디버그 정보까지 보여줍니다.

콜스택과 함께 접근하려는 메모리 주소, 그리고 메모리 덤프에서 근방의 stack guard(shadow bytes)들이 보입니다.

“Read Violation까지도 잡아내는 정도의 능력”

그런데 정말 대단하다고 느낀 점은, read violation까지도 catch 해낸다는 점입니다. 코드를 아래와 같이 조금 수정하고 돌리면...

#include <stdio.h>

static void letsmakebug2(volatile int *arr, int limit) {
    int c = 0;
    for (int i = 0; i < limit; ++i) c += arr[i];
    printf("%d\n", c);
}

int main(int, char**) {
    volatile int a, b[100], buf[100], *c;
    c = &a;
    a = 100;
    for (int i =0; i < 100; ++i) b[i] = 1;
    for (int i =0; i < 100; ++i) buf[i] = 1;
    printf("Lets make memory dirty >:)\n");
    letsmakebug2(b, 200);
    printf("Addr is: 0x%X\n", c);   // expected to print valid memory addr
    printf("Val is: %d\n", *c);     // expected to print '100'
    return 0;
}

중간에 stack guard가 더해져서 이상한 값이 나오게 됩니다. 더더군다나 런타임 상에서는 오류가 검출되지 않습니다. 이렇게 변질된 값은 보통 한참 뒤에 프로그램을 터뜨려서 개발자 복창도 같이 터뜨리는 상황을 유발하곤 하죠...

하지만 sanitizer에서는 바로 잡힙니다.

보다 자세한 원리

이쯤되니 실제로 어떻게 어셈블리가 만들어지는지가 궁금해졌습니다. 친절하게도 논문에서는 이에 대해서 상세히 설명해 주고 있는데, 아래와 같이 shadow byte를 그대로 compare한다고 씌여 있습니다. 뭐 실제로 그럴 것이겠고, 이러더라도 local cache나 branch prediction 등 덕분에 성능 하락이 그렇게 크지는 않을겁니다.

실제로 만들어진 코드를 보면 뭔가 덕지덕지 많이 붙어있습니다. 하지만 제가 잘 몰라서 구체적으로 어떤 방식으로 오류가 발생하게 되는지는 이것만으로는 알기 힘드네요 😅 JMP(B, BL)에 해당되는 눈에 띄는 코드는 그렇게 많이 보이지 않으나 SUBS와 같은 특수 명령어들이 눈에 띕니다. 아마 0x5e8 이 검사 로직이 아닐까...

그리고 ASAN 보면서 가장 감탄했던 점 중 하나가 바로 memory align을 적극 이용하고 있다는 것입니다. 일반적으로 컴퓨터는 8byte align된 메모리 주소만을 사용하도록 되어있고 그렇지 않을 경우 SIGNAL이 발생하게 되는데, (아주 간단하게 설명하면) Shadow memory를 참조하려고 할 경우 unaddressable memory를 참조하게 되어 바로 문제를 탐지할 수 있다는 내용입니다.

하지만, ASAN도 만능은 아닙니다. 논문의 False Negatives에도 나와 있지만, 특정 패턴의 경우에는 잡아낼 수 없습니다. 이런 식으로 메모리를 확 건너 뛴다던가 ...

성능에 미치는 영향

값을 쓸 때마다 일종의 hook이 걸리는 것이기 때문에 성능이 월등히 느릴 수밖에 없습니다. 그래도 비슷한 메모리 분석 툴인 valgrind를 붙이는 것보다는 훨씬 낫습니다. 컴파일 시에 코드를 삽입하는 구조라서 그나마 낫다는 정도...

...라지만 실제로 얼마나 영향을 끼치는지 궁금해지기 때문에 바로 테스트를 해 봤습니다. 가장 간단하고 무식하게 메모리 주소에 값을 계속 쓰도록 하는 코드를 만들고 돌려봤습니다. 아무래도 메모리 접근 횟수가 많다 보니 성능 차이를 가장 적나라하게 볼 수 있을 거라는 생각을 했습니다.

#include <stdio.h>
#include <time.h>
#define ARRSIZE 10000000

volatile int asdf[ARRSIZE];

int main(int, char**) {
    clock_t t = clock();
    for (int k = 0; k < 10; ++k)
        for (int i = 0; i < ARRSIZE; ++i) asdf[i] = i;
    t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC;
    printf("Elapsed time: %lf\n", time_taken);
    return 0;
}

정말로 차이가 별로 없네요. 매 연산마다 체크를 수행함에도 불구하고 성능 하락이 적은 이유라면 아마 branch prediction의 이유도 있을 거라고 생각이 되지만, 설령 그러더라도 이 정도 차이밖에 나지 않는건 정말 대단하다는 생각이 듭니다.

논문에서도 실험한 자료가 있어서 들고와 보았는데, READ ONLY의 경우에는 위에서 직접 실험한 것과 비슷한 수준의 slowdown이 나타난다고 되어 있습니다. 그런데 write 포함이면 좀 느리네요... 뭐 보통은 read를 많이 하니까 이 정도는 감안 가능할지도?

또 그리고 메모리 소모량도 확인해 볼 필요가 있습니다. 논문을 보면, 바이너리 따라 다르지만 평균 3배 증가한다고 되어 있습니다. 피치 못할 상황으로 해당 알고리즘을 프로덕션에 올려야 할 경우라면 여전히 심사숙고가 필요하겠네요...

그 이외 잡소리...

• 당연한 이야기지만, 혹여라도 custom allocator을 쓰고 있다면 이 기능의 특혜를 맛볼 수 없습니다. 뭐 보통은 allocator을 커스텀 할거면 기본 allocator을 사용할 정도의 유연성은 염두에 두고 만들긴 했을 듯 하지만...
• 이것도 무려 구글 작품입니다. https://github.com/google/sanitizers/wiki/AddressSanitizer 논문도 여기에서 확인할 수 있습니다. https://research.google/pubs/pub37752/ 구글이 남긴 훌륭한 업적 중 하나...

참조

• http://egloos.zum.com/rousalome/v/10025873