基于關聯規則挖掘的智能云防護技術研究*

方忠進,夏志華,周 舒

(1.南京信息工程大學 計算機與軟件學院,江蘇南京210044;

2.南京信息工程大學 濱江學院,江蘇南京 210044;

3.南京信息工程大學 江蘇省網絡監控工程中心,江蘇南京210044)

基于關聯規則挖掘的智能云防護技術研究*

方忠進1,2,3,夏志華1,3,周 舒1,3

(1.南京信息工程大學 計算機與軟件學院,江蘇南京210044;

2.南京信息工程大學 濱江學院,江蘇南京 210044;

3.南京信息工程大學 江蘇省網絡監控工程中心,江蘇南京210044)

針對傳統安全防護技術存在的被動防御、效率較低的缺陷,提出了一種基于關聯規則挖掘的智能云防護技術。該技術引入一種改進的FP-Growth挖掘算法,用來提取數據的特征信息,提交到云端,通過將此特征信息與入侵特征庫和網絡正常活動行為特征庫進行匹配,從而發現病毒和攻擊行為。特征庫根據龐大的云探針系統采集的數據樣本不斷更新完善。實驗結果表明,基于改進的FP-Growth挖掘算法的智能云防護技術對攻擊行為響應較快,檢測效率較高,準確記錄攻擊日志,具有較好的安全防護性能。

關聯規則 云安全 FP-Growth算法 數據挖掘

0 引 言

隨著網絡技術的快速發展,網絡攻擊、數據泄露等信息安全事件頻發,防火墻等傳統的靜態安全防御技術對于攻擊缺乏主動的響應,已無法滿足日益復雜的安全應用要求。利用云計算來提高安全防護能力已成為信息安全領域研究的新課題。“云計算”直接起源于2007年Amazon EC2產品和Google-IBM分布式計算項目,這兩個項目直接使用了“云計算”這一概念[1]。云計算是網格計算、分布式計算、并行計算、效用計算、網格存儲、虛擬化、負載均衡等傳統計算機和網絡技術發展融合的產物,它能有效解決網格計算無法同時支持異構多任務體系、無法實現資源動態流轉的不足[2-3]。云計算以新的業務模式提供高性能、低成本的持續計算和存儲服務,支撐各類信息化應用。

針對云計算具有的資源動態流轉、支持海量信息處理的特點,提出一種智能云防護技術。云平臺的每一個客戶端作為一個探針,網狀的大量探針提取出數據信息中的特征,提交給云端進行分析和處理,對于木馬、病毒等攻擊行為,云端將解決方案下發給探針。當某個探針遭受新的安全威脅,智能云防護技術將會獲取其特征信息,更新入侵特征庫。最新的入侵、病毒特征信息會及時更新共享,并適時給出解決方案。通過分布在全球各地的探針,云端數據庫積累了大量的特征信息,及其全面、準確地創建了網絡正常活動行為特征庫,利用特征庫來監視是否存在安全威脅行為,正常行為特征庫精確地提前定義出可能發生的安全風險與威脅。

數據挖掘,也稱數據庫中的知識發現(KDD, Knowledge Discovery in Database),指從大型數據庫或數據倉庫中提取人們感興趣的知識,這些知識是隱含的、事先未知的潛在有用信息,提取的知識一般可表示為概念(Concepts)、規則(Rules)、規律(Regularities)、模式(Patterns)等形式[4]。簡單地說,數據挖掘就是從大量的數據中抽取挖掘出未知的、有價值的模式或規律知識的復雜過程。

關聯規則挖掘是數據挖掘中最活躍、最有效的研究方法之一,本文提出了一種基于關聯規則挖掘的智能云防護技術框架,采用一種改進的FPGrowth算法進行網絡數據特征提取,分析了相關實驗結果。

1 技術架構

智能云防護技術將云端和客戶端有機結合,構建高效的智能威脅收集系統,通過數據挖掘技術創建入侵特征庫和正常行為特征庫,云端根據各探針收集上報的數據信息,運用數據挖掘技術,對入侵特征庫和正常行為特征庫進行實時更新完善,及時發現新型威脅并將解決方案分發到各客戶端,從而將安全威脅消滅在最初階段。

基于關聯規則挖掘的智能云防護技術架構如圖1所示。

圖1 基于關聯規則挖掘的智能云防護技術架構Fig.1 Structure ofthe intelligent cloud protection technology based on association rule mining

系統方案設計如下:

1)位于不同位置的用戶上傳日志文件到云端通信模塊。

2)云端通信模塊將日志文件寫入到特定的數據庫。

3)挖掘模塊定時讀取日志數據庫并執行數據挖掘操作,輸出特征內容寫入到特征數據庫

4)用戶端定期通過云端通信模塊訪問特征數據庫,更新本地特征庫。用戶端根據特征庫攔截可能存在的攻擊行為。

建立特征庫的過程見圖2。

圖2 應用關聯規則挖掘建立特征庫的過程Fig.2 Building feature database with application of association rule mining

2 改進的FP-Growth關聯算法

數據挖掘是一種有效地針對海量數據進行分析處理的技術,能夠提取出大量網絡數據中潛在的規則信息,本文使用中的數據挖掘模塊采用的是關聯分析算法,關聯規則挖掘可以發現數據中項集之間有用的關聯或相關聯系,對于安全防護系統而言,則可以提取出網絡數據中的特征模式[5]。本文采用一種改進的FP-Growth關聯算法。

2.1 FP-Growth關聯算法分析

FP-Growth(Frequent-pattern Growth)算法是由Jiawei Han,Jian Pei等人提出的,該算法采用模式增長的方法,從大規模數據中挖掘出頻繁模式,這樣就不需要額外產生候選集。該算法使用的策略如下:算法將數據庫中的頻繁項集合進行壓縮,使之成為一棵頻繁模式樹(FP-tree)的同時,關聯信息依舊被保留。將壓縮后的數據庫分成一組條件數據庫,每個條件數據關聯一個頻繁項,進而分別挖掘這些條件數據庫。該算法可以通過遞歸方式發現一些短模式,替代了原本復雜地發現長頻繁模式的問題,然后連接后綴,效率上較之經典關聯Apriori算法有了很大的提高[4,6]。

FP-tree的定義如下:

1)樹有一個根結點,用空值“null”來標記,它的子樹是一個項前綴子樹的集合。除此之外,還有一張表來存貯每個頻繁項結點的頭結點。

2)項前綴子樹各節點由以下3部分組成:項目名稱、頻繁項計數器和一個結點指針。其中項目名稱表示的是該結點所描述的頻繁項,頻繁項計數器記錄的是從根結點出發到此結點的詳細路徑所包含的事務的數量,結點指針所指向的是項前綴子樹里下面一個和此結點具有同樣名稱的結點,如果后續已經沒有表示該項目的其他結點了,則設這個結點的指針值為空值。

3)頻繁項頭表中的各個項由兩個字段構成:項目名稱與頭指針。頭指針指向項前綴子樹中第一個同名項。

FP-Growth算法的主要步驟[7]如下:

1)掃描事務數據庫一遍得到各項目的頻度,根據最小支持度得到頻繁項;對頻繁項按其頻度由大到小排列成表L,形成頭表。

2)再次掃描事物數據庫一遍,對每一條交易中的所有頻繁項,按表L中的次序插入到FP-Tree中。

3)調用FP_growth算法對FP-Tree進行挖掘。

FP-Growth算法在本質上不同于Apriori算法的候選生成-篩選方法,克服了Apriori算法的缺點,通過采用關聯規則挖掘新思路,解決了傳統方法中需要產生候選項集的問題。該算法中所構造出的FP-tree是一種具有高壓縮度的數據結構,存儲的是與頻繁模式相關的重要內容;此算法僅對數據庫掃描兩遍,將掃描時間減少到最少,提高了效率。數據挖掘的主要工作就是對累加值進行計算并對前綴樹進行調整,這種在存儲和計算資源上的花費要比Apriori算法中使用的候選項集產生算法與模式匹配操作算法小得多。

2.2 FP-Growth改進算法

盡管FP-Growth算法有不少優點,但它仍有不足之處。例如在對頻繁模式進行挖掘時,其需要使用遞歸算法不斷地生成條件FP-tree,當生成一個頻繁模式時就會產生一個與其對應的條件FP-tree。在最小支持度相對較小時,即使挖掘不太大的數據庫,也將產生成千上萬的條件FP-tree。如此多的條件FP-tree的動態創建和釋放,會耗費非常多的CPU處理時間和存儲空間,這對挖掘效率的影響是非常大的。同時,FP-tree與條件FP-tree生成時需要采用自頂向下的方式,而對于頻繁模式的挖掘使用的卻是自底向上的方法進行處理。FP-Growth算法使用遞歸方式生成條件FP-tree,因此構造的FP-tree與條件FP-tree必須能夠雙向可遍歷,這樣系統就需要更多的存儲空間來保存FP-tree和條件FP-tree。因此,FP-Growth算法在時間和空間效率上仍然有待提高,對于大數據的處理能力也不是太強。

本文提出的一種改進的FP-Growth算法,該算法改進了FP-tree結構,引入了一種前綴樹結構AFP-tree。對AFP-tree的挖掘采用深度優先的策略,不需要構造條件模式庫,所以該算法能夠顯著提高挖掘效率。

(1)AFP-tree

前綴樹AFP-tree記錄的是事務數據庫DB中的每個事務Trans的頻繁項,FP-tree中的項按支持度降序排列,在前綴樹AFP-tree中,所有的頻繁項組成一個偏序集,事務中的項按字典順序排列。所以,兩者的區別在于頻繁項的順序不同。AFP-tree中的每個節點由4部分組成:項目名稱、頻繁計數、節點指針和父節點指針。有3個頻繁項的完全前綴樹如圖3所示,包含了3個頻繁項所構成的所有模式。從根節點到其它節點表示每種模式,每個子樹表示以該子樹的根為前綴的所有模式。

從前綴樹的結構可以看出,事務數據庫的每條記錄都存在于前綴樹AFP-tree的某條路徑中,前綴樹AFP-tree的深度為數據庫中事務的最大長度。前綴樹AFP-tree的結構為我們提供了一個高效的挖掘策略:如果某節點的計數小于最小支持度minsup,也就是說該項不頻繁,那么以該節點為根的整個子樹中不存在頻繁模式。因此,這種樹結構可以顯著提高挖掘的效率。當使用基于FP-tree的FPGrowth算法時,由于相同模式可能分布在不同的子樹中,對單個子樹進行挖掘時無法判斷某個模式是否頻繁,必須遞歸地構建條件FP-tree才能最終判斷,效率不高。而挖掘前綴樹AFP-tree就不需要構造條件模式樹,采用深度優先的挖掘策略就可判斷某個模式是否為頻繁模式。

圖3 3個頻繁項的完全前綴樹AFP-treeFig.3 Complete prefix tree of AFP-tree with three frequent items

(2)基于AFP-tree的頻繁模式挖掘算法

本算法采用由上而下的深度優先的策略進行挖掘,挖掘步驟分為以下幾步:

1)掃描事務數據庫DB一遍,根據頻繁項之間的偏序關系構造初始前綴樹AFP-tree,對各頻繁項按照支持度計數的順序形成頭表。

2)不斷調整前綴樹中的節點鏈和節點計數,從而在AFP-tree中采用由上而下的深度優先的挖掘策略來挖掘頻繁模式。

算法的執行過程如下:

輸入:事務數據庫DB,最小支持度min_sup。

輸出:頻繁模式的完全集。

①生成AFP-tree

對數據庫項進行一遍掃描,獲取各頻繁項的集合F與其支持度的相關信息。按照支持度對集合F進行降序排序,獲得頻繁項表L。

構建樹的根部節點,其值記為“null”。然后對數據庫中的每項事物Trans按以下方式處理:a)將位于Trans中的各頻繁項按照L當中的相同次序進行排序。假設排序以后的頻繁項列表表示為[p| P],其中p是首個項目,P是列表的其他部分;b)調用方法insert_tree([p|P],T),insert_tree([p|P], T)的具體執行過程如下:假如T中包含1個子結點N,滿足條件N.item_name=p.item_name,則對N的計數器執行加1操作;否則,按照偏序關系新建1個節點N,使其計數為1,通過父節點指針鏈接到它的父節點T,并且使用節點鏈結構將其鏈接到item_ name相同的節點上。如果P不是空集,則遞歸調用方法insert_tree(P,N)。

②對AFP-tree進行挖掘

對每個頻繁項α執行以下過程:

Procedure AFP_Mine(α,AFP-tree)

for anyα的子樹根節點subroot do

if(α的右兄弟節點中存在節點ribroot,使得ribroot.item=subroot.item)or(α的右兄弟節點中不存在與節點subroot相同名稱的節點,ribroot=null) then Combine(subroot,ribroot);

將α.αi和α.αi.count加到頻繁模式集;

設β的子節點中與αi名稱相同的節點為βi, Combine(αi,βi);

3 實驗與分析

本文采用XenServer構建模擬云平臺作為實驗平臺,并選取美國麻省理工學院林肯實驗室公開提供的DARPA入侵檢測評價計劃中的數據集KDDCup99[8]進行實驗,構建客戶實例。整個KDDCup99數據集約有490萬條數據記錄,數據量很龐大。考慮到實驗的可行性,從中選取10%的數據作為本實驗的數據集。

分別選用較少、普通和很多攻擊案例來模擬真實世界中的網絡使用環境,可以得到3組不同的數據集合,各組數據集合中的訓練集與測試集情況如表1所示。

使用本文提出的改進FP-Growth算法對表1中的3組訓練集分別進行學習訓練,進而提取特征模式,生成特征庫,然后使用測試集分別對其進行測試,得到的實驗結果如表2所示。

采用未改進的FP-Growth算法進行實驗的結果見表3。

比較表2和表3可以看出:

1)本文中的各組訓練時間分別比傳統的FPGrowth算法降低50.82%、52.40%和54.00%。因此,本文提出的FP-Growth改進算法可以在很大程度上提高系統的檢測效率。

2)對于各組數據,改進后的FP-Growth算法的檢測效率比傳統FP-Growth算法提高了1.19%～1.75%,誤報率降低了13.84%～17.52%,漏報率降低30.90%～44.46%,檢測性能得到了很大改善。

實驗結果表明,本文提出的FP-Growth改進算法較傳統算法在性能上有顯著提高,非常適用于云環境下的安全防護。

表1 數據集樣本組成情況Table 1 Composition of data sets

表2 基于FP-Growth改進算法的實驗結果Table 2 Experimental results of the improved FP-Growth algorithm

表3 改進前的FP-Growth算法實驗結果Table 3 Experimental results of the FP-Growth algorithm

4 結 語

本文提出一種基于關聯規則挖掘的智能云防護技術,利用云平臺中大量探針提取出的數據信息,在云端進行分析和處理,應用數據挖掘技術建立網絡行為特征庫。針對傳統FP-Growth算法存在的時空效率不高,海量數據處理能力較弱的缺點,提出一種改進的FP-Growth算法,該算法改進了FP-tree結構,引入了一種前綴樹結構。實驗結果表明,改進算法能有效地提高數據挖掘的速度,增強檢測能力,為網絡安全維護提供了堅實的基礎。

[1] HUANG Dijiang,ZHOU Zhibin,XU Le.Secure Data ProcessingFrameworkforMobileCloudComputing [C]//IEEE INFOCOM 2011 Workshop on Cloud Computing.Shanghai:IEEE,2011:614-618.

[2] SAKR Sherif,LIU Anna,BATISTA Daniel M.A Survey of Large Scale Data Management Approaches in Cloud Environments[J].IEEE Communications Surveys&Tutorials,2011,13(03):311-336.

[3] DIMITRIOS Zissis,DIMITRIOSLekkas.Addressing Cloud Computing Security Issues[J].Future Generation Computer Systems,2012,28(03):583-592.

[4] HAN Jiawei,KAMBER Micheline.數據挖掘——概念與技術[M].北京:機械工業出版社,2001.

HAN Jiawei,KAMBER Micheline.Data Mining:Concepts and Techniques[M].Peking:China Machine Press,2001.

[5] 肖東榮,楊磊.基于遺傳算法的關聯規則數據挖掘[J].通信技術,2010,43(01):205-207.

XIAO Dongrong,YANG Lei.Association Rule Data Mining Based on Genetic Algorithm[J].Communications Technology,2010,vol.43(1):205-207.

[6] RAMASWAMY Sridhar,RASTOGI Rajeev,SHIM Kyuseok.Efficient Algorithms for Mining Outliers from Large Data Sets[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data.Dallas,TX,USA:ACM,2000:427-438.

[7] SEQUEIRA Karlton,ZAKI Mohammed.ADMIT:Anomaly-based Data Mining for Intrusions[C]//Proceedings of the 8th ACMSIGKDD International Conference on Knowledge Discovery and Data Mining.Edmonton,Alberta, Canada:ACM,2002:386-395.

[8] KDD Cup 1999 Data[EB/OL].(1999-10-28)[2014-04-10].http://kdd.ics.uci.edu/databases/kddcup99/ kddcup99.html.

FANG Zhong-jin(1979-),male,Ph.D student,lecturer,majoring in network information security and cloud security.

夏志華(1983-),男,博士,講師,主要研究方向為信息安全、隱寫分析;

XIA Zhi-hua(1983-),male,Ph.D.,lecturer,mainly engaged ininformation security and steganography.

周 舒(1984-)女,碩士,助理研究員,主要研究方向為信息安全。

ZHOU Shu(1984-),female,M.Sci.,research associate,mainly working atinformation security.

Study on the Intelligent Cloud Protection Technology based on Association Rule Mining

FANG Zhong-jin1,2,3,XIA Zhi-hua1,3,ZHOU Shu1,3
(1.School of Computer&Software,Nanjing University of Information Science&Technology,Nanjing Jiangsu 210044,China; 2.Binjiang College,Nanjing University of Information Science&Technology,Nanjing Jiangsu 210044,China; 3.Jiangsu Engineering Center of Network Monitoring,Nanjing University of Information Science&Technology,Nanjing Jiangsu 210044,China)

According to the limit of passive defense and low detection efficiency of traditional security technology,an intelligent cloud protection technology based on association rule mining is proposed.An improved FP-Growth algorithm is applied to extract the feature information of data.The feature information is matched with intrusion feature database and normal activities feature database to detect viruses and attacks. Feature database is continuously updated and improved according to the data samples collected by the huge cloud probe system.Experimental results show that the intelligent cloud protection technology based on the improved FP-Growth algorithm can detect attacks in time,and record attack log accurately.It has a high detection efficiency and good protection performance.

association rule;cloud security;FP-Growth algorithm;data mining

TP391.4

A

1002-0802(2014)08-0925-05

10.3969/j.issn.1002-0802.2014.08.017

方忠進(1979-),男,博士研究生,講師,主要研究方向為網絡信息安全、云安全;

2014-05-06;

2014-06-24 Received date：2014-05-06;Revised date：2014-06-24