며칠 전에, 저는 야후 메신져의 패스워드 관련 취약점을 연구하고 있었습니다.
야후 메신져는 로그인 패스워드를 힙에 저장하는데, 저는 그 패스워드를 찾아내서 뿌려주는
툴을 만들었습니다. 근데 그 패스워드는 대략 60000번째 힙 블럭에 위치하고 있었습니다 =_=
그래서 저는 패스워드가 담긴 힙에 도달하기 위해 60000번의 힙 블럭을 따라가야했습니다.
이 작업은 대략... 10분이 걸렸습니다..!
여러 PC에서 프로그램을 돌려봤으나 결과는 마찬가지였습니다.
당연히 저는 짱이 나기 시작했습니다. 그거 하나 보자고 이렇게 오래 기다려야하다니...

이 문제에 대한 해결책을 찾기 위해 인터넷을 뒤져보았으나 암것도 찾지 못했습니다.
결국엔 내가 직접 해결해보겠어!라는 생각이 들었고, 힙 관련 Windows API들을 리버싱 하기
시작했습니다. -_-v

몇 시간이 흐른 후...
저는 그렇게 시간이 오래 걸리는 이유를 발견해 냈습니다.
그리고 단 몇 초 안에 힙을 모두 검색하는 저만의 툴을 개발했습니다. ^.^
 

이 검색 방법은 작은 수의 힙 블럭을 탐색할 땐 큰 문제가 되지 않습니다.
하지만, 50000개 이상의 힙 블럭을 검색하기 시작하려면 10분이 넘게 걸립니다.
이 것은 오늘날의 컴퓨팅 세계에선 용납할 수 없는 시간입니다.
 

그 이유는 Heap32First과 Heap32Next 함수가 너무 너무 구리게 구현되어있었기
때문이었습니다. -_-

위 두 함수는 힙 블럭을 옮기기 위한 약간의 수학적 루틴을 제외하곤 거의 똑같았습니다.
다음은 kernel32.dll에 있는 Heap32Next 함수의 어셈 코드를 가져온 것입니다.
이 함수 내에서 무엇이 이루어지는지 함 봅시다..
 

일단 RtlCreateQueryDebugBuffer(0, FALSE) 함수를 실행하네요.
얘는 힙 데이터를 저장하기 위한 버퍼를 할당 받습니다.
이 함수 호출 후 버퍼의 주소가 리턴되고, 그게 ebx 레지스터에 저장됩니다.

만약 버퍼 할당에 실패하면 함수의 끝으로 점프하고, 그렇지 않으면 아래의 코드로
넘어갑니다.
 

다음으로 RtlQueryProcessDebugInformation 함수가 콜 됩니다.
이 함수는 프로세스의 모~~든 힙 블럭들을 로딩합니다.
다시말해 이 함수는 모든 힙 노드들과 그에 상응하는 힙 블럭들을 로딩합니다.

앞서 할당받은 버퍼의 0x38번째 오프셋엔 힙 정보 구조체가 있습니다.
힙 구조체의 첫 번째 값은 node count이고, 그 다음 값은 DEBUG_HEAP_INFORMATION
구조체의 배열입니다. 이 구조체가 각각의 힙 노드를 나타내고 있습니다.

지금 설명한 힙 정보 구조체의 원형은 다음과 같슴다.

그리고 첫 번째 힙 노드를 가리키기 위해 ecx 레지스터가 4 증가합니다.

이 것은 우리가 올바른 힙 노드에 있는지를 체크하는 루프입니다.
만약 아니라면, ecx는 다음 힙 노드를 가리키기 위해 DEBUG_HEAP_INFORMATION
사이즈로 증가됩니다.

올바른 힙 노드가 발견되었다면 curHeapNode->Blocks 값을 참조하여 힙 블럭의
포인터를 얻어옵니다.

여기서 HEAPENTRY32-> dwResvd는 블럭 카운트의 트랙을 유지하기 위해 내부적으로
사용됩니다.

위의 코드는 특정 플래그를 기반으로 유요한 힙 블럭을 찾습니다.
각가의 힙 블럭은 다음 구조체와 같습니다.

위 코드는 첨에 만들어진 버퍼를 해제하는 에러 핸들러입니다.
LAST ERROR CODE를 세팅하고, 부모 함수로 리턴합니다.

첫 번째 블럭에서, 만약 curBlock->flag & 2 != 2 이라면, 현재 블럭의 주소는
전 블럭 주소와 사이즈를 더하여 구해집니다.

올바른 힙 블럭이 찾아졌을 때, 그 힙의 타입은 LF32_FIXED, LF32_FREE 혹은
LF32_MOVEABLE 값으로 결정됩니다.

이 정보를 이용하여 HEAPENTRY32->dwFlags 값이 업데이트 됩니다.

마지막 부분에선 RtlDestroyQueryDebugBuffer 함수를 통해 할당받은 버퍼가 해제됩니다.

만약 에러가 발생하면, BaseSetLastNTError 함수가 호출되고, LAST ERROR가 세팅됩니다.
그렇지 않다면 이 함수는 정상적으로 리턴됩니다.

자, 여기까지를 정리하면 Heap32Next 함수 호출 시 다음의 행동들이 일어납니다.
 

이러한 과정은 Heap32Next 함수가 호출될 때마다 매번 발생합니다.
만약 50000개의 힙 블럭을 탐색한다고 가정해 봅시다.
그렇다면 매 함수 호출 때마다 버퍼가 생성되고, 프로세스의 전체 힙이 로딩되고,
탐색하고, 버퍼를 해제합니다. 매 호출 때마다.. =_=

이것이 바로 많은 수의 힙을 탐색할 때 시간이 그렇게 오래 걸리는 이유였던 겁니다.

다시 말해, 잘못된 설계가 문제입니다.
버퍼 할당, 힙 저장, 등의 작업은 딱 한번만 이루어져도 됩니다.
다음 위치의 유효한 힙 블럭을 찾기 위한 탐색 작업만 하면 됩니다.

다음은 단 몇 초 안에 거대한 힙 블럭을 탐색하는 방법입니다.

위의 사실에 근거하여 저는 저만의 힙 탐색 함수를 짰습니다.
Windows의 힙 API들보다 훨 빠르고 효과적입니다 -_-v
다음은 제가 함수를 구현한 방법입니다.

다음은 프로세스의 모든 힙 노드들을 탐색하는 예제 코드입니다.
버퍼를 할당받고, RtlQueryProcessDebugInformation 함수를 이용해서 전체 힙을
로딩합니다. 그 담에 모든 힙 노드들을 열거하면서 관련 정보들을 뿌려줍니다.
마지막에선 버퍼가 해제됩니다.
 

이 함수는 힙을 초기화하고, 특정 힙 노드를 찾기 위해 모든 힙 노드들을 탐색합니다.
그 담에 GetFirstHeapBlock과GetNextHeapBlock 함수를 이용하여 그 노드 안의 모든
힙 블럭들을 열거하고, 관련 정보를 뿌려줍니다.

위 코드의 대부분은 Heap32First 와 Heap32Next 함수를 리버싱해서 뽑아온 것입니다.
GetFirstHeapBlock 함수는 현재 힙 노드 안의 첫 번째 유효한 힙을 리턴합니다.
GetNextHeapBlock 함수는 다음 힙 블럭을 찾기 위한 비슷한 일을 합니다.

바로 직전 힙의 정보는 HeapBlock 구조체에 저장되어 있습니다.
얘는 부모 함수에 의해 건드려지면 안됩니다.

만약 당신의 프로젝트에서 이와 같은 함수를 구현하길 원한다면, 다음의 템플릿을
가져다 쓰시면 됩니다. ^.^

이 문서를 통해 Windows 힙 API의 내부 구현을 살펴봤습니다.
글구 도대체 왜케 느린지에 대해 분석을 해봤습니다.
마지막으로 더 빠르게 힙 탐색을 할 수 있는 방법에 대해 알아보았습니다. ^.^