Post

[Heap Explploitation] Bins

Posted
Heap Exploitation
Heap Exploitation
By Jeong JongBae 22 min read

Fastbin

작은 크기의 heap chunk를 할당하고 해제할 때 사용하는 bin 이다.

  • LIFO(Last In First Out) 형식을 사용하여 마지막으로 해제된 chunk가 가장 먼저 재할당 된다.
  • 64비트 아키텍처의 경우 [0x20, 0x30, 0x40, 0x50, 0x60, 0x70, 0x80] 크기의 chunk를 가진다.
  • fastbin은 single-linked list로 구성된다.
    • 같은 크기의 chunk가 해제되었을 때 마지막으로 해제된 chunk의 fd 에 현재 해제된 chunk의 주소가 저장된다.
    • single-linked list 이기 때문에 bk 는 사용되지 않는다.
  • fastbin은 인접한 chunk가 있어도 병합되지 않는다.

Fastbin 해제 과정

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

#if TRIM_FASTBINS
      /*
	If TRIM_FASTBINS set, don't place chunks
	bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)
#endif
      ) {

    if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
	|| __builtin_expect (chunksize (chunk_at_offset (p, size))
			     >= av->system_mem, 0))
      {
	/* We might not have a lock at this point and concurrent modifications
	   of system_mem might have let to a false positive.  Redo the test
	   after getting the lock.  */
	if (have_lock
	    || ({ assert (locked == 0);
		  mutex_lock(&av->mutex);
		  locked = 1;
		  chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
		    || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
	      }))
	  {
	    errstr = "free(): invalid next size (fast)";
	    goto errout;
	  }
	if (! have_lock)
	  {
	    (void)mutex_unlock(&av->mutex);
	    locked = 0;
	  }
      }

    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

    set_fastchunks(av);
    unsigned int idx = fastbin_index(size);
    fb = &fastbin (av, idx);

    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
    mchunkptr old = *fb, old2;
    unsigned int old_idx = ~0u;
    do
      {
	/* Check that the top of the bin is not the record we are going to add
	   (i.e., double free).  */
	if (__builtin_expect (old == p, 0))
	  {
	    errstr = "double free or corruption (fasttop)";
	    goto errout;
	  }
	/* Check that size of fastbin chunk at the top is the same as
	   size of the chunk that we are adding.  We can dereference OLD
	   only if we have the lock, otherwise it might have already been
	   deallocated.  See use of OLD_IDX below for the actual check.  */
	if (have_lock && old != NULL)
	  old_idx = fastbin_index(chunksize(old));
	p->fd = old2 = old;
      }
    while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);

    if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
      {
				errstr = "invalid fastbin entry (free)";
				goto errout;
      }
  }

fb = &fastbin (av, idx); 를 보면 fastbinsY 배열에서 현재 chunk 크기에 해당하는 fastbin 리스트를 가져온다.

1

#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

p->fd = old2 = old 를 통해 해제된 현재 chunk의 fd 에 저장한다.

Fastbin 재할당

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
  {
    idx = fastbin_index (nb);
    mfastbinptr *fb = &fastbin (av, idx);
    mchunkptr pp = *fb;
    do
      {
        victim = pp;
        if (victim == NULL)
          break;
      }
    while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
           != victim);
    if (victim != 0)
      {
        if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
          {
            errstr = "malloc(): memory corruption (fast)";
          errout:
            malloc_printerr (check_action, errstr, chunk2mem (victim), av);
            return NULL;
          }
        check_remalloced_chunk (av, victim, nb);
        void *p = chunk2mem (victim);
        alloc_perturb (p, bytes);
        return p;
      }
  }

mfastbinptr *fb = &fastbin (av, idx); 에서 할당 요청한 크기와 같은 fastbin을 찾는다.

1
2

#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

12번째 라인에서 마지막으로 추가된 chunk의 fd 를 참조하여 해당 chunk의 fd 가 가리키는 chunk를 fastbin의 첫 번째 리스트로 업데이트하여 LIFO 구조를 유지한다. 그리고 victim 에는 자연스럽게 마지막으로 저장된 chunk가 저장된다.

1
2
3
4
5
6
7
8
9
10

#ifndef catomic_compare_and_exchange_val_acq
# ifdef __arch_c_compare_and_exchange_val_32_acq
#  define catomic_compare_and_exchange_val_acq(mem, newval, oldval) \
  __atomic_val_bysize (__arch_c_compare_and_exchange_val,acq,		      \
		       mem, newval, oldval)
# else
#  define catomic_compare_and_exchange_val_acq(mem, newval, oldval) \
  atomic_compare_and_exchange_val_acq (mem, newval, oldval)
# endif
#endif

1
2
3
4
5
6
7
8
9

/* The only basic operation needed is compare and exchange.  */
#define atomic_compare_and_exchange_val_acq(mem, newval, oldval) \
  ({ __typeof (mem) __gmemp = (mem);				      \
     __typeof (*mem) __gret = *__gmemp;				      \
     __typeof (*mem) __gnewval = (newval);			      \
								      \
     if (__gret == (oldval))					      \
       *__gmemp = __gnewval;					      \
     __gret; })

첫 번째 free 후 chunk가 fastbin에 저장된다.

1
2
3
4
5
6
7

Fastbins[idx=0, size=0x20]  ←  Chunk(addr=0x602010, size=0x20, flags=PREV_INUSE)
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00

두 번째 free 후 마찬가지로 fastbin에 저장되는데 single-linked list 형식으로 연결된다.

1
2
3
4
5
6
7

Fastbins[idx=0, size=0x20]  ←  Chunk(addr=0x602030, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x602010, size=0x20, flags=PREV_INUSE)
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00

heap memory를 보면 현재 해제된 chunk의 fd 에 이전에 해제되었던 chunk의 주소가 저장된다.

1
2
3
4
5
6
7
8
9

gef➤  x/16gx 0x602000
0x602000:       0x0000000000000000      0x0000000000000021
0x602010:       0x0000000000000000      0x0000000000000000
0x602020:       0x0000000000000000      0x0000000000000021
0x602030:       0x0000000000602000      0x0000000000000000
0x602040:       0x0000000000000000      0x0000000000020fc1
0x602050:       0x0000000000000000      0x0000000000000000
0x602060:       0x0000000000000000      0x0000000000000000
0x602070:       0x0000000000000000      0x0000000000000000

재할당 시 마지막으로 fastbin에 담긴 chunk가 다시 사용되고, fastbin 리스트에서 제거된다.

1
2
3
4
5
6
7

Fastbins[idx=0, size=0x20]  ←  Chunk(addr=0x602010, size=0x20, flags=PREV_INUSE)
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00

unsorted bin

small bin과 large bin 크기의 heap chunk가 해제된 후 재할당을 위해 사용되는 bin 이다.

  • bin 의 개수는 1개이다.
  • 크기 제한이 없기 때문에 다양한 크기의 heap chunk가 저장될 수 있다.
  • double-linked list를 사용한다.
  • FIFO(First In First Out) 구조를 사용한다.
  • 해제된 chunk를 재할당 받기 위해서는 해제된 chunk의 크기보다 작거나 같은 크기를 할당되어야 한다.

할당 요청이 들어온 nb 와 unsorted bin의 size 를 비교하여 같은 경우 unsorted bin에 저장된 chunk를 재사용한다.

1
2
3
4
5
6
7
8
9
10
11
12

/* Take now instead of binning if exact fit */

if (size == nb)
  {
    set_inuse_bit_at_offset (victim, size);
    if (av != &main_arena)
      victim->size |= NON_MAIN_ARENA;
    check_malloced_chunk (av, victim, nb);
    void *p = chunk2mem (victim);
    alloc_perturb (p, bytes);
    return p;
  }

할당 요청을 받은 크기가 smallbin 의 범위 내에 있고, unsorted bin 에 저장 되어있는 chunk이 분할된 last remainder chunk라면 if 문을 만족시킨다.

  • 분할되고 난 후의 남는 chunk를 unsorted bin 과 last remainder 에 저장한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
  }
  • smallbin 의 크기가 unsorted bin 에 남아있다면 해당 chunk를 small bin으로 옮긴다.
    • small bin 에 존재하는 chunk와 fd , bk 를 연결한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

if (in_smallbin_range (size))
  {
    victim_index = smallbin_index (size);
    bck = bin_at (av, victim_index);
    fwd = bck->fd;
  }
  
... 중략

mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
  • large bin 의 크기가 unsorted bin 에 남아있다면 해당 chunk를 large bin 으로 옮긴다.
  • large bin 에 존재하는 chunk와 fd_nextsize , bk_nextsize 를 연결하고 fd, bk 를 연결한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

else
  {
    victim_index = largebin_index (size);
    bck = bin_at (av, victim_index);
    fwd = bck->fd;

    /* maintain large bins in sorted order */
    if (fwd != bck)
      {
        /* Or with inuse bit to speed comparisons */
        size |= PREV_INUSE;
        /* if smaller than smallest, bypass loop below */
        assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
        if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
          {
            fwd = bck;
            bck = bck->bk;

            victim->fd_nextsize = fwd->fd;
            victim->bk_nextsize = fwd->fd->bk_nextsize;
            fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
          }
        else
          {
            assert ((fwd->size & NON_MAIN_ARENA) == 0);
            while ((unsigned long) size < fwd->size)
              {
                fwd = fwd->fd_nextsize;
                assert ((fwd->size & NON_MAIN_ARENA) == 0);
              }

            if ((unsigned long) size == (unsigned long) fwd->size)
              /* Always insert in the second position.  */
              fwd = fwd->fd;
            else
              {
                victim->fd_nextsize = fwd;
                victim->bk_nextsize = fwd->bk_nextsize;
                fwd->bk_nextsize = victim;
                victim->bk_nextsize->fd_nextsize = victim;
              }
            bck = fwd->bk;
          }
      }
    else
      victim->fd_nextsize = victim->bk_nextsize = victim;
  }

mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

unsorted bin 해제 과정

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

    } else
clear_inuse_bit_at_offset(nextchunk, 0);

    /*
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))
{
  errstr = "free(): corrupted unsorted chunks";
  goto errout;
}
    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;

    set_head(p, size | PREV_INUSE);
    set_foot(p, size);

    check_free_chunk(av, p);

clear_inuse_bit_at_offset 매크로를 이용하여 인접한 다음 chunk의 prev_inuse 비트를 0으로 만들고 현재 해제된 chunk를 double-linked list에 포함시킨다.

1
2

#define clear_inuse_bit_at_offset(p, s)					      \
  (((mchunkptr) (((char *) (p)) + (s)))->size &= ~(PREV_INUSE))

small bin

32비트 아키텍처에서는 512 바이트, 64비트 아키텍처에서는 1024 바이트 미만의 사이즈로 heap chunk가 해제되었을 때 unsorted bin 에 추가된 후 저장되는 bin 이다.

  • double-linked list 를 사용
  • 두 개의 해제된 chunk가 인접해 있을 수 없고, 인접해 있다면 하나의 chunk로 병합된다.
  • FIFO(First In First Out) 구조 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

if (in_smallbin_range (nb))
  {
    idx = smallbin_index (nb);
    bin = bin_at (av, idx);

    if ((victim = last (bin)) != bin)
      {
        if (victim == 0) /* initialization check */
          malloc_consolidate (av);
        else
          {
            bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
              {
                errstr = "malloc(): smallbin double linked list corrupted";
                goto errout;
              }
            set_inuse_bit_at_offset (victim, nb);
            bin->bk = bck;
            bck->fd = bin;

            if (av != &main_arena)
              victim->size |= NON_MAIN_ARENA;
            check_malloced_chunk (av, victim, nb);
            void *p = chunk2mem (victim);
            alloc_perturb (p, bytes);
            return p;
          }
      }
  }
  • 1 line : 할당 요청을 받은 chunk가 small bin 크기 범위 내에 있는 지 확인

  • 3 ~ 4 line : small bin 에 해당하는 배열을 가져온다.

    1
2
3

      #define smallbin_index(sz) \
    ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
     + SMALLBIN_CORRECTION)

  • 6 line : small bin 의 연결 리스트가 비어 있는 지 확인한다. 비어 있으면 malloc_consolidate(av) 를 통해 fastbin과 병합한다.

    1

      #define last(b)      ((b)->bk)

  • 18 ~ 20 line : 인접한 chunk에 prev_inuse 비트를 설정하고 반환될 chunk의 bk 를 main_arena 의 bk 가 가리키게 하고, 해당 chunk의 fd (반환될 chunk의 bk)는 main_arena 를 가리키게 설정하여 double-linked list 를 만들고, small bin의 첫 번째 리스트로 만든다.

    1
2

      #define set_inuse_bit_at_offset(p, s)					      \
    (((mchunkptr) (((char *) (p)) + (s)))->size |= PREV_INUSE)

마지막으로 chunk를 반환하고 할당 과정이 종료된다.

small bin 예제

128 바이트 이상의 chunk가 해제되면 먼저 unsorted bin에 저장된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

gef➤  heap bins
[+] No Tcache in this version of libcty bins.
──────────────────── Fastbins for arena 0x7ffff7dd1b20 ────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────── Unsorted Bin for arena 'main_arena' ───────────────────
[+] unsorted_bins[0]: fw=0x602000, bk=0x602000
 →   Chunk(addr=0x602010, size=0x90, flags=PREV_INUSE)
[+] Found 1 chunks in unsorted bin.
──────────────────── Small Bins for arena 'main_arena' ────────────────────
[+] Found 0 chunks in 0 small non-empty bins.
──────────────────── Large Bins for arena 'main_arena' ────────────────────
[+] Found 0 chunks in 0 large non-empty bins.

그리고 해제된 chunk의 fd 와 bk 에는 bins 의 주소가 저장되어 있다.

1
2
3
4
5
6
7
8
9
10

gef➤  x/64gx 0x0000000000602000
0x602000:       0x0000000000000000      0x0000000000000091
0x602010:       0x00007ffff7dd1b78      0x00007ffff7dd1b78
0x602020:       0x0000000000000000      0x0000000000000000
0x602030:       0x0000000000000000      0x0000000000000000

gef➤  x/16gx 0x00007ffff7dd1b78
0x7ffff7dd1b78 <main_arena+88>: 0x0000000000602140      0x0000000000000000
0x7ffff7dd1b88 <main_arena+104>:        0x0000000000602000      0x0000000000602000
0x7ffff7dd1b98 <main_arena+120>:        0x00007ffff7dd1b88      0x00007ffff7dd1b88

2번 째 small bin 크기의 chunk를 해제하면 unsorted bin에 추가된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

gef➤  heap bins
[+] No Tcache in this version of libc
──────────────────── Fastbins for arena 0x7ffff7dd1b20 ────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────── Unsorted Bin for arena 'main_arena' ───────────────────
[+] unsorted_bins[0]: fw=0x6020b0, bk=0x602000
 →   Chunk(addr=0x6020c0, size=0x90, flags=PREV_INUSE)   →   Chunk(addr=0x602010, size=0x90, flags=PREV_INUSE)
[+] Found 2 chunks in unsorted bin.
──────────────────── Small Bins for arena 'main_arena' ────────────────────
[+] Found 0 chunks in 0 small non-empty bins.
──────────────────── Large Bins for arena 'main_arena' ────────────────────
[+] Found 0 chunks in 0 large non-empty bins.
  • 1번째로 해제된 chunk의 fd 는 bins 의 주소를 가리키고, bk 는 2번째로 해제된 chunk를 가리킨다.
  • 2번째로 해제된 chunk의 fd 는 1번째로 해제된 chunk를 가리키고, bk 는 bins 의 주소를 가리킨다.
  • double-linked list 형태임을 알 수 있다.
  • 중간에 해제되지 않은 chunk를 보면 prev_size 가 0x90 으로 세팅되었고 PREV_INUSE flag가 0으로 세팅되었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

gef➤  x/64gx 0x0000000000602000
0x602000:       0x0000000000000000      0x0000000000000091
0x602010:       0x00007ffff7dd1b78      0x00000000006020b0
0x602020:       0x0000000000000000      0x0000000000000000
0x602030:       0x0000000000000000      0x0000000000000000
0x602040:       0x0000000000000000      0x0000000000000000
0x602050:       0x0000000000000000      0x0000000000000000
0x602060:       0x0000000000000000      0x0000000000000000
0x602070:       0x0000000000000000      0x0000000000000000
0x602080:       0x0000000000000000      0x0000000000000000
0x602090:       0x0000000000000090      0x0000000000000020
0x6020a0:       0x0000000000000000      0x0000000000000000
0x6020b0:       0x0000000000000000      0x0000000000000091
0x6020c0:       0x0000000000602000      0x00007ffff7dd1b78
0x6020d0:       0x0000000000000000      0x0000000000000000
0x6020e0:       0x0000000000000000      0x0000000000000000

같은 크기의 chunk를 재할당하면 다음과 같이 먼저 해제된 chunk를 사용한다. 그리고 2번째로 해제된 chunk의 fd , bk 는 bins 의 주소를 가리킴으로써 double-linked list 형태를 유지한다.

  • 추가로 인접한 chunk를 보면 PREV_INUSE 가 1 로 세팅이 된 것을 볼 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

gef➤  x/64gx 0x0000000000602000
0x602000:       0x0000000000000000      0x0000000000000091
0x602010:       0x00007ffff7dd1b78      0x00000000006020b0
0x602020:       0x0000000000000000      0x0000000000000000
0x602030:       0x0000000000000000      0x0000000000000000
0x602040:       0x0000000000000000      0x0000000000000000
0x602050:       0x0000000000000000      0x0000000000000000
0x602060:       0x0000000000000000      0x0000000000000000
0x602070:       0x0000000000000000      0x0000000000000000
0x602080:       0x0000000000000000      0x0000000000000000
0x602090:       0x0000000000000090      0x0000000000000021
0x6020a0:       0x0000000000000000      0x0000000000000000
0x6020b0:       0x0000000000000000      0x0000000000000091
0x6020c0:       0x00007ffff7dd1b78      0x00007ffff7dd1b78
0x6020d0:       0x0000000000000000      0x0000000000000000
0x6020e0:       0x0000000000000000      0x0000000000000000

large bin

large bin 은 512 바이트 이상의 큰 크기의 chunk가 해제 되었을 때 사용되는 bin 이다.

  • large bin chunk는 다른 chunk 들과 다르게 fd_nextsize , bk_nextsize 를 사용한다.
  • FIFO(First In First Out) 구조를 사용한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

/*
   If a large request, scan through the chunks of current bin in
   sorted order to find smallest that fits.  Use the skip list for this.
 */

if (!in_smallbin_range (nb))
  {
    bin = bin_at (av, idx);

    /* skip scan if empty or largest chunk is too small */
    if ((victim = first (bin)) != bin &&
        (unsigned long) (victim->size) >= (unsigned long) (nb))
      {
        victim = victim->bk_nextsize;
        while (((unsigned long) (size = chunksize (victim)) <
                (unsigned long) (nb)))
          victim = victim->bk_nextsize;

        /* Avoid removing the first entry for a size so that the skip
           list does not have to be rerouted.  */
        if (victim != last (bin) && victim->size == victim->fd->size)
          victim = victim->fd;

        remainder_size = size - nb;
        unlink (av, victim, bck, fwd);

        /* Exhaust */
        if (remainder_size < MINSIZE)
          {
            set_inuse_bit_at_offset (victim, size);
            if (av != &main_arena)
              victim->size |= NON_MAIN_ARENA;
          }
        /* Split */
        else
          {
            remainder = chunk_at_offset (victim, nb);
            /* We cannot assume the unsorted list is empty and therefore
               have to perform a complete insert here.  */
            bck = unsorted_chunks (av);
            fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
              {
                errstr = "malloc(): corrupted unsorted chunks";
                goto errout;
              }
            remainder->bk = bck;
            remainder->fd = fwd;
            bck->fd = remainder;
            fwd->bk = remainder;
            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;
      }
  }
  • 6 line : !in_smallbin_range(nb) 를 통해 해제하고자 하는 chunk가 large bin인지 확인한다.
  • 11 line : large bin 이 비어 있는지, 할당 요청된 chunk가 large bin 의 크기 보다 큰 지 검사한다.
  • 15 line : victim->bk_nextsize 를 돌면서 할당 요청된 chunk의 크기에 부합하는 chunk를 찾는다.

  • 25 line : 반환될 chunk를 제외한 앞, 뒤 chunk 들의 연결리스트를 유지하기 위해서 unlink 매크로를 사용한다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

      /* Take a chunk off a bin list */
  #define unlink(AV, P, BK, FD) {                                            \
      FD = P->fd;								      \
      BK = P->bk;								      \
      if (__builtin_expect (FD->bk != P || BK->fd != P, 0))		      \
        malloc_printerr (check_action, "corrupted double-linked list", P, AV);  \
      else {								      \
          FD->bk = BK;							      \
          BK->fd = FD;							      \
          if (!in_smallbin_range (P->size)				      \
              && __builtin_expect (P->fd_nextsize != NULL, 0)) {		      \
  	    if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)	      \
  		|| __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))    \
  	      malloc_printerr (check_action,				      \
  			       "corrupted double-linked list (not small)",    \
  			       P, AV);					      \
              if (FD->fd_nextsize == NULL) {				      \
                  if (P->fd_nextsize == P)				      \
                    FD->fd_nextsize = FD->bk_nextsize = FD;		      \
                  else {							      \
                      FD->fd_nextsize = P->fd_nextsize;			      \
                      FD->bk_nextsize = P->bk_nextsize;			      \
                      P->fd_nextsize->bk_nextsize = FD;			      \
                      P->bk_nextsize->fd_nextsize = FD;			      \
                    }							      \
                } else {							      \
                  P->fd_nextsize->bk_nextsize = P->bk_nextsize;		      \
                  P->bk_nextsize->fd_nextsize = P->fd_nextsize;		      \
                }								      \
            }								      \
        }									      \
  }
  • 35 line : large bin chunk가 요청된 크기보다 큰 경우 remainder_sizse 를 검사하여 MINSIZE 보다 큰 경우 unsorted bin 과 연결리스트를 형성하여 저장한다.
Hacking, Pwn
Heap Theory
This post is licensed under CC BY 4.0 by the author.