基于Apriori算法的安全事件二級關聯方法

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

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

基于Apriori算法的安全事件二級關聯方法

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

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

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

網絡安全; Apriori算法; 關聯方法

0 前言

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

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

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

1 基于Apriori算法的安全事件二級關聯方法

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

1.1 因果關聯模型

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

設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在安全事件數據庫D中的支持度（Support）是安全事件集中包含X和Y的事件數與所有事件數之比，可信度（reliability）是包含X和Y的事件數與包含X的事件數之比。

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

1.2 關聯規則模型

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

圖1 Apriori算法

2 安全事件二級關聯方法

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

圖2 基于Apriori算法的安全事件二級關聯方法

3 測試與分析

3.1 測試環境和工具

測試環境硬件列表見表1，測試軟件環境見表2。

表1 測試硬件列表

表2 測試軟件列表

3.2 測試結果及分析

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

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

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

圖3 測試界面截圖

圖4 安全事件關聯分析效率

圖5 安全事件關聯規則數量比較

4 結束語

本章對網絡安全事件關聯進行了需求分析，將網絡安全事件關聯劃分為4個子模塊，對各個子模塊進行了詳細設計。采用基于因果關聯方法的聚類對安全事件進行歸并，將安全告警事件劃分為具有邏輯因果關系的集合，然后利用基于Apriori算法的關聯規則挖掘方法挖掘出各個安全告警事件集合之間的內在關聯關系，實現了對于告警數據進行事件關聯的模塊功能，較好地提高了對組合攻擊的關聯效率。不足之處是需要進一步優化Apriori算法，解決Apriori算法處理大規模數據庫效率不高的問題。

[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]李芝棠.網絡安全態勢關聯分析.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]熊云燕，毛宜君.安全事件關聯分析引擎的研究與實現.計算機工程，2006.

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

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

[11]徐勇等.基于XML數據的關聯規則挖掘.計算機工程與設計，2006.

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

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

[14]彭雪娜，聞英友.網絡安全信息關聯與分析技術的研究進展.計算機工程，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）; 湖南省教育科學十二規劃課題資助項目（XJK011BXJ004）; 海南大學博士啟動基金（kyqd1328）; 海南大學青年基金（qnjj14444）; 海南省自然科學基金（20166217）; 海南大學研究生實踐創新項目。