heap(1) - Dynamic Memory Allocation

워 게임 문제를 풀면서 메모리 힙 관련한 취약점(use-after-free, double-free, heap overflow 등등..)을 이용한 공격에 대한 문제들이 나오면서 힙에 대한 이해의 필요성을 느끼게 되었다.

 

힙 기반 취약점에 대한 공격 기법은 힙 영역을 할당해주는 Dynamic Memory Allocator의 내부 구현이 어떻게 작동하는지에 대한 이해가 필요하므로 이번에 힙에 대한 전반적인 이해와 관련한 취약점이 무엇인지 공부하고 정리하기로 한다. (스택 기반 취약점보다 힙 기반 취약점을 이해하는데 상당한 시간과 노력이 필요...)

 

이번에 소개되는 내용은 동적 메모리를 관리하는 Dynamic Allocator에 관해 이론적인 위주로 다룰 것이다.

 

---

0. Heap 영역

 

들어가기전에..

먼저, 복습할 겸 메모리 구조 한 번 되새기고 데이터 저장하는 3가지 방법과 힙 영역이 무엇인지 왜 필요한지 다루도록 한다.

 

프로그램이 실행되기 위해서 먼저 프로그램이 메모리에 올라가게 되며 OS는 프로그램 실행을 위해 메모리 공간을 할당해주게 된다.

 

이 때, 할당된 메모리 공간에는 다양한 영역이 존재하며 사용되는 용도가 다르다. 여기서 할당된 메모리 공간에는 코드(code, 또는 text)영역, 데이터(data)영역, 스택(stack)영역, bss영역, 힙(heap)영역으로 구분된다.

 

여기서 데이터를 저장하는 방법은 크게 전역 변수로 할당된 데이터, 정적으로 할당된 데이터, 동적으로 할당된 데이터로 구분되며 각 데이터들은 위 영역에서 데이터 영역, 스택 영역, 힙 영역을 사용하게 된다.

• 데이터(data) 영역

  • 전역 변수, static변수가 저장된 영역

  • 컴파일 시점에 사이즈 결정

  • Lifetime : 프로그램 시작과 동시에 할당되며 종료시 소멸

• 스택(stack) 영역

  • 지역변수, 매개변수가 저장된 영역

  • 컴파일 시점에 사이즈 결정

  • Lifetime : 함수가 호출시 할당되며 리턴할 때 소멸

• 힙(heap) 영역

  • malloc(), calloc()과 같은 함수에 의해 동적으로 생성된 변수를 저장하는 영역

  • 런타임 시점에 사이즈 결정

  • LifeTme : 런타임에만 알 수 있음

 

 

heap 영역이란?

위에서 설명했듯이 malloc()이나 calloc(), new 등을 통해 동적 할당된 데이터를 저장하는 영역으로 OS에 의해서 관리되지 않고 사용자가 직접 메모리 할당 및 해제할 수 있는 공간이다.

 

[ 스택 vs 힙 ]

스택 영역과 비교하였을 때 속도면이나 비용문제에서 스택을 사용하는 것이 성능면에서 우수하며 힙은 스택과 달리 메모리를 직접 관리(메모리 할당 및 해제)를 해줘야하지만 스택 영역은 힙 영역에 비해 메모리 공간이 부족하며 할당해야 할 메모리 크기를 프로그램이 실행하는 동안 결정해야 하는 경우 힙 영역을 사용한다.

 

 

---

1. Dynamic Memory Allocator

1.1 Allocator가 하는 일

Dynamic Memory Allocator : 시스템에게 동적으로 메모리 할당을 요구할 때 해당 작업을 처리하며 힙 영역을 관리하는 모듈이다. 이 때, 애플리케이션 내부 오브젝트 들은 페이지 크기보다 작으므로 해당 페이지들 안의 블록들을 관리하며 관리하는 블록들은 allocated 또는 free 두 가지 상태로 존재한다.

 

예를 들어 C나 C++, Java에서 코딩할 때 메모리 할당시 사용되는 malloc()이나 new와 메모리 해제할 때 사용되는 free()나 delete와 같은 함수(또는 연산자)들 모두 Memory Allocator에 속해 있다.

 

이처럼 Allocator가 하는 일은 메모리 요청이 들어오면 할당해주고 사용을 다하면 반환해주는 일이 전부이다.

 

1.2 Allocator 종류

1) Explict allocator : 개발자가 공간의 할당 및 해제

• ex) libc의 malloc()과 free() 등

• 종류)

  • tcmalloc(Google) : thread caching malloc의 약자로 구글이 만든 성능 도구에 포함되어 있는 힙 메모리 할당자로써 크롬 및 많은 프로젝트에 사용 - (멀티 쓰레드 최적화 Allocator)

  • Jemalloc(FreeBSD와 Firefox) : Jason Evans가 만들었으며 페이스북이나 파이어 폭스에 사용 - (멀티 쓰레드 최적화 Allocator)

  • ptmalloc2(glibc) : GNU library(glibc)에서 사용하는 Allocator로 dlmalloc코드를 기반으로 하며 멀티 스레딩 기능 추가

  • dlmalloc(General Purpose Allocator) : Doug Lea가 만들었으며 일반적인 목적의 Allocator, 많은 malloc의 베이스가 됨

2) Implict allocator : 개발자가 공간의 할당만 담당 (free()나 delete사용하지 않아도 알아서 해제해줌)

• ex) java의 GC(Garbage Collector), Lisp 등

 

1.3 Performance

대부분 프로그램에서 유연하고 확장성 있게 프로그램을 작성하기 위해 동적으로 메모리를 할당하고 해제하는 작업이 빈번하게 발생한다. 이러한 작업들을 신속하고 효율적으로 처리하기 위해서는 Allocator의 Performance가 중요하다.

따라서, Allocator의 Performance를 높이기 위해서 1) 처리속도와 2) 메모리 사용 효율성을 최대화해야 한다.

 

1) 처리속도(Throughput)

• 특정 시간 내 처리된 요청의 수

2) 메모리 사용 효율성(Peak Memory Utilization)

• 현재까지 할당된 블록의 합 / 힙 영역의 총 크기

• 메모리 사용 효율성을 떨어뜨리는 가장 큰 문제가 Fragmentation

※ 메모리 파편화(Fragmentation)

① Internal Fragmentation

• 요청한 데이터의 크기가 블록의 크기보다 작을 때 발생

• 발생 원인

  • Allocator는 Alignment에 맞춰 할당하므로

  • 힙 메타데이터 저장을 위한 공간

  • 메모리 할당 정책 및 알고리즘에 따른 결과

 

② External Fragmentation

• 할당되지 않은 블록은 존재하나 요청한 데이터의 크기보다 작을 때 발생

• 발생 원인

  • 반복된 할당 / 해제 패턴으로 인해 블록 사이에 빈 공간이 생긴 경우

 

---

2. Free List Algorithm

위에서 설명했듯이 Allocator는 단순히 메모리 요청이 들어오면 할당하고 해제하는 역할을 한다.

 

그럼 이제 Allocator는 요청에 따라 어디에 블록을 할당하고 얼마나 메모리를 해제하고 또, 힙에다가 어떻게 다시 돌려줄지 등등.. 어떻게 관리하는지 의문점이 발생한다.

 

결론적으로 얘기하자면 Allocator는 각각의 블록들이 사용 중인지, 아니면 사용하지 않는지 그리고 추가적으로 사용하고 있다면 얼만큼 사용하고 있는지에 대한 정보를 알고 있으면 된다.

 

이러한 정보들은 각 블록의 헤더에 기록되어 있으며 Allocator는 이러한 블록들을 관리하기 위해 블록 간에 리스트를 만든다.

 

다음은 해제된(free) 블록들을 관리하기 위한 방법 3가지를 간단히 소개하겠다.

 

2.1 Implicit Free List

1) Concept

• 포인터를 사용하지 않고 길이 계산을 통해 모든 블록을 연결

[블록 포맷]

 

2) Allocation

2-1) Search Free Block : 할당을 하기 위해서 먼저 요청된 크기에 맞는 사용되지 않은(free) 블록을 탐색

• 방법 ① First fit : 리스트 시작점부터 탐색하여 만족하는 크기의 free block 선택

• 방법 ② Next fit : 이전에 탐색한 시점부터 탐색하여 만족하는 크기의 free block선택

• 방법 ③ Best fit : 리스트 전체를 탐색하여 가장 적합한(Fragmentation이 최소화되는) free block 선택

2-2) Allocate Block : 선택된 free block이 요청한 크기보다 클 수 있으므로 잘라서 할당

 

3) Free

• 블록의 상태를 "Allocated"에서 "Free"로 변경

• 이 때, 해제하려는 블록 다음 위치의 블록 또한 Free상태이면 이어 붙임(Coalescing)

  +) 양방향 Coalescing

• Boundary tags : 해제된 블록의 끝에 헤더 정보를 복사하여 블록을 반대 방향으로도 따라갈 수 있게 함

[블록 포맷]

 

4) 특징

• 구현이 간단함

• Allocation Cost : O(n)

• Free Cost : O(c) (c : 상수)

• 메모리 사용 : Placement 정책(first, next, best fit 등)에 따라 다름

 

2.2 Explicit Free List

1) Concept

• 포인터를 사용하여 모든 블록 대신 해제된 블록만 연결(Double Linked List를 이용하여 구현)

[블록 포맷]

 

2) Allocation

• Implict Free List와 비슷하게 블록을 나누어서 할당하며 할당된 블록은 Free List에서 사라지고 나누고 남는 나머지 블록은 다시 list에 연결시켜준다.

3) Free

• 새로 해제된 block을 Free List의 어느 부분에 삽입할지 문제 생김 → 블록 삽입 정책

  • 방법 ① LIFO(Last-In-First-Out)

    • Free List의 시작(Head)에 넣음

  • 방법 ② Address Order

    • 주소 순서대로 연결되도록 Free List에 삽입

4) 특징

• Implicit Free List에 비해 구현이 복잡함

• Allocation cost : O(n)

  • But, 모든 블록의 수가 아닌 Free 블록의 개수에 의존하며 힙이 거의 꽉 차있다면 즉, Free List의 노드가 거의 없다면 훨씬 빠름

• 각각의 블록당 포인터를 저장할 추가 공간 필요 → 최소 블록 크기 증가

• Explicit Free List는 보편적으로 segregated free list와 함께 사용

 

2.3 Segregated Free List

1) Concept

• 각각 다른 블록 할당 크기 클래스에 따라서 여러 Free List 관리

2) Allocation

• 요청하는 크기의 맞는 블록을 찾았다면 나누고 나머지 free블록을 사이즈 클래스에 알맞게 list에 추가

• 하지만, 만족하는 크기의 블록을 찾지 못했다면 더 큰 사이즈의 클래스 free list를 조회

3) Free

• 블록의 메타 데이터 업데이트, Coalesce후 알맞은 free list에 추가

4) 특징

• 다른 알고리즘에 비해 더 높은 속도를 발휘하며 효율적인 메모리 활용을 가져다 줌

 

---

3. 참고 자료

 

[User level] Memory Allocator 구현 (1)

Implementing a Memory Allocator

+)

• https://cs.nyu.edu/courses/spring17/CSCI-UA.0201-001/resources/lecture22.pdf

• https://cs.nyu.edu/courses/spring17/CSCI-UA.0201-001/resources/lecture23.pdf