Pwn/Heap

Heap_기초 2

c0wb3ll ㅣ 2020. 12. 1. 18:54

Heap_기초 2

정리

오늘 정리는 힙 공부를 하면서 여기저기 많이 들려보았지만 fkillrra님의 블로그를 보고 추천영상을 받아 그것을 기초로 정리하였다.

마지막 부분에 reference를 첨부했으니 그 글을 보는 것을 추천한다.

또한 이 글은 힙에 대한 기초적인 내용의 이해를 위해 glibc_2.23버전에서 실습하였다. (ubuntu16.04)

dlmalloc의 알고리즘

boundary tag

chunk의 크기 정보가 chunk의 앞뒤에 저장
binning

재사용가능한 chunk를 크기 단위로 관리

boundary tag

각 chunk들이 할당될 때 크기 정보는 각 chunk의 size부분에 저장된다.

각 청크가 해제될 때 크기 정보가 바로 뒤 chunk의 prev_size부분에 저장된다.

위 그림을 예시로 들면 B chunk가 해제되었을 때는 바로 뒤 chunk인 C chunk에 prev_size에 B chunk의 크기 정보가 기록된다.

이를 통해 알 수 있는 정보는 allocated chunk 와 freed chunk가 존재할 때 인접한 앞/뒤 chunk의 주소를 계산할 수 있다는 점이다.

#include <stdio.h>
#include <stdlib.h>

void main(){
    char *heap1 = malloc(0x90);
    char *heap2 = malloc(0x90);
    char *heap3 = malloc(0x90);

    free(heap1);
    free(heap2);
    free(heap3);
}

이를 실제 코드를 통해 확인해 보도록 하자.

인접한 chunk가 해제되었을 때 prev_size를 이용하여 인접한 앞의 chunk의 주소 계산을 할 수 있다.

위 사진에서 보면 A chunk가 해제된 경우 B chunk의 address와 prev_size를 이용하여 A chunk의 주소를 알아낼 수 있다.

A chunk address = B chunk address - B chunk prev_size
0x1710000       = 0x17100a0       - 0xa0

또한 chunk의 size를 알고 있다면 인접한 뒤의 chunk를 알아낼 수 있다.

위 사진에서 보면 B chunk의 address와 size를 이용하여 C chunk의 주소를 알아낼 수 있다.

C chunk address = B chunk address + B chunk size
0x1710140       = 0x17100a0       + 0xa0

이것을 다른 관점으로 생각해보면

prev_size를 조작하면, 이전 chunk의 위치를 조작 가능하다.
size를 조작하면, 다음 chunk의 위치를 조작 가능하다.
prev_inuse bit를 조작하면 이전 chunk의 할당/해제 여부를 조작 가능하다.

binning

binning이란 dlmalloc이 메모리를 효율적으로 관리하기 위해서 free된 chunk를 크기 단위로 관리하는 방식이다.

이렇게 free된 chunk들을 크기 단위로 관리함으로써 재사용하고 효율적으로 메모리를 관리하게 됩니다.

bin의 종류

Fast bin
- 작은 크기의 chunk들을 빠르게 관리
- chunk의 크기
  - 32bit : 64 byte 미만
  - 64bit : 128 byte 미만
- linked list 종류
  - single
- fit 알고리즘
  - exact fit
- 개수
  - 10
- 입출력 방식
  - LIFO
Small bin
- 일반적인 크기의 chunk를 관리
- chunk의 크기
  - 512 byte 미만
- linked list 종류
  - double
- fit 알고리즘
  - exact/best fit
- 개수
  - 62
- 입출력 방식
  - FIFO
Large bin
- 큰 크기의 chunk를 관리
- chunk의 크기
  - 512 byte 이상
- linked list 종류
  - double
- fit 알고리즘
  - best fit
- 개수
  - 63
- 입출력 방식
  - FIFO
Unsorted bin
- 다양한 용도로 사용
- chunk의 크기
  - variable
- linked list 종류
  - double
- fit 알고리즘
  - exact fit
- 개수
  - 10,000
- 입출력 방식
  - FIFO

Fastbin

size가 다른 10개의 chunk를 single linked list로 관리
LIFO 선입후출 구조
chunk의 크기
- 32bit : 64byte 이하
- 64bit : 128byte 이하
해제가 되어도 prev_inuse bit가 변경되지 않음 (중요)
- 인접한 chunk들과 병합되지 않음

#include <stdio.h>
#include <stdlib.h>

void main(){
    char *heap1 = malloc(16);
    char *heap2 = malloc(16);
    char *heap3 = malloc(16);

    free(heap1); 
    free(heap2); // bp
}

실제로 첫번째 free 이후에 힙 영역을 보면 인접한 chunk가 free되었음에도 불구하고 size + prev_inuse bit 값으로 0x21이라는 값을 가지고 있는것을 확인할 수 있다.

그리고 앞서 말한것과 같이 single linked list로 관리되고 있는것을 확인할 수 있었다.

Small bin

size가 다른 63개의 chunk를 double linked list로 관리
FIFO 선입선출 구조
chunk의 size
- 512byte 이하
해제가 되면 뒤 chunk의 prev_inuse_bit 변경
- free할 때 인접한 freed chunk와 병합시킴

#include <stdio.h>
#include <stdlib.h>

void main(){
    char *heap1 = malloc(0x100);
    char *heap2 = malloc(0x100);
    char *heap3 = malloc(0x100);

    free(heap2);
    free(heap1);
}