鄭哲淵，劉 淵

（江南大學 數(shù)字媒體學院，江蘇 無錫214000）

0 引 言

入侵檢測技術［1］（IDS）是一種對入侵行為進行檢測的技術，是包括技術、人、工具3 方面因素的一個整體。但人們大多為了追求IDS的低漏報率，都以犧牲其效率作為代價，這在大規(guī)模大數(shù)據(jù)量的網絡環(huán)境中，無疑是不可取的。所以，研究如何從大規(guī)模告警數(shù)據(jù)中篩選出有用的入侵信息，是當前的關鍵問題。相關研究工作如下：

文獻 ［2］介紹了TACC組件，該組件的中心思想是對告警數(shù)據(jù)中的某一屬性相同的告警的歸并操作，從而降低了告警的數(shù)量，但是對于冗余信息的 “誤報”問題，卻沒有得到解決；文獻 ［3］在TACC組件的基礎上，加入了因果關系的關聯(lián)方法，介紹TIAA，其基本思想是每個攻擊都有前后關聯(lián)，需要分別建立攻擊的前奏和后續(xù)知識庫，通過告警匹配的方法完成關聯(lián)，此方法的缺陷是需要大量攻擊的先驗知識，這就限制了其可擴展性和實時性；文獻［4］介紹了WINEP，其思想是采用短頻繁集遞歸產生長頻繁集的方式，取得了不錯的效果，但是忽略了告警的 “正?！毙袨槟Ｊ?，使得結果會出現(xiàn)偏差；文獻 ［5］提出了A3PC系統(tǒng)，該系統(tǒng)能較好的濾除冗余信息，但是在大規(guī)模數(shù)據(jù)下，其核心算法Apriori［6］由于要多次掃描數(shù)據(jù)庫，會使得系統(tǒng)的性能急劇下降，難以適應信息篩選的實時性要求。

鑒于當前信息篩選方法難以滿足面向大規(guī)模數(shù)據(jù)的實時性處理需求，本文提出面向大規(guī)模告警數(shù)據(jù)的快速篩選系統(tǒng) （rapid screening system for large－scale alarm data，RSS），能快速有效的篩選出有用信息，并為網絡管理者提供宏觀的視圖展示。為提升系統(tǒng)性能，本文重點研究高性能數(shù)據(jù)挖掘算法［7］。

1 面向大規(guī)模告警數(shù)據(jù)的快速篩選系統(tǒng)

經研究表明，根原因 （root cause）會使得IDS產生大量的告警，并且由于根原因的穩(wěn)定性，大量重復性的告警信息會不斷的產生，直至相應的根原因被移除。然而，根原因都是由于用戶或者系統(tǒng)的正常行為產生的，因此產生的告警都可以看成是IDS的誤報。由此，可以得出如下結論：少量的根原因產生絕大部分告警；無論真實攻擊存在與否，告警的產生都有一定的周期性和趨勢性。因此，假設A 為全部告警信息，則存在A 的一個子集A｀，即使在沒有真實攻擊的情況下，也會頻繁或周期性的出現(xiàn)，這部分告警就能看成是由根原因產生的，因此能認為是告警的“正常”行為模式，相對的， （A－A｀）部分的告警能認為是“異?！毙袨槟Ｊ健＿@些 “異?！毙袨槟Ｊ绞蔷W絡安全管理者需要關注的重點，為此本文研究如何從全部告警信息提取出少量的不定期出現(xiàn)的具有 “異常”行為模式的那部分告警，以提升提高IDS的效率，并降低其誤報率。

本文提出的面向大規(guī)模告警數(shù)據(jù)的快速篩選系統(tǒng)（RSS系統(tǒng)）框架如圖1所示。該系統(tǒng)位于IDS的后端，主要目的是從大規(guī)模IDS告警信息中快速有效的篩選出有用的告警信息，提升系統(tǒng)的時效性。系統(tǒng)主要由3部分組成：預處理模塊、實時處理模塊和輸出模塊。

圖1 RSS模型框架

1.1 預處理模塊

Snort［8］是目前運用最廣泛的IDS系統(tǒng)之一，本系統(tǒng)也是基于Snort進行的研究。本系統(tǒng)預處理模塊位于Snort的告警輸出端，對告警數(shù)據(jù)進行預處理。

（1）Snort產生的告警數(shù)據(jù)庫包含Shcema、Sensor、Event、Signature等15張表，每張表中又有若干告警屬性，而其中有些屬性對于告警的后續(xù)處理用處不大，若是全部作為RSS的輸入，會增加系統(tǒng)的開銷?；谝陨峡紤]，預處理模塊對原始告警屬性進行精簡，選取其中一部分屬性進行研究。本文提取了組號、組內編號、告警大類信息、rules種類、源地址、目的地址、源端口、目的端口、時間、協(xié)議等10 個屬性的屬性集，對原始告警進行歸一化處理。

（2）當用戶在短期內進行某些重復操作或是遭受拒絕服務攻擊等情況時，Snort會在段時間內產生大量告警，這些告警的共同特征是除了組內編號和時間這兩個屬性不同之外，其他各屬性均相同，這樣的告警數(shù)據(jù)集合可看成是“同一”告警。當這種告警數(shù)據(jù)大量出現(xiàn)時，就會增大告警數(shù)據(jù)庫的規(guī)模。為了解決此問題，預處理模塊在告警屬性集中增加一個告警條數(shù)屬性，用于表征在一個短時間段內的 “同一”告警的條數(shù)，這樣就將 “同一”告警合并成一條，減小數(shù)據(jù)庫規(guī)模。

1.2 實時處理模塊

實時處理模塊位于預處理模塊后，是對告警數(shù)據(jù)的進一步處理。該模塊分為兩個部分：快速篩選 （rapid screening，RS）子 模 塊 和 實 時 在 線 聚 類 分 析 （real－time online clustering analysis，ROCA）子模塊。

RS是通過高性能數(shù)據(jù)挖掘算法，利用告警數(shù)據(jù)集挖掘得到若干關聯(lián)規(guī)則，然后依據(jù)這些規(guī)則對后續(xù)的告警進行篩選，得到我們需要的具有 “異?！毙袨槟Ｊ降母婢，F(xiàn)在常見的數(shù) 據(jù)挖掘 算法有Apriori、FP－Growth［9］、COFITree［10］等。此外，考慮到告警數(shù)據(jù)流具有實時性，系統(tǒng)定義了關聯(lián)規(guī)則的有效時間，并對數(shù)據(jù)流進行實時抽樣。當規(guī)則失效時，對抽樣得到的小數(shù)據(jù)集進行挖掘，產生新的規(guī)則，以保證關聯(lián)規(guī)則的有效性。

ROCA 模塊布置在RS模塊之后，對篩選出來的告警數(shù)據(jù)進行深入分析，以挖掘其內在聯(lián)系。根據(jù)告警數(shù)據(jù)流的實時性、連續(xù)性和順序性等特性，ROCA 使用了實時在線數(shù)據(jù)流增量聚類方法LOCALSEARCH［11］，使得聚類形態(tài)能實時的反映出數(shù)據(jù)流的變化情況。

1.3 輸出模塊

實時處理模塊最終得到各個聚類的結果，輸出模塊的目的是將這些抽象的聚類結果轉換成精簡的視圖，方便網絡管理者觀察。每一個聚類代表一種可能的攻擊，該模塊任務就是根據(jù)該聚類的特征，如告警個數(shù)、告警屬性等，與攻擊特征庫進行比對，并得到該聚類屬于各種攻擊的可能性 （百分比）。輸出模塊將結果用餅狀圖顯示，讓管理人員直觀看到每個聚類可能存在的攻擊類型，并將每次的結果存入結果數(shù)據(jù)庫，與最近兩次的結果集做比較，按照攻擊種類連續(xù)出現(xiàn)的次數(shù)將其威脅指數(shù)分別定為一級、二級和三級 （三級最高）。按威脅指數(shù)從高到低的排序方式將攻擊類型用表格形式列出，以便管理人員優(yōu)先處理威脅指數(shù)高的攻擊類型。

RSS是針對IDS系統(tǒng)的低漏報率和系統(tǒng)效率之間的矛盾，對IDS告警數(shù)據(jù)進行快速篩選，挖掘其內在聯(lián)系，從大規(guī)模告警數(shù)據(jù)中得到有用的信息。該系統(tǒng)考慮到告警數(shù)據(jù)的實時性，加入了時間有效性；并運用實時的在線聚類分析方法，周期性的挖掘數(shù)據(jù)間的聯(lián)系，確保聚類結果能正確反映當前告警數(shù)據(jù)的特征。RSS系統(tǒng)的開銷主要集中在數(shù)據(jù)篩選的部分，因此數(shù)據(jù)挖掘算法的性能也就直接決定了系統(tǒng)的整體性能。在大規(guī)模告警數(shù)據(jù)的環(huán)境下，數(shù)據(jù)挖掘算法的性能顯得非常關鍵，下面將圍繞與RSS有關的數(shù)據(jù)挖掘算法進行分析研究。

2 若干數(shù)據(jù)挖掘算法比較

由于告警數(shù)據(jù)的大規(guī)模性和實時性，系統(tǒng)在選取數(shù)據(jù)挖掘算法時必須在其時間復雜度和空間復雜度等性能上做綜合評判。本節(jié)就對幾種主流的數(shù)據(jù)挖掘算法進行分析比較，并從中選出適合本系統(tǒng)的算法。

2.1 Apriori算法

Apriori算法由Agrawal R.等在1994年提出，使用逐層搜索的迭代方法找出最大頻繁項集。其算法的基本構造：

（1）遍歷所有數(shù)據(jù)集中的項，找出所有滿足最小支持度 （minsup）的項，組成1－項頻繁集。

（2）從第2步開始，循環(huán)處理直到沒有新的最大項集生成。循環(huán)過程：第K 步中，根據(jù)K－1步中生成的K－1維最大項集按照自連接的方式產生K 維候選項集，然后遍歷D中每個事務，得到各個項的支持度，找出支持度大于minsup的項，組成K 維頻繁項集。

（3）由最小置信度，在最大頻繁集中篩選出關聯(lián)規(guī)則。

顯而易見，該算法在實際應用中存在兩個方面的不足：首先，在每次生成候選項集時，都需要遍歷整個數(shù)據(jù)集，當最大項集的維數(shù)較高時，算法的時間開銷會嚴重增加；其次，當候選項集的規(guī)模很大時，會增加其空間開銷。

2.2 FP－Growth算法

FP－Growth算法是J.Han等人提出的一種不產生候選集頻繁項集生成算法，稱為頻繁模式增長 （Frequent－Pattern Growth）。FP－Growth算法采用頻繁模式樹 （FP－Tree）儲存數(shù)據(jù)集的信息，最大限度的壓縮了數(shù)據(jù)集并保證了數(shù)據(jù)的完整性，然后通過對FP－Tree的一次遍歷，得到最大頻繁集。

算法主要分為兩部分：生成頻繁模式樹 （FP－Tree）和模式增長算法。

2.2.1 構建FP－Tree

輸入：數(shù)據(jù)集 （D）和最小支持度 （minsup）。

輸出：FP－Tree。

方法：

（1）遍歷D，根據(jù)minsup得到1－項頻繁集。

（2）再次遍歷D，將D 中的每個事務 （T）都與1－項頻繁集進行比較，選出T 中屬于1－項頻繁集中的項并按升序排列，得到項集L。將L 中的項與FP－Tree中的節(jié)點元素比較，若相等，則節(jié)點的支持度加1；若不相等，則將該項插入FP－Tree中，并將其支持度置1。如此重復，直至遍歷完整個D，得到完整的FP－Tree。

2.2.2 模式增長

其主要算法思想如下：

輸入：生成的FP－Tree，最小支持度閾值minsup。

輸出：最大頻繁集。

方法：調用FP－Growth （Tree，a）

可見，此算法只需兩次遍歷數(shù)據(jù)集，但是需要不斷的遞歸尋找短模式，然后連接其后綴，最終得到最大頻繁集。

2.3 COFI－Tree算法

COFI－Tree算法同樣基于FP－Tree，并為1－項頻繁集中的每個項都創(chuàng)建一個COFI－Tree，具體算法思想如下：

輸入：FP－Tree，1－項頻繁集。

輸出：最大頻繁集。

方法：

（1）for 1－項頻繁集中的每個項xido｛

（2） 根據(jù)指針找到FP－Tree中的所有xi所在位置，并以它為底自底向上搜索這一支上的所有節(jié)點，同一支上所有節(jié)點的支持度與該支中的xi的支持度一致。然后構造xi的COFI－Tree，根據(jù)minsup得到的結果放入最大頻繁集候選集｝

（3）對最大頻繁集候選集進行查看，若有存在包含關系的項，就進行合并，獲得最大頻繁集。

該算法的特點是某一時間在內存中只有一個COFITree，這樣占用內存空間較小，使得算法運行速度快。

2.4 算法性能比較

本文從空間復雜度和時間復雜度這兩個方面對以上3個算法進行分析。

從時間復雜度的角度，主要看算法遍歷數(shù)據(jù)集的次數(shù)。設1－項頻繁集中項的個數(shù)為L1，數(shù)據(jù)集事務個數(shù)為S，首先，Apriori算法中，需要構造候選項集，對候選項集中的每一項都遍歷數(shù)據(jù)集，其中K 維候選項集的項個數(shù)CK可用 （LK－1－1）LK－1／2大致表示。為了結果表示方便，用C表示候選項集的平均數(shù)，當最大頻繁集的維數(shù)為M，則Apriori算法的時間復雜度可表示為O（M＊C＊N）。其次，F(xiàn)P－Growth和COFI－Tree算法都只需要遍歷數(shù)據(jù)集兩遍，所以它們的時間復雜度可看成是一致的，都是O（N＊L1）。

從空間復雜度的角度，首先給出空間復雜度的定義：空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度。Apriori算法每次只處理一個事務，所以空間復雜度記為O（1）。FP－Growth 需要要遞歸建立條件FPTree，要用到臨時堆棧存儲數(shù)據(jù)，其空間復雜度記為O（N）。COFI－Tree同一時間在內存中只需要建立一棵COFITree，所以空間復雜度是O（1）。

由表1，從時間復雜度來看，F(xiàn)P－Growth和COFI－Tree算法至少要比Apriori算法低一個數(shù)量級；從空間復雜度來看，F(xiàn)P－Growth要比其他兩種算法高。因此，相比之下，COFI－Tree算法在綜合性能方面要優(yōu)于其他兩種算法。

表1 數(shù)據(jù)挖掘算法的復雜度比較

3 實驗驗證與分析

3.1 實驗環(huán)境

為了驗證不同算法運用于RSS上的性能差異，本文在CentOS 5.3 上 進 行 測 試，測 試 環(huán) 境 為DELL 服 務 器（CPU：E5520 2.27GHz＊16，內存：8G）。本實驗使用的是MIT Lincoln實驗室開發(fā)的DARPA 1999年IDS測試數(shù)據(jù)集，該數(shù)據(jù)集包含了5周的測試數(shù)據(jù)，其中包括不含任何攻擊的正常數(shù)據(jù)和包含多種攻擊類型的攻擊數(shù)據(jù)。這也使得實驗環(huán)境更貼近實際的網絡環(huán)境，所以也保證了測試結果的正確性。

利用Snort 的默認規(guī)則分別對這五周的outside.tcpdump測試文件進行檢測，得到相應的告警數(shù)據(jù)集，并在不同告警數(shù)的情況下在RSS中分別使用Apriori算法和COFI－Tree算法進行測試，并從時間、CPU 利用率、內存占用率等方面對系統(tǒng)性能進行測試。

3.2 實驗結果分析

本實驗運用了前二周、前三周和前五周的outside.tcpdump產生告警 數(shù)據(jù)集，分別得到2.5 萬、13.8 萬和16.2萬的告警數(shù)據(jù)。圖2、表2和表3分別是當告警數(shù)不同情況下Apriori算法和COFI－Tree算法對CPU 的占用率、系統(tǒng)時間的開銷和系統(tǒng)內存消耗的對比。

圖2 CPU 占用率比較

由圖2可看出，COFI－Tree算法在計算時CPU 的占用率明顯比Apriori算法低很多。

表2 時間開銷比較

表3 內存開銷比較

表2和表3分別從時間和空間開銷將兩算法進行了對比，結果顯而易見，COFI－Tree在時間開銷上遠比Apriori算法要少，且隨著告警數(shù)量的增加基本維持在1 秒左右，而Apriori算法隨告警數(shù)量的增加時間的開銷也隨之增加，且漲幅很大，最后已經接近2000 秒；空間開銷方面，COFI－Tree算法的優(yōu)勢也是很明顯。

表4為兩種算法在不同告警數(shù)量的情況下得到的最大頻繁項集，括號內的是項的支持度。比較后可得出，使用Apriori算法和COFI－Tree算法的結果近似完全一致。

表4 最大頻繁集比較

由上分析可得，無論是從CPU 占用率、時間開銷還是空間開銷的角度，COFI－Tree算法都比Apriori算法有著明顯的改進，且最后得到的最大項集基本一致。由此，充分說明了基于COFI－Tree算法的RSS系統(tǒng)具有高性能。

4 結束語

本文提出了一種位于IDS后端的通用系統(tǒng)RSS，主要是對告警數(shù)據(jù)進行篩選并挖掘出其內部聯(lián)系，最后利用精簡的視圖展現(xiàn)結果。相對于以往的IDS系統(tǒng)為了降低漏報率而犧牲效率的做法，本系統(tǒng)在保證了IDS的低漏報率的情況下，對系統(tǒng)的效率進行提高。同時，從時間和空間復雜度這兩個方面分析了幾種數(shù)據(jù)挖掘算法性能上的差異，從理論上證實了COFI－Tree的優(yōu)越性。并且結合現(xiàn)在大規(guī)模告警數(shù)據(jù)的環(huán)境，分別將Apriori算法和COFI－Tree算法用于本系統(tǒng)，在兩者實驗結果基本相同的情況下，使用COFI－Tree的系統(tǒng)在時間開銷和空間開銷上都有明顯改善。

［1］CAI Hongmin，WU Naiqi，CHEN Su，et al.Research and implement of distributed intrusion detection system ［J］.Computer Engineering and Design，2009，30（6）：1383－1386 （in Chinese）.［蔡洪民，伍乃騏，陳素，等.分布式入侵檢測系統(tǒng)的研究與實現(xiàn)［J］.計算機工程與設計，2009，30（6）：1383－1386.］

［2］Alexander Hofmann，Bernhard Sick.Online intrusion alert aggregation with generative data stream modeling ［J］.IEEE Transactions on Dependable and Secure Computing，2011，8（2）：282－294.

［3］Ganapathi Reddy K L，Srinivas K.GDS－an efficient approach for online intrusion alert aggregation ［J］.International Journal of Computer Application，2012，2 （1）：131－139.

［4］Kimmo H¨at¨onen.Data mining for telecommunications network log analysis ［M］.Department of Computer Science Series of Publications，2009.

［5］TIAN Zhihong，ZHANG Yongzheng，ZHANG Weizhe，et al.An adaptive alert correlation method based on pattern mining and clustering analysis［J］.Journal of Computer Research and Development，2009，46 （8）：1304－1315 （in Chinese）.［田志宏，張永錚，張偉哲，等.基于模式挖掘和聚類分析的自適應告警 關 聯(lián) ［J］. 計 算 機 研 究 與 發(fā) 展，2009，46 （8）：1304－1315.］

［6］CUI Guanxun，LI Liang.Research and improvement on Apriori algorithm of association rule mining［J］.Journal of Computer Applications，2010，30 （11）：2952－2955 （in Chinese）.［崔貫勛，李梁.關聯(lián)規(guī)則挖掘中Apriori算法的研究與改進 ［J］.計算機應用，2010，30 （11）：2952－2955.］

［7］WANG Aiping，WANG Zhanfeng.Common algorithms of association rules mining in data mining ［J］.Computer Technology and Development，2010，20 （4）：105－108 （in Chinese）. ［王愛平，王占鳳.數(shù)據(jù)挖掘中常用關聯(lián)規(guī)則挖掘算法 ［J］.計算機技術與發(fā)展，2010，20 （4）：105－108.］

［8］Go＇mez J，Gil C，Padilla N，et al.Design of a snort－based hybrid intrusion detection system ［C］／／Proceedings of the 10th International Work－Conference on Artificial Neural Networks，2009：515－522.

［9］Wang Lei，F(xiàn)an Xingjuan.Mining data association based on a revised FP－growth algorithm ［C］／／IEEE Conference Publications，2012：91－95.

［10］Virendra Kumar Shrivastava，Dr Parveen Kumar.FP－tree and COFI based approach for mining of multiple level association rules in large databases［J］.International Journal of Computer Science and Information Security，2010，7 （2）：273－279.

［11］Wu Ou，Hu Weiming.Efficient clustering aggregation based on data fragments［J］.IEEE Transaction on Systems Man and Cybernetics Part B－Cybernetics，2012，42 （3）：913－926.