申利民，孫中魁，2，陳 磊，馮佳音，李志明

1(燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004) 2(華北理工大學(xué)輕工學(xué)院 電氣信息學(xué)院，河北 唐山 063000) 3(華北理工大學(xué) 研究生院，河北 唐山 063000)

1 引 言

隨著現(xiàn)代信息技術(shù)的發(fā)展，賽博空間安全問題的重要性也隨之凸顯出來.2019 年全年超過 6，200 萬個(gè)計(jì)算機(jī)惡意程序樣本被捕獲，日均傳播次數(shù)達(dá) 824 萬余次，涉及計(jì)算機(jī)惡意程序家族 66 萬余個(gè)(1)https：//www.cert.org.cn/ publish/main /upload /File/2019-year.pdf.截止2019年12月，CNCERT接收到網(wǎng)絡(luò)安全事件報(bào)告107801件，較2018年底增長1.0%(2)http：//www.cac.gov.cn.為了適應(yīng)日趨復(fù)雜化、多樣化的網(wǎng)絡(luò)環(huán)境和各種各樣的網(wǎng)絡(luò)入侵手段，入侵檢測系統(tǒng)(Intrusion Detection System，IDS)通過分析網(wǎng)絡(luò)連接和系統(tǒng)審計(jì)數(shù)據(jù)，生成安全策略并發(fā)現(xiàn)入侵攻擊，已經(jīng)成為賽博空間安全不可或缺的組成部分.

在現(xiàn)實(shí)網(wǎng)絡(luò)中，入侵檢測系統(tǒng)面對的數(shù)據(jù)大都是高維數(shù)據(jù)，部分研究者們對高維數(shù)據(jù)首先采用特征提取或特征選擇的方法降低數(shù)據(jù)維度，再采用傳統(tǒng)的數(shù)據(jù)挖掘方法進(jìn)行處理.Tian等提出了一種基于PCA的分層孤立點(diǎn)檢測模型，首先基于PCA進(jìn)行特征提取，然后利用正常數(shù)據(jù)建立一個(gè)異常檢測模型，再分析異常數(shù)據(jù)類型[1]；Zyad等在PCA的基礎(chǔ)上提出了利用修剪后的平均向量來估計(jì)平均向量，從而使Trimmed PCA具有更好的魯棒性[2].降維的方法可以剔除某些特征，降低計(jì)算的時(shí)間復(fù)雜度，但每個(gè)特征代表不同的孤立值，如果錯(cuò)誤的選擇特征就會得到錯(cuò)誤的孤立值，從而產(chǎn)生不適合未來計(jì)算的近似結(jié)果.基于低維數(shù)據(jù)的挖掘算法在面對高復(fù)雜性、稀疏性和多樣性的高維數(shù)據(jù)時(shí)往往無能為力，適用于低維數(shù)據(jù)的數(shù)據(jù)挖掘算法在處理高維數(shù)據(jù)時(shí)通常會遇到算法效率降低，存在傳統(tǒng)的基于距離和密度的定義失效等問題，降低了入侵檢測準(zhǔn)確性[3].研究者們提出了針對高維數(shù)據(jù)的入侵檢測方法.Zhang等針對高維數(shù)據(jù)網(wǎng)絡(luò)數(shù)據(jù)流中的異常檢測，提出了SPOT技術(shù)，具有良好的檢測效果[4]；Prajapati等針對高維數(shù)據(jù)中的數(shù)據(jù)不均勻和剛性聚類問題，利用K-mean算法和模糊C-Mean(FCM)算法的優(yōu)點(diǎn)，提出了一種最近鄰搜索算法，能在更短的時(shí)間內(nèi)實(shí)現(xiàn)最近鄰搜索[5].

入侵行為中的“攻擊”數(shù)據(jù)通常被視為異常數(shù)據(jù)，而孤立點(diǎn)數(shù)據(jù)挖掘是對大規(guī)模數(shù)據(jù)中偏離正常行為的異常數(shù)據(jù)進(jìn)行的挖掘，因此孤立點(diǎn)數(shù)據(jù)挖掘?qū)θ肭中袨榉治鼍哂兄匾饬x.針對高維孤立點(diǎn)挖掘，研究者提出了幾種典型的孤立點(diǎn)挖掘算法：基于空間投影[6，7]、基于超圖模型[8，9]和基于頻繁模式的算法.基于頻繁模式的孤立點(diǎn)挖掘算法簡單、易于理解，并且比前兩種算法，有著更低的時(shí)間復(fù)雜度，研究者做了廣泛的研究.早期，He等提出了頻繁模式孤立因子(FPOF)的度量概念，并提出了基于頻繁模式的孤立點(diǎn)挖掘算法(FindFPOF)，通過計(jì)算每條數(shù)據(jù)的頻繁模式因子來發(fā)現(xiàn)孤立點(diǎn)[10]；周等在FindFPOF的基礎(chǔ)上提出了加權(quán)頻繁模式孤立因子的概念，并在此基礎(chǔ)上給出一種快速數(shù)據(jù)流孤立點(diǎn)檢測算法，該算法具有良好的適用性和有效性[11]；王等提出了一種新的算法NFPOF(New Frequent Pattern Outlier Factor)，通過頻繁模式的相關(guān)屬性進(jìn)一步精確定位每一條孤立點(diǎn)數(shù)據(jù)的異常屬性[12]；Yuan等針對權(quán)值嚴(yán)重影響孤立值檢測結(jié)果的問題，提出了一種加權(quán)頻繁模式孤立點(diǎn)挖掘方法(WFP-Outlier)，用于從加權(quán)數(shù)據(jù)流中發(fā)現(xiàn)隱式孤立點(diǎn)[13].

綜上所述，基于頻繁模式的高維孤立點(diǎn)挖掘在入侵檢測中具有非常重要作用，但在基于頻繁模式算法及其改進(jìn)算法中存在兩個(gè)問題，首先上述算法需要獲取完全頻繁模式，但是在高維數(shù)據(jù)中，發(fā)現(xiàn)頻繁模式的完全集是非常困難的；其次頻繁模式的挖掘算法的時(shí)間復(fù)雜度與頻繁模式的數(shù)量有直接關(guān)系，頻繁模式的數(shù)量越多，時(shí)間復(fù)雜度越大.針對基于頻繁模式的高維孤立點(diǎn)挖掘算法中存在的不容易獲取完全頻繁模式和時(shí)間復(fù)雜度高等問題，引入關(guān)聯(lián)規(guī)則中的最大頻繁模式因子的概念，提出一種基于最大頻繁模式因子的高維孤立點(diǎn)挖掘(MFPOF-OM)算法，并把其和入侵檢測結(jié)合起來，在保證檢測性能優(yōu)良的前提下，降低了時(shí)間復(fù)雜度.

2 基于最大頻繁模式因子的高維孤立點(diǎn)挖掘生成入侵檢測模式

設(shè)D={tl，t2，…，tn}為一個(gè)包含n個(gè)網(wǎng)絡(luò)行為記錄t的數(shù)據(jù)集，tk稱為事務(wù).I={il，i2，…，ip}是網(wǎng)絡(luò)行為記錄中所有屬性的集合，im稱為項(xiàng)目.

定義1.項(xiàng)目集：I的任何子集X稱為D的項(xiàng)目集.

定義2.支持度：項(xiàng)目集X的支持度記為support(X)：

(1)

其中：‖D‖表示數(shù)據(jù)集D的事務(wù)總數(shù)，‖X‖表示項(xiàng)目集X的支持?jǐn)?shù).

定義3.頻繁模式：如果項(xiàng)目集X的支持度support(X)≥MinSP，則X為頻繁模式，否則稱為非頻繁模式，其中MinSP表示用戶定義的最小支持度.

定義4.超集：若一個(gè)集合S2中的每一個(gè)元素都在集合S1中，且集合S1中可能包含S2中沒有的元素，則集合S1就是S2的一個(gè)超集.S1是S2的超集，則S2是S1的真子集，反之亦然.

定義5.最大頻繁項(xiàng)模式：頻繁項(xiàng)集X，如果其所有超集都是非頻繁項(xiàng)集，那么稱X為最大頻繁模式.

定理1.設(shè)X、Y是數(shù)據(jù)集D中的項(xiàng)集，如果X?Y，若Y是頻集，則X也是頻集.

設(shè)Y為最大頻繁模式，由定義5可知Y必為頻繁模式，如果X?Y成立，則有定理1可知，X必為頻繁模式，也即是最大頻繁模式中已經(jīng)包含了所有的頻繁模式.

由以上分析可知，基于最大頻繁模式的孤立點(diǎn)挖掘算法中只需要發(fā)現(xiàn)最大頻繁模式集，而不是完全頻繁模式集，既解決了發(fā)現(xiàn)頻繁模式的完全集的困難問題，又因?yàn)樽畲箢l繁模式的數(shù)量遠(yuǎn)遠(yuǎn)小于頻繁模式的數(shù)量，從而可以降低算法的時(shí)間復(fù)雜度.

2.1 數(shù)據(jù)離散化

入侵檢測的數(shù)據(jù)類型可分為文本型數(shù)據(jù)、離散數(shù)值型數(shù)據(jù)和連續(xù)數(shù)值型數(shù)據(jù)3大類，而最大頻繁模式的挖掘要求數(shù)據(jù)類型必須是離散數(shù)值型，因此需要對連續(xù)數(shù)值型數(shù)據(jù)進(jìn)行離散化處理，轉(zhuǎn)化成為可靠的精確的適合進(jìn)行高維孤立點(diǎn)挖掘的數(shù)據(jù).

連續(xù)數(shù)據(jù)的離散化就是將連續(xù)數(shù)據(jù)分割為有限個(gè)相互獨(dú)立的區(qū)間.離散化的方法有多種，其中基于聚類分析的方法因其可以根據(jù)數(shù)據(jù)的分布特點(diǎn)自行決定屬性值如何劃分區(qū)間，能夠盡量減少人工的干預(yù)，在實(shí)際中得到廣泛的應(yīng)用.聚類形成模式類之后，同一個(gè)模式類內(nèi)的對象因其高度相似可當(dāng)成一個(gè)對象來對待，而不同模式類的對象因其迥異性而被看作不同的離散值.

基于聚類分析的離散化方法有兩個(gè)步驟：

1)對連續(xù)數(shù)據(jù)類型的屬性值進(jìn)行聚類.

2)聚類后，同一個(gè)模式類所包含的連續(xù)屬性值作為一個(gè)對象，統(tǒng)一標(biāo)記，而不同模式類的數(shù)值分別標(biāo)記，完成離散化處理.

其中，基于聚類分析離散化的關(guān)鍵步驟是是對屬性值的聚類挖掘.

K-means算法作為一種基于劃分的無監(jiān)督的經(jīng)典算法，在實(shí)踐應(yīng)用被廣泛應(yīng)用，但K-means算法也有其本身的缺點(diǎn)，就是對聚類個(gè)數(shù)K和初始聚類中心的選擇非常敏感.

針對K值敏感的問題.因?yàn)樵陔x散化過程中K值并不是固定和唯一的，所以可采用手肘法確定最優(yōu)的K值.手肘法的核心思想是：當(dāng)K小于最優(yōu)聚類數(shù)時(shí)，增大K值會大幅增加每個(gè)模式類的聚合程度，聚合程度的好壞由樣本的聚類誤差平方和(SSE)來表示，SSE會大幅下降，當(dāng)K達(dá)到合理數(shù)量的模式類時(shí)，SSE將急劇下降，最后，SSE值趨于平坦，即SSE和K之間的函數(shù)關(guān)系呈肘形，并且對應(yīng)于肘部的K值是最佳的簇?cái)?shù).

誤差平方和(SSE)定義為：

(2)

其中，Ci為第i個(gè)簇，p為Ci中的樣本點(diǎn)，mi為Ci的質(zhì)心(Ci中所有樣本的均值).

針對初始聚類中心的選擇敏感的問題，采用最大距離法選取K個(gè)樣本作為初始中心點(diǎn).最大距離法的核心思想是認(rèn)為所有樣本中距離最遠(yuǎn)的樣本點(diǎn)最不可能被分到同一個(gè)模式類中.

3https：//www.unb.ca /cic/datasets/index.html

2.2 基于最大頻繁模式因子的高維孤立點(diǎn)挖掘算法思想

基于FindFPOF算法中頻繁模式因子(FPOF)的概念，提出最大頻繁模式因子(MFPOF)的定義.

定義6.最大頻繁模式因子：對于數(shù)據(jù)集中D中的每個(gè)網(wǎng)絡(luò)行為記錄t，MFPOF(t)定義為：

(3)

其中：

MFPs(D，MinSP)表示滿足給定最小支持度閾值MinSP的數(shù)據(jù)集D的最大頻繁模式集合；

‖MFPs(D，MinSP)‖表示最大頻繁模式集合中最大頻繁項(xiàng)的個(gè)數(shù)；

support(X)表示一個(gè)最大頻繁模式X的支持度.

基于最大頻繁模式因子的高維孤立點(diǎn)挖掘(MFPOF-OM)算法描述如算法1所示.

算法1.MFPOF-OM算法

輸入：D//網(wǎng)絡(luò)行為數(shù)據(jù)集

MinSP//最小支持度閾值

k//孤立點(diǎn)個(gè)數(shù)閾值

輸出：k個(gè)網(wǎng)絡(luò)行為孤立點(diǎn)數(shù)據(jù)記錄

Begin：

//基于PF-Tree挖掘出最大頻繁模式集合

1.對于D，生成滿足MinSP的項(xiàng)頭表HeaderTable(D)；

2.對于D，采用PF-Tree算法生成滿足MinSP的頻繁項(xiàng)樹，記為：T；

3.采用一種改進(jìn)的高效最大頻繁模式因子挖掘算法，獲取MFPs(D，MinSP)和support(X)；

//基于生產(chǎn)的最大頻繁模式，開始孤立點(diǎn)挖掘

4.foreachtinD

5.依據(jù)公式(3)，計(jì)算每個(gè)記錄t的最大頻繁模式因子值：MFPOF(t)；

6.end foreach

7.獲取所有t的MFPOF值；

8.對所有t，按照MFPOF值升序排序；

9.return MFPOF值最小的前k網(wǎng)絡(luò)行為記錄，即k個(gè)網(wǎng)絡(luò)行為孤立點(diǎn)數(shù)據(jù)

End

MFPOF-OM算法分3個(gè)部分：1)從數(shù)據(jù)庫中挖掘最大頻繁模式；2)計(jì)算每個(gè)網(wǎng)絡(luò)行為記錄的MFPOF(t)；3)發(fā)現(xiàn)k個(gè)孤立點(diǎn)數(shù)據(jù).總的時(shí)間復(fù)雜度為O(n2+n*l+n*logn)，其中n表示數(shù)據(jù)量的個(gè)數(shù)，l表示最大頻繁模式的個(gè)數(shù).

2.3 基于關(guān)聯(lián)分析自動構(gòu)建誤用檢測模式

采用關(guān)聯(lián)分析可以自動發(fā)現(xiàn)網(wǎng)絡(luò)行為的數(shù)據(jù)特征，關(guān)聯(lián)分析產(chǎn)生的最大頻繁模式能夠反映網(wǎng)絡(luò)行為數(shù)據(jù)的最大共同特征，最大共同特征又是通過網(wǎng)絡(luò)行為數(shù)據(jù)的屬性值表示出來的，可利用這些屬性值來構(gòu)建具有很強(qiáng)分類能力的入侵檢測模式[14].

以MFPOF-OM算法所獲取的孤立點(diǎn)數(shù)據(jù)集作為輸入，并設(shè)定一個(gè)最小支持度閾值，算法可參考算法1的1-3步，可以獲取孤立點(diǎn)集的最大頻繁模式，即為網(wǎng)絡(luò)攻擊的入侵檢測模式.

3 實(shí)驗(yàn)分析

為了對所提出的方法進(jìn)行驗(yàn)證，本文使用NSL-KDD數(shù)據(jù)集3作為實(shí)驗(yàn)數(shù)據(jù)，該數(shù)據(jù)集包含了12多萬條連接記錄，每條連接記錄包含41個(gè)表示連接記錄特征的條件屬性和1個(gè)表示連接記錄攻擊類型的決策屬性.其中第20個(gè)屬性(num_outbound_files)的屬性值全為0，依據(jù)信息論理論，信息熵為0，因此剔除第20個(gè)屬性.

NSL-KDD的訓(xùn)練數(shù)據(jù)集包含24種攻擊類型分類標(biāo)識，所有的分類標(biāo)識都可以根據(jù)其攻擊特點(diǎn)映射為4種攻擊類別：Probing、DoS、U2R和 R2L，及一種正常類別：Normal，共5大類.

所有的實(shí)驗(yàn)在MATLAB 2012中實(shí)現(xiàn)，對4組樣本數(shù)據(jù)Normal+DoS，Normal+Probing，Normal+R2L，Normal+U2R從準(zhǔn)確度和復(fù)雜度兩個(gè)方面進(jìn)行分析.

3.1 準(zhǔn)確度分析

4組樣本數(shù)據(jù)分析獲取的DoS、Probing、R2L、U2R入侵檢測模式實(shí)驗(yàn)結(jié)果如圖1所示.對4種攻擊的入侵檢測模式進(jìn)行綜合分析，并以檢測率(DR)和誤報(bào)率(FPR)作為判定入侵檢測模式的性能評價(jià)標(biāo)準(zhǔn).

檢測率、誤報(bào)率分別定義為：

檢測率=(檢測出的異常攻擊數(shù)/異常攻擊總數(shù))*100%

誤報(bào)率=(錯(cuò)誤分類的進(jìn)程總數(shù)/正常的進(jìn)程總數(shù))*100%

1)4種網(wǎng)絡(luò)攻擊模式測試結(jié)果分析

通過比較4種網(wǎng)絡(luò)攻擊在不同MinSP閾值情況下的檢測率和誤報(bào)率，來說明所提算法的檢測效果，進(jìn)而驗(yàn)證所提算法的可行性.入侵檢測攻擊模式由一條或多條規(guī)則組成：每條規(guī)則內(nèi)部各屬性是“與”的邏輯關(guān)系，即所有的屬性取值都滿足要求則本條規(guī)則成立；規(guī)則之間是“或”的邏輯關(guān)系，即多條規(guī)則只要其中一條成立則可判定本條記錄為一個(gè)網(wǎng)絡(luò)攻擊行為.

實(shí)驗(yàn)結(jié)果從檢測率、誤報(bào)率兩個(gè)性能指標(biāo)來綜合衡量入侵檢測模式的檢測效果.以Probing攻擊入侵檢測模式為例進(jìn)行數(shù)據(jù)分析.實(shí)驗(yàn)過程中MinSP所取閾值不同，則獲取的入侵檢測模式也不同，實(shí)驗(yàn)結(jié)果如圖1(b)所示.圖1(b)表示MinSP分別為58000和59000兩個(gè)閾值下獲取的入侵檢測模式，并用獲取的Probing入侵檢測模式分別對5種數(shù)據(jù)類型(即DoS、Probing、R2L、U2R 4種攻擊數(shù)據(jù)和Normal類型)進(jìn)行檢測.分析發(fā)現(xiàn)，在閾值為59000的情況下，Probing入侵檢測模式對Probing數(shù)據(jù)的檢測率為95%，但是用Probing入侵檢測模式來檢測其它類型數(shù)據(jù)會存在一定誤差，如檢測Normal數(shù)據(jù)，會把3%的Normal數(shù)據(jù)誤檢測為Probing類型數(shù)據(jù)，對DoS數(shù)據(jù)誤檢率為2%，對R2L數(shù)據(jù)誤檢率為1%，對U2R數(shù)據(jù)誤檢率為10%.閾值為58000時(shí)各檢測結(jié)果如圖1(b)中白色柱體所示，不再一一描述.通過對多個(gè)閾值下的檢測結(jié)果綜合分析，閾值為59000時(shí)的檢測結(jié)果最好，因此把閾值為59000時(shí)的入侵檢測模式作為Probing攻擊的入侵檢測模式，模式規(guī)則如表1所示.

比較圖1中的4種攻擊入侵檢測模式發(fā)現(xiàn)，當(dāng)最小支持度閾值較大時(shí)都會有更好的檢測率，對其它類型數(shù)據(jù)的檢測誤差則大小變化不一，但基本持平.這正是孤立點(diǎn)挖掘的特點(diǎn)決定的，閾值越大孤立點(diǎn)的個(gè)數(shù)越少，更能反映攻擊類型數(shù)據(jù)的特征.當(dāng)然閾值也有一定的限定，如果閾值取值過大反而會對降低檢測率造成不良影響.

表1 閾值等于59000時(shí)Probing攻擊的入侵檢測模式Table 1 Misuse detection patterns of Probing attack when the threshold is 59000

比較圖1中的4個(gè)子圖發(fā)現(xiàn)U2R類型數(shù)據(jù)在DoS、Probing和R2L攻擊入侵檢測模式中都有較高的檢測誤差，分別為4%、10%和33%；U2R攻擊入侵檢測模式的檢測率相較于其它3種攻擊入侵檢測模式，它的檢測率也相對不高，只有87%的檢測率.這是由NSL-KDD數(shù)據(jù)集中U2R類型數(shù)據(jù)的特點(diǎn)決定的，U2R的數(shù)據(jù)量太少，只有52條，以至于數(shù)據(jù)挖掘無法充分發(fā)現(xiàn)其數(shù)據(jù)特征，導(dǎo)致檢測性能不盡完善.

圖1 4種網(wǎng)絡(luò)攻擊模式的測試結(jié)果Fig.1 Test results of four network attacks

比較圖1(c)和圖1(d)發(fā)現(xiàn)，利用R2L攻擊入侵檢測模型檢測U2R數(shù)據(jù)和利用U2R攻擊入侵檢測模型檢測R2L數(shù)據(jù)都有較高的誤差，這說明R2L類型數(shù)據(jù)和U2R類型數(shù)據(jù)之間相較于其他3種類型數(shù)據(jù)，具有較高的數(shù)據(jù)相似性，這與現(xiàn)實(shí)中2種網(wǎng)絡(luò)攻擊的特點(diǎn)相符.

2)基于高維數(shù)據(jù)下入侵檢測結(jié)果對比分析

為了測試所提算法的準(zhǔn)確度，把所提MFPOF-OM算法與FindFPOF算法[10]、NFPOF算法[12]、AOD-FP-MaxFPOF算法[15]、ADASYN-SDA算法[16]進(jìn)行比較，其中FindFPOF、NFPOF、AOD-FP-MaxFPOF是3種基于頻繁模式或改進(jìn)的基于頻繁模式孤立點(diǎn)檢測算法，ADASYN-SDA是基于深度學(xué)習(xí)的算法，比較結(jié)果如圖2所示.結(jié)果表明MFPOF-OM算法優(yōu)于FindFPOF和NFPOF算法；和AOD-FP-MaxFPOF算法比較，檢測率上非常接近，誤報(bào)率比后者相比偏高；和基于深度學(xué)習(xí)的ADASYN-SDA算法相比，兩個(gè)性能指標(biāo)都稍有不如，但ADASYN-SDA算法需要復(fù)雜的前期數(shù)據(jù)處理，首先需要使用ADASYN算法進(jìn)行數(shù)據(jù)過采樣處理，然后使用Adam優(yōu)化算法，以及Dropout正則化對SDA深度學(xué)習(xí)模型進(jìn)行改進(jìn)，提取出低維的集成特征，最后再在Softmax分類器中進(jìn)行入侵檢測識別，會大大增加算法的時(shí)間復(fù)雜度.從總體性能上分析顯示，所提算法和有監(jiān)督的深度學(xué)習(xí)方式相比性能稍有不如，但在無監(jiān)督的檢測算法中性能表現(xiàn)較佳，網(wǎng)絡(luò)中的入侵行為能夠被有效地檢測出來，可以滿足實(shí)際的運(yùn)行需求.

圖2 其它入侵檢測方法和所提方法的比較Fig.2 Comparison between other intrusion detection methods and the method proposed

3)高維入侵檢測和降維入侵檢測的對比分析

入侵檢測系統(tǒng)中的數(shù)據(jù)是高維的，高維數(shù)據(jù)表達(dá)能力較強(qiáng)，能夠刻畫入侵檢測系統(tǒng)內(nèi)部復(fù)雜的結(jié)構(gòu).但在入侵檢測分析中，很多方法都使用了降維的概念，進(jìn)行維度的約簡.而某些看似不重要的維度，特別是在孤立點(diǎn)挖掘算法中，更可能代表著有用的信息，而這些維度的消除，可能會影響到入侵檢測結(jié)果準(zhǔn)確度.且原始數(shù)據(jù)處理過程中的降維也會增加入侵檢測的時(shí)間復(fù)雜度.為了比較高維數(shù)據(jù)入侵檢測和數(shù)據(jù)降維入侵檢測對檢測性能的影響，利用MFPOF-OM算法和兩種基于降維的方法基于PCA的特征提取[1]、截?cái)嗑礚DA方法[17]進(jìn)行對比分析，結(jié)果如圖3所示.從中可以看出，MFPOF-OM算法和文獻(xiàn)[1]中檢測性能基本一致，而又明顯的優(yōu)于文獻(xiàn)[17]所提出的方法，說明不適當(dāng)?shù)臄?shù)據(jù)降維方法會把某些含有重要孤立點(diǎn)信息的特征剔除掉，從而大大降低入侵系統(tǒng)的檢測性能.

圖3 降維挖掘和高維挖掘測試比較Fig.3 Comparison dimension reduction methods with the method proposed in this paper

3.2 時(shí)間復(fù)雜度分析

對4組樣本數(shù)據(jù)Normal+DoS、Normal+Probing、Normal+R2L、Normal+U2R進(jìn)行復(fù)雜度分析.FindFPOF、NFPOF、AOD-FP-MaxFPOF這3種基于頻繁模式及其改進(jìn)算法的流程類似，都可以分為3步，其中第1步從數(shù)據(jù)庫中挖掘頻繁模式和第3步發(fā)現(xiàn)k個(gè)網(wǎng)絡(luò)行為孤立點(diǎn)數(shù)據(jù)，這兩步基本雷同，只有第2步因?yàn)樗惴ㄖ攸c(diǎn)不同而不太一樣.FindFPOF算法第2步是計(jì)算每個(gè)網(wǎng)絡(luò)行為記錄的FPOF(t)；NFPOF算法是計(jì)算新頻繁模式離群因子NFPOF(t)；AOD-FP-MaxFPOF算法是計(jì)算最大頻繁孤立點(diǎn)因子MaxFPOF(t).依據(jù)所給算法分析，時(shí)間復(fù)雜度也可根據(jù)算法流程分為3部分，且3種算法的時(shí)間復(fù)雜度基本一致，總的時(shí)間復(fù)雜度為O(n2+n*m+n*logn)，其中n表示數(shù)據(jù)量的多少，m表示頻繁模式的多少.

表2 兩類挖掘算法結(jié)果比較Table 2 Compared the results of two mining algorithm

與上述算法一樣，MFPOF-OM算法流程圖也分3步，如2.2節(jié)中所述，總的時(shí)間復(fù)雜度為O(n2+n*l+n*logn)，其中m表示數(shù)據(jù)量的個(gè)數(shù)，l表示最大頻繁模式的個(gè)數(shù).對于海量數(shù)據(jù)來說，n取值足夠大，兩種算法的時(shí)間復(fù)雜度從理論計(jì)算上都可以簡化為O(n2).但在實(shí)際運(yùn)行中，當(dāng)n取值一定時(shí)，會因?yàn)閘?m，4組樣本數(shù)據(jù)獲取的頻繁模式個(gè)數(shù)(m)和MFPOF-OM算法中的最大頻繁模式個(gè)數(shù)(l)如表2所示，從而使MFPOF-OM算法比上述3種算法具有更優(yōu)的時(shí)間復(fù)雜度.

4 結(jié) 論

針對現(xiàn)實(shí)中入侵檢測系統(tǒng)中多為高維數(shù)據(jù)這一現(xiàn)實(shí)問題，利用基于頻繁模式高維孤立點(diǎn)挖掘的相關(guān)技術(shù)，本文提出了一種基于最大頻繁模式因子的高維孤立點(diǎn)挖掘算法(MFPOF-OM).MFPOF-OM算法只需挖掘出最大頻繁模式集，解決了基于頻繁模式孤立點(diǎn)算法中挖掘完全頻繁模式比較困難的問題，也因頻繁模式的數(shù)量的大幅減少，從而降低算法的時(shí)間復(fù)雜度.實(shí)驗(yàn)表明，所提出的方法是可行的，相較于對比算法，在保證了檢測性能優(yōu)良的前提下，進(jìn)一步降低了時(shí)間復(fù)雜度.