一种基于集群概率的网络入侵检测算法
摘 要
本文针对近年来传统免疫算法在网络入侵应用中检测率较低以及误报率较高的问题，提出一种基于集群概率的免疫算法(CPAI)。该算法首先根据随机生成的单个检测器与自体元素的亲和力来生成候选检测器;然后采用概率密度函数(PDF)将具有相似行为的候选检测器组成一个群组并产生群组检测器;最后再通过对比每一个外来元素与群组检测器的亲和力，来判断该外来元素是否为异常。通过网络入侵的仿真实验表明，与传统的肯定选择算法(PSA)和实值否定选择算法(RVNSA)相比较，该方法在检测率、误报率以及平均反应时间方面都体现出了明显的优势。因此，也证明了本文提出方法的有效性。
【关键词】免疫算法 网络入侵 概率密度函数 集群概率
随着当前经济的发展，互联网在越来越多的金融交易中已成为一个不可或缺的角色，信息时代的快速性以及环境的动态性也时刻在推动着组织机构去构建更为复杂的信息网络。然而，由于涉及到在线服务，网络正在不断的受到各种各样的攻击入侵，而且攻击的种类也在不断加剧，网络非法入侵已经对信息安全构成了巨大的威胁，有效的监控放防御网络攻击已经刻不容缓。在这种情况下，入侵检测系统(IDS)被看作安全工具来加强信息网络的安全性。
近年来，越来越多的学者和研究人员致力于对入侵检测系统的研究和开发。文献[3]和文献[4]分别提出了利用支持向量机的方法来检测网络入侵，通过有效的消除网络中数据的无关的特性而加快了检测的速度同时也带来了训练阶段速度慢的问题。文献提出基于机器学习的方法来检测网络中的攻击，该方法具有在检测永久特征的时候不需要进行反馈，但是过于依赖正常的通信数据。人工免疫方法是根据自然免疫的原理，利用人工的方法使人体获得特异性免疫以此来防御外界病原体，该方法具有强大的鲁棒性和不断学习的能力，使得其在网络入侵研究中有着巨大的潜力。本文在免疫算法的基础上，提出概率密度函数和集群思想，对普通的免疫算法进行进一步的优化计算，并通过仿真实验证明该方法的高效性。
1 传统的免疫算法
1.1 实值否定选择算法(RVNSA)
实值否定选择算法(Real Value Negative Selection Algorithm)是由Dasgup在否定选择算法的基础上提出的，主要特征是用n维实值空间描述自体-非自体空间，用一个n维向量定义检测器，并且检测器半径用实值描述。因此，一个检测器可以被看作一个识别球。通过计算检测器与抗原之间的距离来识别异常。实值否定选择算法是采用一个启发式过程来反复地改变检测器的位置，以此达到对非自体空间覆盖的最大化和对字体样本覆盖的最小化的目的。
实值否定选择算法与编码二进制否定选择算法一样，整个检测过程包括数据的预处理、检测器的产生以及异常检测三个阶段。
检测器以及自体的表示：检测器d有一个中心点和一个非自体的识别半径。每个自体元素都有一个中心点和自体半径。这个自体半径的引入主要是为乐把靠近自体中心点的元素考虑为自体元素。在检测的时候，如果被检测的元素与检测器的距离小于检测器的非自体识别半径，则认为这个元素是异常的数据。
定义检测器：d=(c，rd)，其中c=(c1，c2，...，cm)为m维的点， d表示以c为中心，rd为半径的识别球(每一个检测器都由它的中心和半径组成)。
和检测器一样，自体也是由一个n维的点表示，以参数rs表示自体样本的阈值(允许半径)，也就是说，与样本点中心的距离大于 n这个阈值的样本点被认为是异常的样本数据。
匹配规则：当样本数据与检测器(或者自体)的中心距离小于它们的半径时，则说明样本数据与检测器(或者自体)发生了匹配。两点之间的距离使用欧式距离公式进行计算。如公式(1)所示：
1.2 肯定选择算法(PSA)
肯定选择算法是与否定选择算法[8]相对立的一种方法，该算法的具体描述如下：
(1)随机产生大量的候选检测器;
(2)对每一个候选检测器计算其与每个自体元素的亲和力，如果其不能识别自体中的任何元素，则被删除，否则，保留到成熟检测器集合中;
(3)将待检测数据与成熟检测器中的元素进行比较，发生匹配，则为正常数据;否则为异常。
检测器生成与检测如图1所示。
2 基于集群概率的人工免疫算法(CPAI)
2.1 概率密度函数
高斯模型就是用高斯概率密度函数(正态分布曲线)精确地量化事物，将一个事物分解为若干的基于高斯概率密度函数(正态分布曲线)形成的模型。本文在初始肯定选择算法的基础上，引入概率密度函数来对检测器的产生进行优化。在随机检测器与自体集合进行匹配的时候，引入概率密度函数计算自体集合中的元素与每个检测器的亲和度值，形成高斯概率密度混合模型，高斯混合模型是对在训练阶段产生检测器的概率密度函数的逼近，高斯混合模型如公式(1)所示：
P(x)= (1)
其中，n为检测器的数量，F为特征数， s表示自体集中的元素，xi为第i个检测器， σ为高斯分布的方差。
在检测阶段，同样使用概率密度函数对异常进行检测，如公式(2)所示：
P(x)= (2)
其中，x表示来自外部空间的新数据，其他字母的含义和公式(1)中的相同。利用高斯混合模型对每一个来自外部空间的新数据计算其与检测器之间的概率密度函数值，如果该值大于给定的某一个阈值，则判定该新数据为自体或者正常数据，否则将其判断为异常。
2.2 对检测器进行集群分类
基于上述单个使用概率密度函数的方法会增加计算成本，本文又引入了集群的思想。在网络入侵检测的过程中，正常行为的定义是一个很困难的任务，并且不同的定义程度都会影响到算法的性能。换句话说，就是正常行为会随着时间的改变而发生改变，现在还没有一个能够对他进行完整定义文件。例如，当一个新用户进入网络或者是一个新应用在网络中建立起来时，网络中的行为就可能发生变化，该新的网络行为就应该加入到已经存在的正常文件中。这也意味着正常行为的文件是由不同正常行为的子文件构成的，由于这些子文件表示不同种类的正常网络行为，因此它们之间能够互相区别。
在本文中，将正常行为的子文件看作是不同的正常行为集群，这样对生成的检测器也进行集群分类，以此提高算法的性能。首先，对正常行为的文件进行集群分类，将具有相似行为的自体集分在同一个组中，这样各个集群集合分别代表不同的正常行为;其次，利用上述概率密度函数对其进行计算，以此生成检测器的集群集合。如图2所示，检测器首先被分成若干个集群小组，再分别计算各自的概率密度函数。
在上述过程中，由于生成不同的集群检测器，因此需要对各自集群进行概率密度函数的计算。这样便产生多个高斯混合模型来对进入网络中的数据进行检测。当有新的数据进入网络时，则开始计算其与第一个检测器集群的概率密度函数，如果结果大于一定的阈值，则判断其为正常行为;否则，将其与第二个检测器集群进行匹配比较。如果该数据与所有集群检测器的概率密度函数值都比所给的阈值小，那么该数据则判定为异常数据。检测阶段如图3所示。
2.3 CPAI算法描述及具体步骤
在初始引入概率密度函数的时候，每当有一个新数据进入网络时，要计算其与所有检测器的概率密度函数值，这样就会增加计算成本。也就是说每有一个新数据出现，就要利用公式2对其进行运算，如果有M个新数据进入网络，则计算的复杂度为n×M，这样便大大的增加了检测器在检测阶段的时间。与此同时，引入集群思想后，每个新数据只需跟集群检测器进行匹配，因为每个集群检测器中含有多个检测器，因此检测器的集群个数必然小于检测器的个数n。
假设分成的集群个数为P，每个集群中含有pi个检测器，新数据的个数为M。当有新数据进入网络时，在入侵检测阶段，当新数据与第一个集群匹配时，则考虑其为正常，就不必再与余下的集群检测器进行匹配，这是最好的情形，计算的复杂度为pi×M，最坏的情况则是新数据要与所有的集群检测器进行匹配，这样计算的复杂度则为n×M，只有在这种情况下，计算复杂度才与上面所述相同。由于正常行为的情况一般会多于异常攻击的情况，因此加入集群思想使得此种方法更有效率。
在此种情况下，假设每个检测器检测新数据的高斯混合模型是相同的，每个检测器识别新数据的概率是相同的为1/n，其中n为检测器的个数。设pi是第i个集群中检测器的个数，则与第一个集群匹配的新数据所计算的复杂度为(p1+p2) ×1/n，如果不与第一个匹配与第二个匹配，则计算复杂度为(p1+p2) ×1/n，以此类推，平均的复杂度为公式(3)所示：
p1 ×1/n+ (p1+p2) ×1/n+ (p1+p2+p3) ×1/n+…
=1/n (n-i)pi (3)
该方法的具体实现步骤如下：
步骤1：随机产生检测器;
步骤2：利用集群思想将自体集进行分群处理;
步骤3：利用概率密度函数对随机检测器与分群自体集进行肯定选择匹配训练，生成集群检测器;
步骤4：计算新数据与集群检测器的概率密度函数值，如果该值大于阈值 ，则判定其为正常行为;否则，将其同余下的集群检测器继续进行匹配;
步骤5：转到步骤4。
该算法的流程图如图4所示：
3 仿真实验及结果分析
3.1 实验设计
对于网络入侵检测的研究，需要大量有效的实验数据。本实验数据采用KDD CUP1999入侵检测标准数据集，该数据集是从一个模拟的美国空军局域网上采集来的9个星期的网络连接数据，是用于网络安全中比较多的一个数据集，被分成具有标识的训练数据和未加标识的测试数据。测试数据和训练数据有着不同的概率分布，测试数据包含了一些未出现在训练数据中的攻击类型，这使得入侵检测更具有现实性。
KDDCup99训练数据集中每个记录包含了41个固定的特征属性，其中9个属性为离散的，其余32个属性为连续的;异常数据分为37种入侵类型，训练集中包含22种，另外15种攻击出现在测试数据集中。本实验采用KDDCup99中的网络入侵检测数据包Kddcup_data_10percent，Kddcup_data_10percent数据包是对KDDCup99数据包(大约490万条数据记录)10%的抽样，从中选取4600条数据，选择10种入侵模式，7个属性。实验环境采用Matlab 2012b、windows 7、Visual C++ 6.0作为仿真测试工具平台。
3.2 对比算法模型以及评价标准
在本实验中，将4600条中的1000条数据作为训练数据，再将剩余的3600条数据作为测试数据并分成8组，第一组到第八组的测试数据分别为100、200、300、400、500、600、700、800，把检测率，误报率和平均检测时间作为对比属性，将肯定选择算法、实值否定选择选法以及本文算法分别对8组数据进行运行计算再做一些比较。实验结果分别如图5和图6以及表1所示。
检测率的定义如下：
检测率=×100% (4)
误报率的定义如下：
误报率=
×100% (5)
由图5可以看出，在样本量一定时，本文所提出的CPAI(基于集群的免疫算法)方法具有较高的检测率，三种检测方法的检测率都是随着样本量的增多有所降低。这是因为随着数据量的增大，一方面增加了检测的基数，提高了检测的计算复杂度;另一方面，样本中会含有大量的“野值”样本，从而影响了检测器的性能。然而我们可以发现，本文所提出的算法在任意时刻斜率的绝对值分别小于RVNSA和PSA算法，这从另一个侧面体现了本文提出算法的鲁棒性，受“野值”样本点的干扰较小。
由图6可以看出，在误报率方面本文提出的算法相较于文中所涉及的算法也比较低，但是他们都随着样本量的增多而升高。然而，我们可以发现，当样本量大于700时，我们提出的方法的误报率有趋于平缓的趋势，而且在整个升高的过程中，其曲线的斜率始终小于前两种方法，在一定程度上也体现了方法的优势。
由表1可以看出，在检测时间上我们的方法明显优于前两中方法，这是由于我们的方法在检测的过程中采用了集群的思想，在样本量相同的情况下，大大降低了检测的次数，从而降低了检测的时间复杂度。
4 结语
本文提出一种基于集群概率的免疫算法，通过实验仿真与肯定选择算法和实值否定选择算法的比较验证了该算法具有较高的检测率和较低的误报率以及平均检测时间也优于其他两种方法，虽然由图形显示在检测数据增多的情况下，检测率会降低、误报率会增高，但是降低和增高的趋势都有所减缓且仍能保持较低的误报率和较高的检测率，具有较好的理论意义。
参考文献
[1]Zhou，Chenfeng Vincent，Leckie， Shanika Karunasekera et al.A survey of coordinated attacks and collaborative intrusion detection[J].Computers and Security，2009，29(1)：124-140.
[2]于海涛，李梓，王振福等.入侵检测相关技术的研究[J].智能计算机与应用，2013(04)，3(2)：62-67.
[3]温祥西，孟相如，马志强.基于双重支持向量机的网络故障诊断[J].控制与决策，2013，28(4)：506-510.
[4]向昌盛，张林峰.PSO-SVM在网络入侵检测中的应用[J].计算机工程与设计，2013，34(4)：1222-1225.
[5]唐菀，曹阳，杨喜敏，覃俊.网络入侵检测的GEP规则提取算法研究[J].计算机科学，2009，36(11)：79-82.
[6]柴争义，王献荣，王亮.用于异常检测的实值否定选择算法[J].吉林大学学报(工学版)，2012，12(1)：176-181.
[7]钱淑渠，武慧虹.混沌系统动态多目标免疫优化算法及其应用[J].计算机仿真，2009，26(6)：207-211+262.
[8]金章赞，廖明宏，肖刚.否定选择算法综述[J].通信学报，2013，34(1)：159-170.
[9]袁礼海，李钊，宋建社.利用高斯混合模型实现概率密度函数逼近[J].无线电通信技术，2007，33(2)：20-22.
[10]黄红艳，安素芳.数据流聚类算法在入侵检测中的应用[J].计算机工程与应用，2012，48(20)：112-116.
[11]覃艳，王洪，周全华.数据挖掘中聚类算法的研究[J].网络安全技术与应用，2014(01)：65-66.
[12]Stolfo S， Fan W，Lee W，et al.KDD cup 1999data[DB/OL].[1999].http：//kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.