what is unsorted bin , small bin, large bin → bin ) (deep analyze ) & libc leak

Nov 5, 2025 · Dreamhack

#Heap#Glibc#Pwnable#How2pwn

unsorted bin에 대해서 자세히 다루어보다 보니 원형 이중 연결 리스트에 다루게 되었고, 이는 사실

unsorted bin 뿐만 아니라 small bin, large bin 도 같은 방식으로 동작하고 있다는 것을 알았다. 따라서 한번에 정리할려고 한다. 즉, glibc에서 bin에 대한 것을 자세히 다뤄볼려고 한다.

일단 bin이 bin

해당 글을 보면 알겠지만, ptmalloc에는 총 128개의 bin이 정의되어 있다. 이 중 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin으로 사용되고, 나머지 2개는 사용되지 않음

라고 되어있는데 이게 무슨 말인지 이해가 안되었다. 근데 이게 말그대로였다. 원형 이중연결 리스트 bin이 몇개냐 라는 의미였다. 즉, 한개의 bin 안에 원형으로 chunk들이 뭉치는 구조이다.

unsorted bin은 아시다시피 원형 이중연결 리스트이다. 따라서 시작점이 명백히 존재해야 하는데 그걸 아레나에서는

가짜 chunk 헤더로 구현을 해놓았다. 즉, 내부의 가짜 chunk가 하나 들어있는셈 ( 모든 원형 이중연결 리스트가 같은 방식 )

초기화 구현을 보면

C
static void 
malloc_init_state (mstate av)
{
  int i;
  mbinptr bin; 

  /* Establish circular links for normal bins */
  for (i = 1; i <. NBINS; ++i) 
    {    
      bin = bin_at (av, i);
      bin->fd = bin->bk = bin; 
    }    

    ...

}

다음과 같은데 circular links라고 주석으로도 명시를 해놓았고 여기서 NBINS 가 위에서 말한 128이다. 그리고 실제로 bin_at 이 사용되는데

C
/* addressing -- note that bin_at(0) does not exist */
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))			      \
             - offsetof (struct malloc_chunk, fd))

bin_at(m,i) 에서 m은 주로 mstate, 즉 struct malloc_state * 을 의미한다. 어떤 아레나를 사용할지를 의미한다.

그리고 i는 해당 아레나에 i번째 bin을 의미한다.

  • 0: unused
  • 1: unsorted bin
  • 2–64: small bins
  • 65–127: large bins

각 i는 대부분의 시스템에서 다음과 같이 정의가 된다. 당연히 small, large가 여러개의 bin을 가지는 이유는 크기별로 분류해서 각각의 bin이 있기 때문이다.

그렇다면 bin_at(m,i) 은 어떤 값을 반환할까? 바로 각각의 bin에 헤더를 반환하는데 헤더라고 거창한게 아니라 바로 우리가 아는 chunk 구조체의 시작주소를 반환하는데 실제 있는 chunk가 아니고 glibc에서 bin마다 각각 있는 가짜청크를 반환한다.

근데 어떻게 생각하면 원형 이중 연결 리스트 이니깐 당연히 뭔가가 들어가 있어야 하고 애초에 bin에 들어가는게 free가 된 chunk 구조체가 들어가니깐 가짜 청크가 들어가 있어도 전혀 이상하지 않다.

따라서 각각의 bin에 초기에는 가짜청크만 들어가있고 위에 있는 초기화 함수에 의해 가짜 청크의 fd와 bk필드는 자기 자신을 가리키게 된다.

이제 bin에 다른 청크가 들어오면 당연히 서로 연결을 해야하는데 그럼 당연히 기존에 있는

가짜 chunk의 fd와 bk는 모두 새로 들어온 청크의 헤더 시작부분을 가리키게 되고 당연히 새로 들어온 chunk의 fd와 bk는 가짜 chunk를 가리키게 될것이다.

C
	Place the chunk in unsorted chunk list. Chunks are
	not placed into regular bins until after they have
	been given one chance to be used in malloc.
      */

      bck = unsorted_chunks(av);
      fwd = bck->fd;
      if (__glibc_unlikely (fwd->bk != bck))
	malloc_printerr ("free(): corrupted unsorted chunks");
      p->fd = fwd;
      p->bk = bck;
      if (!in_smallbin_range(size))
	{
	  p->fd_nextsize = NULL;
	  p->bk_nextsize = NULL;
	}
      bck->fd = p;
      fwd->bk = p;

실제로 확인해보면

p 가 지금 free 된 chunk인데

unsorted_chunks(av); 을 먼저 사용한다. 이는

C
/* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
#define unsorted_chunks(M)          (bin_at (M, 1))

다음과 같은 매크로 인데 bin_at으로 현재 아레나의 1번 bin의 헤더(가짜 chunk)를 가져온다. 즉, unsorted bin의 헤더를 가져온다. 이걸 생각해서 코드를 보면 맨초기 상태에서 fwd = bck->fd; 역시 헤더를 의미하므로

지금 free된 chunk의 fd와 bk모두 헤더를 가리키게 됨을 알 수 있다.

그리고 지금 코드를 보면 계속 free된 청크가 들어갈때마다 bk는 unsorted_chunks(av); 이므로 계속 가짜청크 앞으로 들어가는 원형 연결 리스트 임을 알 수 있다.

요약

  • unsorted bin에 청크가 혼자 있을 때
    • 그 청크의 fd = unsorted_chunks(av) (헤더)
    • 그 청크의 bk = unsorted_chunks(av) (헤더)
  • 두 개 있을 때 (최근에 free 된 게 q, 그 전에 p)
    • 헤더(H):
      • H->fd = q, H->bk = p
    • q:
      • q->bk = H, q->fd = p
    • p:
      • p->bk = q, p->fd = H

libc leak

자 그러면 이러한 bin들을 사용해서 어떻게 libc leak이 가능할까? 정답은 너무 뻔하다 바로 가짜 chunk의 주소를 leak 하면 이는 libc 상에 있기에 libc leak으로 이어갈 수 있다.

일반적으로 처음에 unsorted bin에 들어가기 때문에 주 공격 타겟이 되며, unsorted bin에 free가 된 chunk가 들어가게 한다음에 ( tcache , fastbin에 안들어가게 크기를 정하고) 이제 이 free된 chunk를 다시 읽을 수 있다면(UAF) 그 청크의 fd = unsorted_chunks(av) (헤더)

그 청크의 bk = unsorted_chunks(av) (헤더) fd와 bk 필드에 헤더주소가 있을테니 이를 통해 libc leak을 하면된다.

l