基于序列模式挖掘的入侵檢測技術研究
2009-04-29 00:00:00潘建生,胡孔法
電腦知識與技術 2009年36期
摘要:隨著計算機的發(fā)展，網(wǎng)絡安全在現(xiàn)代社會中扮演著越來越關鍵的角色，并成為比較嚴重的問題。該文詳細分析了基于序列模式的數(shù)據(jù)挖掘技術，并且在挖掘過程中提出了一種新的序列模式算法。
關鍵詞:入侵檢測;數(shù)據(jù)挖掘;序列模式挖掘
中圖分類號:TP393文獻標識碼:A文章編號: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
信息社會的到來，給全世界帶來了技術和經(jīng)濟飛速發(fā)展的契機。但是，隨著網(wǎng)絡技術在世界包括中國在內(nèi)的各個領域應用的深入開展，人們在進行資源共享的同時，也感受到信息安全問題的日益凸顯。由于計算機系統(tǒng)中硬件設備、操作系統(tǒng)、應用軟件不可避免地會存在一些安全方面的漏洞，而且Internet自身協(xié)議和結(jié)構(gòu)的初始設計也存在一些缺陷，所有這些都使“黑客”侵犯和操縱一些重要信息和數(shù)據(jù)成為可能。
1 網(wǎng)絡入侵檢測技術
入侵檢測通過對計算機網(wǎng)絡或計算機系統(tǒng)中的若干關鍵點收集信息并進行分析，從中發(fā)現(xiàn)網(wǎng)絡或系統(tǒng)中是否有違反安全策略的行為和被攻擊的跡象，進行入侵檢測的軟件與硬件的組合就是入侵檢測系統(tǒng)。入侵檢測系統(tǒng)執(zhí)行的主要任務包括:監(jiān)視、分析用戶及系統(tǒng)活動，審計系統(tǒng)構(gòu)造和弱點識別，反映已知進攻的活動模式，向相關人士報警，統(tǒng)計分析異常行為模式，評估重要系統(tǒng)和數(shù)據(jù)文件的完整性，審計、跟蹤管理操作系統(tǒng)，識別用戶違反安全策略的行為。
入侵檢測一般分為3個步驟，依次為信息收集、數(shù)據(jù)分析、響應(被動響應和主動響應)。入侵檢測系統(tǒng)可以從不同角度分類，包括檢測方法、檢測對象、反應機制、體系結(jié)構(gòu)、分析時間等。一般來說，主要從檢測對象、檢測方法來分類。根據(jù)檢測對象的不同可以分成基于主機的入侵檢測系統(tǒng)和基于網(wǎng)絡的入侵檢測系統(tǒng);根據(jù)檢測方法的不同可以分成誤用檢測系統(tǒng)和異常檢測系統(tǒng)。
2 數(shù)據(jù)挖掘技術
數(shù)據(jù)挖掘過程一般需要經(jīng)歷確定挖掘?qū)ο蟆?shù)據(jù)準備、模型建立、數(shù)據(jù)挖掘、結(jié)果分析和知識應用這樣幾個階段。目前數(shù)據(jù)挖掘技術在網(wǎng)絡安全領域的主要應用有:對安全檢測對象的海量的審計數(shù)據(jù)的分析、對安全檢測對象的行為數(shù)據(jù)分析、對安全系統(tǒng)報警事件的數(shù)據(jù)分析等。目前數(shù)據(jù)挖掘分析方法中常用的有:關聯(lián)分析、序列分析、分類分析、聚類分析。
3 基于數(shù)據(jù)挖掘的入侵檢測系統(tǒng)
入侵檢測系統(tǒng)的任務就是在提取到的龐大的檢測數(shù)據(jù)中找到入侵的痕跡。入侵分析過程需要將提取到的事件與入侵檢測規(guī)則進行比較，從而發(fā)現(xiàn)入侵行為。
本文設計的入侵檢測系統(tǒng)其系統(tǒng)模塊如圖1所示。
4 序列模式挖掘的研究
序列模式挖掘可以分為五個具體階段，分別是排序階段、大項集階段、換階段、序列階段以及選最大階段。目前主要的序列模式挖掘算法包括:AprioriAll、SPADE、PrefixSpan、SPAM等算法。本文提出一種改進的基于位圖的序列模式挖掘算法(sequential patterns mining based on bitmap representation， SMBR)，與SPAM算法不同，SMBR算法對序列模式的某些術語進行了重新定義。
定義1 序列數(shù)據(jù)庫D是元組
定義2序列擴展-SE(Sequence Extension)。是在原序列s的末尾添加一個項，新添加項作為序列的一個新元素，即s◇sα=
性質(zhì)1(Apriori性質(zhì)) 如果一個序列s的支持度小于minsup，也就是不頻繁的序列模式，那么該序列s的任何超序列都是不頻繁的序列。
推理1(SE(Sequence Extension)剪枝) 如果存在序列s=
推理2(IE(Item Extension)剪枝) 如果存在序列s=
為了快速計數(shù)提出一種簡化位圖結(jié)構(gòu)來表示序列數(shù)據(jù)庫。將序列數(shù)據(jù)庫(表1)轉(zhuǎn)化為頻繁序列首位置表(the first_position table， FPT)(表2)和重復項簡單位圖表(the simple bitmap table， BT)(表3)。頻繁序列首位置表構(gòu)造方法:以序列中元素為計數(shù)單位，若序列首次出現(xiàn)在序列中第幾個元素則標示幾;若該序列沒有出現(xiàn)，則在該序列位置標示0。重復項簡單位圖表構(gòu)造方法:以序列中元素為計數(shù)單位，將同一序列中重復項以(0 1)簡單位圖形式標示，若重復項出現(xiàn)在某元素位置則標示1，否則標示0。
SMBR算法描述
算法1 生成并簡化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 實驗分析 為測試SMBR算法的有效性，在Windows XP、Pentium IV 2.8GHz、內(nèi)存512MB實驗環(huán)境下利用Visual C++實現(xiàn)對算法的測試，主要參數(shù)依據(jù):|D|:總序列交易數(shù)、|C|:序列中交易的平均長度、|T|:交易中項的平均長度、|S|:最大序列平均長度|I|:最大序列中交易的平均長度。本文將SMBR算法與SPAM算法、BitSPADE算法在算法執(zhí)行時間和內(nèi)存使用情況兩方面進行比較:第1組實驗是對數(shù)據(jù)集(D3KC6T5S5I5)，分別在0.05、0.1、0.15、0.2、0.25等5個不同最小支持度minSup下的算法執(zhí)行時間，其實驗結(jié)果如圖2所示。第3組實驗加大數(shù)據(jù)庫事務數(shù)，同時提高最小支持度minSup，對數(shù)據(jù)集(D10KC15T10S10I10)，分別在0.65、0.7、0.75、0.8、0.85等5個不同最小支持度minSup下的算法執(zhí)行時間，其實驗結(jié)果如圖2所示。 由圖2可以得出，支持度小于0.2時，SMBR算法執(zhí)行時間小于SPAM算法和算法BitSPADE，支持度大于0.2時，三種算法執(zhí)行時間相當。對于小數(shù)據(jù)集(D3KC6T5S5I5)，支持度相對較大時，滿足minSup≥0.2條件的序列銳減，SMBR算法無法發(fā)揮簡化位圖結(jié)構(gòu)的優(yōu)勢。由圖3可以得出，當數(shù)據(jù)集增大時，SMBR算法執(zhí)行時間和其他兩種算法執(zhí)行時間拉開差距，SMBR算法充分發(fā)揮簡化位圖優(yōu)勢，利用序列首位置和被擴展項首位置快速運算，快速統(tǒng)計計數(shù)，減低時間復雜度。由圖可見對大數(shù)據(jù)集(D10KC15T10S10I10)當minSup≤0.7時，SMBR算法執(zhí)行時間減少近SPAM算法執(zhí)行時間的三分之一，SMBR算法執(zhí)行時間減少近BitSPADE算法執(zhí)行時間的二分之一。 6 結(jié)論 將數(shù)據(jù)挖掘技術引入入侵檢測是近年來新出現(xiàn)的研究領域.序列挖掘是數(shù)據(jù)挖掘的重要范疇.本文提出了一種基于位圖序列模式挖掘算法，并將其應用于入侵檢測技術中。通過實驗檢測，證明SMBR算法與SPAM算法相比，有更高的網(wǎng)絡入侵檢測效率。隨著數(shù)據(jù)挖掘技術在入侵檢測的設計開發(fā)領域廣泛應用，數(shù)據(jù)挖掘技術會發(fā)展得越來越完善。 參考文獻: [1] 戴英俠，連一峰，王航.系統(tǒng)安全與入侵檢測[M].北京:清華大學出版社，2002. [2] Han Jiawei，Kamber M.Data Mining:Concepts and Techniques[M].北京:機械工業(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] 毛國君，段立娟.數(shù)據(jù)挖掘原理與算法[M].北京:清華大學出版社，2005.
