粗糙集属性约简在入侵检测系统中的应用＊

吴建源

(广东培正学院计算机科学与工程系,广东广州 510830)

粗糙集属性约简在入侵检测系统中的应用＊

吴建源

(广东培正学院计算机科学与工程系,广东广州 510830)

入侵检测系统 (I DS)是一种以攻为守的主动式防御措施,它针对网络内部攻击进行防御.为了实现对海量入侵检测数据的数据挖掘,首先可对入侵检测系统采集的海量数据进行抽样分析,然后使用粗糙集理论的属性约简方法对数据进行预处理,获得入侵检测数据的决策规则,并判断流经网络的数据包的安全性,最后编程以实现数据挖掘的自动化.

粗糙集;数据挖掘;属性约简;入侵检测

近年来,计算机和网络基础设施,特别是各种官方机构的网站,不断受到黑客的攻击,各种入侵事件层出不穷.一些传统的网络安全技术,如访问控制机制、加密、防火墙等已不能满足网络安全的要求,而逐渐成熟起来的入侵检测系统 (Intrusion Detection System,简称为 I DS)则为我们提供了又一重保障.数据挖掘在入侵检测中的应用,旨在对海量的安全审计数据进行智能化处理,试图从大量数据中提取人们感兴趣的数据信息,及与安全相关的系统特征属性,建立基于数据挖掘的入侵检测模型,包括数据源选择、数据预处理、算法选择、创建数据挖掘模型、挖掘结果分析处理及其可视化等[1,2].

由于入侵检测系统采集的数据量是巨大的,因此对采集的数据采用分等级多次抽样的方法获取信息系统表.粗糙集理论作为一种新的数据挖掘工具,在处理不确定性知识方面有着突出的优势.用粗集理论的属性约简方法对样本信息系统进行预处理,删除冗余的属性,从而得到入侵检测数据的决策规则,进而判断流经网络的数据包的安全与否.

1 理论知识

1.1 入侵检测系统

入侵检测是在 1980年由 James Anderson在为美国空军做的技术报告中首次提出来的[1].入侵检测,顾名思义,是对入侵的一种检测行为,它是通过从计算机网络或计算机系统中的若干关键点收集信息并对其进行分析,从中发现网络或系统中是否有违反安全策略的行为和遭到袭击的迹象.作为一种安全防护工具,I DS弥补了防火墙的很多不足,甚至在很多方面可以取而代之.相对于采用封锁、过滤等被动防御的防火墙而言,入侵检测系统能主动地发现网络中的非法入侵,并采取相应的措施,如记录、报警、阻断网络等,防止危害的扩大.

入侵检测实质是对基于主机或基于网络的计算机系统的运行状态进行监视,发现各种攻击企图、攻击行为或者攻击结果,以保证系统资源的机密性、完整性与可用性[3].从功能上,我们将入侵检测系统划分为四个基本部分:数据采集子系统、数据分析子系统、控制台子系统、数据库管理子系统(如图 1所示).

图1 入侵检测功能结构示意图

其中数据分析模块相当于 I DS的大脑,它必须具备高度的“智慧”和“判断能力”.所以,在设计此模块之前,我们需要对各种网络协议、系统漏洞、攻击手法、可疑行为等有一个很清晰、深入的研究,然后制订相应的安全规则库和安全策略,再分别建立滥用检测模型和异常检测模型,让机器模拟自己的分析过程,识别确知特征的攻击和异常行为,最后将分析结果形成报警消息,发送给控制管理中心.

1.2 粗糙集 (Rough Set)

Rough Sets理论是由波兰华沙理工大学 Pawlak于 1982年提出的一种数据分析理论,主要研究不完整、不确定知识和数据的表达、学习、归纳的方法[4].其主要思想是在保持分类能力不变的前提下,进行知识约简.目前,粗糙集理论已被成功地用于机器学习、决策分析、过程控制、模式识别和数据挖掘等领域,所以在使用决策树之前可先利用粗糙集方法对入侵检测数据进行属性约简.

下面简单介绍一下粗糙集理论中属性约简的思想[5,6,7].

设非空集U是我们感兴趣的对象组成的有限集合,称为论域.任意 X⊆U,称为 U中的一个概念或范畴.U上的一族划分称为关于 U的一个知识库,而集合上的划分与等价关系是相互对应的.

(1)决策信息系统:是一个有序四元组 S=(U,A,V,f),其中 U={x1,x2,…,xn}是论域,A=C∪D是属性集合,其中 C是条件属性集合,D是决策属性集合,是属性值的集合,Va是属性 a的值域,f:U×A→V是一个信息函数,对每一个 a∈A,x∈U,f(x,a)∈Va,即信息函数 f指定U中每一个对象 x的每个属性值.

信息系统的每个属性均决定一个等价关系,当然属性子集也决定一个等价关系,如 P⊆A,则由 P决定的等价关系的等价类的集合记为U/P={[x]P|x∈U}.

(2)上近似和下近似:在信息系统 S=(U,A,V,f)中,设 P⊆A,X⊆U,X关于 P的下近似 P_(X)={x|x∈U,[x]P⊆X},上近似 P-(X)={x|x∈U,[x]P∩X≠Φ},POSP(X)=P_(X)也称为 X的 P正域.

(3)属性约简

定义 1设 U为一个论域,P和 Q为定义在 U上的两个等价关系簇,称

POSP(Q)为 Q的 P正域.

定义 2设 S=(U,A,V,f)是一个信息系统,P,Q ⊆ A,r∈ P,如果

则称 r为 P中 Q不必要的;否则 r为 P中 Q必要的.不必要属性在信息系统中是多余的.若将它从系统中去掉,不会改变系统分类能力.

定义 3设 S=(U,A,V,f)是一个信息系统,P,Q⊆A,如果每个 r∈P都是 Q必要的,则称 P为Q独立的;否则,称 P为 Q依赖的.

对于相依赖的属性集合来说,其中必包含有多余的属性,可以对其约简.

定义 4设 S=(U,A,V,f)是一个信息系统,P,Q⊆A,P中所有Q必要的属性构成的集合称为P的 Q核,简称相对核,记为 coreQ(P).

定义 5设 S=(U,A,V,f)是一个信息系统,P,Q⊆A,K⊆P,如果满足:

POSK(Q)=POSP(Q),而且 K是 Q独立的,则称 K是 P的一个 Q约简,P的Q约简也称为相对约简.

相对约简一般不唯一,而且相对核是所有相对约简的交集.相对核的概念有两方面的意义:首先它可以作为所有约简的计算基础,因为核包含在所有的约简之中,并且计算可以直接进行;其次当知识化简时它是不能消去的知识特征的集合.

2 入侵检测数据挖掘模型

现在我们利用上述介绍的粗糙集理论以及决策树 I D3算法对入侵检测系统采集的检测数据进行归纳学习.

(1)入侵检测数据的采集:入侵检测数据采集模块是实现整个入侵检测系统高效工作的基石,为整个系统提供数据来源.因此,在设计整个入侵检测系统时,必须保证网络数据截获模块工作稳定可靠,为整个入侵检测模块稳定可靠地提供数据.现在比较流行的有两种方法,一种网络数据截获方法,是在 BPF(Berkeley Packet Fliter)模型的基础上,利用一些流行的函数库进行开发;另外一种是在W indows的驱动程序的基础上进行的开发.

在UN IX或Linux系统中,一般采用由美国洛伦兹伯克利国家实验室所编写的专用于数据包捕获功能的 API函数库 Libpcap来实现.Libpcap实质上是一个系统独立的 API函数接口,用于用户层次的数据截获工作,可在相关网站下载到.

具体地说,入侵检测数据的采集主要基于两大类:一种基于标志 (signature-based),另一种基于异常情况(anomaly-based)[3].对于基于标识的检测技术来说,首先要定义违背安全策略的事件的特征,如网络数据包的某些头信息,主要判别这类特征是否在所收集到的数据中出现,此方法非常类似杀毒软件.而基于异常的检测技术则是先定义一组系统“正常”情况的数值,如 CPU利用率、内存利用率、文件校验等 (这类数据可以人为定义,也可以通过观察系统、并用统计的办法得出),然后将系统运行时的数值与所定义的“正常”情况比较,得出是否有被攻击的迹象,这种检测方式的核心在于如何定义所谓的“正常”情况.

根据上述检测的方法,需要对诸如数据包头信息、CPU利用率等 10来个属性进行数据采集,得到如下面表 1的入侵数据信息系统,该信息系统模拟网络环境获得 9个星期的 TCP元数据,这些数据的基础是正常的网络数据,其余的为多种入侵数据.

(2)由于信息系统数据量非常大,为了便于学习,首先要进行抽样分析,可依次取 1/10000,1/5000,1/1000,1/100,1/10的数据量进行多次抽样,对每次的样本进行实验.

(3)对样本信息系统,采用下文介绍的粗糙集属性约简软件对它进行约简,获得该样本的分类决策规则.

(4)利用这些规则,判断出哪些是正常的网络数据包,哪些是恶意的入侵行为.

3 仿真实现

3.1 系统设计

基于粗糙集方法的入侵检测系统是一种基于数据挖掘的入侵检测系统.该系统主要由数据采集、数据挖掘、模式匹配和智能决策等 4个模块组成(如图 2所示).

数据采集模块从数据源,如系统日志、网络数据包等,获取原始数据,同时该模块还对原始数据进行一些必要的处理,如可能需要对数据投影,处理连续属性,对不完整的数据进行补充等.这部分为进一步的数据分析和约简作准备[8].

数据挖掘模块首先利用粗糙集理论中的属性约简算法对数据采集模块提交的数据进行预处理,去除冗余属性,再运用决策树 I D3算法对预处理得到的审计数据进行整理、归纳分析,找到可用于入侵检测的模式与知识,即生成安全规则,然后提交给模式匹配模块进行入侵分析,做出最终判断,最后由决策模块给出应对措施.

图2 基于粗集方法的入侵检测系统模块结构图

在数据挖掘模块中,可以选择基于可辨识矩阵的一般算法、基于可辨识矩阵的改进算法和启发式属性算法等三种不同的属性约简方法进行约简,以去除原始数据中的冗余属性,减少规则生成时的数据量,提高规则的简洁度.对于属性约简后的数据,运用决策树 I D3算法进行规则提取,得到相应的网络安全规则.规则显示程序负责为用户显示当前数据生成的安全规则.由于数据具有不确定和存在噪音等特点,可能存在相互冲突的规则,可能需要对规则进行检查以去除潜在的不一致性,因此程序还为用户提供对相关规则进行检查修改的功能.对规则集的一致性等检查完毕后,就可以把该规则集加入到相应的规则库 (知识库),作为对用户行为特征分析判定的依据.

3.2 软件实现

软件基于W indows2000 Professional操作系统,编程平台为MicrosoftVisual C++6.0,后台数据库采用SQL Server 2000.

3.2.1 数据库接口

W indows常见数据库接口有:ODBC(开放数据库互连 )、DAO(数据访问对象 )、OLE DB(对象链接嵌入数据库).

OLE DB属于底层的数据库编程接口,与传统的数据库接口相比,有更好的健壮性和灵活性,能够与非关系数据源进行通信,它作为数据库与应用程序的中间层,允许应用程序以相同接口访问不同类型的数据源.当客户程序对数据库进行操作时,只需要对 OLE接口发出指令,数据服务器从数据源取得所要查询的数据,以表格的形式提供给接口,再由客户程序将数据从接口取出并使用.在这些操作中,客户和服务器都不必知道对方的具体应用,而只需对接口进行操作,简化了程序设计,提高了对数据库的访问速度.

因此,本软件采用 OLE DB作为应用程序与数据库之间的接口.

3.2.2 功能简介

本软件主要用来处理信息系统和决策表,可以从不同的数据源中获取数据集合,并输入到后台SQL Server 2000数据库中,使之适用于本系统的操作.通过“测试连接”连接到所要处理的数据库,然后点“属性约简”进行启发式属性约简,再点“规则生成”进行归纳学习,从而获得决策表的规则,其界面如图 3所示.

图3 基于粗集和决策树的数据挖掘软件界面

4 结论

入侵检测系统作为一种积极主动的安全防护技术,提供了对内部攻击、外部攻击和误操作的实时保护,在网络系统受到危害之前响应和拦截入侵,为网络安全构建立体纵深、多层次的防御做出了贡献.基于粗糙集的数据挖掘方法应用于入侵检测中,能够提高入侵检测的有效性,并且对于海量的主机和网络审计数据来说,入侵检测的误报率随着数据量的增大而明显减小,因此相比其他数据挖掘方法来说,更具有客观性和实用性.

[1]D.E.Denning.An Intrusion Detection Model[J].IEEE Transactions on Software Engineering,1987,12(13):222-232.

[2]Han Jiawei,et al.Data Mining:Concepts and Techniques[M].北京:机械工业出版社,2000.

[3]韩东海,等.入侵检测系统实例剖析[M].北京:清华大学出版社,2002.

[4]Pawlak Z.Rough set approach to knowledge-based decision support[J]. European Journal of Operational Research,1997,99(23):48-57.

[5]Quinlan J R. Induction of decision trees[J].Machine Learning,1986,1(1):81-106.

[6]张文修,等.粗糙集理论与方法 [M].北京:科学出版社,2001.

[7]王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社,2001.

[8]UCI KDD Archive.KDD CUP 1999 data set[EB/OL].http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.ht ml,1999.

TP271+.82

A

1008-4681(2010)02-0047-03

2010-03-09;

2010-03-25

吴建源 (1978-),男,福建泉州人,广东培正学院计算机科学与工程系助教,硕士.研究方向:数据挖掘.

(责任编校:简子)