基于非監督學習的入侵分析新方法

摘要：提出一種新的基于非監督學習的入侵分析方法。該方法具有發現未知攻擊類型的能力，既可以作為獨立的分析方法使用，又可以作為基于數據融合的入侵檢測的一個分析引擎。在該方法中，核心非監督學習算法采用最大最小距離算法，同時融合非線性的歸一化預處理和非數值型特征的有效編碼等技術。與同類方法相比，該方法檢測率較高，尤其是對于DoS和Probing兩大類攻擊效果更好。

關鍵詞：入侵檢測； 非監督學習； 機器學習

中圖分類號：TP309文獻標志碼：A

文章編號：1001－3695(2007)07－0146－05

0引言

入侵檢測是對計算機系統攻擊行為的檢測。攻擊定義為試圖滲透系統或繞過系統安全策略獲取信息，更改信息或者中斷目標網絡或系統正常運行的活動。入侵檢測系統（Intrusion Detection System）能實時監控系統的活動。及時發現攻擊行為并采取相應的措施，以避免攻擊的發生或盡量減少攻擊造成的危害。

傳統的入侵分析技術分為濫用檢測和異常檢測。濫用檢測(Misuse Detection)主要利用收集到的已知入侵或攻擊的相關知識(入侵攻擊的特征、模式等)來檢查系統中是否出現這些已知入侵攻擊的特征和模式，并據此判斷系統是否遭受到攻擊。異常檢測(Anomaly Detection)主要為被監控的信息系統構造一個關于系統正常行為的參考模型(有關用戶、系統關鍵程序等的特征輪廓)，然后檢查系統的運行情況，若與給定的參考模型存在較大的偏差，則認為系統受到了入侵攻擊。目前已有大量文獻對單一的入侵分析技術進行了討論，具有代表性的有：

（1）基于規則匹配的濫用檢測方法[1]。對數據包進行基本協議解碼后結合數據包數據區的內容匹配來檢測攻擊。其缺點是不能有效檢測已知攻擊的變種或未知攻擊。

（2）基于狀態轉換的入侵檢測方法（包括以狀態圖、Petri網表示）[2，3]。將入侵表示為一系列的狀態轉換，當特征行為發生時，狀態發生轉移。如果到達危險狀態，表示當前可能正在發生入侵事件。其缺點是復雜應用狀態遷移難以表示，而且存在狀態組合爆炸的可能。

（3）基于層次樹的入侵檢測方法[4]。使用攻擊樹來表示攻擊。樹的根節點表示最終的入侵目標，節點則表示取得上級節點入侵目標的方法。有自己的攻擊模型語言。其難點在于樹結構的建立依賴于經驗模式。

（4）基于統計異常的檢測方法[5]。根據統計模型中各測量值，以用戶當前行為比較長期行為，發現異常。其缺點是存在入侵者“有意”訓練的可能性，誤報率高。

（5）基于貝葉斯推理的異常檢測方法[6]。通過在任意給定的時刻，測量A1，Ai，…，An變量值。根據貝葉斯公式推理判斷系統中入侵事件發生的概率。其中每個A變量表示系統不同方面的特征。其缺點是假設條件難以滿足，要考慮各個變量Ai之間的獨立性。

（6）基于貝葉斯網絡的異常檢測方法[7]。通過建立異常入侵檢測貝葉斯網，將其用做分析異常測量結果。其難點是貝葉斯網絡圖中的節點和弧難以確定。

（7）基于非監督學習的異常檢測方法。通過在數據中發現不同類別的數據集合來區分異常用戶類，進而推斷入侵事件的發生，檢測異常入侵行為。其缺點是異常閾值難以確定，在線處理速度有待提高，數據流之間的時間關系難以反映在模型中。

（8）基于數據挖掘的異常檢測方法[8，9]。使用數據挖掘算法從審計數據或數據流中提取感興趣的知識去檢測異常入侵和已知的入侵。其缺點是通用模型難以建立，檢測的實時性難以滿足。

（9）基于系統調用的異常檢測方法[10]。監視進程使用的系統調用，—個程序的正常行為由短序列來表征，與這些模式的偏離可認為是入侵。其缺點是不能適應用戶經常更改其工作的習慣。

（10）基于神經網絡的入侵檢測方法[11]。利用神經網絡檢測系統的審計數據，通過自學習從中提取正常的用戶或系統活動的特征模式，獲得預測的能力，對偏離系統正常工作的事件作出反應。但該方法要求訓練數據集純凈，可移植性差。

（11）基于專家系統的入侵檢測方法[12]。針對有特征的入侵行為，利用專家系統進行推理。其難點是專家系統知識庫的完備性。

（12）基于代理的入侵檢測方法[13]。利用Agent的分布、可移動及自治，多點協作檢測入侵行為。其具有靈活性、魯棒性、可擴展性。但需要一定的網絡環境，且技術不成熟。

（13）基于免疫的入侵檢測方法[14，15]。將生物學的人體免疫機理用于計算機的自適應入侵檢測和響應，其整個體系還不成熟。

在入侵分析技術中，濫用檢測根據已知的特征或規則匹配來檢測入侵。雖然其具有較低的誤警率，但它不能檢測出新出現的一些入侵行為，故漏報率也較高。異常檢測一般通過對歷史數據的訓練學習，從中發現正常使用行為模式，以定量的統計方式描述可接受的行為特征，并由被檢測數據和正常行為模式的偏差捕獲到異常，以區分非正常的、潛在的入侵行為。通過檢查與正常行為相違背的行為，異常檢測能夠發現一些新的未知的入侵。但由于其正常行為模型的建立完全依賴于對訓練數據集中正常數據樣本的學習，所以保證該數據集的潔凈性對建立一個實用的入侵檢測系統是至關重要的。而實際上，要為系統的學習收集這樣一個潔凈數據集往往是不太容易的，一旦有入侵數據被作為正常數據出現在訓練數據集中，必然導致該類入侵行為及其變種均將被系統視為正常數據，這也是將神經網絡等技術用于入侵檢測的一個癥結。

針對以上技術的不足，目前研究人員開始考慮高層次的集成多入侵分析技術的系統，如DARPA的研究項目EMERALD集成入侵特征識別和異常檢測技術協同進行分析，每個模塊都可重復使用和分層協作[16]；DARPA的研究項目JAM應用分布式Agent的學習算法構造下一代入侵檢測系統[17]，每個Agent在不同的數據源上分布式Meta－learning學習，并且每個Agent的知識均共享，進行數據挖掘。

本文另辟蹊徑，設計并實現了一種新的基于非監督學習的入侵分析方法。該方法能處理不帶標志且含異常數據樣本的訓練集數據，分類過程無須手工干預，可以在較低的誤警率下檢測出新的攻擊類型，降低了對訓練數據集的要求。它既可以作為獨立的分析方法使用，又可以作為基于數據融合的入侵檢測的一個分析引擎。

1基于非監督學習的入侵檢測方法

基于非監督學習的入侵分析方法屬于異常檢測方法。與有監督學習相比，非監督學習的識別率要低一些，但因其可以發現數據中的隱性模式，具有發現未知相似類型的能力。模式識別過程如圖1所示。

在這里信息獲取是指以任何可能的手段從網絡或主機獲得原始數據。在將數據加工成一定表達方式的特征后，需要對特征進行一系列的預處理工作，包括特征的選擇、加權、標準化等。接下來選擇一定量的樣本，使用一種非監督學習算法訓練以形成分類器。最終形成的分類器就可以按照一定的準則用于檢測數據流中的異常樣本。其中非監督學習訓練的過程可以是在線的，也可以是離線的；非監督學習訓練的過程和檢測的過程可以是并行的。

1．1特征的選擇

該方法并不是將已經提取出的樣本的所有特征直接使用，而較多使用對分類有利的特征，避免使用對正確分類造成干擾的特征。信息論中的熵值理論有助于特征選擇。熵是不確定性的一種度量，熵值越小，不同類別的分離程度越大。從特征提取角度看，顯然用最小不確定的那些特征，即熵值最小的特征進行分類是有利的。本文選取KDD99[18]的所有訓練樣本為數據集，經過兩個星期的測試，對38維數值特征測得熵值（表1）。

可以看出，各個特征的熵值差別不是很大，比較集中。在相同條件下，對使用全部特征和只使用熵值小于15的特征進行了實驗，發現其結果非常接近。同時考慮到熵值法對訓練集的依賴性、樣本的可重復性等因素，本文使用全部特征。當然，測出的各特征的熵值并不是沒有用，它們將參與特征的加權。

1．2特征的標準化和加權

在數據集中由于各個特征具有不同的物理含義和具有不同的量綱，其取值范圍大不相同。例如生存期（Duration）最大值可達57 715，而Urgent數據包的個數只在0~10。如果沒有標準化的處理，在非監督學習過程中前者的影響足以淹沒后者。在處理數據之前必須對數據進行標準化。

利用標準化公式進行標準化工作[19]：

通過計算每個特征值與平均值之間的標準偏差得到該特征值在歸一化空間中的新值。

為了加大有利特征參與計算的比重，該方法引入特征加權。加權信息來源于領域知識和上一步的特征熵值?？梢詫⑻卣鞣譃橹匾?、較重要、普通三個等級，并分別加以權重。

1．3核心非監督學習算法

訓練集中經過預處理的樣本就可以直接用于分類器的生成。這一過程就是非監督學習的過程，是整個訓練過程的核心。非監督學習算法決定了最終的分類效果。核心算法是基于關鍵元素試探的非監督學習算法——基于最大最小距離的非監督學習算法。

1．4類型標定

一般的分類過程到這一步均是按照一定的準則為每一個類貼上相應的類標簽，但在這里訓練集可能包含未知的、新的入侵數據，而且訓練集的分布可能隨環境的不同而有所不同，所以不可能一一確定地給出每一個類的類標簽，這樣會限制該方法發現未知攻擊的能力。

假設在采集的訓練數據集中，正常行為的類及其子類數據在數量上將遠遠大于各種體現攻擊行為的類及其子類數據。這樣，非監督學習算法所得到的類劃分就能夠幫助區分正常與異常類。一種作法就是將所有的類按其中包含的數據量大小排列，并設定一個比例數N，那些位于N以上的包含最多數據量的類被判斷為正常類，而其余的類則被認為是異常類。用這種方法會出現一個問題，其有效性依賴于在訓練集中有多少正常實例的子類。舉一個例子，也許有許多不同類型的正常網絡活動，比如使用不同的FTP協議、遠程通訊網、萬維網等。這些應用的每一種均有可能在特征空間中有自己的獨特點，其實例將傾向于非監督學習在一起。這樣可能分別產生大量的正常的非監督學習，每一個代表一種正常類型的網絡使用。這些非監督學習的每一個均擁有相對小數量的與之相關聯的數據實例——甚至少于包含攻擊數據實例的非監督學習，那么，這些正常的非監督學習就被誤分類為異常。因此，需要盡量增大各類正常數據的容量，確定正常數據實例在訓練集中的百分比相對于異常攻擊占絕對優勢。這樣，每一種類型的正常網絡應用才可能相對于每一種攻擊的子類型有足夠的代表。

1．5檢測

一旦從訓練集中創建好分類器(該分類器有自己的標簽和非監督學習中心點)，系統就為執行入侵檢測做好了準備。檢測入侵其實也就是數據分類的過程，給定一個實例d（該實例就是從被測試集中取出的），分類按如下過程進行：

（1）根據創建非監督學習的訓練集的統計信息對d進行轉變（即預處理），轉變后的數據實例為d′；

（2）找到與d′最近的非監督學習（也就是說，在非監督學習集中有一個非監督學習C，在S中的所有C′，均有dist(C，d′)≤dist(C′，d′));

（3）按照C的標志分類d′（是正?；蛘卟徽＃?。

在第（1）步中有效地將d轉換到了訓練集空間，這樣做是為了使被檢測樣本在相同的尺度下與訓練樣本集的比較有意義。

對上述步驟的一種改進就是找到k個與d′距離最小的非監督學習，如果在這k個類中，有半數以上的類為正常類，則判斷該連接數據為正常連接；否則，判斷其為異常。為避免得到的正常類數目與異常類數目相同，k值一般取為奇數常量。當然在實時檢測過程中也可以只選擇最近鄰的一個類，并將當前數據劃分到該類中。但考慮到數據類分布可能存在的不準確性以及訓練數據集與測試數據集之間數據分布可能存在的偏差，選擇最近鄰的k個類，能在統計意義上盡量減少這些問題造成的不利影響。在本系統中k一般取3或5。

2系統設計及實現

整個系統是在Windows平臺下使用C++與MSSql完成的。數據庫的支持有利于對KDD99數據集的靈活使用。系統按功能主要分為五大模塊：

（1）數據構造模塊。根據KDD99數據集靈活構造訓練數據集和檢測數據集，可以定制樣本總容量、攻擊類型總數、各種攻擊的容量。

（2）數據訓練模塊。選擇一定的訓練集，定制參數，按照算法流程生成分類器。可定制的選項包括初始點設置（默認點、隨機、指定點）、參數a設置、特征加權（默認、全1、指定）、距離公式設置（歐氏距離、馬氏距離）。

（3）數據檢測模塊。設置檢測閾值，選擇已有的分類器對任意的檢測集進行檢測。

（4）融合仿真模塊。將基于非監督學習的分析與基于規則匹配的分析融合檢測，并比較分析結果（該模塊用于下文的基于數據融合的入侵檢測）。

（5）數據統計模塊。對各次訓練和檢測的結果進行分析比較。

系統的存儲設計是對大量數據管理和存儲方式的選擇，包括兩部分，即非數據庫與數據庫。

①非數據庫。在該系統中訓練集中樣本的樣本距離矩陣采用在內存中的下三角矩陣存儲方式，主要是為了能以最快的速度進行距離運算，并減少存儲，動態釋放資源。

②數據庫。數據庫庫表的設計主要分兩類，即數據管理表和數據表。數據管理表以圖3中的第六張為主，主要責任是管理各類數據并協作前臺程序執行算法；數據表主要是存儲各類數據，如各類攻擊數據、一次訓練的分類器的詳細數據等。

如圖3所示，主要的管理表使用流程如下：由TrainingSourceSets負責管理訓練集。訓練時由TrainingSourceSets選擇訓練集，將訓練集導入SourceTemp，進行歸一化，將歸一化的數據放入NormalizationTemp中；按照選擇的非監督學習方法訓練，將結果存入TraingResultTemp，如果需要保存訓練結果，則自動命名保存，由TraingResultSets統一管理。檢測時由Traing－ResultSets選擇分類器，需要用到TrainingSourceSets中的均值和方差（視不同的歸一化方法而有所不同）；如果需要保存檢測結果，則自動命名保存，由DetectionResultSets統一管理。

訓練集的樣本數以1 000、2 000或5 000為單位，訓練集的構造符合正常數據占絕對優勢的假設，即正常數據占95％~98％。檢測集的構造一般與訓練集分布相同，即入侵的種類數與總量相同，但樣本個體均隨機產生，以保證實驗的有效性。筆者所做的各種預處理工作都是為了使樣本在特征空間的可分離性更大，并能合理地表現入侵檢測的物理含義。

在相同的參數下，對入侵進行分類和不分類的測試。分類測試仍然按照KDD99分為四大類。

從圖4、5可以看出，隨著檢測閾值的調整檢測率和誤警率的變化趨勢是一致的，這也符合檢測率的提高必然伴隨著誤警率上升的原理。綜合比較可以看出，對DoS和Probing兩大類攻擊的性能明顯比另外兩大類要好。誤警率低于2%的系統在實際當中才有可用性。在較低的誤警率下，對DoS的檢測率最穩定，對Probing的檢測率最高。而U2R類的攻擊最容易產生誤警。當前DoS攻擊是攻擊后果較為嚴重而為大家研究重點的一類，對其檢測的穩定性為本系統的進一步發展提供了方向。

同時，本文也對無分類的攻擊作了大量實驗。在誤警率低于2%的情況下，檢測率在39．625%~81．7%。其特點在于穩定性不如分類測試，檢測率會隨著訓練集的不同（實際上是樣本的分布不同）而有所差異。其原因可能是某種攻擊類型對其他的攻擊類型的分類造成了干擾所致，需要進一步分析。但就總體性能來講，與文獻[20]中所設計的方法相比，本文的系統性能更好。表2列出了兩種方法的詳細比較。

本文也考慮了訓練集樣本容量對算法的影響，分別對樣本容量為1 000、2 000、5 000的同類型數據集進行了測試，結果顯示其影響非常小，可以忽略不計，這也顯示了系統另一個方面的穩定性。

入侵檢測系統的一個非常重要的特性就是對實時性的要求很高。系統的精度再高，事后分析的延遲超過一定的限度對用戶來說也是無用的。對于基于非監督學習的入侵檢測而言，需要分別考慮其訓練的實時性和檢測的實時性。

（1）訓練的實時性。分別對樣本容量為1 000、2 000、5 000的訓練集作了整體性測試，如圖6所示。

可以看出，樣本容量為1 000時訓練耗時為2min40s，而增加到2 000時已經需要16min。訓練時間是隨著樣本容量的增加而呈指數級增長。就算以最低的樣本容量訓練也遠不能達到實時的要求。進一步分析發現大部分時間都用來進行距離矩陣的運算，實際最大最小距離算法的單次迭代花費小于2s。從程序的編寫角度還可以提升20 %以上的速度。例如，距離在首次使用時計算；數據庫的查詢速度可以提升；數值預處理以后無須開方運算。另外，由以上分析可知，在“實時采集，實時訓練，實時檢測”的系統中，訓練樣本的采集不要批量而是一條條的采集，采集到一條就立刻計算相關的距離值，即將集中計算距離矩陣的時間分散開。這樣總體的訓練時間可以降到5s以下，達到接近實時訓練的要求。

3結束語

本文提出的一種新的基于非監督學習的入侵分析方法。下一步的工作中，要進一步完善整個框架，提高基于非監督學習的檢測方法在線學習的穩定性；并爭取引入其他類型的分析引擎進行融合，提高反饋控制的精確性。

參考文獻：

[1]GARG S， MORRSEL A V. A methodology for detection and estimation of software aging: proc.of the 9th Intnl. Symposium on Software Reliability Engineering[C]. Paderborn，Germany:[s.n.]， 1998:282－292.

[2]BUYYA R. PARMON: a portable and scalable monitoring system for clusters[J]. Software Practice and Experience Journal， 2000，30(7):723－739.

[3]SOTTILE M， MINNICH R. Supermon: a high－speed cluster monitoring system: proc.of IEEE Intl. Conference on Cluster Computing[C].[S.l.]:[s.n.]， 2002.

[4]AGARWALA S， POELLABAUER C， KONG J， et al. Resource－aware stream management with the customizable dproc distributed monitoring mechanisms: proc.of the 12th IEEE International Symposium on High Performance Distributed Computing[C]. Seattle，Washington:[s.n.]， 2003:250－259.

[5]HARRIS B， HUNT R. TCP/IP security threats and attack methods[J]. Computer Communications， 2002，10:885－897.

[6]SKOUNDRIANOS E N， TZAFESTAS S G. Flow－fault forecast via local neural networks[J]. Mathematics and Computers in Simulation， 2002，60:169－180.

[7]BULLELL P， INMAN D. An expert system for the analysis of faults in an electricity supply network: problems and Achievements[J]. Computer in Industry， 1998，37:113－123.

[8]TAGLIAFERRI R， ELEUTERI A， MENEGANTI M， et al. Fuzzy min－max neural network: from classification to regression[J]. Soft Computing， 2001，5:69－76.

[9]GAVALAS D， GREENWOOD D， GHANBBARI M. Advanced network monitoring applications based on mobile/intelligent agent technology[J]. Computer Communications， 2002，23:720－730.

[10]LI Qianmu， XU Manwu， ZHANG Hong， et al. A new method of network data link troubleshooting[J]. Lecture Notes in Computer Science， 2005，3758（11）:890－900.

[11]LI Qianmu， XU Manwu， ZHANG Hong， et al. Neural network based flow forecast and diagnosis[J]. Lecture Notes in Artificial Intelligence， 2005，3734（12）.

[12]LI Qianmu， XU Manwu， ZHANG Hong， et al. Web classification based on latent semantic indexing[J]. Journal of Communication and Computer， 2006，3(1).

[13]李千目，戚湧，劉鳳玉.一種改進的基于系統調用的入侵檢測技術[J].小型微型計算機，2004，25(7):1351－1384.

[14]李千目，戚湧，張宏，等.IIDS行為特征提取方案研究[J]. 南京理工大學學報：自然科學版，2004，28(2):140－144.

[15]劉鳳玉，李千目，衷宜.基于貝葉斯分類的分布式網絡故障診斷模型[J].南京理工大學學報:自然科學版，2003，27(5):546－550.

[16]李千目，張琨，張宏，等.一種基于生物免疫學的入侵檢測系統[J].計算機工程與應用，2003，39(8):45－48.

[17]李千目，戚湧，汪洋，等.基于多代理的網絡故障檢測新方法[J].兵工學報，2005，26(5):675－680.

[18]李千目，許滿武，楊云，等.一種新的網絡故障診斷方法——FTFD[J].計算機研究與發展，2005，42(11):1928－1933.

[19]李千目，戚湧，張宏，等.基于粗糙集神經網絡的網絡故障診斷新方法[J].計算機研究與發展，2004，41(10):1696－1702.

[20]李千目，游靜，張宏，等.一種數據鏈用戶保障策略研究與設計[J]. 北京航空航天大學學報，2004，30(11):1029－1032.

[21]徐永紅，楊云，李千目，等.確保最小發送速率的TCP友好擁塞控制算法[J].通信學報，2003，24(10):131－138.

[22]LIPPMANN R， HAINES J W， et al. The 1999 DARPA off－line intrusion detection evaluation[J]. Computer Networks， 2000(34):579－595.

[23]LIAO Yihua， RAO V. Vemuri use of k－nearest neighbor classifier for intrusion detection[J]. Computers Security， 2002，21(5):439－448.

[24]LIAO Yihua， RAO V. Vemuri use of text categorization techniques for intrusion detection[D]. California: Department of Computer Science University of California， 2002.

[25]VERWOERD T. Ray hunt intrusion detection techniques and approaches[J]. Computer Communications， 2002(25):1356－1365.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”