适用于即时网路流量分析的快速模糊关联规则产生方法-电算中心网路组PPT课件

-,1,適用於即時網路流量分析的快速模糊關聯規則產生方法,蘇民揚，戴宏偉，龍京佑銘傳大學資訊工程學系,-,2,摘要,對於網路安全的運用中，許多的網路入侵偵測工具都必須藉由分析網路流量來完成，對於動態新增資料庫(網路流量)資訊而言，所設計的演算法必須快速且準確的分析網路資訊。本文提出了一個快速的模糊關聯規則演算法，適用於分析即時動態的網路流量，能針對大量的網路流量做即時、動態且準確的分析。,-,3,摘要,為了達到即時分析，系統設定3秒鐘統計一筆網路流量的資訊，針對6種特徵，且各特徵分低、中、高，3種程度做挖掘，經過測試，系統處理一筆新進資料平均只需要0.0067秒，可以有效的支援線上即時探勘的需求。系統也可以針對於不同的環境如地點、時間點以及不同的網路行為做特徵選取上的更動。,-,4,背景知識,關聯規則演算法-Apriori模糊關聯規則漸進式模糊關聯規則探勘-Real-Time,-,5,關聯規則演算法-Apriori,在關聯規則演算法中，目前以Apriori演算法為基礎所推導出的各種資料探勘技術為最具代表性的方法之一，其設計為針對靜態的資料做探勘的動作，而從中擷取出對使用者有興趣的相關法則。Apriori演算法中主要包含以下兩個主要的步驟：1、重複的產生候選項目組(candidateitemset)並且搜尋整個資料庫，直到找出所有大型項目組(largeitemset)。2、利用上述所找出的大型項目組進行拆解，並且推倒出所有的關聯法則。,-,6,關聯規則演算法-Apriori,在步驟1之中，候選項目組(candidateitemset)必須大於使用者所設定的最小支持門檻值(minimalsupport)才能成為大項目組(largeitemset)。同樣在步驟2之中，所產生的關聯法則也必須大於使用者所設定的最小可靠門檻值(minimalconfidence)才能成為一條有效的法則。,-,7,Apriori演算法推導過程,DataBase,Sup,-,8,Apriori所面臨問題,由於Apriori演算法牽涉到多次資料庫的掃描，或者產生大量的項目組，因此，當資料庫產生變動時，必須從頭的掃描來產生項目組以產生新的關聯法則，當資料庫龐大時，搜索的動作便成了耗時的工作，因此，對於使用在動態的網路流量的探勘中，很顯然的Apriori演算法並不適用。,-,9,模糊關聯規則,Apriroi演算法之support(X)是以項目集X中的項目同時出現在資庫D中記的筆計算，而用在網路入侵偵測上，每個項目在每筆記中會出現，因此每個項目會有一個化的值。如下圖：,-,10,模糊關聯規則,很顯然，對於化的資庫，傳統的Apriori演算法並適用。資探勘域中對於這種項目化的問題也有干方法被提出，而對化資庫探勘最直接簡單的方法，就是對於每個項目的值給予明確的割以判定等級，我們用重要性(significance)及穩定度(certainty)分別取代傳統Apriori演算法中的支持度(support)以及信賴度(confidence)我們融入了模糊理論的觀念，套用模糊理論的術語，每個項目名稱改稱為模糊變量(fuzzyVariable)，每個項目名稱的分改稱為模糊集合(fuzzySets)，如low，medium，high，個別用一個續函式，稱為成員函式(membershipfunction)，描述之。,-,11,模糊關聯規則,將切割的等級分成不同程度(低、中、高)帶入模糊函式，取自於MATLABFuzzyToolBox的預設函如下，其中a,b,c為可調整之常，右圖為不同程度所代表的模糊函數分類。,Low：f(x)=1/(1+exp(a(x-c)Medium：f(x)=1/(1+|(x-c)/a|2b)High：f(x)=1/(1+exp(-a(x-c),-,12,漸進式關聯規則,網路資料(流量)的更新是隨時進行的，因此，資料庫中的資料也必須隨著交易的新增而動態的紀錄新的資料。但由於一般所謂的動態資料並不適用於用在網路流量分析上，因為適用於網路中的動態資料，其對於即時更為關鍵，所設計的演算法必須快速的處理一筆新增的資料，且在下一筆新增資料進入之前完成探勘，並產生關聯法則。,-,13,漸進式關聯規則,設計想法考慮到不需要針對資料庫做重複的掃描，融合了漸進式關聯規則(incremental)的觀念，其演算法設計的方式，只需要針對上一筆資料的結果加入新進資料做結合來處理。不同於傳統關聯規則必須針對資料庫重複的掃描，漸進式關聯規則能針對新的資料處理，大大的改進重複搜索資料庫所浪費的時間與資源，因此，動態的關聯規則便能有效率的提高即時探勘的速度。,-,14,實際應用例子,我們預計使用四台電腦(如下頁)，每台電腦各自分擔不同工作，其主要目的為減少每台電腦的負擔，以達到最有效率的Mining，來完成線上即時偵測。電腦A:擷取封包並且統計特徵。電腦B:將電腦A傳送的資料帶入演算法進行Mining，產生Rules。電腦C:從資料庫去讀取每一筆Training出來的records。電腦D:將電腦B及電腦C所收到的Rules進行比對並計算相似度。,-,15,應用例子(圖解),擷取封包並且統計特徵,電腦A,電腦B,進行即時線上Mining,電腦C,自資料庫(MySQL)讀取正常的record,電腦D,進行模糊關聯規則相似度的比對,-,16,於動態資料中快速的模糊關聯規則產生演算法,傳統關聯規則探勘的技術中，假若資料庫有異動的資料時，就必須重複掃描資料庫計算關聯規則的過程，如此大量且耗時的方法，對於目前即時動態線上探勘並不適用，因為對於所挖掘的特徵無法達到即時的分析，因此如何設計出一套快速運用於網路(段)中的探勘演算法便成為我們所研究的重點。,-,17,設計動機,為了改進用於線上偵測即時關聯規則程式的效率與正確性，我們加入了動態的觀念。為了解決關聯規則最大的問題，是其必須不斷的重新掃描資料庫來產生Rule，然而這項過程與工作往往是關聯規則最大的問題，其所需要的時間以及執行步驟將無法即時且有效率的在特定的時間內完成。因此為了能有效的運用在網路上，我們必須找出一套方式來更快速的處理大量的封包資料。,-,18,設計想法,由於目前電腦的處理效能以及記憶體空間相當大，所以我們將犧牲空間來換取時間，也就是利用大量的記憶體空間位置來記錄龐大的項目組。程式將紀錄到長度為8的item-set，也將會花費上萬筆資料的記憶體空間，所以如何有效的處理記憶體空間便成為首先面對的問題，我們考慮用動態配置的方式，在系統一開始便將所以記憶體的位置依序的產生。,-,19,設計想法,為了更有效率的處理線上即時更新的動態資料，首先面臨必須能快速的處理一筆新進資料，我們採用動態配置記憶體的技術來產生各種不同程度(low、medium、high)的項目組，分別用鏈結串列的方式將其分別儲放在記憶體空間。右圖為系統開始時所建立的記憶體空間，並且照順序排列。,項目組Itemset1,項目組Itemset2,項目組Itemset3,項目組Itemsetn,-,20,結構建立方式,爲了將來所產生的關聯法則，系統必須要知道每個結構裡面所代表的意義(low、med、high)，所以我們採用2維陣列的方式來建立記憶體空間，給予標記。LowMedHighLowMedHighf11ABCf21DEFf3=GHIf4JKLf5MNOf6PQR,-,21,節點產生,透過1的個數來跑，不斷的呼叫函式來產生，例如項目組1的時候，結構建立的方式就是f1-lowf1-medf1-highf2-low.項目組2的時候產生兩個1，一個1固定在f1-low，另外一個放在f2-low然後去呼叫函式，結構建立的方式變為f1-low,f2-lowf1-low,f2-med下圖為系統在處理產生長度為2的項目組時所產生的節點。,-,22,1,1,1,1,1,1,1,1,1,1,“1”在這15個格子內依序移動,“1”在這15個格子內依序移動,“1”在這15個格子內依序移動,“1”在這12個格子內依序移動,“1”在這3個格子內依序移動,長度為2的項目組(2-itemset),Forexample:產生所有長度為2的candidateitemset，共有18C2個節點,-,23,節點標記,目前為止，我們建立了所有項目組所產生可能性，為了加入模糊化(Fuzzy)的觀念，在結構中加入了一個用來存放模糊之後的值(number)。此外，為了考慮到陣列無法快速的做分析及拆解以及必須明白各節點所代表的意義(為了將來產生關聯法則)，因此我們必須將各個節點做標記。我們透過上面介紹的英文字母以及所對應的英文字母做配對，來產生不同程度的配對。,-,24,B,C,D,O,A,D,D,D,G,P,“A”依序從D開始以下的15個格子做配對：ADAR,“B”依序從D開始以下的15個格子做配對：BDBR,“C”依序從D開始以下的15個格子做配對：CDCR,“D”依序從D開始以下的12個格子做配對：DGDR,“O”依序從P開始以下的3個格子做配對：OPOR,長度為2的項目組(2-itemset),Forexample:將會產生ADAR、BDBR、CDCR、DCDR、OPOR這些長度為2的candidateitemset。,-,25,關聯規則的問題,為了用於線上動態的偵測，其講究的不外乎是執行的效率，也就是再下一筆拆解分析的資料進來之前，是否能將之前的資料結束，否則將再同一時間延後分析的效率，影響其結果。但是關聯規則最大的問題就是必需重複的掃描資料庫來建立項目組，這是一項費時的工作，因為前項-項目組有可能會影響之後所結合的項目組。(4-itemset是由3-itemset與2-itemset來建立),-,26,解決方法,此外，為了不需要再去重複的搜索資料庫浪費龐大的計算時間，將採用上列建立資料結構的方法來解決。我們加入了incremental(動態資料處理)的方式，利用動態改變資料庫的內容，再每一筆新資料進入之前，我們保存之前的資料結果在一起計算。便可以不需要從頭搜索資料庫一遍，只需針對上幾筆資料的結果來運算。,-,27,結構中的值改變,經過第2筆資料帶入，其結構中的以及變化。,交易筆數：1項目組1-itemset,交易筆數：2結果：Support(舊)+Support值(新)/交易筆數,-,28,結構中2-itemset的值,此時，結構中將會把所有可能產生的項目組的組合都建立出來，需要注意的是，相同一層的程度是不可能同時出現的，也就是A(f1-low)不可能跟相同一層的B(f1-med)跟C(f1-high)做組合成AB跟AC。,-,29,改進方式,需要強調的是，帶入模糊運算以及結構中值的改變是每次都必須的，也就是不管成不成立與否，都必須改變結構中的值，才能保證下筆資料進入前的資料是正確的。上頁的例子，只針對1-itemset來做解釋，在同時n-itemset(n從16)都必須做改變，如此並解決重複搜索資料庫的問題了，因此只需要針對前一筆的資料來做處理。,-,30,Rule產生,每個項目組都會產生滿足的項目如：BE、ADG、CFHK等等。接下來Rule的產生就必須針對滿足支持度的項目去做拆解。,BEBEEB,ADGADGDAGGADDGAAGDADG,CFHKCFHKFHKCFCHKCHKFHCFKCFKHKCFHCFHKCFHKHKCFCHFKFKCHCKFHFHCK,此外，拆解完成所有可能的集合同時，必須去計算confidence值，滿足大於等於才能判斷是一條可以參考的Rule。,-,31,Confidence值補充,confidence值的計算：ADG：confidence=ADG(support)/A(support)DGA：confidence=ADG(support)/DG(support)我們發現計算confidence只用到箭頭右邊的英文字，所以我們必須要紀錄並且回到資料庫去搜尋位於箭頭左邊英文字所對應的結構中support值。而這個support值必須回到所宣告的陣列結構之中搜索，也就是當初所設計的將陣列轉換成字串，因為字串的拆解比較方便、容易解讀。confidence必須大於等於所設定的範圍才能稱為一條可信賴的Rule。,-,32,可行性分析,目前CPU的計算及硬體I/O的考量，資料存放的空間已經不再是一個嚴重的問題，因此我們採用動態記憶體配置的技術來將所有項目組的可能產生，我們採用8個特徵，3種程度，而所花費的記憶體空間如下頁圖，對於應用在網路流量的探勘中，太高的項目組所代表意義可能被大量且不同類型的封包給掩蓋掉，因此，本系統只產生到項目組8，而大約花費1.1MB的記憶體空間，可針對不同的環境做項目組的改變。,-,33,記憶體空間,-,34,即時網路流量分析演算法特性,本文所設計的即時動態關聯規則演算法中主要包含以下主要的步驟：Step1.系統進行初始化並設定最小支持度(minimumsupport)。Step2.動態配置記憶體，建立所需的Link-list，根據項目組長度建立資料所存放空間。Step3.每單位時間讀入新增封包紀錄，並與每個節點計算此筆紀錄之fuzzy值(high、medium、low)，更新記憶體中的資料。,-,35,即時網路流量分析演算法特性,Step4.計算其支持度是否符合，若大於所設定的最小支持度，則找出此點之Rule，進行分析，小於則淘汰，紀錄該節點資料。Step5.計算Rule之信賴度，將大於最小信賴度之Rule印出。Step6.自演算法系統中取出即時線上探勘的關聯法則與資料庫中正常封包的關聯法則進行交叉比對，判斷是否遭受攻擊。,-,36,效能評估,在失一般情況下，我們使用隨機產生每筆交資的項目，做為評估前面章節演算法之執效能的資源。實驗平台為P4-3.0G、RAM為512M、作業系統為WindowsXPSever，使用C+撰寫程式。假設項目共有6項，且各分為低、中、高三種不同的等級，每筆交資所包含的項目以產生(每次新增交資就須重新計算)，來評估執效能。我們初始以1000筆交資為探勘的資源，在設定最小支持為0.3及最小信賴為0.5的條件下，然後以每次新增1000筆交資，且每次皆重新執行，評估我們演算法的執時間。,-,37,效能評估,在每次新增交資時，本演算法於一開始探勘的執時會有一段初始化的時間。由於第一次探勘時就將其過程中的項目組與其出現次儲存於記憶體中，因此對於