基于序列模式挖掘的入侵檢測(cè)技術(shù)研究

摘要:隨著計(jì)算機(jī)的發(fā)展，網(wǎng)絡(luò)安全在現(xiàn)代社會(huì)中扮演著越來(lái)越關(guān)鍵的角色，并成為比較嚴(yán)重的問(wèn)題。該文詳細(xì)分析了基于序列模式的數(shù)據(jù)挖掘技術(shù)，并且在挖掘過(guò)程中提出了一種新的序列模式算法。

關(guān)鍵詞:入侵檢測(cè);數(shù)據(jù)挖掘;序列模式挖掘

中圖分類號(hào):TP393文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)36-10254-03

Research of Intrusion Detection System Based on Sequential Pattern Mining

PAN Jian-sheng1，2， HU Kong-fa1

(1.College of Information Engineering， Yangzhou University， Yangzhou 225009， China; 2.School of Computer Science Technology， Nantong University， Nantong 226007， China)

Abstract: With the increasing growth of computer， the networks security play increasingly vital roles in modern society. The network security has become a serious problem. This paper analyzes intrusion detection system based on sequential pattern mining. In the mining process，we present a new algorithm of the sequential pattern mining based on bitmap representation.

Key words: intrusion detection; data mining; sequential pattern mining

信息社會(huì)的到來(lái)，給全世界帶來(lái)了技術(shù)和經(jīng)濟(jì)飛速發(fā)展的契機(jī)。但是，隨著網(wǎng)絡(luò)技術(shù)在世界包括中國(guó)在內(nèi)的各個(gè)領(lǐng)域應(yīng)用的深入開(kāi)展，人們?cè)谶M(jìn)行資源共享的同時(shí)，也感受到信息安全問(wèn)題的日益凸顯。由于計(jì)算機(jī)系統(tǒng)中硬件設(shè)備、操作系統(tǒng)、應(yīng)用軟件不可避免地會(huì)存在一些安全方面的漏洞，而且Internet自身協(xié)議和結(jié)構(gòu)的初始設(shè)計(jì)也存在一些缺陷，所有這些都使“黑客”侵犯和操縱一些重要信息和數(shù)據(jù)成為可能。

1 網(wǎng)絡(luò)入侵檢測(cè)技術(shù)

入侵檢測(cè)通過(guò)對(duì)計(jì)算機(jī)網(wǎng)絡(luò)或計(jì)算機(jī)系統(tǒng)中的若干關(guān)鍵點(diǎn)收集信息并進(jìn)行分析，從中發(fā)現(xiàn)網(wǎng)絡(luò)或系統(tǒng)中是否有違反安全策略的行為和被攻擊的跡象，進(jìn)行入侵檢測(cè)的軟件與硬件的組合就是入侵檢測(cè)系統(tǒng)。入侵檢測(cè)系統(tǒng)執(zhí)行的主要任務(wù)包括:監(jiān)視、分析用戶及系統(tǒng)活動(dòng)，審計(jì)系統(tǒng)構(gòu)造和弱點(diǎn)識(shí)別，反映已知進(jìn)攻的活動(dòng)模式，向相關(guān)人士報(bào)警，統(tǒng)計(jì)分析異常行為模式，評(píng)估重要系統(tǒng)和數(shù)據(jù)文件的完整性，審計(jì)、跟蹤管理操作系統(tǒng)，識(shí)別用戶違反安全策略的行為。

入侵檢測(cè)一般分為3個(gè)步驟，依次為信息收集、數(shù)據(jù)分析、響應(yīng)(被動(dòng)響應(yīng)和主動(dòng)響應(yīng))。入侵檢測(cè)系統(tǒng)可以從不同角度分類，包括檢測(cè)方法、檢測(cè)對(duì)象、反應(yīng)機(jī)制、體系結(jié)構(gòu)、分析時(shí)間等。一般來(lái)說(shuō)，主要從檢測(cè)對(duì)象、檢測(cè)方法來(lái)分類。根據(jù)檢測(cè)對(duì)象的不同可以分成基于主機(jī)的入侵檢測(cè)系統(tǒng)和基于網(wǎng)絡(luò)的入侵檢測(cè)系統(tǒng);根據(jù)檢測(cè)方法的不同可以分成誤用檢測(cè)系統(tǒng)和異常檢測(cè)系統(tǒng)。

2 數(shù)據(jù)挖掘技術(shù)

數(shù)據(jù)挖掘過(guò)程一般需要經(jīng)歷確定挖掘?qū)ο蟆?shù)據(jù)準(zhǔn)備、模型建立、數(shù)據(jù)挖掘、結(jié)果分析和知識(shí)應(yīng)用這樣幾個(gè)階段。目前數(shù)據(jù)挖掘技術(shù)在網(wǎng)絡(luò)安全領(lǐng)域的主要應(yīng)用有:對(duì)安全檢測(cè)對(duì)象的海量的審計(jì)數(shù)據(jù)的分析、對(duì)安全檢測(cè)對(duì)象的行為數(shù)據(jù)分析、對(duì)安全系統(tǒng)報(bào)警事件的數(shù)據(jù)分析等。目前數(shù)據(jù)挖掘分析方法中常用的有:關(guān)聯(lián)分析、序列分析、分類分析、聚類分析。

3 基于數(shù)據(jù)挖掘的入侵檢測(cè)系統(tǒng)

入侵檢測(cè)系統(tǒng)的任務(wù)就是在提取到的龐大的檢測(cè)數(shù)據(jù)中找到入侵的痕跡。入侵分析過(guò)程需要將提取到的事件與入侵檢測(cè)規(guī)則進(jìn)行比較，從而發(fā)現(xiàn)入侵行為。

本文設(shè)計(jì)的入侵檢測(cè)系統(tǒng)其系統(tǒng)模塊如圖1所示。

4 序列模式挖掘的研究

序列模式挖掘可以分為五個(gè)具體階段，分別是排序階段、大項(xiàng)集階段、換階段、序列階段以及選最大階段。目前主要的序列模式挖掘算法包括:AprioriAll、SPADE、PrefixSpan、SPAM等算法。本文提出一種改進(jìn)的基于位圖的序列模式挖掘算法(sequential patterns mining based on bitmap representation， SMBR)，與SPAM算法不同，SMBR算法對(duì)序列模式的某些術(shù)語(yǔ)進(jìn)行了重新定義。

定義1 序列數(shù)據(jù)庫(kù)D是元組的集合，sid為序列標(biāo)識(shí)號(hào)。如果序列T是S的子序列(即TíS)，稱元組包含序列T，則序列T在序列數(shù)據(jù)庫(kù)D中的支持?jǐn)?shù)是數(shù)據(jù)庫(kù)中包含T的元組數(shù)，即support(T)=|{|?DùTíS }|，記作support(T)。給定一個(gè)最小支持度閾值minsup，如果序列s的支持度不小于minsup，則稱序列s為頻繁序列模式。

定義2序列擴(kuò)展-SE(Sequence Extension)。是在原序列s的末尾添加一個(gè)項(xiàng)，新添加項(xiàng)作為序列的一個(gè)新元素，即s◇sα=。項(xiàng)擴(kuò)展-IE(Item Extension)。是在原序列s的末尾添加一個(gè)項(xiàng)， 該新添加項(xiàng)和原序列s的最后一個(gè)元素來(lái)組成一個(gè)新的元素，其中新添加項(xiàng)為新元素的最后一項(xiàng)，即s◇iα= 且k∈an， k<α(表示k發(fā)生在α前面)。

性質(zhì)1(Apriori性質(zhì)) 如果一個(gè)序列s的支持度小于minsup，也就是不頻繁的序列模式，那么該序列s的任何超序列都是不頻繁的序列。

推理1(SE(Sequence Extension)剪枝) 如果存在序列s=不滿足最小支持度minsup，那么序列s進(jìn)行序列擴(kuò)展產(chǎn)生新序列s◇sα=也不頻繁。即在產(chǎn)生候選序列時(shí)，不必在節(jié)點(diǎn)序列s上進(jìn)行序列擴(kuò)展。

推理2(IE(Item Extension)剪枝) 如果存在序列s=不滿足最小支持度minsup，那么序列s進(jìn)行項(xiàng)擴(kuò)展產(chǎn)生新序列s◇iα=也不頻繁。即在產(chǎn)生候選序列時(shí)，不必在節(jié)點(diǎn)序列s上進(jìn)行項(xiàng)擴(kuò)展。

為了快速計(jì)數(shù)提出一種簡(jiǎn)化位圖結(jié)構(gòu)來(lái)表示序列數(shù)據(jù)庫(kù)。將序列數(shù)據(jù)庫(kù)(表1)轉(zhuǎn)化為頻繁序列首位置表(the first_position table， FPT)(表2)和重復(fù)項(xiàng)簡(jiǎn)單位圖表(the simple bitmap table， BT)(表3)。頻繁序列首位置表構(gòu)造方法:以序列中元素為計(jì)數(shù)單位，若序列首次出現(xiàn)在序列中第幾個(gè)元素則標(biāo)示幾;若該序列沒(méi)有出現(xiàn)，則在該序列位置標(biāo)示0。重復(fù)項(xiàng)簡(jiǎn)單位圖表構(gòu)造方法:以序列中元素為計(jì)數(shù)單位，將同一序列中重復(fù)項(xiàng)以(0 1)簡(jiǎn)單位圖形式標(biāo)示，若重復(fù)項(xiàng)出現(xiàn)在某元素位置則標(biāo)示1，否則標(biāo)示0。

SMBR算法描述

算法1 生成并簡(jiǎn)化FPT表和BT表算法

1: For each sequence si

2: For each element ei∈si

3:For each item k∈ei

4:FPk(si)=j;

5: Bitk(si)=1;

6:For each item k in FPT

7:If count(k)

8: Remove the tuple [k， FPk()] from FPT;

9:Remove Bitk()from BT;

10: Else

11: L1= L1∪{K};

12:If count si (k)=<1

13: Remove Bitk(si) corresponding si in BT。

算法2 生成所有頻繁序列算法

輸入:FPT表和BT表，用戶定義最小支持度minsup;輸出:所有頻繁序列模式S={L1， L2，… Lk}

1:For each frequent sequence Lp

2:Generate Cp+1 by SE() and IE();

3:For each frequent sequence Lp

4:For each item T in Lp

5: Call FPLp()and FPT();

6: IF FPLp(si)

7: FPCp+1(si)= FPT(si);

8: Continue to compare FPLp(si+1) and FPT(si+1);

9: Else

10: Call BitT(si)，

11: If FPLp(si)<{FPT(si)+h}

12: FPCp+1(si)={ FPT(si)+h};

13:Continue to compare FPLp(si+1) and FPT(si+1);

14: Else

15: Continue to perform the left_shift operation until the last bit;

16: If FPLp(si)>{FPT(si)+h}

17:FPCp+1(si)=0;

18:IF FPLp(si)=FPT(si)

19: FPCp+1(si)= FPT(si);

20: Continue to compare FPLp(si+1) and FPT(si+1);

21:Else

22: Call BitT(si)， Perform the left_shift

operation until the second value “1”apprear;

23:If FPLp(si)={FPT(si)+h}

24: FPCp+1(si)={ FPT(si)+h};

25:Continue to compare FPLp(si+1)

and FPT(si+1);

26: Else

27: Continue to perform the left_shift

operation until the last bit;

28:If FPLp(si)=!{FPT(si)+h}

29: FPCp+1(si)=0;

30: If count(Cp+1)>=mincount

31:Lp+1=Lp+1∪{Cp+1};

32: S=S∪{ L1，L2，…LP…}。

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

為測(cè)試SMBR算法的有效性，在Windows XP、Pentium IV 2.8GHz、內(nèi)存512MB實(shí)驗(yàn)環(huán)境下利用Visual C++實(shí)現(xiàn)對(duì)算法的測(cè)試，主要參數(shù)依據(jù):|D|:總序列交易數(shù)、|C|:序列中交易的平均長(zhǎng)度、|T|:交易中項(xiàng)的平均長(zhǎng)度、|S|:最大序列平均長(zhǎng)度|I|:最大序列中交易的平均長(zhǎng)度。本文將SMBR算法與SPAM算法、BitSPADE算法在算法執(zhí)行時(shí)間和內(nèi)存使用情況兩方面進(jìn)行比較:第1組實(shí)驗(yàn)是對(duì)數(shù)據(jù)集(D3KC6T5S5I5)，分別在0.05、0.1、0.15、0.2、0.25等5個(gè)不同最小支持度minSup下的算法執(zhí)行時(shí)間，其實(shí)驗(yàn)結(jié)果如圖2所示。第3組實(shí)驗(yàn)加大數(shù)據(jù)庫(kù)事務(wù)數(shù)，同時(shí)提高最小支持度minSup，對(duì)數(shù)據(jù)集(D10KC15T10S10I10)，分別在0.65、0.7、0.75、0.8、0.85等5個(gè)不同最小支持度minSup下的算法執(zhí)行時(shí)間，其實(shí)驗(yàn)結(jié)果如圖2所示。

由圖2可以得出，支持度小于0.2時(shí)，SMBR算法執(zhí)行時(shí)間小于SPAM算法和算法BitSPADE，支持度大于0.2時(shí)，三種算法執(zhí)行時(shí)間相當(dāng)。對(duì)于小數(shù)據(jù)集(D3KC6T5S5I5)，支持度相對(duì)較大時(shí)，滿足minSup≥0.2條件的序列銳減，SMBR算法無(wú)法發(fā)揮簡(jiǎn)化位圖結(jié)構(gòu)的優(yōu)勢(shì)。由圖3可以得出，當(dāng)數(shù)據(jù)集增大時(shí)，SMBR算法執(zhí)行時(shí)間和其他兩種算法執(zhí)行時(shí)間拉開(kāi)差距，SMBR算法充分發(fā)揮簡(jiǎn)化位圖優(yōu)勢(shì)，利用序列首位置和被擴(kuò)展項(xiàng)首位置快速運(yùn)算，快速統(tǒng)計(jì)計(jì)數(shù)，減低時(shí)間復(fù)雜度。由圖可見(jiàn)對(duì)大數(shù)據(jù)集(D10KC15T10S10I10)當(dāng)minSup≤0.7時(shí)，SMBR算法執(zhí)行時(shí)間減少近SPAM算法執(zhí)行時(shí)間的三分之一，SMBR算法執(zhí)行時(shí)間減少近BitSPADE算法執(zhí)行時(shí)間的二分之一。

6 結(jié)論

將數(shù)據(jù)挖掘技術(shù)引入入侵檢測(cè)是近年來(lái)新出現(xiàn)的研究領(lǐng)域.序列挖掘是數(shù)據(jù)挖掘的重要范疇.本文提出了一種基于位圖序列模式挖掘算法，并將其應(yīng)用于入侵檢測(cè)技術(shù)中。通過(guò)實(shí)驗(yàn)檢測(cè)，證明SMBR算法與SPAM算法相比，有更高的網(wǎng)絡(luò)入侵檢測(cè)效率。隨著數(shù)據(jù)挖掘技術(shù)在入侵檢測(cè)的設(shè)計(jì)開(kāi)發(fā)領(lǐng)域廣泛應(yīng)用，數(shù)據(jù)挖掘技術(shù)會(huì)發(fā)展得越來(lái)越完善。

參考文獻(xiàn):

[1] 戴英俠，連一峰，王航.系統(tǒng)安全與入侵檢測(cè)[M].北京:清華大學(xué)出版社，2002.

[2] Han Jiawei，Kamber M.Data Mining:Concepts and Techniques[M].北京:機(jī)械工業(yè)出版社，2001.

[3] Agrawal R，Srikant R.Mining Sequential Patterns[C] // Taipei:Proceedings of the Eleventh International Conference on Data Engineering，1995:3-10.

[4] Lee Wenke.Stolfo S J.Data mining approaches for intrusion detection[C]//San Antonio:Proc of the 7Th USENIX Security Symp，1998.

[5] 毛國(guó)君，段立娟.數(shù)據(jù)挖掘原理與算法[M].北京:清華大學(xué)出版社，2005.