改進的粒子群算法在入侵檢測中的應用

牛永潔

（延安大學 數(shù)學與計算機學院，陜西 延安 716000）

改進的粒子群算法在入侵檢測中的應用

牛永潔

（延安大學 數(shù)學與計算機學院，陜西 延安 716000）

為了提高入侵檢測系統(tǒng)的檢測率和降低系統(tǒng)的誤檢率，對基本的粒子群算法采用在粒子群初始化階段，種群的離散度必須滿足一定的要求才能開始迭代；在算法迭代過程中，慣性權(quán)重、加速系數(shù)的調(diào)整都與當前粒子群的離散度相關(guān)；當種群的離散度小于一定數(shù)值時，進行保優(yōu)重初始化，同時采用適應度函數(shù)拉伸操作，重新迭代等幾個方面的改進。經(jīng)過KDD Cup 1999數(shù)據(jù)集的訓練和檢驗數(shù)據(jù)的仿真測試，改進后的粒子群算法具有較高的檢測正確率和較低的誤檢率，而且新算法收斂速度快，不易局部最優(yōu)。

入侵檢測；粒子群算法；離散度；適應度函數(shù)；拉伸

目前，計算機網(wǎng)絡(luò)已經(jīng)滲透到人們工作、生活的各個方面，特別是“互聯(lián)網(wǎng)+”的興起，使計算機網(wǎng)絡(luò)成為經(jīng)濟騰飛的另一個重要契機。同時，越來越多的個人隱私信息和敏感信息在網(wǎng)絡(luò)中傳輸。如何保證這些信息的安全性？為社會的發(fā)展提供一個干凈的網(wǎng)絡(luò)環(huán)境，網(wǎng)絡(luò)安全問題越來越受到人們的重視，同時網(wǎng)絡(luò)攻擊的形式也不斷的多樣化，用戶的計算機系統(tǒng)隨時都會被未知的網(wǎng)絡(luò)攻擊方法攻擊。

入侵檢測系統(tǒng)（Intrusion Detection System，IDS）是一種能夠主動發(fā)現(xiàn)進入系統(tǒng)非正常行為的技術(shù)。相對其他安全措施而言，入侵檢測系統(tǒng)具有主動性與識別新攻擊方法的優(yōu)點。在IDS系統(tǒng)中，通過在計算機系統(tǒng)關(guān)鍵點位置或者網(wǎng)絡(luò)流量的關(guān)鍵路徑上進行信息的收集、整理、分析，從中判斷系統(tǒng)是否被入侵，一旦發(fā)現(xiàn)被入侵事件，及時采取相應的防護措施。入侵檢測系統(tǒng)是一種主動防御的系統(tǒng)，其技術(shù)的核心是對收集的數(shù)據(jù)進行分析，判斷出正常行為和非正常行為［1］。

入侵檢測的原理是對流經(jīng)計算機系統(tǒng)的數(shù)據(jù)包進行抓取和數(shù)據(jù)清洗，然后使用合適的數(shù)據(jù)分析算法，判斷出數(shù)據(jù)包屬于正常或者非正常數(shù)據(jù)，針對非正常的數(shù)據(jù)采取報警或者其他的措施對用戶進行警告或者提示。所以對數(shù)據(jù)包進行分析，用來分辨數(shù)據(jù)是否正常的算法是入侵檢測系統(tǒng)的核心。

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）由美國的Kennedy和Eberhart基于對鳥群社會系統(tǒng)研究中得到的啟發(fā)，在1995年提出［2］。粒子群優(yōu)化算法因為具有深刻的智能背景，與遺傳算法相比原理更加直觀、實現(xiàn)簡單并且優(yōu)化速度及精度都有一定的提高。所以一提出立即引起演化計算領(lǐng)域?qū)W者的廣泛關(guān)注，在短時間內(nèi)涌現(xiàn)出大量的研究成果，形成了一個研究熱點。而且在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓練、工程系統(tǒng)優(yōu)化、入侵檢測等領(lǐng)域得到廣泛應用［3-8］。

文中首先闡述了入侵檢測的基本概念，然后簡要介紹了基本PSO，分析了基本PSO的優(yōu)點與不足。針對這些優(yōu)點與不足，對基本PSO進行了兩個方面的改進，提出基于“離散度”的種群初始化方法，又結(jié)合“拉伸”技術(shù)對算法迭代過程中的適應度函數(shù)進行放大處理，這些改進措施很好的解決了收斂速度與局部最優(yōu)的問題［9-10］。通過在KDD Cup 1999網(wǎng)絡(luò)數(shù)據(jù)集上的實驗仿真，發(fā)現(xiàn)效果良好。

1 入侵檢測

入侵是指試圖破壞資源的完整性、機密性以及可用性的活動的集合。入侵檢測系統(tǒng)（IDS）是通過監(jiān)視和檢測數(shù)據(jù)的通信或用戶的行為來證明是否有入侵的系統(tǒng)［11-15］。根據(jù)檢測方法的不同，有兩種基本的檢測方法:誤用檢測（misuse detection）和異常檢測（anomaly detection）。

誤用檢測使用已知的攻擊模式或系統(tǒng)弱點來進行攻擊識別。異常檢測主要是利用大量主機的日志信息或網(wǎng)絡(luò)流量中的特征數(shù)據(jù)來建立系統(tǒng)正常運行情況下的模式。然后，以此為依據(jù)，任何對正常情況的偏離都認為是異常。IDS根據(jù)偵聽策略可分為基于網(wǎng)絡(luò)的IDS和基于主機的IDS。前者利用網(wǎng)絡(luò)偵聽技術(shù)收集網(wǎng)絡(luò)上傳輸?shù)臄?shù)據(jù)包，并對數(shù)據(jù)包信息進行解讀，從中發(fā)現(xiàn)異常的行為?；谥鳈C的IDS：其輸入數(shù)據(jù)來源主要是主機系統(tǒng)和系統(tǒng)本地用戶的審計數(shù)據(jù)和系統(tǒng)的日志。

入侵檢測系統(tǒng)是通過監(jiān)視和檢測數(shù)據(jù)的通信或用戶的行為來證明是否有入侵的系統(tǒng)。本文采用的入侵檢測系統(tǒng)采用基于網(wǎng)絡(luò)的IDS，其基本的工作原理如圖1所示。

圖1 入侵檢測的基本原理

入侵檢測的第一步是進行數(shù)據(jù)采集，對數(shù)據(jù)的采集使用一種叫嗅探器的工具。嗅探器有硬件和軟件兩種實現(xiàn)方式。硬件網(wǎng)絡(luò)嗅探器靈活性比較差、但是其性能高而且價格比較昂貴。軟件網(wǎng)絡(luò)嗅探器具有實現(xiàn)方便、布置靈活和成本低的優(yōu)勢。不同的軟件版本需要不同的平臺支持，比較常見的嗅探器有：Linux系統(tǒng)下的 Tcpdump、HP-UX系統(tǒng)平臺下的NfSwatch和 Windows系 統(tǒng) 平 臺 下 的 lpman、FoxSniffe、Wireshark、WinPcap等。SharpPcap是一個.NET環(huán)境下的網(wǎng)絡(luò)包捕獲框架，基于著名的WinPcap庫開發(fā)。提供了捕獲、注入、分析和構(gòu)建的功能，適用于.NET開發(fā)語言。本文對數(shù)據(jù)包的抓取基于SharpPcap庫進行。

對抓取的數(shù)據(jù)包進行數(shù)據(jù)預處理的過程主要包含3個步驟，它們分別是降維、數(shù)字化、標準化。由于抓取的數(shù)據(jù)包一般維數(shù)比較大大，為了減少后續(xù)算法的運算量，同時還不能影響算法的準確度，文中采用主成分分析（Principal Component Analysis，PCA）方法對網(wǎng)絡(luò)數(shù)據(jù)包進行降維處理。由于在抓取的網(wǎng)絡(luò)數(shù)據(jù)包中含有很多文本屬性用來描述每條記錄，如為了表示網(wǎng)絡(luò)連接類型的不同，會對記錄的連接類型標記為TCP、UDP等類型，為了能夠進行很好的數(shù)據(jù)分析，需要對文本字符進行變換，變換為數(shù)值。最后由于每條記錄的屬性量綱不同，為了消除量綱不同的影響，需要對數(shù)據(jù)進行標準化處理。數(shù)據(jù)的標準化采用公式（1）、（2）進行。

其中xij表示第i行第j列的一個標量數(shù)據(jù)，表示第j列的算術(shù)平均值，而Sj表示第j列的標準方差，而表示經(jīng)過數(shù)據(jù)標準化處理后的新數(shù)據(jù)。經(jīng)過數(shù)據(jù)標準化處理消除了量綱的影響。

2 粒子群算法的改進

2.1 基本粒子群算法

標準粒子群算法描述如下：在D維的目標搜索空間中，由N個粒子組成一個群體，稱為種群。其中第i個粒子是一個D維的向量Xi=（xi1，xi2，…，xiD），i=1，2，…，N，每個粒子都代表搜索空間中一個潛在的可行解?？尚薪獾闹涤蛇m應度函數(shù)計算得出。種群中的每個粒子在搜索空間中按照一定的速度、方向運動，每到達一個新的位置，用適應度函數(shù)對粒子進行優(yōu)劣評價，根據(jù)適應度值的優(yōu)劣決定粒子下一步運動速度的大小與方向。因此，粒子速度、位置的更新是算法的驅(qū)動力，根據(jù)速度、位置更新的原理不同，可以將粒子群算法分為全局粒子群算法與局部粒子群算法等不同的類型。

算法運行過程中，一個粒子Xi自身搜索到的歷史最優(yōu)解表示為Phibest，稱為自身歷史最優(yōu)解，所有粒子搜索到的最優(yōu)解表示為Pgbest，稱為全局歷史最優(yōu)解，粒子鄰域內(nèi)的其他粒子搜索到的歷史最優(yōu)解表示為Plibest，稱為鄰域歷史最優(yōu)解，粒子運行的速度記為Vi。

標準全局粒子群算法 （Standard Global Particle Swarm Optimization，SG-PSO）按照公式（3）（4）進行速度、位置的更新。

標準局部粒子群算法 （Standard Local Particle Swarm Optimization，SL-PSO）按照公式（5）（6）更新速度、位置。

目前，對粒子群算法的改進主要集中在慣性權(quán)重、加速系數(shù)、約束系數(shù)方面。文獻［16］對慣性權(quán)重做了詳盡的研究。

文獻［17］對種群的初始化方法進行了改進。文獻［18］對約束系數(shù)的選擇進行了探討。根據(jù)對這些文獻的研究和實踐驗證，本文提出兩個方面的改進措施。

2.2 粒子群算法的改進

文中提出的新算法主要針對兩個方面進行改進。

1）離散度概念的引入

根據(jù)文獻［17］的結(jié)論，種群的初始化對粒子群算法的運行結(jié)果具有重要的影響，為此本文根據(jù)文獻［9］的研究結(jié)果，采用更能體現(xiàn)種群初始化時粒子分布的均勻度的離散度方法。離散度的定義如下：

積的概念：N個二維粒子在空間中占據(jù)的面積使用公式（7）計算

其中x為N個粒子的橫坐標，y是粒子的縱坐標，以此類推D維空間中N個粒子的積的定義如公式（8）所示。

其中xi是粒子的第i維。把D維空間的積記為SD。則離散度MD=SD/N。其中N為粒子的個數(shù)。

盡管對慣性權(quán)重、加速系數(shù)、約束系數(shù)3個系數(shù)調(diào)整的策略有多種，但有一個總原則：3個系數(shù)的調(diào)整都與種群粒子的當前狀態(tài)相關(guān)。

在算法迭代過程中，按照公式（3），（4）進行位置與速度的更新，慣性權(quán)重用φ代替，加速系數(shù)c1=6*（φ-1）2+4，c2=0.5*sin（φ）+0.8。這樣c1從4以凹函數(shù)遞增到10，c2從0.8開始逐漸遞增到1.2。

2）適應度函數(shù)的拉伸技術(shù)

在粒子群算法運行過程中，為了避免算法陷入局部最優(yōu)和算法運行后期動力不足的問題，往往對適應度函數(shù)采用“拉伸”技術(shù)［19-20］。文中采用的拉伸操作是將小于當前全局最優(yōu)適應度的函數(shù)值保持不變，比當前全局最優(yōu)適應度大的適應度值，根據(jù)該值與當前全局最優(yōu)的差值進行拉伸，擴大二者之間的差異，以加速新的迭代的收斂速度。

文中采用的拉伸技術(shù)的思想：

假設(shè)尋找函數(shù)y=1-cos（3*x）*exp（-x）在區(qū)間［0，4］之間的最大值，采用該函數(shù)本身作為粒子適應度評價函數(shù)。該函數(shù)的圖形如圖2所示。

圖2 函數(shù)y=1-cos（3*x）*exp（-x）的圖形

如果PSO算法收斂到局部最優(yōu)x=3，y=1.045 4時，對適應度評價函數(shù)采用公式（9）進行拉伸。

f（u）為原來適應度評價函數(shù)，ū為取得當前全局最優(yōu)值的位置，γ為大于1的正整數(shù)，代表放大的倍數(shù)，G（u）成為新的適應度評價函數(shù)。經(jīng)拉伸后的函數(shù)圖形如圖3虛線所示。

圖3 拉伸后的函數(shù)圖形

拉伸技術(shù)的基本思路：采用全局版的PSO來保證收斂速度，在迭代過程中，當RM小于一個閾值時，保留本次搜索過程的全局最優(yōu)值，對所有粒子的位置、速度、個體最優(yōu)值進行初始化，重新迭代，同時對適應度函數(shù)采用公式（9）進行拉伸操作，拉伸后的函數(shù)作為新的適應度評價函數(shù)。這樣即保證了收斂速度，又能保證算法在全局最優(yōu)值處收斂。

3 仿真試驗

為了對新算法的有效性進行評價，采用KDD Cup 1999網(wǎng)絡(luò)數(shù)據(jù)集進行測試數(shù)據(jù)，該數(shù)據(jù)集由麻省理工學院Lincoln實驗室模擬美國軍方環(huán)境而搭建網(wǎng)絡(luò)實驗室，對網(wǎng)絡(luò)流量測試而得到，同時也是第三屆數(shù)據(jù)挖掘所使用的數(shù)據(jù)集。

該數(shù)據(jù)集包括約500萬條訓練集和300萬條測試集，每條記錄包含34個數(shù)值型字段和7個非數(shù)值型字段，并帶有正常、Probing、DoS、R2L、U2R 5種類標簽。數(shù)據(jù)中包括4種類型的攻擊：DoS（拒絕服務攻擊），R2L（未經(jīng)授權(quán)的遠程訪問），U2R（對本地超級用戶的非法訪問）和Probing（掃描與探測）。從數(shù)據(jù)集中隨機抽取5 000條記錄，使正常記錄與異常記錄的比例為7:3。

算法中參數(shù)的設(shè)置為種群規(guī)模N為1000，每個粒子的維數(shù)D為10，閾值b為0.9，閾值k為0.01，約束系數(shù)r為0.729，拉伸系數(shù)γ為3，算法迭代3000次終止，每種算法平均運行20次，取運行結(jié)果的平均值作為衡量的最終結(jié)果。表1列出了采用經(jīng)典的粒子群算法和新算法檢測率和誤報率的對比結(jié)果。

4 結(jié) 論

通過對基本的粒子群算法進行兩個方面的改進，得到一種新的粒子群算法，將這種新型的算法應用于入侵檢測。新算法通過采用離散度作為衡量種群分布均勻的指標，并且在算法運行過程中將慣性權(quán)重、加速系數(shù)、約束系數(shù)與離散度進行關(guān)聯(lián)，為了避免算法運行后期陷于局部最優(yōu)和動力不足的問題，在離散度達到一個閾值時，對適應度函數(shù)進行了拉伸和保優(yōu)重新初始化種群的措施，這些措施能夠保證搜索空間的全面性，算法收斂的速度，而且能夠防止算法的“早熟”現(xiàn)象。最后，通過KDD Cup 1999數(shù)據(jù)集對算法的訓練、檢驗數(shù)據(jù)的仿真，結(jié)果表明新的粒子群算法能夠有效的提高入侵檢測的檢測率、降低誤檢率且具有收斂速度快和不易“早熟”的優(yōu)勢。

表1 經(jīng)典算法與改進算法的對比結(jié)果

［1］馬茂剛.基于粒子群算法的入侵檢測技術(shù)研究［D］.哈爾濱：哈爾濱理工大學，2011.

［2］Kennedy J，Eberhart R.Particle swarm optimization［C］//In: IEEE Int'1 Conf on Neural Networks，Perth，Australia，1995:1942-1948.

［3］牛永潔，趙耀鋒.改進的LF算法在入侵檢測中的應用［J］.計算機與現(xiàn)代化，2013（6）:57-59，63.

［4］劉孔源.基于核方法的網(wǎng)絡(luò)入侵檢測若干研究［D］.南京：南京郵電大學，2014.

［5］匡芳君.群智能混合優(yōu)化算法及其應用研究［D］.南京：南京理工大學，2014.

［6］徐鵬，姜鳳茹.粒子群算法和K近鄰相融合的網(wǎng)絡(luò)入侵檢測［J］.計算機工程與應用，2014（11）:95-98.

［7］馮瑩瑩，余世干，劉輝.KNN-IPSO選擇特征的網(wǎng)絡(luò)入侵檢測［J］.計算機工程與應用，2014（17）:95-99.

［8］趙暉.融合鄰域粗糙集與粒子群優(yōu)化的網(wǎng)絡(luò)入侵檢測［J］.計算機工程與應用，2013（18）:73-77，93.

［9］牛永潔，劉濤.基于離散度與拉伸技術(shù)的粒子群優(yōu)化算法［J］.計算機工程與科學，2011（5）:112-115.

［10］杜利峰，牛永潔.改進的粒子群算法在智能組卷中的應用研究［J］.信息技術(shù)，2012（9）:165-167，171.

［11］黃業(yè)宇.一種基于OCSVM-PSO的網(wǎng)絡(luò)入侵檢測技術(shù)［D］.廣州：暨南大學，2014.

［12］牛永潔，常浩.基于Boosting與SVM的入侵檢測技術(shù)［J］.信息技術(shù)，2010（12）:92-93，98.

［13］李鋒.粒子群模糊聚類算法在入侵檢測中的研究［J］.計算機技術(shù)與發(fā)展，2014（12）:138-141.

［14］張拓，王建平.基于CQPSO-LSSVM的網(wǎng)絡(luò)入侵檢測模型［J］.計算機工程與應用，2015（2）:113-116，155.

［15］龔明朗，許榕生.一種改進的PSO算法在網(wǎng)格入侵檢測系統(tǒng)中的研究［J］.計算機應用與軟件，2011（3）:274-278.

［16］陳貴敏，賈建援，韓琪.粒子群優(yōu)化算法的慣性權(quán)值遞減策略研究［J］.西安交通大學學報，2006（1）:53-56.

［17］張永強，張墨華.反向?qū)W習粒子群算法和多層分類器相融合的網(wǎng)絡(luò)入侵檢測［J］.計算機應用與軟件，2015（4）:305-308.［18］吳亮，蔣玉明.基于適應值的粒子群優(yōu)化改進［J］.計算機工程與設(shè)計，2010，31（6）:1283-1285.

［19］牛永潔，陳莉.基于競爭與拉伸技術(shù)的粒子群算法［J］.計算機工程與設(shè)計，2008，（22）5802-5804，5809.

［20］肖立中，劉云翔，陳麗瓊.基于改進粒子群的加速K均值算法在入侵檢測中的研究［J］.系統(tǒng)仿真學報，2014（8）:1652-1657.

Application of intrusion detection based on improved particle swarm optim ization

NIU Yong-jie
（College ofMathematics&Computer Science，Yan'an University，Yan'an 716000，China）

In order to improve the detection rate and reduce the false detection rate of intrusion detection systems，In the initialization phase of particle swarm，discrete degree of swarm mustmeet certain requirements before its iteration.In the process of iterative algorithm，the adjustment of inertia weight and acceleration coefficient was related to current discrete degree of particle swarm.When discrete degree was smaller than certain value，it should reinitialize in order to retain high quality，stretch fitness function and reiterate.The improved particle swarm optimization algorithm has higher detection accuracy and lower false detection rate，The new algorithm has the advantages of fast convergence and difficult to local optimum.

intrusion detection；particle swarm optimization；discrete degree；fitness function；stretch

TN918.91

A

1674－6236（2016）20-0094-04

2016-01-13 稿件編號：201601096

陜西省教育廳自然科學研究項目（14JK1828）

牛永潔（1977—），男，河南許昌人，碩士，副教授。研究方向：數(shù)據(jù)挖掘、智能算法、網(wǎng)絡(luò)安全。