Large Bin Attack 学习记录

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

/*
  This struct declaration is misleading (but accurate and necessary).
  It declares a "view" into memory allowing access to necessary
  fields at known offsets from a given base. See explanation below.
*/
struct malloc_chunk {
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

 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
71
72
73

if (in_smallbin_range(size)) 
{
  victim_index = smallbin_index(size);//获取size对应的smallbin的index
  bck = bin_at(av, victim_index);//bck指向size对应的smallbin的链表头
  //fwd指向size对应的smallbin的链表中的新加入的chunk(small bin使用头插法)
  fwd = bck->fd;
}
else//如果不再smallbin的范围，也就是说在large bin 的范围
{
  victim_index = largebin_index(size);//获取size对应的large bin的index
  bck = bin_at(av, victim_index);//bck指向size对应的large bin的链表头
  fwd = bck->fd;//fwd指向size对应的large bin的链表中的新加入的chunk
  
  //如果large bin 非空，在largbin进行按顺序插入
  if (fwd != bck) {
	  /* Or with inuse bit to speed comparisons */
	  size |= PREV_INUSE;
	  assert((bck->bk->size & NON_MAIN_ARENA) == 0);//默认不启用assert
	  /*
		large bin中的chunk是按从大到小排列的，如果size < large bin 
		的最后一个chunk，说明size是这个large bin中的最小的，我们把它
		加入到此large bin尾部。
	  */
	  if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) {
		  
		  fwd = bck;
		  bck = bck->bk;
		  
		  /*
		  large bin 中size最小的chunk的fd_nextsize会指向size最大的
		  那个chunk，也就是首部的chunk。同样，large bin 中size最大的
		  chunk的bk_nextsize会指向size最小的那个chunk。
		  victim的bk_nextsize指向large bin原来最小的chunk，它的
		  bk_nextsize指向最大的那个chunk。那么原来的最小的就成了第二小的了。
		  把它fd_nextsize和bk_nextsize都修正。
		  */
		  victim->fd_nextsize = fwd->fd;
		  victim->bk_nextsize = fwd->fd->bk_nextsize;
		  //最大size的chunk的bk_nextsize，和原来最小chunk的bk_nextsize都指向victim
		  fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
	  } 
	  else //如果victim不是large bin 中最小的chunk
	  {
		  assert((fwd->size & NON_MAIN_ARENA) == 0);//默认不启用assert
		  //从大到小（从头到尾）找到合适的位置
		  while ((unsigned long) size < fwd->size) {
			  fwd = fwd->fd_nextsize;
			  assert((fwd->size & NON_MAIN_ARENA) == 0);
		  }
	//如果size刚好相等，就直接加入到其后面省的改fd_nextsize和bk_nextsize了
		  if ((unsigned long) size == (unsigned long) fwd->size)
			  fwd = fwd->fd;
		  else 
		  {
			  //size不相等，即size>fwd->size，把victim加入到纵向链表中
			  victim->fd_nextsize = fwd;
			  victim->bk_nextsize = fwd->bk_nextsize;
			  fwd->bk_nextsize = victim;
			  victim->bk_nextsize->fd_nextsize = victim;
		  }
		  bck = fwd->bk;
	  }
  } 
  else //如果large bin 为空，将victim加入到纵向列表
	victim->fd_nextsize = victim->bk_nextsize = victim;
}
//#define mark_bin(m, i)    ((m)->binmap[idx2block (i)] |= idx2bit (i))
mark_bin(av, victim_index); //把victim加入到的bin的表示为非空
//把victim加入到large bin的链表中
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

1
2
3
4

victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;

1

victim->bk_nextsize->fd_nextsize = victim;

1

bck->fd = victim;

1
2

if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
    malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");

 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

if ((unsigned long)(size)
	< (unsigned long)chunksize_nomask(bck->bk))
{
	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(chunk_main_arena(fwd));
	while ((unsigned long)size < chunksize_nomask(fwd))
	{
		fwd = fwd->fd_nextsize;
		assert(chunk_main_arena(fwd));
	}
	if ((unsigned long)size
		== (unsigned long)chunksize_nomask(fwd))
		/* Always insert in the second position.  */
		fwd = fwd->fd;
	else
	{
		victim->fd_nextsize = fwd;
		victim->bk_nextsize = fwd->bk_nextsize;
		if (__glibc_unlikely(fwd->bk_nextsize->fd_nextsize != fwd))
			malloc_printerr("malloc(): largebin double linked list corrupted (nextsize)");
		fwd->bk_nextsize = victim;
		victim->bk_nextsize->fd_nextsize = victim;
	}
	bck = fwd->bk;
	if (bck->fd != fwd)
		malloc_printerr("malloc(): largebin double linked list corrupted (bk)");
}

1
2

victim->bk_nextsize = fwd->fd->bk_nextsize;
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;

1

fwd->fd->bk_nextsize->fd_nextsize = victim;