学习记录发布 ing 。。。

  堆的简单介绍就懒得说了，搜下就知道。

堆的工作原理

Windows 堆历史

  （1） Windows 2000～Windows XP SP1：堆管理系统只考虑了完成分配任务和性能因素，丝毫没有考虑安全因素，可以比较容易发被攻击者利用。
  （2） Windows XP 2～Windows 2003：加入了安全因素，比如修改了块首的格式并加入安全 cookie，双向链表结点在删除时会做指针验证等。这些安全防护措施使堆溢出攻击变得非常困难，但利用一些高级的攻击技术在一定情况下还是有可能利用成功。
  （3） Windows Vista～Windows 7：不论在堆分配效率上还是安全与稳定性上，都是堆管理算法的一个里程碑。
  （4） 后面的书里没有，以后研究的时候收集整理

堆和栈区别

堆内存栈内存
典型用例动态增长的链表等数据结构函数局部数组
申请方式需要用函数申请，通过返回的指针使用。如 p=malloc(8)；在程序中直接声明即可，如 char buffer[8]；
释放方式需要把指针传给专用的释放函数，如 free函数返回时，由系统自动回收
管理方式需要程序员处理申请与释放申请后直接使用，申请与释放由系统自动完成，最后达到栈区平衡
所处位置变化范围很大 0x0012XXXX
增长方向由内存低址向高址排列（不考虑碎片等情况）由内存高址向低址增加

堆的数据结构和管理策略

  响应程序的内存使用申请：在“杂乱”的堆区中“辨别”出哪些内存是正在被使用的，哪些内存是空闲的，并最终“寻找”到一片“恰当”的空闲内存区域，以指针形式返回给程序。

  1、“杂乱”是指堆区经过反复的申请、释放操作之后，原本大片连续的空闲内存区可能呈现出大小不等且空闲块、占用块相间隔的凌乱状态。
  2、“辨别”是指堆管理程序必须能够正确地识别哪些内存区域是正在被程序使用的占用块，哪些区域是可以返回给当前请求的空闲块。
  3、“恰当”是指堆管理程序必须能够比较“经济”地分配空闲内存块。如果用户申请使用 8 个字节，而返回给用户一片 512 字节的连续内存区域并将其标记成占用状态，这将造成大量的内存浪费，以致出现明明有内存却无法满足申请请求的情况。

  堆块 ： 出于性能的考虑，堆区的内存按不同大小组织成块，以堆块为单位进行标识，而不是传统的按字节标识。一个堆块包括两个部分： 块首 和 块身 。块首是一个堆块头部的几个字节，用来标识这个堆块自身的信息，例如，本块的大小、本块空闲还是占用等信息；块身是紧跟在块首后面的部分，也是最终分配给用户使用的数据区。

  堆表 ： 堆表一般位于堆区的起始位置，用于索引堆区中所有堆块的重要信息，包括堆块的位置、堆块的大小、空闲还是占用等。

堆的内存组织
堆的内存组织

  Windows 中， 占用态的堆块被使用它的程序索引 ，而堆表只索引所有空闲态的堆块。其中，最重要的堆表有两种： 空闲双向链表 Freelist 和 快速单向链表 Lookaside 。

  1、 空表
   空闲堆块的块首中包含一对重要的指针，这对指针用于将空闲堆块组织成 双向链表 。按照堆块的大小不同，空表总共被 分为 128 条 。堆区一开始的堆表区中有一个 128 项的指针数组 ，被称做 空表索引（Freelist array） 。该数组的每一项包括两个指针，用于标识一条空表。

空闲双链表
空闲双链表

空闲堆块的大小＝索引项（ID） ×8（字节）

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

  2、快表
   快表是 Windows 用来加速堆块分配而采用的一种堆表。这里之所以把它叫做“快表”是因为这类 单向链表 中从来不会发生堆块合并（其中的空闲块块首被设置为占用态，用来防止堆块合并）。
   快表也有 128 条，组织结构与空表类似，只是其中的堆块按照单链表组织。 快表总是被初始化为空，而且每条快表 最多只有 4 个结点 ， 故很快就会被填满。

快表
快表

  堆中的操作可以分为 堆块分配 、 堆块释放 和 堆块合并（Coalesce） 三种。其中，“分配”和“释放”是在程序提交申请和执行的，而堆块合并则是由堆管理系统自动完成的。
  这里没有讨论堆缓存（heap cache）、低碎片堆（LFH）和虚分配。

  1、堆块分配
   （1） 快表分配
   从快表中分配堆块比较简单，包括寻找到大小匹配的空闲堆块、将其状态修改为占用态、把它从堆表中“卸下”、最后返回一个指向堆块块身的指针给程序使用。

   （2） 普通空表分配
   普通空表分配时首先寻找最优的空闲块分配，若失败，则寻找次优的空闲块分配，即最小的能够满足要求的空闲块。

   （3） 零号空表（free[0]）分配。
   零号空表中按照大小升序链着大小不同的空闲块，故在分配时先从 free[0] 反向查找 最后一个块（即表中最大块），看能否满足要求，如果能满足要求，再正向搜索最小能够满足要求的空闲堆块进行分配

   堆块分配中的 “找零钱”现象 ：当空表中无法找到匹配的“最优”堆块时，一个稍大些的块会被用于分配。这种次优分配发生时，会 先从大块中按请求的大小精确地“割”出一块进行分配，然后给剩下的部分重新标注块首，链入空表 。 由于快表只有在精确匹配时才会分配，故不存在“找钱”现象。

  2、堆块释放
   释放堆块的操作包括 将堆块状态改为空闲，链入相应的堆表 。 所有的释放块都链入堆表的末尾，分配的时候也先从堆表末尾拿。

  3、堆块合并
   当堆管理系统发现两个空闲堆块 彼此相邻的时候，就会进行堆块合并 操作。堆块合并包括将两个块从空闲链表中“卸下”、合并堆块、调整合并后大块的块首信息（如大小等）、将新块重新链入空闲链表。

堆块合并图
堆块合并图

   堆区还有一种操作叫做 内存紧缩（ shrink the compact） ，由 RtlCompactHeap 执行，这个操作的效果与磁盘碎片整理差不多

  内存块大小分类：
   小块： SIZE < 1KB
   大块： 1KB ≤ SIZE < 512KB
   巨块： SIZE ≥ 512KB
  分配和释放算法

分 配释 放
小块首先进行快表分配；
若快表分配失败，进行普通空表分配；
若普通空表分配失败，使用堆缓存（heap cache）分配；
若堆缓存分配失败，尝试零号空表分配（freelist[0]）
若零号空表分配失败，进行内存紧缩后再尝试分配；
若仍无法分配，返回 NULL		优先链入快表（只能链入 4 个空闲块）；
如果快表满，则将其链入相应的空表
大块首先使用堆缓存进行分配；
若堆缓存分配失败，使用 free[0]中的大块进行分配		优先将其放入堆缓存
若堆缓存满，将链入 freelists[0]
巨块一般说来，巨块申请非常罕见，要用到虚分配方法（实际上并不是从堆区分配的）。
这种类型的堆块在堆溢出利用中几乎不会遇到，本书中讨论暂不涉及这种情形		直接释放，没有堆表操作

  要点：
   （1）快表中的空闲块被设置为占用态，故不会发生堆块合并操作。
   （2）快表只有精确匹配时才会分配，不存在“搜索次优解”和“找零钱”现象。
   （3）快表是单链表，操作比双链表简单，插入删除都少用很多指令。
   （4）综上所述，快表很“快”，故在分配和释放时总是优先使用快表，失败时才用空表。
   （5）快表只有 4 项，很容易被填满，因此空表也是被频繁使用的。

堆的具体操作

堆分配函数之间的调用关系

  所有的堆分配函数最终都将使用位于 ntdll.dll 中的 RtlAllocateHeap() 函数进行分配，这个函数也是在用户态能够看到的最底层的堆分配函数。

Windows 堆分配 API 的调用关系
Windows 堆分配 API 的调用关系

堆的调试方式

// 测试代码
#include <windows.h>
main()
{
    HLOCAL h1,h2,h3,h4,h5,h6;
    HANDLE hp;
    hp = HeapCreate(0,0x1000,0x10000);
    __asm int 3
    h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,3);
    h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,5);
    h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,6);
    h4 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
    h5 = HeapAlloc(hp,HEAP_ZERO_MEMORY,19);
    h6 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);
    //free block and prevent coaleses
    HeapFree(hp,0,h1); //free to freelist[2]
    HeapFree(hp,0,h3); //free to freelist[2]
    HeapFree(hp,0,h5); //free to freelist[4]
    HeapFree(hp,0,h4); //coalese h3,h4,h5,link the large block to
    //freelist[8]
return 0;
}

  调试堆与调试栈不同， 不能直接用调试器 Ollydbg、 Windbg 来加载程序 ，否则堆管理函数会检测到当前进程处于调试状态，而使用调试态堆管理策略。

  调试态堆管理策略和常态堆管理策略差异集中体现在：
   1、调试堆不使用快表，只用空表分配。
   2、所有堆块都被加上了多余的 16 字节尾部用来防止溢出（防止程序溢出而不是堆溢出攻击），这包括 8 个字节的 0xAB 和 8 个字节的 0x00。
   3、块首的标志位不同。

  在程序运行后【附加】调试即可。

  所有的堆块分配函数都需要指明堆区的句柄，然后在堆区内进行堆表修改等操作 ，最后完成分配工作。
  malloc 虽然在使用时不用程序员明确指出使用哪个堆区进行分配，但如果逆向了 malloc 的实现，您会发现该函数已经使用HeapCreate()函数为自己创建了堆区。
  通常情况下， 进程中会同时存在若干个堆区 。其中包括开始于 0x00130000 的大小为 0x4000 的进程堆，可以通过 GetProcessHeap() 函数获得这个堆的句柄并使用

识别堆表

堆块的分配

堆块的释放

堆块的合并

快表的使用

堆溢出利用 - DWORD SHOOT

链表“拆卸”中的问题

调试 “DWORD SHOOT”

堆溢出利用 - 代码植入

DWORD SHOOT 的利用方法

狙击 P.E.B 中 RtlEnterCritical-Section()的函数指针

堆溢出利用的注意事项