原理
一旦涉及到free内存，那么就意味着有新的chunk由allocated状态变成了free状态，此时glibc malloc就需要进行合并操作——向前以及(或)向后合并。这里所谓向前向后的概念如下：将previous free chunk合并到当前free chunk，叫做向后合并；将后面的free chunk合并到当前free chunk，叫做向前合并。
完整的unlink宏如下
Copy 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;
}
}
}
} 最简单版本unlink宏如下
Copy /* Take a chunk off a bin list */
define unlink (P , BK , FD) {
FD = P -> fd;
BK = P -> bk;
FD -> bk = BK;
BK -> fd = FD;
} 一、向后合并：
相关代码如下：
Copy /*malloc.c int_free函数中*/
/*这里p指向当前malloc_chunk结构体，bck和fwd分别为当前chunk的向后和向前一个free chunk*/
/* consolidate backward */
if ( ! prev_inuse (p)) {
prevsize = p -> prev_size;
size += prevsize;
#修改指向当前chunk的指针，指向前一个chunk。
p = chunk_at_offset(p , - (( long ) prevsize)) ;
unlink(p , bck , fwd) ;
} 首先检测前一个chunk是否为free，这可以通过检测当前free chunk的PREV_INUSE(P)比特位知晓。在本例中，当前chunk（first chunk）的前一个chunk是allocated的，因为在默认情况下，堆内存中的第一个chunk总是被设置为allocated的，即使它根本就不存在。
如果为free的话，那么就进行向后合并：
1)将前一个chunk占用的内存合并到当前chunk; 2)修改指向当前chunk的指针，改为指向前一个chunk。 3)使用unlink宏，将前一个free chunk从双向循环链表中移除(这里最好自己画图理解，学过数据结构的应该都没问题)。
在本例中由于前一个chunk是allocated的，所以并不会进行向后合并操作。
二、向前合并操作：
首先检测next chunk是否为free。那么如何检测呢？很简单，查询next chunk之后的chunk的 PREV_INUSE (P)即可。相关代码如下：
Copy ……
/*这里p指向当前chunk*/
nextchunk = chunk_at_offset (p , size);
……
nextsize = chunksize (nextchunk);
……
if (nextchunk != av -> top) {
/* get and clear inuse bit */
nextinuse = inuse_bit_at_offset(nextchunk , nextsize) ; #判断nextchunk是否为free chunk
/* consolidate forward */
if ( ! nextinuse) { #next chunk为free chunk
unlink(nextchunk , bck , fwd) ; #将nextchunk从链表中移除
size += nextsize; #p还是指向当前chunk只是当前chunk的size扩大了，这就是向前合并！
} else
clear_inuse_bit_at_offset(nextchunk , 0 ) ;
……
} 整个操作与”向后合并“操作类似，再通过上述代码结合注释应该很容易理解free chunk的向前结合操作。在本例中当前chunk为first，它的下一个chunk为second，再下一个chunk为top chunk，此时 top chunk的 PREV_INUSE位是设置为1的(表示top chunk的前一个chunk，即second chunk, 已经使用)，因此first的下一个chunk不会被“向前合并“掉。
介绍完向前、向后合并操作，下面就需要了解执行free（）合并后或者因为不满足合并条件而没合并 的chunk该如何进一步处理了。在glibc malloc中，会将合并后的chunk放到unsorted bin中(还记得unsorted bin的含义么？)。相关代码如下：
Copy /*
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); #获取unsorted bin的第一个chunk
/*
/* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
#define unsorted_chunks (M) ( bin_at (M , 1 ))
*/
fwd = bck -> fd;
……
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); #设置当前chunk的size , 并将前一个chunk标记为已使用
set_foot (p , size); #将后一个chunk的prev_size设置为当前chunk的size
/*
/* Set size/use field */
#define set_head (p , s) ((p) -> size = (s))
/* Set size at footer (only when chunk is not in use) */
#define set_foot (p , s) (((mchunkptr) (( char * ) (p) + (s))) -> prev_size = (s))
*/ 上述代码完成的整个过程简要概括如下：将当前chunk插入到unsorted bin的第一个chunk(第一个chunk是链表的头结点，为空)与第二个chunk之间(真正意义上的第一个可用chunk)；然后通过设置自己的size字段将前一个chunk标记为已使用；再更改后一个chunk的prev_size字段，将其设置为当前chunk的size；然后更改后一个chunk的size字段的p位，将其设置为0，表示前一个chunk为空闲。
注意：上一段中描述的”前一个“与”后一个“chunk，是指的由chunk的prev_size与size字段隐式连接的chunk，即它们在内存中是连续、相邻的！而不是通过chunk中的fd与bk字段组成的bin(双向链表)中的前一个与后一个chunk，切记！。
三、Unlink部分安全检测机制
size大小检测
Copy #判断nextsize的大小是否是一个正常的值，如果我们fake glibc时将size改成了很大的数，期望达到相应的效果 , 在nextsize的检测中就会出错
if ( __builtin_expect (nextchunk -> size <= 2 * SIZE_SZ , 0 )
|| __builtin_expect (nextsize >= av -> system_mem , 0 ))
{ //如果nextsize小于最小的chunk大小，或者大于了整个分配区的内存总量，报错
errstr = "free(): invalid next size (normal)" ;
goto errout;
}
#由于P已经在双向链表中，所以有两个地方记录其大小，所以检查一下其大小是否一致。
if ( __builtin_expect ( chunksize (P) != prev_size ( next_chunk (P)) , 0 )) \
malloc_printerr ( "corrupted size vs. prev_size" ); 双链表冲突检测
Copy #该机制会在执行unlink操作的时候检测链表中前一个chunk的fd与后一个chunk的bk是否都指向当前需要unlink的chunk。这样攻击者就无法替换second chunk的fd与fd了
if ( __builtin_expect (FD -> bk != P || BK -> fd != P , 0 )) \
malloc_printerr (check_action , "corrupted double-linked list" , P , AV); \ Double Free检测
Copy /* Lightweight tests: check whether the block is already the top block*/
//判断当前free的chunk是否是top chunk，因为top chunk本身就是一个空闲的chunk，如果是top chunk,造成 double free
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. */
if ( __builtin_expect ( contiguous (av) //不是通过mmap分配的，是通过sbrk()分配的
&& ( char * ) nextchunk //下一个chunk的地址如果已经超过了top chunk的结束地址，报错
>= (( char * ) av -> top + chunksize (av -> top)) , 0 )){
errstr = "double free or corruption (out)" ;
goto errout;
}
/* Or whether the block is actually not marked used. */
if ( __glibc_unlikely ( ! prev_inuse (nextchunk))){ //如果下一个chunk没有标示将要释放的这个chunk 的p位为0，说明chunk 可能被double free
errstr = "double free or corruption (!prev)" ;
goto errout;
} 利用
通过溢出设置chunk 0数据，伪造fake_chunk
如图：
Copy chunk0 malloc返回的ptr0 chunk1 malloc返回的ptr1
| | | |
+-----------+---------+----+----+----+----+----+------+------+----+----+------+
| | |fake|fake|fake|fake| D | fake | fake | | | |
| | |prev|size| fd | bk | A | prev | size&| | | |
| prev_size |size&Flag|size| | | | T | size | flag | | | |
| | | | | | | A | | | | | |
| | | | | | | | | | | | |
+-----------+---------+----+----+----+----+----+------+------+----+----+------+ 我们在malloc返回的ptr0（chunk 0）开始地方构造的数据：
Copy p32(0) + p32(81) + p32(&fake_chunk-12) + p32(&fake_chunk-8) + "A"*(80-4*4) + p32(80) + p32(88) 这样的话将chunk 0的mem空间伪造成一个fake_chunk，其中fake_fd=p32(&fake_chunk-12) 代表伪造的chunk头在程序内存空间中的地址-12， fake_bk=p32(&fake_chunk-8) 这样做的话执行unlink操作时
Copy FD = P -> fd = & fake_chunk - 12 ，
BK = P -> bk = & fake_chunk - 8 ，
FD -> bk ，即 * ( & fake_chunk - 12 + 12 ) = * ( & fake_chunk) = buf[ 0 ] = fake_chunk = p
BK -> fd ，即 * ( & fake_chunk - 8 + 8 ) = * ( & fake_chunk) = buf[ 0 ] = fake_chunk = p 这样就绕过了双向链表检查。
Copy if ( __builtin_expect (FD -> bk != P || BK -> fd != P , 0 ))
malloc_printerr (check_action , "corrupted double-linked list" , P); 接下来绕过前后size检查，这个就很简单，只需将chunk 1的fake_prev_size覆盖为ptr0当前mem空间大小即80，并且fake_chunk的fake_size大小必须为ptr0当前mem空间大小加上p标志位=81.
覆盖chunk 1的fake_size&flag要正确，为偶数代表前一个chunk为空可合并，大小满足原本chunk大小，这样可以避免错误的size大小以致double free报错.
free(chunk[1])，触发unlink
由于在 chunk 1 前面构造了一个伪造的空闲内存块，当free(chunk[1])时，就会对伪造的空闲内存块进行unlink操作：
Copy F = p -> fd; #F = & fake_chunk - 12
B = p -> bk; #B = & fake_chunk - 8
if (F -> bk == p && B -> fd == p){
F -> bk = B; #即buf[ 0 ] = B = & fake_chunk - 8
B -> fd = F; #即buf[ 0 ] = F = & fake_chunk - 12
} 从上可知，unlink后，buf[0]存的不再是ptr0 的地址了，而是&fake_chunk - 12 (即 如下图中的 &buf-12)。此时我们只关心buf数组的内存，其布局如下：
总结
程序中存在堆溢出且长度可观时，很容易构造出unlink；但是当程序没有长度溢出，或者堆大小固定时，我们可以构造chunk错位（伪造）的方式来构造unlink的空闲chunk；还有就是利用合并后被放入unsortedbin中的chunk，利用UAF ，对合并前的堆块进行构造。详细见2018强网杯silent2 和网鼎杯Pwn之babyheap
参考
Linux堆溢出漏洞利用之unlink – 阿里移动安全
