基于萤火虫群算法的网络入侵优化检测算法

周丽娟，于雪晶，魏 卓

基于萤火虫群算法的网络入侵优化检测算法

周丽娟1，于雪晶1，魏 卓2

（1.长春工业大学信息传播工程学院，长春130012；2.长春工程学院计算机技术与工程学院，长春130012）

针对模糊C-均值聚类法因对初始聚类中心敏感且容易陷入局部极小值而导致无法在网络入侵检测中获得精确分类结果的问题，提出了基于萤火虫群优化（GSO：Glowworm Swarm Optimization）算法的网络入侵检测方法。采用标记样本得到初始聚类中心，运用萤火虫群优化实现对聚类中心的优化。结果显示该方法有效。

萤火虫群优化算法；网络入侵；模糊C-均值聚类；半监督

0 引言

随着网络技术的高速发展，网络规模不断扩大、功能日趋强大，其用户数量持续增加，为人们的生活带来极大便利，但同时也为各类网络入侵制造了越来越多的漏洞，为网络安全带来了极大的挑战。快速发现各类入侵行为、确保网络安全已成为各国学者讨论的热点问题。

网络入侵检测技术可分为误用检测和异常检测技术。误用检测技术是用来训练一个带有标记样本的分类器，然后运用受过良好训练的分类器识别网络入侵，此种算法存在的问题在于训练的可获得性以及学习过程需要预先识别大量的标记样本。异常检测技术是一种不需要大量标记样本且能实现攻击类型自动分类的算法［1-3］。

通常，机器学习算法可分为监督学习算法、无监督学习算法和半监督学习算法。根据监督学习的设计原理，假定存在一些数据输入和相关输出，机器在此过程中学习一种映射函数，以使其具备预测新数据样本输出的功能。在非监督学习过程中仅有一些数据输入，但不存在任何来自监督信息的引导，此过程旨在设计一些算法，以便开发隐藏在数据之中的各类属性。半监督算法是近年来问世的一种新的聚类算法，是近年来机器学习与模式识别领域的一个重要研究方向。该算法结合了无监督学习和监督学习的优势，实现了聚类质量的提升。基于监督学习的异常检测算法需要大量带有标记数据的类别信息，人们需要付出巨大的努力才能获得此类数据，因此，其应用相对受限。然而，基于无监督学习的异常检测算法根据数据的相似性对其进行分组，能克服监督学习在标记样本数据不足的缺陷。但是，该算法的检测精度明显次于监督检测。在实际应用过程中，半监督聚类仅需获得少量的标记样本数据，因此，其优越性十分明显。

笔者提出了一种基于萤火虫算法的原创半监督模糊C-均值入侵检测优化算法。模糊C-均值聚类算法旨在将样本映射到运用FCM算法进行聚类分析的特征空间。该方法能在一定程度上去除噪声敏感性和杂乱数据并确保分布在不同形状之中的数据的准确聚类，且不依赖数据内在形状分布并能提高算法鲁棒性。但是，FCM的聚类性能依赖于对初始聚类中心的选择且倾向于局部最优。因此，笔者采用经过萤火虫算法优化的FCM算法聚类中心。运用少量标记样本进行监督聚类，以便获得初始聚类中心。同时运用经过萤火虫算法优化的模糊C-均值聚类算法对未标记样本进行分类，在此过程中采用初始聚类中心作为聚类中心。

1 萤火虫算法概述

1.1 萤火虫算法的原理

自然界中存在大约2 000多种萤火虫，其中，大多数种类的萤火虫均能出于不同的目的发出短暂的荧光，但它们发光的原因目前还没有研究清楚。人们基本认同成年萤火虫发光的生物学功能是通过自身发出的独特荧光信号寻找和吸引异性，从而实现交配和繁殖。此外，也有一些种类的萤火虫利用荧光捕食。荧光的另一个作用是作为警告信号，即萤火虫可在遭遇危险时发出荧光。萤火虫群优化算法是一种基于模拟萤火虫在自然界中发光过程的随机优化算法。该算法不考虑萤火虫发光的生物学功能，而仅考虑其在运用荧光寻找配偶、向处于附近最佳位置的萤火虫移动过程中发出荧光的特点。

萤火虫群优化（GSO：Glowworm Swarm Optimization）算法模拟了萤火虫在自然界中的求偶仪式并凭借其高搜索速度和搜索效率而得到广泛关注。目前，该算法已被证明在最优化问题领域（如路径规划、最优化问题等）具有良好的应用效果。

根据萤火虫算法，在目标函数的解空间内对一个萤火虫群进行随机初始化，且该萤火虫群中的每只萤火虫均有一定数量的荧光素，其数值取决于萤火虫所处的位置。萤火虫所处的位置越好，该位置对应的适合度值越高，荧光素阈值越大。同时，荧光素阈值决定了萤火虫发出荧光的强度。荧光的强度越高，萤火虫对周围同类的吸引力越强。某只萤火虫对其他萤火虫的吸引力称为决策方位或领地范围（用rd表示）。只有在i号萤火虫进入j号萤火虫的领地范围内的情况下，j号萤火虫才对i号萤火虫具有吸引力。由于相互吸引，萤火虫会为了实现最优化而奔向相对优于其他萤火虫的那只［4-6］。

可通过两个步骤实现萤火虫算法：荧光素更新和萤火虫的追随运动。

当某只萤火虫需要更新其荧光素时，可通过一种持续的方式实现此类更新。荧光素更新公式为

其中ρ和γ为荧光素控制参数，其区间值在［0，1］之间；l为萤火虫的荧光素阈值；f（xi（t））为每只萤火虫的适合度阈值。

i号萤火虫在一定的概率下会追随j号萤火虫移动可表示为

在i号萤火虫追随j号萤火虫的过程中，i号萤火虫的位置随时发生变化。位置更新公式如下

其中xi（t）为i号萤火虫的位置，s为萤火虫的更新后步长。

1.2 算法改进

为加强算法的优化能力，笔者对萤火虫的交配行为进行模拟，以实现对基本GSO的改进。人们通过观察得知，在交配时节，一只雌性萤火虫周围会存在数只雄性萤火虫等待交配，而雌性萤火虫会选择亮度最高、发光时间最长的萤火虫。假设具有最多荧光素的那只萤火虫为雌性、等待与一只雌性萤火虫交配的雄性萤火虫的数量为m、一只雌性萤火虫会与m只雄性萤火虫交配，则可对萤火虫的交配过程进行模拟。萤火虫交配算法与遗传算法的交叉算法类似公式如下

其中xi为雌性萤火虫；xj为雄性萤火虫；α取值在［0，1］之间。

如果一只雌性萤火虫与m只雄性萤火虫交配，有m只雄性萤火虫已经与一只雌性萤火虫交配，则只有最佳的一只萤火虫可以得到保留，其他萤火虫则被抛弃。

1.3 混沌初始化

混沌是在自然界大多数非线性系统中常见的一种非线性现象。混沌现象是在完全确定的系统（不存在任何额外的随机因素）中表现的一种介于规则与随机之间的类随机行为。混沌现象具有独特的性质。

1）随机性。

2）遍历性。其可在一定的范围内根据自身规律以不重复的方式经历所有的状态。

3）规则性。毫无疑问，运用混沌变量进行最优搜索是一种较优的方法。正是遍历性使其免于在搜索过程中限于局部最优并使其成为一种提升全局收敛能力的机制。

混沌搜索通常采用逻辑函数

其中μ为控制参数。当μ=4时，0≤z0≤1，逻辑完全处于混沌状态下。

1.4 萤火虫算法流程

综上所述，萤火虫算法的流程如下。

第1步：算法参数初始化。

第2步：根据式（5）对萤火虫位置进行混沌初始化、计算萤火虫的目标函数值并以此作为萤火虫各自的荧光亮度l。

第3步：根据式（1）计算萤火虫的追随概率。

第4步：通过式（3）更新萤火虫的空间位置并对处于最佳位置的萤火虫实施随机扰动。

第5步：根据萤火虫的更新位置重新计算萤火虫的荧光亮度。

第6步：如果搜索精度能满足要求或已达到最大搜索次数，则进行第7步，否则，搜索次数加1并回到第3步进行再次搜索。

第7步：输出全局极值和最优值。

2 模糊C-均值聚类

2.1 算法原理

模糊聚类算法是一种基于函数最优法、通过微积分计算技术求得最优代价函数的算法。当概率密度函数用于基于概率算法的聚类方法中时，假设存在一个适当的模型且模糊聚类算法的矢量同时属于多个群集，则上述问题即可获得解决。模糊聚类算法需要在矢量与群集之间定义一个近邻函数，且各群集中矢量的隶属关系是由隶属度函数集赋予的。从模糊法的角度而言，不同群集中矢量的隶属度函数值存在关联。硬聚类可被视为模糊聚类方法中的一个特例。

假设样本集为X=｛x1，x2，…，xn｝。模糊C-均值聚类算法将该样本集分为c个模糊群并计算各模糊群的聚类中心cj（j=1，2，…，C），以实现对算法目标函数的最小化

其中 JC是基于样本 C的代价函数，uij是指 i号数据点对 j号聚类中心的隶属度；cj是指j号模糊聚类中心，其初始值是从训练样本集中随机选出的；α代表模糊性。模糊隶属度与α成正比例关系。计算模糊隶属度uij和聚类中心cj公式如下

n n

FCM聚类过程从一个随机聚类中心开始，并通过搜索目标函数的极小点不断调整聚类中心和每个样本的模糊隶属度，以实现样本分类的最终目标。

2.2 算法改进

在FCM算法中，由于隶属度uij需要归一化，因此，在不良样本集基础上得到的结果很可能并不理想。如果样本点远离各个聚类中心，则其对各群集的隶属度很小。但由于归一化的要求，样本点对各群集的隶属度需要提高，进而导致不理想的迭代结果。为了放宽归一化条件，令每个样本对各群集的隶属度之和为n，如下所示

在新隶属度函数的条件下，隶属度函数

式（10）显然并非一般意义上的隶属度函数，且其区间并非限于小于1的范围内。如必要，可根据公式

最终获得隶属度函数。

凭借经过改进的隶属度，FCM算法即使在存在孤立点的情况下仍然能实现良好的聚类效果。而且，由于归一化条件的放宽，最终的聚类结果对预定义的聚类数并不十分敏感。

3 基于萤火虫算法的入侵检测

3.1 对萤火虫进行编码

所有聚类中心均包含在每只萤火虫的编码中。假设存在K个聚类中心、每个聚类中心的维数为S、每只萤火虫均是维度K×S中的一部分，表示如下

其中cpk为p号萤火虫的k号聚类中心。

3.2 适合度值

每只萤火虫对应一个适合度值，即FCM算法的目标函数。

3.3 算法流程

笔者采用了基于萤火虫优化的半监督聚类算法。算法输入数据包含n个标记数据集和m个未标记数据集，且n≪m。

算法包含两个程序：1）在监督下使用少量标记样本进行聚类，以便得到初始聚类中心；2）通过萤火虫算法对聚类中心进行优化。该程序包括下列步骤：

①根据在程序1）中得到的聚类中心Ok在数据集Cr中生成一个初始隶属度矩阵，并在Ok周围初始化一个萤火虫群；

②对初始模糊C-均值聚类中心的每只萤火虫进行模糊C-均值聚类，并根据最终聚类结果计算每只萤火虫的适合度值；

③追随萤火虫的交配行为和萤火虫群的更新；

④计算更新后的萤火虫群的适合度值；

⑤判断算法是否满足最终要求。如果不满足要求，则返回②。

4 仿真实验

4.1 实验数据

笔者采用KDD CUp99网络攻击数据集验证萤火虫算法的有效性。从数据集中抽取5种类型的数据，分别为Dos、U2R、probe、R2L攻击模式和正常模式数据。实验采用的数据集共有41种特性。由于其中一些数据为冗余数据，因此，仅选取21种能反映用户行为的数据作为研究对象，如Duration（持续时间）、Service（服务）、protocol type（协议类型）和Flag（标记）等。

为了满足检测算法的假设条件，从全部检测数据集中选取4组数据进行试验，每组数据包含117 489条记录。其中116 001条记录为正常数据，1 488条为入侵数据。由于正常数据在每个实验组中所占的比例为99%，因此，满足检测算法中的正常数据远大于入侵数据的假定条件。

4.2 仿真实验与分析

检出率和误报率可用于测试入侵算法的性能。检出率是指被检出的入侵检测样本数量在此类样本总数中所占的比例，误报率是指误报为入侵样本的正常样本数量在正常样本总数中所占的比例。在萤火虫算法中，设群数参数为100，迭代数为250。4组数据的入侵检测结果如表1和表2所示。

表1 检出率测试结果Tab.1 The test results of DR

表2 误报率测试结果Tab.2 The test result of FpR

测试结果表明，萤火虫算法在最优化方面表现良好，能有效提高FCM算法的聚类结果，因而能有效提升检出率、降低误报率。

5结 语

FCM算法易于使用且适用于聚类问题，但该算法容易陷入局部最优，在聚类结果方面表现不佳。笔者提出了萤火虫算法及其在网络入侵方面的应用。通过基于萤火虫算法和半监督聚类的优化，算法的聚类特性已经得到有效提升。仿真实验表明，基于萤火虫算法优化的半监督FCM算法可更好地应用于网络入侵检测，为解决网络入侵问题提供了一种新的思路。

［1］龚俭，陆晟.大规模互联网络的入侵检测［J］.东南大学学报：自然科学版，2002，32（3）：325-330. GONG Jian，LU Sheng.Intrusion Detection in Large-Scale Network［J］.Journal of Southeast University：Natural Science Edition，2002，32（3）：325-330.

［2］吴斌，崔志勇，倪卫红.具有混合群智能行为的萤火虫群优化算法研究［J］.计算机科学，2012（5）：198-200. WU Bin，CUIZhiyong，NIWeihong.Research on Glowworm Swarm Optimization with Hybird Swarm Intelligence Behavior［J］.Computer Science，2012（5）：198-200.

［3］胡亮，康健，赵阔，等.入侵检测系统［J］.吉林大学学报：信息科学版，2002，20（4）：46-47.HU Liang，KANG Jian，ZHAO Kuo，et al.Intrusion Detection Systems［J］.Journal of Jilin University：Information Science Edition，2002，20（4）：46-47.

［4］陈丹瑜，许勇，吴国新.入侵检测系统系统性能参数的仿真法分析［J］.计算机工程与应用，2004，40（7）：139-141. CHEN Danyu，XU Yong，WU Guoxin.Simulation performance Analysis of Intrusion Detection System［J］.Computer Engineering and Applications，2004，40（7）：139-141.

［5］王艳青，郑永凡，王玉.入侵检测系统评估仿真平台的研究［J］.辽宁大学学报：自然科学版，2009，36（1）：49-51. WANG Yanqing，ZHENG Yongfan，WANG Yu.The Research of Simulation p latform for Testing Intrusion Detection System［J］.Journal of Liaoning University：Natural Science Edition，2009，36（1）：49-51.

［6］吕志军，金毅，赖海光，等.DApRA测试分析和IDS测试方法研究［J］.计算机科学，2004，31（11）：73-76. LÜZhijun，JIN Yi，LAIHaiguang，et al.Analysis of DARpA Testand Research of IDSTestMethod［J］.Computer Science，2004，31（11）：73-76.

（责任编辑：刘东亮）

Optimized Detection Algorithm for Network Intrusion Based on the Glowworm Swarm Algorithm

ZHOU Lijuan1，YU Xuejing1，WEIZhuo2

（1.College of Information Dissemination Engineering，Changchun University of Technology，Changchun 130012，China；2.School of Computer Technology and Engineering，Changchun Institute of Technology，Changchun 130012，China）

Because fuzzy C-means clusteringmethod is sensitive to initial cluster centers and easily trapped into localminima，we can't get precise classification result in network intrusion detection.To solve the problem，a network intrusion detectionmethod based on GSO（Glowworm Swarm Optimization）algorithm is proposed.First，sampleswith label is used to get initial cluster center.Then，GSO is employed to optimize cluster center. Simulation result shows that themethod is effective.

glowworm swarm optimization（GSO）algorithm；network intrusion；fuzzy C-means clustering；semi-supervised

Tp301

A

1671-5896（2015）03-0338-06

2015-04-02

周丽娟（1971— ），女，吉林白山人，长春工业大学副教授，主要从事软件开发和人工智能研究，（Tel）86-13604304528（E-mail）wanglijun@ccut.edu.cn。