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

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

（海南大學信息科學技術學院 海南 571101）

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

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

（海南大學信息科學技術學院 海南 571101）

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

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

0 前言

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

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

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

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

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

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

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

設I={Ia，…，Im }是項集，其中的元素稱為項（item）。記D為安全事件S的集合，這里安全事件S是項的集合，并且S∈I。對應每一個安全事件有唯的標識，記作E。設X是一個I中項的集合，如果X∈S，那么稱安全事件S包含X。

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

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

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

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

圖1 Apriori算法

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

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

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

3 測試與分析

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

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

表1 測試硬件列表

表2 測試軟件列表

3.2 測試結果及分析

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

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

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

圖3 測試界面截圖

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

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

4 結束語

本章對網(wǎng)絡安全事件關聯(lián)進行了需求分析，將網(wǎng)絡安全事件關聯(lián)劃分為4個子模塊，對各個子模塊進行了詳細設計。采用基于因果關聯(lián)方法的聚類對安全事件進行歸并，將安全告警事件劃分為具有邏輯因果關系的集合，然后利用基于Apriori算法的關聯(lián)規(guī)則挖掘方法挖掘出各個安全告警事件集合之間的內在關聯(lián)關系，實現(xiàn)了對于告警數(shù)據(jù)進行事件關聯(lián)的模塊功能，較好地提高了對組合攻擊的關聯(liá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)絡安全態(tài)勢關聯(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]熊云燕，毛宜君.安全事件關聯(lián)分析引擎的研究與實現(xiàn).計算機工程，2006.

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

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

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

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

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

[14]彭雪娜，聞英友.網(wǎng)絡安全信息關聯(lián)與分析技術的研究進展.計算機工程，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.

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