oiehso0

이 기술은 glibc의 allocator의 first-fit 동작을 설명한다.

모든 청크(fastbin 제외)가 free될 때마다 unsorted bin에서 끝난다.

삽입은 리스트의 HEAD에서 일어난다. fastbin을 제외하고 새로운 청크를 요청할때, small bin이 비어있을 때 처음에 unsorted bin에서 찾는다.

이 조회는 TAIL에서 일어난다. 

만약 unsorted bin에 필요한 크기의 청크가 있다면 사용하겠지만, 요청된 크기보다 큰 청크가 존재할때 두개로 분할되어 반환된다. 이렇게 하면 FIFO 구조가 된다.

char *a = malloc(300);    // 0x***010
char *b = malloc(250);    // 0x***150

free(a);

a = malloc(250);          // 0x***010

unsorted bin에서 free와 malloc은 아래와 같이 진행된다.

1. 'a'가 free된다.

head -> a -> tail

2. 'malloc'이 요청된다.

head -> a2 -> tail ['a1' is returned]

'a' chunk는 'a1' , 'a2'로 나눠진다.  요청된 크기(250바이트)는 'a'(300바이트)보다 작아서.

이과정은 _int_malloc에서도 해당된다. 그리고 fastbin의 경우에도 마찬가지이다. 

unsorted bin에서 free되는 대신에, fasbin에서 fast chunk는 끝난다. 앞에서 언급 했듯이, fastbin은 single linked list를 가지고 있어 

HEAD에서 추가와 삭제가 이루어진다. 그래서 fastbin은 FILO구조를 같는다.(?)

char *a = malloc(20);     // 0xe4b010
char *b = malloc(20);     // 0xe4b030
char *c = malloc(20);     // 0xe4b050
char *d = malloc(20);     // 0xe4b070

free(a);
free(b);
free(c);
free(d);

a = malloc(20);           // 0xe4b070
b = malloc(20);           // 0xe4b050
c = malloc(20);           // 0xe4b030
d = malloc(20);           // 0xe4b010

deferred coalescing

fastbin에서의 free, malloc 진행

1. 'a'가 free됨

head -> a -> tail

2. 'b' free됨

head -> b -> a -> tail

3. 'c' free됨

head -> c -> b -> a -> tail

4. 'd' free됨

head -> d -> c -> b -> a ->tail

5. malloc 요청 

 d, c, b, a순으로 return됨

20byte의 작은 청크는 unsortedbin 대신에 fastbin으로 들어간다.

Use after Free Vulnerability

위의 예제에서 malloc은 이전에 사용되었고 free된 청크를 return하는 것을 알 수 있었다. 결국 free된 메모리 청크의 재사용은 취약할 수 있다. 청크가 free되면 공격자는 청크 내부의 데이터를 제어 할 수 있다는 뜻이 된다. 

av는 arena ptr(Main or Thread), bytes는 사용자가 요청한 크기

unlink

1. 청크 크기가 다음 청크에 설정된 prev_size와 같은지 // corrupted size vs prev_size

2. FD->bk != P || BK->fd != P // corrupted double-linked list

여기서 p는 unlink 되어지는 청크

fake chunk

참고 : https://www.lazenca.net/display/TEC/unsafe+unlink

_int_malloc

1. fastbin에서 첫 번째 청크를 제거하는 동안, 청크의 크기가 fastbin 의 청크 사이즈 범위에 속하는지 확인 // malloc() : memory corruption(fast)

2. small bin으로부터 마지막 청크(victim)를 제거하는 동안 victim -> bk -> fd 와 victim이 같은지 확인 // malloc() : smallbin double linked list corrupted

3. unsorted bin에서 반복하는 동안, 현재 청크의 사이즈가 최소(2*SIZE_SZ)와 최대(av -> system_mem) 범위 내에 있는지 확인 // malloc() : memory corruption

4. 마지막 remainder chunk를 unsorted bin에 넣는 동안(large chunk를 분할 한 후)에 unsorted_chunks(av) -> fd -> bk == unsorted_chunks(av)인지 확인 // malloc() : corrupted unsorted chunks

 _int_free

1. P가 P+chunksize(P)보다 앞에 있는지 확인(to avoid wrapping) ?? // free() : invalid pointer

여기서 P는 free된 청크 

2. chunk가 최소 MINISZE 크기인지 또는 MALLOC_ALIGNMENT의 배수인지 확인 // free() : invalid size

3. fastbin 범위의 크기를 가진 chunk의 경우, 다음 청크의 크기가 최소와 최대(av -> system_mem)사이의 크기에 있는지 확인 // free() : invalid next size(fast)

4. fast chunk를 fastbin(HEAD)에 넣을때 HEAD에 이미 있는 청크와 동일하지 않은지 확인 // double free or corruption(fasttop)

5. fastbin에 fast chunk를 넣을때(HEAD에), HEAD에 있는 청크의 크기와 삽입 될 청크의 크기가 같은지 확인 // invalid fastbin entry(free)

6. chunk가 fastbin의 크기 범위에 있지 않고 mmapped chunks도 아닌 경우, top chunk와 같은지 확인 // double free or corruption(top)

7. next chunk가 아레나의 범위 안에 있는지 확인한다. // double free or corruption (out)

8. 다음 청크의 prev_inuse 비트가 표시되어 있는지 확인 // double free or corruption(!prev)

9. next chunk의 크기가 최소와 최대(av -> system_mem) 사이즈 사이에 있는지 확인 // free() : invalid next size(normal)

10. unsorted bin에 병합된 청크를 삽입하는 동안 unsorted_chunks(av) -> fd -> bk == unsorted_chunks(av)인지 확인 // free() : corrupted unsorted chunks