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

牛永潔

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

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

牛永潔

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

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

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

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

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

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

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

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

1 入侵檢測

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

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

入侵檢測系統是通過監視和檢測數據的通信或用戶的行為來證明是否有入侵的系統。本文采用的入侵檢測系統采用基于網絡的IDS，其基本的工作原理如圖1所示。

圖1 入侵檢測的基本原理

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

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

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

2 粒子群算法的改進

2.1 基本粒子群算法

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

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

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

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

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

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

2.2 粒子群算法的改進

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

1）離散度概念的引入

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

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

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

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

盡管對慣性權重、加速系數、約束系數3個系數調整的策略有多種，但有一個總原則：3個系數的調整都與種群粒子的當前狀態相關。

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

2）適應度函數的拉伸技術

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

文中采用的拉伸技術的思想：

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

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

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

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

圖3 拉伸后的函數圖形

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

3 仿真試驗

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

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

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

4 結 論

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

表1 經典算法與改進算法的對比結果

［1］馬茂剛.基于粒子群算法的入侵檢測技術研究［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］.計算機與現代化，2013（6）:57-59，63.

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

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

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

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

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

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

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

［11］黃業宇.一種基于OCSVM-PSO的網絡入侵檢測技術［D］.廣州：暨南大學，2014.

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

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

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

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

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

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

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

［20］肖立中，劉云翔，陳麗瓊.基于改進粒子群的加速K均值算法在入侵檢測中的研究［J］.系統仿真學報，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—），男，河南許昌人，碩士，副教授。研究方向：數據挖掘、智能算法、網絡安全。