[이 블로그 포스트는 Medium에서도 실험적으로 볼 수 있습니다: https://medium.com/antirez/a-short-tale-of-a-read-overflow-b9210d339cff]

오래 실행되는 프로세스가 크래시되면 꽤 곤란하다. 그 프로세스가 메모리에 많은 상태를 들고 있다면 더더욱 그렇다. 그래서 나는 큰 성능 오버헤드 없이 페이지 뷰마다 새로운 인터프리터와 새로운 상태를 만들고, 페이지 생성이 끝나면 사용한 모든 자원을 해제할 수 있는 웹 프로그래밍 프레임워크를 좋아한다. 메모리 누수나 디스크립터 누수, 심지어 가끔 일어나는 무작위 크래시도 심각한 문제가 되지 않는, 본질적으로 더 신뢰할 수 있는 프로그래밍 패러다임이다. 하지만 Redis 같은 시스템 소프트웨어는 스펙트럼의 반대편에 있다. 절대 크래시해서는 안 되는 것들이 모여 있는 쪽이다.

몇 달 전 동료 Dvir Volk로부터 크래시 리포트를 받았다. 그는 RediSearch Redis 모듈을 개발 중이었기 때문에, 크래시가 모듈 내부의 프로그래밍 오류, 아마도 힙을 손상시키는 오류 때문인지, 아니면 Redis 내부의 버그 때문인지 명확하지 않았다. 하지만 래딕스 트리 구현 안에 있는 진짜 문제처럼 보였다:

=== REDIS BUG REPORT START: Cut & paste starting from here ===
# Redis 999.999.999 crashed by signal: 11
# Crashed running the instuction at: 0x7fceb6eb5af5
# Accessing address: 0x7fce9c400000
| Backtrace:
| redis-server *:7016 [cluster](raxRemoveChild+0xd3)[0x49af53]
| redis-server *:7016 [cluster](raxRemove+0x34f)[0x49b34f
| redis-server *:7016 [cluster](slotToKeyUpdateKey+0x1ad)[0x4415dd]

래딕스 트리는 memmove() 호출로 가득하고, Redis는 정확히 0x7fce9c400000처럼 끝부분이 0으로 패딩된 묘한 메모리 주소에 접근하려다 크래시됐다. 내 첫 생각은, 여기서 메모리 이동을 잘못하고 있는 게 분명하고, 그 주소가 0으로 덮어쓰여 프로그램이 그 주소를 역참조하려 할 때 크래시로 이어진다는 것이었다.

나는 내 래딕스 트리 구현이 꽤 자랑스럽다. 구현 자체 때문은 아니다. 구현하기 복잡한 자료구조이긴 하지만 로켓 과학은 아니니까. 자랑스러운 이유는 함께 제공되는 퍼즈 테스터 덕분이다. 이 테스터는 전체 소스 코드를 커버할 수 있고(그건 trivial한 일이다) 더 중요하게는 수많은 논트리비얼한 상태를 커버한다(그게 훨씬 더 흥미로운 부분이다). 퍼즈 테스터는 단순히 크래시를 일으키기 위해 퍼징을 하는 게 아니다. 래딕스 트리 딕셔너리와 이터레이터의 구현을 해시 테이블과 qsort를 사용하는 레퍼런스 구현과 비교한다. 완전히 동일한 의미를 갖도록 하되, 짧고 감사하기 쉬운 구현으로 말이다. 크래시 리포트를 받은 뒤 나는 퍼즈 테스터를 개선했고, Valgrind를 켜고 끈 상태로 며칠 동안 돌렸으며, 추가 데이터 모델을 작성하고 1억 개의 키를 이용한 테스트도 만들었다. 하지만 노력에도 불구하고 크래시를 재현할 수 없었다. 며칠 뒤에야 내가 테스트하던 구현에는 버그가 없었다는 것을 알게 됐지만, 당시에는 그 사실을 몰랐다. 애초에 존재하지 않는 버그를 찾을 수는 없었던 것이다. 그래서 재현에 실패한 뒤 포기했다.

일주일 전 거의 동일한 버그 리포트 두 건을 추가로 받았다. 그리고 다시 주소는 0으로 패딩되어 있었다.

Dvir crash: Accessing address: 0x7fce9c400000
Issue 4605: Accessing address: 0x7f2959e00000
Issue 4642: Accessing address: 0x7f0e9b800000

소스 코드 안의 모든 memmove, memcpy, realloc 호출을 읽어보며, 혹시 퍼즈 테스터가 잡아내지 못한 무언가 잘못된 부분이 있는지 파악해야 할 때였다. 아무것도 찾지 못했지만, Redis 크래시 리포트를 살펴보다 재미있는 점을 발견했다. 크래시 시 Redis는 프로세스의 메모리 매핑 영역을 보고하는데, 다음과 같은 것들이다:

*** Preparing to test memory region 7f0e8c400000 (255852544 bytes)

이제 0x7f0e8c400000에 255852544를 더하면 결과는 0x7f0e9b800000이 되는데, 이는 이슈 4642에서 보고된 크래시에서 접근한 주소와 정확히 일치한다. 즉 프로그램은 메모리 주소가 손상되어 크래시된 것이 아니라, 힙의 끝 바로 다음 주소를 접근하다 크래시된 것이다. 다른 이슈들도 확인해 보니 모든 경우에 마찬가지였다. 기본적으로 힙의 끝, 매핑되지 않은 주소 영역의 시작 경계가 범위 밖 접근이 수행될 때 이를 감지해 크래시를 일으키는 메모리 가드 역할을 하고 있었던 것이다. 이는 과거 특정 C 메모리 새니타이제이션 도구들이 흔히 쓰던 기법이다. 그런 도구들은 접근 불가능한 메모리 페이지 경계에 할당된 주소를 반환하는 malloc() 대체 구현을 제공했다. 모든 오버플로는 이런 방식으로 즉시 감지될 수 있었다.

프로그램이 힙의 끝에 있는 래딕스 트리 노드를 해제할 때만 크래시됐기 때문에, 문제가 리드 오버플로라는 것을 쉽게 알 수 있었다. 리드 오버플로는 그 외에는 절대 감지할 수 없다. 구조체 밖의 데이터에 접근하지만 여전히 매핑된 메모리 안에 있기 때문에, 버그는 완전히 무해하고 조용할 뿐이다. 단 매핑된 영역의 끝에서 동일한 연산을 수행하는 경우는 예외다. 마침내 어디를 봐야 할지 명확해졌고, 그곳은 C 코드의 이 부분이었다:

/* 3. Remove the edge and the pointer by memmoving the remaining children pointer and edge bytes one position before. */
int taillen = parent->size - (e - parent->data) - 1;
debugf("raxRemoveChild tail len: %d\n", taillen);
memmove(e,e+1,taillen);
/* Since we have one data byte less, also child pointers start one byte before now. */
memmove(((char*)cp)-1,cp,(parent->size-taillen-1)*sizeof(raxNode**));
/* Move the remaining "tail" pointer at the right position
as well. */
size_t valuelen = (parent->iskey && !parent->isnull) ? sizeof(void*) : 0;
memmove(((char*)c)-1,c+1,taillen*sizeof(raxNode**)+valuelen);
/* 4. Update size. */
parent->size--;

나는 크래시 리포트를 생성한 redis-server 바이너리를 보내달라고 사용자에게 부탁했고, 디스어셈블된 코드를 읽어보니 많은 CPU 레지스터가 — Redis 크래시 리포트에도 포함된 레지스터들이다 — 여전히 위 변수들의 값으로 채워져 있다는 것이 분명해졌다! CPU 레지스터 RDI, RSI, RDX는 memmove에 첫 세 인자를 전달하는 데 사용된다는 점에 유의하자. 크래시 중 하나에서는 다음과 같았다:

parent = RBP = 7f2959dffff
Checking RDI, RSI, RDX we extract the memmove() arguments:
memmove(00007f2959dffff4,00007f2959dffffd,0000000000000008);
The memmove will go out of bound accessing up to 7f2959e00004.

그렇게 증거를 확보했다. 하지만 더 있었다. 다른 레지스터들을 확인해 노드 헤더도 재구성할 수 있었고, 이를 통해 memmove의 count 인자가 어떻게 얻어졌는지 이해할 수 있었다. 뭔가 확실히 잘못되어 있었다. 기본적으로 내가 보고 있는 디스어셈블된 실행 파일이 내가 읽고 있던 C 함수와 일치하지 않는다는 것을 알 수 있었다. 어떻게 그럴 수 있을까? 상태는 정상이었기 때문에 버퍼를 넘어 읽는 일이 일어나서는 안 됐다. 잘못 계산된 것은 크래시가 난 인스턴스의 count뿐이었다. 밤이었고, 나는 이 지긋지긋한 문제에 꼬박 이틀을 매달려 있었기 때문에, gist를 만들어 트위터에 올리기로 했다. 컴파일러가 어떻게 그런 C 코드를 그런 어셈블리로 바꿀 수 있는지 설명해 줄 사람이 있는지 보기 위해서였다.

운 좋게도 Node.js로 유명한 내 친구 Fedor Indutny가 도와주겠다고 했다. 그는 C 코드와 어셈블리가 일치할 수 없는 이유가 매우 명확하다는 것을 금방 알아챘다. 내가 분석하고 있던 것이 올바른 C 코드가 아니라… 같은 함수의 더 새로운 버전이었던 것이다. Fedor는 버그를 보고한 사용자가 사용한 것과 같은 컴파일러인 GCC 5.4.0을 가지고 있었기 때문에, 이전 버전의 코드를 그것으로 컴파일해 보았고, 이제 두 버전의 생성된 코드가 완벽하게 일치한다는 것을 알게 됐다. 그는 내게 연락해 이것이 정말 최신 Redis 버전이 맞는지 물었다. 나는 완전히 확신했다. Redis 4.0.6이었다. 하지만 이내 의심이 들기 시작했고, Redis unstable 브랜치와 Redis 4.0 사이의 rax.c diff를 확인했다. 일어난 일은 내가 약 10개월 전 Streams 구현 과정에서 이 버그를 이미 수정했다는 것이었다. unstable에서 Redis 4.0으로 버그 수정을 백포트하는 체리픽 과정에서, 그 수정은 streams에 관한 커밋 안에 들어 있었기 때문에 나는 계속 건너뛰고 있었던 것이다. 마침내 모든 것이 명확해졌다. 나는 존재하지도 않는 버그를 며칠 동안 디버깅하고 있었던 것이다. 내가 테스트하던 버전에는 이미 없던 버그를.

만약 그저 나의 어리석은 실수였다면 왜 굳이 이 블로그 글을 썼을까? 이 모든 일에서 배울 교훈이 있다고 믿기 때문이다.

첫 번째 교훈은 Redis가 생성할 수 있는 것과 같은 크래시 리포트가 시스템 소프트웨어에서 핵심 자산이라는 것이다. 재현할 수는 없지만 야생에서 매우 드물게 발생하는 버그의 상태를 재구성할 수 있게 해준다. 버그는 이미 수정된 상태였지만, 나는 버그 리포트와 레지스터 덤프, 문제를 일으킨 주소, 호출 스택만 보고도 정확히 무슨 일이 일어났는지 이해할 수 있었다.

두 번째 교훈은 시스템 프로그래밍에 참여하고 싶다면 오늘 당장 AMD64 어셈블리를 배워야 한다는 것이다. 적어도 컴파일러가 생성한 코드를 편안하게 읽고 무슨 일이 일어나고 있는지 따라갈 수 있을 정도는 되어야 한다. 이는 heisenbug 상황에서 무슨 일이 일어나고 있는지 이해하는 유일한 방법인 경우가 많다. 디버거는 별 도움이 되지 않는다. GDB는 크래시가 parent->size-- 명령어에서 발생했다고 주장했다. 물론 불가능한 일이다. 하지만 GDB를 탓할 수는 없다. 최적화 옵션을 켠 최신 컴파일러는 소스 코드와 거의 매칭하기 어려운 코드를 생성한다.

또 다른 교훈은 잘 만들어진 퍼즈 테스팅이 얼마나 강력한가 하는 점이다. 퍼즈 테스터는 망가진 버전에서 버그를 즉시 찾아냈다. 마찬가지로 오래전에 수정된 이 버그 외에는 래딕스 트리 크래시가 전혀 관찰된 적이 없다는 사실 자체가 많은 것을 말해준다. 래딕스 트리 구현은 매우 복잡하지만, 퍼즈 테스팅 덕분에 그토록 새롭고 복잡한 구현임에도 겉보기에 버그가 없는 것이다. 나는 단순히 크래시를 찾기 위한 퍼징이 아니라는 점을 강조하고 싶다. 그건 제로데이를 찾고 싶은 보안 연구자들에게는 좋은 방법이다. 시스템 소프트웨어를 위한 퍼징은 정상적인 연산 모델에 따라 무작위 연산을 수행하고, 그 결과를 레퍼런스 구현과 비교해야 한다.

그리고 마지막으로, 나 자신을 위한 명확한 교훈이 있다. 다음에는 기능 브랜치에서 작업하면서 해당 기능 브랜치에만 국한되지 않는 수정을 할 때 더 신중해야 한다는 것이다. 나는 모든 것을 가능한 한 빨리 4.0으로 다시 머지할 것이라는 생각으로 작업하고 있었다. 그러다 그렇게 되지 않았고, 래딕스 트리 업데이트를 Stream 관련 작업을 구현하는 같은 커밋에 넣은 것이 치명적인 실수였다.

덤으로, 똑똑한 친구들의 도움은 보너스 점수다 :-) 나는 그 시점에서 좀 길을 잃은 상태였는데, Fyodor의 친절한 도움이 퍼즐의 마지막 조각을 맞추고 빠르게 앞으로 나아갈 수 있게 해주었다. 도움을 요청하는 것을 두려워하지 마라. 시스템 소프트웨어에 뛰어든다면, 그것이 프로그래밍의 다른 분야와 매우 다르다는 것을 기억하라. 단순히 작업을 하고 앞으로 나아가는 것만이 아니다. 버그가 왜 발생했는지 이해하기 위해 며칠을 보내야 할 수도 있다. 종종 재현조차 할 수 없는 버그를 말이다. 사용자는 그렇게 크래시되는 것 이상의 소프트웨어를 받을 자격이 있기 때문이다.