遺傳禁忌算法優化BP網絡用于入侵檢測

摘 要:針對入侵檢測系統存在的高漏報率和誤報率，提出一種基于遺傳禁忌神經網絡的入侵檢測模型。該模型基于遺傳禁忌算法的全局搜索和BP網絡局部精確搜索的特性，將遺傳禁忌算法和BP算法有機結合，利用遺傳禁忌算法優化BP網絡初始權重，同時引入小生境技術改進遺傳禁忌算法。實驗表明，改進的遺傳禁忌算法優化BP網絡用于入侵檢測能提高入侵檢測的效率，降低誤警率，可在一定程度上提高入侵檢測系統的準確率。

關鍵詞:入侵檢測;BP神經網絡;遺傳禁忌算法;小生境技術;網絡安全

中圖分類號:TP393 文獻標志碼:A

文章編號:1001-3695(2010)03-1086-03

doi:10.3969/j.issn.1001-3695.2010.03.077

Genetic tabu algorithm for BP network intrusion detection

WANG Yan-pin

(Dept. of Information Engineering， Zhengzhou Railway Vocational Technical College， Zhengzhou 450052， China)

Abstract:For high omission rate and 1 alarm rate in intrusion detection system，this paper proposed a tabu-based genetic neural network intrusion detection model.The model was based on genetic tabu algorithm of global search and BP global network of local search precision features， combined genetic tabu algorithm and BP algorithm， and used genetic tabu algorithm initial weights of BP network， at the same time，used niching technology to improve genetic tabu algorithm.Experiments show that the improved genetic tabu algorithm optimizing the BP network for intrusion detection can improve the efficiency of intrusion detection， lower 1 positive rate，improve the accuracy in the intrusion detection system to some extent.

Key words:intrusion detection; BP neural network; genetic tabu algorithm; niche technology; network security

隨著網絡互連程度的日益擴大，Internet得到迅速發展。尤其是近年來網絡上電子商務等業務的快速發展，網絡的重要性及其對社會的影響也越來越大，網絡與人們的日常生活密不可分。同時，通過網絡犯罪對國家安全、企業安全和個人安全造成的損失也日益嚴重，網絡安全已成為人們最為關心的問題。入侵檢測是近十年發展起來的一種動態監測、預防或抵御系統入侵行為的安全機制[1]。目前入侵檢測有許多模型和方法，而模式識別和數據挖掘等技術的引入使入侵檢測的智能性研究成為熱點[2，3]。神經網絡和模式識別技術具有自學習、自適應的能力，只要提供系統的審計數據或網絡數據包，神經網絡就可以通過自學習從中提取正常的用戶或系統活動特征模式，并檢測出異常活動的攻擊模式[4]。神經網絡的這些特性使其在入侵檢測中得到了很好的應用。最流行的神經網絡學習算法是BP算法(back-propagation algorithm)，它的收斂速度慢，存在局部最優問題[5，6]，故基于神經網絡的入侵檢測面臨的一個主要任務是效率問題和準確性問題[7，8]。

1 相關概念介紹

1.1 入侵檢測

入侵是指系統的未授權用戶試圖或已經竊取了系統的訪問權限，以及系統的授權用戶超越或濫用了系統所授予的訪問權限，從而威脅或危害了網絡資源的完整性、機密性或有效性的行為集合[9]。其中，完整性是指防止網絡資源被非法刪改和破壞;機密性是指防止網絡系統內信息的非法泄露;有效性是指網絡系統數據資源可以被授權用戶隨時正常地訪問，以及程序資源能夠按期望的方式和作用正常地運行。從分類角度可將入侵劃分為信息收集(如路由探測、拓撲重建、系統探查、端口掃描等)、系統侵入、系統滲透、偽裝隱形、系統攻擊(如洪流、郵件炸彈等)和惡意使用等類型。

入侵檢測是通過對系統數據的分析，有效地發現非授權的訪問和攻擊行為。它通過從計算機系統中的日志文件、計算機網絡中的若干關鍵節點等處收集相關信息并分析這些信息，檢查系統或網絡中是否有違反安全策略的行為和遭到襲擊的跡象，在不影響系統性能的情況下能對網絡進行監測[10]。

入侵檢測系統(intrusion detection system，IDS)[11]是一種計算機軟件系統，用于自動檢測上述入侵行為，并收集入侵證據，為數據恢復和事故處理提供依據。有些入侵檢測系統在檢測到入侵特征后還試圖作出某些響應，以遏制或阻止對系統的威脅或破壞。該系統通常包括以下功能:a)檢查系統的配置和系統存在的脆弱性;b)評估關鍵系統和數據文件的完整性和一致性;c)分析用戶和系統的活動情況;d)檢測并響應正在進行的或已經實現的違反系統安全策略的入侵活動;e)收集入侵證據。

在設計網絡入侵檢測系統時，要特別對來自組織機構內部的入侵行為予以更多的重視。據FBI的研究，80%的入侵和攻擊行為來自于組織機構內部。由于內部人員具有訪問系統資源的合法身份、了解系統數據的價值和熟悉系統的安全措施，從而可以使用某些系統特權或調用比審計功能更低級的操作來逃避審計。

1.2 禁忌搜索算法

禁忌搜索算法(TS)最早是由Glover于1986年提出的，它是一種“局部搜索”的修正方法[12]，通過一個靈活的記憶功能和藐似準則達到搜索解空間的目的。與傳統的優化算法相比，其主要特點是:a)在搜索過程中可以接受劣解，所以具有較強的“爬山”能力;b)新解不是在當前解的領域中隨機產生，而是從中選取最好解，即最好解的產生概率遠遠大于其他解。

禁忌搜索算法的缺陷是對于初始解具有較強的依賴性。一個較好的初始解可使禁忌搜索在解空間中搜索到更好的解，而一個較差的初始解則會降低禁忌搜索的收斂速度，搜索到的解也相對較差。此外，其搜索只是單對單操作，即在搜索過程中初始解只能有一個，在每代也只是把一個解移動到另一解。

1.3 遺傳算法與禁忌搜索算法的混合優化算法

Glover等人從廣義的角度對遺傳算法(GA)和禁忌搜索算法(TS)進行了比較和分析，指出了兩者結合的可能性，為GA和TS算法的結合應用提供了理論基礎[13]。為了保持GA和TS算法的優點，提高算法的計算效率，在實際應用時人們提出各種改進策略。本文將兩者混合使用，提出一種將GA和TS算法混合的策略，并在其中引入小生境技術。先將小生境技術融入GA中，使GA的種群保持較高的多樣性，從而避免GA陷入局部最優;用這種融入了小生境的GA進行全局搜索，可以使群體中的個體分布在解空間的大部分區域，待收斂到一定程度后，各個體的位置相對比較固定，再用TS算法進行局部搜索，使算法快速地收斂到全局最優解。

2 改進的遺傳禁忌算法優化BP網絡

2.1 融入小生境的技術

在用BP神經網絡進行入侵檢測時，有一個重要問題就是網絡連接權值的確定問題，因為初始權值選擇不當，不僅會影響到網絡的收斂速度，而且可能對最終網絡的性能有很大影響。對這類問題的解決方法目前主要是憑經驗進行選擇。針對以上問題，本文提出了用遺傳禁忌算法來初始化BP網絡的權值。由于遺傳算法采用根據適應度值的大小來決定個體是否被復制的選擇機制，這樣容易出現來源于同一種群的個體被大量繁衍的情況，形成近親繁殖，造成算法的局部搜索和過早收斂，從而導致全局尋優過程失敗，特別是對于多峰值函數容易出現這種現象。為了避免GA陷入局部最優，將小生境技術引入到算法中。小生境技術通過海明距離定義的排擠策略能夠保證種群的多樣性。

2.2 改進遺傳禁忌算法優化BP網絡的初始權值

本文提出的入侵檢測模型(圖1)，首先通過分類器對捕捉到的數據進行特征分析，然后將出現的未知類型投入到訓練樣本中，進行改進的遺傳禁忌算法優化BP網絡的學習后，再次使用神經網絡分類器進行分類。根據采集可控網絡流量數據，每一分鐘計算一次這段時間內的各流量特征的統計值作為神經網絡的輸入，通過網絡流量異常的可視化分析。利用遺傳禁忌算法優點來克服BP算法收斂慢和易局部收斂的缺陷，同時與BP算法的結合也解決了單獨利用遺傳禁忌算法往往不能在短時間內尋找到接近最優解的這一問題，引入BP算法的梯度信息將會避免這種現象。因此可將BP神經網絡的訓練分成兩部分:a)用遺傳禁忌算法來優化網絡的初始權值;b)用BP算法來訓練入侵檢測數據得到網絡模型。本文將融入小生境的遺傳禁忌算法簡稱為NGATS。

NGATS算法優化BP網絡具體步驟如下:

a)確定初始參數，包括最大迭代次數T、種群規模N、交叉概率Pc和變異概率Pm等，并確定編碼方式，令t=0。

b)隨機產生N個初始個體組成初始種群p(t)={a1，a2，…，ai，…，aN}，并求出各個個體的適應度Fai(i=1，2，…，N)，記錄最好的個體。

c)依據各個個體的適應度進行降序排列，并計算每個個體被選擇的概率Pai=Fai/Mi=1Fai(i=1，2，3，…，M)。選擇過程中使用保優原則(即上一代最優的個體以概率1保存至下一代)，產生種群P(1)(t)。

d)根據交叉概率Pc對群體中的個體進行交叉運算，得到P(2)(t)。

e)根據變異概率Pm對群體中的個體進行變異運算，產生新一代種群P(3)(t)={b1，b2，…，bi，…，bN}。

f)小生境淘汰運算。按照下式[9]求出P(3)(t)中每兩個個體bi和bj之間的海明距離:

‖bi-bj‖=chromlenk=1(bik-bjk)2

其中，i=1，…，N-1;j=i+1，…，N;chromlen為染色體長度。

當‖bi-bj‖

g)判斷是否滿足遺傳算法終止規則，即在規定連續代數Q內均滿足|eval(Ut max)-eval(U(t-1)max)|≤ε。其中:ε為一適當小的正數;eval(Ut max)為第t代的最大適應度值;eval(U(t-1)max)為t-1代的最大適應度值。則遺傳算法終止，繼續下一步迭代，否則轉步驟c)。

h)把遺傳算法得到的最優解作為禁忌搜索的初始解，進行禁忌搜索算法。

i)若t

重復以上步驟，直到進化代數達到要求或網絡誤差滿足條件時結束改進的遺傳禁忌算法，選擇網絡誤差最小的一組權值作為BP網絡訓練的初始權值，再利用BP算法進行訓練，使最終誤差達到要求。

3 仿真實驗結果與分析

3.1 實驗數據與實驗環境

目前，用于網絡入侵檢測的生物算法很多[14，15]，如前面提到的傳統BP算法[16]、遺傳算法[17]以及粒子群算法[18]等。本文把基于遺傳禁忌算法的BP網絡應用到網絡入侵檢測中，期望改進入侵檢測系統的性能。

為了驗證本文所提出方法的有效性，本文采用KDD Cup 1999標準入侵檢測數據集[19]進行實驗。KDD Cup 1999數據集是由Defence Advanced Research Projects Agency(DARPA)和麻省理工學院的Lincoln實驗室提供的入侵數據集采集樣本，該數據集共有近500萬條數據樣本，每個樣本包含了41個特征屬性。其中7個符號特征(離散屬性)、34個數值特征(連續屬性)。這些實驗數據除包含正常連接數據normal外，還包含了四大類入侵行為，分別是DoS(拒絕服務)、R2L(遠程攻擊)、U2R(獲取根權限)和Probe(刺探攻擊)。實驗從KDD Cup 1999數據集中隨機選取了訓練數據7 032條，測試數據16 408條。訓練集中DoS攻擊1 114條、R2L攻擊9條、Probe攻擊38條、U2R攻擊20條;測試數據中DoS攻擊2 581條、R2L攻擊11條、U2R攻擊33條、Probe攻擊78條。

神經網絡采用如下結構:輸入層的節點數為40個，隱含層的節點數為10個，輸出節點數為4個。 采用GA優化初始神經網絡權重的方法，GA操作的參數為:選擇種群N=50，最大進化代數gen=500，選擇概率Ps=0.095。BP算法參數為:初始學習率lr=0.005，設定的誤差(輸出值與真實輸入之間的差值的絕對值)為0.000 01，最大循環數為1 000。

實驗在Intel Celeron 3.0 GHz CPU、512 MB內存、Windows XP操作系統、MATLAB語言編程環境下進行，同時對BP網絡、GA-BP、PSO-BP、本文算法進行比較分析。

3.2 實驗結果與分析

實驗分別是對于同一組混合數據的四種方法BP訓練，示意圖如圖2~5所示。

如圖2~5所示，在這組數據中，NGATS-BP訓練步數為23步，時間為12.238 000 s，均方誤差為1.378 6e-003;PSO-BP訓練步數為161步，時間為19.212 100 s，均方誤差為1.378 6e-003;GA-BP訓練步數為251步，時間為22.219 000 s，均方誤差為1.378 6e-003;BP訓練步數為327步，時間為26.612 000 s，相對收斂較慢，均方誤差為0.11。對NGATS-BP來講，無論是從訓練時間上還是從降低誤差上都有明顯的提高。

在實驗中筆者發現，四種訓練算法訓練神經網絡與權值和閾值的初始值都有一定的關系，而BP算法表現最為明顯。如果初始值比較好，則很快就能得到最佳結果，反之，則得不到最佳結果，誤差會越來越大，最后到達某一結果后停下來。NGATS在訓練過程中一直向理想結果靠近，表現出較好的全局尋優能力。實驗證明，利用本文提出的NGATS算法訓練神經網絡用于入侵檢測能取得較好的性能，針對幾種攻擊類型與其他幾種算法相比，檢測率都有不同程度的提高(表1)。

表1 基于四種算法的檢測率

攻擊類型攻擊名稱

檢測率/%

NGATS-BPPSO-BPGA-BPBP

DoSSmurf99.0596.7276.4772.84

PROBESatan99.3793.2085.6286.55

R2LGuess_passwd99.6091.5673.8767.23

U2RPerl98.7989.3565.7172.58

4 結束語

通過分析表明，遺傳禁忌算法在BP網絡學習中，相對于PSO算法、GA和傳統BP算法，不僅速度快、算法簡單，而且測試精確率高。特別是最后經過網絡入侵數據的仿真實驗的比較，進一步證明了基于遺傳禁忌算法的BP網絡學習算法的優越性和實用性。

參考文獻:

[1]

DE Den-ning.An intrusion detection model[J].IEEE Trans on Software Engineering，1987，139(2):222-232.

[2]卿斯漢，蔣建春，馬恒太，等.入侵檢測技術研究綜述[J].通信學報，2004，25(7):19-29.

[3]林果園，黃皓，張永平.入侵檢測系統研究進展[J].計算機科學，2008，35(2):69-74.

[4]唐勇，盧錫城，王勇軍.攻擊特征自動提取技術綜述[J].通信學報，2009，30(2):96-105.

[5]SHUN J，MALKI H A.Network intrusion detection system using neural networks[C]//Proc of the 4th International Conference on Natural Computation.2008:242-246.

[6]SONG Guang-jun，ZHANG Jia-lin，SUN Zhen-long.The research of dynamic change learning rate strategy in BP neural network and application in network intrusion detection[C]//Proc of the 3rd International Conference on Innovative Computing Information and Control.2008:513-513.

[7]TIAN Jing-wen，GAO Mei-juan.Network intrusion detection method based on high speed and precise genetic algorithm neural network[C]//Proc of International Conference on Networks Security，Wireless Communications and Trusted Computing.2009:619-622.

[8]WANG Hui-ran，MA Rui-fang.Optimization of neural networks for network intrusion detection[C]//Proc of the 1st International Workshop on Education Technology and Computer Science.2009:418-420.

[9]YU Zhen-wei，TSAI J J P，WEIGERT T.An automatically tuning intrusion detection system[J].IEEE Trans on Systems，Man，and Cybernetics，Part B，Cybernetics，2007，37(2):373-384.

[10]PARIKH D，CHEN T.Data fusion and cost minimization for intrusion detection[J].IEEE Trans on Information Forensics and Security，2008，3(3):381-389.

[11]CHEN L，LENEUTRE J.Game theoretical framework on intrusion detection in heterogeneous networks[J].IEEE Trans on Information Forensics and Security，2009，4(2):165-178.

[12]GLOVER F，KELLY J，LAGUNA M.Genetic algorithm and tabu search:hybrids for optimizations[J].Computers and Science，1995，22(1):111-134.

[13]蔣泰，楊海.定位—路線問題的遺傳禁忌混合優化算法[J].計算機應用，2008，28(3):688-691.

[14]劉衍珩，田大新，余雪崗，等.基于分布式學習的大規模網絡入侵檢測算法[J].軟件學報，2008，19(4):993-1003.

[15]易曉梅，陳波，蔡家楣.入侵檢測的進化神經網絡研究[J].計算機工程，2009，35(2):208-209，213.

[16]許朋飛，沈磊.改進BP算法在入侵檢測系統中的應用[J].計算機工程，2008，34(6):151-152.

[17]徐仙偉，葉小嶺.遺傳算法優化BP網絡初始權重用于入侵檢測[J].計算機應用研究，2005，22(3):127-128，132.

[18]肖曉麗，黃繼紅，劉志朋.基于MPSO的BP網絡及其在入侵檢測中的應用[J].計算機工程，2008，34(15):168-169，210.

[19]KDD Cup 1999 data set [EB/OL].http://archive.ics.uci.edu/ml/ databases/kddcup99/kddcup99.html.