數(shù)據(jù)挖掘-西安電子科技大學(xué)軟件學(xué)院

1、1,數(shù)據(jù)挖掘與商務(wù)智能Data Mining & Business Intelligence,西安電子科技大學(xué)　軟件學(xué)院主講人：黃健斌,第八章 異常檢測(cè),內(nèi)容提綱,異常挖掘及其應(yīng)用異常檢測(cè)面臨的主要問(wèn)題異常數(shù)據(jù)挖掘方法簡(jiǎn)介異常檢測(cè)的應(yīng)用案例參考文獻(xiàn),內(nèi)容提綱,異常挖掘及其應(yīng)用異常檢測(cè)面臨的主要問(wèn)題異常數(shù)據(jù)挖掘方法簡(jiǎn)介異常檢測(cè)的應(yīng)用案例參考文獻(xiàn),什么是異常(Outlier)？,Hawkins的定義：異常是在

2、數(shù)據(jù)集中偏離大部分?jǐn)?shù)據(jù)的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)的偏離并非由隨機(jī)因素產(chǎn)生，而是產(chǎn)生于完全不同的機(jī)制。Weisberg的定義：異常是與數(shù)據(jù)集中其余部分不服從相同統(tǒng)計(jì)模型的數(shù)據(jù)。Samuels的定義：異常是足夠地不同于數(shù)據(jù)集中其余部分的數(shù)據(jù)。Porkess的定義：異常是遠(yuǎn)離數(shù)據(jù)集中其余部分的數(shù)據(jù),異常數(shù)據(jù)具有特殊的意義和很高的實(shí)用價(jià)值,現(xiàn)有數(shù)據(jù)挖掘研究大多集中于發(fā)現(xiàn)適用于大部分?jǐn)?shù)據(jù)的常規(guī)模式,在許多應(yīng)用領(lǐng)域中，異常數(shù)據(jù)通常作為噪音而忽略

3、，許多數(shù)據(jù)挖掘算法試圖降低或消除異常數(shù)據(jù)的影響。而在有些應(yīng)用領(lǐng)域識(shí)別異常數(shù)據(jù)是許多工作的基礎(chǔ)和前提，異常數(shù)據(jù)會(huì)帶給我們新的視角。 如在欺詐檢測(cè)中，異常數(shù)據(jù)可能意味欺詐行為的發(fā)生，在入侵檢測(cè)中異常數(shù)據(jù)可能意味入侵行為的發(fā)生。,異常檢測(cè)的應(yīng)用領(lǐng)域,電信、保險(xiǎn)、銀行中的欺詐檢測(cè)與風(fēng)險(xiǎn)分析 發(fā)現(xiàn)電子商務(wù)中的犯罪行為災(zāi)害氣象預(yù)報(bào)稅務(wù)局分析不同團(tuán)體交所得稅的記錄，發(fā)現(xiàn)異常模型和趨勢(shì) 海關(guān)、民航等安檢部門(mén)推斷哪些人可能有嫌疑 海關(guān)報(bào)關(guān)中

4、的價(jià)格隱瞞營(yíng)銷(xiāo)定制：分析花費(fèi)較小和較高顧客的消費(fèi)行為醫(yī)學(xué)研究中發(fā)現(xiàn)醫(yī)療方案或藥品所產(chǎn)生的異常反應(yīng)計(jì)算機(jī)中的入侵檢測(cè)運(yùn)動(dòng)員的成績(jī)分析應(yīng)用異常檢測(cè)到文本編輯器，可有效減少文字輸入的錯(cuò)誤 ……,什么是異常挖掘？,異常挖掘可以描述為：給定N個(gè)數(shù)據(jù)對(duì)象和所期望的異常數(shù)據(jù)個(gè)數(shù)，發(fā)現(xiàn)明顯不同、意外，或與其它數(shù)據(jù)不一致的前k個(gè)對(duì)象。 異常挖掘問(wèn)題由兩個(gè)子問(wèn)題構(gòu)成： (1)如何度量異常； (2)如何有效發(fā)現(xiàn)異常。,為什么會(huì)出現(xiàn)異常數(shù)據(jù)？

5、,測(cè)量、輸入錯(cuò)誤或系統(tǒng)運(yùn)行錯(cuò)誤所致數(shù)據(jù)內(nèi)在特性所決定客體的異常行為所致由于異常產(chǎn)生的機(jī)制是不確定的，異常挖掘算法檢測(cè)出的“異常數(shù)據(jù)”是否真正對(duì)應(yīng)實(shí)際的異常行為，不是由異常挖掘算法來(lái)說(shuō)明、解釋的，只能由領(lǐng)域?qū)＜襾?lái)解釋?zhuān)惓Ｍ诰蛩惴ㄖ荒転橛脩?hù)提供可疑的數(shù)據(jù)，以便用戶(hù)引起特別的注意并最后確定是否真正的異常。對(duì)于異常數(shù)據(jù)的處理方式也取決于應(yīng)用，并由領(lǐng)域?qū)＜覜Q策。,異常數(shù)據(jù)實(shí)例,一個(gè)人的年齡為-999就可能是由于程序處理缺省數(shù)據(jù)設(shè)置默認(rèn)值

6、所造成的 ；一個(gè)公司的高層管理人員的工資明顯高于普通員工的工資可能成為異常數(shù)據(jù)但卻是合理的數(shù)據(jù)(如平安保險(xiǎn)公司2007年 5位高管稅后收入超過(guò)了1000萬(wàn)元)； 一部住宅電話的話費(fèi)由每月200元以?xún)?nèi)增加到數(shù)千元可能就因?yàn)楸槐I打或其它特殊原因所致； 一張信用卡出現(xiàn)明顯的高額消費(fèi)也許是因?yàn)槭潜I用的卡。,,異常數(shù)據(jù)與眾不同但具有相對(duì)性： 高與矮，瘋子與常人。類(lèi)似術(shù)語(yǔ)： Outlier mining，Exception m

7、ining:異常挖掘、離群挖掘、例外挖掘和稀有事件挖掘 。,11,內(nèi)容提綱,異常挖掘及其應(yīng)用異常檢測(cè)面臨的主要問(wèn)題異常數(shù)據(jù)挖掘方法簡(jiǎn)介異常檢測(cè)的應(yīng)用案例參考文獻(xiàn),Main Problems 主要問(wèn)題,典型正常區(qū)域的定義不易正常對(duì)象和離群點(diǎn)之間的界線不明確離群點(diǎn)的確切概念隨應(yīng)用領(lǐng)域而異訓(xùn)練 / 驗(yàn)證已標(biāo)記數(shù)據(jù)的可用性數(shù)據(jù)可能包含噪聲惡意對(duì)手的存在，反檢測(cè)正常行為不斷演變,12,13,內(nèi)容提綱,異常挖掘及其應(yīng)用異常檢測(cè)

8、面臨的主要問(wèn)題異常數(shù)據(jù)挖掘方法簡(jiǎn)介異常檢測(cè)的應(yīng)用案例參考文獻(xiàn),14,Anomaly Detection Schemes 異常檢測(cè)方法,一般步驟構(gòu)建“正常”行為的資料集資料集可以是針對(duì)數(shù)據(jù)整體的圖案或者匯總統(tǒng)計(jì)通過(guò)使用“正?！辟Y料集檢測(cè)異常行為異常行為是特征與“正常”資料有顯著差別的觀察對(duì)象異常檢測(cè)方法的類(lèi)型分類(lèi)和聚類(lèi)基于統(tǒng)計(jì)的方法基于距離和基于密度的方法基于圖形的方法,Anomaly Detection Sche

9、mes異常檢測(cè)方法,15,主要思想基于已標(biāo)記的訓(xùn)練數(shù)據(jù)，對(duì)正常事件(和(極少)異常事件)構(gòu)建一個(gè)分類(lèi)模型，以此對(duì)每一個(gè)新的未知事件進(jìn)行分類(lèi)分類(lèi)模型必須能夠處理傾斜(不均衡)的類(lèi)分布分類(lèi)監(jiān)督分類(lèi)技術(shù) 需要了解正常類(lèi)和異常類(lèi)建立分類(lèi)，以區(qū)分正常事件和已知的異常事件半監(jiān)督分類(lèi)技術(shù) 只需要了解正常類(lèi)使用改進(jìn)的分類(lèi)模型學(xué)習(xí)正常行為，然后將檢測(cè)到的偏離正常行為的對(duì)象作為異常行為,Ⅰ. Classification-Based Te

10、chniques分類(lèi),16,Ⅰ. Classification-Based Techniques分類(lèi),優(yōu)點(diǎn)監(jiān)督分類(lèi)技術(shù) 模型很容易理解在多種已知異常對(duì)象的檢測(cè)中具有高精度半監(jiān)督分類(lèi)技術(shù) 模型很容易理解正常行為可以被準(zhǔn)確學(xué)習(xí)缺點(diǎn)監(jiān)督分類(lèi)技術(shù) 需要正常類(lèi)的標(biāo)記和異常類(lèi)的標(biāo)記不能檢測(cè)未知的和新興的異常對(duì)象半監(jiān)督分類(lèi)技術(shù) 需要正常類(lèi)的標(biāo)記可能存在高誤報(bào)率：先前未知(但合法)的數(shù)據(jù)記錄可能被認(rèn)為是異常的,17,Ⅱ. Cl

11、ustering-Based Techniques 聚類(lèi),關(guān)鍵假設(shè)正常數(shù)據(jù)記錄屬于大型的、密集的集群，而異常數(shù)據(jù)記錄不屬于任何集群或者形成極小的集群按照標(biāo)簽分類(lèi)半監(jiān)督： 聚集正常數(shù)據(jù)，以創(chuàng)建正常行為模式。如果一個(gè)新實(shí)例不屬于或者不靠近任何集群，那么就是異常無(wú)監(jiān)督： 在聚類(lèi)過(guò)程所需步驟之后，需要進(jìn)行后處理來(lái)決定集群的大小，集群間的距離用來(lái)判別數(shù)據(jù)點(diǎn)是否異常應(yīng)用基于聚類(lèi)的方法進(jìn)行異常檢測(cè)不適合任何集群的數(shù)據(jù)記錄(集群殘差)

12、小集群低密度集群或局部異常(遠(yuǎn)離屬于同一聚類(lèi)的其他點(diǎn)),18,19,基本思想將數(shù)據(jù)聚類(lèi)劃分為不同密度的簇選擇小簇中的點(diǎn)作為候選離群點(diǎn)計(jì)算非候選點(diǎn)形成的簇和候選點(diǎn)間的距離如果候選點(diǎn)距離非候選點(diǎn)形成的簇較遠(yuǎn)，那么他們是離群點(diǎn),Ⅱ. Clustering-Based Techniques 聚類(lèi),優(yōu)點(diǎn)不需要監(jiān)督易適應(yīng)在線/增量模式，適用于時(shí)空數(shù)據(jù)的異常檢測(cè)缺點(diǎn)代價(jià)極大使用索引結(jié)構(gòu)(k-d樹(shù)，R*樹(shù))可能能夠減輕該問(wèn)題如果

13、正常點(diǎn)不能創(chuàng)建任何簇，那么該方法可能會(huì)失敗在高維空間中，數(shù)據(jù)是稀疏的，任意兩個(gè)數(shù)據(jù)記錄間的距離可能會(huì)非常相似聚類(lèi)算法可能不會(huì)得到有意義的簇,Ⅱ. Clustering-Based Techniques 聚類(lèi),20,Ⅲ.NN-Based Techniques 最近鄰方法,關(guān)鍵假設(shè)正常點(diǎn)有近鄰，而離群點(diǎn)遠(yuǎn)離其他節(jié)點(diǎn)一般為二步法計(jì)算每個(gè)數(shù)據(jù)記錄和其鄰居間的關(guān)系分析鄰居關(guān)系，以確定該數(shù)據(jù)記錄異常與否分類(lèi)基于距離的方法離群點(diǎn)是遠(yuǎn)

14、離其他節(jié)點(diǎn)的數(shù)據(jù)點(diǎn)基于密度的方法離群點(diǎn)是低密度區(qū)域的數(shù)據(jù)點(diǎn),21,優(yōu)點(diǎn)可以應(yīng)用于無(wú)監(jiān)督或半監(jiān)督環(huán)境中(對(duì)數(shù)據(jù)分布不作出任何假設(shè)) 缺點(diǎn)如果正常點(diǎn)沒(méi)有足夠數(shù)量的鄰居，該方法可能會(huì)失敗代價(jià)極大在高維空間中，數(shù)據(jù)是稀疏的，相似度的概念不能起到很大作用兩個(gè)數(shù)據(jù)記錄間的距離會(huì)由于稀疏而變得十分相似，以至于每個(gè)數(shù)據(jù)記錄都可能被視為潛在的離群點(diǎn),Ⅲ.NN-Based Techniques 最近鄰方法,22,Ⅲ.NN-Based Te

15、chniques 最近鄰方法,基于距離的方法對(duì)于數(shù)據(jù)集中的點(diǎn)O，如果數(shù)據(jù)集中至少有p(百分比)的節(jié)點(diǎn)到點(diǎn)O的距離超過(guò)d，那么就認(rèn)為O是數(shù)據(jù)集中的離群點(diǎn)，記為DB(p, d) *基于密度的方法計(jì)算特定區(qū)域的局部密度，將低密度區(qū)域的實(shí)例報(bào)為潛在離群點(diǎn)方法局部離群因子(Local Outlier Factor, LOF)連接離群因子(Connectivity Outlier Factor, COF?）多粒度偏差因子(Multi

16、-Granularity Deviation Factor, MDEF),*Knorr, Ng,Algorithms for Mining Distance-Based Outliers in Large Datasets, VLDB98,23,(1) 基于距離的NN方法,基于距離的方法有兩種不同的策略第一種策略是采用給定鄰域半徑，依據(jù)點(diǎn)的鄰域中包含的對(duì)象多少來(lái)判定異常；如果一個(gè)點(diǎn)的鄰域內(nèi)包含的對(duì)象少于整個(gè)數(shù)據(jù)集的一定 比例則標(biāo)識(shí)

17、它為異常，也就是將沒(méi)有足夠鄰居的對(duì)象看成是基于距離的異常。利用k最近鄰距離的大小來(lái)判定異常 。使用k-最近鄰的距離度量一個(gè)對(duì)象是否遠(yuǎn)離大部分點(diǎn)，一個(gè)對(duì)象的異常程度由到它的k-最近鄰的距離給定 。這種方法對(duì)k的取值比較敏感。如果k太小(例如1)，則少量的鄰近異常點(diǎn)可能導(dǎo)致較低的異常程度。如果k太大，則點(diǎn)數(shù)少于k的簇中所有的對(duì)象可能都成了異常點(diǎn)。,到k-最近鄰的距離的計(jì)算,k-最近鄰的距離：一個(gè)對(duì)象的異常點(diǎn)得分由到它的k-最近鄰的距

18、離給定。異常點(diǎn)得分的最低值為0，最高值是距離函數(shù)的可能最大值----如無(wú)窮大,基于距離的異常點(diǎn)檢測(cè) 例1,,請(qǐng)問(wèn)該二維數(shù)據(jù)集中，當(dāng)k=5時(shí)，哪個(gè)點(diǎn)具有最高的異常點(diǎn)得分？,基于距離的異常點(diǎn)檢測(cè) 例2,,請(qǐng)問(wèn)該二維數(shù)據(jù)集中，當(dāng)k=5時(shí)，哪個(gè)點(diǎn)具有最高的異常點(diǎn)得分？,基于距離的異常檢測(cè)的優(yōu)缺點(diǎn),優(yōu)點(diǎn)：基于距離的異常點(diǎn)檢測(cè)方案簡(jiǎn)單 缺點(diǎn)：時(shí)間復(fù)雜度O(m2)，不適用于大數(shù)據(jù)集不能處理不同密度區(qū)域的數(shù)據(jù)集，因?yàn)樗褂萌珠撝?，?/p>

19、能考慮這種密度的變化,不能處理不同密度區(qū)域的數(shù)據(jù)集,當(dāng)k=5時(shí)，哪個(gè)點(diǎn)具有最高的異常點(diǎn)得分,B的異常點(diǎn)得分和D的異常點(diǎn)得分哪個(gè)低？,例：,局部離群因子法(Local Outlier Factor, LOF)Example:,(2) Local Outlier Factor(LOF)基于密度的NN方法,* - Breunig, et al, LOF: Identifying Density-Based Local Outliers, K

20、DD 2000.,30,在NN方法中，p2 并沒(méi)有被認(rèn)為是離群點(diǎn), 而在LOF 方法中發(fā)現(xiàn) p1 和 p2 都是離群點(diǎn)NN方法可能認(rèn)為 p3 是離群點(diǎn), 但 LOF 方法不會(huì),31,(2) Local Outlier Factor(LOF)基于密度的NN方法,對(duì)每一個(gè)數(shù)據(jù)點(diǎn)q，計(jì)算到第k個(gè)近鄰的距離(k-distance)對(duì)任意兩個(gè)數(shù)據(jù)，計(jì)算可達(dá)距離(reach-dist) reach-dist(p, o) = max{k-d

21、istance(o), d(p,o)},32,(2) Local Outlier Factor(LOF)基于密度的NN方法,計(jì)算局部可達(dá)密度(local reachability density, lrd)基于數(shù)據(jù)p的MinPts-NN的平均可達(dá)距離的逆 lrd(p) = 計(jì)算 LOF(p)作為p的k近鄰平均局部可達(dá)密度比率數(shù)據(jù)記錄p的局部可達(dá)密度為 LOF(p)

22、=,* - Breunig, et al, LOF: Identifying Density-Based Local Outliers, KDD 2000.,(2) Local Outlier Factor(LOF)基于密度的NN方法,* - Breunig, et al, LOF: Identifying Density-Based Local Outliers, KDD 2000.,對(duì)象p的離群因子不為空，則稱(chēng)p為離群點(diǎn)平均局部可

23、達(dá)密度比率 p 的MinPts-NN鄰居很容易看出： p的LOF 值越高，則p的局部可達(dá)密度越低， p 的MinPts-NN的局部可達(dá)密度越高.,33,內(nèi)容提綱,異常挖掘及其應(yīng)用異常檢測(cè)面臨的主要問(wèn)題異常數(shù)據(jù)挖掘方法簡(jiǎn)介異常檢測(cè)的應(yīng)用案例參考文獻(xiàn),應(yīng)用案例 1 Intrusion Detection 入侵檢測(cè),35,Case Study:Data Mining in Intrusion Detection,

24、隨著互聯(lián)網(wǎng)的不斷發(fā)展，越來(lái)越多的組織易受到網(wǎng)絡(luò)攻擊網(wǎng)絡(luò)攻擊的復(fù)雜性和嚴(yán)重性都在增長(zhǎng)安全機(jī)制總有不可避免的漏洞防火墻不足以確保計(jì)算機(jī)網(wǎng)絡(luò)的安全性?xún)?nèi)線攻擊,36,1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003,計(jì)算機(jī)應(yīng)急反應(yīng)協(xié)調(diào)中心的事故報(bào)告,攻擊復(fù)雜性 vs. 入侵技術(shù)知識(shí)源：www.cert.org/

25、archive/ppt/cyberterror.ppt,Sapphire/Slammer Worm攻擊30分鐘后的地理分布源：www.caida.org,What are Intrusions?入侵,37,掃描活動(dòng),攻擊者,計(jì)算機(jī)網(wǎng)絡(luò),易損機(jī)器,,,入侵活動(dòng)試圖繞過(guò)計(jì)算機(jī)系統(tǒng)的安全機(jī)制通常的行為有攻擊者從因特網(wǎng)訪問(wèn)系統(tǒng)內(nèi)線攻擊已授權(quán)用戶(hù)試圖獲取或誤用未被授權(quán)的權(quán)限典型的入侵場(chǎng)景,受損機(jī)器,IDS - Analysis Str

26、ategy入侵檢測(cè)系統(tǒng)策略分析,誤用檢測(cè)(Misuse detection) 是基于與專(zhuān)家提供的已知攻擊相關(guān)的外部知識(shí)模式現(xiàn)有的方法：(簽字)模式匹配，專(zhuān)家系統(tǒng)，狀態(tài)轉(zhuǎn)換分析，數(shù)據(jù)挖掘主要的限制：不能檢測(cè)異常的或者意料之外的攻擊簽名數(shù)據(jù)庫(kù)要為每一個(gè)新發(fā)現(xiàn)的攻擊進(jìn)行修改異常檢測(cè)(Anomaly detection) 是基于代表用戶(hù)、主機(jī)或網(wǎng)絡(luò)的正常行為的配置文件，檢測(cè)這個(gè)文件中有顯著偏差的攻擊主要好處：潛在地對(duì)不可預(yù)見(jiàn)攻擊的識(shí)

27、別能力主要限制因素：可能有較高的誤報(bào)率，因?yàn)闄z測(cè)偏差不一定代表真實(shí)攻擊主要方法：統(tǒng)計(jì)方法，專(zhuān)家系統(tǒng)，聚類(lèi)，神經(jīng)網(wǎng)絡(luò)，支持向量機(jī)，異常檢測(cè)計(jì)劃,38,Intrusion Detection入侵檢測(cè),www.snort.org,39,入侵檢測(cè)系統(tǒng) 將可能執(zhí)行入侵檢測(cè)的軟硬件結(jié)合當(dāng)可能有入侵發(fā)生時(shí)拉響警報(bào) 傳統(tǒng)入侵檢測(cè)系統(tǒng)(IDS)工具(例如:SNORT)是基于已知簽名攻擊SNORT 規(guī)則實(shí)例 (MS-SQL “Slammer”

28、worm)?any -> udp port 1434 (content:"|81 F1 03 01 04 9B 81 F1 01|";content:"sock"; content:"send")限制當(dāng)出現(xiàn)新的入侵類(lèi)型時(shí)，簽名數(shù)據(jù)庫(kù)必須手動(dòng)修改無(wú)法檢測(cè)新興的網(wǎng)絡(luò)威脅部署新創(chuàng)建的簽名會(huì)造成整個(gè)計(jì)算機(jī)系統(tǒng)的重大延遲數(shù)據(jù)挖掘可以緩解這些限制,Data Mining

29、 for Intrusion Detection 入侵檢測(cè)數(shù)據(jù)挖掘,對(duì)基于數(shù)據(jù)挖掘的入侵檢測(cè)興趣日增攻擊造成簽名難以建立攻擊具有隱蔽性不可預(yù)見(jiàn)的/未知的/新出現(xiàn)的攻擊分布式/協(xié)調(diào)的攻擊針對(duì)入侵檢測(cè)的數(shù)據(jù)挖掘方法誤用檢測(cè)(Misuse detection) 基于已標(biāo)記的數(shù)據(jù)集(數(shù)據(jù)標(biāo)記為”正?！被颉碑惓！?建立預(yù)測(cè)模型，判別已知入侵在檢測(cè)多種已知攻擊中具有高精度不能檢測(cè)未知的和新興的攻擊異常檢測(cè)(Anomaly dete

30、ction) 從”正?！毙袨闄z測(cè)異常攻擊作為偏差潛在高誤報(bào)率：以前不可見(jiàn)(但合法)系統(tǒng)行為也可能被認(rèn)為是異常網(wǎng)絡(luò)流量綜述(Summarization of network traffic),40,,Data Mining for Intrusion Detection,誤用檢測(cè)：建立預(yù)測(cè)模型,41,絕對(duì)的,當(dāng)時(shí)的,持續(xù)的,分類(lèi),,訓(xùn)練集,,學(xué)習(xí)分類(lèi)器,,,,,,絕對(duì)的,異常檢測(cè),,發(fā)現(xiàn)的規(guī)則:{Src IP = 206.163

31、.37.95, Dest Port = 139, Bytes ? [150, 200]} --> {ATTACK},使用關(guān)聯(lián)規(guī)則對(duì)攻擊進(jìn)行綜述,,,,,,Anomaly Detection on Real Network Data真實(shí)網(wǎng)絡(luò)數(shù)據(jù)的入侵檢測(cè),在明尼蘇達(dá)州和美國(guó)陸軍研究實(shí)驗(yàn)室，使用異常檢測(cè)來(lái)檢測(cè)各種侵?jǐn)_活動(dòng)或可以活動(dòng)其中許多入侵不能被廣泛應(yīng)用的異常檢測(cè)工具檢測(cè)到，如SNORT異常/攻擊被MINDS發(fā)現(xiàn)掃描活

32、動(dòng)不規(guī)范的行為違反策略蠕蟲(chóng),42,MINDS – Minnesota Intrusion Detection System明尼蘇達(dá)異常檢測(cè)系統(tǒng),MINDS,,網(wǎng)絡(luò),,數(shù)據(jù)捕獲裝置,,,異常檢測(cè),,……,獲取異常,,,Humananalyst,,,檢測(cè) 新的攻擊,Summary and characterizationof attacks,,,,,已知攻擊檢測(cè),,Detected known attacks,,,標(biāo)記,,

33、特征抽取,,相關(guān)模式分析,MINDSAT,,,過(guò)濾,Net flow toolstcpdump,三組特征TCP 連接個(gè)體的基本特征源&目的地IP Features 1 & 2源&目的端口 Features 3 & 4協(xié)議 Feature 5持續(xù)時(shí)間 Feature 6每包字節(jié) Feature 7字節(jié)數(shù) Feature 8基于時(shí)間的特征網(wǎng)絡(luò)中對(duì)于相同的

34、源(目的地) IP地址, 最后T秒鐘唯一目的地(源) IP地址數(shù)目– Features 9 (13)最后T秒鐘從源 (目的地) IP 到同一個(gè)目的地(源) 端口的連接數(shù)目– Features 11 (15)基于連接的特征網(wǎng)絡(luò)中對(duì)于相同的源(目的地) IP地址,最后N個(gè)連接中唯一目的地(源) IP地址數(shù)目- Features 10 (14)最后N個(gè)連接中從源 (目的地) IP 到同一個(gè)目的地(源) 端口的連接數(shù)目- Feature

35、s 12 (16),43,Feature Extraction 特征抽取,Typical Anomaly Detection Output 典型異常檢測(cè)輸出,“slammer” 蠕蟲(chóng)病毒爆發(fā)48小時(shí)后,44,,連接到“half-life”游戲服務(wù)器 的機(jī)器所對(duì)應(yīng)的連接“slammer” 蠕蟲(chóng)病毒對(duì)應(yīng)的異常連接 進(jìn)行ping掃描異常連接,Detection of Anomalies on Real Network Data真實(shí)網(wǎng)

36、絡(luò)數(shù)據(jù)中的異常檢測(cè),MINDS檢測(cè)出的異常/攻擊，包括掃描活動(dòng)、蠕蟲(chóng)病毒以及像違反規(guī)則行為、內(nèi)部攻擊行為等不正常的行為。這些攻擊中的大部分均可被MINDS檢測(cè)出來(lái)，并被放在當(dāng)前計(jì)算機(jī)應(yīng)急反應(yīng)協(xié)調(diào)中心( CERT/CC )的咨詢(xún)列表中。下面是MINDS檢測(cè)出的入侵行為的一些說(shuō)明例子。ScansAugust 13, 2004, Detected scanning for Microsoft DS service on port 445

37、/TCP (Ranked#1)Reported by CERT as recent DoS attacks that needs further analysis (CERT August 9, 2004)Undetected by SNORT since the scanning was non-sequential (very slow). Rule added to SNORT in September 2004August

38、 13, 2004, Detected scanning for Oracle server (Ranked #2), Reported by CERT, June 13, 2004Undetected by SNORT because the scanning was hidden within another Web scanningOctober 10, 2005, Detected a distributed windows

39、 networking scan from multiple source locations (Ranked #1)Policy ViolationsAugust 8, 2005, Identified machine running Microsoft PPTP VPN server on non-standard ports (Ranked #1)Undetected by SNORT since the collected

40、 GRE traffic was part of the normal traffic August 10 2005 & October 30, 2005, Identified compromised machines running FTP servers on non-standard ports, which is a policy violation (Ranked #1)Example of anomalous

41、behavior following a successful Trojan horse attackFebruary 6, 2006, The IP address 128.101.X.0 (not a real computer, but a network itself) has been targeted with IP Protocol 0 traffic from Korea (61.84.X.97) (bad since

42、 IP Protocol 0 is not legitimate)February 6, 2006, Detected a computer on the network apparently communicating with a computer in California over a VPN or on IPv6WormsOctober 10, 2005, Detected several instances of sl

43、apper worm that were not identified by SNORT since they were variations of existing worm codeFebruary 6, 2006, Detected unsolicited ICMP ECHOREPLY messages to a computer previously infected with Stacheldract worm (a DDo

44、s agent),45,46,應(yīng)用案例 2 Fraud Detection 欺騙檢測(cè),Online Auctions: Growing Froud 欺詐日增,#1 網(wǎng)上犯罪2006年，投訴超過(guò)40,000件平均損失> $602.50,47,Source: http://www.ic3.gov/media/annualreport/2006_IC3Report.pdf,48,,Potential Buyer A,,$$

45、$,,Seller,$,$$,Buyer,A Transaction,What if something goes BAD?,未交付欺詐,Online Auctions: How They Work,Problem Description 問(wèn)題描述,通過(guò)觀察By observing拍賣(mài)者的行為模式與其他用戶(hù)相互交流一些關(guān)于已暴露的欺詐者的知識(shí)預(yù)測(cè)在未來(lái)，誰(shuí)可能犯欺詐接下來(lái)是更具體的說(shuō)明……,49,Modeling Fra

46、udulent Behavior 欺詐行為建模,捕捉用戶(hù)之間的關(guān)系，而不是個(gè)人行為模式關(guān)系圖模型節(jié)點(diǎn)——每個(gè)用戶(hù)邊——兩個(gè)用戶(hù)成交潛在希望：全球性的圖屬性更難操縱,50,Modeling Fraudulent Behavior (contd.),欺詐者的行為如何反應(yīng)在圖中？與其他欺詐者間密切互動(dòng)愚弄基于信譽(yù)的系統(tǒng)這是一種極好的檢測(cè)方法，可以很容易地發(fā)現(xiàn)詐騙群體不太符合實(shí)際一個(gè)真實(shí)的eBay數(shù)據(jù)集的實(shí)驗(yàn)表明，他們很

47、少拉幫結(jié)派,51,0,9,24,53,0,11,21,49,信譽(yù),Modeling Fraudulent Behavior (contd.),那么，詐騙者是如何操作的?,52,,,,,,,,,,,,,,,,,,,= 詐騙者,= 同謀,= 誠(chéng)實(shí)者,二部圖核心,,,Modeling Fraudulent Behavior (contd.),3個(gè)角色誠(chéng)實(shí)者 Honest普通人，如：你、我詐騙者 Fraudsters那些真正犯詐騙罪的人

48、同謀 Accomplices往日的行為像誠(chéng)實(shí)的用戶(hù)通過(guò)低成本的交易積累反饋的人偷偷提高信譽(yù)的詐騙者 (例如：偶爾購(gòu)買(mǎi)貴重物品的人),53,Modeling Fraudulent Behavior (contd.),為什么尋找二部圖核心，而不是小集體？詐騙者之間不會(huì)之間聯(lián)系一旦一次詐騙交易被曝光，相關(guān)的賬目會(huì)被eBay掃描，并立即作廢“架構(gòu)重用”一次欺詐后同謀不比丟棄長(zhǎng)時(shí)間積累信譽(yù)分?jǐn)?shù),54,Problem Desc

49、ription (Concrete),已知在線拍賣(mài)用戶(hù)圖關(guān)于一些已經(jīng)暴露的詐騙者的知識(shí)檢測(cè)二部圖核心 Bipartite cores,55,Solution 解決方案,大量的方法可以用來(lái)檢測(cè)二部圖核心， 要使用哪一個(gè)？這是一個(gè)軍備競(jìng)賽詐騙者勢(shì)必會(huì)形成新的模式，試圖突破你的系統(tǒng)適應(yīng)他們千變?nèi)f化的行為對(duì)詐騙者的行為建模，而不是生成圖形模式,56,N O N E !,The NetProbe Algorithm

50、,NetProbe對(duì)拍賣(mài)圖建?！R爾可夫隨機(jī)域(Markov Random Field)用預(yù)期詐騙者的行為對(duì)模型進(jìn)行訓(xùn)練通過(guò) “置信傳播”來(lái)推斷節(jié)點(diǎn)最可能的標(biāo)簽 它不依賴(lài)于任何特定的圖形模型，甚至是詐騙者與其他人相互交流的模式,57,Markov Random Fields 馬爾可夫隨機(jī)域,圖形模型推理問(wèn)題節(jié)點(diǎn)可能的狀態(tài)屬于固定集合兩個(gè)不同狀態(tài)的節(jié)點(diǎn)間的連接似然性狀態(tài)集 = { F, A, H }連接似然性F 非常

51、可能連接到 AF 不大可能連接到 F,58,Markov Random Fields (contd.),訓(xùn)練模型連接似然性通過(guò)傳播矩陣表達(dá),59,,,,,[i,j] = 已知節(jié)點(diǎn)在狀態(tài) i 、有一個(gè)在狀態(tài) j 的鄰居節(jié)點(diǎn)，則它們之間的似然性,F, F = ? ~ 0,F, A = 1 - 2? ~ 1,Markov Random Fields (contd.),重申馬爾可夫隨機(jī)域模型下的問(wèn)題已知傳播矩陣一些節(jié)點(diǎn)的初始狀態(tài)

52、推斷其余節(jié)點(diǎn)最可能的狀態(tài),60,Belief Propagation 置信傳播,通過(guò)迭代消息傳播計(jì)劃來(lái)解決推理問(wèn)題用有限的理論擔(dān)保來(lái)進(jìn)行啟發(fā)式計(jì)劃在很多領(lǐng)域的問(wèn)題中實(shí)踐都得到了很好的結(jié)果(尤其是物理方面! ),61,Belief Propagation: Algorithm 算法,消息mij 從節(jié)點(diǎn) i傳播到節(jié)點(diǎn) j針對(duì)節(jié)點(diǎn) i 考慮節(jié)點(diǎn) j 在哪個(gè)狀態(tài)？每次迭代每個(gè)節(jié)點(diǎn)與它所接收到的消息相結(jié)合，計(jì)算它自己的置信度每

53、個(gè)節(jié)點(diǎn)基于自己最新計(jì)算出的置信度，將消息傳遞給自己的鄰居繼續(xù)傳遞，直到置信度收斂,62,Belief Propagation: Details 細(xì)節(jié),63,,,,,,,,Message computation 消息計(jì)算,Belief computation 置信度計(jì)算,,使用傳播矩陣進(jìn)行變換,,,將鄰居處得到的消息結(jié)合在一起,,Belief Propagation: Example 舉例,64,,,A,C,B,E,D,The Net

54、Probe Algorithm,已知的詐騙者的初始狀態(tài)為F初始化其它節(jié)點(diǎn)，無(wú)刻意偏向每次迭代對(duì)于每個(gè)節(jié)點(diǎn)通過(guò)結(jié)合前次達(dá)到收到的消息，計(jì)算自身置信度通過(guò)傳播矩陣，將自身置信度轉(zhuǎn)化為消息傳遞給每一個(gè)鄰居繼續(xù)迭代，直到收斂用最可能的狀態(tài)對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行標(biāo)記,65,Evaluation: Real Datasets 評(píng)價(jià)：真實(shí)數(shù)據(jù),來(lái)自eBay的真實(shí)數(shù)據(jù)66,130 用戶(hù)和795,320 交易對(duì)數(shù)據(jù)形象為期2個(gè)月的爬行多層并

55、行履帶式架構(gòu)Java + MySQL一直進(jìn)行，直到我們不能在eBay發(fā)現(xiàn)黑名單為止?,66,Evaluation: eBay Dataset,評(píng)價(jià)度量：精密/二次行動(dòng)?完全正確的結(jié)果并不知道詐騙者沒(méi)有完全暴露未來(lái)進(jìn)行詐騙行為的可能性不能確定eBay 不公開(kāi)提供超過(guò)6個(gè)月的信息很無(wú)奈，我們不得不做出一個(gè)主觀評(píng)價(jià),67,Evaluation: eBay Dataset (contd.),68,,,,通過(guò)NetProbe方法

56、檢測(cè)二部圖核心,Practical Considerations 實(shí)際考慮,如果圖形發(fā)生變化，會(huì)怎樣?新的用戶(hù)出現(xiàn)，新的交易發(fā)生如果小范圍圖形發(fā)生變化，則從新開(kāi)始計(jì)算置信度拓?fù)浣Y(jié)構(gòu)上的改變帶來(lái)的影響本質(zhì)上應(yīng)當(dāng)局部化,69,Practical Considerations (contd.),增量式的NetProbe新節(jié)點(diǎn)或邊的 k 近鄰的傳播置信度初步試驗(yàn)表明：在精確度近乎零損失的情況下，執(zhí)行時(shí)間降低80% 進(jìn)一步切實(shí)改

57、進(jìn)并行爬行的基礎(chǔ)架構(gòu)用戶(hù)界面顯示可疑的圖模式,70,System Overview 系統(tǒng)綜述,71,內(nèi)容提綱,異常挖掘及其應(yīng)用異常檢測(cè)面臨的主要問(wèn)題異常數(shù)據(jù)挖掘方法簡(jiǎn)介異常檢測(cè)的應(yīng)用案例參考文獻(xiàn),72,參考文獻(xiàn),[P4] J. Naisbitt, Megatrends: Ten New Directions Transforming Our Lives. New York: Warner Books, 1982.[P7]

58、 Xiuyao Song, Mingxi Wu, Christopher Jermaine, Sanjay Ranka, Conditional Anomaly Detection, IEEE Transactions on Data and Knowledge Engineering, 2006. [P21.22] Knorr, Ng,Algorithms for Mining Distance-Based Outliers in

59、 Large Datasets, VLDB98.[P22] S. Ramaswamy, R. Rastogi, S. Kyuseok: Efficient Algorithms for Mining Outliers from Large Data Sets, ACM SIGMOD Conf. On Management of Data, 2000.[P23.25.26] Breunig, et al, LOF: Identif

60、ying Density-Based Local Outliers, KDD 2000.,73,利用SPSS軟件進(jìn)行異常檢測(cè),異常檢測(cè)建模,方法具體如下所示：在回歸模型診斷里面，一般稱(chēng)預(yù)測(cè)值與實(shí)際值的偏差為"殘差",殘差有幾種表示方法:標(biāo)準(zhǔn)化殘差, 學(xué)生化殘差等等，按照需要取一種殘差，再按照某種標(biāo)準(zhǔn)取一個(gè)閥值來(lái)限定異常點(diǎn)，只要那個(gè)點(diǎn)的殘差大于閥值，就可以認(rèn)為它是異常點(diǎn)。,75,SPSS在異常檢測(cè)中應(yīng)用,Step01

61、：選定對(duì)話框打開(kāi)SPSS軟件，選擇菜單欄中的【File(文件)】→【Open(打開(kāi))】→【Data(數(shù)據(jù))】命令，彈出【Open Data(打開(kāi)數(shù)據(jù))】對(duì)話框。Step02：選定打開(kāi)文件類(lèi)型在數(shù)據(jù)表格中填寫(xiě)如下圖所示的數(shù)據(jù)。接著，點(diǎn)擊【File(文件)】 →【Save (保存)】 。填寫(xiě)保存數(shù)據(jù)的位置，完成數(shù)據(jù)的保存操作。,76,SPSS在異常檢測(cè)中應(yīng)用,77,SPSS在異常檢測(cè)中應(yīng)用,Step03：打開(kāi)對(duì)話框選擇菜單欄中的【A

62、nalyze(分析)】→【Regression（回歸）】→ 【Linear（線性）】命令，彈出【Linear Regression（線性回歸）】對(duì)話框，這是線性回歸分析的主操作窗口。,78,SPSS在異常檢測(cè)中應(yīng)用,Step04：選擇因變量在【Linear Regression（線性回歸）】對(duì)話框左側(cè)的候選變量列表框中選擇一個(gè)變量，將其添加至【Dependent（因變量）】列表框 中，即選擇該變量作為多元線性回歸的因變量。Step0

63、5：選擇自變量在【Linear Regression（線性回歸）】對(duì)話框左側(cè)的候選變量列表框中選擇一個(gè)變量，將其添加至【Independent(s)（自 變量）】列表框中，即選擇該變量作為一元線性回歸的自變 量。,79,SPSS在異常檢測(cè)中應(yīng)用,如下圖所示：,80,SPSS在異常檢測(cè)中應(yīng)用,Step06：樣本的篩選從主對(duì)話框的候選變量列表框中選擇一個(gè)變量，將其移至【Selection Variable（選擇變量）】列表框中，這表示要

64、按照這個(gè)變量的標(biāo)準(zhǔn)來(lái)篩選樣本進(jìn)行回歸分析。具體操作可以在Rule窗口中實(shí)現(xiàn)。Step07：選擇個(gè)案標(biāo)簽從候選變量列表框中選擇一個(gè)變量進(jìn)入【Case Labels（個(gè)案診斷）】列表框中，它的取值將作為每條記錄的標(biāo)簽。這表示在指定作圖時(shí)，以 哪個(gè)變量作為各樣本數(shù)據(jù)點(diǎn)的標(biāo)志變量。設(shè)置離群值為3,81,SPSS在異常檢測(cè)中應(yīng)用,如下圖所示：,82,SPSS在異常檢測(cè)中應(yīng)用,Step08：?jiǎn)螕簟綩K】按鈕，結(jié)束操作，SPSS軟件自動(dòng)輸出結(jié)果

65、。,83,由上表可知復(fù)相關(guān)系數(shù)R=0.898，決定系數(shù)R方=0.806，均小于1，由決定系數(shù)看出回歸方程的顯著性不高，接下來(lái)看方差分析表3,SPSS在異常檢測(cè)中應(yīng)用,由表3知F值為8.283較小，說(shuō)明x1、x2、x3整體上對(duì)y的影響不太顯著。,84,SPSS在異常檢測(cè)中應(yīng)用,回歸方程為,85,SPSS在異常檢測(cè)中應(yīng)用,86,對(duì)數(shù)據(jù)用spss進(jìn)行分析得：,從表中可以看出,絕對(duì)值最大的學(xué)生化殘差SRE=2.11566,小于3,因而根據(jù)學(xué)生化