基于有向滑動時間窗的報警動態(tài)選擇算法

汪永偉，蘇會芳，張紅旗，劉育楠，邱 衛(wèi)

（1.信息工程大學(xué)，河南 鄭州450004；2.河南省信息安全重點實驗室，河南 鄭州450004；3.河南省外貿(mào)學(xué)校，河南 鄭州450002）

0 引 言

報警關(guān)聯(lián)分析可以在相關(guān)的報警信息之間建立關(guān)聯(lián)，消除冗余報警，能夠有效降低系統(tǒng)中的報警數(shù)量，提高網(wǎng)絡(luò)安全狀態(tài)分析的效率和準確性［1－3］。新報警來臨時，需要從已有報警中選擇一個或一組報警與之建立關(guān)聯(lián)。在現(xiàn)有關(guān)聯(lián)分析方法中，報警選擇主要采用兩種方法：第一種方法是，選擇所有的已有報警與新報警建立關(guān)聯(lián)［4－6］；另外一種方法是，將最近的關(guān)聯(lián)報警劃分為若干時間窗，從時間窗中隨機選擇報警與新報警建立關(guān)聯(lián)［7］。第一種方法實現(xiàn)較為簡單，關(guān)聯(lián)結(jié)果最為精確，但是計算資源消耗巨大，關(guān)聯(lián)方法的實時性受到影響，不適于實時在線態(tài)勢分析［8］；相對于第一種方法，第二種方法在性能上有所提升，但是由于報警選擇的無目的性，一定程度上會降低關(guān)聯(lián)分析的準確性。

針對上述問題，本文提出了一種基于有向滑動時間窗的報警動態(tài)選擇算法ADSA＿DSTW （alert dynamic selection algorithm based on direct slide time window）。該算法依據(jù)歷史關(guān)聯(lián)結(jié)果的趨向特征，調(diào)整每個時間窗內(nèi)報警抽取的概率，向歷史關(guān)聯(lián)強度高的時間窗分配更高的抽取概率，以提高報警關(guān)聯(lián)的實時性和準確性。

1 基于有向滑動時間窗的報警動態(tài)選擇算法

1.1 基本思想

新報警來臨時，報警選擇策略決定了已關(guān)聯(lián)報警的抽取原則。報警全選方法雖然精準，但是資源消耗巨大；隨機選擇方法雖然性能優(yōu)異，但是精確度下降。在采用報警隨機選擇方法時，按照時間窗的新鮮度，從每個時間窗內(nèi)隨機抽取報警建立關(guān)聯(lián)對，在整個關(guān)聯(lián)過程中，某一時間窗所獲得的抽取概率始終完全相同［7］。隨機選擇方法考慮了窗口新鮮度因素，相對比較合理，但是，其沒有考慮關(guān)聯(lián)歷史因素。在關(guān)聯(lián)過程中，時間窗內(nèi)的歷史關(guān)聯(lián)強度會對新的報警關(guān)聯(lián)帶來有益的啟示：由于關(guān)聯(lián)報警在時間上具有聚集性，歷史關(guān)聯(lián)強度更高的時間窗與新報警發(fā)生關(guān)聯(lián)的概率更大，歷史關(guān)聯(lián)強度低的時間窗與新報警關(guān)聯(lián)的可能性較小。這一特征與計算機網(wǎng)絡(luò)中的擁塞管理機制類似：在經(jīng)典的網(wǎng)絡(luò)管理中，當丟包狀況提示網(wǎng)絡(luò)發(fā)生擁塞時，擁塞控制算法會降低窗口大小，減少數(shù)據(jù)包發(fā)送規(guī)模；當網(wǎng)絡(luò)狀態(tài)良好時，增加窗口大小，擁塞控制算法擴大數(shù)據(jù)包發(fā)送規(guī)模。

因此，受經(jīng)典計算機網(wǎng)絡(luò)中擁塞窗口管理機制的啟發(fā)，本文提出了一種基于有向滑動時間窗的報警動態(tài)選擇算法ADSA＿DSTW。ADSA＿DSTW 算法依據(jù)歷史關(guān)聯(lián)結(jié)果的趨向特征，調(diào)整每個時間窗內(nèi)報警抽取的概率，向歷史關(guān)聯(lián)強度高的時間窗分配更高的抽取概率，降低歷史關(guān)聯(lián)強度較低的時間窗的抽取概率，從而提高報警關(guān)聯(lián)的效率和準確性。

1.2 初始報警選擇

假設(shè)，將時間劃分為n個等間隔的時間窗，每個時間窗的序號從1到n。按照報警產(chǎn)生的順序，將每個報警分配到對應(yīng)的時間窗內(nèi)，其所隸屬的時間窗序號通過式 （1）獲得

發(fā)生越久的報警與新報警發(fā)生關(guān)聯(lián)的概率越小，因此，在報警選擇上，可為其分配較低的抽取概率。

假設(shè)，序號為i的時間窗內(nèi)的報警數(shù)量為si，窗口報警抽取概率為ρ，報警選擇數(shù)位select＿numi，則，在初始狀態(tài)下，時間窗的抽取概率和從其中可選擇的報警數(shù)量為

由式 （1）可以看出，報警產(chǎn)生越久，其所屬時間窗的序號越大，根據(jù)式 （2）計算的抽取概率越小，進而由式（3）所分配的告警選擇數(shù)越小。

例如，圖1所示的時間窗中，時間窗的序號由左到右依次為。依據(jù)式 （2）、式 （3），從每個窗口中選擇的報警數(shù)量分別為3，5，9，8和12。每個窗口對應(yīng)的抽取概率分別為18.7%，35.7%，60%，72.7%，100%，越新鮮的時間窗被分配的抽取概率越大。

圖1 初始報警選擇

1.3 ADSA＿DSTW 報警動態(tài)選擇算法

假設(shè)，Comax表示新報警Anew與時間窗Ti內(nèi)已有報警關(guān)聯(lián)過程中關(guān)聯(lián)強度的最大值。Seaverage是歷史上的報警關(guān)聯(lián)強度均值。時間窗的報警抽取概率通過調(diào)節(jié)報警選擇數(shù)量來實現(xiàn)，調(diào)整過程中的兩個閾值分別為：最小報警選擇調(diào)整閾值SeThreshmin和最大報警選擇調(diào)整閾值SeThreshmax

其中，α為調(diào)節(jié)參數(shù)，用于調(diào)節(jié)報警選擇數(shù)量的變化速度，取值范圍 ［0.5，1.0］。α值較大時，時間窗內(nèi)報警選擇數(shù)量的調(diào)整速率較快；α值較小時，時間窗內(nèi)報警選擇數(shù)量的調(diào)整速率較慢。為了保證報警選擇調(diào)節(jié)的有效性，α的選擇需保證SeThreshmax＜CoT 。

由前面的分析可知，歷史關(guān)聯(lián)強度更高的時間窗與新報警發(fā)生關(guān)聯(lián)的概率更大，歷史關(guān)聯(lián)強度低的時間窗與新報警關(guān)聯(lián)的可能性較小。本文將新報警與時間窗內(nèi)報警關(guān)聯(lián)的可能性定義為關(guān)聯(lián)興趣度CI（correlation interest）。

定義1 關(guān)聯(lián)興趣度由本次報警關(guān)聯(lián)過程中的最大值Comax與SeThreshmax、SeThreshmin之間的關(guān)系決定，其計算方法如下

ADSA＿DSTW 算法的工作原理為：

首先，利用式 （2）和式 （4）計算每個時間窗的初始select＿numi。然后，在新報警Anew與時間窗Ti內(nèi)報警的關(guān)聯(lián)過程中，不斷更新最大關(guān)聯(lián)強度Comax。當時間窗Ti內(nèi)檢測過的報警數(shù)量超過select＿numi／2時，檢驗Comax與調(diào)整閾值之間的關(guān)系。若Comax小于SeThreshmin，說明Anew與時間窗Ti內(nèi)報警發(fā)生關(guān)聯(lián)的興趣度較小，則減小該時間窗的報警選擇數(shù)量，將select＿numi減小CI；若Comax大于SeThreshmax，說明Anew與時間窗Ti內(nèi)報警發(fā)生關(guān)聯(lián)的興趣度較大，則增大該時間窗的報警選擇數(shù)量，將select＿numi增加CI。

算法1給出了基于有向滑動時間窗的報警動態(tài)選擇算法的偽碼描述。

算法1基于有向滑動時間窗的報警動態(tài)選擇算法ADSA＿DSTW輸入：Alertnew，Rules輸出：SelectedAlerts（1） BEGIN（2） n＝SetTWcount（）；（3） For i＝1：n（4） selectNum ［i］＝si＊（1－i－1）n（5） j＝0；／／（6） Comax ＝－1；（7） While（j＜selectNum ［i］）＆＆ （j＜si）（8） a＝randSelect（）；（9） Ctemp＝caculateCorrelation （Alertnew，a）；（10） If（Ctemp＞Comax ）（11） Comax ＝Ctemp；（12） End if（13） j＝j(luò)＋1；（14） If （j ＞ selectNum［i］2 ） ＆＆ （Comax＜SeThreshmin ）（15） selectNum ［i］ ＝selectNum ［i］－SeThreshmin／Co max ；（16） End if（17） If（j＝＝selectNum ［i］）＆＆ （Comax ＞SeThreshmax ）＆＆ （j＜si）（18） selectNum ［i］ ＝selectNum ［i］ ＋Comax／SeThresh max ；（19） Comax ＝0；（20） End if（21） End while（22） End for（23） End

其中，第 （2）－（6）行完成初始參數(shù)和初始報警選擇數(shù)量設(shè)置。第 （8）－（12）行記錄報警關(guān)聯(lián)過程中的最大關(guān)聯(lián)強度。第 （14）－（20）依據(jù)歷史報警關(guān)聯(lián)強度對報警選擇數(shù)量進行動態(tài)調(diào)整。

通過ADSA＿DSTW 的動態(tài)調(diào)整策略，歷史關(guān)聯(lián)強度較高的時間窗所分配的select＿numi逐漸變大，相應(yīng)的報警抽取概率會逐漸提高。在時間窗內(nèi)報警數(shù)量較多的情況下，歷史關(guān)聯(lián)強度高、關(guān)聯(lián)趨向特征明顯的時間窗所分配的報警選擇數(shù)增加的也更快，而歷史關(guān)聯(lián)強度低、不相關(guān)趨向特征明顯的時間窗所分配的報警選擇數(shù)的下降則會迅速下降，從而使報警的選擇過程更具目的性，提高報警關(guān)聯(lián)的效率和準確性。

2 實驗仿真與分析

2.1 實驗方法

為了驗證本文提出的報警選擇算法對關(guān)聯(lián)分析性能的作用，本文在文獻 ［9］所提出的關(guān)聯(lián)分析方法的基礎(chǔ)上加載了ADSA＿DSTW 算法，在LLDOS1.0數(shù)據(jù)集上分別測試了報警全選、隨機選擇和本文的ADSA＿DSTW 對報警關(guān)聯(lián)執(zhí)行時間的影響。實驗數(shù)據(jù)共分為8組，每組實驗輸入的報警數(shù)分別為120、225、350、450、600、700、800、900，時間窗個數(shù)n＝10。為了測試時間窗大小對執(zhí)行時間的影響，分別測試了8組報警數(shù)據(jù)在時間窗大小Wwidth＝100s、Wwidth＝200s和Wwidth＝300s的運行結(jié)果。

在實驗中，為了測試報警選擇算法對關(guān)聯(lián)精度的影響，在測試結(jié)果對比分析過程中，采用文獻 ［10］提出的關(guān)聯(lián)分析結(jié)果評價指標：完備率CR （completeness rate）和有效率SR （soundness rate）。

定義2 完備率［10］：該指標用于評價關(guān)聯(lián)方法的對關(guān)聯(lián)報警的發(fā)掘能力，是正確關(guān)聯(lián)的報警數(shù)與實際相關(guān)報警數(shù)的比率，計算方法如式 （7）所示

定義3 有效率［10］：該指標用于評價關(guān)聯(lián)方法的正確性，是正確關(guān)聯(lián)的報警數(shù)與已建關(guān)聯(lián)總數(shù)的比率，計算方法如式 （8）所示

2.2 實驗結(jié)果

圖2給出了不同報警選擇方法在Wwidth＝100s情況下的運行時間對比。圖3給出了報警動態(tài)選擇算法在Wwidth＝100s、Wwidth＝200s和Wwidth＝300s情況下的運行時間對比。圖4給出了報警動態(tài)選擇算法在不同時間窗下的精度對比。

圖2 報警選擇實驗結(jié)果 （窗口100s）

2.3 實驗分析

圖3 時間窗大小對運行時間的影響

圖4 時間窗大小對關(guān)聯(lián)精度的影響

由圖2可以看出，報警全選方法的執(zhí)行時間幾乎呈指數(shù)曲線變化，而隨機選擇算法和ADSA＿DSTW 算法的執(zhí)行時間明顯要低于報警全選的執(zhí)行時間。當輸入報警的數(shù)量較少時，隨機選擇算法和ADSA＿DSTW 算法的執(zhí)行時間差別不大，隨著報警集中報警數(shù)量的增加，兩者在執(zhí)行時間上的差異逐漸擴大，當報警數(shù)量達到900時，ADSA＿DSTW 算法的測試組在執(zhí)行時間上比隨機選擇算法的測試組降低了13.93%，比全選測試組降低了63.41%。這是因為，當時間窗內(nèi)報警數(shù)量較多時，ADSA＿DSTW 算法能夠基于歷史關(guān)聯(lián)概率對窗口內(nèi)的報警選擇次數(shù)進行調(diào)整，將抽取概率快速傾斜向于歷史關(guān)聯(lián)強度高的時間窗，減少了新報警與無關(guān)窗口中報警的關(guān)聯(lián)運算次數(shù)，從而降低了整體報警關(guān)聯(lián)執(zhí)行過程的運行時間。

圖3是不同時間窗大小情況下的運行時間對比?？梢钥闯觯瑫r間窗的大小對報警關(guān)聯(lián)的執(zhí)行時間有一定影響，時間窗變大時，運行時間相應(yīng)變長。這是因為，窗口變大時，每個窗口中的報警數(shù)量增加，初始報警選擇數(shù)量分配時的基數(shù)變大，相應(yīng)的，通過報警選擇算法從每個時間窗內(nèi)平均選擇的報警數(shù)量增多，可以想象，當報警窗口擴大到整個歷史區(qū)間時，初始的報警選擇數(shù)就是所有報警的數(shù)量，因此，窗口的擴大會導(dǎo)致整個關(guān)聯(lián)執(zhí)行時間的增加。

圖4是不同時間窗大小情況下的有效率和完備率對比?？梢钥闯觯瑫r間窗的大小對報警關(guān)聯(lián)的精度有一定影響，時間窗減小時，關(guān)聯(lián)完備率相應(yīng)降低。這是因為，窗口減小時，每個窗口中的報警數(shù)量減少，初始報警選擇數(shù)量分配時的基數(shù)變小，相應(yīng)的，通過報警選擇算法從每個時間窗內(nèi)平均選擇的報警數(shù)量減少，報警選擇數(shù)量的減少必然會漏掉可能的報警關(guān)聯(lián)對。因此，窗口的減小會導(dǎo)致關(guān)聯(lián)完備率的下降。因此，在實際運行過程中，通過調(diào)節(jié)窗口大小，可適應(yīng)對不同實時性和精度要求的應(yīng)用場景。對于一些對實時性要求較高的關(guān)聯(lián)分析場景，可以選擇相對較小的時間窗，以提高關(guān)聯(lián)效率；而對精度要求較高的關(guān)聯(lián)分析場景，則可以選擇較大的時間窗，以提高關(guān)聯(lián)精度。

3 結(jié)束語

針對現(xiàn)有報警選擇方法在實時性和精確性方面存在的不足，本文提出了一種基于有向滑動時間窗的報警動態(tài)選擇算法。該算法依據(jù)歷史關(guān)聯(lián)結(jié)果的趨向特征，調(diào)整每個時間窗內(nèi)報警抽取的概率，向歷史關(guān)聯(lián)強度高的時間窗分配更高的抽取概率，降低歷史關(guān)聯(lián)強度較低的時間窗的抽取概率，從而提高報警關(guān)聯(lián)的效率和準確性。仿真結(jié)果表明，ADSA＿DSTW 算法的運行時間隨著時間窗的減小而減小，在運行時間上遠低于報警全選方法和隨機選擇方法；ADSA＿DSTW 算法的完備率受時間窗大小的影響較大，隨著窗口的增大而增大，而有效率則保持相對穩(wěn)定。通過窗口大小調(diào)節(jié)，ADSA＿DSTW 算法與報警關(guān)聯(lián)分析方法相結(jié)合可適應(yīng)對不同實時性和精度要求的應(yīng)用場景。

［1］Peng L，Chen W，Xie D，et al.Dynamically real－time anomaly detection algorithm with immune negative selection ［J］.Appl Math，2013，7 （3）：1157－1163.

［2］Chen S.Optimized multilevel immune learning algorithm in abnormal detection ［J］.Information Technology Journal，2013，12 （3）：514－517.

［3］Suarez－Tangil G，Palomar E，Pastrana S，et al.Artificial immunity－based correlation system ［C］／／SECRYPT，2011：422－425.

［4］LIU J，LI Y，MENG J，et al.Intrusion detection system alerts fusion based on fuzzy comprehensive evaluation and immune evolution ［J］.Journal of Computational Information Systems，2013，9 （4）：1509－1516.

［5］Kabiri P，Ghorbani A.A rule－based temporal alert correlation system ［J］.International Journal of Network Security，2007，5 （1）：66－72.

［6］Ren H，Stakhanova N，Ghorbani A.An online adaptive approach to alert correlation ［M］.Detection of Intrusions and Malware，and Vulnerability Assessment，Springer Berlin Heidelberg，2010：153－172.

［7］Ahmadinejad H，Jalili S.Alert correlation using correlation probability estimation and time windows［C］／／Proceedings of the International Conference on Computer Technology and Development，IEEE，2009：170－175.

［8］Bateni M，Baraani A.Time window management for alert correlation using context information and classification ［J］.International Journal of Computer Network ＆Information Security，2013，5 （11）：9－16.

［9］Bateni M，Baraani A，Ghorbani A A.Using artificial immune system and fuzzy logic for alert correlation ［J］.Int J Netw Secur，2013，15 （1）：160－174..

［10］Elshoush H T，Osman I M.Alert correlation in collaborative intelligent intrusion detection systems－a survey ［J］.Applied Soft Computing，2011，11 （7）：4349－4365.