GLIBC环境下double-free堆操作漏洞利用原理及相关漏洞分析 作者：stardust 主页：http://www.nsfocus.com 日期：2003-07-02 Linux系统使用GNU C程序库，它的内存分配管理功能Malloc部分是Doug Lea实现的，此部分管理功能提供了malloc()、free()、realloc()等函数用于分配和释放位于堆中的内存。 按照Doug Lea的实现方式，整个堆区被划分成若干个连续的块(chunk)，堆区的内存结构可能是如下这样的： Heap 低地址 ---> 高地址 +----------------------+------------------------+-------------------------+ | U | F | U | U | F | U | TOP块 | +----------------------+------------------------+-------------------------+ 标记： U ---- 正在被使用的块 F ---- 空闲的块 TOP块 ---- 位于高地址最边缘的那个块，此块是所有块中最大的，而且也只有此块可以被扩大尽寸。 堆区中不可能出现两个相邻的空闲块，这是由free()函数的实现方式决定的，为了尽可能地减轻内存碎片化的程度，在释放某块内存时free()会检查与此块相邻的前后两个内存块是否为空闲块，如果当前块的紧邻前块是空闲的，则当前块会被合并到前块去，如果当前块的紧邻后块是空闲的，由后块会被合并到当前块。如果要释放的当前块紧邻TOP块则会肯定被合并到TOP块。 每个内存块的头部有一个用于管理当前块的管理结构，这个管理结构的长度对于正在被使用的块是8字节，而对于空闲的块由于另加了两个指针为16字节，管理结构的具体内容在malloc.c中的定义如下： struct malloc_chunk { INTERNAL_SIZE_T prev_size; /* 如果上一个块是空闲的话，此值为上一个块的长度 */ INTERNAL_SIZE_T size; /* 当前块的长度包括管理结构本身 */ struct malloc_chunk* fd; /* 双向链表的前指针 -- 只有在块空闲的时候才被使用到 */ struct malloc_chunk* bk; /* 双向链表的后指针 -- 只有在块空闲的时候才被使用到 */ }; 一个正在使用的内存块结构图如下： 0 16 32 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 上一个块的字节数(prev_size),如果上一个块空闲的话 | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 当前块的字节数 (size) |M|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 用户数据开始... . . . . (用户可以用空间大小) . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 这里chunk指针是malloc()在内部使用的，而malloc()调用返回给用户的是mem指针(chunk + 8)，对于用户来说chunk的管理结构是不可见的。 一个空闲的内存块结构图如下： 0 16 32 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 上一个块的字节数(prev_size) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `head:' | 当前块的字节数 (size) |M|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 前指针fd(指向链表中的下一个块) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 后指针bk(指向链表中的上一个块) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 未被双向链表使用的空间(也可能是0字节长) . . . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `foot:' | 上一个块的字节数 (等于chunk->size) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 可以看到与正在使用的块不同的是，空闲chunk管理结构除了prev_size和size字段外，增加了fd和bk两个用于双向链表的指针，这个双向链接的结构下面会讲到。需要注意的是，一个空闲块一旦被malloc分配出去给用户使用，fd和bk所在的位置会成为用户数据区的一部分，也就是说会被用户数据的前8个字节覆盖，对于堆漏洞的利用其实主要就是围绕着如果操纵这8个字节展开的。 上面两个表中都有一个"P"标志是"当前块字节数"(chunk->size)中的最低一位，表示是否上一块正在被使用。如果P位置1，则表示上一块正在被使用，这时chunk->prev_size通常为零；如果P位为零，则表示上一块是空闲块, 这时chunk->prev_size字段其实是上一个块用户数据区的一部分，任何一个块的空闲与否是由下一个块的chunk->size的P标志来确定的。 "M"位是表示此内存块是不是由mmap()分配的，如果置一，则是由mmap()分配的，那么在释放时会以另外的方式处理，与我们的现在的讨论无关。 两个标位在malloc.c中的定义如下： #define PREV_INUSE 0x1 #define IS_MMAPPED 0x2 由于malloc实现中是8字节对齐的，size字段的低3位总是不会被使用的，所以在实际计算chunk大小时，要去掉标志位。用以下的宏来计算块真实的大小： #define chunksize(p) ((p)->size & ~(SIZE_BITS)) 因为所分配的内存至少要包括管理结构的长度，所以一次malloc()操作，即便是malloc(0)，也会实际分配至少16字节的内存。 在Doug Lea实现的Malloc中，除了TOP块外的所有空闲块以长度大小被分组，它们的信息被存放在称为Bin的双向循环链表中，有128个Bin链表，它们分别存放特定长度的空闲内存块信息，单个Bin链表中每个单元包含的前后两个指针就是上面介绍的chunk管理结构中的fd和bk。系统在分配内存时首先会到Bin链表中寻找是否存在合适大小的内存块，如果找不到才会从TOP块中分割出一块来并把指针返回给用户进程。 Bin链表的索引指针存放在一个数组中，Malloc根据块的大小来获取Bin链表指针在数组中的索引。小于512字节的空闲内存块被认为是小块，由于内存块的大小一定大于等于16字节而且是8的倍数，这些小块的信息被存放在62个Bin链表中，第1个Bin链表存放16字节大小内存块的信息，第2个24链表存放32字节大小的，以此类推，第62个Bin链表存放504字节大小的空闲块信息，所有小块单个Bin链表所存放的块的大小都是一样的。所有大于504字节的空闲块被认为是大块，它们的信息存放在后66个Bin链表中，每个Bin链表存放了一定长度范围的空闲块。 下图表示了堆区中可能的Bin链表的链接情况，箭头方向表示指针的指向： Bin(64) +-----------------------------------------------------------+ +-> Bin(32) | Bin(32) | | <-------------+ +----+----------------------+ | | 空闲块1 | | | 空闲块2 | 空闲块3 空闲块4 | | +-------------+---+-+..v-------------------+..v-------------------+..+-------------+---+-+ |p_size|s=32|*fd|*bk| |p_size|s=64|*fd|*bk| |p_size|s=32|*fd|*bk| |p_size|s=64|*fd|*bk| ^-------------------+..+-------------+---+-+..+-------------+---+-+..^-------------------+ | Bin(32) | | | | | Bin(32) +------------------------------------+---+------------------+ +----+-------------------> Bin(64) | | Bin(64) | <------------------------------------+ +---------------------------+ 上图中分别有两个32字节和64字节的空闲块，各种长度的空闲内存块被链入各自所属的Bin链表，Bin(xx)表示相关的块属于管理xx字节长块的Bin链表。 Malloc的实现使用两个宏来完成对于Bin链表的插入和删除操作。用于删除单元的unlink宏定义如下： #define unlink( P, BK, FD ) { \ BK = P->bk; \ FD = P->fd; \ FD->bk = BK; \ BK->fd = FD; \ } 删除操作的图示如下，箭头方向为数据移动的方向： chunk0 chunk chunk1 +----------------------+..+----------------------+..+----------------------+ |prev_size|size|*fd|*bk| |prev_size|size|*fd|*bk| |prev_size|size|*fd|*bk| +----------------^-----+..+----------------+---+-+..+--------------------^-+ |_________________________| |_________________________| 宏实际所进行的操作就是： chunk0->fd <== chunk->fd chunk1->bk <== chunk->bk 也就是： chunk->bk + 8 <== chunk->fd chunk->fd + 12 <== chunk->bk 这是两个写内存的操作，如果我们这们能控制fd、bk这两个指针的值，就可以写任意4个字节的值到任意地址的内存中去。 unlink宏在malloc()和free()函数中都有用到，在malloc()中用于把已分配出去的内存块从链表中摘除下来，在free()中把已经合并到其他块中的内存块从链表中摘除下来。如何利用free()过程中的unlink操作可以参看W3的《一种新的Heap区溢出技术分析》，上面的分析其实都是从那儿C&P过来的。这回的CVS double-free漏洞则利用的是malloc中的unlink，要理解为什么能利用double-free漏洞，还有必要解释一下向Bin链表的插入操作，free()函数的主要工作就是调用frontlink宏把已经释放掉的内存块插入到管理相应大小的Bin链表中，Malloc的实现定义了frontlink宏来处理链表的插入： #define frontlink( A, P, S, IDX, BK, FD ) { \ if ( S < MAX_SMALLBIN_SIZE ) { /* 处理小块时 */ \ IDX = smallbin_index( S ); /* 获取Bin链表的索引 */ \ mark_binblock( A, IDX ); /* 标记此链表不再为空 */ \ BK = bin_at( A, IDX ); /* 定位Bin链表的地址 */ \ FD = BK->fd; \ P->bk = BK; /* 修改指针操作 */ \ P->fd = FD; /* 修改指针操作 */ \ FD->bk = BK->fd = P; /* 修改指针操作 */ \ } else { /* 处理大块时 */ \ IDX = bin_index( S ); \ BK = bin_at( A, IDX ); \ FD = BK->fd; \ if ( FD == BK ) { \ mark_binblock(A, IDX); \ } else { \ while ( FD != BK && S < chunksize(FD) ) { \ FD = FD->fd; \ } \ BK = FD->bk; \ } \ P->bk = BK; \ P->fd = FD; \ FD->bk = BK->fd = P; \ } \ } 假设一个Bin(32)的链表在被插入新单元之前的指向关系如下图所示，箭头方向表示指针的指向： Bin(32) Bin(32) <-------------+ +---------------------------+ 空闲块1 | | | 空闲块2 +-------------+---+-+.........................v-------------------+..+ |p_size|s=32|*fd|*bk| |p_size|s=32|*fd|*bk| | ^-------------------+.........................+-------------+---+-+..+ | Bin(32) | | +-----------------------------------------------------------+ +----> 插入新空闲块的操作图示如下，箭头方向为数据移动的方向，冒号前的数字表示操作的次序： +--------------------+ 空闲块1 | 空闲块2 | +-------------------+..+ | v-------------v-----+..+ |p_size|s=32|*fd|*bk| | | |p_size|s=32|*fd|*bk| | +-----------------^-+..+ | +-------------------+..+ | |6:FD->bk=P | | v 2:FD=BK->fd | | | 1:BK=bin_at(A,IDX) +---+ | +---+ 5:BK->fd=P | v |FD | +--+ P +-------------+ +---+ +-+-+ +---+ |BK +---------------+ | ^ +-+-+ | | | 空闲块3 | | +-------------------+..+ | | |p_size|s=32|*fd|*bk| | | | +-------------^---^-+..+ | | 4:P->fd=FD | | 3:P->bk=BK | +------------------------------------+ +----------------------+ 插入操作后的图示如下，箭头方向为指针的指向： <--------------+ +--------------------+ 空闲块1 | | 空闲块2 | +-------------+-----+..+ | +-------------+-----+..+ |p_size|s=32|*fd|*bk| | | |p_size|s=32|*fd|*bk| | ^-----------------+-+..+ | ^-----------------+-+..+ | | | | | | | | | +----> | | | | | +----+---------------+ | | | +-----------------+ | | | | | 空闲块3 | | v-------------------+..+ | | |p_size|s=32|*fd|*bk| | | | +-------------+---+-+..+ | | | | | +------------------------------------+ +----------------------+ 可以看到空闲块3已经被成功地插入了链表。 如果用户进程的实现有问题，对一个已经释放掉的内存块再做一次free()，那么free()会调用frontlink()对一个刚刚已经插入Bin链表的空闲块3执行再一次的插入操作，插入操作的图示如下，箭头方向为数据移动的方向，冒号前的数字表示操作的次序： 空闲块1 空闲块2 +-------------------+..+ +-------------------+..+ |p_size|s=32|*fd|*bk| | |p_size|s=32|*fd|*bk| | +-----------------^-+..+ +-------------------+..+ | |6:FD->bk=P v 2:FD=BK->fd | +---+ | +---+ 5:BK->fd=P |FD | +--+ P +-----------+ +-+-+ +---+ | | ^ | | | 空闲块3 | | +-------------v-----+..+ | |p_size|s=32|*fd|*bk| | | +-------------^---^-+..+ | 4:P->fd=FD | | | +----------------------+-------------+ | 1:BK=bin_at(A,IDX) | | v | +---+ | |BK + | +-+-+ | | 3:P->bk=BK | +-----------------+ 虽然空闲块的fd字段被写入了两次，但其值应该是后一次操作BK->fd=P 。 执行第二次插入操作后的图示如下，箭头方向为指针的指向： <--------------+ +--------------------+ 空闲块1 | | 空闲块2 | +-------------+-----+..+ | +-------------+-----+..+ |p_size|s=32|*fd|*bk| | | |p_size|s=32|*fd|*bk| | +-----------------+-+..+ | +-----------------+-+..+ | | | | | +----> +----+---------------+ | | 空闲块3 v-------------------+..+ |p_size|s=32|*fd|*bk| | ^-------------+---+-+..+ | | | +-------------+ | | | +-----------------+ 这样，空闲块3的fd和bk指针都指向了自己，这种错误的情况导致的后果是，当此空闲块被再一次分配出去的时候，unlink宏试图把此块从Bin链表中摘除的操作会失败，因为fd和bk都指向的是块自身。由于此块已无法从链表中摘除，如果相应的Bin链表中只含有此空闲块时，那么无论此块实际是不是空闲的，当用户请求分配相应长度的内存块时，Malloc都会返回此块的地址。一旦内存块分配给了用户，fd、bk所在位置就成了用户数据区，用户数据的前8个字节就可以覆盖这两个指针，对攻击者来说这正是他们想要的。攻击者用特定的值覆盖这两个指针，然后再次调用malloc()请求分配相应长度的内存块，malloc()就会调用unlink宏试图摘除Bin链表中的此单元时重写攻击者指定的任意地址的内存。 几个月前的CVS 1.11.4及以下版本软件就存在一个典型的double-free漏洞，以下是对其的简单分析： 问题存在于server.c文件中的dirswitch()函数中，此函数用于处理转换目录的请求，它会接收客户端提交的目录名并为之在堆里分配一个缓冲区，在使用完以后会通过free()调用将其释放掉。由程序流程上设计失误，通过向服务器发送一定序列的非法目录访问请求会导致程序多次释放同一个存放目录名的缓冲区，利用这个问题就可能在服务器上执行任意指令。相关的存在漏洞的代码如下： ---------------------------------------------------------------------------------------- static char *dir_name; dirswitch (dir, repos) char *dir; char *repos; { int status; FILE *f; size_t dir_len; server_write_entries (); if (error_pending()) return; /* Check for bad directory name. FIXME: could/should unify these checks with server_pathname_check except they need to report errors differently. */ if (isabsolute (dir)) { if (alloc_pending (80 + strlen (dir))) sprintf (pending_error_text, "E absolute pathname `%s' illegal for server", dir); return; } if (pathname_levels (dir) > max_dotdot_limit) { if (alloc_pending (80 + strlen (dir))) sprintf (pending_error_text, "E protocol error: `%s' has too many ..", dir); return; } if (dir_name != NULL) /* 这个dir_name是一个静态的指针，指向堆里 free (dir_name); 分配的存放客户端提交的目录名相关的字串 ，如果是第一次处理提交的目录，此指针为 空，如果指针不为空，指向的内存块存放的 是上一次操作的目录名。此内存块先被释放 掉，在接下来的代码中会分配新内存块存放 客户端提交的目录名。但如果下面的代码中 并没有分配新内存块并把指针赋给dir_name （由于接下来的一个检测目录名合法性的判 断，这种情况完全可能出现的），在下次目 录操作执行到这时，dir_name指向的内存块 会再次被释放。 */ dir_len = strlen (dir); /* Check for a trailing '/'. This is not ISDIRSEP because \ in the protocol is an ordinary character, not a directory separator (of course, it is perhaps unwise to use it in directory names, but that is another issue). */ if (dir_len > 0 && dir[dir_len - 1] == '/') /* 判断客户端提交的目录名是否最后一个 字符是'/' ，如果是则报错直接返回了 ，需要注意的是这时上面的dir_name指 向的内存块已经被释放了，而dir_name 本身的值没变。 */ { if (alloc_pending (80 + dir_len)) sprintf (pending_error_text, "E protocol error: invalid directory syntax in %s", dir); return; } /* 下面的这行代码是使用malloc()调用（xmalloc只是malloc的一个wrapper）分 配一个新的用于存放目录相关字串的缓冲区，并把指针赋给dir_name，如果客 户端提交的目录名没有通过上面的合法性检查，则代码在上面就已经返回，执 行不到这儿，也就是说dir_name指向的还是已经被前面的free()调用释放掉的 内存。 */ dir_name = xmalloc (strlen (server_temp_dir) + dir_len + 40); if (dir_name == NULL) { pending_error = ENOMEM; return; } strcpy (dir_name, server_temp_dir); strcat (dir_name, "/"); strcat (dir_name, dir); ... ---------------------------------------------------------------------------------------- 通过对上面代码的分析，可以知道客户端只要提交最后个字符为'/'的目录名，会使dir_name指向的内存块被释放后程序无法分配新的内存块并把指针赋给dir_name，dir_name还是保存着指向已经被释放的内存块的指针，在下一次进行目录操作时，dir_name指向的已经释放的内存会再次被释放，这样就导致了典型的double-free的问题，攻击者可能利用这个漏洞重写一个任意地址的4字节内存，如果用一个shellcode的地址重写一个函数的指针，就可以执行攻击者指定的任意指令。Igor Dobrovitski 提供了cvs_sploit.c测试程序，有兴趣的可以分析他实现的具体攻击方法。 相关链接与资料： http://www.nsfocus.net/index.php?act=magazine&do=view&mid=847 http://www.phrack.org/show.php?p=57&a=8 http://www.phrack.org/show.php?p=57&a=9 http://lists.netsys.com/pipermail/full-disclosure/2003-January/003606.html http://archives.neohapsis.com/archives/bugtraq/2003-02/0001.html