Background : ptmalloc2

Memory Allocator

• 한정된 메모리 자원을 각 프로세스에 효율적으로 배분
• 리눅스 : ptmalloc2
  구글 : tcmalloc
  페이스북/파이어폭스 : jemaloc
• ptmalloc2는 어떤 메모리가 해제되면, 해제된 메모리의 특징을 기억하고 있다가 비슷한 메모리의 할당 요청이 발생하면 이를 빠르게 반환해 준다.
• ptmalloc2는 동적 메모리를 관리하는 리눅스의 핵심 알고리즘이며ㅡ , 이와 관련하여 과거부터 다양한 공격 기법이 연구되었고, 새로운 보호기법도 탄생하였다.
• ptmalloc2가 구현된 GLibc의 버전에 따라 적용할 수 있는 공격 기법에 큰 차이가 생긴다.

ptmalloc2

• 리눅스에서 사용되는 Memory Allocator, GLibc에 구현되어 있다.

• 메모리의 효율적인 관리

  • 메모리 낭비 방지
    • 메모리 할당 요청이 발생하면, 먼저 해제된 메모리 공간 중에서 재사용 가능한 공간을 탐색
    • 같은 크기의 공간이 있다면, 이를 그대로 재사용
    • 작은 크기의 할당 요청이 발생했을 때, 해제된 메모리 공간 중 매우 큰 메모리 공간이 있으면 그 영역을 나누어 주기도 함
  • 빠른 메모리 재사용
    • 특정 메모리 공간을 해제한 후 이를 빠르게 재사용하려면 해제된 메모리 공간의 주소를 기억하고 있어야 함
    • ptmalloc은 메모리 공간을 해제할 때 tcache 혹은 bin이라는 연결리스트에 해제된 공간의 정보를 저장해 둠
  • 메모리 단편화 방지
    • 내부 단편화 : 할당한 메모리 공간의 크기에 비해 실제 데이터가 점유하는 공간이 적을 때
    • 외부 단편화 : 할당한 메로리 공간들 사이에 공간이 많아서 발생하는 비효율
    • 공간을 해제하고 재사용할 때, 정확이 같은 크기의 할당 요청이 발생할 확률보다 비슷한 크기의 요청이 발생할 확률이 높음
      • 따라서 비슷한 크기의 요청에 대해서는 모두 같은 크기의 공간을 반환
    • ptmalloc은 단편화를 줄이기 위해 정렬, 병합, 분할을 사용함
      • 정렬 : 64비트 환경에서 메모리 공간을 16바이트 단위로 할당
      • 병합 : 특정 조건을 만족하면 해제된 공간들을 병합
      • 분할 : 병합된 메모리 공간이 이후의 할당 요청에 의해 분할

• ptmalloc의 객체

  • 청크 : ptmalloc이 할당한 메모리 공간, 헤더와 데이터로 구성

  이름	크기	의미
  prev_size	0x8 bytes	인접한 직전 청크의 크기, 청크를 병합할 때 직전 청크를 찾는 데 사용
  size	0x8 bytes	현재 청크의 크기, 헤더의 크기도 포함한 값
  flag	0x3 bits	size의 하위 3비트를 청크 관리에 필요한 플래그 값으로 사용, 각 플래그는 순서대로 allocated arena, mmap'd, prev-in-use prev-in-use 플래그는 직전 청크가 사용중인지를 나타내므로, 이 플래그를 참조하여 병합 여부를 판단
  fd	0x8 bytes	연결 리스트에서 다음 청크의 주소 (해제된 청크에만 존재)
  bk	0x8 bytes	연결 리스트에서 이전 청크의 주소 (해제된 청크에만 존재)

  

  • bin : 사용이 끝난 청크들이 저장되는 객체
    small bin[62], large bin[63], unsorted bin[1], unused[2]
    • small bin : 32바이트 이상 1024 바이트 미만의 크기를 갖는 청크들이 보관되는 곳
      • index가 증가하면 저장되는 청크들의 크기가 16바이트씩 증가
        smallbin[0]=32bytes, smallbin[61]=1008bytes
      • 원형 이중 연결 리스트, FIFO 구조
      • unlink : small bin에 청크를 추가하거나 꺼낼 때 연결을 끊는 과정
      • small bin의 청크들은 병합 대상
        메모리상에서 인접한 두 청크가 해제되어 있고, 이들이 small bin에 들어있으면 병합
        → consolidation
    • fast bin : 32바이트 이상 176바이트 이하의 청크들이 보관되는 곳
      • 메모리 단편화보다 속도를 더 우선순위로 두는 bin
      • 리눅스에서는 32~128바이트 이하의 청크들을 fast bin에 저장
      • 단일 연결 리스트, LIFO 구조 → unlink의 과정이 필요없음
      • 병합 과정이 없음(병합에 사용되는 연산도 아끼기 위함)
    • large bin : 1024바이트 이상의 크기를 갖는 청크들이 보관되는 곳
      • index가 증가하면 저장되는 청크의 크기가 로그적으로 증가
        largebin[0]은 1024~1088, largebin[32]는 3072~3584
      • 이중 연결 리스트, FIFO 구조, 내부적으로 크기 내림차순 정렬
      • 범위에 해당하는 모든 청크를 보관하기 때문에, 재할당 요청이 발생했을 때 그 안에서 크기가 가장 비슷한 청크를 꺼내 재할당+unlink
      • 연속된 large bin 청크는 병합 대상
    • unsorted bin : 분류되지 않은 청크들이 보관되는 곳
      • fastbin에 들어가지 않는 모든 청크들은 일단 unsorted bin에 보관
      • 원형 이중 연결 리스트, 내부적으로 정렬되진 않음
      • smallbin 크기에 해당하는 청크를 할당 요청하면, fastbin/smallbin을
        탐색하고 unsorted bin을 탐색
      • unsorted bin에서 적절한 청크가 발견되면 해당 청크를 꺼내어 사용
        이 과정에서 탐색된 청크들은 크기에 따라 적절한 bin(small, large)으로 분류
  • arena : fastbin, smallbin, largebin 등의 정보를 모두 담고 있는 객체
    • 레이스 컨디션을 막기 위해 arena에 접근할 때 arena에 락을 적용
      • 레이스 컨디션은 어떤 공유 자원을 여러 쓰레드나 프로세스에서 접근할 때 발생하는 오동작을 말함
      • 한 쓰레드에서 어떤 공유 자원에 락을 걸면, 그 공유 자원을 이용하려는 다른 쓰레드는 락이 해제될 때까지 대기
      • 쓰레드를 무제한으로 대기시키기 때문에, 구현을 잘못하거나 쓰레드의 수가 과다하게 많아지면 병목 현상을 일으킬 수 있으며, 여러 쓰레드가 서로 물리고 물려서 어떤 쓰레드도 락을 해제하지 못하는 데드락(Deadlock)이 발생할 수 있음
    • 병목 현상의 방지를 위해 최대 64개의 arena 생성 가능
    • arena에 락이 걸려서 대기해야 하는 경우, 새로운 arena를 만들어 이를 피할 수 있음
    • 과도한 멀티 쓰레드 환경에서는 결국 병목 현상이 발생하므로, tcache가 도입됨
  • tcache : thread local cache, 각 쓰레드에 독립적으로 할당되는 캐시 저장소
    • 각 쓰레드는 64개의 tcache를 가짐
    • 단일 연결리스트, LIFO 구조
    • 쓰레드마다 정의되는 tcache의 특성상 메모리 낭비 가능성이 있으므로
      하나의 tcache는 같은 크기의 청크들만 보관(리눅스는 각각 7개로 제한)
    • 32~1040 바이트의 청크들이 보관
    • 이 범위에 속하는 청크들은 할당 및 해제될 때 tcache를 가장 먼저 조회
      tcache가 가득 찼을 경우 적절한 bin으로 분류
    • arena의 bin에 접근하기 전에 tcache를 먼저 사용하므로 레이스 컨디션을 고려하지 않아도 되며, arena에서 발생할 수 있는 병목 현상을 완화하는 효과가 있음
    • tcache는 보안 검사가 많이 생략되어 있어 힙 익스플로잇의 좋은 도구로 활용되고 있음