0x0a Windows-Heap

안녕하세요. Joel입니다.

오늘부터는 Windows Heap에 대해 알아보도록 하겠습니다.

What is Heap?

Heap은 프로세스가 실행되는 동안 메모리를 필요한만큼 동적으로 할당하여 사용하는 영역입니다.

그리고 c/c++에서는 malloc, new 함수를 사용하여 Heap 영역을 할당받아 사용합니다.

윈도우에서는 힙을 이용할 수 있도록 API 함수들을 제공하고 있는데 대표적인 윈도우 힙 함수는 다음과 같습니다.

• HeapCreate : 힙을 생성합니다.
• HeapDestroy : 힙을 삭제합니다.
• HeapAlloc : 힙 블록을 할당합니다.
• HeapFree : 할당된 힙 블록을 해제합니다.

이 정도는 이미 알고 계실거라 생각합니다.

그럼 조금만 더 상세하게 알아볼게요.

Process Heap

Process가 시작되면 최소한 하나의 기본 Process Heap(또는 Default Heap)이 생성됩니다.

이 Process Heap은 Process 시작 시에 생성되고(기본 크기는 1MB) Process가 종료될 때까지 없어지지 않는 특징이 있습니다.

흔히 사용하는 malloc, new는 Process Heap에서 할당하는 것입니다.

이 기본 Heap은 프로그램 내에서 명시적으로 사용될 수도 있고 윈도우 내부 함수에 의해 암묵적으로 사용될 수도 있는데 프로그램에서 GetProcessHeap을 이용해 기본 Process Heap을 구할 수 있습니다.

요약을 해보자면, Process가 시작되면 기본 Heap이 생성된다는 것과 malloc, new를 이용해서 아래 그림처럼 Heap을 할당받아 사용한다는 것입니다.

지금까지 기본 Heap에 대한 설명을 했는데요,

지금부터는 위 그림처럼 하나만 할당받는 것이 아닌 다양한 크기의 Heap 공간을 반복적으로 할당/해제하는 경우를 한 번 생각해보겠습니다.

Heap Fragmentation

사용자가 Heap 공간을 쓰기 위해 할당을 요청하면 사용가능한 “연속된” 공간이 할당됩니다.

그런데 다양한 크기의 Heap 공간을 요청하고 해제한다고 생각해봅시다.

분명 할당받은 순서대로 해제하지는 않겠죠?

정해진 순서없이 다양한 크기의 Heap이 할당되고 해제된다면, 아래 그림처럼 특정 순간에는 원하는 크기의 Heap을 할당해줄 수 없는 순간이 올 겁니다.

이를 Heap Fragmentation(힙 단편화)이라고 합니다.

위 그림에서 보듯, 남은 메모리 용량의 총합은 할당을 원하는 객체의 크기보다 크지만 연속된 공간을 할당해 줄 수 없는 상황이 옵니다.

윈도우는 이러한 단편화 문제를 해결하기 위해서 특별한 방식들을 사용하고 있습니다.

이 방식들을 살펴보면서 Heap에 대한 이해를 더 높여보겠습니다.

Free List

http://www.slideshare.net/ffri/mr201312-history-and-current-state-of-heap-exploit-eng

Free List란 말 그대로 해제된 Heap 메모리들을 담아두는 List입니다.

어떤 메모리를 할당해서 사용하고 난 뒤, 해제를 하면 그 메모리는 Free List에 들어가게 됩니다.

그리고 다음 메모리를 할당하려고 하면 Heap 공간을 바로 쓰게 해주는 것이 아니라 Free List를 먼저 살펴봅니다.

Free List에 적합한 크기의 Heap 메모리가 있을 경우는 해당 메모리를 할당해줍니다.

만약 적절한 크기의 메모리가 없다면 요청한 크기만큼의 Heap을 새로 할당해주는 방식입니다.

예를 들어, 프로그램이 시작된 후 처음으로 0x20 크기의 Heap을 요청했다고 가정하겠습니다.

해제된 메모리가 없으니 Free List는 비어있겠죠?

그럼 Heap의 할당은 다음 그림처럼 이루어집니다.

(실제로는 0x20 + Heap Header 크기만큼 할당이 이루어집니다.)

그런 다음 이 메모리를 해제하게 되면 이 메모리는 Free List에 들어가게 됩니다.

이후 프로그램이 다시 0x30 크기의 Heap을 요청하면 Free List를 먼저 살펴봅니다.

0x30을 할당할 수 있을 만한 크기가 없기 때문에 새로 0x30만큼의 메모리를 할당해줍니다.

이번에는 0x10만큼의 메모리 할당 요청이 들어왔다고 가정하겠습니다.

이번에도 Heap 관리자는 Free List를 먼저 살펴보겠지요?

Heap 관리자는 Best-Fit 정책을 사용하고 있기 때문에 최대한 적합한 크기의 Heap을 할당하려고 합니다.

지금 상황에서는 0x30이 제일 적합한 메모리가 되겠네요.

이 0x30 메모리를 모두 할당하는 것이 아니라 메모리를 분할하여 0x10만큼만 할당을 해줍니다.

그런데 이런 방식을 사용하는 환경에서 작은 메모리 요청/해제가 빈번하게 일어나면 어떻게 될까요?

작은 메모리 조각이 계속해서 발생할 것이고 이를 관리하는 것에 한계가 생길 겁니다.

이런 현상을 개선하기 위해서 최신 윈도우에서는 Low Fragmentation Heap이라는 정책을 도입했습니다.

Low Fragmentation Heap

Low Fragmentation Heap(저단편화 힙)은 말 그대로 위에서 살펴본 Free List 방식에서 발생하는 단편화 현상을 줄이기 위해 도입되었습니다.

Free List에서는 Heap을 계속해서 분할하는 방식이기 때문에 단편화 문제가 있다고 했었죠?

그래서 Low Fragmentation Heap은 Bucket이라는 미리 정의된 서로 다른 크기의 범위를 갖는 블록을 관리함으로써 단편화를 해결합니다.

쉽게 이야기해서, 미리 여러 크기로 Heap 공간을 분할해놓고 할당 요청이 오면 해당 크기를 포함하는 가장 작은 Bucket을 선택해 할당합니다.

Bucket은 총 128개인데 첫 번째 Bucket은 1~8바이트, 두 번째는 9~16바이트 식으로 8바이트 단위로 구분되며, 마지막 Bucket은 15873~16384 바이트 크기까지 지원할 수 있습니다.

만약 요청된 크기가 16384 바이트보다 크다면 Backend로 요청을 보냅니다.

Backend로 요청이 이루어지면 Free List 방식으로 Heap 할당을 진행합니다.

즉, Low Fragmentation Heap 기법은 미리 Bucket으로 나누어서 적합한 메모리를 찾는 속도를 증가시키고, 크기별 Free List들을 Lookaside List에 나누어 관리하는 것이죠.

지금까지 Windows Heap 대해 알아봤습니다.

다음 시간부터는 Heap에 대한 공격 기법을 살펴보도록 하겠습니다.