Continuous free bug (double free bug)

* 서론

솔직히 이건 double free라고 하지말고 continuous free나 heap free unlink bug라던지라고 불러야하는게 맞지 않나?

double free는 동일 heap 영역에 대한 free를 이야기해야되는거 아니야?

나만그래...?

 

*원리

- 전제 조건 및 기본 원리

double free bug는 기본적으로 heap overflow를 기본으로 한다.

즉, P flag가 수정 가능해야하기에 heap overflow가 필수적이다.

heap 영역은 free 될 때 다음에 사용할 주소를 fd 영역에 저장한다.

더불어 heap 영역이 초기화될 때 heap 영역들 사이에 빈 공간이 있다면 합쳐주며, 이는 unlink 함수를 통해 이루어진다.

이는 heap 영역을 효율적으로 사용하려함에 있다.

double free bug의 주요 사항은 위의 두가지를 조합한 것이다.

 

- 예제 1

연속된 3개의 heap chunk a, b, c가 있다고 가정하자.

aaaa bbbb cccc의 값을 넣고 heap 영역의 값들을 보면 아래와 같다.

0x7ffff7ef6000: 0x0000000000000000      0x0000000000000031
0x7ffff7ef6010: 0x0000000061616161      0x0000000000000000
0x7ffff7ef6020: 0x0000000000000000      0x0000000000000000
0x7ffff7ef6030: 0x0000000000000000      0x0000000000000031
0x7ffff7ef6040: 0x0000000062626262      0x0000000000000000
0x7ffff7ef6050: 0x0000000000000000      0x0000000000000000
0x7ffff7ef6060: 0x0000000000000000      0x0000000000000031
0x7ffff7ef6070: 0x0000000063636363      0x0000000000000000
0x7ffff7ef6080: 0x0000000000000000      0x0000000000000000
0x7ffff7ef6090: 0x0000000000000000      0x00000000000fff71

이를 heap chunk 구조로 표현하면 아래 테이블과 같다

heap a pre_size	0x0000000000000000	heap a size	0x0000000000000031
heap a data = fd	0x0000000061616161	heap a data = bk	0x0000000000000000
heap a data	0x0000000000000000	heap a data	0x0000000000000000
heap b pre_size	0x0000000000000000	heap b size	0x0000000000000031
heap b data = fd	0x0000000062626262	heap b data = bk	0x0000000000000000
heap b data	0x0000000000000000	heap b data	0x0000000000000000
heap c pre_size	0x0000000000000000	heap c size	0x0000000000000031
heap c data = fd	0x0000000063636363	heap c data = bk	0x0000000000000000
heap c data	0x0000000000000000	heap c data	0x0000000000000000
top chunk pre_size	0x0000000000000000	top chunk size	0x00000000000ffff71

여기서 c부터 차례로 free 하면 값은 아래와 같이 변경된다.

heap a pre_size	0x0000000000000000	heap a size	0x0000000000000031
heap a data = fd	0x00007ffff7ef6030	heap a data = bk	0x0000000000000000
heap a data	0x0000000000000000	heap a data	0x0000000000000000
heap b pre_size	0x0000000000000000	heap b size	0x0000000000000031
heap b data = fd	0x00007ffff7ef6060	heap b data = bk	0x0000000000000000
heap b data	0x0000000000000000	heap b data	0x0000000000000000
heap c pre_size	0x0000000000000000	heap c size	0x0000000000000031
heap c data = fd	0x0000000000000000	heap c data = bk	0x0000000000000000
heap c data	0x0000000000000000	heap c data	0x0000000000000000
top chunk pre_size	0x0000000000000000	top chunk size	0x00000000000ffff71

위와 같이 b의 fd는 c chunk의 시작 주소, a의 fd는 b chunk의 시작 주소를 저장한다.

c는 fd 값이 없는데 당연하다. 다음 chunk가 top chunk이기 때문.

 

보통은 위와 같이 pre_size, bk 값은 잘 쓰이지 않는다.

malloc 함수의 소스코드를 보면 large block에만 쓰인다던지 한다.

하지만 해당 위치에 값이 있다면 이를 참조한다.

 

- unlink 함수

여기서 의문을 가져야하는 부분은, 결국 heap 영역에 특정 값이 쓰여졌다는 점이다.

이 값은 어떻게 구하고 어떻게 삽입되는 것일까.

요약하면 bin에서 heap 영역을 관리하기 때문인데 우선 이는 추후에 다시 다뤄보기로 하자.

 

결국은 unlink 함수에 의해서 특정 위치에 특정 값을 쓰게 된다는 점을 주목하자.

unlink 함수의 경우 size 영역의 P flag 즉 마지막 1의 여부에 따라 작동하는데, 만일 아래와 같이 b chunk의 P flag가 1이 아니라면 

heap a pre_size	0x0000000000000000	heap a size	0x0000000000000031
heap a data = fd	0x6161616161616161	heap a data = bk	0x6161616161616161
heap a data	0x6161616161616161	heap a data	0x6161616161616161
heap b pre_size	0x6161616161616161	heap b size	0x0000000000000032
heap b data = fd	0x0000000062626262	heap b data = bk	0x0000000000000000
heap b data	0x0000000000000000	heap b data	0x0000000000000000
heap c pre_size	0x0000000000000000	heap c size	0x0000000000000031
heap c data = fd	0x0000000063636363	heap c data = bk	0x0000000000000000
heap c data	0x0000000000000000	heap c data	0x0000000000000000
top chunk pre_size	0x0000000000000000	top chunk size	0x00000000000ffff71

b를 free하는 순간 heap은 b가 비어있다고 판단하여 b와 c를 병합하려할테니 unlink 함수가 작동한다.

정상적이라면 b는 fd와 bk 값을 가지고 있어야하지만 위와 같은 상황에서는 오류가 발생한다.

 

버전에 따라 다르지만 unlink 함수는 대략 아래와 같은 구조를 가지고 있다. (아래는 libc 2.23)

malloc.c - malloc/malloc.c - Glibc source code (glibc-2.23) - Bootlin

malloc.c - malloc/malloc.c - Glibc source code (glibc-2.23) - Bootlin

 

중요한 부분만 요약하면 아래 부분이다.

#define unlink(AV, P, BK, FD) {
    FD = P->fd;
    BK = P->bk;
    FD->bk = BK;
    BK->fd = FD;

 

unlink 함수는 3가지 값을 기준으로 작동하는데 pre_size, fd, bk 값이며 보통 p, fd, bk로 표현한다.

pre_size는 해당 chunk 이전에 위치한 chunk의 위치를 저장한 공간이다.

fd = forward pointer 와 bk = backward pointer를 의미하며, 이전 chunk의 위치 및 다음 chunk의 위치를 의미한다.

 

위 unlink 함수를 보면 FD와 fd, BK와 bk를 변수로 사용하고 있어 헷갈리는데, 아래와 같이 테이블화 하면 조금 더 보기 쉽다.

BK (P 이전 chunk)		P (현재 chunk)		FD(P 다음 chunk)
BK -> fd	BK -> bk	P -> fd	P -> bk	FD -> fd	FD -> bk

이를 다시 예제에 적용하면 아래와 같고

BK (a chunk)		P (b chunk)		FD(c chunk)
BK -> fd	BK -> bk	P -> fd	P -> bk	FD -> fd	FD -> bk

unlink 함수가 작동하면 아래의 모양이 된다.

BK (a chunk)		P (b chunk)		FD(c chunk)
BK -> fd = P-> fd	BK -> bk	P -> fd	P -> bk	FD -> fd	FD -> bk = P -> bk

 

이제 chunk를 조금 확장해서 보자.

BK (a chunk)		P (b chunk)		FD(c chunk)
pre_size	size	pre_size	size	pre_size	size
fd	bk	fd	bk	fd	bk
data	data	data	data	data	data

 

unlink 함수에서 앞, 뒤 chunk의 위치는 bin 영역의 값 또는 pre_size를 참조한다. (대략 그렇다고 알고 넘어가자)

만일 b pre_size가 -8이라고 가정하면 b 이전의 chunk가 b의 위치 - (-8) 위치부터 시작한다고 인식하기에 b size 위치가 a chunk의 시작점으로 인식한다.

또한 fd와 bk의 경우 chunk 시작점으로부터의 offset으로 값을 찾기에 chunk의 시작점 + 16 = fd, chunk의 시작점 + 24 = bk로 인식하게 된다.

이를 반영하면 아래와 같은 모양이 된다.

BK (a chunk)		P (b chunk)		FD(c chunk)
pre_size	size	pre_size = -8	size = a chunk 시작점 = a chunk pre_size	pre_size	size
fd	bk	fd = a chunk size	bk = a chunk fd	fd	bk
data	data	data = a chunk bk	data = a chunk data	data	data

 unlink가 작동하게 되면 위에서 보았던

BK (a chunk)		P (b chunk)		FD(c chunk)
BK -> fd = P-> fd	BK -> bk	P -> fd	P -> bk	FD -> fd	FD -> bk = P -> bk

에 따라

b chunk의 fd 값을 a chunk의 fd 위치에,

b chunk의 bk 값을 c chunk의 bk 위치에 삽입하려 할 것이다.

여기서 후자의 경우 쓸모가 없기에 전자의 경우만 요약해서 아래와 같은 공식을 세울 수 있게 된다.

 

P chunk P flag = 초기화

P chunk pre_size = -8

P chunk + (data size * 3) = 삽입할 주소

P chunk + (data size * 2) = 삽입할 값

data size : 32 bit = 4, 64 bit = 8

 

* 결론

이까지 오는데 오래 걸렸는데, 결국은

"b chunk의 fd 값을 a chunk의 fd 위치에"

삽입하는 것이 double free

아... 아니 continuous free나 heap free unlink bug의 목적이다.

 

많은 글들이 그냥

FD+12 -> BK
BK + 8 -> FD

뭐 이런 식으로 대충 갈겨놨는데 원리는 제대로 알아야지.