基于多克隆和C—均值算法的入侵检测系统
时间：2022-10-27 01:01:28
【前言】基于多克隆和C—均值算法的入侵检测系统由文秘帮小编整理而成，但愿对你的学习工作带来帮助。0 引言 随着计算机网络技术的飞速发展，网络入侵的风险也日益加剧，如何对网络攻击进行有效的检测已成为网络安全领域的重要课题。入侵检测就是从系统所处理的数据中找出威胁系统安全的因素，并对威胁做出相应处理。是一种主动的、实时的网络安全防御措施[1]。 入侵检...
摘要： 本文将多克隆算子和模糊C-均值算法相结合，将多克隆的免疫基因策略作用于特定的亲合度函数来指导聚类过程，得到一种无监督的聚类分析方法。该方法不依赖先验知识、与数据分布无关、能够有效处理大规模原始数据。在KDD CUP99数据集上进行了仿真实验，实验结果表明基于本文方法的入侵检测系统具备良好的性能。
Abstract： A novel clustering algorithm is developed by using polyclonal algorithm and fuzzy C-means algorithm， which is directed by affinity function applied by polyclonal strategy. Independent of transcendental knowledge and data distribution， this algorithm can deal with mass unlabeled data， and the computer simulations on the KDD CUP99 dataset show that this method can achieve good performance.
Key words： poly-clonal strategy；Fuzzy C-Means；intrusion detection
中图分类号：TP393 文献标识码：A 文章编号：1006-4311（2013）25-0192-02
0 引言
随着计算机网络技术的飞速发展，网络入侵的风险也日益加剧，如何对网络攻击进行有效的检测已成为网络安全领域的重要课题。入侵检测就是从系统所处理的数据中找出威胁系统安全的因素，并对威胁做出相应处理。是一种主动的、实时的网络安全防御措施[1]。
入侵检测算法通过建立用户正常行为模型，以是否显著偏离正常模型来进行检测。大多数系统在构造检测算法时，均采用带标签或完全正常的数据来训练获得正常模型，这种有监督的方法在实际中工作量巨大，并不可行。本文旨在构造一种无监督的入侵检测系统：将人工免疫系统中的多克隆策略引入聚类算法进行聚类分析获得正常模型，从而进行异常检测。
1 多克隆策略
1.1 克隆算法
克隆算法是一种人工免疫系统方法[2]。其操作过程可表示成如下的随机过程，即克隆操作、免疫基因操作和压缩选择操作。
A（i）■B（i）■C（i）■A（i+1）
克隆的实质就是在进化过程中，在一代最优解的附近，根据亲合度的大小，产生一个变异解的群体，扩大搜索范围，增加抗体的多样性，防止了进化早熟和搜索陷于局部最优。
1.2 多克隆算法
在人工免疫系统中，免疫基因操作包括抗体的交叉和变异。仅采用变异的克隆算法为单克隆算法；交叉和变异都采用的为多克隆算法，其更多的继承了父代的特点，收敛速度更快。
2 基于多克隆策略的模糊C-均值聚类算法
聚类分析是一种无监督的数据分析方法，将一个未标记的样本集按某种准则划分成若干子集。其中相似的样本尽量归为一类，不相似的样本尽量归为不同类[3]。
传统的聚类分析方法是一种硬划分，会将每个待辨识的对象严格的划分到某一类中，具有非此即彼的性质。然而实际中，大多数对象并没有严格的属性，它们在性态和类属方面存在着中介性，适合进行软划分。模糊集理论为这种软划分提供了有力的分析工具，用模糊的方法来处理聚类问题的过程即为模糊聚类分析方法。模糊聚类建立起了样本对于类别的不确定性的描述，可以更客观的反映现实世界，从而成为聚类分析研究的主流。在众多模糊聚类方法中，应用最广泛的就是模糊C-均值聚类算法。从本质上来说，该算法是一种局部搜索优化方法，对初始化很敏感，容易在迭代中陷入局部最优。为了克服这些缺点，可以引入人工免疫系统算子对算法进行改进，从而提高算法的收敛速度和聚类的有效性。本文就将多克隆算子作用于特定的亲和度函数来指导模糊C-均值聚类的过程。
2.1 目标函数
令X={x1，…，xn}表示一个样本集，其中xi=（x■■，…，x■■，x■■，
x■■，…，x■■）■表示第i个样本的m个特征值。对X进行聚类，目的就是要找到一个最优划分，将其分为k类。本文通过以下目标函数来指导聚类的过程。
C（W，P）=■（■w■■■x■■-p■■■）+λ■w■■■δ（x■■，
p■■），w∈[0，1]（1）
其中pi=（pi1，pi2，…，pim）T表示第i类的原型，wij是xj属于第I类的隶属度。W是k×n阶的划分矩阵，满足概率约束■w■=1。
2.2 相异度度量 网络数据的特点是具有混合类属特征，设d为混合类型数据的匹配相异度值：
d（xi，xj）=■（2）
对非数值分类属性的相异匹配测度定义为：
δ（a，b）=0 a=b1 a≠b
2.3 编码 令一组聚类原型P为一个抗体。把原型中的各组特征连接起来，根据各自的取值范围将其量化值k编码成一个抗体：
A■（0）={ξ■，…，ξ■，…，ξ■，…，ξ■，ξ■，…，ξ■}，i=1，2，…，N（3）
2.4 亲合度函数 抗原xi与抗体yj的亲合度函数f（xi， yj，）构造如下，f（xi，yj，）越大，说明yj越接近xi。
f（xi，yj，）=f（xi，yj）=■（4）
2.5 多克隆算法
Step1.k=0；初始化抗体群A（0），设定交叉、变异、选择概率等参数；
Step2.计算A（0）中抗体间亲合度；
Step3.当A（k）中没有最优个体出现时：
Step3.1克隆：B（k）=（A（k））=[（a1（k）），（a2（k）），…，（au（k））]T；
Step3.2交叉：C（k）=TCc（B（k）；
Step3.3变异：D（k）=TCm（C（k））；
Step3.4计算机当前种群中抗体亲合度；
Step4.克隆选择：A（k+1）=TCs（D（k））；
Step5.在A（k+1）中，计算机抗体亲合度，k=k+1，若满足预设的终止条件，算法结束。
2.6 聚类正常模型 在聚类算法中，对抗体编码后进行抗体多克隆操作，对目标函数进行优化，直到聚类原型收敛到最优解，得到聚类结果，即X被划分为c个子集。若某个子集中的样本数量X中样本数据总量之比不小于δ（0
在以上聚类分析算法中，多克隆算子在每代个体中进行交叉、变异和克隆选择操作。交叉和变异算子使得聚类算法的动态性能受进化策略控制，使其具备自学习的
能力。
克隆选择是由亲合度诱导的抗体随机映射过程，其实质是将一个低维空间（n维）的问题转化到更高维（N维）的空间中解决，然后将结果投影到低维空间（n维）中，从而获得对问题更全面的认识。
3 基于多克隆聚类的入侵检测算法
对于样本集Y，计算yi（1？燮i？燮n）和各聚类中心pi的距离测度d（yi，pj），找到最短距离d（yi，pmin）（1？燮min？燮c），pmin∈Pc。那么yi应属于第c类且此类的类别（正常或异常子集）就是yi的类标，由此判定出输入的数据是否为网络攻击。
4 仿真实验
实验采用KDD CUP99入侵检测数据集，该数据集包含4，900，000多条网络连接记录。有大约500万条训练数据，约200万条测试数据。每个数据都带有协议类型、传输的字节数等参数，参数属性共有42个，其中8个离散属性，33个连续属性。本文随机选取10万条无标签的原始网络连接记录作为训练集，其中入侵记录为2000条，随机选取各包含8万条数据的两个测试集，其中入侵数据都为1000条。
本文将模糊C-均值和基于单克隆的C-均值聚类算法作为比较算法。经30次独立实验，在平均的情况下检测结果如表1。其中，检测率为被检测出的异常样本数占异常样本总数的百分比；误警率为正常样本被识别为异常样本的数目占正常样本总数的百分比[4]。
从实验结果看，本文算法用于入侵检测，误警率和检测率较理想，这是因为采用了性能良好的聚类分析方法进行训练数据的学习，由此建立的正常模型具备较高的准确性。通过对比实验可以看出，理想的检测效果源于性能较好的聚类分析方法。
本文将多克隆规划作用于特定的亲和度函数来指导模糊C-均值聚类的过程。多克隆算法更多的继承了父代的特性，采用多克隆算子构造的无监督聚类算法利用多克隆算子对抗体进行交叉、变异和选择，将进化搜索与随机搜索、全局搜索和局部搜索相结合，提高了局部搜索和脱离局部极小值的能力，收敛速度更快。使得在聚类过程中，本文算法在保证候选解多样性的基础上，性能更为优越，尤其当数据量很大的时候，也能有效进行聚类分析。
5 小结
本文设计了一种基于多克隆算法和模糊C-均值聚类的入侵检测训练算法，该方法与数据分布无关，可以处理大规模、原始的、无标签数据集。实验证明，由该算法构造的检测系统能够有效的检测出网络入侵行为。
参考文献：
[1]蒋建春，马恒太，任党恩.网络安全入侵检测：研究综述[J].软件学报，2000，11（11）：1460-1466.
[2]Haifeng DU， Licheng JIAO， Sun'an Wang. Clonal Operator and Antibody Clone Algorithms. Proceedings of the First International Comference on Machine Learning and Cybernetics， Beijing， 4～5 November 2002：506-510.
[3]Jiawei Han等著，范明等译.数据挖掘概念与技术.机械工业出版社，2001，8.
[4]Leandro Nunes de Castro， Fenando J. Von Zuben. An Evolutionary Immune Network for Data Clustering. Proc. of the IEEE SBRN， 2000：84-89.
