[ptmalloc] 리눅스 동적할당 heap 하게 공부하자 (2) : Boundary Tag, Binning편

그 충분히 다른 블로그 참고하고 왔을 거 같아서 Binning은 기본적인 요소보다는 중요한 포인트만 갖고 왔습니다.

 

Boundary Tag

메모리 청크(블록이라고 표현하는게 맞을 수도) 경계를 식별하고 관리하기 위한 메커니즘이다.

-> 청크의 헤더 정보를 다음 청크에 복사하는 식으로 관리한다.

그러면 어떤 일이 발생하냐면, 청크의 앞뒤 정보를 빠르게 확인할 수 있다. 그러면 인접한 청크들이 free된다면 병합을 할 수 있다! 그러면 메모리 관리가 효율적이다!

 

Boundary Tag 메커니즘이 heap에서 장점들이 Chaining된다

 

+--------+--------------------+--------+
| Header |      Payload       | Footer | <-- 여기서는 Footer를 next chunk의 header로 대체
+--------+--------------------+--------+

 

사실 dlmalloc에서 Boundary Tag는 완벽한 개념이 아니다.
Boundary Tag 자체는 Header, Footer를 갖고 있지만, 실제로 dlmalloc 알고리즘에서는 Header만으로 관리된다. 사실상 Footer는 다음 청크의 Header로 충분히 대체할 수 있기 때문이다.

 

 

할당 해제를 하고 free된 청크들을 합병할 때 이전 청크의 헤더를 알아야 한다.

 

그러면 이제 시각화 자료를 보자.

-> 카네기 멜런 대학의 PPT 자료를 인용했다. 

https://www.cs.cmu.edu/afs/cs/academic/class/15213-s12/www/lectures/18-allocation-basic-1up.pdf

 

 

여기서 p1~p4는 모두 본인의 데이터 크기 + 청크의 헤더(0x10)만큼 포함되어있다고 가정하자.

 

만약 여기서 free(p2)가 된다면 다음 인접한 위치에 있는 p3의 prev_size는 p2의 size를 저장하게 된다.

걍 그림으로 그려보자면 이렇다.

 

 

그러면 Boundary Tag를 통해 청크를 어떻게 관리해요?

 

쨔쨘!!!@@@@@

B청크 기준으로 보았을 때 이전 청크를 B청크 주소에서 prev_size를 빼주면!

할당해제된 A청크의 주소를 알 수 있습니다.

 

C청크의 주소를 알기 위해선 B청크의 주소에 size를 더해주면 됩니다.

 

그러면 A -> B -> C -> D로 할당된 청크가 있다면, Boundary Tag로 의해

addr(B) = addr(A) + size(A)

addr(C) = addr(B) + size(B)

addr(D) = addr(C) + size(C)

 

해당 메커니즘으로 추후 청크를 해제하고 해제된 청크들을 병합할 때 계산이 용이하다

 

 

 

시스템 해킹 관점

그러면 하나 더! 해커의 관점에서 생각해봅시다.

 

prev_size를 조작하면 이전 청크의 위치를 조작할 수 있지요.

size를 조작하면 다음 청크의 위치를 조작할 수 있지요.

prev_inuse bit를 조작하면 이전 청크의 할당/해제 여부를 조작할 수 있지요.

 

좋습니다. 이러한 행위로 다음에 작성할 exploitation이 나오는겁니다.

 

Binning

메모리 블록을 청크별로 나누어 할당과 해제 시 성능을 향상시키기 위한 메커니즘이다.

메모리 조각화 줄이기, 할당 요청 빠르게 응답하기에 초점 맞춰져있다.

 

이름도 귀엽다.

 

Fast bin, Small bin, Large bin

 

 

unsorted bin은 다양한 청크를 사용하기 전에 잠깐 저장했다두는 곳으로 생각하자. 

 

Bin	Fast bin	Large bin	Small bin	Unsorted bin
청크 크기	< 64 (32bits) < 128 (64bits)	>= 512	< 512	유동적
개수	10	63 (64 ~ 126)	62 (2  ~63)	1
입출력	LIFO	FIFO	FIFO	FIFO
list 알고리즘	single linked list	double linked list	double linked list	double linked list
fit 알고리즘	exact fit	best fit	exact, best fit	exact fit

 

 

Fast bin 주요점

서로 다른 크기를 갖는 10개의 청크가 singled linked list로 관리된다!

해제되어도 다음 청크의 prev_inuse (P)가 변경되지 않는다!

즉, Fast bin은 인접한 청크와 병합하지 않음.

 

Small bin 주요점

서로 다른 크기를 갖는 62개의 청크가 double linked list로 관리된다!

해제되면 뒤 청크의 prev_inuse bit가 변경된다.

즉, 인접한 freed 청크와 병합된다.

 

Large bin

서로 다른 크기를 갖는 63개의 청크가 double linked list로 관리된다!

fd, bk말고 fd_nextsize, bk_nextsize가 추가됐는데

 

Large bin은 small/fast bin처럼 정확한 크기 단위로 계산되는게 아닌, 청크의 크기를 범위 단위로 관리한다.

 

범위 내에서 가장 큰 사이즈를 갖는 청크가 가장 앞으로 오게 된다.

 

해제되면 뒤 청크의 prev_inuse bit가 변경된다. -> 인접한 freed 청크와 병합

 

Unsorted bin

들어가는 경우

1. small / large bin에 들어갈 사이즈가 해제된 경우 : small / large bin에 들어가기 전 들어간다.

2. fast bin이 병합될 경우 : fast bin은 prev_inuse가 바뀌지 않아 병합되지 않지만, 큰 청크의 요청을 받았을 때는 예외로 청크가 병합된다.

3. best fit으로 할당된 청크의 남은 부분 : 0x100만큼 free된 다음 사용자가 0x80만큼 할당하면 남은 0x20은 unsorted bin으로 들어감

4. 인접한 청크가 이미 free되어 병합된 경우

 

나오는 경우

사용자가 특정 사이즈를 할당했는데 요청한 사이즈와 동일한 청크가 있을 경우 : free(0x40) -> malloc(0x40)

 

 

지금까지 배운거로 consolidate, unlink를 한다

인접한 청크끼리 free 된다면 병합(consolidate)된다.

 

 

 

unlink는 bin list에 등록된 청크를 제거하기 위해 fd, bk를 정리한다.

이 경우 A-B-C에서 A-C이니 A의 bk의 C의 fd가 수정된다.

 

 

어렵게 분석하는 글이 많은데 이 포스팅엔 간단하고 중요하다 생각하는 것만 들고 와서 다른 설명도 많이 참고하면 좋다.

 

여기에 있는 모든 것들이 나중엔 vulnerability가 되어 heap을 exploit한다.

다음엔 heap exploitation으로 들고 오겠다!