一种基于粗糙集属性约简的入侵检测算法

谢景伟

（湖南大众传媒职业技术学院，长沙 410100）

0 概述

一般情况下入侵检测系统（简称IDS）是对入侵的方法和系统的脆性进行分析的即时监视，以及依据专业人员知识人工写入的，且它是根据具体的系统环境和不同的检测方法的，普通的IDS是由事件采集器和分析器、检测模式数据库、检测模式生成器等主要部件组成。

事件采集器主要负责采集数据（包括网络数据包，系统日志等）；

事件分析器主要负责分析检测，并发出入侵警报；

检测模式数据库主要负责存放已检测出的攻击模式（也包括正常行为）；

检测模式生成器主要负责生成新模式加入到检测模式数据库。

在现实的网络传输中，平常数据量传输特别巨大、数据异常繁复。并且海量的数据里很多与入侵攻击没有关系，这些数据也许不一致、不完整，这样就造成入侵检测误报、漏报。

粗糙集理论（Rough set）是一类对付不确定、不精确和知识模糊等问题的数学方面的工具。在应对残缺数据分析、推断和找出数据间的联系、摄取有效特征、简化数据信息、模糊知识的说明、总结、归纳等地方有着无与伦比的优势。这些年来它获得了学术界的瞩目，并已出色地被用在机械学习、决断分析、模式识别等方面。而将其用在入侵检测，就可以达到自发从海量统计数据中找出新模型并制定新的安全规则，建立高精的智能IDS。

1 粗糙集基本概念

1.1 信息处理系统

信息处理系统可以简称信息系统，一般可以用S=（U，A）简化替代S=（U，A，V，f）。

信息处理系统的信息变换为关系表格形式显示，关系表每一行对应需要进行分析的一个对象，每一列对应这个对象的一个属性值。对象信息由各属性值来代替，此外关系表中一个属性就表示一个等价关系，全部的关系表也就是被定义的一系列等价关系，这就是知识库，这么做之后，之前讨论的信息约简就能够转化成关系表中属性约简。

1.2 属性约简

决策表代表决策信息系统的简化，其中有海量的样本信息。而其中一个样本代表一条决策规则，全部规则又构成一个决策规则集。在现实使用里，这种决策规则集没有实用性，因里面每个基本规则没有适用性，仅仅是机械的记下一个样本信息，没法适应别的状况，而进行属性约简后决策表的一条记录变成了有相同规律的样本信息，决策规则于是有了非常强的适用性[6]。

在信息分析中，最开始的决策表里的属性并非相同重要，不必要关系在信息库里是冗余的，冗余属性不单占用资源，且会扰乱人们，不能作出正确、简洁的决策，故决策表中属性约简的作用就是把冗余信息从信息库中剔除，并且属性约简不影响信息库的分类功能。笼统的说，决策表的条件属性对应决策属性时相对属性约简不唯一，也就是说同一决策表可以存在多个属性约简，其中属性的数量将直接决定决策规则的繁复和功能。所以，人们都希望能找到有最少属性数量的属性约简，只是由于属性组合的冲突问题又变成最小约简问题即是NP-Hard问题。当今应对此问题措施是引入启发数据到属性约简，之后经由启发数据可以缩减样本待搜索信息量，由此达到优化约简效率目的。

2 基于粗糙集属性入侵检测系统(DIS)模型

2.1 DIS模型

当前，基于粗糙集理论的DIS组成部分为事件采集器、数据挖掘器、智能决策机制以及模式匹配，主要是应用粗糙集理论对采集过来的数据进行分析和处理，得到用于入侵检测的模式，也就是能够生成有效的安全规则，然后模式匹配模块就能够依据这些规则来做入侵分析，得出判断，而决策部分就依据该判断作出相应的改进。

本章所讨论的基于粗糙集的DIS模型就是在对粗糙集属性频度约简算法进行改进的基础上，实现了入侵数据的处理分析，经由对应的处理剔除审计数据中冗余的信息，大大提升了数据挖掘步骤的效率，并能得到高效、简洁的安全规则。

2.2 基于属性频度的启发式约简算法及其改进

2.2.1 启发式约简算法（基于属性频度）

当前，一般的属性频度算法以决策表相应的差别矩阵为基本，综合其中全体属性集合，列出全部非核属性在差别矩阵中的频数，假如某非核属性的频数max，则表明这个非核属性在甄别两个不同的决策对象中起的作用最大，故应首先把它加入到约简集合中，并把包含该属性的全部其他属性组合删除。

基于属性频度的启发式算法：

将一个决策表作为算法的输入：T=U,R,V,f,U是论域，R=C∪D中C,D分别表示条件属性的集合和决策属性的集合。

该决策表T的一个约简B表示算法的输出。

第一步：寻找核属性即C0；开始初始化 B：C0→B

第二步：删除M中全部和B的交集不为空集的元素，且从条件属性集合中剔除B中所含元素。即：M-Q→M，C-B→P，Q={ | AijAij∩B≠∅}。

第三步：将ck∈P带入，算出在M中属性频度函数p(ck)，再从全部的 p(ck)找出有max值的cq，即 p(cq)= max{p(ck)}。

第四步：将cq归入约简集合中：B∪cq→B

第五步：重复第一到第四步直到M=∅。

2.2.2 基于属性频度的启发式约简算法的改进（最优化约简）

属性频度算法是根据属性的频度数来确定核属性，如果某个属性在决策表所对应的差别矩阵中出现的频数很多，那么就说这个属性对于决策规则是很重要的，故应首先被考虑加入核属性集合中。然而在现实运用中会出现达到max频度的属性不止一个。

对这一现象原算法采取从这些都达到最大频度的属性中随机挑选一个加入核属性集合中。显然这样得到的约简结果很可能不是决策表最优化约简。

基于属性频度的启发式算法的改进（实例）：

输入端：一个决策表T=U,R,V,f，U表示论域，R=C∪D，C,D表示条件属性集合以及决策属性集合。

输出端：决策表T的约简结果B。

第一步：寻找决策表核属性C0，同时初始化B：C0→B

第二步：删除M中全部和B的交集不为空集合的元素，从条件属性集合中剔除B相应元素。即：M-Q→M，C-B→P，Q={ | AijAij∩B≠∅}。

第三步：

(1)对全部的ck∈P，算出M的属性频度函数p(ck)；

(2)从全部p(ck)列出具有max值的cq，如果有max频度的属性有且只有一个，则 p(cq)=max{p(ck)}，随后将cq加入约简集合：B∪cq→B，随后跳到第四步；如果有max频度的属性不止一个时转到第三步的（3）；

(3)算出属性频度最大的各属性的 POSB∪{cq}(D) /IND(B,D)中所含元素数目，之后将 POSB∪{cq}(D) /IND(B,D)内元素数目最多的属性cq加入约简集合：B∪cq→B。

第五步：重复第一到第四步直到M=∅。

2.2.3 实验证明

为验证改进后算法可靠性，本节将进行UCI中的信息系统的测试分析。

仿真程序的开发环境及平台：

（1）CPU：Intel*2 2.4G

（2）内存： DDR400 768M

（3）操作系统：Windows XP sp3

（4）开发平台：VC++6.0

程序分为三部分进行：

第一部分：将数据集合用常用的属性频度算法进行属性约简，即原始算法约简对照。

第二部分：用改进算法对同样数据集合进行约简。即改进算法推演。

表1 医疗数据属性列表

第三部分：依据前两部分实验结果比较分析，并且得出最终结论。

例证：

使用一组共有700条的医疗数据属性列表作为数据集合。其中条件属性和决策属性（用class表示）如下表所示，此类属性均为离散型数据，故能够进行直接属性约简计算。

两部分的运算结果如表2所示：

表2 两种算法的约简结果

依据约简集合{A,C,E,F}、{C,E,F,G}约简原始数据集，最后约简比对情况如表3所示：

表3 约简结果比对

显然，约简集合{C,E,F,G}比{A,C,E,F}约简效率高得多。此外，根据多次实验在50%的情况下原算法得出的约简集合相对较弱，这证明了改进算法或多或少地优化了约简率。

3 结束语

现实的入侵检测非常复杂，入侵检测的分析数据量也越来越大，而粗糙集理论是处理这类问题的强有力的工具。本文在分析了粗糙集理论、约简算法的研究基础上，把粗糙集的数据约简技术应用到对网络数据的分析处理中，对基于属性频度的启发式约简算法进行了改进，实验结果表明，这种方法具有很高的约简性，通过粗糙集属性约简能够剔除待分析数据集合里冗余信息，此外通过数据挖掘获取安全规则。在识别未知攻击方面具有较好的性能，对于入侵检测技术的发展具有重要价值。

[1]王丹,吴孟达,刘银山.属性约简的一种简单算法[A].第12届全国模糊系统与模糊数学学术年会论文集[C].2004.

[2]武志峰.粗糙集理论及其在入侵检测中的应用研究[D].南京师范大学硕士论文，2005，(4).

[3]曾黄磷.粗集理论及其应用——关于数据推理的新方法[M].重庆：重庆大学出版社,1996.

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

[5]谢旭东,梁刚,黄天云.入侵检测系统技术介绍与发展趋势[J].福建电脑，2004，（6）.

[6]常晓艳,刘振娟.基于粗糙集属性约简的过程控制规则提取[A].第二届全国信息获取与处理学术会议论文集[C].2004.

[7]唐忠，曹俊月.基于粗糙集属性约简的SVM异常入侵检测方法[J].通信技术,2009，（2）.