Fp樹算法的研究以及在入侵檢測中的應用

1、Fp樹算法的研究以及在入侵檢測中的應用 江蘇大學 碩士學位論文 Fp樹算法的研究以及在入侵檢測中的應用 姓名：黃學平 申請學位級別：碩士 專業(yè)：計算機應用技術 指導教師：薛安榮 20080605 江蘇大學碩士研究生畢業(yè)論文 摘 要 關聯(lián)規(guī)則是數(shù)據(jù)挖掘的一個重要研究方向，旨在挖掘項集之間的內(nèi)在聯(lián)系。 Fp樹算法是關聯(lián)規(guī)則的一種基于深度的典型算法，具有良好的性能和可擴展性。 Fp樹通過自頂向下構(gòu)造頻繁樹和自底向上挖掘頻繁項集，只需掃描事務數(shù)據(jù)庫 兩次便可以有效的挖掘出頻繁項集，因而比基于寬度的Apriori算法快一個數(shù)量 級。但是，F(xiàn)p樹采用遞歸的方法，同一條路徑需要多次遍歷，這成為制約Fp樹 算

2、法效率的瓶頸。改進后的算法采用空間換時間的方法在每個節(jié)點上添加一個標 記位來標識該節(jié)點是否被遍歷，首先通過遍歷Fp樹找到所有葉子節(jié)點，然后從 頭表找出樹中的葉子節(jié)點，從葉子節(jié)點開始回溯樹中的路徑，將同一條路徑存儲 在一個線性鏈表中，從而減少同一條路徑的遍歷次數(shù)。實驗顯示：改進后的算法 對于稀疏事務數(shù)據(jù)和稠密事務數(shù)據(jù)都能有效的提高挖掘效率，雖然增加了標記位 的空間消耗，但是同時減少了條件Fp樹的生成，因而空間性能也有所提高。 入侵檢測是數(shù)據(jù)挖掘的一個重要應用方向，而挖掘算法效率的提高則是其中 的一個研究熱點。本文分析了當前入侵檢測的研究進展，采用Jpcap開源庫設計 了入侵檢測的數(shù)據(jù)采集模塊。將

3、改進后的Fp算法應用于入侵檢測中的關聯(lián)規(guī)則 挖掘中，采用主軸因子和參考因子有效地過濾頻繁項集來獲得規(guī)則集，通過模式 比較來獲得入侵行為。采用林肯實驗室的1998年的網(wǎng)絡實時數(shù)據(jù)進行實驗，將 改進后的Fp樹算法應用到關聯(lián)規(guī)則的模式庫挖掘中，采用不同的支持度來挖掘 訓練數(shù)據(jù)集和測試數(shù)據(jù)集。實驗結(jié)果顯示，對于入侵數(shù)據(jù)，改進后的Fp樹算法 比原Fp樹算法挖掘效率更高。檢測結(jié)果顯示，改進后的算法具有良好的檢測率 和較低的誤檢率。 關鍵詞： Fp樹，入侵檢測，數(shù)據(jù)挖掘，關聯(lián)規(guī)則 江蘇大學碩士研究生畢業(yè)論文 ABSTRACT mle researchdireCtionofdata isto Associat

4、ionis鋤imponant miIlin2Itspm口ose findoutmeinhertliIll【softhe Tteeis it鋤setsFpa帥icaId印thbasedal擘rorit量lIIl of舔sociation tlle mle，whichh觴900dperf0肌觚ce鋤dscalabilityByconstmcting tlle and tlle me to bottom it鋤sets丘Dm f equent仃fbmtop mimngthe向equent tome treecanmine itemsetswithin2 of bottomtop，F(xiàn)p me仔eque

5、m tim鷦scanniIlg the itisl0times thaIlmewide-baSed databaSe，so quicker Ap訂orialgorimmHoweV吼 duetotherecursive s鋤e be廿aVeledforseveral method，thepammay timeS，whiCh the the becomesthemainfactorthataa、ectsthe of e銜ciency a190rithmByusing to me amarkto Ilodeofthe m鋤oryreducetime，theimprovedalgoritaddseVe

6、ry treetod鋤onstratewhetherthenodeisvisitedAtfirstt11e the algoritllrIl位els wholetreeto aUtheleaf then行omtheheadtableofthetreeto6ndout Pret sets，aIld andstore hDmtheleaftotheroot linl 1ist theleafsetsinthetree thewholepam ina showsthat：the hasamuchbetter not Theexperience improvedal擘roritluIl e伍cienc

7、y fort le datab嬲ebutalsoforthedcflse t11emark only spafSe databaSeA1thou曲adding theConditionandhas causesome Hlduces tre：e maV space，theimprovedalPromm Fp abetter in thantree pe舶nnancespaceFp Intrusiondetectionisan ofdata importantapplication笛pectmining，while a the the is hotresearchThis a190rithIn

8、impr0Vingmining e伍ciency paperaJlalysises oftheintnJSion to reSearch progress detection，andus骼JpcapopsouIcedesi印the datacollcction the to the it鋤setS， moduleByusingimpr0Vedalgorithmget fbquent tllis usesthe factoraIldreferc 11cefactortofilter tlle paper spindle mles，鋤dcompares to behaviorThel998Linc

9、olnLabsrealtimen舐vorkdata pattemgettheintrusion setsandtIle areusedinthe di仃打鋤t are improveda1盛oritlll experience， suppons that usedinthe data鋤dtestdataTheresultshowsthe training improvedal星rorittlIIl thanthe treefortheintrusiondataaIldalsohas hasa塒【uchmoree伍ciency Fp a星rood detectionrateandlowmisdc

10、tectionrate 11lle 1 eywords：Fptree，intmsiondetection，datamillin私sociation 學位論文版權使用授權書 本學位論文作者完全了解學校有關保留、使用學位論文的規(guī)定，同意學校保 留并向國家有關部門或機構(gòu)送交論文的復印件和電子版，允許論文被查閱和借 閱。本人授權江蘇大學可以將本學位論文的全部內(nèi)容或部分內(nèi)容編入有關數(shù)據(jù)庫 進行檢索，可以采用影印、縮印或掃描等復制手段保存和匯編本學位論文。 在 保密口， 年解密后適用本授權書。 本學位論文屬于 不保密團 指導教師簽名： 學位論文作者簽名：董哮乎 艫年月l日 移年參月 7日 本人鄭重聲明：所

11、呈交的學位論文，是本人在導師的指導下， 獨立進行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容以 外，本論文不包含任何其他個人或集體己經(jīng)發(fā)表或撰寫過的作品 成果。對本文的研究做出重要貢獻的個人和集體，均已在文中以 明確方式標明。本人完全意識到本聲明的法律結(jié)果由本人承擔。 學位論文作者簽名：覆豸尹 易月勿月 11日 日期：j，J呸年日期：j，J哂年 11日 江蘇大學碩士研究生畢業(yè)論文 第一章緒論 11課題的研究背景及意義 計算機科學技術的迅猛發(fā)展對人類社會產(chǎn)生巨大的影響，一場信息革命正在 醞釀。人們認知自然、改造自然的方式也隨之發(fā)生變化，在眾多領域，計算機正 逐漸代替人類完成一些極具挑戰(zhàn)性的任務

12、，24年，美國“勇氣”號宇宙飛船 成功踏上火星，不僅鼓舞人類探索自然的勇氣，同時還說明計算機在人類生活中 已開始扮演著越來越重要的角色。 in 數(shù)據(jù)庫中的知識發(fā)現(xiàn)n1 KnowledgeDiscovery 年在第一界KDD會議上提出，它強調(diào)的是通過數(shù)據(jù)驅(qū)動發(fā)現(xiàn)方法，獲得“知識”。 KDD是指從數(shù)據(jù)庫中抽取出其中隱含的、新穎的、有用的信息的非平凡過程，即 從大型數(shù)據(jù)庫的數(shù)據(jù)中提取入們感興趣的知識。這些知識是隱含的、事先來知的、 Mining 就是從大量的數(shù)據(jù)中提取或“挖掘知識”，也就是從大量不安全的、有噪聲的、 模糊的或者隨機的數(shù)據(jù)中提取人們事先不知道的但又是有用的信息和知識。關聯(lián) Rule 規(guī)

13、則挖掘1 AssoeiationMining 是數(shù)據(jù)挖掘研究的一個重要分支，是 數(shù)據(jù)挖掘的眾多知識類型中最為典型的一種。關聯(lián)規(guī)則挖掘可以發(fā)現(xiàn)存在于數(shù)據(jù) 知的和被隱藏的，也就是說不能通過數(shù)據(jù)庫的邏輯操作或統(tǒng)計的方法得出。隨著 科學技術的發(fā)展，我們獲取各種數(shù)據(jù)的能力提離得很快，需要挖掘的數(shù)據(jù)癢通常 極為龐大，如果采用一些基本算法，運算復雜度會很高，需要占用大量時間和空 間，這些將導致用戶滿意度下降，從而限制數(shù)據(jù)挖掘的應用和發(fā)展。所以，數(shù)據(jù) 挖掘的核心步驟是算法的設計階段，算法是影響數(shù)據(jù)挖掘效率的最重要的因素。 因此，研究設計出快速高效的挖掘算法熊有效提高數(shù)據(jù)挖掘的效率，擴展數(shù)據(jù)挖 掘的應用范圍，對

14、數(shù)據(jù)挖掘具有十分重要的意義。 計算機信息躁終已經(jīng)成為一個國家最為關鍵的政治、經(jīng)濟和軍事資源，也成 為國家實力的象征。網(wǎng)絡改變了人們的生活、工作方式，使信息的獲取、傳遞、 處理和利用更加高效、迅捷；但是網(wǎng)絡也使“黑客侵犯和操作一些重要的信息 t 江蘇大學碩士研究生畢業(yè)論文 和數(shù)據(jù)成為可能，因而引發(fā)了網(wǎng)絡信息安全與對抗問題。國內(nèi)由于以前計算機和 互聯(lián)網(wǎng)的普及較低，并且黑客的攻擊技術較為落后，因此，前幾年因為計算機和 網(wǎng)絡安全造成的問題暴露得不是太明顯。但是隨著近年計算機和互聯(lián)網(wǎng)的飛速發(fā) 展、普及，黑客攻擊技術的不斷提高，我們本就十分脆弱的系統(tǒng)面臨著越來越嚴 重的威脅。據(jù)調(diào)查，國內(nèi)考慮并實施完整安全

15、措施的機構(gòu)寥寥無幾，很多機構(gòu)僅 僅用了一些安全策略或根本無任何安全防范。近年來發(fā)生的中美、中日黑客大戰(zhàn) 就充分說明了國內(nèi)很多機構(gòu)安全的脆弱性。因此加強網(wǎng)絡的安全性已經(jīng)成為人們 必須面對的問題。 入侵檢測技術口1是一種積極主動的安全防護技術，成為了目前網(wǎng)絡上廣泛應 用的技術和管理手段。但是當前大多數(shù)的入侵檢測系統(tǒng)1是通過手工定制的方法 建立起來的，例如在誤用檢測系統(tǒng)中，一些入侵模式需要用特定的模式語言進行 手工編寫在異常監(jiān)測系統(tǒng)中，需要根據(jù)系統(tǒng)設計者的經(jīng)驗并利用審計數(shù)據(jù)的特征 和度量加以描述入侵模式。這使得入侵檢測的效率以及對付攻擊行為的能力受到 了一定的限制。因此，迫切需要有效的工具幫助人們及

16、時、準確地從海量的數(shù)據(jù) 中發(fā)現(xiàn)數(shù)據(jù)之間存在的關系或模式、找出有用的信息以便做出正確的決策。數(shù)據(jù) 挖掘正是這樣一種工具和技術。它的優(yōu)勢是可從大量的網(wǎng)絡數(shù)據(jù)以及主機的R志 數(shù)據(jù)中挖掘出J下常的或入侵性的行為模式。 把數(shù)據(jù)挖掘的算法融入到入侵檢測技術進行研究具有理論意義和實際應用 價值，因此本文的意義主要體現(xiàn)在以下三方面： 1 關聯(lián)規(guī)則的典型算法Fp樹算法對于稠密事務數(shù)據(jù)和稀疏事務數(shù)據(jù)都具 有良好的性能，但是要產(chǎn)生大量的條件頻繁樹。提高Fp樹算法的效率對于關聯(lián) 規(guī)則算法的研究以及相關的應用具有重要的意義。 2 入侵檢測是網(wǎng)絡信息系統(tǒng)的一種重要的動態(tài)防護手段，基于數(shù)據(jù)挖掘 的入侵檢測系統(tǒng)同益成為一個研

17、究熱點。如何提高入侵檢測的效率和提高入侵檢 測的精度則是一個重要的研究方向。挖掘引擎的核心算法的研究對于提高網(wǎng)絡安 全有著重要的意義。 3 數(shù)據(jù)挖掘和入侵檢測兩種技術的有效結(jié)合，為數(shù)據(jù)挖掘提供寬廣應用前 景的同時，也將極大地推動數(shù)據(jù)挖掘和入侵檢測技術本身的研究與發(fā)展。 12國內(nèi)外的研究現(xiàn)狀 數(shù)據(jù)挖掘技術的迅速發(fā)展使得它在入侵檢測領域中得到廣泛的應用。當前， 2 江蘇大學碩士研究生畢業(yè)論文 國內(nèi)外已有很多研究機構(gòu)及大學教研室從事基于數(shù)據(jù)挖掘的入侵檢測方面的研 究工作。 最早將關聯(lián)規(guī)則引入入侵檢測中進行研究的是美國C01umbia大學weeke Lee$81所在的課題組。WeekeLee提出了一個

18、構(gòu)造入侵檢測模型的數(shù)據(jù)挖掘框架 AuditDataforAutomatedModelsforIntrusion MADAMID Mining Detection 。 weeke Lee對通用的關聯(lián)分析算法進行了改進，在基于統(tǒng)計學度量的支持度和可 信度的基礎上，提出了與領域知識密切相關的興趣度量度，用以指導關聯(lián)挖掘過 程。通過引入主軸屬性和參考屬性的概念剪除了無關模式，引入逐層近似挖掘概 念解決重要的低頻模式挖掘問題，用相對支持度解決屬性值分布不均勻的問題， 這些研究成果使得檢測模型獲得了較好的檢測率。 其它有代表性的成果還包括GeorgeMason大學DanielBarbara等人研究的面 D

19、ata and 向入侵檢測的數(shù)據(jù)挖掘ADAM陽1 AuditAna】ysis Mining 。ADAM從 tcpdump審計軌跡中挖掘頻繁模式，并以此發(fā)現(xiàn)入侵。ADAM首先將TCPIP流量數(shù) 據(jù)進行預處理，從每個數(shù)據(jù)包中抽取其頭部信息，為每個連接建立一個連接記錄， 挖掘過程在連接記錄數(shù)據(jù)集上進行。ADAM的挖掘引擎是由一組關聯(lián)規(guī)則挖掘算法 所組成的，用以實現(xiàn)訓練和檢測任務，挖掘引擎的輸出是一組可疑的關聯(lián)規(guī)則， 然后由分類引擎進行進一步處理。它是一個實時的異常入侵檢測系統(tǒng)，其主要缺 點是對純凈數(shù)據(jù)的依賴較多，雖然具有一定的檢測未知入侵類型的能力，但誤報 率較耐10】。 ofNew Univers

20、ityMexico UNM 的StephanieForrest叫2研究組進行的是 針對主機系統(tǒng)調(diào)用的審計數(shù)據(jù)分析處理，最初的思想是基于生物免疫系統(tǒng)的概 念，無論是針對生物機體還是針對計算機系統(tǒng)，免疫系統(tǒng)的關鍵問題在于：使用 一組穩(wěn)定的、并且在不同個體之間存在足夠差異的特征 features 來描述自我， 從而使系統(tǒng)具備識別“自我非自我”的能力。然而，對于計算機系統(tǒng)來說，要 解決這個問題相當困難。由于惡意代碼隱藏在正常代碼之中難以區(qū)分且系統(tǒng)的可 能狀態(tài)幾乎是無限的，要尋找一組穩(wěn)定的特征來定義“自我并不容易。Stephanie Forrest使用短序列匹配算法對特定的特權程序所產(chǎn)生的系統(tǒng)調(diào)用序列進

21、行了細 致的分析，并在這一領域做出了大量開創(chuàng)性工作。 在基于數(shù)據(jù)挖掘的入侵檢測研究方面，有代表性的國內(nèi)學者的研究成果包括 中國科學院研究生院選擇了層次化協(xié)作模型n31作為研究基礎，在模型中采用數(shù)據(jù) 3 江蘇大學碩士研究生畢業(yè)論文 挖掘算法對安全審計數(shù)據(jù)進行分析處理，以便幫助系統(tǒng)自動生成入侵檢測規(guī)則， 從而建立異常檢測模型；清華大學提出了一種基于數(shù)據(jù)挖掘方法的協(xié)同入侵檢測 建立檢測模型；華中科技大學的王卉n礎將最大頻繁項目集挖掘算法用于入侵檢 測；武漢大學電子信息學院的凌軍n剛等人提出并實現(xiàn)了一個基于規(guī)則的、層次化 的智能入侵檢測原型系統(tǒng)。 孫志強阻力為了解決入侵檢測在不降低精度的同時提高檢測速

22、度的問題，提高 Fptree的頭表結(jié)構(gòu)并引入關鍵屬性來挖掘原始審計數(shù)據(jù)中的頻繁模式，實驗結(jié) 果表明改進后的算法比傳統(tǒng)的關聯(lián)算法在入侵檢測中的應用效果更好。 張帆n踟等在分析幾種現(xiàn)有關聯(lián)規(guī)則算法的基礎上，針對網(wǎng)絡數(shù)據(jù)的具體情況， 引入關鍵屬性、參考屬性以及屬性相對支持度的約束，對關聯(lián)規(guī)則挖掘算法 FpGrowth進行了擴展，解決了基本關聯(lián)規(guī)則挖掘算法中產(chǎn)生大量無用模式的問 題，從而幫助系統(tǒng)發(fā)掘出更有意義的模式，提高了系統(tǒng)挖掘的執(zhí)行效率和規(guī)則庫的 準確度。 黃雯霆n鍆等在分析了傳統(tǒng)關聯(lián)規(guī)則算法缺點的基礎上，對關聯(lián)規(guī)則挖掘算法 的優(yōu)化策略和時態(tài)因素的分類處理重點進行了討論。即在利用主屬性約束最后規(guī)

23、則的同時，提出了高頻屬性直接入選的策略。以更快地獲取有效的入侵檢測規(guī)則 實驗測試結(jié)果表明，優(yōu)化后的算法在挖掘速度和規(guī)則的檢出率等性能上有較大提 高，找到了一些原來被忽略的規(guī)則并剔除了一些不重要的規(guī)則，證明此優(yōu)化算法 是切實有效的。 鄧菲楠啪1等針對入侵檢測系統(tǒng)中由于模式庫更新不及時造成的高誤報率和 漏報率，提出了協(xié)同數(shù)據(jù)挖掘的入侵檢測模型。該技術依據(jù)關聯(lián)規(guī)則，自動發(fā)現(xiàn)事 物問聯(lián)系的特性，利用關聯(lián)規(guī)則自動生成模式庫，并針對傳統(tǒng)Apriori算法的缺陷 引入加權關聯(lián)規(guī)則。實驗結(jié)果表明，該模型對已有的典型攻擊檢測率為90以上。 于楓乜門等提出了一種基于事件序列的頻繁情節(jié)挖掘算法，并將該算法用于基 于

24、網(wǎng)絡的入侵檢測中。實驗結(jié)果證明，與關聯(lián)規(guī)則挖掘算法相比較，頻繁情節(jié)挖掘 算法可以有效地提高入侵檢測系統(tǒng)的準確性，降低誤報率。 總之，國內(nèi)外對于數(shù)據(jù)挖掘在入侵檢測系統(tǒng)中的應用主要集中在如何提高入 侵檢測的挖掘效率和提高入侵檢測的檢測率兩個方面。其中，數(shù)據(jù)挖掘算法效率 4 江蘇大學碩士研究生畢業(yè)論文 的提高以及如何將挖掘算法應用到入侵檢測中是一個熱門的研究方向。 13研究的主要內(nèi)容 基于數(shù)據(jù)挖掘的入侵檢測系統(tǒng)的核心是挖掘算法的效率的提高以及如何提 高檢測精度，因此本文研究的內(nèi)容主要包括： 1 研究關聯(lián)規(guī)則中的Fp樹算法的優(yōu)缺點以及Fp樹的相關性質(zhì)，針對Fp 樹算法多次遍歷同一條路徑所產(chǎn)生的缺點，提

25、出一種采用增加節(jié)點標記位的方法 從葉子節(jié)點開始回溯減少同一條路徑的遍歷次數(shù)的fpc算法，并使用稠密事務數(shù) 據(jù)庫和稀疏事務數(shù)據(jù)庫進行測試，分析了改進后的算法的時間效率和空間效率。 2 入侵檢測的相關知識以及基于關聯(lián)規(guī)則的異常檢測系統(tǒng)的研究。針對 入侵檢測的數(shù)據(jù)特點，采用改進的Fp樹挖掘規(guī)則集，并用主軸因子和參考因子 來過濾規(guī)則庫得到有效的規(guī)則集。 3 設計了基于關聯(lián)規(guī)則的異常檢測系統(tǒng)，采用java開源包jpcap實現(xiàn)網(wǎng) 絡數(shù)據(jù)的監(jiān)聽，并將改進的Fp算法應用到該系統(tǒng)中，采用林肯實驗室1998年的 數(shù)據(jù)進行模擬實驗，將改進后的算法與原來的Fp算法的挖掘進行了比較，對于 訓練數(shù)據(jù)集和測試數(shù)據(jù)集采用不同

26、的支持度進行挖掘，并進行模式比較，得出規(guī) 則集與入侵行為，并分析了相關的檢測結(jié)果。 14論文的組織結(jié)構(gòu) 第一章緒論，闡述了網(wǎng)絡安全的現(xiàn)狀以及國內(nèi)外對基于數(shù)據(jù)挖掘的入侵檢 測的研究現(xiàn)狀，提出了本文的研究意義并概述了本文的研究內(nèi)容。 第二章入侵檢測的基本理論，介紹了入侵檢測以及入侵檢測系統(tǒng)的概念與 功能、入侵檢測的分類以及它們的區(qū)別。闡述了數(shù)據(jù)挖掘應用到入侵檢測中的優(yōu) 勢，介紹了國內(nèi)外基于數(shù)據(jù)挖掘的入侵檢測方法的研究，并重點介紹了關聯(lián)規(guī)則 的相關概念，為后文介紹關聯(lián)規(guī)則算法以及關聯(lián)規(guī)則算法在入侵檢測中的應用做 了鋪墊。 第三章Fp樹算法的相關知識，介紹了Fp算法的構(gòu)造過程以及Fp樹的完備 性和緊密

27、性。分析了Fp樹算法的優(yōu)缺點以及國內(nèi)外學者對Fp樹算法的改進。針 對Fp樹算法需要多次重復遍歷同一條路徑的缺點，提出了基于標記的改進方法， 并采用稠密數(shù)據(jù)庫和稀疏數(shù)據(jù)庫進行測試，對改進后的算法進行時間和空間兩方 面的分析。 5 汪蘇太學碩士研究生畢業(yè)論文 第四章基于改進的Fp樹算法的入侵檢測系統(tǒng)的研究，介紹了入侵檢測系統(tǒng) 的技術指標，改進了入侵檢測系統(tǒng)的模式，采焉jpc印包設計了數(shù)據(jù)采集模塊， 采用改進后的Fp樹算法設計了關聯(lián)規(guī)則挖掘模塊，采用林肯實驗室1998年的數(shù) 據(jù)作為閼絡實時數(shù)據(jù)，設計了數(shù)據(jù)預處理模塊，規(guī)剿過濾模塊，檢測模塊。 第血章對全文的工作做了總結(jié)，并提出了進一步的工作。 6 江

28、蘇大學碩士研究生畢業(yè)論文 第二章入侵檢測與數(shù)據(jù)挖掘技術 作為一種新型的、積極主動的安全防護體系的入侵檢測是新一代的網(wǎng)絡安全 技術，它在眾多研究人員的參與下快速的發(fā)展著，本文的研究離不開對入侵檢測 的相關內(nèi)容進行深入的認識與理解，因此對入侵檢測進行概述性的分析與研究是 非常必要的。 21 入侵檢測的定義和功能 1980年，Anderson船2。2盯首次提出了入侵檢測的概念。他將入侵定義為未經(jīng)授 權蓄意嘗試訪問信息、篡改信息、使系統(tǒng)不可靠或不可用。他將入侵行為劃分為 外部闖入、內(nèi)部授權、用戶的越權使用和濫用等三種類型，并提出用審計追蹤監(jiān) 視入侵威脅。 美國國際計算機安全協(xié)會對入侵檢測的定義是入侵檢

29、測是通過從計算機網(wǎng) 絡或計算機系統(tǒng)中的若干關鍵點收集信息并對其進行分析，從中發(fā)現(xiàn)網(wǎng)絡或系統(tǒng) 中是否有違反安全策略的行為和遭到襲擊跡象的一種安全技術。 1986年，美國斯坦福國際研究所首次提出了一種抽象入侵檢測模型。此模 型獨立于任何特殊的系統(tǒng)、應用環(huán)境、系統(tǒng)脆弱性或入侵種類。隨后，在此基礎 上，經(jīng)過二十年的發(fā)展，大量的入侵檢測系統(tǒng)己經(jīng)被研制出來，并得到了一定范 圍的應用。 IntrusionDetection 入侵檢測系統(tǒng) IDS System 可以使管理員能夠及時的 處理入侵警報，盡可能地減少入侵對系統(tǒng)造成的損害。由于入侵事件的實際危害 越來越大，對入侵檢測系統(tǒng)的關注也越來越多，入侵檢測系統(tǒng)

30、也就成為網(wǎng)絡安全 體系結(jié)構(gòu)中的一個重要環(huán)節(jié)。 一個入侵檢測系統(tǒng)應能夠具有以下功能： 1 監(jiān)視分析用戶和系統(tǒng)的行為； 2 審計系統(tǒng)的配置和漏洞； 3 評估敏感數(shù)據(jù)和系統(tǒng)的完整性； 4 識別攻擊行為； 5 對異常行為進行統(tǒng)計； 6 進行審計跟蹤，識別違反安全規(guī)則的行為； 這些特點結(jié)合起來，就可使系統(tǒng)管理員輕松的監(jiān)視、審計、評估網(wǎng)絡系統(tǒng)的 7 江蘇大學碩士研究生畢業(yè)論文 安全性。 22入侵檢測的分類 入侵檢測技術的出發(fā)點是，認為用戶或者程序在計算機上的任何操作 包括 合法和非法操作 都是可以被監(jiān)測的，并認為合法和非法操作對系統(tǒng)造成的結(jié)果 是截然不同的。入侵檢測從原理上可分為兩種檢測模型心鍆：誤用檢測

31、模型 Misuse Detection Detection Model 和異常檢測模型 Ano唿1yModel ，均可用于實時 檢測和事后檢測，對應的檢測方法是誤用入侵檢測和異常入侵檢測。 221 誤用檢測 誤用檢測方法是利用已知的系統(tǒng)缺陷和己知的入侵模式來進行入侵活動的 檢測，和病毒檢測的方法類似，因此又稱特征檢測1 Signaturedetection 。 執(zhí)行誤用檢測，需要具備以下幾個條件： 1 完備的規(guī)則模式庫： 2 可信的用戶行為記錄： 3 可靠的記錄分析技術： 誤用檢測依賴于模式庫，其關鍵是如何表達入侵的模式，以J下確區(qū)分真F的 入侵與J下常行為。與異常檢測相反，誤用檢測能直接檢測

32、不利的或違法的行為， 而異常檢測足發(fā)現(xiàn)同正常行為相違背的行為。它的優(yōu)點是能有針對性地建立高效 的IDS，檢測精度高，誤報率低。主要缺點是只能檢測到大部分或所有己知的攻 擊和入侵模式，不能檢測到未知的入侵和已知入侵的變種，因此可能發(fā)生漏報。 同時，對具體系統(tǒng)的依賴性太強，移植性較差。 222異常檢測 異常檢測 Anomalydetection 是利用正常用戶和系統(tǒng)的行為特征來檢測當 前行為的背離度，以確定當前行為是否為入侵行為。異常檢測技術假定所有入侵 行為都是與正常行為不同的，即假設入侵活動是異?；顒拥淖蛹孟到y(tǒng)或用 戶的正常行為模式檢測入侵。 異常入侵檢測的主要工作分為兩個階段：學習階段

33、和檢測階段。 1 學習階段：系統(tǒng)首先對提供的數(shù)據(jù) 訓練數(shù)據(jù) 進行學習、分析，從中歸 納、總結(jié)出訓練數(shù)據(jù)中存在的規(guī)律，為系統(tǒng)建立安全模型。這是一種有指導的學 習，提供學習的訓練數(shù)據(jù)可以是安全狀態(tài)下的數(shù)據(jù)，也可以是入侵發(fā)生時的數(shù)據(jù)， 但都必需由安全人員指定數(shù)據(jù)所屬的類別 是正常數(shù)據(jù)還是入侵數(shù)據(jù) 。 8 江蘇大學碩士研究生畢業(yè)論文 2 檢測階段：系統(tǒng)以學習階段建立的安全模型為標準，對實際檢測的數(shù)據(jù) 進行分析，并對不符合安全模型標準的數(shù)據(jù)進行記錄并報警。 理想狀況下的異?；顒蛹c入侵性活動集等同，若能檢測所有的異?；顒樱?才可檢測所有入侵性活動。而實際上入侵性活動并不等同異?；顒?，這里存在4 種可能情

34、況： 1 入侵但非異常； 2 非入侵且非異常； 3 非入侵但異常； 4 入 侵且異常。因此，異常入侵要解決的問題就是構(gòu)造異?；顒蛹闹邪l(fā)現(xiàn)入侵性 活動子集。 223兩種檢測技術的比較 1 檢測結(jié)果 誤用檢測檢測率相對較高，因為檢測的匹配條件描述清楚，所以可以明確指 示出當前發(fā)生攻擊的類型，但是只能檢測到已知的攻擊模式，而異常檢測檢測率 相對較低，盡管無法明確指示攻擊為何種類型，但是可以檢測到未知的入侵行為。 2 誤報警率 誤用檢測相對較低，而異常檢測相對較高，因為系統(tǒng)的正?；顒邮遣粩嘧兓?的，需要不斷的學習，所以在學習階段，異常模式在正常工作可能會生成額外的 虛假報警信號，或者在此階段，信息

35、系統(tǒng)遭受非法的入侵攻擊后，學習結(jié)果中可 能包含了相關的入侵行為的信息，使得今后系統(tǒng)無法檢測到此種入侵行為。 3 可移植性 誤用檢測的可移植性較差，需要在某個特定的環(huán)境下生效，而異常檢測較少 依賴特定的操作系統(tǒng)環(huán)境。 4 內(nèi)部用戶 誤用檢測對于檢測內(nèi)部用戶的誤用權限活動很困難，而異常檢測對內(nèi)部用戶 超越權限的違法行為檢測能力相對較強。 5 報告的數(shù)據(jù) 誤用檢測報告的數(shù)據(jù)是一條指示特定攻擊行為發(fā)生的警告信號，其中還包含 相關的提示數(shù)據(jù)，而異常檢測生成的數(shù)據(jù)量多，這些數(shù)據(jù)量都是超出期望行為范 圍的事件。 6 系統(tǒng)配置工作量 誤用檢測系統(tǒng)配置工作量較少，并且相對容易，而異常檢測比較難配置，需 要對系統(tǒng)

36、的已知和期望的行為模式做全面綜合的定義，因此也就需要更多的數(shù)據(jù) 9 江蘇火學碩士研究生畢業(yè)論定 收集、分析和更新工作。 2。3 數(shù)據(jù)挖掘用于入侵檢測中的優(yōu)勢 數(shù)據(jù)挖掘通常應用于市場行銷、金融投資、生產(chǎn)制造等領域，但在入侵檢測 設計領域中運用數(shù)據(jù)挖掘技術對網(wǎng)絡業(yè)務進行分析也具有嚼顯優(yōu)勢，主要體現(xiàn)在 以下幾方面： 1 霹絡中監(jiān)測到的數(shù)據(jù)量大且種類繁多，并具有穩(wěn)定的數(shù)據(jù)來源，適合 進行數(shù)據(jù)挖掘； 2 鼴絡中監(jiān)聽到的數(shù)據(jù)按其所具有的不同屬性可以進行分類，同時，不 同的數(shù)據(jù)之間的確存在有某種相關性，如一個連接往往伴隨另一種連接發(fā)生。因 此，運用數(shù)據(jù)挖掘技術對審計數(shù)據(jù)進行挖掘能夠得到有價值的信息； 3 從

37、各種渠道所獲得的審計數(shù)據(jù)，經(jīng)過加工處理之后適合運用數(shù)據(jù)挖掘 ? 中的聯(lián)系分析方法。 2。4入侵檢測中的數(shù)據(jù)挖掘方法 數(shù)據(jù)挖掘在入侵檢測中的應用一般包括數(shù)據(jù)源的選擇、數(shù)據(jù)預處理和挖掘算 法選擇幾個主要閥題，其關鍵之處就是在予挖掘算法的選擇。常用于入侵檢測巾 的數(shù)據(jù)挖掘算法主要有關聯(lián)規(guī)則分析、序列模式分析、分類分析以及聚類分析。 24。l關聯(lián)規(guī)則分析 關聯(lián)規(guī)則分析算法是本文主要研究和應用的算法，所以在第3章中將重點對 其進行分概與研究。下面先給出關聯(lián)規(guī)則分析的相關概念和屬性。 關聯(lián)規(guī)則是數(shù)據(jù)挖掘的一個重要的研究方向，它是RAgrawal瞳鯽等人1993 年首先提出的。它用于確定不同項目集之翔酶聯(lián)系

38、，找出關聯(lián)規(guī)則的挖掘，我們 可以找出事物之問的內(nèi)在聯(lián)系，為決策提供支持。關聯(lián)規(guī)則最初是用于商業(yè)中， 著名的啤酒和尿布的故事就是這個道理。 下面從數(shù)據(jù)挖掘出發(fā)，給出關聯(lián)規(guī)則形式化的定義。 假設薹 缸；，薹：，至 是項的集合。設任務相關的數(shù)據(jù)D是數(shù)據(jù)庫事務的集合， 其中每個事務T是項的集合，使得r互，。每一個事務有一個標識符，稱作TID。 設X是薹中項的集合，稱作項集 量毫e掇se專s ，事務善包含X當且僅當X主F。 如果X中有k個項目，則又稱X為k一項目集，或X的長度為k。 定義l：關聯(lián)規(guī)則泣 10 江蘇大學碩士研究生畢業(yè)論文 ny盤彩。 關聯(lián)規(guī)則是形如X專y的蘊涵式，其中，石j，y王，盟X 規(guī)

39、則的支持度和置信度是規(guī)則興趣度的兩種度量。它們分別反映所發(fā)現(xiàn)的規(guī) 則的有用性和確定性。 u】， 規(guī)則X一】，在事務集D中成立，具有支持度s，其中s是D中事務包含X 的百分比。它是概率P Xuy 。攬劉x專y在事務集D中具有置信度e，其 x 。即 中c是D中包含x的事務同時也包含Y的百分比。這是條件概率P Y 2一1 support Xy p Xuy confidence X爭y P YlX 22 稱作強規(guī)則。滿足最小支持度的項集稱為頻繁項集 frequent“emset 。 關聯(lián)規(guī)則主要有基于寬度的算法和基于深度的算法?；趯挾鹊乃惴ㄍㄟ^挖 掘頻繁k一項集來挖掘頻繁k+卜項集，該類算法需要多次

40、掃描事務數(shù)據(jù)庫，因而效 典型代表，需掃描數(shù)據(jù)集的次數(shù)等于最大頻繁項目集的項臣數(shù)。磊prioriTid算法 在Apriori算法的基礎上對數(shù)據(jù)集進行修剪，以減少掃描數(shù)據(jù)庫的時間，但對數(shù) 據(jù)集的修剪需要額外的計算和IO操律。D P算法采用哈希技術對數(shù)據(jù)集和候選項 目集進行修剪，特別是對候選2項目集的修剪特別有效。AprioriHybrid算法是 次掃描完數(shù)據(jù)集之后計算修剪后的數(shù)據(jù)集的大?。蝗粜藜艉蟮臄?shù)據(jù)集可在內(nèi)存中 進行處理，燹|j切換至AprioriTid算法直到找出所有的頻繁項目集。 基于深度的算法的思想是采用樹的深度遍歷的方式來挖掘頻繁項集，該類算 法比基于寬度的算法效率高效得多。此類算法中最新最高效的是JHan等人提出 的Fpgrowth算法1。目前已經(jīng)提出的用于發(fā)現(xiàn)最大頻繁模式的典型算法有 滟fia洶3以及Gen四等。磷afia采用垂直二進制位圖表示投影數(shù)據(jù)庫，同時使用 parentequivalencepruning和dynalnicreordering等方法來減少搜索空聞； ve Gen也采用數(shù)據(jù)庫垂直投影方法，同時使用了progr