glibc-2.23源码分析(完结)

12月忙着期末考试(T_T),其余时间都在打buu的题目,解题都放在了https://blog.csdn.net/zzq487782568?spm=1000.2115.3001.5343

放假了,准备花几天时间写一下glibc的源码分析。2.23下没有tcache,主要对_int_malloc_int_free这两个部分进行分析

malloc部分

一步一步来,先看一下malloc部分的吧。

struct_malloc_chunk

有pwn堆基础的应该会知道上面定义的是什么吧。其实就是堆的最最基本的组成形式。

prev_size:前一个chunk为free时会被调用

size:堆的大小,包含着prev_size、size、data。

fd,bk:当chunk被free后就会出现,将被释放后同大小的chunk形成一个链表(根据size来)

fd_nextsize,bk_nextsize:被free后使用。用来链接其它的chunk。

这样看的话堆的结构就很明确。堆的结构就写到这里了。

chunk 宏

Size and alignment checks and conversions

这里大致就是尺寸和对齐的检查和转换。malloc头到用户指针的转换,可分配最小的chunk和size等功能

chunk2mem:将指向chunk header移到fd

mem2chunk:与上面相反

MIN_CHUNK_SIZE:最小的chunk的size,应该有header和fd、bk

offestof:为了方便计算出某个成员的偏移

MINSIZE:取反为了消除标志位。

aligned_ok:检查是否与malloc_alignment对齐,不对齐则为0

misaligned_chunk:chunk是否对齐,没有对齐则返回未对齐的字节数。

request size

REQUEST_OUT_OF_RANGE:检查用户请求的内存大小是否大于规定的最大内存大小。

request2size:将用户请求的内存大小转换为内存对齐的大小。

checked_request2size:很明显,为request2size加上了size的检查

Physical chunk operations

有堆基础的应该知道这上面是什么了。

PREV_INUSE:物理相邻的上一个chunk是否处于被分配状态

IS_MMAPPED:是否由mmap()进行内在分配得到

NON_MAIN_ARENA:是否是一个不属于main_arena的chunk

Bits to mask off when extracting size

Note: IS_MMAPPED is intentionally not masked off from size field in macros for which mmapped chunks should never be seen. This should cause helpful core dumps to occur if it is tried by accident by people extending or adapting this malloc.

这里不需要太多解释了,重点看unstortedbin smallbin largebin,和_int_malloc_int_free这两部分的代码

Bins

当chunk被释放后会以size大小来组成一个数组,用以存放闲置chunk的数组,按照size来存放在不同的下标的bin中。一共有128个bin,bin中的chunk链表采取FIFO机制,bins一共可以有三类:unstorted bin、small bin、large bin。

unstorted bin

pwn的堆题的话,许多都是unstorted bin来泄露libc。什么是unstroted bin呢?

可以看到unstorted bin宏调用了bin_at这个宏

bin_at:取出位于下标i的bin chunk,这里获得的指针为原始存在bin中的指针再减去了chunk header的大小所得到的值,这是由于在bins数组中存放的为fd/bk,需要减去chunk header的大小才能获得一个指向chunk的指针而不是指向mem的指针,从这里我们也可以看出一个bin占据bins数组两格的空间。

next_bin:获取下一个bin

first && last:获得bin chunk的fd/bk

在chunk分割过程中所剩余的chunk、以及所有回归闲置的chunk都会首先被存放在unstortedbin中。当再次malloc时其中的chunk会被放到正常的bins中,如fastbin。

这里对存放unstortedbin的size没有做限制。bin 0不存在,bin 1放的是unstorted bin。

small bin

bin 2开始放small bin。

最大的small bin的size在32位下为为504,64是1008,small bins的数量为62

large 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
31
#define largebin_index_32(sz)                                                \
(((((unsigned long) (sz)) >> 6) <= 38) ? 56 + (((unsigned long) (sz)) >> 6) :\
((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
126)

#define largebin_index_32_big(sz) \
(((((unsigned long) (sz)) >> 6) <= 45) ? 49 + (((unsigned long) (sz)) >> 6) :\
((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
126)

// XXX It remains to be seen whether it is good to keep the widths of
// XXX the buckets the same or whether it should be scaled by a factor
// XXX of two as well.
#define largebin_index_64(sz) \
(((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) :\
((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
126)

#define largebin_index(sz) \
(SIZE_SZ == 8 ? largebin_index_64 (sz) \
: MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) \
: largebin_index_32 (sz))

获取index的过程有点复杂。largebin_index_32(sz) 这个宏是32位下获取large bin chunk在bin中的index。一共有63个large bin。

在一些pwn中有时会用的unlink这个操作来进行堆块重叠。

  • p是被unlink的chunk。

  • 从源码的第一行可以看到FD是p->fd,BK则是p->bk。

  • 然后会进行检查,检查FD->bk和BK->fd是否都为P,若是的话则将FD->bk=BK,BK->fd=FD

  • 假如size是在small bin的范围内,则unlink结束。若不在则还需要将它从nextsize链表中进行unlink

  • 检查P->fd_nextsize->bk_nextsize和P->bk_nextsize->fd_nextsize是否都指向P

  • FD->fd_nextsize不为NULL时,将P从所处nextsize链表中unlink,为NULL时,若P->fd_nextsize指向P则将FD->fd_nextsize = FD->bk_nextsize = FD都 指向FD,否则使用FD替换掉P所在的nextsize链表中的位置

具体的unlink的实战在我blog的其他文章下专门写了。

binmap

To help compensate for the large number of bins, a one-level index structure is used for bin-by-bin searching. binmap’ is a bitvector recording whether bins are definitely empty so they can be skipped over during during traversals. The bits are NOT always cleared as soon as bins are empty, but instead only when they are noticed to be empty during traversal in malloc.

其实就是因为bins的数量多,binmap使用位向量来标记bins数组中的每一个bin,以便于能够快速遍历bins。

fastbin

定义上的最大的fastbin chunk的size—–>MAX_FAST_SIZE。超过这个size的chunk都将会被放进unsorted bin中。

__int_malloc

malloc中最重要的部分来了。对它进行慢慢地分析吧。

变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static void *
_int_malloc (mstate av, size_t bytes)//参数为指针av,申请空间bytes,其函数声明
{
INTERNAL_SIZE_T nb; /* normalized request size */ //对齐后所需内存大小
unsigned int idx; /* associated bin index */ //保存chunk在bins中的下标
mbinptr bin; /* associated bin */ //保存bin

mchunkptr victim; /* inspected/selected chunk */ //保存候选chunk
INTERNAL_SIZE_T size; /* its size */ //chunk的size
int victim_index; /* its bin index */ //候选chunk的index

mchunkptr remainder; /* remainder from a split */ //从候选chunk分配内在后剩余的内存指针
unsigned long remainder_size; /* its size */ //剩余部分内存大小

unsigned int block; /* bit map traverser */
unsigned int bit; /* bit map traverser */
unsigned int map; /* current word of binmap */

mchunkptr fwd; /* misc temp for linking */
mchunkptr bck; /* misc temp for linking */

const char *errstr = NULL;

开头定义了一些局部变量在_int_malloc中。一些变量的意思写在了注释里

开始分配

这里其实就是取得对齐后的size值,假如没有可用的arena,则随机分配一块内存并返回

fast 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
31
32
33
34
35
36
  /*
If the size qualifies as a fastbin, first check corresponding bin.
This code is safe to execute even if av is not yet initialized, so we
can try it without checking, which saves some time on this fast path.
*/
//如果一个size在fast bins中的范围内,则从fast bins中分配,第一次调用malloc时,max_fat为0

if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb); //大小在fast bins中的下标
mfastbinptr *fb = &fastbin (av, idx); //从对应下标中取出堆块指针
mchunkptr pp = *fb;
//若存在可用bin,将bin从链表中取出。取出当前bin的fd放入链表尾,fd的值不能和当前bin相同
do
{
victim = pp;
if (victim == NULL)
break;
}
while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
!= victim);
if (victim != 0) //这里前面定义了,候选chunk,如果候选chunk存在,则对其进行利用
{
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0)) //检查size!!!!
{
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); //返回chunk地址
alloc_perturb (p, bytes);
return p;
}
}

注意这里会检测size,z1r0在初学堆时,2.23下进行利用,申请堆块到malloc发现会出错malloc(): memory corruption (fast)原因是malloc_hook那里的size不一样才导致malloc失败,这时就要找有没有符合size的地址,在malloc_hook - 0x23那里存在0x7f的大小,将地址申请在那里即可。(同时在bins中的大小也要符合size!!!)

small 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
31
32
33
34
35
36
37
38
 /*
If a small request, check regular bin. Since these "smallbins"
hold one size each, no searching within bins is necessary.
(For a large request, we need to wait until unsorted chunks are
processed to find best fit. But for small ones, fits are exact
anyway, so we can check now, which is faster.)
*/
//如果大小在small bins范围内,则在small bins中分配
if (in_smallbin_range (nb))
{
idx = smallbin_index (nb); //所需大小对应的下标
bin = bin_at (av, idx); //从arena获取下标对应的bin

if ((victim = last (bin)) != bin) //如果候选chunk等于表头,表示该链表为空
{
if (victim == 0) /* initialization check *///如果候选chunk为0,表示还没有创建双向循环链表
malloc_consolidate (av); //第一次malloc时会调用这个函数合并所有的fast bin
else //候选chunk不为0,尝试将候选chunk从small bin中取出
{
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); //设置候选chunk的inuse标志,该标志位于下一个chunk size位的第0个bit
bin->bk = bck; //将bin从链表中取出,相当于unlink。
bck->fd = bin; ////最后一个chunk中的fd为main_arena+xxx

if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb); //进行检测
void *p = chunk2mem (victim); //返回chunk
alloc_perturb (p, bytes);
return p;
}
}
}

可以看到上面有一个相当于unlink的功能,其实small bin也有对应的small bin attack,需要伪造 一个heap地址来绕过bck->fd != victim,可以看到最后一个chunk中的fd为main_arena+xxx因为在伪造chunk时还需要libc地址,没什么利用价值,但是在高版本中比如glibc2.27和glibc2.29中malloc small bin操作不一样,可以任意地址写入libc地址。这个笔者在写后面的高版本glibc源码分析再看一下。

large 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
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
  /*
If this is a large request, consolidate fastbins before continuing.
While it might look excessive to kill all fastbins before
even seeing if there is space available, this avoids
fragmentation problems normally associated with fastbins.
Also, in practice, programs tend to have runs of either small or
large requests, but less often mixtures, so consolidation is not
invoked all that often in most programs. And the programs that
it is called frequently in otherwise tend to fragment.
*/
//大小不属于small bins,则位于large bin中。在malloc源码中,把非small bin的部分定义为large bin
else
{
idx = largebin_index (nb); //计算所需大小对应large bins的下标
if (have_fastchunks (av)) //判断是否存在属于fast bins的空闲chunk
malloc_consolidate (av); //合并所有的fast bin
}

/*
Process recently freed or remaindered chunks, taking one only if
it is exact fit, or, if this a small request, the chunk is remainder from
the most recent non-exact fit. Place other traversed chunks in
bins. Note that this step is the only place in any routine where
chunks are placed in bins.

The outer loop here is needed because we might not realize until
near the end of malloc that we should have consolidated, so must
do so and retry. This happens at most once, and only when we would
otherwise need to expand memory to service a "small" request.
*/

for (;; )
{
int iters = 0;
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av)) //反向遍历unsorted bins双向循环链表,直到候选chunk指向头节点
{
bck = victim->bk;
if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0) //判断size是否合法
|| __builtin_expect (victim->size > av->system_mem, 0))
malloc_printerr (check_action, "malloc(): memory corruption",
chunk2mem (victim), av);
size = chunksize (victim); //若合法则取出size位。

/*
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.
*/
//如果这个chunk大小属于small bins,且unsorted bins中只有一个chunk,且这个chunk为last remainder chunk,且这个chunk的大小大于所需要的size + MINSIZE
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中取出所需要的部分,也表头形成双向循环链表
remainder_size = size - nb; //取出剩余部分
remainder = chunk_at_offset (victim, nb); //获得chunk指针
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder; ///arena指向remainder
av->last_remainder = remainder; //设置新的remainder
remainder->bk = remainder->fd = unsorted_chunks (av); //remainder指向arena
if (!in_smallbin_range (remainder_size)) //如果剩余部分不为small bins,则只能是large bins
//因此需要将fd_nextsize和bk的那个清空,unsorted bin无需这两个
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}

set_head (victim, nb | PREV_INUSE | //设置chunk的相关信息
(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 */ //将bin从unsortedbin中取出
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);

/* Take now instead of binning if exact fit */ //若size位等于所需要大小,则设置标志位,将bin取出并返回用户指针

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;
}

/* place chunk in bin */
//若size属于small bin,则将chunk加入到bck和fwd之间,作为small bins的第一个chunk
if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
else //如果不属于small bin,则是largebin,将chunk加入到bck和fwd之间,作为large bins的第一个chunk
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;

/* maintain large bins in sorted order */
if (fwd != bck) //fwd不等于bck,说明large bins中存在空闲chunk
{
/* 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);
//如果当前size比最后一个chunk size还要小,则将当前size的chunk加入到chunk size链表尾,然后将所有大小的链表取出首个chunk到一起
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) //正向遍历chunk size链表,找到第一个chunk大小小于等于当前大小的chunk
{
fwd = fwd->fd_nextsize;
assert ((fwd->size & NON_MAIN_ARENA) == 0);//chunk是否位于main_arena中。
}

if ((unsigned long) size == (unsigned long) fwd->size)//如果相等
/* Always insert in the second position. *///插入第二个位置
fwd = fwd->fd;
else//否则将伸出一个大小等于当前size的chunk链表,将该链表加入到chunk size链表的尾部
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
}
}
else//当链表中只有一个chunk时
victim->fd_nextsize = victim->bk_nextsize = victim;
}
//将当前chunk加入large bins的空闲链表中
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
}

/*
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.
*/
//如果请求过大,扫描中的当前bin块按顺序排序以找到适合的最小值。为此使用跳过列表
//当处理完unsorted bins后,使用最佳匹配法匹配chunk

if (!in_smallbin_range (nb))//不存在于small bin中,那就是是否位于large bins中
{
bin = bin_at (av, idx);

/* skip scan if empty or largest chunk is too small */
//判断large bins是否为空,以及链表中最大size是否满足所需大小
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)))//循环寻找合适的chunk
victim = victim->bk_nextsize;

/* Avoid removing the first entry for a size so that the skip
list does not have to be rerouted. */
//为了尽量不破坏链表结构,尝试取出victim->fd作为候选chunk
if (victim != last (bin) && victim->size == victim->fd->size)//判断是否前一个结点的size与申请空间相等
victim = victim->fd;

remainder_size = size - nb;
unlink (av, victim, bck, fwd);//进行unlink。

/* Exhaust */
//如果小于MINSIZE,将整个chunk分配给应用层。
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);//设置inuse标记位
if (av != &main_arena)//是否位于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. */
//将剩余部分作为新chunk加入到unsorted bins中。
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))//若在large bin的范围内,将fd_nextsize和bk_nextsize设置为0。
{
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);//检测chunk
void *p = chunk2mem (victim);//转换为用户chunk
alloc_perturb (p, bytes);//初始化chunk
return p;//返回指针给应用层
}
}

large bin attack的话其实就是在插入的过程中伪造large bin的bk_nextsize以及bk,即可实现任意地址写堆地址

binmap

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
     /*
Search for a chunk by scanning bins, starting with next largest
bin. This search is strictly by best-fit; i.e., the smallest
(with ties going to approximately the least recently used) chunk
that fits is selected.

The bitmap avoids needing to check that most blocks are nonempty.
The particular case of skipping all bins during warm-up phases
when no chunks have been returned yet is faster than it might look.
*/
//在small bins和large bins中都没有找到大小合适的chunk,尝试从大小比所需大小更大的空闲chunk中寻找合适的
++idx;
bin = bin_at (av, idx);
block = idx2block (idx);
map = av->binmap[block];
bit = idx2bit (idx);

for (;; )
{
/* Skip rest of block if there are no more set bits in this block. */
//如果该块中没有更多的设置位,则跳过该块的其余部分
if (bit > map || bit == 0)
{
do
{
if (++block >= BINMAPSIZE) /* out of bins *///没有合适的chunk,尝试使用top chunk分配
goto use_top;
}
while ((map = av->binmap[block]) == 0);
//bin指向block的第一个bit对应的bin
bin = bin_at (av, (block << BINMAPSHIFT));
bit = 1;
}

/* Advance to bin with set bit. There must be one. */
//在block中遍历对应的bin,直到找到一个不为0的bit
while ((bit & map) == 0)
{
bin = next_bin (bin);
bit <<= 1;
assert (bit != 0);
}

/* Inspect the bin. It is likely to be non-empty */
//将chunk加入链表尾
victim = last (bin);

/* If a false alarm (empty bin), clear the bit. */
//若victim与bin链表头指针相同,表示该bin中没有空闲chunk
if (victim == bin)
{
av->binmap[block] = map &= ~bit; /* Write through */
bin = next_bin (bin);
bit <<= 1;
}

else
{
size = chunksize (victim);

/* We know the first chunk in this bin is big enough to use. */
//chunk大小是否满足
assert ((unsigned long) (size) >= (unsigned long) (nb));

remainder_size = size - nb; //计算分配后的剩余大小

/* unlink */
unlink (av, victim, bck, fwd); //进行unlink

/* Exhaust */
//剩余在小小于minsize,则将整个chunk分配给用户
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. */
//剩余部分作为新chunk加入到unsorted bins中
bck = unsorted_chunks (av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "malloc(): corrupted unsorted chunks 2";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;

/* advertise as last remainder */
//若分配大小属于small bin,将last_remainder设置为剩余部分构成的chunk
if (in_smallbin_range (nb))
av->last_remainder = remainder;
if (!in_smallbin_range (remainder_size))//属于large bin将fd_nextsize和bk_nextsize给设置为0
{
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;//返回指针
}
}

top chunk

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
	  use_top:
/*
If large enough, split off the chunk bordering the end of memory
(held in av->top). Note that this is in accord with the best-fit
search rule. In effect, av->top is treated as larger (and thus
less well fitting) than any other available chunk since it can
be extended to be as large as necessary (up to system
limitations).

We require that av->top always exists (i.e., has size >=
MINSIZE) after initialization, so if it would otherwise be
exhausted by current request, it is replenished. (The main
reason for ensuring it exists is that we may need MINSIZE space
to put in fenceposts in sysmalloc.)
*/
//获得top chunk指针与大小
victim = av->top;
size = chunksize (victim);
//满足size > nb + minsize才能分配
//这里的size为unsigned long当size为-1时,size会变得特别大,会符合条件,再控制下面的指针就可以任意地址写
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder;
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);

check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;//返回指针
}

/* When we are using atomic ops to free fast chunks we can get
here for all block sizes. */
//topchunk也无法满足要求则检查fast bins中是否存在空闲的chunk
else if (have_fastchunks (av))
{
malloc_consolidate (av);
/* restore original bin index */
//从small bin和large bins获取下标
if (in_smallbin_range (nb))
idx = smallbin_index (nb);
else
idx = largebin_index (nb);
}

/*
Otherwise, relay to handle system-dependent cases
*/
else
{//所有方法不可行,最后的解决方案是向系统申请一块新的内存
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
}
}

top chunk的漏洞利用手段:house of force,篡改top chunk的size字段,申请任意大小的堆内存

free 部分············_int_free

变量

1
2
3
4
5
6
7
8
9
10
11
12
13
static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
INTERNAL_SIZE_T size; /* its size */ //存储size字段值
mfastbinptr *fb; /* associated fastbin */ //存储fast bin堆块指针
mchunkptr nextchunk; /* next contiguous chunk */ //下一个chunk的指针
INTERNAL_SIZE_T nextsize; /* its size */ //下一个chunk size
int nextinuse; /* true if nextchunk is used */ //下一个chunk的使用情况
INTERNAL_SIZE_T prevsize; /* size of previous contiguous chunk */ //距离上一个堆块距离
mchunkptr bck; /* misc temp for linking */ //临时,bk指针指向的堆块
mchunkptr fwd; /* misc temp for linking */ //临时,fd指针指向的堆块
const char *errstr = NULL;
int locked = 0;

开始free

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
  size = chunksize (p);//获得目标chunk的size字段的值
/* Little security check which won't hurt performance: the
allocator never wrapps around at the end of the address space.
Therefore we can exclude some size values which might appear
here by accident or by "design" from some intruder. */
//安全检查,检查chunk指针合法性,是否对齐等,不会影响性能
if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
|| __builtin_expect (misaligned_chunk (p), 0))
{
errstr = "free(): invalid pointer";
errout:
if (!have_lock && locked)
(void) mutex_unlock (&av->mutex);
malloc_printerr (check_action, errstr, chunk2mem (p), av);
return;
}
/* We know that each chunk is at least MINSIZE bytes in size or a
multiple of MALLOC_ALIGNMENT. */
//size是否小于chunk的最小size,以及是否对齐
if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
{
errstr = "free(): invalid size";
goto errout;
}
//chunk是否在空闲状态(检查下一个chunk的p位)
check_inuse_chunk(av, p);

fast bins

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
74
75
76
  /*
If eligible, place chunk on a fastbin so it can be found
and used quickly in malloc.
*/
//因为是fastbin,所以这里判断了一下size是否小于0x80
if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

#if TRIM_FASTBINS
/*
If TRIM_FASTBINS set, don't place chunks
bordering top into fastbins
*/
//如果设置了TRIM_FASTBINS,就不能将与top chunk相邻的chunk放入fast bins
&& (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);
//将chunk放入fast bins中
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
{//检测double free,这里可以被绕过,free(1)free(2)free(1)
/* 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;
}
}

fast bins这里的话就是double free的利用。检查只会检查头部的chunk,而free(1)free(2)free(1)这样即可绕过。

unsorted bins

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
  /*
Consolidate other non-mmapped chunks as they arrive.
*/
//如果chunk不过通过mmap映射的,则chunk进入unsorted bins
else if (!chunk_is_mmapped(p)) {
if (! have_lock) {
(void)mutex_lock(&av->mutex);
locked = 1;
}
//下一个chunk的位置
nextchunk = chunk_at_offset(p, size);

/* Lightweight tests: check whether the block is already the
top block. */
//如果释放的堆块为top则触发异常
if (__glibc_unlikely (p == av->top))
{
errstr = "double free or corruption (top)";
goto errout;
}
/* Or whether the next chunk is beyond the boundaries of the arena. */
//下一个堆 块地址是否超过top chunk地址,超过则异常
if (__builtin_expect (contiguous (av)
&& (char *) nextchunk
>= ((char *) av->top + chunksize(av->top)), 0))
{
errstr = "double free or corruption (out)";
goto errout;
}
/* Or whether the block is actually not marked used. */
//chunk已经被free,触发异常
if (__glibc_unlikely (!prev_inuse(nextchunk)))
{
errstr = "double free or corruption (!prev)";
goto errout;
}
//size是否合法与对齐的情况
nextsize = chunksize(nextchunk);
if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (nextsize >= av->system_mem, 0))
{
errstr = "free(): invalid next size (normal)";
goto errout;
}

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

/* consolidate backward */
//若下一个chunk的p位也为1的话则进行unlink,向上合并
if (!prev_inuse(p)) {
prevsize = p->prev_size;
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
unlink(av, p, bck, fwd);
}
//下一个chunk不是top chunk的话,获得p标记位
if (nextchunk != av->top) {
/* get and clear inuse bit */
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

/* consolidate forward */
//下一个chunk已经空闲,则unlink向下合并
if (!nextinuse) {
unlink(av, nextchunk, bck, fwd);
size += nextsize;
} 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.
*/
//得到arena中的bins指针
bck = unsorted_chunks(av);
fwd = bck->fd;//指向最后一个进入unsorted bins的指针
if (__glibc_unlikely (fwd->bk != bck))//最后一个堆块bk不指向bins的话,触发异常
{
errstr = "free(): corrupted unsorted chunks";
goto errout;
}//chunk进入unsorted bins
p->fd = fwd;
p->bk = bck;
if (!in_smallbin_range(size))//chunk为large bins,将fd_nextsize和bk_nextsize设置为null
{
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);
}

/*
If the chunk borders the current high end of memory,
consolidate into top
*/

else {
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
check_chunk(av, p);
}

/*
If freeing a large space, consolidate possibly-surrounding
chunks. Then, if the total unused topmost memory exceeds trim
threshold, ask malloc_trim to reduce top.

Unless max_fast is 0, we don't know if there are fastbins
bordering top, so we cannot tell for sure whether threshold
has been reached unless fastbins are consolidated. But we
don't want to consolidate on each free. As a compromise,
consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
is reached.
*/
//如果size大于FASTBIN_CONSOLIDATION_THRESHOLD,则合并堆中所有空闲的fast bin
if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
if (have_fastchunks(av))
malloc_consolidate(av);
//如果为main_arena,且top chunk超过阈值,则切割arena
if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM
if ((unsigned long)(chunksize(av->top)) >=
(unsigned long)(mp_.trim_threshold))
systrim(mp_.top_pad, av);
#endif
} else {
/* Always try heap_trim(), even if the top chunk is not
large, because the corresponding heap might go away. */
heap_info *heap = heap_for_ptr(top(av));

assert(heap->ar_ptr == av);
heap_trim(heap, mp_.top_pad);
}
}
//解除互斥锁
if (! have_lock) {
assert (locked);
(void)mutex_unlock(&av->mutex);
}
}

free掉超过fast bin时,进unsorted bin,这时fd和bk指向main_arena+offest。此时如果有uaf,则可以直接输出main_arena+offest

mmap

1
2
3
4
5
6
7
8
  /*
If the chunk was allocated via mmap, release via munmap().
*/

else {
munmap_chunk (p);
}
}

不符合以上的所有情况,则直接解除内存映射

summary

看了_int_malloc_int_free这两部分源码,可以发现有很多地方并没有太过严格的检查。2.23下可以用fast bin double free,house全家桶等攻击手法https://ctf-wiki.org/pwn/linux/user-mode/heap/ptmalloc2/introduction/上讲得很全面,笔者在之前的文章上出写了很多利用手法,这篇文章仅仅用来学习libc-2.23的源码。

Reference

https://blog.csdn.net/qq_41988448/article/details/121859213
https://blog.csdn.net/njh18790816639/article/details/121846347
https://arttnba3.cn/2021/01/15/NOTE-0X00-MALLOC-2.23-PART-I/#%E5%9B%9B%E3%80%81Fastbins%EF%BC%9A%E5%BF%AB%E9%80%9F%E5%AD%98%E5%8F%96chunk%E7%9A%84%E6%95%B0%E7%BB%84
https://ctf-wiki.org/pwn/linux/user-mode/heap/ptmalloc2/introduction/
https://blog.csdn.net/qq_41988448/article/details/121590288