• Home
  • About
    • tearorca photo

      tearorca

      Wishful thinking have to be willing to bet on clothing!

    • Learn More
    • Google+
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

《0day 安全》Windows堆的结构

20 Mar 2019

Reading time ~1 minute

  • 堆表介绍:
    • 空闲双向链表Freelist(空表)
    • 快速单向链表Lookaside(快表)
  • 堆的操作
    • 堆块分配
      • 快表分配:
      • 普通空表:
      • 零号空表分配:
      • “找零钱”现象:
    • 堆块释放
    • 堆块合并
    • 分配和释放算法图
    • 注意点
  • 实验
  • 参考链接

堆表介绍:

空闲双向链表Freelist(空表)

空闲堆块的块首中包含一对重要的指针,这对指针用于将空闲堆块组织成双向链表。按照堆块大小的不同,空表总共被分为128条。

堆区一开始的堆表区中有一个128项的指针数组,被称作空表索引。该数组的每一项包括两个指针,用于标识一条空表。

除了空表索引的第一项外,其余空表的大小为:

空闲堆块的大小=索引项(ID)*8(字节)

空表索引的第一项所标识的空表相对比较特殊。这条双向链表链入了所有大于等于1024字节的堆块(小于512KB).这些堆块按照各自的大小在零号空表中升序地依次排列下去。

快速单向链表Lookaside(快表)

快表不会发生堆块合并(其中的空闲块块首被设置为占用态,用来防止堆块合并)

快表也有128条,结构和空表类似,只是其中的堆块按照单链表组织。每个快表最多只有4个结点。

堆的操作

堆块分配

快表分配:

寻找大小匹配的空闲堆块、将其状态修改为占用态、把它从堆表中“卸下”、最后返回一个指向堆块块身的指针给程序用。

普通空表:

首先寻找最优的空闲块分配,若失败,则寻找次优的空闲块分配,即最小的能满足的。

零号空表分配:

按照大小升序链着大小不同的空闲块,从free[0]反向查找最后一块(即表中最大块),如果能满足要求,再正向搜索最小能满足要求的空闲堆块进行分配。

“找零钱”现象:

当空表中无法找到“最优”堆块时,一个稍大些的块会被用于分配。这种次优分配发生时,会先从大块中按请求的大小精确地“割”出一块进行分配。然后给剩下的部分重新标注块首,链入空表。

堆块释放

所有的释放块都链入堆表的末尾,分配的时候也先从堆表末尾拿。

堆块合并

当堆管理系统发现两个空闲堆块彼此相邻的时候,就会进行堆块合并。

分配和释放算法图

注意点

1.  快表中的空闲块被设置为占用态,故不会发生堆块合并操作。

2.  快表只有精确匹配时才会分配,不存在“搜索次优解”和“找零钱”现象。

3.  快表是单链表,操作比双链表简单,插入删除都很少用很多命令。

4.  快表很快,故再分配和释放时总是优先使用快表,失败时才用空表。

5.  快表只有4项,很容易被填满,因此空表也是被频繁使用的。

实验

代码:

 #include <stdio.h>
 #include <windows.h>
 void main()
 {
	 HLOCAL h1;
	 HANDLE hp;
	 hp = HeapCreate(0,0x1000,0x10000);
	 __asm int 3
	 h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,16);
 }

直接运行出错后选择取消进入od调试,现在的eax就是前面HeapCreate的返回地址,也就是创建堆的起始地址。 从3A0000开始包含的信息依次是段表索引,虚表索引,空表使用标识和空表索引区 跟进

参考链接

具体的实践:http://oldblog.giantbranch.cn/?p=437



Share Tweet +1