基于AFSA－KNN选择特征的网络入侵检测

李 佳

（江苏食品药品职业技术学院 信息工程系，江苏 淮安223003）

0 引 言

特征选择是在保持原有网络数据信息完整性的基础上，剔除无用或者冗余特征，以提高网络入侵检测效率，因此特征选择成为网络入侵检测的核心问题［1－5］。

当前网络特征选择方法主要采用随机搜索算法和启发式搜索算法，随机搜索算法采用穷举搜索策略，其计算量大，对于大规模数据集的特征选择，运行效率低，时间复杂度高，不能满足网络入侵检测的实时性要求［6］；启发式搜索算法具有搜索并行性，速度快等优点，成为当前网络入侵检测中的特征选择算法，主要有模拟退火算法、蚁群算法、蛙跳算法、粒子群优化算法、遗传算法、杂草算法和等特征选择方法［5－8］。但是在实际应用中，这些算法均存在不同程度的缺陷，如遗传算子概率设置没有统一标准，寻优结果极不稳定；粒子群优化算法易出现 “早熟”现象，影响了网络特征选择的性能［9］。人工鱼群算法 （artificial fish swarm algorithm，AFSA）是近几年兴起的一种智能优化算法，具有并行性、收敛速度快等优点，为了网络入侵检测过程中的特征选择提供了新研究工具［10］。

通过上述分析，为了提高了网络入侵检测正确率和检测效率，本文提出一种K近邻算法 （KNN）和人工鱼群算法选择特征的网络入侵检测模型 （AFSA－KNN）。采用KNN算法根据特征之间的关联度消除原始网络数据中的冗余特征，使用AFSA对特征进行搜索，并针对AFSA法的不足进行改进，从而得到最优特征子集，最后建立网络入侵检测分类器，并进行仿真测试，以验证AFSA－KNN的有效性。

1 KNN算法生成ASFA的初始解

由于入侵检测数据的特征维数比较高，直接采用AFSA进行选择特征，效率低，为此首先采用KNN算法利用特征间的关联性来消除高维网络数据中的冗余特征，获得AFSA的初始特征子集。

1.1 特征关联性的度量

理想的网络状态特征应该是表示该特征与网络入侵行为相关，而与其它网络特征无关，或者相关性比较小，当前特征关联性的度量方法主要为：信息理论法和线性关联法，信息理论法主要有熵值法，线性关联法主要有：Pearn积矩相关、线性关联系数、最大信息压缩和最小衰减误差平方等，本文选择最大信息压缩度量特征之间的关联度。假设2个网络状特征分别为：X和Y，那么最大信息压缩指数计算公式为

式中：λ——相关系数，λ＝0时，表示X和Y线性相关。

1.2 KNN算法产生初始特征子集

K近邻算法 （KNN）是一种基于统计的分类方法，根据式 （1）计算每个特征与它的第K个近邻特征间最大信息压缩指数λ值，然后根据λ值对特征进行排序，保留λ值最小的网络状态特征，其余K个近邻特征被删除。在上述过程中，设置一个阈值ε，另一个值为上一次循环的λ值，在下面的循环中，将第K个近邻的λ值与ε值进行比较，如果λ＞ε，那么减小K的值［11］。

设原始网络状态特征数目为M，那么特征集可以表示为：O＝ ｛Fi，i＝1，2，…，M｝；消除冗余特征的网络状态特征子集为R；λ（Fi，Fj）用于度量特征Fi和Fj之间关联度；表示特征Fi与消除冗余特征子集R第K个近邻特征的关联度。KNN算法生成的初始特征子集具体步骤如下：

（1）确定KNN算法的初始K值，初始化消除冗余特征子集R，使R＝O。

（2）计算特征子集R中的一个每个特征Fi的K＞cardinality（R）－1值。

（3）找出Fi值最小的对应的特征F′i，选择F′i，将其K个最相近特征删除，令ε＝。

（4）若有K＞cardinality（R）－1，那么K＝cardinality（R）－1。

（5）若K＝1，表示R中没有特征和其近邻的λ值小于ε了，那么就转到步骤 （8）。

（8）选择此时R中所有特征，并输出R，得到人工鱼算法的初始特征子集，有效去除冗余特。

综合上述可知，基于KNN算法生成AFSA的初始特征子集的流程如图1所示。

2 ASFA的网络特征子集选择

2.1 人工鱼群算法

人工鱼群算法 （AFSA）是一种模仿鱼群觅食行为的新型群智能算法，具有全局搜索能力强，速度快等优点，人工鱼群的几种典型行为：觅食行为、聚群行为、追尾行为和随机行为。

2.2 编码规则

对于给定含有m维特征的网络状态数据集D，特征选择的目的是选择出一个满足目标函数最优的特征子集R，本研究采用二进制编码规则，那么人工鱼位置状态x的每一维的值用二进制表示，选中的特征取为1，否则为0。

2.3 食物密度

食物密度是人工鱼位置优劣的评价依据，即特征子集性能评价标准，入侵特征选择目标包括2个方面：①网络入侵检测率更高；②特征维数尽量最少，则目标函数 （食物密度）由所选特征子集的大小和检测率两部分组成。食物密度计算公式如下

式中：d——选取特征子集的维数；D——入侵检测原始特征维数；Perror——5折交叉验证SVM训练模型的检测率；λ——检测正确率权重系数。

2.4 视野范围

若视野范围 （Fv）太小，易出现Fv内里没有人工鱼伙伴，随机性觅食概率太大，导致算法搜索盲目性增强，但是若Fv太大，聚群行为和追尾行为概率增大，不利于探索新的可行解空间区域。本研究通过人工鱼状态差异位的个数来表示2个状态之间的相似程度。如果2个状态间的相似度越高，表示人工鱼位置间的差异就越小。人工鱼当前位置Xi的可见域Fv定义为

式中：xik——人工鱼当前位置Xi的第k维值，σk定义为

2.5 AFSA的特征选择步骤

（1）收集网络状态信息，提取网络状态特征。

（2）采用0／1串位表示特征集，根据特征间的关联度，采用KNN算法来消除原始特征集的冗余特征，得到了人工鱼群算法的初始特征子集。

（3）初始化人工鱼参数，主要有位置、移动步长Step、种群规模n、拥挤度因子δ、最大迭代次数max＿iterate等。

（4）在可行域范围内随机生成n条人工鱼，并设置初始迭代次数passed＿iterate＝0。

（5）对初始鱼群的个体当前位置食物浓度值 （FC）进行计算，然后对它们进行排序，选择FC值最大的人工鱼个体进入公告板。

（6）评价某条人工鱼的觅食、追尾和聚群行为所得的结果，若执行某个行为后，人工鱼的状态优于当前状态，则该人工鱼向此方向前进一步。

（7）更新公告牌，将最好人工鱼状态记入公告牌。

（8）判断算法结束条件，如果达到最大迭代次数，则结束算法，并转向步骤 （9），否则passed＿iterate＝passed＿iterate＋1，转步骤 （6）执行。

（9）公告牌中人工鱼状态为最优特征子集。如图2所示。

3 仿真实验

3.1 数据来源

为了测试AFSA－KNN特征选择算法性能，在P4 3.0G CPU、4GRAM，Windows XP环境中，采用VC＋＋编程实现仿真实验，实验数据来自入侵检测研究中的标准数据集－KDD CUP 99数据集［12］。该数据集包括9个星期的国空军局域网络连接数据，其中训练集包含500万条记录，测试集包含200万条记录，每一个记录包含41个特征，具体见表1。由于KDDKDD CUP 99的数据量相当庞大，为此，随机从训练集与测试集中选择部分数据进行仿真实验，不同类型入侵为数据见表2。

表1 KDD CUP 99的特征

?

3.2 特征值归一化处理

由于网络入侵特征多、变化范围大，为了获得更优的入侵检测效果，对特征值进行归一化处理，具体为

式中：xi、x′i——原始和归一化后的特征值，max（xi）——特征xi的最大值。

3.3 实验方案设计

为了对AFSA－KNN特征选择方法的性能进行全面、准确地分析，采用支持向量机构建网络入侵分类器，设计了2种实验方案：

（1）首先采用AFSA－KNN对表2数据集的特征进行选择，得到对应的网络状态特征子集，然后对训练集进行学习，建立AFSA－KNN入侵检测模型，同时采用全部41个特征建立入侵检测模型，最后采用AFSA－KNN和全部41个特征的建立的入侵检测模型对测试集的检测时间和正确性能进行分析。

（2）采用AFSA－KNN对表2数据集的特征进行选择，得到对应的特征子集，并建立相应的入侵检测模型，然后采用人工鱼群算法 （AFSA）、粒子群优化算法 （PSO）、遗传算法 （GA）对相同训练集进行特征选择，并建立应的入侵检测模型，最后3种入侵检测模型对测试集的检测时间和正确性能进行分析和比较。

3.4 结果分析

3.4.1 与原始特征的性能比较

采用AFSA－KNN特征选择方法对表2训练集进行特征选择，提到的特征子集见表3。从表3可知，采用AFSAKNN对原始特征进行选择后，大幅度降低了特征维数。针对每一种网络入侵类型，采用表1中的特征子集和原始特征集建立相应的入侵检测模型，不同模型的检测时间和正确率见表4。从表4中可知，相对于全部特征的入侵检测模型，基于AFSA－KNN算法选择特征的网络入侵检测的检测时间大幅度降低，这主要是由于采用AFSA－KNN进行特征选择后，消除大量的冗余特征，减少了分类器输入向量维数，计算时间复杂度降低，提高了网络入侵检测效率；同时网络入侵检测正确率得以明显提高，这表明冗余特征会对网络分类器的分类性能产生不利影响，导致全部特征的入侵检测模型检测正确率降，对网络特征进行是必须。

表3 AFSA－KNN算法选择的特征子集

表4 特征选择前后的网络入侵检测性能对比

3.4.2 与其它特征算法的性能比较

AFSA－KNN和其它特征算法的入侵检测结果如图3和图4所示。对图3和图4的结果进行分析，可以得到如下结论：

（1）相对于单一的AFSA，AFSA－KNN的网络入侵检测综合性能明显提升，这说明通过KNN对网络入侵特征进行聚类，消除冗余特征，得到了更优的AFSA初始特征，这样AFSA的寻优目标更加明确，迭代次数减少，减少了检测时间，提高了网络入侵检测速度，同时AFSA－KNN找到了更优的网络特征子集，网络入侵检测正确率相应得到提高。

（2）相对于GA、PSO算法，AFSA－KNN不仅提高了网络入侵检测正确率，同时检测时间相应减少，这表明采用AFSA－KNN可以获得比GA、PSO算法更优的特征子集，降低了计算时间复杂度，建立了性能更优的网络入侵检测模型，可以满足现代大规模、高维的网络入侵检测在线、实时要求。

4 结束语

本文为了提高网络入侵检测正确率和效率，提出一种AFSA－KNN选择特征的网络入侵检测模型AFSA－KNN。首先计算特征之间的关联度，采用KNN算法消除原始网络数据中的冗余特征，然后得到的特征子集作为AFSA初始解，并通过模拟鱼群的觅食、聚群及追尾行为找到最优特征子集，最后建立网络入侵检测分类器，进行了仿真实验。实验结果表明，AFSA－ANN在保证检测准确率的前提下，大幅度提高了入侵检测效率，而且检测速度和正确率均优于现有特征选择方法，可以满足特征复杂多变的网络入侵检测。

［1］Tan F，Fu X Z，Zhang Y Q，et al.A genetic algorithm－based method for feature subset selection ［J］.Soft Computing，2008，12 （2）：111－120.

［2］JING Xiaopei，WANG Houxiang，NIE Kai，et al.Feature selection algorithm based on IMGA and MKSVM to intrusion detection ［J］.Computer Science，2007，18 （7）：1639－1651（in Chinese）.［井小沛，汪厚祥，聂凯，等.面向入侵检测的基于IMGA和 MKSVM的特征选择算法 ［J］.计算机科学，2012，39 （7）：96－100.］

［3］Hu W M，Hu M，Maybank S.Adaboost based algorithm for network intrusion detection ［J］.IEEE Transactions on Systems，Man and Cybernetic，Parb B：Cybernetics，2008，38（2）：577－583.

［4］Denning D E.An intrusion detection model［J］.IEEE Transaction on Software Engineering，2010，13 （2）：222－232.

［5］Hang C L，Wang C J.A GA－based feature selection and parameters optimization for support vector machines ［J］.Expert Systems with Applications，2009，31 （2）：231－240.

［6］Khan L，Awad M，Thuraisingham B.A new intrusion detection system using support vector machines and hierarchical clustering ［J］.The VLDB Journal，2007，16 （4）：507－521.

［7］ZHANG Xueqin，GU Chunhua.Vision－based inspection algorithm for chip components ［J］.Journal of South China University of Technology （Natural Science Edition），2010，38 （1）：81－86（in Chinese）.［张雪芹，顾春华.一种网络入侵检测特征提取方法 ［J］.华南理工大学学报 （自然科学版），2010，38 （1）：81－85.］

［8］GUO Wenzhong，CHEN Guolong，CHEN Qingliang，et al.Feature subset selection based on particle swarm optimization algorithm and relevance analysis ［J］.Journal of Computer Science，2008，35 （2）：144－146 （in Chinese）.［郭文忠，陈国龙，陈庆良，等.基于粒子群优化算法和相关性分析的特征子集选择 ［J］.计算机科学，2008，35 （2）：144－146.］

［9］Kim D S，Nguyen H N，Ohn SY.et al.Fusions of GA and SVM for anomaly detection in intrusion detection system ［J］.Advances in Neural Networks，2009，10 （1）：415－420.

［10］Gao YF，Chen YD.The optimization of water utilization based on artificial fish－swarm algorithm ［C］／／Sixth International Conference on Natural Computation，2010：4415－4419.

［11］CHEN Shitao，CHEN Guolong，GUO Wenzhong，et al.Feature selection of the intrusion detection data based on particle swarm optimization and neighborhood reduction ［J］.Journal of Computer Research and Development，2010，47（7）：1261－1267 （in Chinese）.［陈仕涛，陈国龙，郭文忠，等.基于粒子群优化和邻域约简的入侵检测日志数据特征选择 ［J］.计算机研究与发展，2010，47 （7）：1261－1267.］

［12］CHEN You，CHENG Xueqi，LI Yang，et al.Lightweight intrusion detection system based on feature selection ［J］.Journal of Software，2007，18 （7）：1639－1651 （in Chinese）.［陈友，程学旗，李洋，等.基于特征选择的轻量级入侵检测系统 ［J］.软件学报，2007，18 （7）：1639－1651.］