基于Apriori算法的安全事件二級(jí)關(guān)聯(lián)方法

◆唐湘滟 程杰仁 劉博藝 鄭兆華 周靜荷

（海南大學(xué)信息科學(xué)技術(shù)學(xué)院 海南 571101）

基于Apriori算法的安全事件二級(jí)關(guān)聯(lián)方法

◆唐湘滟 程杰仁 劉博藝 鄭兆華 周靜荷

（海南大學(xué)信息科學(xué)技術(shù)學(xué)院 海南 571101）

安全信息的數(shù)據(jù)關(guān)聯(lián)技術(shù)是目前網(wǎng)絡(luò)安全領(lǐng)域的熱點(diǎn)，國際上許多國家的安全機(jī)構(gòu)都在大力研究安全事件關(guān)聯(lián)技術(shù)來建立完善可靠的安全防御系統(tǒng)，保障國家利益。本文對(duì)網(wǎng)絡(luò)安全事件關(guān)聯(lián)進(jìn)行了需求分析，將網(wǎng)絡(luò)安全事件關(guān)聯(lián)劃分為4個(gè)子模塊，對(duì)各個(gè)子模塊進(jìn)行了詳細(xì)設(shè)計(jì)。采用基于因果關(guān)聯(lián)方法的聚類對(duì)安全事件進(jìn)行歸并，將安全告警事件劃分為具有邏輯因果關(guān)系的集合，然后利用基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘方法挖掘出各個(gè)安全告警事件集合之間的內(nèi)在關(guān)聯(lián)關(guān)系，實(shí)現(xiàn)了對(duì)于告警數(shù)據(jù)進(jìn)行事件關(guān)聯(lián)的模塊功能，較好地提高了對(duì)組合攻擊的關(guān)聯(lián)效率。

網(wǎng)絡(luò)安全; Apriori算法; 關(guān)聯(lián)方法

0 前言

安全信息的數(shù)據(jù)關(guān)聯(lián)技術(shù)最早開始于入侵檢測(cè)研究技術(shù)中關(guān)于分布式IDS中告警的協(xié)同分析方法的研究，是目前網(wǎng)絡(luò)安全領(lǐng)域的熱點(diǎn)。國際上許多國家的安全機(jī)構(gòu)都在大力研究安全事件關(guān)聯(lián)技術(shù)來建立完善可靠的安全防御系統(tǒng)，保障國家利益。

1993年R．Agrawal首次提出關(guān)聯(lián)規(guī)則的定義[1]，1994年提出了Apriori算法[2]，2000年韓家瑋提出了FP-TREE算法[3]，兩人的工作為關(guān)聯(lián)規(guī)則挖掘技術(shù)提供了理論基礎(chǔ)。2002年起R．Agrawal 負(fù)責(zé)的IBM Zurich研究所開始研制“Tivoli關(guān)聯(lián)分析系統(tǒng)”[4]，預(yù)計(jì)2016年完成。美國國防部從1998年到2006年研制了“EMERALD”系統(tǒng)[4]，提供美國軍方使用。美國的DARPA&NSF從2006年起利用數(shù)據(jù)挖掘關(guān)聯(lián)技術(shù)進(jìn)行IDS告警分析[4]并有償向大型企業(yè)提供商業(yè)應(yīng)用。法國國防部1999年推出“30年遠(yuǎn)景計(jì)劃”，是一個(gè)具備入侵檢測(cè)，報(bào)警，自動(dòng)跟蹤的MIRADOR項(xiàng)目[4]。國際上雖然已經(jīng)將關(guān)聯(lián)規(guī)則挖掘引入網(wǎng)絡(luò)安全態(tài)勢(shì)評(píng)估系統(tǒng)[5-7]，但是目前大多數(shù)系統(tǒng)的關(guān)聯(lián)規(guī)則應(yīng)用與安全事件關(guān)聯(lián)模塊是分離的，實(shí)現(xiàn)評(píng)估功能更多的是憑借高速數(shù)據(jù)存儲(chǔ)技術(shù)和高速的巨型機(jī)，關(guān)聯(lián)規(guī)則的應(yīng)用大多在數(shù)據(jù)庫中處理物理數(shù)據(jù)而不是在關(guān)聯(lián)的核心模塊中處理邏輯數(shù)據(jù)，關(guān)聯(lián)還是主要依靠專家系統(tǒng)與人工判斷，這樣在很大程度上會(huì)限制了安全事件關(guān)聯(lián)的效率。

近幾年來，隨著對(duì)于關(guān)聯(lián)規(guī)則挖掘的重視和網(wǎng)絡(luò)安全評(píng)估系統(tǒng)的建設(shè)，國內(nèi)在相關(guān)領(lǐng)域出現(xiàn)了大量的研究成果[8-14]。華中科大李家春領(lǐng)導(dǎo)研究小組研發(fā)了分布式入侵告警關(guān)聯(lián)技術(shù)分析系統(tǒng)，西安交通大學(xué)李輝提出了一種基于交互式知識(shí)發(fā)現(xiàn)的入侵事件關(guān)聯(lián)方法。目前，清華大學(xué)，北京大學(xué)，國防科技大學(xué)，信息安全國家重點(diǎn)實(shí)驗(yàn)室，東南大學(xué)，南京大學(xué)，華南理工大學(xué)，哈爾濱工業(yè)大學(xué)等學(xué)校均在開展相關(guān)的課題研究[12-14]。瑞星公司已經(jīng)推出了商業(yè)產(chǎn)品“SDS-1000 網(wǎng)絡(luò)安全評(píng)估系統(tǒng)”。國內(nèi)的大多數(shù)研究仍然是將安全事件關(guān)聯(lián)與關(guān)聯(lián)規(guī)則分離開進(jìn)行研究，大多數(shù)的安全態(tài)勢(shì)評(píng)估系統(tǒng)實(shí)際上還是在模式匹配方面進(jìn)行研究。

1 基于Apriori算法的安全事件二級(jí)關(guān)聯(lián)方法

基于Apriori算法的安全事件二級(jí)關(guān)聯(lián)方法是首先通過事先定義的各種網(wǎng)絡(luò)安全事件類型因果關(guān)聯(lián)知識(shí),采用因果關(guān)聯(lián)算法對(duì)安全事件集聚類，形成因果事件集,然后利用Apriori算法對(duì)因果事件集進(jìn)行關(guān)聯(lián)挖掘，生成關(guān)聯(lián)事件集。由于網(wǎng)絡(luò)安全事件一般不會(huì)孤立存在，絕大多數(shù)網(wǎng)絡(luò)安全事件相互之間具有一定的因果聯(lián)系。基于這種固有的因果關(guān)系可以將描述網(wǎng)絡(luò)安全事件地關(guān)聯(lián)起來，進(jìn)而形成可以描述網(wǎng)絡(luò)安全事件之間關(guān)系的攻擊場(chǎng)景。

1.1 因果關(guān)聯(lián)模型

因果關(guān)聯(lián)雖然可以揭示網(wǎng)絡(luò)安全事件之間的關(guān)系，但是由于攻擊場(chǎng)景的缺損和攻擊場(chǎng)景的高噪聲問題會(huì)阻礙安全人員對(duì)攻擊場(chǎng)景的識(shí)別，甚至在一定程度上誤導(dǎo)安全人員。為降低這些問題的影響，本文引入因果可信度（reliability）和支持度（Support）對(duì)因果關(guān)聯(lián)程度較強(qiáng)的事件進(jìn)行加權(quán)和累計(jì)。

設(shè)I={Ia，…，Im }是項(xiàng)集，其中的元素稱為項(xiàng)（item）。記D為安全事件S的集合，這里安全事件S是項(xiàng)的集合，并且S∈I。對(duì)應(yīng)每一個(gè)安全事件有唯的標(biāo)識(shí)，記作E。設(shè)X是一個(gè)I中項(xiàng)的集合，如果X∈S，那么稱安全事件S包含X。

設(shè)X為前提，Y為結(jié)果，X與Y有因果關(guān)系，記為X-〉Y，其中X∈I，Y∈I并且X與Y的交集是空集。則X-〉Y在安全事件數(shù)據(jù)庫D中的支持度（Support）是安全事件集中包含X和Y的事件數(shù)與所有事件數(shù)之比，可信度（reliability）是包含X和Y的事件數(shù)與包含X的事件數(shù)之比。

為了簡(jiǎn)化的安全事件關(guān)聯(lián)過程和通用性，本文通過匹配前提（prerequisite）和結(jié)果（consequence）形成安全事件之間的因果對(duì)應(yīng)關(guān)系，將安全事件的前后事件特征進(jìn)行抽象化處理，即將攻擊場(chǎng)景中的原子攻擊事件作為某一攻擊抽象類集合的一個(gè)實(shí)例。一個(gè)安全事件抽象類A（attack）可以用一個(gè)五元組來描述，即C（E，P，R，C，O），E（eventType）為事件的類型標(biāo)識(shí)，P（prerequisite）為攻擊事件成功發(fā)生所需前提條件事件集合，記為P（E），R（reliability）為前提條件事件可信度集合，記為R（E），C（consequence）為攻擊事件發(fā)生后可能產(chǎn)生的事件集合，記為C（E），它們可為單個(gè)原子謂詞或謂詞公式，謂詞參數(shù)變量來自屬性名集合O，一般至少包括源IP地址、目的IP地址、源端口和目的端口等。其中每一個(gè)屬性名都有一個(gè)對(duì)應(yīng)的論域。

1.2 關(guān)聯(lián)規(guī)則模型

關(guān)聯(lián)規(guī)則挖掘的任務(wù)是:給定一個(gè)因果關(guān)聯(lián)事件集D，求出所有滿足最小支持度min-sup和最小可信度min-conf的關(guān)聯(lián)規(guī)則事件集，為安全態(tài)勢(shì)評(píng)估提供有效的數(shù)據(jù)源。關(guān)聯(lián)規(guī)則挖掘可以分解為兩個(gè)子問題:求出D中滿足最小支持度min-sup的所有頻繁項(xiàng)目集; 利用頻繁項(xiàng)目集生成滿足最小可信度min-conf的所有關(guān)聯(lián)規(guī)則。挖掘關(guān)聯(lián)規(guī)則過程為兩步:第一步產(chǎn)生所有的頻繁項(xiàng)目（簡(jiǎn)稱頻繁集），即找出所有支持度不低于用戶指定的最小支持度的項(xiàng)目集。第二步從已得到的頻繁集中構(gòu)造置信度不低于用戶指定的最小置信度的規(guī)則。關(guān)聯(lián)規(guī)則概念是由Agrawal等人在1993年率先提出的，并隨后提出了Apriori算法，Apriori算法使用一種稱作“逐層的迭代”的方法通過低維頻繁項(xiàng)目集來產(chǎn)生高維頻繁項(xiàng)目集。Apriori算法的核心思想見圖1。

圖1 Apriori算法

2 安全事件二級(jí)關(guān)聯(lián)方法

基于Apriori算法的安全事件二級(jí)關(guān)聯(lián)方法的偽代碼描述見圖2。

圖2 基于Apriori算法的安全事件二級(jí)關(guān)聯(lián)方法

3 測(cè)試與分析

3.1 測(cè)試環(huán)境和工具

測(cè)試環(huán)境硬件列表見表1，測(cè)試軟件環(huán)境見表2。

表1 測(cè)試硬件列表

表2 測(cè)試軟件列表

3.2 測(cè)試結(jié)果及分析

測(cè)試程序界面截圖如圖3，測(cè)試結(jié)果安全事件關(guān)聯(lián)分析效率見圖4，安全事件關(guān)聯(lián)規(guī)則數(shù)量比較見圖5。通過對(duì)測(cè)試結(jié)果的分析，得到了一下的一些結(jié)論:

在用戶定義的可信度和置信度不變的情況下，算法的效率受數(shù)據(jù)庫事件總量影響明顯。

數(shù)據(jù)庫事件數(shù)量越多，用戶的置信度和可信度都應(yīng)該相應(yīng)減少，否則很難挖掘出足夠多的符合用戶需要的關(guān)聯(lián)規(guī)則，基于相同的置信度和可信度，一般待挖掘事件集內(nèi)的事件個(gè)數(shù)越多，越容易挖掘出更多的關(guān)聯(lián)規(guī)則。用戶能否在實(shí)踐中設(shè)置適合的可信度參數(shù)，對(duì)于事件關(guān)聯(lián)的結(jié)果有很大的影響。測(cè)試結(jié)果表明，事件關(guān)聯(lián)模塊的關(guān)聯(lián)規(guī)則挖掘部分可以較好地實(shí)現(xiàn)Apriori算法，在輸出的關(guān)聯(lián)規(guī)則中標(biāo)明了該規(guī)則的可信度和置信度。

圖3 測(cè)試界面截圖

圖4 安全事件關(guān)聯(lián)分析效率

圖5 安全事件關(guān)聯(lián)規(guī)則數(shù)量比較

4 結(jié)束語

本章對(duì)網(wǎng)絡(luò)安全事件關(guān)聯(lián)進(jìn)行了需求分析，將網(wǎng)絡(luò)安全事件關(guān)聯(lián)劃分為4個(gè)子模塊，對(duì)各個(gè)子模塊進(jìn)行了詳細(xì)設(shè)計(jì)。采用基于因果關(guān)聯(lián)方法的聚類對(duì)安全事件進(jìn)行歸并，將安全告警事件劃分為具有邏輯因果關(guān)系的集合，然后利用基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘方法挖掘出各個(gè)安全告警事件集合之間的內(nèi)在關(guān)聯(lián)關(guān)系，實(shí)現(xiàn)了對(duì)于告警數(shù)據(jù)進(jìn)行事件關(guān)聯(lián)的模塊功能，較好地提高了對(duì)組合攻擊的關(guān)聯(lián)效率。不足之處是需要進(jìn)一步優(yōu)化Apriori算法，解決Apriori算法處理大規(guī)模數(shù)據(jù)庫效率不高的問題。

[1]R.Agrawal,R.Srikant.Fast algorithms for mining associati on rules in large databases.Research Report RJ 9839,IBM Al maden Research Center,California,June 1994.

[2]JIAWEI HAN,JIAN PEI,YIWEN YIN,RUNYING M AO,Mining Frequent Patterns without Candidate Generation:A Frequent-Pattern Tree,Data Mining and Kno wledge Discov ery,8,53–87,2004.

[3]李芝棠.網(wǎng)絡(luò)安全態(tài)勢(shì)關(guān)聯(lián)分析.CERNET,13.昆明,200 6.

[4]Bass T.Intrusion Detection Systems and Muhisensor Da ta Fusion:Creating Cyberspace Situational Awareness.Communi cations of the ACM,2000.

[5]CUPPENS F,LAMBDA OR.A language to model a database for detection of attacks.In:Proc.of Recent Advances in Intrusion Detection（RAID 2000）[C],2000.

[6]Yaxuan Qi,Lianghong Xu,Baohua Yang,Yibo Xue and Jun Li，Packet Classification Algorithms:FromTheory to Pract ice,Proc.of the 28th IEEE INFOCOM,2009.

[7]Bin Z,Gang T,Greg M.Combining Control-Flow Integ rity and Static Analysis for Efficient and Validated Data Sandb oxing[C].ACM Conference on Computer and Communication s Security（CCS）,2011.

[8]熊云燕，毛宜君.安全事件關(guān)聯(lián)分析引擎的研究與實(shí)現(xiàn).計(jì)算機(jī)工程，2006.

[9]HAN Jia wei，KAMBER M.數(shù)據(jù)挖掘概念和技術(shù).范明，孟小峰譯.北京機(jī)械工業(yè)出版社，2001.

[10]李家春，李芝棠.分布式入侵告警關(guān)聯(lián)分析.計(jì)算機(jī)研究與發(fā)展，2004.

[11]徐勇等.基于XML數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘.計(jì)算機(jī)工程與設(shè)計(jì)，2006.

[12]王文娟，王杰等.入侵檢測(cè)系統(tǒng)報(bào)警信息聚合與關(guān)聯(lián)技術(shù)研究綜述.信息安全，2006.

[13]Margaret H.Dunham等著，郭崇慧等譯.數(shù)據(jù)挖掘教程.清華大學(xué)出版社，2005.

[14]彭雪娜，聞?dòng)⒂?網(wǎng)絡(luò)安全信息關(guān)聯(lián)與分析技術(shù)的研究進(jìn)展.計(jì)算機(jī)工程，2006.

[15]Fu Z.,Ren K.,etc.(2016).Enabling Personalized Search ov er Encrypted Outsourced Data with Efficiency Improvement[J].IE EE Transactions on Parallel and Distributed Systems.Vol.27,PP.254 6 - 2559.

[16]Gu Bin,Victor S.Sheng.（2016）.A Robust Regularizatio n Path Algorithm for ν-Support Vector Classification[J].IEEE Tran sactions on Neural Networks and Learning Systems.Vol.1，PP. 1 - 8.

[17]Gu B.，Sun X.，etc.（2007）.Structural Minimax Proba bility Machine[J].IEEE Transactions on Neural Networks and Lear ning Systems.Vol.6，PP.1 - 11.

[18]Gu B.，Victor S.Sheng，etc.（2015）.Incremental Supp ort Vector Learning for Ordinal Regression[J].IEEE Transactions o n Neural Networks and Learning Systems.Vol.26，PP.1403 - 1416.

[19]Fu Z.，Sun X.，etc（2015）.Achieving Efficient Cloud S earch Services:Multi-Keyword Ranked Search over Encrypted Cl oud Data Supporting Parallel Computing[J].IEICE Transactions o n Communications.Vol.98，PP.190-200.

[20]Gu B.,Victor S.Sheng,etc.(2015).Incremental learning fo r ν-Support Vector Regression[J].Neural Networks.Vol.67，PP.14 0–150.

[21]Wen X.,Shao L.,etc.(2015).A rapid learning algorithm fo r vehicle classification[J].Information Sciences.Vol.295,PP.395–40 6.

國家自然科學(xué)基金（61363071）; 湖南省教育科學(xué)十二規(guī)劃課題資助項(xiàng)目（XJK011BXJ004）; 海南大學(xué)博士啟動(dòng)基金（kyqd1328）; 海南大學(xué)青年基金（qnjj14444）; 海南省自然科學(xué)基金（20166217）; 海南大學(xué)研究生實(shí)踐創(chuàng)新項(xiàng)目。