基于ＡＬＴ算法的入侵檢測分析系統(tǒng)的研究

[摘 要] 針對關聯(lián)規(guī)則挖掘算法在處理海量數(shù)據(jù)的過程中存在的效率低、需要反復訪問數(shù)據(jù)庫等，在入侵檢測系統(tǒng)產生誤報、效率低下等問題。提出了基于關聯(lián)規(guī)則挖掘算法的ALT算法，設計了基于ALT算法的入侵警報檢測系統(tǒng)模型，通過實驗證明ALT算法在減少入侵警報的數(shù)量和降低誤報率等方面明顯優(yōu)于其它算法。

[關鍵詞] ALT算法 入侵檢測 數(shù)據(jù)挖掘 警報分析

引言

入侵檢測技術是信息網絡安全技術的重要組成部分，而數(shù)據(jù)挖掘本身是一項通用的知識發(fā)現(xiàn)技術，目的是從海量數(shù)據(jù)中提取出對解決問題感興趣的數(shù)據(jù)信息 。Wenke Lee于1999年首次將數(shù)據(jù)挖掘技術引入入侵檢測，提高入侵檢測系統(tǒng)(IDS)的準確性和自適應性。近年來，由于入侵檢測技術對實時性要求較高，傳統(tǒng)的IDS效果都不明顯。這里提出一種改進的高效關聯(lián)挖掘算法——ALT算法，將其應用到入侵警報分析過程中，在保證入侵檢測實時性的前提下，減少侵警報的數(shù)量、降低誤報率，最終達到提高入侵檢測性能的目的。

一、ALT算法原理

ALT算法原理在于先求取所有的最大頻繁項目集，然后依次求取每一個最大頻繁項目集的子集，從而得到頻繁項目集。

ALT算法求最大頻繁項目集如下：

輸入：事務數(shù)據(jù)庫，最小支持度；

輸出：最大頻繁項目集(Answer)。

(1)計算最小支持計數(shù)，最小支持計數(shù)(Minsup)＝最小支持度×事務數(shù)；(2)生成頻繁1-項目集L，及其對應的鏈表族；(3)依次處理頻繁K-項目集對應的鏈表，據(jù)此得到最大頻繁項目集。

通過頻繁項目集分析，發(fā)現(xiàn)其中隱藏的異常模式，進而進行入侵檢測。

1.關聯(lián)規(guī)則挖掘。關聯(lián)規(guī)則挖掘算法中，最有影響的是Agrwal和Srikant于1994年提出的Apriori算法。但缺陷也十分明顯。針對Apriori算法的缺陷，文獻提出FP2Growth算法。該算法采用分而治之策略，將發(fā)現(xiàn)長頻繁模式的問題轉換為遞歸發(fā)現(xiàn)一些短模式。把數(shù)據(jù)庫中的頻繁項集壓縮進一棵頻繁模式樹( FP2tree) 并分化成條件庫，對這些條件庫分別進行挖掘，大大降低了搜索開銷，大約比Apriori算法快一個數(shù)量級。

2.ALT算法思想及實現(xiàn)步驟。ALT算法的基本思想是該算法只需遍歷事務數(shù)據(jù)庫一次，生成頻繁項目集簇，采用鏈表簇數(shù)據(jù)結構來存貯，通過指針來鏈接簇中的下一鏈表，生成新的頻繁項目集……。大大降低了算法存儲結構的復雜度，提高算法的挖掘效率。其實現(xiàn)步驟如下：

首先，對事務數(shù)據(jù)庫進行處理，遍歷事務數(shù)據(jù)庫一次，生成頻繁1-項目集。并由此可以得到頻繁2-項目集，頻繁3-項目集，……，頻繁k項目集。

其次，對于頻繁i(1≤i≤k)-項目集，采用鏈表簇數(shù)據(jù)結構存貯。簇中的每一鏈表用來表示頻繁i-項目集各項目的信息，表頭節(jié)點(patternData)和表節(jié)點(tidData)存儲結構如圖1所示。

再次，對項目集簇進行處理。如圖1所示，處理完一個項目集，用pattern來存儲頻繁i-項目集某一項目，通過nextL指針來鏈接簇中下一鏈表； 用newed來標示項目集pattern域是否生成了新的頻繁項目集，同時也作為最大頻繁項目集判斷條件。

最后，求最大頻繁項目集，獲取頻繁項目集。初始值置為1，若由pattern域產生了新的頻繁項目集，其值變?yōu)閠rue，當新的頻繁K+1項目集的鏈表族生成后，若某頻繁k項目集對應newed域值仍然為1，則該頻繁-k項目集鏈表對應的pattern域值為一最大頻繁項目集。依次求取每一個最大頻繁項目集的子集，從而得到頻繁項目集。

二、系統(tǒng)設計與實現(xiàn)

1.系統(tǒng)設計思想。入侵警報分為正常警報和異常警報，本文提出的ALT算法入侵檢測分析系統(tǒng)是利用數(shù)據(jù)挖掘算法從正常警報數(shù)據(jù)中提取描述正常警報行為模式的關聯(lián)規(guī)則，通過分析入侵警報，提取出真正攻擊的異常警報，減少入侵檢測系統(tǒng)的警報數(shù)量，降低誤報率。最終生成相應的頻繁項目集和關聯(lián)規(guī)則，數(shù)據(jù)挖掘過程的流程圖如圖2所示。

2.系統(tǒng)框架結構?；谏鲜龅脑O計思想，入侵分析系統(tǒng)模型包括警報采集模塊、提取模塊、預處理模塊、數(shù)據(jù)挖掘模塊和分析模塊。利用關聯(lián)規(guī)則挖掘算法對入侵檢測系統(tǒng)產生的警報數(shù)據(jù)進行過濾，提取出包含攻擊的入侵警報，以達到減少警報數(shù)量、降低誤報率的目的。系統(tǒng)總體框架如圖3所示。各模塊功能如下:

(1)采集模塊。將網卡置于混雜模式，捕獲并分析網絡數(shù)據(jù)包，對異常的數(shù)據(jù)存入警報數(shù)據(jù)庫并報警產生的警報。(2)提取模塊。從警報數(shù)據(jù)庫中提取出系統(tǒng)需要的字段。(3)預處理模塊。對提取的警報數(shù)據(jù)對應的IP地址由數(shù)值型轉化為點分十進制的標準IP地址格式，將協(xié)議由數(shù)值型轉化為可讀性較好的字符串表示。(4)數(shù)據(jù)挖掘模塊。利用ALT算法挖掘經過預處理的正常警報數(shù)據(jù)，生成相應的頻繁項目集。(5)分析模塊。分析、判斷警報是否正常，若正常，利用數(shù)據(jù)挖掘模塊更新關聯(lián)規(guī)則集，否則存入異常警報數(shù)據(jù)庫并報警。

三、實驗結果和分析

1.算法執(zhí)行效率模擬實驗。為了說明ALT算法的執(zhí)行效率，本文在同樣的實驗環(huán)境下將其與Apriori、FP2Growth算法進行了比較。

實驗環(huán)境: P4 3.0 GHz處理器， 320 GB硬盤， 512MB內存，Windows XP操作系統(tǒng)，VC++6.0開發(fā)環(huán)境，實驗數(shù)據(jù)集T10 I4D100K。算法執(zhí)行時間對比結果如表1所示，對比結果可以看出，在相同的支持度下， ALT算法所用的執(zhí)行時間比其他算法要少(尤其是在支持度較小的情況下) 。因此算法在執(zhí)行效率方面具有明顯的優(yōu)勢。

2.系統(tǒng)模擬實驗。實驗數(shù)據(jù)采用林肯實驗室的DARPA99入侵檢測評估數(shù)據(jù)集在LAN中進行，運行Snort的主機配置同3.1。前臺開發(fā)環(huán)境采用VC++6.0企業(yè)版，后臺數(shù)據(jù)庫采用SQL2000。實驗結果如表2所示。其中Original表示直接由入侵檢測系統(tǒng)產生的警報數(shù)量，Abnormal表示經過警報分析處理后的警報數(shù)量。從圖示的實驗結果可以看出，系統(tǒng)在警報數(shù)量的精簡方面效果較好，警報數(shù)量得到了降低，同時減少了誤報率。

四、結語

本文針對傳統(tǒng)算法在入侵檢測系統(tǒng)產生的警報數(shù)量多、誤報以及效率低下等問題。提出基于關聯(lián)規(guī)則的改進算法——ALT算法，設計了基于ALT算法的入侵警報檢測系統(tǒng)模型。 該模型借助特殊數(shù)據(jù)結構實現(xiàn)了最大頻繁項目集的挖掘，實現(xiàn)了關聯(lián)規(guī)則的快速發(fā)現(xiàn)。最后，通過實驗證明了ALT算法在減少入侵警報的數(shù)量和降低誤報率等方面明顯優(yōu)于Apriori和FP2Growth算法。

參考文獻:

[1]AGRAWAL R， IMIEL IENSKI T， SWAMIA. Mining association rulesbetween sets of items in large databases [C]//Proceedings of the ACM SIGMOD Conference on Management of data. New York: ACMPress， 1993: 207 - 216

[2]AGRAWAL A，MANN ILA H， SR IKANT R， et al. Fast discovery of association rules [Z].Cambridge: AAA I Press/M IT Press，1996:307～328

[3]HAN J， PEI H， YIN Y. Mining frequent patterns without candidate generation[C]//2000ACM2SIGMOD.New York: ACM Press，2000

[4]BORGELT C. Efficient implementations of a priori and eclat [C ] / /Proceedings of the IEEE ICDM Workshop on Frequent ItemsetMining Implementations. Melbourne: IEEE Press， 2003

[5]WANG X M， BORGELT C， KRUSE R. Fuzzy frequent pattern discovery based on recursive elimination[C]//ICMLA 2005. New York: IEEE Press， 2005: 391～396

[6]BORGELT C. Keeping things simple: Finding frequent item sets by recursive elimination[C]//OSDM 2005.New York: ACM Press，2005: 66～70

[7]馮玉才 馮劍琳:關聯(lián)規(guī)則的增量式更新算法[J].軟件學報，1998，9(1):301～306

[8]IBM Almaden Research Center. Synthetic data generation code for associations and sequential patterns [EB/OL].[2008-02-15].http://www. almaden. ibm. com / software /quest/ resources/ index.shtml