Unsorted bin attack

unsorted bin attack은 free 청크의 BK를 조작할 수 있을 때, 임의 주소에 main_arena 영역의 주소를 쓸 수 있는 공격 기법이다.
libc leak, 버퍼 사이즈 덮기 등 추가적인 공격을 연계하기 위해서 사용한다.

Conditions

1. unsorted bin에 free chunk을 넣을 수 있어야 한다.
2. free chunk의 bk 포인터를 조작할 수 있어야 한다.
3. unsorted bin에서 bk 포인터가 조작된 free chunk를 뺄 수 있어야 한다.

Analysis

  for (;; )
    {
      int iters = 0;
      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
        {
          bck = victim->bk;
          if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
              || __builtin_expect (victim->size > av->system_mem, 0))
            malloc_printerr (check_action, "malloc(): memory corruption",
                             chunk2mem (victim), av);
          size = chunksize (victim);

          /*
             If a small request, try to use last remainder if it is the
             only chunk in unsorted bin.  This helps promote locality for
             runs of consecutive small requests. This is the only
             exception to best-fit, and applies only when there is
             no exact fit for a small chunk.
           */

          if (in_smallbin_range (nb) &&
              bck == unsorted_chunks (av) &&
              victim == av->last_remainder &&
              (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
            {
              /* split and reattach remainder */
              remainder_size = size - nb;
              remainder = chunk_at_offset (victim, nb);
              unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
              av->last_remainder = remainder;
              remainder->bk = remainder->fd = unsorted_chunks (av);
              if (!in_smallbin_range (remainder_size))
                {
                  remainder->fd_nextsize = NULL;
                  remainder->bk_nextsize = NULL;
                }

              set_head (victim, nb | PREV_INUSE |
                        (av != &main_arena ? NON_MAIN_ARENA : 0));
              set_head (remainder, remainder_size | PREV_INUSE);
              set_foot (remainder, remainder_size);

              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }

          /* remove from unsorted list */
          unsorted_chunks (av)->bk = bck;
          bck->fd = unsorted_chunks (av);

로직은 위와 같다.

/* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
#define unsorted_chunks(M)          (bin_at (M, 1))
/* 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))

매크로 함수는 위와 같다.

int iters = 0;
      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
        {
          bck = victim->bk;

unsorted_chunks (av)는 arena에서 bins[0]을 가리키고 unsorted_chunks (av) -> bk는 bins[1]을 가리킨다.
이때 둘이 다르면, free chunk가 있다는 소리니, bck에 victim -> bk를 저장한다.

더 아래 코드들은 unsorted bin에서 분류하는 코드이니 스킵하고 unsorted list에서 chunk를 빼는 부분을 보면 아래와 같다.

/* remove from unsorted list */
          unsorted_chunks (av)->bk = bck;
          bck->fd = unsorted_chunks (av);

bck->fd에 unsorted_chunks (av)를 넣음으로서 circular doubly linked list에서 청크가 제거되는 작업이 수행된다.

정상적인 구조는 위와 같다.
bck = victim->bk; 에서 bck가 bin2를 가리키게 되고, bck->fd = unsorted_chunks (av); 에서 victim->bk->fd = unsorted_chunks(av)가 되면서 청크가 제거된다.

Exploitation

unsorted chunk의 bk를 target-0x10으로 조작하면, victim->bk->fd가 target을 가리키게 되고, bck->fd = unsorted_chunks (av);에 의해서 unsorted_chunks (av)의 주소가 써진다.