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

1、1,數(shù)據(jù)挖掘與商務(wù)智能Data Mining & Business Intelligence,西安電子科技大學(xué)　軟件學(xué)院主講人：黃健斌,第八章 異常檢測,內(nèi)容提綱,異常挖掘及其應(yīng)用異常檢測面臨的主要問題異常數(shù)據(jù)挖掘方法簡介異常檢測的應(yīng)用案例參考文獻(xiàn),內(nèi)容提綱,異常挖掘及其應(yīng)用異常檢測面臨的主要問題異常數(shù)據(jù)挖掘方法簡介異常檢測的應(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ù)據(jù)是許多工作的基礎(chǔ)和前提，異常數(shù)據(jù)會帶給我們新的視角。 如在欺詐檢測中，異常數(shù)據(jù)可能意味欺詐行為的發(fā)生，在入侵檢測中異常數(shù)據(jù)可能意味入侵行為的發(fā)生。,異常檢測的應(yīng)用領(lǐng)域,電信、保險(xiǎn)、銀行中的欺詐檢測與風(fēng)險(xiǎn)分析 發(fā)現(xiàn)電子商務(wù)中的犯罪行為災(zāi)害氣象預(yù)報(bào)稅務(wù)局分析不同團(tuán)體交所得稅的記錄，發(fā)現(xiàn)異常模型和趨勢 海關(guān)、民航等安檢部門推斷哪些人可能有嫌疑 海關(guān)報(bào)關(guān)中

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

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

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

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

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

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

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

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

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

13、正常點(diǎn)不能創(chuàng)建任何簇，那么該方法可能會失敗在高維空間中，數(shù)據(jù)是稀疏的，任意兩個數(shù)據(jù)記錄間的距離可能會非常相似聚類算法可能不會得到有意義的簇,Ⅱ. Clustering-Based Techniques 聚類,20,Ⅲ.NN-Based Techniques 最近鄰方法,關(guān)鍵假設(shè)正常點(diǎn)有近鄰，而離群點(diǎn)遠(yuǎn)離其他節(jié)點(diǎn)一般為二步法計(jì)算每個數(shù)據(jù)記錄和其鄰居間的關(guān)系分析鄰居關(guān)系，以確定該數(shù)據(jù)記錄異常與否分類基于距離的方法離群點(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)用于無監(jiān)督或半監(jiān)督環(huán)境中(對數(shù)據(jù)分布不作出任何假設(shè)) 缺點(diǎn)如果正常點(diǎn)沒有足夠數(shù)量的鄰居，該方法可能會失敗代價(jià)極大在高維空間中，數(shù)據(jù)是稀疏的，相似度的概念不能起到很大作用兩個數(shù)據(jù)記錄間的距離會由于稀疏而變得十分相似，以至于每個數(shù)據(jù)記錄都可能被視為潛在的離群點(diǎn),Ⅲ.NN-Based Techniques 最近鄰方法,22,Ⅲ.NN-Based Te

15、chniques 最近鄰方法,基于距離的方法對于數(shù)據(jù)集中的點(diǎn)O，如果數(shù)據(jù)集中至少有p(百分比)的節(jié)點(diǎn)到點(diǎn)O的距離超過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)的鄰域中包含的對象多少來判定異常；如果一個點(diǎn)的鄰域內(nèi)包含的對象少于整個數(shù)據(jù)集的一定 比例則標(biāo)識

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

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

19、能考慮這種密度的變化,不能處理不同密度區(qū)域的數(shù)據(jù)集,當(dāng)k=5時，哪個點(diǎn)具有最高的異常點(diǎn)得分,B的異常點(diǎn)得分和D的異常點(diǎn)得分哪個低？,例：,局部離群因子法(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 并沒有被認(rèn)為是離群點(diǎn), 而在LOF 方法中發(fā)現(xiàn) p1 和 p2 都是離群點(diǎn)NN方法可能認(rèn)為 p3 是離群點(diǎn), 但 LOF 方法不會,31,(2) Local Outlier Factor(LOF)基于密度的NN方法,對每一個數(shù)據(jù)點(diǎn)q，計(jì)算到第k個近鄰的距離(k-distance)對任意兩個數(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.,對象p的離群因子不為空，則稱p為離群點(diǎn)平均局部可

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

24、隨著互聯(lián)網(wǎng)的不斷發(fā)展，越來越多的組織易受到網(wǎng)絡(luò)攻擊網(wǎng)絡(luò)攻擊的復(fù)雜性和嚴(yán)重性都在增長安全機(jī)制總有不可避免的漏洞防火墻不足以確保計(jì)算機(jī)網(wǎng)絡(luò)的安全性內(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ù)知識源：www.cert.org/

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

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

27、別能力主要限制因素：可能有較高的誤報(bào)率，因?yàn)闄z測偏差不一定代表真實(shí)攻擊主要方法：統(tǒng)計(jì)方法，專家系統(tǒng)，聚類，神經(jīng)網(wǎng)絡(luò)，支持向量機(jī)，異常檢測計(jì)劃,38,Intrusion Detection入侵檢測,www.snort.org,39,入侵檢測系統(tǒng) 將可能執(zhí)行入侵檢測的軟硬件結(jié)合當(dāng)可能有入侵發(fā)生時拉響警報(bào) 傳統(tǒng)入侵檢測系統(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)新的入侵類型時，簽名數(shù)據(jù)庫必須手動修改無法檢測新興的網(wǎng)絡(luò)威脅部署新創(chuàng)建的簽名會造成整個計(jì)算機(jī)系統(tǒng)的重大延遲數(shù)據(jù)挖掘可以緩解這些限制,Data Mining

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

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

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

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

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

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

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

36、絡(luò)數(shù)據(jù)中的異常檢測,MINDS檢測出的異常/攻擊，包括掃描活動、蠕蟲病毒以及像違反規(guī)則行為、內(nèi)部攻擊行為等不正常的行為。這些攻擊中的大部分均可被MINDS檢測出來，并被放在當(dāng)前計(jì)算機(jī)應(yīng)急反應(yīng)協(xié)調(diào)中心( CERT/CC )的咨詢列表中。下面是MINDS檢測出的入侵行為的一些說明例子。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 欺騙檢測,Online Auctions: Growing Froud 欺詐日增,#1 網(wǎng)上犯罪2006年，投訴超過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 問題描述,通過觀察By observing拍賣者的行為模式與其他用戶相互交流一些關(guān)于已暴露的欺詐者的知識預(yù)測在未來，誰可能犯欺詐接下來是更具體的說明……,49,Modeling Fra

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

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

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

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

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

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

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

53、個節(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)，無刻意偏向每次迭代對于每個節(jié)點(diǎn)通過結(jié)合前次達(dá)到收到的消息，計(jì)算自身置信度通過傳播矩陣，將自身置信度轉(zhuǎn)化為消息傳遞給每一個鄰居繼續(xù)迭代，直到收斂用最可能的狀態(tài)對每個節(jié)點(diǎn)進(jìn)行標(biāo)記,65,Evaluation: Real Datasets 評價(jià)：真實(shí)數(shù)據(jù),來自eBay的真實(shí)數(shù)據(jù)66,130 用戶和795,320 交易對數(shù)據(jù)形象為期2個月的爬行多層并

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

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

57、進(jìn)并行爬行的基礎(chǔ)架構(gòu)用戶界面顯示可疑的圖模式,70,System Overview 系統(tǒng)綜述,71,內(nèi)容提綱,異常挖掘及其應(yīng)用異常檢測面臨的主要問題異常數(shù)據(jù)挖掘方法簡介異常檢測的應(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)行異常檢測,異常檢測建模,方法具體如下所示：在回歸模型診斷里面，一般稱預(yù)測值與實(shí)際值的偏差為"殘差",殘差有幾種表示方法:標(biāo)準(zhǔn)化殘差, 學(xué)生化殘差等等，按照需要取一種殘差，再按照某種標(biāo)準(zhǔn)取一個閥值來限定異常點(diǎn)，只要那個點(diǎn)的殘差大于閥值，就可以認(rèn)為它是異常點(diǎn)。,75,SPSS在異常檢測中應(yīng)用,Step01

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

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

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

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

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