文/焦寶臣 劉振昌 陳詩明 于名飛

入侵檢測算法三大分類

文/焦寶臣 劉振昌 陳詩明 于名飛

入侵檢測系統(tǒng)（IDS，Intrusion Detection System）就是利用入侵檢測技術發(fā)現(xiàn)計算機或網(wǎng)絡中存在的入侵行為和被攻擊的跡象的軟硬件系統(tǒng)。區(qū)別于防火墻，入侵檢測系統(tǒng)是一種主動防御的系統(tǒng)，能夠更加及時地主動發(fā)現(xiàn)非法入侵并報警和采取應急措施，是人們研究的熱點領域。

當前研究入侵檢測系統(tǒng)的核心是對其算法的研究，人們的工作也大多集中于此。對于算法研究的目標是降低入侵檢測系統(tǒng)的誤報、漏報率和提升系統(tǒng)的運行效率。由于各種算法都有其局限性的一面，而具體的網(wǎng)絡使用環(huán)境各不相同，這也是阻礙入侵檢測系統(tǒng)商業(yè)應用的重要障礙，尋找一種具有適用性更廣泛的算法也是研究工作的重要內容，對當前入侵檢測算法研究現(xiàn)狀進行綜合考慮是十分必要的。本文從當前入侵檢測算法的熱點領域入手，依據(jù)入侵檢測系統(tǒng)種類對當前流行的算法進行分類并詳細介紹研究現(xiàn)狀。

蟻群算法是一種基于生物種群的模擬進化算法，模擬蟻群在尋找食物的過程中總能找到蟻巢和食物源之間的最短路徑的方法。

入侵檢測算法分類

當前入侵檢測算法多種多樣，其中以關聯(lián)規(guī)則、聚類和支持向量機等算法為代表的數(shù)據(jù)挖掘技術是當前研究的重點方面，另外，人工智能算法也在逐漸引起人們的注意。對入侵檢測算法進行分類，首先考慮入侵檢測系統(tǒng)的分類。入侵檢測系統(tǒng)的分類有多種方法，如根據(jù)審計對象的不同，可分為基于網(wǎng)絡的IDS、基于主機的IDS和基于網(wǎng)絡/主機混合型IDS；按照系統(tǒng)的體系結構可以分為集中式和分布式入侵檢測系統(tǒng)；按照檢測技術可分為誤用檢測和異常檢測兩類。由于

檢測技術實際上指的就是所使用的入侵檢測算法，所以這里主要考慮按照檢測技術分成的誤用檢測和異常檢測的分類方法。另外隨著人們對人工智能算法在入侵檢測系統(tǒng)中應用研究的開展，這類系統(tǒng)呈現(xiàn)出與前兩類不同的一些特性。因此將當前入侵檢測算法歸結為誤用檢測算法、異常檢測算法和人工智能算法三類，具體情況如圖1。圖1給出了入侵檢測算法的分類。下面就誤用檢測、異常檢測和人工智能算法三種入侵檢測算法分別進行介紹。

圖1 入侵檢測算法分類

誤用檢測算法

誤用檢測的基本原理是將已知的入侵行為和企圖進行特征抽取，提取共同模式并編寫進規(guī)則庫，再將監(jiān)測到的網(wǎng)絡行為與庫進行模式匹配，如果特征相同或相似，就認為是入侵行為或者企圖，并觸發(fā)警報。模式匹配是這類系統(tǒng)所采用的方法，如圖1所示。

Snort入侵檢測系統(tǒng)是一種典型的誤用檢測系統(tǒng)。它是在Libcap基礎上研發(fā)的較為成熟的輕量級入侵檢測系統(tǒng)，具有尺寸小、易于安裝、便于配置、功能強大、使用靈活等特點。該系統(tǒng)采用的算法是模式匹配，因此人們的研究主要是集中在對模式匹配算法的優(yōu)化上。例如：黃侃【1】對BM算法進行了優(yōu)化，能夠有效節(jié)省Snort系統(tǒng)的運算時間，提高系統(tǒng)性能，BM算法是Snort入侵檢測系統(tǒng)中重要的字符串匹配算法。郝偉臣【2】給出一種基于哈希算法的匹配算法應用于Snort系統(tǒng)，取得了較好的效果。

該方法具有低誤報率的優(yōu)點，但是不能檢測出規(guī)則庫中不存在的入侵行為和企圖，即無法檢測未知的攻擊。

異常檢測算法

異常檢測是通過建立一個主體正常行為的模型，將攻擊行為作為異常活動從大量的正?；顒又袡z測出來，達到對攻擊行為檢測的目的，其顯著的優(yōu)點是對未知攻擊的檢測。

數(shù)據(jù)挖掘是指從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中提取隱含在其中的、人們不知道的但又是潛在有用的信息和知識的過程。這一點與異常檢測所要求的對未知入侵和威脅的檢測是相一致的。隨著數(shù)據(jù)挖掘算法的發(fā)展，其在入侵檢測領域中的應用愈加深入，受到人們研究的關注。當前流行的數(shù)據(jù)挖掘技術是異常檢測算法研究的主要領域，如圖1所示，其中以關聯(lián)規(guī)則、聚類和支持向量機等算法尤其具有代表性。下面就各種有代表性的算法進行介紹。

關聯(lián)規(guī)則

關聯(lián)規(guī)則算法的目的是發(fā)現(xiàn)隱藏在大型數(shù)據(jù)集的各不同屬性之間的有意義聯(lián)系，發(fā)現(xiàn)的聯(lián)系用關聯(lián)規(guī)則或者頻繁相集來表示。關聯(lián)規(guī)則的基本形式X→Y，這里X∩Y=?。支持度（Support）和置信度（Confidence）是最重要的兩個概念，它們的定義：

Support（X→Y）=P(X∪Y) （1）；

Confidence（X→Y）=P(Y│X) （2）。

支持度可以確定規(guī)則中出現(xiàn)在給定數(shù)據(jù)集的頻繁程度，置信度可以確定Y出現(xiàn)在包含X的事務中的頻繁程度。因此，關聯(lián)規(guī)則算法就是從某事物數(shù)據(jù)集中發(fā)現(xiàn)滿足最小支持度和最小置信度的關聯(lián)規(guī)則的過程。

采用關聯(lián)規(guī)則算法對數(shù)據(jù)進行挖掘主要包括產(chǎn)生頻繁項集和產(chǎn)生規(guī)則兩個步驟。產(chǎn)生頻繁項集：從數(shù)據(jù)集中發(fā)現(xiàn)滿足最小支持度閾值的項集，即頻繁項集。產(chǎn)生規(guī)則：從頻繁項集中提取出所有滿足最小置信度的規(guī)則。關聯(lián)規(guī)則算法通常是先產(chǎn)生頻繁項集后再產(chǎn)生規(guī)則， Apriori及其衍生的相關算法是這種典型的關聯(lián)規(guī)則算法。一般情況頻繁項集產(chǎn)生所需要的計算開銷要遠大于規(guī)則產(chǎn)生所需要的計算開銷，為了降低運算成本，也可以不生成頻繁項集的算法，如FP-Growth算法。

聚類算法

聚類就是按照一定的要求和規(guī)律對事物進行區(qū)分和分類。由于在聚類的過程中沒有任何關于分類的先驗知識，僅靠事物間的相似性作為類屬劃分的準則，因此這是一種無監(jiān)督的分類方式 。

K-means是經(jīng)典的聚類算法，它使用簡單的迭代將數(shù)據(jù)集聚成K個類，該算法具有簡單、易懂、良好的可伸縮性等顯著優(yōu)點。成為當前入侵檢測系統(tǒng)中聚類算法研究方面的重要算法。例如：薛京花【3】等人對K-means算法進行了改進并應用到入侵檢測系統(tǒng)中，并取得了明顯的效果。

除了K-means算法之外，聚類方法還包括模糊聚類和蟻群聚類算法。傳統(tǒng)的聚類分析是一種具有非此即彼的性質的硬劃分。但現(xiàn)實中大部分數(shù)據(jù)對象并沒有嚴格的屬性，在形態(tài)和類屬方面存在著中介性，更適合進行軟劃分。因此人們開始用模糊的方法來處理聚類問題。模糊C-均值算法是典型的模糊聚類算法。

蟻群算法是一種基于生物種群的模擬進化算法，模擬蟻群在尋找食物的過程中總能找到蟻巢和食物源之間的最短路徑的方法。該算法具有分布式并行計算、自適應和易于其他算法相結合的優(yōu)點。但存在過早限于局部最優(yōu)解和收斂速度慢的缺陷。

支持向量機

支持向量機（Support Vector Machine, SVM）算法是建立在統(tǒng)計學習理論的基礎上，能從大量訓練數(shù)據(jù)中選出很少的一部分用于構建模型，通常對維數(shù)不敏感。在當前高速網(wǎng)絡環(huán)境條件中很難獲得完備的訓練樣本集，同時為了降低部署模型的資源開銷，應盡可能地減少在數(shù)據(jù)挖掘的過程中使用的訓練樣本數(shù)據(jù)量。而SVM更適合小樣本數(shù)據(jù)學習，更符合實際高速網(wǎng)絡中的現(xiàn)實情況。另一方面，SVM能在很大程度上克服了傳統(tǒng)機器學習（神經(jīng)網(wǎng)絡、決策樹等）的維數(shù)災難和局部極小等問題，獲得比較好的泛化能力。具有良好泛化性能的入侵檢測系統(tǒng)對應其實際應用有著重要的意義，是人們研究所期望獲得的。綜上所述，SVM成為研究構建入侵檢測系統(tǒng)的重要算法。例如：李漢彪，劉淵【4】采用多SVM融合的方法，有效地彌補單個SVM檢測的局限性，能有效地提高入侵檢測率的同時降低誤報率。

采用SVM算法構建入侵檢測系統(tǒng)，通常需要其他算法對數(shù)據(jù)樣本進行屬性約減，降低維數(shù)，來提高運行效率。

另外也有利用蟻群、魚群等生物種群算法對SVM進行改進。例如：楊聰明【5】采用將自組織蟻群聚類算法作為SVM算法中查詢策略的方案，把蟻群聚類算法與SVM有效的融合，并應用到入侵檢測系統(tǒng)中，獲得了較高的檢測率和較低的誤報率、漏報率，并能提高算法的執(zhí)行效率。

決策樹

決策樹是一種樹狀結構，用于揭示數(shù)據(jù)中的結構化信息。利用該結構可以將大型記錄集分割為相互連接的小記錄集，通過每一次連續(xù)分割，結果集中的成員彼此變得越來越相似。使用決策樹算法可以將數(shù)據(jù)規(guī)則可視化，構造決策樹的過程所需的時間也比較短，且輸出的結果容易理解。決策樹具有分類精度高，操作簡單以及對噪聲數(shù)據(jù)有很好健壯性的優(yōu)點，C4.5、ID3是常見的決策樹算法方法。

史珊姍【6】在利用決策樹C4.5算法構建入侵檢測系統(tǒng)方面做了相關研究。但是C4.5決策樹算法在生成樹的過程中，需要對樣本集進行多次的掃描和排序，導致算法的效率比較低；另外C4.5 算法只適用于可以駐留于內存的數(shù)據(jù)集，當訓練集超過內存的容納能力時，程序就無法運行，使該算法對硬件要求比較高。

綜上所述，異常檢測算法主要采用關聯(lián)規(guī)則、聚類、SVM等數(shù)據(jù)挖掘算法，如圖1所示。除上述常用數(shù)據(jù)挖掘方法之外，還有k-最近臨（kNN）、樸素貝葉斯（Nave Bayes）等數(shù)據(jù)挖掘算法也是被人們應用于入侵檢測系統(tǒng)的研究中。根據(jù)這些算法的介紹可以得出，提高運行效率，提高準確率，降低誤報率是人們對算法研究的目標，然而各種算法本身有著各自的缺陷，限制了傳統(tǒng)算法的應用。

人工智能算法

通過前面對傳統(tǒng)數(shù)據(jù)挖掘算法的研究發(fā)現(xiàn)，各種算法自身存在著缺陷，研究具有高效率、低誤報率和良好泛化特性的算法仍舊是工作的中心。另外，具有分布式架構的入侵檢測系統(tǒng)更能適應當前網(wǎng)絡實際使用環(huán)境的需求，已成為當前入侵檢測系統(tǒng)研究的主流構架。因此傳統(tǒng)的算法已經(jīng)不能滿足當前入侵檢測系統(tǒng)發(fā)展需求。隨著人工智能的發(fā)展，將智能算法運用到入侵檢測系統(tǒng)中，將成為入侵檢測系統(tǒng)新的研究熱點發(fā)展方向。免疫方法和神經(jīng)網(wǎng)絡是當前入侵檢測系統(tǒng)主流的人工智能算法。

免疫方法

生物免疫系統(tǒng)的核心思想是識別并處理“自己”和“非己”，這與入侵檢測系統(tǒng)的工作目標是一致的。生物免疫系統(tǒng)具有識別能力、學習認知能力、多樣性、自適應性、自組織性、分布性的特點。其中分布性的特點是指免疫系統(tǒng)可以被視為一個分布式系統(tǒng)，因為免疫分子、免疫器官和免疫細胞不是集中分布在生物體的同一位置，而是分散開的，它們之間是相互獨立的處理單元，通過免疫網(wǎng)絡相互連接，共通完成比較復雜的免疫功能。這一點與當前構建分布式入侵檢測系統(tǒng)的現(xiàn)實需求是一致的。因此利用免疫系統(tǒng)運算原理構建的入侵檢測系統(tǒng)具有天然的優(yōu)勢。

姚云志【7】等人根據(jù)生物免疫系統(tǒng)與入侵檢測系統(tǒng)工作目的的統(tǒng)一性，在結合了否定選擇、克隆選擇和檢測子基因庫進化三種免疫機制基礎上，提出了一個改進的基于人工免疫的入侵檢測新模型。周志凱【8】等人對免疫算法構建的入侵檢測系統(tǒng)中關于具有信息增益的檢測器做了較深入的研究。

神經(jīng)網(wǎng)絡

人工神經(jīng)網(wǎng)絡（ANN，Artificial Neural Network）是由人工神經(jīng)元互連而成的網(wǎng)絡，它從微觀結構和功能上實現(xiàn)對人腦的抽象和簡化。人工神經(jīng)網(wǎng)絡具有非線性逼近性，很好的魯棒性以及容錯性，快速的運算能力，較好的實時特性，良好的并行特性，良好的學習能力和自適應性等諸多優(yōu)點。將人工神經(jīng)網(wǎng)絡技術應用于入侵檢測系統(tǒng)，能夠較好地解決目前一些不宜解決的問題，提高系統(tǒng)檢測率，減少誤報率。神經(jīng)網(wǎng)絡技術是最近幾年研究的熱點問題，如：多層前饋BP神經(jīng)網(wǎng)絡、蜜罐等等。

宋麟【9】等人研究了基于BP人工神經(jīng)網(wǎng)絡技術的入侵檢測系統(tǒng)。對失真或不完全數(shù)據(jù)的處理能力，是基于BP神經(jīng)網(wǎng)絡的實時入侵檢測系統(tǒng)的獨特優(yōu)點。李晨光【10】建立了基于BP神經(jīng)網(wǎng)絡的入侵檢測系統(tǒng)，該系統(tǒng)具備了入侵檢測技術的諸多優(yōu)點，可以有效的檢測出異常的網(wǎng)絡攻擊行為。蜜罐技術是一種主動的網(wǎng)絡保護技術，其思想是構建一個嚴格的欺騙環(huán)境誘騙入侵者對其進行攻擊，并在受到攻擊后作出預警，從而實現(xiàn)保護實際運行的網(wǎng)絡和系統(tǒng)。汪潔【11】等人設計并實現(xiàn)了一個基于人工神經(jīng)網(wǎng)絡的蜜罐入侵檢測系統(tǒng)。該系統(tǒng)應用感知器學習方法構建FDM檢測模型用于劃分正常類和攻擊類；構建SDM檢測模型對一些具體的攻擊類型進行識別。該系統(tǒng)對入侵行為具有較好的檢測率和較低的誤報率。

遺傳算法

遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的算法，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。將遺傳算法應用到入侵檢測中也有相關的研究。例如：朱紅萍【12】等人構建了基于遺傳算法的入侵檢測系統(tǒng)，重點研究如何進行特征選擇，來去除數(shù)據(jù)源中的不相關和冗余特征。

小結

從對人工智能算法入侵檢測系統(tǒng)研究現(xiàn)狀的情況看，人工智能算法目前還處于起步階段，但是由于其算法先天的優(yōu)勢，正在被研究人員所關注，越來越多的研究工作正在展開。

人工神經(jīng) 網(wǎng)絡（ANN，Artificial Neural Network）是由人工神經(jīng)元互連而成的網(wǎng)絡，它從微觀結構和功能上實現(xiàn)對人腦的抽象和簡化。

通過對當前入侵檢測算法的梳理，可分為誤用檢測算法、異常檢測算法和人工智能算法三類。其中誤用檢測以模式匹配算法為主，關聯(lián)規(guī)則、聚類、SVM等數(shù)據(jù)挖掘算法通常用于異常檢測，免疫方法和神經(jīng)網(wǎng)絡是人工智能算法的代表。傳統(tǒng)的數(shù)據(jù)挖掘算法仍是研究的重點和熱點，以免疫算法和神經(jīng)網(wǎng)絡為代表的人工智能算法正引起人們的關注，其在入侵檢測系統(tǒng)中的應用有著傳統(tǒng)數(shù)據(jù)挖掘算法所不具備的優(yōu)勢和廣泛的前景，應成為下一步研究的重點。

降低入侵檢測系統(tǒng)的誤報、漏報率和提升系統(tǒng)的運行效率仍然是算法研究的基本問題。另外，分布式架構和良好泛化性也是入侵檢測系統(tǒng)所要亟待解決的問題。因此，研究算法來解決上述問題仍是當前科研人員主要工作。利用傳統(tǒng)數(shù)據(jù)挖掘算法的特點和人工智能算法的優(yōu)勢，將其二者相結合或許能成為解決問題的一條路徑。

（作者單位為南開大學信息化建設與管理辦公室）

注釋：

[1]黃侃．對Snort系統(tǒng)中BM模式匹配算法的研究與改進[J]．網(wǎng)絡安全技術與應用，2014.7:39-40

[2]郝偉臣．Snort規(guī)則分組和映射算法的研究[D]．西安：西安電子科技大學，2014

[3]薛京花．K-means聚類算法在網(wǎng)絡入侵檢測中的應用研究[D]．長沙：中南林業(yè)科技大學，2012

[4]李漢彪，劉淵．一種SVM入侵檢測的融合新策略[J]．計算機工程與應用，2012，48(4)：87-90

[5]楊聰明．基于蟻群聚類的SVM算法在入侵檢測中的應用[D]．南京：南京理工大學，2012

[6]史珊姍．基于決策樹C4.5算法的網(wǎng)絡入侵檢測研究[D]．蘇州：蘇州大學，2012

[7]姚云志，田玉玲．改進的基于人工免疫的入侵檢測模型[J]．計算機應用與軟件，2014，31(1)：308-310

[8]周志凱，張鳳斌，馬天宇．實值形態(tài)空間中基于信息增益的屬性選擇算法[J]．中國科技在線，2014，3(316)：1-9

[9]宋麟．人工神經(jīng)網(wǎng)絡技術在入侵檢測系統(tǒng)中的應用[D]．成都：電子科技大學，2012

[10]李晨光．基于神經(jīng)網(wǎng)絡的入侵檢測技術研究與應用[D]．長春：吉林大學，2013

[11]汪潔，楊柳．基于蜜罐的入侵檢測系統(tǒng)的設計與實現(xiàn)[J]．計算機應用研究，2012，29(2)：667-671

[12]朱紅萍，鞏青歌，雷戰(zhàn)波．基于遺傳算法的入侵檢測特征選擇[J]．計算機應用研究，2013， 29(4)：1417-1419