Backgorund: ptmalloc2
1. ptmalloc2
1) ptmalloc2 (pthread malloc 2)
- 리눅스에서 사용됨
- GLibc에 구현되어 있음
- 사용 목표 : 메모리의 효율적인 관리
① 메모리 낭비 방지
② 빠른 메모리 재사용
③ 메모리 단편화 방지
2) 메모리 낭비 방지
- 메모리의 동적 할당과 해제는 매우 빈번하게 발생하지만 컴퓨터 전체 메모리는 한정적이므로 메모리를 무한히 할당할 수 없음
- 메모리 할당 요청이 발생 시, ptmalloc은 먼저 해제된 메모리 공간 중에서 재사용할 수 있는 공간이 있는지 탐색함
- 해제된 메모리 공간 중에서 요청된 크기와 같은 크기의 메모리 공간이 있다면 이를 그대로 재사용
3) 빠른 메모리 재사용
- 가상 메모리 공간은 매우 넓어, 특정 메모리 공간을 해제한 후 이를 재사용하려면 해제된 메모리 공간의 주소를 기억하고 있어야 함
-> ptmalloc은 메모리 공간을 해제할 때, tcache 또는 bin에 해제된 공간의 정보를 저장
4) 메모리 단편화 방지
- 내부 단편화 : 할당한 메모리 공간의 크기에 비해 실제 데이터가 점유하는 공간이 적을 때 발생
- 외부 단편화 : 할당한 메모리 공간 사이에 공간이 많아서 발생
- 단편화가 심해질수록 메모리 사용 효율 감소
- 단편화를 줄이기 위해 ptmalloc은 정렬, 병합, 분할을 사용
2. ptmalloc의 객체
1) 청크
- 청크(Chunk) : ptmalloc이 할당한 메모리 공간
- 청크 = 헤더 + 데이터
- 헤더 : 청크 관리에 필요한 정보를 담고 있음
- 데이터 : 사용자가 입력한 데이터 저장
- 헤더는 청크의 상태를 나타내므로 사용 중인 청크(in-use)의 헤더와 해제된 청크(freed)의 헤더는 구조가 다소 다름
- 사용 중인 청크는 fd와 bk를 사용하지 않고, 그 영역에 사용자가 입력한 데이터를 저장함
| 이름 | 크기 | 의미 |
| prev_size | 8 btye | 인접한 직전 청크의 크기. 청크를 병합할 때 직전 청크를 찾는 데 사용됩니다. |
| size | 8 btye | 현재 청크의 크기. 헤더의 크기도 포함한 값입니다. 64비트 환경에서, 사용 중인 청크 헤더의 크기는 16바이트이므로 사용자가 요청한 크기를 정렬하고, 그 값에 16바이트를 더한 값이 됩니다. |
| flgs | 3 bit | 64비트 환경에서 청크는 16바이트 단위로 할당되므로, size의 하위 4비트는 의미를 갖지 않습니다. 그래서 ptmalloc은 size의 하위 3비트를 청크 관리에 필요한 플래그 값으로 사용합니다. 각 플래그는 순서대로 allocated arena(A), mmap’d(M), prev-in-use(P)를 나타냅니다. prev-in-use 플래그는 직전 청크가 사용 중인지를 나타내므로, ptmalloc은 이 플래그를 참조하여 병합이 필요한지 판단할 수 있습니다. |
| fd | 8 btye | 연결 리스트에서 다음 청크를 가리킴. 해제된 청크에만 있습니다. |
| bk | 8 btye | 연결 리스트에서 이전 청크를 가리킴. 해제된 청크에만 있습니다. |
- 청크의 구조
2) bin
- bin : 사용이 끝난 청크들이 저장되는 객체
- 메모리의 낭비를 막고, 해제된 청크를 빠르게 재사용할 수 있게 함
- ptmalloc에는 총 128개의 bin이 정의되어 있음
- 이 중 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin, 나머지 2개는 사용되지 않음
3) smallbin
- 32 바이트 이상, 1024 바이트 미만의 크기를 갖는 청크들이 보관됨
- 하나의 smallbin에는 같은 크기의 청크들만 보관됨
- 인덱스값이 증가하면 저장되는 청크들의 크기는 16 바이트씩 커짐
ex. smallbin[0]은 32 바이트 크기의 청크를, smallbin[61]은 1008 바이트 크기의 청크를 보관
- smallbin은 원형 이중 연결 리스트이며, FIFO 방식
- 이중 연결 리스트 특성상, smallbin에 청크를 추가하거나 꺼낼 때 연결고리를 끊는 과정이 필요 (unlink 과정)
- smallbin의 청크들은 ptmalloc의 병합 대상
- 메모리 상에서 인접한 두 청크가 해제되어 있고, 이들이 smallbin에 들어있으면 이 둘은 병합됨 (consolidation 과정)
- smallbin의 할당 및 해제, 병합 과정
4) fastbin
- 32 바이트 이상, 176 바이트 이하 크기의 청크들이 보관됨
- 16 바이트 단위로 총 10개
- 리눅스는 이 중에서 작은 크기부터 7개의 fastbin을 사용
- fastbin은 단일 연결 리스트이며, LIFO 방식
- 청크를 꺼낼 때 꺼낸 청크의 앞, 뒤를 연결하는 unlink 과정이 필요x
- fastbin에 저장되는 청크들은 서로 병합x
- fastbin의 할당 및 해제 과정
5) largebin
- 1024 바이트 이상의 크기를 갖는 청크들이 보관됨
- 총 63개의 largebin이 존재
- 일정 범위 안에 크기를 갖는 청크들을 모두 보관 (이 범위는 largebin의 인덱스 증가에 따라 로그적으로 증가)
ex. largebin[0]은 1024 바이트 이상, 1088 바이트 미만의 청크 보관
largebin[32]는 3072 바이트 이상, 3584 바이트 미만의 청크 보관..
- largebin은 범위에 해당하는 모든 청크를 보관
-> 재할당 요청이 발생했을 때 ptmalloc은 그 안에서 크기가 가장 비슷한 청크를 꺼내 재할당
- largebin은 이중 연결 리스트이므로 재할당 과정에서 unlink도 동반됨
- 연속된 largebin 청크들은 병합의 대상
6) unsortedbin
- 분류되지 않은 청크들을 보관하는 bin
- unsortedbin은 하나만 존재
- astbin에 들어가지 않는 모든 청크들은 해제되었을 때 크기를 구분 없이 unsortedbin에 보관됨
- unsortedbin은 원형 이중 연결 리스트
- ptmalloc은 unsortedbin을 활용하여 불필요한 연산을 줄이고, 성능을 최적화함
7) arena
- fastbin, smallbin, largebin 등의 정보를 모두 담고 있는 객체
- 멀티 쓰레드 환경에서 ptmalloc은 레이스 컨디션을 막기 위해 arena에 접근할 때 arena에 락을 적용함
- 하지만, 이 방식을 사용하면 레이스 컨디션은 막을 수 있찌만, 병목 현상을 일으킬 수 있음
cf) 레이스 컨디션 : 어떤 공유 자원을 여러 쓰레드나 프로세스에서 접근할 때 발생하는 오동작
- ptmalloc은 위의 문제를 최대한 피하기 위해 최대 64개의 arena를 생성할 수 있게 하고 있음
- arena에 락이 걸려서 대기해야 하는 경우, 새로운 arena를 생성해서 이를 피할 수 있음
8) tcache
- tcache (thread local cache) : 각 쓰레드에 독립적으로 할당되는 캐시 저장소
- 각 쓰레드는 64개의 tcache를 가지고 있음
- tcache는 fastbin과 마찬가지로 LIFO 방식으로 사용되는 단일 연결리스트이며, 하나의 tcache는 같은 크기의 청크들만 보관함
- tcache에는 32바이트 이상, 1040바이트 이하의 크기를 갖는 청크들이 보관됨
- 이 범위에 속하는 청크들은 할당 및 해제될 때 tcache를 가장 먼저 조회함
- 청크가 보관될 tcache가 가득찼을 경우에는 적절한 bin으로 분류됨
- tcache는 각 쓰레드가 고유하게 갖는 캐시이기 때문에, ptmalloc은 레이스 컨디션을 고려하지 않고 이 캐시에 접근 가능
- arena의 bin에 접근하기 전에 tcache를 먼저 사용하므로, arena에서 발생할 수 있는 병목 현상을 완화시킴
- tcache를 활용한 메모리 할당과 해제 과정
Memory Corruption: Double Free Bug
1. Double Free Bug
1) Double Free Bug (DFB)
- 같은 청크를 두 번 해제할 수 있는 버그
- 공격자에게 임의 주소 쓰기, 임의 주소 읽기, 임의 코드 실행, 서비스 거부 등의 수단으로 활용될 수 있음
- Dangling Pointer는 Double Free Bug를 유발하는 대표적 원인
- Dangling Pointer가 생성되는지, 그리고 이를 대상으로 free를 호출하는 것이 가능한지 살피면 DFB가 존재여부 확인 가능
2) Tcache Double Free
- 예제
- 같은 청크를 두 번 해제하는 예제
// Name: dfb.c
// Compile: gcc -o dfb dfb.c
#include <stdio.h>
#include <stdlib.h>
int main() {
char *chunk;
chunk = malloc(0x50);
printf("Address of chunk: %p\n", chunk);
free(chunk);
free(chunk); // Free again
}
- 실행하면 tcache에 대한 double free가 감지되어 프로그램이 종료되는 것을 확인할 수 있음
2. Mitigation for Tcache DFB - 정적 패치 분석
1) tcache_entry
- tcache에 도입된 보호 기법을 분석하기 위해, 패치된 코드의 diff를 살펴보자
//tcache_entry 구조체의 Diff
typedef struct tcache_entry {
struct tcache_entry *next;
+ /* This field exists to detect double frees. */
+ struct tcache_perthread_struct *key;
} tcache_entry;
- double free를 탐지하기 위해 key 포인터가 tcache_entry에 추가되었음을 알 수 있음
- tcache_entry는 해제된 tcache 청크들이 갖는 구조
- 일반 청크의 fd가 next로 대체되고 LIFO로 사용되므로 bk에 대응되는 값은 없음
2) tcache_put
- tcache_put은 해제한 청크를 tcache에 추가하는 함수
//tcache_put 함수의 Diff
tcache_put(mchunkptr chunk, size_t tc_idx) {
tcache_entry *e = (tcache_entry *)chunk2mem(chunk);
assert(tc_idx < TCACHE_MAX_BINS);
+ /* Mark this chunk as "in the tcache" so the test in _int_free will detect a
double free. */
+ e->key = tcache;
e->next = tcache->entries[tc_idx];
tcache->entries[tc_idx] = e;
++(tcache->counts[tc_idx]);
}
- tcache_put 함수는 해제되는 청크의 key에 tcache라는 값을 대입하도록 변경됨
- 여기서 tcache는 tcache_perthread라는 구조체 변수를 가리킴
3) tcache_get
- tcache_get은 tcache에 연결된 청크를 재사용할 때 사용하는 함수
//tcache_get 함수의 Diff
tcache_get (size_t tc_idx)
assert (tcache->entries[tc_idx] > 0);
tcache->entries[tc_idx] = e->next;
--(tcache->counts[tc_idx]);
+ e->key = NULL;
return (void *) e;
}
- tcache_get 함수는 재사용하는 청크의 key 값에 NULL을 대입하도록 변경됨
4) _int_free
- _int_free는 청크를 해제할 때 호출되는 함수
//_int_free 함수의 Diff
_int_free (mstate av, mchunkptr p, int have_lock)
#if USE_TCACHE
{
size_t tc_idx = csize2tidx (size);
-
- if (tcache
- && tc_idx < mp_.tcache_bins
- && tcache->counts[tc_idx] < mp_.tcache_count)
+ if (tcache != NULL && tc_idx < mp_.tcache_bins)
{
- tcache_put (p, tc_idx);
- return;
+ /* Check to see if it's already in the tcache. */
+ tcache_entry *e = (tcache_entry *) chunk2mem (p);
+
+ /* This test succeeds on double free. However, we don't 100%
+ trust it (it also matches random payload data at a 1 in
+ 2^<size_t> chance), so verify it's not an unlikely
+ coincidence before aborting. */
+ if (__glibc_unlikely (e->key == tcache))
+ {
+ tcache_entry *tmp;
+ LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
+ for (tmp = tcache->entries[tc_idx];
+ tmp;
+ tmp = tmp->next)
+ if (tmp == e)
+ malloc_printerr ("free(): double free detected in tcache 2");
+ /* If we get here, it was a coincidence. We've wasted a
+ few cycles, but don't abort. */
+ }
+
+ if (tcache->counts[tc_idx] < mp_.tcache_count)
+ {
+ tcache_put (p, tc_idx);
+ return;
+ }
}
}
#endif
- 위에서 22번째 줄 이후를 보면, 재할당하려는 청크의 key 값이 tcache이면 Double Free가 발생했다고 보고 프로그램을 abort 시킴
- 그 외의 보호 기법은 없으므로, 22번째 줄의 조건문만 통과하면 Double Free를 일으킬 수 있음
3. Mitigation for Tcache DFB - 동적 분석
1) 동적 분석 (실제 디버깅을 해보았으나 일부 주소값이 다르게 나와 원활한 설명을 위해 디버깅 과정은 강의안 캡쳐를 사용)
- 청크 할당 직후에 중단점을 설정하고 실행한다.
- heap 명령어로 청크들의 정보를 조회하면 아래와 같다.
- 이 중 malloc(0x50)으로 생성한 chunk의 주소는 0x555555756250
- 해당 메모리 값을 덤프하면, 아무런 데이터가 입력되지 않았음을 확인할 수 있다.
- chunk를 해제할 때까지 실행하고, 청크의 메모리를 출력하면 아래와 같다.
- chunk의 key 값이 0x555555756010로 설정된 것을 확인할 수 있다.
- 이 주소의 메모리 값을 조회하면, 해제한 chunk의 주소 0x555555756260가 entry에 포함되어 있음을 알 수 있는데,
이는 tcache_perthread에 tcache들이 저장되기 때문이다.
- 이 상태에서 실행을 재개하면 key값을 변경하지 않고, 다시 free를 호출하므로 abort가 발생한다.
2) 우회 기법
- 앞에서 언급했듯, if (__glibc_unlikely (e->key == tcache)) 만 통과하면 tcache 청크를 Double Free 시킬 수 있음
+ /* This test succeeds on double free. However, we don't 100%
+ trust it (it also matches random payload data at a 1 in
+ 2^<size_t> chance), so verify it's not an unlikely
+ coincidence before aborting. */
+ if (__glibc_unlikely (e->key == tcache)) // Bypass it!
+ {
+ ...
+ if (tmp == e)
+ malloc_printerr ("free(): double free detected in tcache 2");
+ }
+ ...
+ if (tcache->counts[tc_idx] < mp_.tcache_count)
+ {
+ tcache_put (p, tc_idx);
+ return;
+ }
}
- 즉, 해제된 청크의 key 값을 1비트만이라도 바꿀 수 있으면, 이 보호 기법을 우회할 수 있음
4. Tcache Duplication
1) Tcache Duplication
- 아래는 tcache에 적용된 double free 보호 기법을 우회하여 Double Free Bug를 트리거하는 코드
// Name: tcache_dup.c
// Compile: gcc -o tcache_dup tcache_dup.c
#include <stdio.h>
#include <stdlib.h>
int main() {
void *chunk = malloc(0x20);
printf("Chunk to be double-freed: %p\n", chunk);
free(chunk);
*(char *)(chunk + 8) = 0xff; // manipulate chunk->key
free(chunk); // free chunk in twice
printf("First allocation: %p\n", malloc(0x20));
printf("Second allocation: %p\n", malloc(0x20));
return 0;
}
- chunk가 tcache에 중복 연결되어 연속으로 재할당되는 것을 확인할 수 있음
'Security > System Hacking' 카테고리의 다른 글
| [Dreamhack System Hacking] STAGE 12 - tcache_dup2 (0) | 2022.04.05 |
|---|---|
| [Dreamhack System Hacking] STAGE 12 - 함께실습 (0) | 2022.04.05 |
| [Dreamhack System Hacking] STAGE 11 - 함께실습 (0) | 2022.04.01 |
| [Dreamhack System Hacking] STAGE 11 (0) | 2022.04.01 |
| [Dreamhack System Hacking] STAGE 10 - basic_exploitation_003 (0) | 2022.02.19 |
댓글