참고자료
https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/
https://bpsecblog.wordpress.com/2016/10/06/heap_vuln/
http://tribal1012.tistory.com/78
HEAP이란 무엇일까?
스택 메모리는 함수 내에 선언된 지역 변수, 필요한 공간의 크기를 컴파일 시에 확정한다.
함수 호출시 그에 해당하는 지역변수를 위한 공간을 확보하며 함수의 실행이 끝나게 되면 지역변수의
공간을 자동으로 해제하게 된다!
힙메모리의 경우 프로그램 실행 중 필요에 의한 동적 메모리 할당을 위한 공간
힙 영역은 컴파일러가 예측할 수 없는 프로그래머가 관리하는 영역!
memory allocator에는 여러 종류가 있고, glibc malloc에 대해서 살펴볼 것이다
/* Per thread arena example. */
출처: http://tribal1012.tistory.com/78 [Trillion]
메인스레드에서 malloc 호출 이전: 힙영역이 아직 없고, thread1이 생성되지 않아 스레드의 스택이 없다!
메인스레드에서 malloc 호출 이후: 힙영역이 생성되었고, 힙 메모리의 크기는 132KB나 생성되었다(사용자는 1000바이트만 요청했다!)
이러한 힙 메모리의 인접한 지역을 arena라고 루른다.
이 arena는 메인 스레드로써 생성되었기 때문에, 이것을 main arena라고 부른다.
이후, 할당 요청은 이 arena를 사용하여 비어있는 공간이 없어질 때까지 유지하면서 사용한다.
arena의 비어있는 공간이 고갈되었을 경우, 프로그램의 break위치를 증가시킴으로써 더욱 성장할 수 있다.
(top 청크의 크기를 증가시켜 여분의 공간을 포함할 수 있도록 조정한 후)
이와 비슷하게 top 청크에 비어있는 공간이 많은 경우, arena는 또한 줄어들 수 있다.
top 청크는 arena의 최상단의 청크를 말한다.
메인스레드에서 free호출 이후: 할당된 메모리 집단이 해제된 경우, 메모리의 뒤에서 해제된 메모리가 즉각 운영체제에 반환되지 않는다.
할당된 메모리의 일부분(1000바이트)은 오로지 main arena의 bin(glibc malloc에서 freelist data structures는 bin으로서 참조됨)에 이 해제된 블럭을 추가하고 glibc malloc 라이브러리에 반환된다. 이후 사용자가 메모리를 요청하는 경우, glibc malloc은 커널로부터 새로운 힙 메모리를 얻지 않고, 대신 bin에서 비어있는 블럭을 탐색해준다. 그리고 비어있는 공간이 존재하지 않는 경우, 커널로부터 메모리를 받는다.
thread1에서의 malloc 호출 이전: thread1의 힙 영역은 없으나 thread1의 스레드 스택은 생성된 것을 볼 수 있다
thread1에서의 malloc 호출 이후: thread1의 힙 영역이 생성된 것을 볼 수 있다. 그리고 이 영역은 메모리의 매핑된 세그먼트 일부에 위치하며, sbrk를 사용하는 main thread와 달리 mmap을 사용하여 힙 메모리가 생성된다. 사용자는 1000바이트만 요청했지만, 1MB크기의 힙 메모리가 프로세스 주소 공간에 매핑되어 있다. 이 1MB 중, 132KB가 read-write권한이 세트되어, 이 스레드를 위해 힙 메모리로 할당되었다. 이러한 메모리의 일부분(132KB)을 thread arena라고 부른다.
*사용자가 128KB(ex, malloc(132*1024))보다 큰 크기를 요청할 경우와 arena에 사용자의 요청을 만족시킬 수 있는 충분한 공간이 없는 경우, 비록 main arena또는 thread arena에서 만들어진 요청이지만 이것을 무시하고 메모리는 mmap syscall을 사용하여 할당된다.
thread1에서의 free호출 이후: 해제한 할당된 메모리 집단은 운영체제에 힙 메모리를 반환하지 않는다. 대신 할당된 메모리 지역(1000바이트)을 thread arena의 bin에 해제된 블럭을 추가하고, glibc malloc에 반환한다.
arena의 수: 위의 예제에서 메인 스레드가 main arena를 가지고, thread1이 자신의 thread arena를 가지는 것을 보았다. 그래서 스레드의 수를 무시하고 스레드들과 arena 사이의 일대일 매핑은 존재할 수 있는가? 아니다. 어플리케이션의 arena제한은 현재 시스템의 core 갯수에 기반한다.
32비트 시스템->2*코어수
64비트 시스템->8*코어수
glibc malooc의 소스코드에서 아래와 같은 3개의 데이터 구조체를 확인할 수 있다.
heap_info-Heap Header-단일 스레드 arena는 여러 개의 힙을 가질 수 있다. 각 힙은 각자의 헤더를 가진다. 왜 여러 개의 힙이 필요한가? 모든 스레드 arena는 오직 하나의 힙만을 가지고 시작하지만, 힙 영역의 공간이 부족해지는 경우, arena에 새로운 힙을 할당해주어야 한다.
malloc_state-Arena Header- 단일 스레드 arena는 여러개의 힙을 가질 수 있지만, 이러한 모든 힙에 대해서는 오직 하나의 arena header만이 존재한다. Arena header는 bin, top chunk, last remainder chunk 등에 대한 정보를 가진다.
malloc_chunk-Chunk Header-힙은 사용자의 요청을 기반으로 다수의 청크로 분열된다. 그리고 각 청크는 각자의 청크 헤더를 가진다.
*Main arena는 여러개의 힙과 heap_info 구조체를 가질 수 없다. main arena의 공간이 부족한 경우, sbrk 힙 영역은 메모리가 매칭된 영역까지 확장된다.
*thread_arena와 달리 main_arena는 arena header는 sbrk 힙 영역의 일부가 아니다. main arena는 전역 변수이며, libc.so의 데이터 영역에서 찾을 수 있다.
여러 개의 힙 영역
청크!
청크는 힙 영역에서 찾을 수 있으며, 아래 중 하나의 타입을 가진다.
1. Allocated chunk
2. Free chunk
3. Top chunk
4. Last Remainder chunk
Allocated Chunk
prev_size: 만일 이전 청크를 해제하는 경우, 이 필드는 이전 청크의 크기를 저장한다. 만일 이전 청크가 할당된 경우에는, 이 필드는 이전 청크의 사용자 데이터를 저장한다.
size: 이 필드는 할당된 청크의 크기를 저장한다. 이 필드의 맨 끝 3bit는 flag 정보를 저장한다.
PREV_INUSE(P): 이 비트는 이전 청크가 할당된 경우 세트된다.
IS_MMAPPED(M): 이 비트는 현재 청크가 mmap을 통해 할당된 경우 세트된다.
NON_MAIN_ARENA(N): 이 비트는 현재 청크가 thread arena에 위치하는 경우 세트된다.
*malloc_chunk의 다른필드(fd, bk)는 할당되어 있는 청크에서는 사용하지 않는다. 따라서 할당되어 있는 청크는 사용자 데이터가 저장되어 있다.
*사용자가 요청한 크기는 malloc_chunk를 저장하고 메모리를 정렬하기 위해서는 약간의 공간이 여분으로 필요하기 때문에 사용할 수 있는 크기(청크 내부를 나타내는 크기)로 변환된다.
Free Chunk
prev_size: 2개의 free chunk는 함꼐 붙어 있을 수 없다. 각 청크를 해제하는 경우, 하나의 단일 free chunk로 결합된다. 따라서 항상 해제된 청크의 이전 청크를 할당하고 있어서, prev_size는 이전 청크의 사용자 데이터를 저장하고 있다. Hence always previous chunk to this freed chunk would be allocated and therefore prev_size contains previous chunk’s user data.
size: 이 필드는 free chunk의 크기를 저장하고 있다.
fd: Forward pointer- 동일한 빈에서의 다음 청크를 가리킨다. (물리 메모리에서의 다음 청크가 아니다!)
bk: Backward pointer- 동일한 빈에서의 이전 청크를 가리킨다. (물리 메모리에서의 이전 청크가 아니다!)
Bins
Bin은 freelist data structures이며, free chunk들을 수용하는데 사용한다. 청크의 크기를 기준으로 사용가능한 bin이 달라지게 된다
-Fast bin
-Unsorted bin
-Small bin
-Large bin
fastbinsY - 이 배열은 fast bin을 수용한다.
bins - 이 배열은 unsorted, small, large bin을 수용한다. 총 126개의 bin이 있고 다음과 같은 기준으로 나뉜다.
Bin1: Unsorted bin
Bin2~Bin63: Small bin
Bin64~Bin126: Large bin
Fast Bin
청크의 크기가 16~80바이트인 경우, fast chink라고 부른다. fast chunk를 수용한 bin을 fast bin이라고 부른다. 모든 bin들 중 가운데, fast bin은 메모리 할당과 반납(해제)가 빠르다.
bin의 갯수: 10개
각 fast bin은 free chunk로 구성된 단일 연결리스트를 가진다. 단일 연결리스트는 list의 중간으로부터 fast bin chunk를 제거할 수 없기 때문에 사용된다. 추가와 제거는 list의 앞쪽 끝에서 발생한다. - LIFO
청크의 크기: 각 8바이트씩
Fast bin은 각 8바이트 크기를 가지는 청크의 bin list를 가진다. ex)첫번째 fast bin(index 0)은 16바이트 크기의 청크 bin list를 가지며, 두번째 fast bin(index 1)은 24바이트 크기의 청크 bin list를 가지는 식으로 이어진다.
fast bin 내부의 청크는 동일한 크기이다.
malloc 초기화에서 fast bin의 최대 크기는 64바이트로 세트되어 있다. 기본 청크의 크기는 16~64인 경우, fast chunk로 분류된다.
병합 없음-해제된 2개의 청크가 서로 인접해있을 수 있으며, 단일 free chunk로 결합되지 않는다. 병합이 없다는 것은 외부 단편화라는 결과를 가져올 수 있지만 해제의 속도가 빠르다는 장점도 있다.
malloc(fast chunk)->When malloc is called return chunk1
초기의 fast bin의 최대 크기와 fast bin 인덱스는 비어있기 때문에, 사용자가 fast chunk를 요청하더라도 fast bin code 대신 small bin code가 서비스할 수 있다. 이후에 비어있지 않게 된 경우, fast bin 인덱스는 해당하는 binlist로부터 검색을 하여 계산된다. 위에서 반환된 binlist의 첫 번째 청크는 삭제된 후, 사용자에게 반환된다.
free(fast chunk)->When chunk is freed, insert chunk
fast bin 인덱스는 해당하는 binlist로부터 검색을 하여 계산된다. free chunk는 위에서 반환된 binlist의 앞쪽 위치에 추가된다.
Unsorted Bin
small 또는 large chunk는 각각의 bin에서 추가가 아닌 해제되는 경우, unsorted bin에 추가된다. 이러한 처리방법은 최근에 해제된 청크를 재사용할 수 있도록 glibc malloc가 2번째 기회를 제공하기 위해서 있다. 따라서 적절한 bin을 찾는데 걸리는 시간이 적기 때문에 메모리 할당과 반납의 비트처리속도가 빠르다.
Unsorted bin은 free chunk의 환형 이중 연결리스트를 가진다. 청크의 크기에 제한이 없기 때문에 다양한 크기의 청크가 이 bin에 저장될 수 있다.
bin의 갯수 1개
Small Bin
청크의 크기가 512바이트보다 작은 경우, small chunk라고 부른다. small chunk를 수용한 bin을 small bin이라고 부른다. small bin은 메모리 할당 및 반환이 large bin보다 빠르다(다만 fast bin보다는 느리다)
bin의 갯수 62개
각 small bin은 free chunk로 구성된 환형 이중 연결리스트를 가진다. 이중 연결리스트는 list의 중간에서 small bin chunk를 제거할 수 있기 때문에 사용된다. 노드의 추가는 앞쪽 끝에서 발생하고 삭제는 list의 뒤쪽 끝에서 발생한다.-FIFO
Chunk Size – 8 bytes apart
- Small bin contains a binlist of chunks whose sizes are 8 bytes apart. ie) First Small bin (Bin 2) contains binlist of chunks of size 16 bytes, second small bin (Bin 3) contains binlist of chunks of size 24 bytes and so on…
- Chunks inside a small bin are of same sizes and hence it doesnt need to be sorted.
병합: 해제된 2개의 청크는 각각 인접해 있을 수 없으며, 단일 free chunk로 결합된다. 병합은 외부 단편화를 제거하지만, 해제의 속도가 느리다.
malloc(small chunk): 초기의 모든 small bin은 NULL이기 때문에, 사용자가 small chunk를 요청했더라도 small bin code대신 unsorted bin code가 서비스할 수 있다. 또한 malloc을 처음 호출할 경우, small bin과 large bin의 bins는 malloc_state는 초기화되어있기 때문에 찾을 수 있다.
이후에 small bin이 비어있지 않은 경우, 해당하는 binlist의 마지막 청크는 제거된 후, 사용자에게 반환된다.
free(small chunk): 이 청크를 해제하는 동안, 이전 또는 다음 청크가 해제되었는지 체크하여, 해제된 경우 병합한다.
ex) 각각의 연결리스트로부터 청크를 제거하고 unsorted bin의 연결리스트의 시작 부분에 새롭게 합병된 청크를 추가한다.
Large Bin
청크의 크기가 512바이트와 같거나 큰 경우, large chunk라고 부른다. large chunk를 수용한 Bin을 large bin이라고 부른다. Large bin은 메모리 할당 및 반환이 small bin보다 느리다.
bin의 개수: 63개
Out of these 63 bins:
- 32 bins contain binlist of chunks of size which are 64 bytes apart. ie) First large bin (Bin 65) contains binlist of chunks of size 512 bytes to 568 bytes, second large bin (Bin 66) contains binlist of chunks of size 576 bytes to 632 bytes and so on…
- 16 bins contain binlist of chunks of size which are 512 bytes apart.
- 8 bins contain binlist of chunks of size which are 4096 bytes apart.
- 4 bins contain binlist of chunks of size which are 32768 bytes apart.
- 2 bins contain binlist of chunks of size which are 262144 bytes apart.
- 1 bin contains a chunk of remaining size.
small bin과 달리 large bin 내부의 청크는 동일한 크기를 가지고 있지 않다. 따라서 내림차순으로 저장된다. 가장 큰 청크는 binlist의 가장 앞쪽에 저장되고, 가장 작은 청크는 binlist의 가장 뒷쪽에 저장된다.
병합: 해제된 2개의 청크는 각각 인접해 있을 수 없으며, 단일 free chunk로 결합된다.
malloc(large chunk): 초기의 모든 large bin은 NULL이기 때문에, 사용자가 large chunk를 요청했더라도, large bin code 대신, next largest bin code가 서비스할 수 있다.
또한 malloc 처음 호출할 경우, small bin과 large bin의 bins는 malloc_state는 초기화되어 있기 떄문에 찾을 수 있다.
이후에 large bin이 비어있지 않은 경우에서 largest chunk의 크기가 사용자가 요청한 크기보다 크다면, binlist를 뒷쪽 끝부터 앞쪽 끝까지 확인하여, 사용자가 요청한 크기에 가깝거나 같은 적합한 크기의 청크를 찾는다. 찾게 되면, 해당 청크는 2개의 청크로 분리된다.
User chunk(사용자가 요청한 크기)-사용자에게 반환
Remainder chunk(나머지 크기)-Unsorted bin에 추가
만일 largest chunk의 크기가 사용자가 요청한 크기보다 작다면, 비어있지 않은 다음 largest bin을 사용하여 사용자의 요청에 응답한다. 다음 largest bin code는 비어있지 않은 다음 largest bin을 찾기 위해 binmaps을 스캔하여, 해당하는 bin을 찾은 경우, 해당 binlist에서 적합한 청크가 검색되고, 적합한 청크를 분리하여 사용자에게 반환된다. 만일 찾지 못한 경우에는 top chunk를 사용하여 사용자의 요청에 응답한다.
free(large chunk)-free(small chunk)와 비슷
Top Chunk
arena의 가장 꼭대기 가장자리에 있는 청크를 top chunk라고 부른다. Top Chunk는 어떤 bin에도 속하지 않는다. Top Chunk는 bin들 중 하나에서 해제된 블럭이 없는 경우, 사용자의 요청에 응답하기 위해 사용된다. 만일 top chunk 가 사용자가 요청한 크기보다 큰 경우, top chunk는 2개로 분리된다.
User chunk(사용자가 요청한 크기)
Remainder Chunk(나머지 크기)
remainder chunk는 새로운 꼭대기가 된다. 만일 top chunk의 크기가 사용자가 요청한 크기보다 작은 경우 sbrk(main arena) 또는 mmap(thread arena) syscall을 사용하여 top chunk를 확장시킨다.
Last Remainder Chunk
Remanider는 요청에 의해 너무 작게 분할되어 만들어진다. Last remainder chunk는 지역 참조성을 증가시키는데 도움을 준다.
사용자가 작은 청크를 요청헀는데, small bin과 unsorted bin으로 제공할 수 없는 경우 binmaps는 비어있지 않는 다음 largest bin을 찾기 위해 스캔된다. 무사히 비어있지 않는 다음 largest bin을 찾은 경우 2개로 분리되어 user chunk는 사용자에게 반환되고, remainder chunk는 unsorted bin에 추가된다. 이 추가로 새로운 last remainder chunk가 생겼다.
'시스템 해킹 > HEAP' 카테고리의 다른 글
| Use After Free (0) | 2018.02.16 |
|---|---|
| malloc free 실습 fastbin unsortbin 정리! (0) | 2018.02.16 |
| Fast bin (0) | 2018.02.16 |
| Top Chunk (0) | 2018.02.16 |
| Unsorted bin (0) | 2018.02.16 |
