论文部分内容阅读
[摘要]针对入侵检测系统中安全规则提取的困难，提出利用粗集方法从系统日志信息中挖掘安全规则，并给出规则挖掘算法。通过KDDCup99入侵数据测试集中的数据验证该方法的有效性和可行性，为入侵检测中安全规则的提取提供一种新方法。
[关键词]网络安全 入侵检测 粗集方法 数据挖掘
中图分类号：TP3文献标识码：A文章编号：1671－7597（2009）0310044－02
一、引言
将数据挖掘技术应用于入侵检测中，构建基于数据挖掘技术的入侵检测系统，就可以自动地从大量的审计数据中发现新的模型或安全规则，消除入侵检测系统中规则提取和编码的困难，建立一个准确性高的智能入侵检测系统。
二、有关概念与理论
1．粗集理论是波兰数学家Z.Pawlak在1982年提出的一种数据分析的方法。在分类的意义下，粗集理论定义了模糊性与不确定性的概念，其特点是不需要预先给定某些特征或属性的数量描述，而是直接从给定问题的描述集合出发，找出该问题中的内在规律。目前已被广泛应用于人工智能、模式识别、知识数据库挖掘、决策支持、机器学习、智能控制等领域。粗集理论中的核心问题是属性约简，即从决策表中去除不必要的属性。属性约简的目标就是要从条件属性集合中发现部分必要的条件属性，使得这部分条件属性形成的相对于决策属性的分类和所有条件属性所形成的相对于决策属性的分类一致，即与所有条件属性相对于决策属性有相同的分类能力。入侵检测可以看作是一种分类问题，即将每一条审计记录分为正常的或是某一种特定的入侵。
2．入侵检测：顾名思义，是指对入侵行为的发现，它通过在计算机网络或计算机系统中的若干关键点收集信息并对收集到的信息进行分析，从而判断网络或系统中是否有违反安全策略的行为和被攻击的迹象。入侵检测是指识别恶意破坏计算机或网络系统安全的过程，通过对计算机或网络系统中的若干关键信息进行收集、分析，从中发现网络或系统中是否有违反安全策略的行为和被攻击的迹象。完成入侵检测功能的软件和硬件组合便是入侵检测系统。
三、系统原型设计
（一）设计原理与方法
基于入侵检测系统与Rough集理论的特点，且考虑到本文主要讨论Rough集理论在基于异常的入侵检测上的应用，本文将主要关注Rough集理论在检测时的应用细节，以此证明Rough集理论在异常入侵检测上的应用可能性、优越点、不足以及应用时所需要考虑的问题。在进行系统设计时，将遵循以下原则进行系统设计：
1．多层抽象化：即系统以分层形式实现，并在各层间抽象化，以减少算法本身对外部数据形式及模块的依赖。
2．架构参考一些当前学术界和行业领域里的IDS框架模型，以此作为系统架构的模板，这样可以避免在设计架构时出现重大缺陷，同时也有利于兼容性。
（二）模型中Rough集的核心算法
使用Rough Set理论分析决策系统的一般过程是先对决策表的属性进行约简然后由属性约简得到决策规则具体步骤如下：
1．数据采集建立样本集；
2．对连续属性进行离散化；
3．用离散化后的条件属性和决策属性建立决策表；
4．用Rough Set 理论对条件属性化简得到最小决策表即决策规则；
5．用决策规则对经属性处理后的待识样本进行决策。
其中使用到关于Rough集理论的主要算法有下列几种：离散化算法、属性约简算法、规则生成算法、分类算法，以及在处理数据集规模比较大时所用到的分解算法。有些算法也可以把属性约简和规则生成合并在一起，然而功能依然是相似的。而这些算法之间的彼此关系，可以用下面的图1表示。
（三）数据离散化
一般在进行属性约简和规则生成之前，都需要进行离散化。离散化过程是对属性值属于连续空间的属性进行处理，使得该属性值的值域可以由若干个区间来表示，每个区间作为一个离散子，原来该属性里的各记录中，该属性的值将根据它所属的离散子，转化成该离散子所对应的新值。从而使得所有连续空间可以由若干个离散区间表示，从而在规则算法处理时，能产生更加符合需要的规则集。在对入侵检测数据集的处理中，我们采用算法1所示的离散化过程。
Algorithm 1：离散化过程
Input:The consistent decision table A
Output:The semi-minimal set of cuts P consistent with A
Data Structure: D-the semi-minimal set of cuts; L=PART(D)-the partition of U defined by D;CA-the set of all possible cuts on A
（四）Decomposition Tree算法
标准的RSKDD处理过程对于大数据集的分析效率较低，在做规则生成之前，应对数据表进行分解。分解过程是KDD在处理数据规模非常大的数据集时常常使用的方法。分解过程是一个比较通用的方法，其主要目的是通过在数据集的属性中通过寻找出某些分类标记或分类界限，然后以这些分类标记或界限作为分解因子，把数据集分解成数个子集，然后再对这些子集使用相同的分解方法，直到所有分解出来的子集所包含的数据元素个数均符合规定的大小，然后再对每个数据子集使用数据挖掘算法。树状结构通常是表示这种分解结果的一个比较好的形式，我们称它为分解树。在分解树中，每个分支的集合，在该分支所表示的属性上，有着相同的属性特点，如左分支的所有集合该属性都小于等于这个分支节点的节点值，而右分支的所有集合该属性都大于这个分支节点的节点值。分解树算法过程大致如下，它首先去找到表A的最佳模板，然后根据模板将A分成两个子集，再对两个子集判断，若未达到符合的大小，则递归进行分解直到完成。
Algorithm2: Decomposition by template tree
Step1Find the best template T in A.
Step2Divide A onto two subtables:A1 containing all objects satisfying
T and A2=A- A1
Step3If obtained subtables are of acceptable size(in the sense of rough set methods)
then stop
else repeat from step 1 to 3 for all"too large"subtables.
该算法生成一个二叉树，叶子节点是从原表中分解出来的子表，这些子表再通过规则生成算法生成各自的规则集保存在叶节点里，则该生成树可用于接下来的分类操作中。假设u为一个待分类对象且A(T)是一个包含所有符合模板T的对象的子表，通过算法3从根开始搜索直到将该对象的类别分类出来。
Algorithm3: Classification by template tree
Step 1 If u matches template T found for A
then: go to subtree related to A(T)
else :go to subtree related to A(〕.
Step2 If u is at the leaf of the tree then go to 3
else: repeat 1-2 substituting A(T)(or A()for A .
四、实验结果
实验中使用了KDDCup99的数据作为训练和检测数据。
（一）实验选取的数据介绍
在实验中，我们选取KDDCup99数据集中的一部分数据作为我们实验的训练数据和测试数据。
（二）属性集约简
实验中我们对离散化后的训练数据用粗糙集进行属性约简，在具有41个属性的训练数据上，我们共生成了4个属性集约简，属性集约简的表示形式如下：
(duration,service,src_bytes,dst_bytes)
(duration,service,src_bytes,dst_host_count)
(service,src_bytes,dst_bytes,logged_in,dst_host_count,
dst_host_same_src_port_rate)
(protocol_type,src_bytes,dst_bytes,is_guest_login,dst_host_count,
dst_host_srv_count,dst_host_same_src_port_rate)
（三）实验结果和分析
经过对大量训练数据和测试数据的反复训练及测试，得到比较理想的效果。从表2可以看出，本文提出的Rough集在基于异常的入侵检测方法具有高检测率、低误检率。
五、总结
本文通过实验验证了基于Rough集理论的异常入侵检测模型的有效性，测试了系统的性能。实验结果表明，该方法对DoS和Probe攻击具有很高的检测率，具有较低的误检率，并且对U2R和R2L攻击也具有较好的检测率，这进一步说明了将Rough集应用于基于异常的入侵检测模型的可行性。
基金项目：湖南省教育厅科学研究资助项目(07c720)
参考文献：
[1]E著、李逢天等译，Carter,Cisco，安全入侵检测系统，北京：人民邮电出版社，2003.
[2]罗守山，入侵检测，北京邮电大学出版社，2004.4.
[3]韩东海、王超、李群，入侵检测系统及实例剖析，北京：清华大学出版社，2002.5.
[关键词]网络安全 入侵检测 粗集方法 数据挖掘
中图分类号：TP3文献标识码：A文章编号：1671－7597（2009）0310044－02
一、引言
将数据挖掘技术应用于入侵检测中，构建基于数据挖掘技术的入侵检测系统，就可以自动地从大量的审计数据中发现新的模型或安全规则，消除入侵检测系统中规则提取和编码的困难，建立一个准确性高的智能入侵检测系统。
二、有关概念与理论
1．粗集理论是波兰数学家Z.Pawlak在1982年提出的一种数据分析的方法。在分类的意义下，粗集理论定义了模糊性与不确定性的概念，其特点是不需要预先给定某些特征或属性的数量描述，而是直接从给定问题的描述集合出发，找出该问题中的内在规律。目前已被广泛应用于人工智能、模式识别、知识数据库挖掘、决策支持、机器学习、智能控制等领域。粗集理论中的核心问题是属性约简，即从决策表中去除不必要的属性。属性约简的目标就是要从条件属性集合中发现部分必要的条件属性，使得这部分条件属性形成的相对于决策属性的分类和所有条件属性所形成的相对于决策属性的分类一致，即与所有条件属性相对于决策属性有相同的分类能力。入侵检测可以看作是一种分类问题，即将每一条审计记录分为正常的或是某一种特定的入侵。
2．入侵检测：顾名思义，是指对入侵行为的发现，它通过在计算机网络或计算机系统中的若干关键点收集信息并对收集到的信息进行分析，从而判断网络或系统中是否有违反安全策略的行为和被攻击的迹象。入侵检测是指识别恶意破坏计算机或网络系统安全的过程，通过对计算机或网络系统中的若干关键信息进行收集、分析，从中发现网络或系统中是否有违反安全策略的行为和被攻击的迹象。完成入侵检测功能的软件和硬件组合便是入侵检测系统。
三、系统原型设计
（一）设计原理与方法
基于入侵检测系统与Rough集理论的特点，且考虑到本文主要讨论Rough集理论在基于异常的入侵检测上的应用，本文将主要关注Rough集理论在检测时的应用细节，以此证明Rough集理论在异常入侵检测上的应用可能性、优越点、不足以及应用时所需要考虑的问题。在进行系统设计时，将遵循以下原则进行系统设计：
1．多层抽象化：即系统以分层形式实现，并在各层间抽象化，以减少算法本身对外部数据形式及模块的依赖。
2．架构参考一些当前学术界和行业领域里的IDS框架模型，以此作为系统架构的模板，这样可以避免在设计架构时出现重大缺陷，同时也有利于兼容性。
（二）模型中Rough集的核心算法
使用Rough Set理论分析决策系统的一般过程是先对决策表的属性进行约简然后由属性约简得到决策规则具体步骤如下：
1．数据采集建立样本集；
2．对连续属性进行离散化；
3．用离散化后的条件属性和决策属性建立决策表；
4．用Rough Set 理论对条件属性化简得到最小决策表即决策规则；
5．用决策规则对经属性处理后的待识样本进行决策。
其中使用到关于Rough集理论的主要算法有下列几种：离散化算法、属性约简算法、规则生成算法、分类算法，以及在处理数据集规模比较大时所用到的分解算法。有些算法也可以把属性约简和规则生成合并在一起，然而功能依然是相似的。而这些算法之间的彼此关系，可以用下面的图1表示。
（三）数据离散化
一般在进行属性约简和规则生成之前，都需要进行离散化。离散化过程是对属性值属于连续空间的属性进行处理，使得该属性值的值域可以由若干个区间来表示，每个区间作为一个离散子，原来该属性里的各记录中，该属性的值将根据它所属的离散子，转化成该离散子所对应的新值。从而使得所有连续空间可以由若干个离散区间表示，从而在规则算法处理时，能产生更加符合需要的规则集。在对入侵检测数据集的处理中，我们采用算法1所示的离散化过程。
Algorithm 1：离散化过程
Input:The consistent decision table A
Output:The semi-minimal set of cuts P consistent with A
Data Structure: D-the semi-minimal set of cuts; L=PART(D)-the partition of U defined by D;CA-the set of all possible cuts on A
（四）Decomposition Tree算法
标准的RSKDD处理过程对于大数据集的分析效率较低，在做规则生成之前，应对数据表进行分解。分解过程是KDD在处理数据规模非常大的数据集时常常使用的方法。分解过程是一个比较通用的方法，其主要目的是通过在数据集的属性中通过寻找出某些分类标记或分类界限，然后以这些分类标记或界限作为分解因子，把数据集分解成数个子集，然后再对这些子集使用相同的分解方法，直到所有分解出来的子集所包含的数据元素个数均符合规定的大小，然后再对每个数据子集使用数据挖掘算法。树状结构通常是表示这种分解结果的一个比较好的形式，我们称它为分解树。在分解树中，每个分支的集合，在该分支所表示的属性上，有着相同的属性特点，如左分支的所有集合该属性都小于等于这个分支节点的节点值，而右分支的所有集合该属性都大于这个分支节点的节点值。分解树算法过程大致如下，它首先去找到表A的最佳模板，然后根据模板将A分成两个子集，再对两个子集判断，若未达到符合的大小，则递归进行分解直到完成。
Algorithm2: Decomposition by template tree
Step1Find the best template T in A.
Step2Divide A onto two subtables:A1 containing all objects satisfying
T and A2=A- A1
Step3If obtained subtables are of acceptable size(in the sense of rough set methods)
then stop
else repeat from step 1 to 3 for all"too large"subtables.
该算法生成一个二叉树，叶子节点是从原表中分解出来的子表，这些子表再通过规则生成算法生成各自的规则集保存在叶节点里，则该生成树可用于接下来的分类操作中。假设u为一个待分类对象且A(T)是一个包含所有符合模板T的对象的子表，通过算法3从根开始搜索直到将该对象的类别分类出来。
Algorithm3: Classification by template tree
Step 1 If u matches template T found for A
then: go to subtree related to A(T)
else :go to subtree related to A(〕.
Step2 If u is at the leaf of the tree then go to 3
else: repeat 1-2 substituting A(T)(or A()for A .
四、实验结果
实验中使用了KDDCup99的数据作为训练和检测数据。
（一）实验选取的数据介绍
在实验中，我们选取KDDCup99数据集中的一部分数据作为我们实验的训练数据和测试数据。
（二）属性集约简
实验中我们对离散化后的训练数据用粗糙集进行属性约简，在具有41个属性的训练数据上，我们共生成了4个属性集约简，属性集约简的表示形式如下：
(duration,service,src_bytes,dst_bytes)
(duration,service,src_bytes,dst_host_count)
(service,src_bytes,dst_bytes,logged_in,dst_host_count,
dst_host_same_src_port_rate)
(protocol_type,src_bytes,dst_bytes,is_guest_login,dst_host_count,
dst_host_srv_count,dst_host_same_src_port_rate)
（三）实验结果和分析
经过对大量训练数据和测试数据的反复训练及测试，得到比较理想的效果。从表2可以看出，本文提出的Rough集在基于异常的入侵检测方法具有高检测率、低误检率。
五、总结
本文通过实验验证了基于Rough集理论的异常入侵检测模型的有效性，测试了系统的性能。实验结果表明，该方法对DoS和Probe攻击具有很高的检测率，具有较低的误检率，并且对U2R和R2L攻击也具有较好的检测率，这进一步说明了将Rough集应用于基于异常的入侵检测模型的可行性。
基金项目：湖南省教育厅科学研究资助项目(07c720)
参考文献：
[1]E著、李逢天等译，Carter,Cisco，安全入侵检测系统，北京：人民邮电出版社，2003.
[2]罗守山，入侵检测，北京邮电大学出版社，2004.4.
[3]韩东海、王超、李群，入侵检测系统及实例剖析，北京：清华大学出版社，2002.5.