李 佳

（江蘇食品藥品職業(yè)技術(shù)學(xué)院 信息工程系，江蘇 淮安223003）

0 引 言

特征選擇是在保持原有網(wǎng)絡(luò)數(shù)據(jù)信息完整性的基礎(chǔ)上，剔除無用或者冗余特征，以提高網(wǎng)絡(luò)入侵檢測效率，因此特征選擇成為網(wǎng)絡(luò)入侵檢測的核心問題［1－5］。

當(dāng)前網(wǎng)絡(luò)特征選擇方法主要采用隨機(jī)搜索算法和啟發(fā)式搜索算法，隨機(jī)搜索算法采用窮舉搜索策略，其計算量大，對于大規(guī)模數(shù)據(jù)集的特征選擇，運(yùn)行效率低，時間復(fù)雜度高，不能滿足網(wǎng)絡(luò)入侵檢測的實(shí)時性要求［6］；啟發(fā)式搜索算法具有搜索并行性，速度快等優(yōu)點(diǎn)，成為當(dāng)前網(wǎng)絡(luò)入侵檢測中的特征選擇算法，主要有模擬退火算法、蟻群算法、蛙跳算法、粒子群優(yōu)化算法、遺傳算法、雜草算法和等特征選擇方法［5－8］。但是在實(shí)際應(yīng)用中，這些算法均存在不同程度的缺陷，如遺傳算子概率設(shè)置沒有統(tǒng)一標(biāo)準(zhǔn)，尋優(yōu)結(jié)果極不穩(wěn)定；粒子群優(yōu)化算法易出現(xiàn) “早熟”現(xiàn)象，影響了網(wǎng)絡(luò)特征選擇的性能［9］。人工魚群算法 （artificial fish swarm algorithm，AFSA）是近幾年興起的一種智能優(yōu)化算法，具有并行性、收斂速度快等優(yōu)點(diǎn)，為了網(wǎng)絡(luò)入侵檢測過程中的特征選擇提供了新研究工具［10］。

通過上述分析，為了提高了網(wǎng)絡(luò)入侵檢測正確率和檢測效率，本文提出一種K近鄰算法 （KNN）和人工魚群算法選擇特征的網(wǎng)絡(luò)入侵檢測模型 （AFSA－KNN）。采用KNN算法根據(jù)特征之間的關(guān)聯(lián)度消除原始網(wǎng)絡(luò)數(shù)據(jù)中的冗余特征，使用AFSA對特征進(jìn)行搜索，并針對AFSA法的不足進(jìn)行改進(jìn)，從而得到最優(yōu)特征子集，最后建立網(wǎng)絡(luò)入侵檢測分類器，并進(jìn)行仿真測試，以驗(yàn)證AFSA－KNN的有效性。

1 KNN算法生成ASFA的初始解

由于入侵檢測數(shù)據(jù)的特征維數(shù)比較高，直接采用AFSA進(jìn)行選擇特征，效率低，為此首先采用KNN算法利用特征間的關(guān)聯(lián)性來消除高維網(wǎng)絡(luò)數(shù)據(jù)中的冗余特征，獲得AFSA的初始特征子集。

1.1 特征關(guān)聯(lián)性的度量

理想的網(wǎng)絡(luò)狀態(tài)特征應(yīng)該是表示該特征與網(wǎng)絡(luò)入侵行為相關(guān)，而與其它網(wǎng)絡(luò)特征無關(guān)，或者相關(guān)性比較小，當(dāng)前特征關(guān)聯(lián)性的度量方法主要為：信息理論法和線性關(guān)聯(lián)法，信息理論法主要有熵值法，線性關(guān)聯(lián)法主要有：Pearn積矩相關(guān)、線性關(guān)聯(lián)系數(shù)、最大信息壓縮和最小衰減誤差平方等，本文選擇最大信息壓縮度量特征之間的關(guān)聯(lián)度。假設(shè)2個網(wǎng)絡(luò)狀特征分別為：X和Y，那么最大信息壓縮指數(shù)計算公式為

式中：λ——相關(guān)系數(shù)，λ＝0時，表示X和Y線性相關(guān)。

1.2 KNN算法產(chǎn)生初始特征子集

K近鄰算法 （KNN）是一種基于統(tǒng)計的分類方法，根據(jù)式 （1）計算每個特征與它的第K個近鄰特征間最大信息壓縮指數(shù)λ值，然后根據(jù)λ值對特征進(jìn)行排序，保留λ值最小的網(wǎng)絡(luò)狀態(tài)特征，其余K個近鄰特征被刪除。在上述過程中，設(shè)置一個閾值ε，另一個值為上一次循環(huán)的λ值，在下面的循環(huán)中，將第K個近鄰的λ值與ε值進(jìn)行比較，如果λ＞ε，那么減小K的值［11］。

設(shè)原始網(wǎng)絡(luò)狀態(tài)特征數(shù)目為M，那么特征集可以表示為：O＝ ｛Fi，i＝1，2，…，M｝；消除冗余特征的網(wǎng)絡(luò)狀態(tài)特征子集為R；λ（Fi，F(xiàn)j）用于度量特征Fi和Fj之間關(guān)聯(lián)度；表示特征Fi與消除冗余特征子集R第K個近鄰特征的關(guān)聯(lián)度。KNN算法生成的初始特征子集具體步驟如下：

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

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

（3）找出Fi值最小的對應(yīng)的特征F′i，選擇F′i，將其K個最相近特征刪除，令ε＝。

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

（5）若K＝1，表示R中沒有特征和其近鄰的λ值小于ε了，那么就轉(zhuǎn)到步驟 （8）。

（8）選擇此時R中所有特征，并輸出R，得到人工魚算法的初始特征子集，有效去除冗余特。

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

2 ASFA的網(wǎng)絡(luò)特征子集選擇

2.1 人工魚群算法

人工魚群算法 （AFSA）是一種模仿魚群覓食行為的新型群智能算法，具有全局搜索能力強(qiáng)，速度快等優(yōu)點(diǎn)，人工魚群的幾種典型行為：覓食行為、聚群行為、追尾行為和隨機(jī)行為。

2.2 編碼規(guī)則

對于給定含有m維特征的網(wǎng)絡(luò)狀態(tài)數(shù)據(jù)集D，特征選擇的目的是選擇出一個滿足目標(biāo)函數(shù)最優(yōu)的特征子集R，本研究采用二進(jìn)制編碼規(guī)則，那么人工魚位置狀態(tài)x的每一維的值用二進(jìn)制表示，選中的特征取為1，否則為0。

2.3 食物密度

食物密度是人工魚位置優(yōu)劣的評價依據(jù)，即特征子集性能評價標(biāo)準(zhǔn)，入侵特征選擇目標(biāo)包括2個方面：①網(wǎng)絡(luò)入侵檢測率更高；②特征維數(shù)盡量最少，則目標(biāo)函數(shù) （食物密度）由所選特征子集的大小和檢測率兩部分組成。食物密度計算公式如下

式中：d——選取特征子集的維數(shù)；D——入侵檢測原始特征維數(shù)；Perror——5折交叉驗(yàn)證SVM訓(xùn)練模型的檢測率；λ——檢測正確率權(quán)重系數(shù)。

2.4 視野范圍

若視野范圍 （Fv）太小，易出現(xiàn)Fv內(nèi)里沒有人工魚伙伴，隨機(jī)性覓食概率太大，導(dǎo)致算法搜索盲目性增強(qiáng)，但是若Fv太大，聚群行為和追尾行為概率增大，不利于探索新的可行解空間區(qū)域。本研究通過人工魚狀態(tài)差異位的個數(shù)來表示2個狀態(tài)之間的相似程度。如果2個狀態(tài)間的相似度越高，表示人工魚位置間的差異就越小。人工魚當(dāng)前位置Xi的可見域Fv定義為

式中：xik——人工魚當(dāng)前位置Xi的第k維值，σk定義為

2.5 AFSA的特征選擇步驟

（1）收集網(wǎng)絡(luò)狀態(tài)信息，提取網(wǎng)絡(luò)狀態(tài)特征。

（2）采用0／1串位表示特征集，根據(jù)特征間的關(guān)聯(lián)度，采用KNN算法來消除原始特征集的冗余特征，得到了人工魚群算法的初始特征子集。

（3）初始化人工魚參數(shù)，主要有位置、移動步長Step、種群規(guī)模n、擁擠度因子δ、最大迭代次數(shù)max＿iterate等。

（4）在可行域范圍內(nèi)隨機(jī)生成n條人工魚，并設(shè)置初始迭代次數(shù)passed＿iterate＝0。

（5）對初始魚群的個體當(dāng)前位置食物濃度值 （FC）進(jìn)行計算，然后對它們進(jìn)行排序，選擇FC值最大的人工魚個體進(jìn)入公告板。

（6）評價某條人工魚的覓食、追尾和聚群行為所得的結(jié)果，若執(zhí)行某個行為后，人工魚的狀態(tài)優(yōu)于當(dāng)前狀態(tài)，則該人工魚向此方向前進(jìn)一步。

（7）更新公告牌，將最好人工魚狀態(tài)記入公告牌。

（8）判斷算法結(jié)束條件，如果達(dá)到最大迭代次數(shù)，則結(jié)束算法，并轉(zhuǎn)向步驟 （9），否則passed＿iterate＝passed＿iterate＋1，轉(zhuǎn)步驟 （6）執(zhí)行。

（9）公告牌中人工魚狀態(tài)為最優(yōu)特征子集。如圖2所示。

3 仿真實(shí)驗(yàn)

3.1 數(shù)據(jù)來源

為了測試AFSA－KNN特征選擇算法性能，在P4 3.0G CPU、4GRAM，Windows XP環(huán)境中，采用VC＋＋編程實(shí)現(xiàn)仿真實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)來自入侵檢測研究中的標(biāo)準(zhǔn)數(shù)據(jù)集－KDD CUP 99數(shù)據(jù)集［12］。該數(shù)據(jù)集包括9個星期的國空軍局域網(wǎng)絡(luò)連接數(shù)據(jù)，其中訓(xùn)練集包含500萬條記錄，測試集包含200萬條記錄，每一個記錄包含41個特征，具體見表1。由于KDDKDD CUP 99的數(shù)據(jù)量相當(dāng)龐大，為此，隨機(jī)從訓(xùn)練集與測試集中選擇部分?jǐn)?shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，不同類型入侵為數(shù)據(jù)見表2。

表1 KDD CUP 99的特征

?

3.2 特征值歸一化處理

由于網(wǎng)絡(luò)入侵特征多、變化范圍大，為了獲得更優(yōu)的入侵檢測效果，對特征值進(jìn)行歸一化處理，具體為

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

3.3 實(shí)驗(yàn)方案設(shè)計

為了對AFSA－KNN特征選擇方法的性能進(jìn)行全面、準(zhǔn)確地分析，采用支持向量機(jī)構(gòu)建網(wǎng)絡(luò)入侵分類器，設(shè)計了2種實(shí)驗(yàn)方案：

（1）首先采用AFSA－KNN對表2數(shù)據(jù)集的特征進(jìn)行選擇，得到對應(yīng)的網(wǎng)絡(luò)狀態(tài)特征子集，然后對訓(xùn)練集進(jìn)行學(xué)習(xí)，建立AFSA－KNN入侵檢測模型，同時采用全部41個特征建立入侵檢測模型，最后采用AFSA－KNN和全部41個特征的建立的入侵檢測模型對測試集的檢測時間和正確性能進(jìn)行分析。

（2）采用AFSA－KNN對表2數(shù)據(jù)集的特征進(jìn)行選擇，得到對應(yīng)的特征子集，并建立相應(yīng)的入侵檢測模型，然后采用人工魚群算法 （AFSA）、粒子群優(yōu)化算法 （PSO）、遺傳算法 （GA）對相同訓(xùn)練集進(jìn)行特征選擇，并建立應(yīng)的入侵檢測模型，最后3種入侵檢測模型對測試集的檢測時間和正確性能進(jìn)行分析和比較。

3.4 結(jié)果分析

3.4.1 與原始特征的性能比較

采用AFSA－KNN特征選擇方法對表2訓(xùn)練集進(jìn)行特征選擇，提到的特征子集見表3。從表3可知，采用AFSAKNN對原始特征進(jìn)行選擇后，大幅度降低了特征維數(shù)。針對每一種網(wǎng)絡(luò)入侵類型，采用表1中的特征子集和原始特征集建立相應(yīng)的入侵檢測模型，不同模型的檢測時間和正確率見表4。從表4中可知，相對于全部特征的入侵檢測模型，基于AFSA－KNN算法選擇特征的網(wǎng)絡(luò)入侵檢測的檢測時間大幅度降低，這主要是由于采用AFSA－KNN進(jìn)行特征選擇后，消除大量的冗余特征，減少了分類器輸入向量維數(shù)，計算時間復(fù)雜度降低，提高了網(wǎng)絡(luò)入侵檢測效率；同時網(wǎng)絡(luò)入侵檢測正確率得以明顯提高，這表明冗余特征會對網(wǎng)絡(luò)分類器的分類性能產(chǎn)生不利影響，導(dǎo)致全部特征的入侵檢測模型檢測正確率降，對網(wǎng)絡(luò)特征進(jìn)行是必須。

表3 AFSA－KNN算法選擇的特征子集

表4 特征選擇前后的網(wǎng)絡(luò)入侵檢測性能對比

3.4.2 與其它特征算法的性能比較

AFSA－KNN和其它特征算法的入侵檢測結(jié)果如圖3和圖4所示。對圖3和圖4的結(jié)果進(jìn)行分析，可以得到如下結(jié)論：

（1）相對于單一的AFSA，AFSA－KNN的網(wǎng)絡(luò)入侵檢測綜合性能明顯提升，這說明通過KNN對網(wǎng)絡(luò)入侵特征進(jìn)行聚類，消除冗余特征，得到了更優(yōu)的AFSA初始特征，這樣AFSA的尋優(yōu)目標(biāo)更加明確，迭代次數(shù)減少，減少了檢測時間，提高了網(wǎng)絡(luò)入侵檢測速度，同時AFSA－KNN找到了更優(yōu)的網(wǎng)絡(luò)特征子集，網(wǎng)絡(luò)入侵檢測正確率相應(yīng)得到提高。

（2）相對于GA、PSO算法，AFSA－KNN不僅提高了網(wǎng)絡(luò)入侵檢測正確率，同時檢測時間相應(yīng)減少，這表明采用AFSA－KNN可以獲得比GA、PSO算法更優(yōu)的特征子集，降低了計算時間復(fù)雜度，建立了性能更優(yōu)的網(wǎng)絡(luò)入侵檢測模型，可以滿足現(xiàn)代大規(guī)模、高維的網(wǎng)絡(luò)入侵檢測在線、實(shí)時要求。

4 結(jié)束語

本文為了提高網(wǎng)絡(luò)入侵檢測正確率和效率，提出一種AFSA－KNN選擇特征的網(wǎng)絡(luò)入侵檢測模型AFSA－KNN。首先計算特征之間的關(guān)聯(lián)度，采用KNN算法消除原始網(wǎng)絡(luò)數(shù)據(jù)中的冗余特征，然后得到的特征子集作為AFSA初始解，并通過模擬魚群的覓食、聚群及追尾行為找到最優(yōu)特征子集，最后建立網(wǎng)絡(luò)入侵檢測分類器，進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，AFSA－ANN在保證檢測準(zhǔn)確率的前提下，大幅度提高了入侵檢測效率，而且檢測速度和正確率均優(yōu)于現(xiàn)有特征選擇方法，可以滿足特征復(fù)雜多變的網(wǎng)絡(luò)入侵檢測。

［1］Tan F，F(xiàn)u 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］.計算機(jī)科學(xué)，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）.［張雪芹，顧春華.一種網(wǎng)絡(luò)入侵檢測特征提取方法 ［J］.華南理工大學(xué)學(xué)報 （自然科學(xué)版），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）.［郭文忠，陳國龍，陳慶良，等.基于粒子群優(yōu)化算法和相關(guān)性分析的特征子集選擇 ［J］.計算機(jī)科學(xué)，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）.［陳仕濤，陳國龍，郭文忠，等.基于粒子群優(yōu)化和鄰域約簡的入侵檢測日志數(shù)據(jù)特征選擇 ［J］.計算機(jī)研究與發(fā)展，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）.［陳友，程學(xué)旗，李洋，等.基于特征選擇的輕量級入侵檢測系統(tǒng) ［J］.軟件學(xué)報，2007，18 （7）：1639－1651.］