基于随机算法的堆溢出防范策略
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于随机算法的堆溢出防范策略范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要:缓冲区溢出攻击是一种攻击计算机系统的手段,本文针对缓冲区溢出的堆溢出问题进行了探究。简述了当前堆溢出的原理和防范方法,阐述堆的数据结构和堆溢出的攻击原理。通过堆块的分配策略,以及堆块本身的特点,提出一种随机分配堆块的方法。
关键词:缓冲区溢出;堆溢出;随机分配
中图分类号:TP393.08 文献标识码:A 文章编号:1007-9599 (2012) 13-0000-02
一、堆溢出的攻击原理和防范
(一)堆的溢出攻击原理[1]
堆是在存储器中开辟的一段区域,这段区域经常被应用程序利用,而且在程序运行的时候被动态分配。堆的溢出是指在堆中缓冲区写数据时,数据超出了该缓冲区所能容纳的空间。这时,临近区域的内容被超出的部分覆盖,超出的部分被破坏者利用,改写了一些危险的代码。最后,这些危险代码改写了目标程序。
堆的溢出利用,有两种情况:第一种情况是Matt Conover等提出的堆利用方法,这种利用方法是通过溢出堆覆盖了相邻堆块数据、堆管理数据或指针值;第二种是利用堆结构本身的特点。第一种方法是被利用的比较多的方法,我们这里主要关注第一种堆溢出利用方法。
第一种方法的实现原理如图1所示,在堆管理数据的两侧分别动态分配了内存块M和N,当向内存块M中输入数据时,如果超过了M的边界,堆管理数据的内容就会被覆盖掉,导致溢出的产生。如果超过了堆管理数据的边界,就会将内存块N覆盖掉。攻击者可以通过溢出直接改写敏感数据如函数指针等内容。
上面程序展示了简单的堆溢出漏洞,也简单揭示了堆分配的策略。程序执行前后内存中的模拟图如图2所示。
在Linux系统中,该程序的编译执行有如下结果:
从上述的编译结果得出,output中的数据已经被覆盖。如果大于003D2480地址空间中含有函数指针,则可以通过给该函数输入足够长的字符串来覆盖该函数地址,从而改变程序的执行流程。
(二)堆溢出的攻击防范
堆溢出攻击的防范现阶段可分为两种:编译时的静态分析和运行时的动态防范。
1.静态分析
从本质上讲,缓冲区溢出是由编程语言自身的缺陷引起的,对程序代码进行分析检查的方法称为静态分析。常见的方法就是将C语言中不安全函数进行替换,例如:将strcpy等函数替换为strncpy等函数。除此之外,通过实现类似于编译器前端的工作,使用语法分析的方法,发现程序的缺陷或错误,这是帮助程序员在编译阶段中完成的,如PCLint等。但到目前为止,静态分析工具还处于研究的阶段,功能不完善,不能发现系统中的所有漏洞,并不可避免地存在大量的误报。
2.动态防范
动态防范主要是采用增强系统内核和监视堆栈等方法。增强系统内核是从环境角度来预防缓冲区溢出。一般情况下,恶意代码会存放在堆或栈上,可以通过禁止执行堆或栈上的代码来提高系统的安全性。比如在linux系统内核上的Pax补丁。但该方法的缺点也是很明显的:由于系统的某些正常代码程序只能放在栈中的,比如linux通过向进程栈填写代码然后引发终端来执行栈中的代码以便实现向进程发送信号。这种使堆栈不可执行的方法具有一定的局限性。监视堆栈的方法是编译器的一个补丁,通常是在堆栈中加一个标记。比如随机放一个“canary”字,在函数返回之前检查“canary”的完整性。
内存管理系统是先分配一大块内存,保留这块内存起始部分用于放置管理数据,后面部分作为空闲块分配给用户使用。在管理数据中有一个空闲链表表头数组,数组中每一项元素都是一个双向链表的表头。该双向链表由若干特定大小的空闲块构成,空闲块大小随数组索引递增。此外管理数据中还维护一个大空闲块链表的表头,超过一定大小的空闲块均存放在这个链表中。
在LINUX系统中,每个堆实质上是由用户数据区和管理结构区两部分组成。用户数据区存储用户的数据,管理区存放堆的信息,这些信息包括堆是否空闲、堆的大小以及双向链表指针等,图3是已分配好的堆内存映像。
MALLOC()函数在内部使用的是CHUNK指针,但给用户返回的是CHUNK+8也就是MEM指针,而指向下一个的是NEXTCHUNK指针。当使用者提出申请时,系统其实掩盖了一个内在的结构,具体说就是,例如,用户需要LONG字节长度的存储单元,但得到的最少是LONG+8字节长度的,最终用户能使用到的就是LONG字节。
以上是对已使用的堆来说的,对于没有被使用的堆来说,它的信息是存储在一个双向循环链表中,图4是它在存储单元中的分布情况。
三、随机数的产生方法
(一)随机数的应用[3]
很明显,要做到随机分配一段内存空间,需要使用随机数。目前应用的随机数通常都是通过某些数学公式计算而产生的伪随机数,即伪随机数发生器产生的,它是由一个初始状态(称为“种子”)开始,通过一个确定的算法来生成随机数。一旦给定算法和种子值,输出序列就是确定的了,有一定的周期性,有规律性和重复性。但是,只要伪随机数能够通过随机数的一系列的统计检验,我们就可以把它当作真随机数而放心地使用,这样我们就可以很经济地,重复地产生出随机数。对物理问题的计算机模拟所需要的伪随机数应当满足如下的标准:
理论上,要求伪随机数产生器具备以下特征:统计分布特性是良好的,伪随机数产生是高效率的、并且循环周期长,产生的程序可移植性好和可以重复产生的伪随机数。常用的随机数产生算法有:冯·诺依曼平方取中法,线性同余法等[4]。
(二)冯·诺依曼平方取中法
伪随机数产生器产生的实际上是伪随机数序列最基本的产生器是均匀分布的伪随机数产生器。
最早的伪随机数产生器可能是冯·诺依曼平方取中法:该方法首先给出一个2r位的数,取它的中间的r位数码作为第一个伪随机数;然后将第一个伪随机数平方构成一个新的2r位数,再取中间的r位数作为第二个伪随机数…。如此循环便得到一个伪随机数序列。类似上述方法,利用十进制公式表示2r位数的递推公式[5]。
这样得到的 伪随机数序列是分布在[0,1]上的。相应的二进制递推公式为
这种方法由于产生的数列具有周期性,现在已经不常用了。
四、结束语
本文提出的随机算法在分配存储单元时不会退化为确定性算法,也不会造成太多额外的空间开销。随机化比较彻底,是堆溢出防范的一个思路。本文只是阐述了堆分配时的算法,对于堆溢出的防范有一定的帮助,但没有栈溢出的防范,同时随机算法也在一定程度上增加了系统管理的开销,并有可能产生更多的碎片,进一步的完善工作有待于进一步的研究。
参考文献:
[1]赵奇永.基于可执行代码的缓冲区溢出检测[D].上海交通大学,2008
[2]彭锋.一种基于随机匹配算法的堆溢出防范策略[J].计算机应用,2006
[3]龚红.真随机数发生器设计[D].微电子学与固体电子学,2007,4
[4]郑胜.基于贝努利大数定律的数据分布算法[J].计算机工程,2009
[5]肖利群.蒙特卡罗方法在总和生育率计算中的应用[D].厦门大学,2008