基于有向滑動時間窗的報警動態選擇算法

汪永偉，蘇會芳，張紅旗，劉育楠，邱 衛

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

0 引 言

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

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

1 基于有向滑動時間窗的報警動態選擇算法

1.1 基本思想

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

因此，受經典計算機網絡中擁塞窗口管理機制的啟發，本文提出了一種基于有向滑動時間窗的報警動態選擇算法ADSA＿DSTW。ADSA＿DSTW 算法依據歷史關聯結果的趨向特征，調整每個時間窗內報警抽取的概率，向歷史關聯強度高的時間窗分配更高的抽取概率，降低歷史關聯強度較低的時間窗的抽取概率，從而提高報警關聯的效率和準確性。

1.2 初始報警選擇

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

發生越久的報警與新報警發生關聯的概率越小，因此，在報警選擇上，可為其分配較低的抽取概率。

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

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

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

圖1 初始報警選擇

1.3 ADSA＿DSTW 報警動態選擇算法

假設，Comax表示新報警Anew與時間窗Ti內已有報警關聯過程中關聯強度的最大值。Seaverage是歷史上的報警關聯強度均值。時間窗的報警抽取概率通過調節報警選擇數量來實現，調整過程中的兩個閾值分別為：最小報警選擇調整閾值SeThreshmin和最大報警選擇調整閾值SeThreshmax

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

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

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

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

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

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

算法1基于有向滑動時間窗的報警動態選擇算法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＋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）行完成初始參數和初始報警選擇數量設置。第 （8）－（12）行記錄報警關聯過程中的最大關聯強度。第 （14）－（20）依據歷史報警關聯強度對報警選擇數量進行動態調整。

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

2 實驗仿真與分析

2.1 實驗方法

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

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

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

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

2.2 實驗結果

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

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

2.3 實驗分析

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

圖4 時間窗大小對關聯精度的影響

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

圖3是不同時間窗大小情況下的運行時間對比。可以看出，時間窗的大小對報警關聯的執行時間有一定影響，時間窗變大時，運行時間相應變長。這是因為，窗口變大時，每個窗口中的報警數量增加，初始報警選擇數量分配時的基數變大，相應的，通過報警選擇算法從每個時間窗內平均選擇的報警數量增多，可以想象，當報警窗口擴大到整個歷史區間時，初始的報警選擇數就是所有報警的數量，因此，窗口的擴大會導致整個關聯執行時間的增加。

圖4是不同時間窗大小情況下的有效率和完備率對比。可以看出，時間窗的大小對報警關聯的精度有一定影響，時間窗減小時，關聯完備率相應降低。這是因為，窗口減小時，每個窗口中的報警數量減少，初始報警選擇數量分配時的基數變小，相應的，通過報警選擇算法從每個時間窗內平均選擇的報警數量減少，報警選擇數量的減少必然會漏掉可能的報警關聯對。因此，窗口的減小會導致關聯完備率的下降。因此，在實際運行過程中，通過調節窗口大小，可適應對不同實時性和精度要求的應用場景。對于一些對實時性要求較高的關聯分析場景，可以選擇相對較小的時間窗，以提高關聯效率；而對精度要求較高的關聯分析場景，則可以選擇較大的時間窗，以提高關聯精度。

3 結束語

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

［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.