NFPOF算法在入侵檢測中的應(yīng)用

穆 俊

(臨滄師范高等?？茖W(xué)校信息科學(xué)與技術(shù)系，云南 臨滄 677000)

入侵檢測是使用數(shù)據(jù)挖掘方式計(jì)算原型系統(tǒng)的常見網(wǎng)絡(luò)應(yīng)用方式，離群點(diǎn)計(jì)算是常用的數(shù)據(jù)挖掘算法之一。通過離群點(diǎn)計(jì)算，可以將正常運(yùn)行行為分成多個(gè)簇，將異常運(yùn)行的點(diǎn)看作離散點(diǎn)，找出這部分離散點(diǎn)即可挖掘出數(shù)據(jù)當(dāng)中混雜的異常數(shù)據(jù)。

1 頻繁模式挖掘規(guī)則

假定一個(gè)項(xiàng)目的集本身并不是頻繁的，那么該項(xiàng)目所有的超集全都不是頻繁的，則可以用“A非頻繁—A”來表示，如下例所示:

如果頻繁項(xiàng)的集也是頻繁的，那么該頻繁項(xiàng)的所有子集都將是頻繁的。如果{4}屬于非頻繁集，那么其中的{1，4}也一定是非頻繁集，因?yàn)轫?xiàng)目集的支持度必然小于{4}，那么在同一時(shí)間段內(nèi)包含了項(xiàng)目1和項(xiàng)目4的交易類型整體數(shù)目必然小于或等于上述{4}的整體交易數(shù)目。反之，如果項(xiàng)目集{1，2，3，4}屬于頻繁項(xiàng)集，那么其余的子項(xiàng)目集也一定屬于頻繁的項(xiàng)目集。

一般在搜索頻繁項(xiàng)集時(shí)，不僅可以使用從底部向上這一常規(guī)方式進(jìn)行檢查，同時(shí)也可以采取從上到下的方式來進(jìn)行取樣。在第一步執(zhí)行時(shí)，將所有的項(xiàng)集都當(dāng)成非頻繁的項(xiàng)集，由頻繁的性質(zhì)可知所有超集的值都不可能超過頻繁項(xiàng)集。對(duì)其余預(yù)備項(xiàng)集用相同方法處理，重復(fù)各步驟，直至最后找到所需頻繁項(xiàng)集才可以停止操作。

在這一過程當(dāng)中，只有整體頻繁項(xiàng)集的長度都比較短時(shí)，采用從下至上的方式才會(huì)效率最高。如果所有項(xiàng)目的長度都較大，可以適當(dāng)使用從上至下的方式進(jìn)行計(jì)算。從上而下這一搜索方法的本質(zhì)就是以第N維的項(xiàng)集為基準(zhǔn)點(diǎn)進(jìn)行搜索，且候選項(xiàng)集所有項(xiàng)目需順次遞減1。如果其中任何一個(gè)項(xiàng)集被系統(tǒng)判定成非頻繁的項(xiàng)集，那么可以確定這一項(xiàng)集屬于頻繁的項(xiàng)集，這一項(xiàng)集自身所有子項(xiàng)集都必然會(huì)是頻繁項(xiàng)集，因此在后續(xù)檢查中可忽略上述項(xiàng)集。

2 面向數(shù)據(jù)流的離群點(diǎn)

在一些投影當(dāng)中，數(shù)據(jù)的密度會(huì)比整體密度平均數(shù)值略低，那么這些投影便可以稱之為異常的低緯度投影。根據(jù)數(shù)據(jù)的不同屬性，可將其劃分為等深的區(qū)域，并對(duì)數(shù)值進(jìn)行記錄。在每一個(gè)區(qū)域當(dāng)中都可以得到一些單元，使用這些單元可判定項(xiàng)目是否處于稀疏狀態(tài)。在N段緯度當(dāng)中提取出N個(gè)區(qū)間，之后使所有區(qū)間組成一個(gè)立方體，根據(jù)實(shí)際情況對(duì)統(tǒng)計(jì)屬性的分布情況進(jìn)行記錄。這一過程不僅應(yīng)統(tǒng)計(jì)數(shù)據(jù)，同時(shí)也要注意到每一個(gè)區(qū)域內(nèi)部的差距，在對(duì)離群點(diǎn)進(jìn)行檢測時(shí)首先分析空間的密度差。若數(shù)據(jù)庫當(dāng)中所有點(diǎn)總數(shù)為S，且在空間數(shù)據(jù)呈平均分布，則可判定N維的立方體自身伯努利變量是fk。如果將立方體中所有點(diǎn)視為正態(tài)分布，就必須事先設(shè)定一個(gè)極限定理，該定理標(biāo)準(zhǔn)差設(shè)為，期望值設(shè)定為N-fk。如果將Z(D)認(rèn)定為立方體當(dāng)中所具備的實(shí)際點(diǎn)數(shù)，就可以利用稀疏Z(D)表示D的稀疏程度:

若稀疏程度小于期望值，則表明S(D)數(shù)值越小，D的數(shù)值就越稀松。

3 基于頻繁模式離群算法的入侵檢測模型

基于異常檢測的入侵檢測系統(tǒng)可發(fā)現(xiàn)與大多數(shù)正常數(shù)據(jù)模型或數(shù)據(jù)軌跡發(fā)生偏離的數(shù)據(jù)，從而檢測出入侵行為。異常檢測與離群點(diǎn)檢測具有非常多的共通性，將有效的離群點(diǎn)檢測技術(shù)應(yīng)用于入侵檢測系統(tǒng)非常必要。在此，介紹一種入侵檢測系統(tǒng)模型，此模型的建立基于數(shù)據(jù)流環(huán)境。在該系統(tǒng)中，關(guān)鍵部分是對(duì)捕獲數(shù)據(jù)的處理與管理以及相應(yīng)的入侵檢測算法的選擇，而數(shù)據(jù)流挖掘算法模塊和數(shù)據(jù)流管理系統(tǒng)是整個(gè)系統(tǒng)模型的核心。圖1為系統(tǒng)工作流程示意圖［8］。

圖1 系統(tǒng)工作流程示意圖

(1)數(shù)據(jù)包捕獲模塊。數(shù)據(jù)包捕獲模塊的作用是獲得原始的數(shù)據(jù)信息，對(duì)源自網(wǎng)絡(luò)的數(shù)據(jù)包進(jìn)行數(shù)據(jù)預(yù)處理，然后將這些數(shù)據(jù)傳遞到數(shù)據(jù)流管理模塊，以供數(shù)據(jù)流挖掘模型進(jìn)行分析。對(duì)這些數(shù)據(jù)包的檢測依賴于算法模型。

(2)數(shù)據(jù)管理模塊。數(shù)據(jù)流管理模塊主要用于進(jìn)行存儲(chǔ)數(shù)據(jù)和管理數(shù)據(jù)，數(shù)據(jù)可以統(tǒng)一進(jìn)入檢測模塊進(jìn)行檢測。

(3)數(shù)據(jù)檢測模塊。使用現(xiàn)有成功建立的模型或計(jì)算方法，對(duì)捕獲之后需要處理的數(shù)據(jù)進(jìn)行深層次評(píng)估，以判定數(shù)據(jù)是否被入侵或存在錯(cuò)誤。這一方式的實(shí)際應(yīng)用可以靈活多變，將檢測器多樣化并且分層次化，以提升模塊檢測工作的整體工作效率。我們可以將整體工作視為多維的運(yùn)行方式，將各種運(yùn)行結(jié)果分配到所有檢測器上，以此分析檢測出的數(shù)據(jù);同時(shí)也可以將檢驗(yàn)器分成不同的種類，根據(jù)前端快速檢測以及后端復(fù)雜檢測器的實(shí)際情況對(duì)數(shù)據(jù)進(jìn)行分析。

4 NFPOF算法

NFPOF是基于頻繁模式離群點(diǎn)檢測算法的改進(jìn)算法，下面介紹其算法流程和計(jì)算過程。

4.1 算法流程

假設(shè)一個(gè)網(wǎng)絡(luò)上痕跡數(shù)據(jù)集屬于數(shù)集D，Di代表D當(dāng)中的一個(gè)數(shù)據(jù)。設(shè)定一組數(shù)集X，則可以將X稱之為數(shù)據(jù)集當(dāng)中的一種模式。如果一些數(shù)據(jù)可以滿足其中所有項(xiàng)，那么可以稱之為Di滿足X。算法簡化后處理過程可以分段:第一部分就是對(duì)數(shù)據(jù)進(jìn)行預(yù)期處理;第二部分就是發(fā)現(xiàn)頻繁模式并且對(duì)其中每個(gè)頻繁模式的權(quán)值進(jìn)行計(jì)算，之后計(jì)算每一條數(shù)據(jù)當(dāng)中的離群因子，并且根據(jù)實(shí)際情況來檢測離群點(diǎn)，在算出具體數(shù)值之后再檢查異常屬性。具體計(jì)算過程如圖2所示。

在數(shù)據(jù)預(yù)處理時(shí)，可以從安全審計(jì)日志當(dāng)中摘錄，也可以使用數(shù)據(jù)包的形式抓取數(shù)據(jù)。在提取數(shù)據(jù)時(shí)需要選擇相應(yīng)的窗口，一般使用改良之后的滑動(dòng)窗口，并且可以將窗口的模式當(dāng)成靜態(tài)的片段來處理。處理對(duì)象可以通過數(shù)據(jù)分析確認(rèn)是否有效，同時(shí)考慮剩余數(shù)據(jù)的完整性及有效性，對(duì)噪音等無效數(shù)據(jù)加以剔除。在對(duì)數(shù)據(jù)連續(xù)數(shù)值比進(jìn)行離散處理時(shí)，可以通過聚類處理的方式使數(shù)據(jù)以整數(shù)形式展現(xiàn)。

聚類算法當(dāng)中的HC算法是比較簡單的常見算法，時(shí)間復(fù)雜度比較低，且操作簡便。假設(shè)A為數(shù)據(jù)數(shù)值的具體屬性，那么聚類之后便可以將其整體數(shù)值劃分成一些區(qū)間，然后對(duì)數(shù)值D當(dāng)中的一些屬性進(jìn)行轉(zhuǎn)化，這些數(shù)值可以代表離散化之后的值域。對(duì)數(shù)據(jù)離散化結(jié)果進(jìn)行分析，保證記錄當(dāng)中所有屬性值都可以分配到相應(yīng)的離散值，進(jìn)而保證數(shù)據(jù)后期處理工作的可靠性與準(zhǔn)確性。

圖2 離群點(diǎn)數(shù)值計(jì)算

4.2 計(jì)算過程

通過計(jì)算新的加權(quán)頻繁模式因子來判定某個(gè)數(shù)據(jù)是否為離群點(diǎn)，再甄別離群點(diǎn)中所有的異常屬性。采用NFPOF計(jì)算方法，可以對(duì)安全審計(jì)數(shù)據(jù)或其余數(shù)據(jù)進(jìn)行一次性導(dǎo)入，并對(duì)最初的時(shí)間片段進(jìn)行初始化處理。對(duì)數(shù)據(jù)當(dāng)中的低維模式進(jìn)行編碼處理，使其映射出整個(gè)數(shù)列，數(shù)列可以簡單寫成［1，2，3，…，M］，在設(shè)置數(shù)值1的時(shí)候，可以從最高維數(shù)值當(dāng)中選擇用戶，并且這些模式當(dāng)中存在N元組。將各數(shù)值保存在hash當(dāng)中，利用Aporior計(jì)算方式來獲取頻繁模式。數(shù)據(jù)初始化之后，可以一次性多讀一些數(shù)據(jù)，并且可以通過該方式得到相應(yīng)的頻繁模式數(shù)集，減少反復(fù)計(jì)算的次數(shù)。

輸入K維度在安全日志上體現(xiàn)出的數(shù)據(jù)，其中最低模式的維度可以設(shè)定為l，函數(shù)設(shè)定為H，離群點(diǎn)的個(gè)數(shù)設(shè)定為P，正常數(shù)值設(shè)定為minNor，數(shù)據(jù)放入到D組中，再將X1當(dāng)中的模式存入到CandSer當(dāng)中。模式P1下，若滿足進(jìn)入到FreSer的時(shí)候P1含有屬性A小于等于K的條件，那么就可以進(jìn)行后續(xù)計(jì)算，按照順序?qū)?shù)值插入到outlier D當(dāng)中。離群數(shù)據(jù)有P條，但是1≤i≤P，將Di當(dāng)中的屬性都存入到H中，在數(shù)據(jù)組A當(dāng)中nor自身的最大數(shù)值為Sun，以及與a1成對(duì)立面的Sun(a1)的數(shù)值。若nor的數(shù)值小于最小闕值，那么最終的輸出數(shù)據(jù)則為異常屬性。經(jīng)過試驗(yàn)驗(yàn)證，該算法切實(shí)可行。

5 結(jié)語

介紹頻繁挖掘模式、離群點(diǎn)挖掘的概念，分析頻繁模式離群算法的入侵檢測模型，提出基于頻繁模式離群點(diǎn)檢測算法的改進(jìn)算法 —— NFPOF算法。分析NFPOF算法在入侵檢測中的應(yīng)用，從算法流程和計(jì)算過程說解該算法。該算法用于入侵檢測系統(tǒng)，提升了檢測系統(tǒng)的科學(xué)性與實(shí)用性。

［1］揭財(cái)明.基于密度的局部離群點(diǎn)檢測算法分析與研究［D］.重慶:重慶大學(xué)，2010:11-14.

［2］陳莊，黃勇，鄒航.基于離群點(diǎn)挖掘的工業(yè)控制系統(tǒng)異常檢測［J］.計(jì)算機(jī)科學(xué)，2011，4(2):36-38.

［3］石巖.基于基尼指標(biāo)和屬性相關(guān)性的離群數(shù)據(jù)挖掘及其并行化研究［J］.太原科技大學(xué)，2013，5(1):57-59.

［4］金洪杰.離群點(diǎn)挖掘技術(shù)在入侵檢測中的研究［J］.黑龍江科技信息，2013，8(3):66-68.

［5］薛安榮，姚林，鞠時(shí)光，等.離群點(diǎn)挖掘方法綜述［J］.計(jì)算機(jī)科學(xué)，2012，11(3):111-113.

［6］周曉云，孫志揮，張柏禮，等.高維類別屬性數(shù)據(jù)流離群點(diǎn)快速檢測算法［J］.軟件學(xué)報(bào)，2011，10(2):58-60.

［7］唐向紅，李國徽，楊觀賜.快速挖掘數(shù)據(jù)流中離群點(diǎn)［J］.小型微型計(jì)算機(jī)系統(tǒng)，2012，7(4):33-34.

［8］王茜，唐銳.基于頻繁模式的離群點(diǎn)挖掘在入侵檢測中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用研究，2011，5(1):77-81.