[이 블로그 글은 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는 끝부분이 이상하게 0으로 채워진 메모리 주소인 0x7fce9c400000에 정확히 접근하려는 순간 충돌했습니다. 처음에는 분명 내가 메모리를 잘못 이동시키고 있고, 그 결과 주소가 0으로 덮어써져서 프로그램이 그 주소를 역참조하려 할 때 충돌하는 것이라고 생각했습니다.

저는 제가 구현한 기수 트리를 꽤 자랑스럽게 생각합니다. 구현 자체 때문은 아닙니다. 구현하기 복잡한 자료 구조이기는 하지만, 그렇다고 로켓 과학은 아니니까요. 제가 자랑스러워하는 이유는 함께 제공되는 퍼즈 테스터 때문입니다. 이 테스터는 소스 코드 전체(이 부분은 간단합니다)와 상당히 많은 비자명한 상태(이쪽이 확실히 더 흥미롭습니다)를 모두 다룰 수 있습니다. 이 퍼즈 테스터는 충돌을 일으키는 데만 목적을 두고 퍼징하지 않습니다. 기수 트리 딕셔너리와 이터레이터의 구현을, 해시 테이블과 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이고, 이는 issue 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 바이너리를 사용자에게 보내 달라고 요청했고, 디스어셈블된 코드를 읽어 보니 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의 카운트 인자가 어떻게 계산되었는지 이해할 수 있었습니다. 뭔가 분명히 잘못되어 있었습니다. 기본적으로 디스어셈블된 실행 파일이 제가 읽고 있던 C 함수와 일치하지 않는다는 사실을 확인하고 있었습니다. 어떻게 이런 일이 가능할까요? 상태가 정상적이었으므로 버퍼를 넘어 읽는 일은 일어나면 안 됩니다. 충돌한 인스턴스에서 카운트만 잘못 계산된 것입니다. 밤이었고, 저는 이 빌어먹을 문제를 이틀 내내 쉬지 않고 붙들고 있었습니다. 그래서 gist를 만들어 Twitter에 올리고, 이런 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 어셈블러를 배워야 한다는 것입니다. 적어도 컴파일러가 생성한 코드를 편하게 읽고 무슨 일이 일어나는지 따라갈 수 있을 정도는 되어야 합니다. 시스템 프로그래밍에 관여하고 싶다면 말입니다. 하이젠버그가 발생했을 때 상황을 이해할 수 있는 유일한 방법인 경우가 많습니다. 디버거는 그다지 도움이 되지 않습니다. GDB는 parent->size-- 명령어에서 충돌이 발생했다고 주장했지만, 물론 그럴 수는 없습니다. 그렇다고 GDB를 탓할 수도 없습니다. 최적화를 켠 현대적인 컴파일러는 소스 코드와 거의 대응시킬 수 없을 정도의 코드를 생성하기 때문입니다.

또 다른 교훈은 제대로 만든 퍼즈 테스트가 얼마나 강력한가 하는 점입니다. 퍼즈 테스터는 망가진 버전에서 버그를 즉시 찾아낼 수 있었습니다. 마찬가지로, 오래전에 수정된 이 버그 외에는 기수 트리 충돌이 한 번도 관찰되지 않았다는 사실도 많은 것을 말해 줍니다. 기수 트리 구현은 매우 복잡하지만, 퍼즈 테스트 덕분에 이렇게 새롭고 복잡한 구현에 버그가 없는 것으로 보입니다. 퍼징은 단순히 충돌을 찾기 위해서만 해서는 안 된다는 점을 강조하고 싶습니다. 제로데이를 발견하려는 보안 연구자에게는 그것도 좋은 방법입니다. 하지만 시스템 소프트웨어를 위한 퍼징은 타당한 연산 모델에 따라 무작위 연산을 수행하고, 그 결과를 참조 구현과 비교해야 합니다.

마지막으로 저 자신에게도 분명한 교훈이 있습니다. 다음부터는 기능 브랜치에서 작업하면서 해당 기능에만 국한되지 않는 수정 사항을 만들 때 더 신중해야 합니다. 저는 모든 것을 최대한 빨리 4.0에 다시 병합할 것이라고 생각하고 있었습니다. 하지만 실제로는 그렇게 되지 않았고, 기수 트리 업데이트를 Streams 관련 작업을 구현하는 커밋에 함께 넣은 것은 치명적인 실수였습니다.

아, 보너스 교훈도 있습니다. 똑똑한 친구에게 도움을 받는 것은 정말 유용합니다 :-) 그때 저는 조금 길을 잃은 상태였고, Fyodor의 친절한 도움 덕분에 퍼즐의 마지막 조각을 맞추고 빠르게 앞으로 나아갈 수 있었습니다. 도움을 요청하는 것을 두려워하지 마십시오. 시스템 소프트웨어에 관여하게 된다면, 프로그래밍의 다른 분야와는 매우 다르다는 점을 기억하십시오. 단순히 일을 해내고 계속 진행할 수 있는 분야가 아닙니다. 버그가 왜 발생했는지 이해하려고 며칠씩 매달릴 각오를 해야 합니다. 그런 버그는 사용자가 소프트웨어가 그렇게 충돌하는 것보다 더 나은 것을 누릴 자격이 있기 때문에, 대개 재현조차 할 수 없습니다.