Glibc Heap Exploit 坐牢笔记 - 0x01

(Updated: )
Heap
,

# 堆相关数据结构

# chunk 大小问题

# 最小 chunk 大小、用户 malloc 申请大小和实际 malloc 分割出来的 chunk 大小的关系

众所周知，在 Glibc 源码中，malloc_chunk 的结构体的原码如下：

1
2
3
4
5
6
7
8
9
10
11
12
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;
};

这里面可以看到，如果一个 chunk 无论是处在 allocated 的状态下还是处于 free 状态下，他的 prev_size 和 size 这两个东西是必须存在的，而用户真正可以使用的空间是从 fd 那里开始的。
所以对于一个 chunk，它的实际大小其实是：这个 chunk 对应的存储数据的大小 + 2*size_t=size。
但是众所周知，chunk 存在下一个 chunk 的 prev_size 被复用到当前 chunk 里面用作存储数据。因此，我们可以算出用户实际可以使用的最大空间就是：当前 chunk 存储数据的空间大小 + size_t=size-size_t。
但是用户申请的大小是另一个概念。
众所周知，chunk 存在内存对齐的概念。下面是其在 Glibc 原码中的宏定义：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#ifndef MALLOC_ALIGNMENT
# if !SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_16)
/* This is the correct definition when there is no past ABI to constrain it.

   Among configurations with a past ABI constraint, it differs from
   2*SIZE_SZ only on powerpc32.  For the time being, changing this is
   causing more compatibility problems due to malloc_get_state and
   malloc_set_state than will returning blocks not adequately aligned for
   long double objects under -mlong-double-128.  */

#  define MALLOC_ALIGNMENT       (2 *SIZE_SZ < __alignof__ (long double)      \
                                  ? __alignof__ (long double) : 2 *SIZE_SZ)
# else
#  define MALLOC_ALIGNMENT       (2 *SIZE_SZ)
# endif

这里定义的 MALLOC_ALIGNMENT 就是规定了内存对齐的字节数。可以看到是 2 * SIZE_SZ。这里的 SIZE_SZ 就是 size_t，i386 下是 4 字节，x64 下是 8 字节。所以 32 位下对齐的是 8 字节，对应两个 p32 () 的大小，64 位下就是 16 字节，对应两个 p64 () 的大小。
所以堆管理器为了节省空间，会根据用户申请的空间堆实际申请空间大小进行调整，考虑内存对齐、内存复用等因素，我们大致可以推断出以下内容：
1. 当用户申请的内存小于 2 * size_t 的时候，就申请 2 * size_t 的大小的当前 chunk 存储数据的空间，加上内存复用的空间，实际就是可用 3 * size_t 的大小。
2. 当用户申请的大小刚好满足 2n * size_t < 申请 size <= 2n * size_t + size_t 的时候，实际上申请的当前 chunk 内的存储数据的空间只有 2n * size_t ，剩下的几个字节由复用的内存进行存储。
3. 当用户申请的大小满足 (2n+1) * size_t < 申请的内存 < (2n+2) * size_t 的时候，实际上申请的内存是 (2n+2) * size_t 的当前 chunk 存储数据的空间，因为要进行内存对齐。
这里给出对应的宏进行参考：
1
2
3
4
5
6
7
8
9
10
#define request2size(req) \
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? MINSIZE : ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

#define checked_request2size(req, sz) \
if (REQUEST_OUT_OF_RANGE(req))    \
{                                 \
__set_errno(ENOMEM);          \
return 0;                     \
}                                 \
(sz) = request2size(req);

# 关于 bins 数组和 bin 结构的问题

我们知道，bin 实际上是一个双向循环链表，bins 数组将除了 fastbin 的 bin 的入口进行按照对应 bin 存储的 chunk 大小顺序进行串联，并且通过宏实现寻找对应大小 bin，之后找到遍历双向循环链表的入口。

# bins 数组结构

我们首先看看 bins 数组的结构。
我们首先看看在 malloc_state 中 bins 数组的声明：

1
2
3
4
5
6
7
8
9
10
#define NBINS             128
struct malloc_chunk;
typedef struct malloc_chunk* mchunkptr;
struct malloc_state
{
... ... ... ...
  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];
... ... ... ...
};

可以看到 bins 数组申请的大小是 254 个 mchunkptr。也就是存储 127 个 bin，也就是 127 和双向循环链表的入口。此时我们大致了解到，bins 数组中对应每个 bin 占用 bins 数组两个 mchunkptr，即成对出现。
以下是关于 bins 的几个宏：
1
2
3
4
5
6
typedef struct malloc_chunk *mbinptr;

/* 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))

这里的 m 就是 malloc_state,i 就是要查找的对应 bin 的下标（这里的下标并不是 bins 数组下标，在这里就得到了体现。）

# bins 中 bin 的存储与访问

我们可以看到，bin_at 尝试去寻找 bin 的时候，取到的下标永远是偶数，因此我们可以知道，bin 在 bins 数组里面是连续相邻成对出现的。即：
bin [0],bin [1] 是一个 bin
bin [2],bin [3] 是一个 bin
bin [4],bin [5] 是一个 bin
，当然这里 bins 数组存储的只是每个 bin 的入口，或者可以说是末尾，毕竟是双向循环链表。
我们知道，一个 bin 的双向循环链表的开头是一个 front（是一个 chunk），这个 front 对应的就是 bins 数组那一对。为了节省空间，这里 front 仅仅保留了 fd、bk 这两个元素，对应的就是 bins [2n]、bins [2n+1]。
用图表画出来就是：

注意这里的指针并不是图中显示的那样。
实际上，这里的每一个 fd 都连接到下一个 chunk 的开头，即 prev_size 那里。同样所有的 bk 都是连接到前一个 chunk 的 prev_size 那里。
具体可以自己写几个 chunk 试验一下。

bins 数组中的 bin 有三种类型：unsortedbin,smallbin,largebin，他们对应的位置是：
第 1 个 ：unsorted bin
第 2 ~ 63 个：small bin
第 64 ~ 127 个：large bin

# largebin 独自的双向循环链表

这里只有 largebin 启用了 fd_nextsize,bk_nextsize 这两个元素，具体连接方式：
largebin 每个 bin 选出对应大小的代表元，这些代表元用 fd_nextsize,bk_nextsize 连成一个双向循环链表。

# bins 数组总结

这里总结一下 bins 数组：

# fastbin

说了 bins，顺便该说说不存在于 bins 数组的 bin---fastbin（虽然这个挺好理解的）
结构就是相当于单向链表版本的 bins 数组，malloc_state 中的定义就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct malloc_chunk *mfastbinptr;
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)


/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)

#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)

struct malloc_state
{
... ... ... ...
  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
... ... ... ...
};

直接放个图就啥都明白了，这个没啥难度。

# Conclusion

这篇笔记着重澄清了 bins 数组和 bin 之间的关系以及存储结构等内容，顺便写了一下 fastbin 的结构。
这部分内容对于部分 Glibc 教程来说基本上写的不是不详细就是不易理解。这里仅仅作为本人理解的内容，如有错误，速速指出！！！！！！！。

# ByeBye ༼ つ ◕_◕ ༽つ

༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ
༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ
༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ
༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ
༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ༼ つ ◕_◕ ༽つ