基于粗糙集的免疫入侵检测器优化算法

◆向 婷 谭敏生 于俊勇

（南华大学衡阳计算机科学与技术学院 湖南 421000）

基于粗糙集的免疫入侵检测器优化算法

◆向 婷 谭敏生 于俊勇

（南华大学衡阳计算机科学与技术学院 湖南 421000）

本文分析了免疫入侵检测器在实值空间下存在的问题，提出一种基于粗糙集的免疫入侵检测器优化算法（IIDOA-R&A）：利用粗糙集约简理论将高维形态空间转换为低维空间，并利用属性重要度加权欧式距离来计算亲和度大小，通过亲和度对比来优化检测器。实验表明：优化后的检测器不仅提高了检测的速度，改善检测器存在的高重叠问题，对非自体集的覆盖效果也相对理想。

免疫入侵检测器; 实值形态空间; 粗糙集; 属性重要度; 加权欧式距离

0 前言

随着网络的飞速发展，信息安全防护显得尤为重要。入侵检测作为一种积极主动的网络安全技术，成为了保证网络安全的重要手段。由于生物免疫系统具有自适应、鲁棒性等诸多优点，将免疫机理应用到入侵检测系统中的研究也越来越多。然而对于基于免疫机理的入侵检测系统（IDS）来说，检测器的质量是决定检测性能的重中之重，所以检测器的优化问题成为各个学者争相研究的热点。

1 形态空间

基于免疫机理的IDS，主要是在形态空间下进行讨论[1]。形态空间U主要包含自体空间US和非自体空间UN两个部分在理想状态下，US由自体集合S覆盖，UN由检测器集合覆盖。而现实中却肯定存在没有被检测器覆盖的非自体空间，称之为黑洞H。检测器集合是由候选检测器集合C通过自体耐受过程得到。目前，检测器根据表示的形态空间不同，分为二进制形态空间和实值形态空间。由于二进制空间比较简单，这里不予讨论。在实值空间中，每个自体样本可以表示为:其中i=1，2，…，Ns， sij为该自体样本的第j维属性值，j=1，2，…，N，r为该自体样本训练半径，OtherAttribute为该自体样本的其他属性，如年龄等。同理，也可以用相同方法表示检测器。检测器主要通过亲和力匹配来进行检测。

2 问题分析

在实值形态空间中，检测器存在的问题如下:

（1）检测器高重叠和黑洞问题

高重叠和黑洞问题是基于免疫机理的入侵检测系统一直存在的问题。为此，很多学者也做了相当多的研究:Li[2]等人提出的V-detector检测器生成算法，以检测器中心与其亲和力最大的自体边界间的距离作为检测半径。但是它又造成每个检测器都会覆盖自体与非自体边界区域，重叠覆盖现象严重。席亮[3]提出一种检测器优化算法，通过比较检测器间的亲和力判断检测器的优良程度，并利用子代替换效果较差的个体，取得比较好的结果。

（2）检测器数量问题

假设检测器相互独立，设每个检测器匹配异常事件的概率为Pi，则任一个异常没有被检测器集合匹配的概率当 Nd很大的时候，Pi维持在一个较小的水平，为了方便表示，设定Pi为定值Pm，则上式可近似表示为:当 Pm一定时，检测器集合规模与一次误报率成指数关系。而且在实际应用中，检测器相互独立不可能全部成立，使得检测的失败概率增大，也增大了系统的检测负担。

（3）检测器属性维度问题

对于实值检测器，属性数较多，且有些属性的相关性较强，从而带来了巨大的额外的计算代价。

3 粗糙集理论

粗糙集理论是一种用于处理不确定、不精确、不完整知识的数学工具。其相关概念如下:

（1）定义1 知识库[4]

对于一个论域U，S为U上的等价关系簇，那么二元组K=（U，S）就叫一个知识库，表示论域U上的一个近似空间。

（2）定义2 决策表[5]

对于一个五元组DT=（U，C，D，V，f），其中U={x1，x2，…，xn}是由n个非空对象组成的对象集合，称之为论域; C={a|a∈C}且C≠∅是条件属性集合; D={d|d∈D}且D≠∅为决策属性集; 对于条件属性集C和决策属性集D有:C∩D=∅; V=∪Va（∀a∈C∪D）为信息系统f的值域，可以用Va来表示; f={fa|fa:U→Va，∀a∈C∪D}是一个信息函数，fa表示属性a的信息函数; 此时该五元组DT就叫决策表。

（3）定义3 不可分辨关系[4]

对于论域U上的等价簇S，若∃P≠∅，P⊆S，则∩P依然是U上的一个等价关系集合，称为P上的不可分辨关系，记为IND（P），简称P，即:

（4）定义4 上近似，下近似[4]

对于一个知识库K=（U，S），U为论域，S为U上的等价关系簇，那么∀X⊆U和U上的一个等价关系R∈IND（K），那么定义子集X关于知识R的上近似和下近似分别为:

（5）定义5 属性重要度[5]

给定一个决策表DT，对于条件属性a∈C，相对于决策属性D的重要度为:

4 基于粗糙集的免疫入侵检测器优化算法

4.1 改进的亲和度计算方法

对于传统的亲和力计算方法，往往忽略了各个属性本身存在的重要度的差异，而采用统一的标准来对待数据的每一个属性，而基于属性重要度加权欧式距离很好的考虑到了属性间的关系，属性重要度越大，那么对于亲和力计算的结果就越重要，影响就越大。现两个检测器d1和d2，其加权欧式距离可以表示为:

其中SGFi是第i个属性的重要度，d1i和d2i分别表示检测器d1和检测器d2的第i个属性值。

4.2 基本思想

实值检测器中的属性众多，且有些属性的相关性较强，那么有必要将检测器的属性进行约简，从而减少计算代价的同时，也不影响检测器的分类性。对于约简后的检测器，可以用亲和度来表示两个检测器间的相似程度。亲和度越高，那么两个检测器就越相似。而这种相似的个体越多，则相应的重叠率就越高。所以采取在多个相似的个体之中，只保留较优秀的那个个体的方法来优化检测器的分布。同时由于属性之间有重要度的差异，所以在计算亲和度的时候，应该充分考虑各个属性本身的重要度，利用属性重要度来计算亲和力的大小。

4.3 算法步骤

图1 算法流程

（1）正规化方式

本文的正规化处理采用如下方式:首先计算每一个属性值的方差μj和标准差σj，再根据如下两个公式将样本进行正规化:

5 实验

实验首先将各个数据集样本的属性进行正规化，并设定自体半径为0.05。为了验证本文提出的改进算法和v-detector算法对非自体集的覆盖效果和检测器间的重叠率，实验采用二维空间，以五角星数据集进行实验[6]，分别用本文的优化算法和v-detector算法优化含120个检测器的检测器集合。并使用Monte Carlo方法[7-8]计算检测器对非自体的覆盖率和检测器间的重叠率:

（1）估计单个检测器占整个形态空间的体积（百分比）:

（2）估计单个检测器与其他检测器重叠区域占其本身区域的百分比:

（3）估计检测器集合对非自体空间的覆盖率:

（4）估计检测器集合的总重叠率:

表1 二种算法检测器覆盖率与重叠率的比较

从实验结果可以看出，优化后的算法虽然在检测器对非自体的覆盖率有所下降，但是检测器间的重叠率远远降低。在保证的覆盖率的情况，大幅度降低的重叠率，优化了检测器。

6 结束语

本文利用粗糙集理论，先将检测器属性降维，再利用属性重要度改进传统的简单的利用欧式距离来计算亲和度，通过检测器间的亲和力对比来优化检测器的分布。实验结果表明，本文提出的检测器优化算法，在保证一定的覆盖率的前提下，大大的降低了检测器间的重叠率，进而提高了检测率。

[1]TEW J,PHIPPS P,MANDEL T.The maintenance and regulation of human immune response:persisting antigen and t he role of follicular antigen-binging dendritic cell [J].Immunol ogical Review,1980.

[2]Li G Y,Li T,Zeng J,et al.Negative selection algorithm based on immune suppression[C]//Proceedings of 8th Internati onal Conference on Machine Learning and Cybernetics.Baodin g,China,IEEE,2009.

[3]席亮.免疫入侵检测自体与检测器动态自适应机制研究[D].哈尔滨理工大学，2012.

[4]蔡忠闽，管晓宏，邵萍，孙国基.基于粗糙集理论的入侵检测新方法 [J].计算机学报，2003.

[5]苗夺谦，李道国.粗糙集理论、算法及应用[M].清华大学出版社，2008.

[6]ZHOU J,DASGUPTA D.Estimating the detector cover age in a negative selection algorithm.In:Proceedings of the 20 05 Conference on Genetice and Evolutionary Computation,W ashington DC,USA,2005.

[7]MACK AY J C.Introduction to Monte Carlo method [M].Oak Ridge National Laboratory,Oak Rigde,USA,1995.

[8]LIU J.S.Monte Carlo Strategies in Scientific Computin g [M].Springer-Verleg,Berlin,Germany,2001.