基于加权多随机决策树的入侵检测模型

1、基于加权多随机决策树的入侵检测模型         这篇基于加权多随机决策树的入侵检测模型的关键词是决策树,入侵检测,分辨矩阵,随机决策树,                    摘要：缓冲区溢出攻击对计算机和网络安全构成极大威胁。从缓冲区溢出攻击原理和shellcode实现方式出发，提出针对shellcode的溢出攻

2、击防御技术。描述shellcode获取控制权前后，从代码特点、跳转方式及shellcode恶意功能实现过程等方面入手，检测并阻止shellcode以对抗溢出攻击的几种技术。最后对这些技术的优缺点进行比较分析，指出其中较为优秀的方法，并就更全面提高系统安全性提出了一些建议。        关键词：        缓冲区溢出攻击;缓冲区溢出攻击防御;shellcode;Hook API    

3、0;   0引言        缓冲区溢出攻击是一种非常普遍而又危害极大的攻击，溢出发生后，导致任意代码执行，对系统安全构成极大威胁。远程攻击者能利用这种攻击获取系统控制权，窃取秘密信息或以该机器为跳板攻击其他主机。因此防御溢出攻击对保证系统乃至整个网络的安全尤为重要。        缓冲区溢出攻击防御技术也是计算机和网络安全界研究的重要内容。根据溢出及攻击的原理和特点，相应出现了多种防护技术。俄勒冈科学理

4、工研究生学院计算机科学与工程系的Crispin Cowan等人在他们的文章中介绍并分析了编写正确的代码、不可执行缓冲区、数组边界检查和程序指针完整性检查等几种防御方法，研究了对这几种方法进行组合以更有效对抗缓冲区溢出攻击1。iDefense的Peter Silberman和Richard Johnson详细介绍了运行于Linux和Windows平台下的几种缓冲区溢出防御工具包括StackGuard、ProPolice、StackShield、StackDefender、OverflowGuard等，从可能的攻击模式出发，对这些工具的效果和性能进行了比较，并指出可能绕过这些防御的方法2。可以看出

5、，现有的方法和工具都有各自的针对性和优缺点，从不同程度增加了攻击成功的难度。值得注意的是攻击者仍能想出各种方法绕过这些防护措施。防止缓冲区溢出攻击的最好方法就是从代码入手，防止溢出发生。然而就目前形势看，完全消除缓冲区溢出在近期内是不可能的，因此在溢出既已发生的情况下，采取有效措施对抗攻击仍然非常必要。本文将从shellcode角度出发，根据其代码表现形式、跳转方式及功能实现过程的特点，分析获取控制权前后两个阶段检测预防shellcode以对抗溢出攻击的方法。        1攻击原理和shellcode 

6、;       研究针对shellcode的防御技术，必须先了解缓冲区溢出攻击原理和shellcode的实现。        1.1缓冲区溢出攻击原理        缓冲区是内存中用于存放数据的区域，当程序向缓冲区填充的数据长度超过缓冲区本身容量时，就会发生溢出。若溢出的数据覆盖了相邻缓冲区中存放的函数调用返回地址、函数指针等数据，就会导致程序运行流程改变，可能使恶意

7、代码得以执行。        程序后        程序调用strcpy函数向只有6字节的缓冲区buf填入16字节的数据，导致溢出，覆盖了上一个ebp和返回地址ret等数据，函数返回时程序的运行流程被改变。攻击者利用缓冲区溢出实施攻击主要过程如图2。        1.2攻击代码shellcode表现形式及功能实现   

8、0;    shellcode是具有特定功能的指令集，攻击者将shellcode注入被攻击程序通过它来实现恶意功能。shellcode通常直接操作寄存器、调用API函数，因此必须是形如“x90x90xebx16”的16进制机器码。        早期shellcode通常只获取远程shell或绑定端口，实现起来相对简单。在变形shellcode出现之前，shellcode通常包含两部分：NOPs(空指令)指令段和真正的功能段。加入NOP是为了使攻击者不用精确计算溢出点，增加攻

9、击成功率。        图片        图3简单shellcode        为躲避检测，变形shellcode使用其他无效指令如inc eax，dec eax来代替NOP字段。并对 shellcode的功能部分进行加密，运行时再由解密引擎解密。变形shellcode形如图4。      

10、  S为训练数据集;        F=F1,F2,FK为数据集的属性集合        N为要创建的随机决策树的数量;        R=r1,r2,rK为上一小节中得出的属性权值的集合，其中ri为属性Fi的权值;        K为每个决策树包含的属性数量

11、。        输出： 经过训练的N棵随机决策树T1,T2,TN和每棵树的权值wi        在F中随机选择K个属性,并按Di中值的多少对所选属性进行递增排序得到属性集        以fi1为根节点建立一棵空决策树，树的第j层对应的分裂属性为fij;        设ny

12、为节点中保存经过该节点且属于第y类的训练数据的数量;        从根节点出发搜寻该条测试数据所对应的叶子节点,ny ny+1;        程序后        以下算法为分类算法：        算法2      

13、;  程序前        classify(T1,T2,TN,x)        输入：        N棵经过训练的决策树;        x为一条待分类的数据。        

14、;输出：x属于各类的概率Py        begin        对于每一棵随机决策树Ti,Pi(y|x)表示当前测试数据x属于类y的概率，wi表示该决策树的权值。ny是x所到达Ti的叶子节点中所保存的统计数;        对于所有的分类计算Py，就是该测试数据属于各类的概率;      &#

15、160; 程序后        2加权多随机决策树在入侵检测中的应用        从上一节的算法中我们可以看出加权多随机决策树有以下优点：        1) 建树和训练用时少。传统的决策树构造方法(如：ID3，C4.5)在训练时为了选择下一节点需要计算属性信息熵，所以要对数据集进行多次扫描。而多随机决策树算法只需要对数据集进行一次扫描就可完成训

16、练，用时比传统决策树要少很多。        2) 占用内存空间少。我们对比一下未经剪枝的随机决策树和ID3决策树的空间使用情况。考虑最一般的情况，假设全部属性数为K，每个属性有d个取值。我们为每棵随机决策树选取K=K2个属性，共建立N棵树，则总节点数为n=N×K-1i=0di。而相应的id3树的总节点数为m=K-1i=0di。可以看出，随着K的增加，m与n的差值是以指数增加的。并且因为随机决策树的各节点只保存落入该节点的数据的数量，所以训练数据的多少对树节点的大小没有影响。  

17、60;     3) 因为最后的判断需要综合所有树的分类结果，某一棵树的错误判断对整体的结果不产生决定性的影响。并且，因为引入了属性权值的概念保证了重要属性对分类的贡献。        4) 结果是概率的形式给出的。        5) 可以将不同的树分置于不同的主机之上进行并行分类，然后将结果汇总，则总的分类时间大大减少。     &#

18、160;  6) 用WRDT算法生成的决策树具备增量学习的特性，当有新的数据要对树进行训练时不需要对已生成好树的结构进行改变，也就是说新的训练可以在以前的训练基础上进行。        入侵检测中庞大的数据量和复杂的数据形式是很多数据挖掘算法不能有效应用于入侵检测的原因之一。而通过分析以上特性，我们发现第(1)、(2)条特性保证随机决策树能够处理大量的复杂数据，弥补了传统决策树很难处理大规模数据的不足。第(3)条特性保证了采用加权多随机决策树算法构建的入侵检测系统的稳定性。基于多agent的入侵

19、检测系统是目前入侵检测系统结构的一个发展方向，而应用第(4)、(5)条特性我们可以建立起一个基于多随机决策树的多agent入侵检测系统。其中每个agent包含一棵随机决策树，且每一个agent只处理一棵随机决策树的分类，能快速的判断入侵。各随机决策树的分析结果是以概率的形式给出的，保证了整个系统进行全局分类的灵活性。        3基于加权多随机决策树的入侵检测系统构架        3.1系统中各部件说明  &#

20、160;     数据采集agent负责从系统中采集相关信息(包括主机和网络的信息)并将其送至相应的入侵检测agent。        每一个入侵检测agent封装一棵随机决策树(由算法1生成)负责对相应ICA所采集的数据的信息进行分析以发现是否有入侵发生。多个负责相同任务的IDA被分为同一组，每一组IDA将其检测结果(被检测事件是某类入侵的概率)发送给组内的分析agent进行分析。多个IDA可以驻于同一主机中。    

21、60;   组内的SA对同组IDA的检测结果进行分析(运行算法2)，位于组上层SA对组内分析agent的上传结果进行进一步分析以从更高的层次对系统的安全状况进行监视。多个SA可以驻于同一主机中。        注册agent保存系统中每个agent所需的资源及所能提供的资源。        3.2系统检测过程        初始

22、化时，系统中的所有agent将其本身的信息(包括：该agent的名称、所需的数据、能够提供的数据、agent的功能及检测算法等)上传给注册agent，当一个入侵检测agent需要某些数据时它就向注册agent查询哪些agent有所需的数据，然后直接与这些agent通讯。这样整个系统的资源得到了共享，并且注册agent只传送注册信息(当检测agent得到信息后就不再与注册agent通信)，不会造成注册agent的网络负担过于沉重的问题。        每个ICA将其收集的系统信息上传给相应的入侵检测agent来进行分

23、析，多个执行相同任务的IDA被分为一组，同组中IDA运行的随机决策树由算法1生成，每个组拥有一个SA来收集并分析(采用算法2)同组中IDA 的检测结果，并将其分析结果上传给上层SA。上层SA对其下所有分析agent上传的结果进行进一步的分析以获取更大范围网络的安全情况。当系统发现入侵时采用相应的响应策略。        4试验结果        4.1试验数据      

24、60; 本文的数据采用1998DARPA 入侵检测评估数据。该数据集是由美国DARPAITO 和空军研究实验室资助, 由MIT 林肯实验室负责创建的, 也是世界上第一个用于入侵检测研究的标准数据集()。数据集共提供了7周的训练数据和5周的测试数据。训练数据包括大约5百万条连接记录, 测试数据包括大约3百万条连接记录。共包括四大类入侵：Probe、DoS、R2L和U2R，为了避免偶然性共进行12次分类测试， 每次试验从1998DARPA 入侵检测评估数据的训练数据集中随机抽取200000条记录进行训练，并且随机从测试数据集中抽取50000条记录进

25、行测试。        4.2试验结果        由于本试验的目的在于测试WRDT算法的分类正确率及并行分类的效率，试验只构建了图1中的一个组，并且在SA中未使用其他数据挖掘算法。本文使用7台Pentium台式机(CPU Intel 赛扬 2.4GHz, 内存 DDR256MB,操作系统 Windows XP)构建图1中的网络结构这篇基于加权多随机决策树的入侵检测模型的关键词是决策树,入侵检测,分辨矩阵,随机决策树, &#

26、160;          ，其中5台用于驻留IDA，一台用于SA，一台注册服务器。采用随机抽取的50000条测试数据作为模拟网络输入。试验每次建立10棵加权随机决策树，每棵决策树对应一个IDA。试验的软件环境采用Java 2实现，编程环境为Eclipse。        KDDCUP99所提供的试验数据是对1998DARPA 入侵检测评估数据进行预处理后给出的。所以分类正确率的对比试验采用KDDCUP99的获胜算法。其结果如表1所