蠕蟲正則表達式特征自動提取技術研究

2013-10-29 08:25:04唐勇諸葛建偉陳曙暉盧錫城

通信學報 2013年3期

唐勇，諸葛建偉，陳曙暉，盧錫城

(1. 國防科技大學計算機學院，湖南長沙 410073；2. 清華大學信息網絡工程研究中心, 北京 100084)

1 引言

準確有效的特征是檢測和防范網絡蠕蟲傳播的關鍵，當前，蠕蟲傳播特征主要是依靠安全專家進行人工提取，過程復雜、速度慢，且由于變形技術[1,2]在蠕蟲中的普遍應用，準確性也無法得到保證。近年來，一些蠕蟲傳播特征自動提取方法被相繼提出，這些方法通過分析蠕蟲傳播數據（可能包括噪聲）自動生成蠕蟲傳播特征，它們可被劃分為下列類別[3]：基于 LCS（longest common substring)[4~6]、基于固定長度負載出現頻率[7,8]、基于可變長度負載出現頻率[9,10]、基于有限狀態自動機[11]、基于序列比對[12~14]等。基于序列比對的方法[12~14]在準確性上要優于其他方法，但是也只能輸出僅包含“.*”和“.{k}”這兩類元字符的簡單正則表達式特征，例如，對 CodeRed 蠕蟲產生的“‘GET /’.*‘.ida?’ *‘XX’*‘%u’.{4}‘%u780’*‘=’.{7}‘HTTP /1.0 ’”特征。如何自動提取具有更豐富語義（即包含更多類型元字符）的完整正則表達式特征是一個挑戰性問題。

本文提出一種蠕蟲傳播復雜正則表達式特征自動提取方法。相比現有方法，該方法輸出的正則表達式特征包含“.*”、“.{k}”、“|”、“(c){k}”等元字符，分別表示“匹配任意長度字符串”、“k個任意字符”、“或關系”、“k個字符c”，具有更準確的特征描述能力，從而能夠更加精確地刻畫網絡蠕蟲特征，降低蠕蟲檢測的誤報率和漏報率。

2 變形蠕蟲正則表達式特征自動提取方法

2.1 方法概述

本文提出的變形蠕蟲正則表達式特征自動提取方法的步驟如圖1所示，共分4步。第1步為蠕蟲傳播網絡流樣本獲取，利用 HoneyBow（蜜罐系統）[15]中已捕獲的蠕蟲二進制樣本，在蜜網環境中生成并獲取蠕蟲傳播的網絡流樣本；第2步為特征樹生成，通過多序列比對算法生成蠕蟲網絡流樣本的一組簡單正則表達式特征，并動態組織成特征樹；第3步為高假陽性特征剔除，將特征樹中可能引起大量誤報的特征剔除，輸出最小覆蓋特征集；第4步為特征融合，將最小覆蓋特征集融合為一個或多個復雜正則表達式特征，該特征可用于精確的蠕蟲檢測。以上4步將在2.2節~2.5節分別進行介紹。

2.2 蠕蟲傳播網絡流獲取

本文使用基于高交互式蜜罐技術的惡意代碼自動捕獲器HoneyBow[15]來進行蠕蟲樣本的捕獲。HoneyBow利用真實的存有安全漏洞的服務來誘騙蠕蟲感染，待蠕蟲感染虛擬機后將之捕獲并記錄下該蠕蟲樣本的外連數據流。對于選定的一個蠕蟲樣本，HoneyBow可利用殺毒軟件對該樣本進行分析，如果殺毒軟件未能識別則就可能為未知蠕蟲樣本。此時，將該蠕蟲樣本的外連數據流預處理為網絡流樣本，交由特征生成算法的后續步驟進行處理。

2.3 特征樹生成

2.3.1 SRE特征及特征提取算法

給定某個蠕蟲的一組網絡流樣本，本文采用文獻[14]所提出的基于多序列比對的特征提取方法，生成“簡化正則表達式特征”——SRE（simplified regular expression）特征[13]。SRE特征只包含2種正則表達式元字符，分別為“.*”和“.{k}”，“.*”表示任意（包括零）長度的字符串；“.{k}”表示由k個字符組成的字符串。例如，“one.{2}two.*”是一個SRE特征。

本文將文獻[12, 13]提出的基于多序列比對的特征提取方法抽象為函數 M Align( )，其輸入為字符串或SRE特征的集合，輸出為一個SRE特征。例如, M Align("oxnxexzxtwoxxw","ytwoyownyeyz","cvcvcvtwovcwc")=“.*‘two’.{2}‘w’.*”; M Align("'abc'.{2}'d ' ","'a b ' .*'d ' ") = “ ‘ab’.*‘d’”。

2.3.2 特征樹定義

文獻[14]形式化定義了SRE特征的“包含關系”和“更精確關系?”，使得2個SRE特征可以比較：XY?稱為“Y包含X”，意義是能夠匹配特征X的字符串都能夠匹配特征Y；XY?稱為“X比Y更精確”，意義是能夠匹配特征X的字符串都能夠匹配特征Y，并且特征X的“長度更長”[14]（可理解為包含更多信息）。例如，“‘abc’.*‘cd’”? “‘ab’.*‘cd’”, “‘ab’.{2} ‘cd’”? “‘ab’.* ‘cd’”; “‘aaa’. *‘b’”?“‘aa’.*‘b’”, “‘aa’.{2}‘b’”? “‘aa’.*‘b’”。

定義1 特征樹（signature tree）是一個有根樹，其中每個節點都是一個網絡數據流（樣本）的集合，并且被賦予了一個SRE特征，并用x.sig表示節點x被賦予的特征。特征樹中，根節點被賦予最泛化的特征“*”，每條邊都表示“更精確關系?”。特征樹必須滿足下面2個性質：

1) 任何一個樣本f∈節點C，則f?C. sig；

2) 節點 C1是節點 C2的子節點，則 C1. sig?C2. sig。

特征樹是本文方法的重要中間結果，表示了一組簡單正則表達式（SRE[14]）的邏輯關系，是后續步驟生成復雜正則表達式的基礎。圖2右側給出了特征樹的一個例子。

圖1 方法主要流程

圖2 生成一組樣本的特征樹

2.3.3 特征樹生成算法

特征樹生成算法是本文方法的核心，如算法 1所示。該算法是一個增量式算法，其基本思想是：初始時刻，特征樹中只包含一個根節點，該根節點被賦予最泛化的特征“*”；然后逐個選擇樣本調用SigTreeUpdate過程對特征樹進行更新；SigTreeUpdate函數主要由樣本聚類、新特征提取和特征樹更新調整3個步驟組成。圖2說明從左側的11個樣本，特征樹生成算法如何產生右側的特征樹，其中，iC表示第i個生成的節點。

分析算法 1可知越精確的特征總是處在越深（層數越大）的層中。同時，加入到特征樹中的樣本總是會“沉”到所在層數最大的節點中。因此，對于變形蠕蟲的w，在由算法1生成的特征樹中，同一層中只可能有一個節點（該節點的特征是w的特征之一）含有w的樣本，即變形蠕蟲w可被聚類，并可提取特征。若樣本集包含來自t個攻擊的K個樣本，每個樣本的平均長度為l，則算法的時間開銷為 O ( K tθl2)。

算法1 SigTreeGeneration(S)

輸入：樣本集S；

輸出：特征樹STree；

生成一個只包含根節點（節點特征“*”）的新特征樹STree；

do 從S中隨機取出一個樣本f，SigTreeUpdate(f,STree)

untilS為空

輸出STree

Procedure SinkSamples(TC,STree)

在STree中，將所有滿足下列3個條件的樣本f移動到TC：

f∈C，C. level = CT. level- 1 ，并且 f ?CT. sig

Procedure MoveSubtree(CS,CT,STree)

在STree中，將以 CS為根的子樹移動到 CT（ CS成為 CT的子節點）；

對以 CS為根的子樹中的每一個節點C′調用SinkSamples(C′,STree)

Procedure SigTreeUpdate(f,STree)

//步驟1 樣本聚類

按照下面的順序查找滿足 f ? Cbelong.sig的節點 Cbelong：層次從高到低；如果在最高的某一層中有多個節點滿足條件，則選擇加入該層最早的那一個節點；

Cbelong← Cbelong∪ { f } //將f加入節點 Cbelong

//步驟2 新特征提取

if Cbelong包含一個子集 Cnew={f1, f2, … , fθ-1,f }滿足 M Align( Cnew) ? Cbelong.sig ，then

//產生新節點

Cbelong←CbelongCnew；

將 Cnew增加到攻擊特征樹中成為 Cbelong的子節點；//從 Cbelong分裂出一個新的節點 Cnew

Cnew.sig← M Align( Cnew)；

SinkSamples(Cnew)；

//步驟3 特征樹更新調整

對于所有滿足 C ≠Cnew，C .le vel = Cnew.level并且C. s i g ? Cnew.sig 的節點C，do

MoveSubtree(C,Cnew);

// 移動C使之成為 Cnew的子節點

ifC是 Cbelong的子節點，并且 A lign( C. s i g,Cnew.sig)? Cbelong.sig , then

產生一個新的節點 Cparent={}作為 Cbelong的子節點；

Cparent.sig ← A lign( Cnew.s i g, C. s i g);

MoveSubtree(Cnew,Cparent) ;

MoveSubtree(C,Cparent);

// 讓 Cnew和C成為 Cparent的子節點

SinkSamples(Cparent) ;

2.4 高假陽性特征剔除

高假陽性特征剔除算法見算法 2，其作用是通過不含攻擊的數據流庫N去除可能引起大量誤報的特征，最后輸出一個最小覆蓋特征集合。算法從根節點開始遍歷特征樹，如果一個節點特征能夠滿足誤報率要求，則用它代替其子節點。

算法2 SigRemove(STree)

輸入：特征樹STree；

輸出：特征集合S；

對于每一個節點C∈STree，通過正常數據流庫N計算誤報率 CFP；

2.5 特征規約

特征規約的作用是等價合并特征，輸出描述能力更強數量更少的特征。特征規約算法見算法 3，定理1證明了該算法的正確性。算法通過5條規則進行規約，其中，第1~3條規則引入或關系元字符（“|”），第 4條規則對冗余或關系進行規約，第 5條規則引入元字符“(c){k}”。

算法3 SigMerge(S)

輸入：特征集合S

輸出：規約后的特征集合

/*以下X、 X1、Y2表示SRE特征，A、A1、A2、A3表示字符串，表示字符串的k次連接*/

whileS中存在特征能夠滿足下列5條規則之一,do

if X = X1A, Y = Y1A, then X ' =(X1|Y1) A ,S ←S / { X , Y },S ← S ∪ { X '}; continue; //規則1

if X = AX1, Y = AY1, then X ' = A( X1|Y1),S ←S /{ X , Y },S ← S ∪ { X '}; continue; //規則2

if X = A1X1A2,Y = A1Y2A2, then X ' = A1( X1|Y1)A2,S ←S / { X , Y },S ← S ∪ { X '}; continue; //規則3

if X =(X | Y) AandX?Y, thenX'=YA,S←S/{X}, S ← S ∪ { X'}; continue; //規則4

if X=X1A或 X=AX1或 X = X1AX2,且

X'=(A1){k}，S←S/{X},S ←S ∪ { X'};;

//規則5

end

輸出S

定理 1 特征集合S經過特征規約算法后得到S',S'與S等價。

證明 S '與S等價意思是任何可匹配S中某一條規則的樣本必然也可匹配 S '中的某一條規則，反之亦然。顯然，只需要證明通過規則1~5規約后，規約后的特征 X ' 與原特征X或{X, Y } 等價（ L ( X ' )=L( Y)或 L ( X')=L( X) ∪ L( Y)）即可。

1) 對于規則 1，如果樣本 x ∈L( X)，則x=x1A,x1∈L( X1)。由x1∈L( X1)可知x1∈L( X1)∪L( Y1) = L ( X1|Y )成立，，所以 x1A ∈ L(( X1|Y1) A)，即x∈L( X ')。同理，如果x∈L( Y)也可證x∈L( X')。反之，如果樣本 x ∈L( X ')，則必然存在x = x1x2使得 x1∈ L ( X1|Y1)且 x2∈L( A)。由x1∈ L ( X1|Y1)可知x1∈L( X1)成立或x1∈L( Y1)成立。若是x1∈L( X1)成立且 x2∈L( A)，可得到x∈L( X)；若是x1∈L( Y1)成立且x2?A，得到x∈L( Y)。因此，如果樣本x∈L( X ')，則x ∈ L ( X ) ∪ L ( Y)。綜上， L ( X')=L( X)∪ L( Y)。

2) 規則2、規則3的證明過程與1）類似。

3) 對于規則4，如果樣本 x ∈L( X)，則x = x1A使得x1∈ L ( X | Y ) = L ( X ) ∪ L ( Y)。如果 x1∈L( X)，由 X ∈L( Y)可得到x1∈L( Y)，x = x1A ∈ L ( YA)；如果 x1∈L( Y)顯然x∈L( YA)。反之，如果x∈L( X')，則x= x1A且x1∈L( Y)，此時顯然x ∈ L(( X| Y) A)= L( X ')成立。綜上， L ( X ' )=L( X)成立。

由上述證明過程，可知通過規則1~規則5進行規約后，S保持等價。

圖3 本方法提取Virut.n蠕蟲傳播特征

3 實驗

3.1 實驗方法

現有方法研究主要通過人工生成的模擬蠕蟲樣本進行實驗。本文首先利用模擬的變形蠕蟲樣本評估特征提取的準確性。為CodeRed蠕蟲生成3個變種CodeRed.A、CodeRed.B、CodeRed.C，每個變種20個樣本。

此外，本文對互聯網上的真實蠕蟲進行了實驗。首先，利用了互聯網上在線部署的HoneyBow系統進行蠕蟲樣本的捕獲。對于選定蠕蟲樣本將其傳播網絡流記錄為樣本文件，這些樣本一半用于特征提取，一半用于所提取特征的漏報率測試。實驗中，算法 2高假陽性特征剔除算法中的ρ設為0.001%，用于誤報率測試的正常數據流庫來自2007年9月從國防科技大學網關上捕獲的24GB的網絡數據以及DARPA 99數據集[16]中的正常數據。

3.2 Virut.n蠕蟲傳播特征提取示例

給定Virut.n蠕蟲的31個傳播數據流樣本，圖3顯示了本方法提取Virut.n蠕蟲特征的過程。可以看到，首先，2.3節介紹的特征樹生成算法生成包含7個特征節點的特征樹，然后，2.4節介紹的特征剔除算法輸出特征C3和C4，最后，2.5節介紹的特征規約算法將特征C3和C4等價合并成最后的正則表達式特征（如表1第2行）。

3.3 模擬蠕蟲數據實驗結果

表1對比了已有主要特征提取方法與本文方法輸出的特征以及性能比較。從表中可以看出本文方法輸出的特征既包含全部特征子串，描述了它們的位置關系，并且包含由于3種蠕蟲變種引起的特征“(aaa|bbb|ccc)”，因此本文方法提取的特征更加準確。從表1的性能對比可以看出，本文方法相比通過序列比對提取簡單正則表達式的方法，在準確性更高的同時還大幅地減少了時間開銷。這得益于特征樹生產算法在特征提取過程中的“分治”作用。

3.4 真實蠕蟲數據實驗結果

本文對 Honeybow系統捕獲的被卡巴斯基識別為 virut.n、virut.a、rbot.bsz、sasser.d的 4個蠕蟲樣本進行了特征提取，產生的結果如表2所示。其中，第1列是蠕蟲樣本的名稱，第2列是分析的蠕蟲傳播數據流樣本數量以及特征提取所用時間，第3列是產生特征樹中特征節點的數量，第4列是最后輸出的正則表達式特征，第5列和第6列分別是輸出特征的誤報率和漏報率。可以看出，對 4種蠕蟲本文方法提取的正則表達式元字符均超過20個，且誤報和漏報均為0，因此特征具有較好的準確性。

表1 針對60個模擬蠕蟲樣本的特征提取準確性比較

表2 提取的真實蠕蟲的正則表達式特征

4 方法比較

以表 1為例，表 3給出了本文方法與現有攻擊特征提取方法在準確方面的比較。早期的方法[4,5,8]特征提取準確性差，大量信息不被發掘。基于 Token頻率的方法（如 Polygraph[9]和Hamsa[10]）主要問題是不能提取長度極短的特征片段和特征片段之間的距離關系。較新提出的基于序列比對的方法[12~14]可提取簡單正則表達式特征，缺點是不包含“|”等元字符因而特征描述能力有限。從表中可以看出，相比現有方法本文方法特征提取準確性更好。

表3 本文方法與現有特征提取方法的比較

5 結束語

與現有攻擊特征自動提取方法相比，本文方法輸出的特征更接近完整形式的正則表達式，因此具有更強的攻擊描述能力，準確性更好。使用HoneyBow（蜜罐系統）捕獲的蠕蟲樣本，在真實互聯網環境中測試了該方法的有效性。實驗表明，該方法可準確提取互聯網上真實蠕蟲樣本的正則表達式特征，并可用于準確地檢測網絡蠕蟲傳播。該方法可集成于蜜罐與蜜網、蠕蟲特征自動提取、惡意代碼分析沙盒等系統中，用于快速提取包括未知樣本在內的網絡蠕蟲的特征。本文方法提取的正則表達式特征中仍存在著一些冗余特征字符（例如部分冗余的網絡協議字段），在保證檢測精確度的前提下，如何自動提取更為簡略、語義更為明確的正則表達式特征，以及如何進一步在實際環境中應用、通過量化指標評價特征提取的準確性均可成為下一步研究方向。

[1] FOGLA P, SHARIF M, PERDISCI R, et al. Polymorphic blending attacks[A]. Proceedings of the 15th Conference on USENIX Security Symposium[C]. Berkeley, CA, USA, 2006. 17.

[2] GUNDY M V, BALZAROTTI D, FIELDSCHEMA G V. Catch me, if you can: evading network signatures with Web-based polymorphic worms[A]. Proceedings of the First USENIX Workshop on Offensive Technologies (WOOT)[C]. Boston, MA, USA, 2007.

[3] 唐勇, 盧錫城, 王勇軍. 攻擊特征自動提取技術綜述[J]. 通信學報,2009, 30(2): 96-105.TANG Y, LU X C, WANG Y J. Survey of automatic attack signature generation[J]. Journal on Communications, 2009, 30(2): 96-105.

[4] KREIBICH C, CROWCROFT J. Honeycomb- creating intrusion detection signatures using honeypots[A]. Proceedings of the Second Workshop on Hot Topics in Networks (Hotnets II)[C]. Boston, 2003. 51-56.

[5] WANG K, CRETU G, STOLFO S J. Anomalous payload-based worm detection and signature generation[A].Proceedings of Recent Advances in Intrusion Detection (RAID)[C]. 2003. 227-246.

[6] SINGH S, ESTAN C, VARGHESE G, et al. Automated worm fingerprinting[A]. Proceedings of the 6th USENIX OSDI[C]. 2004. 45-60.

[7] KIM H A, KARP B. Autograph: toward automated, distributed worm signature detection[A]. Proceedings of USENIX Security Symposium[C]. 2004. 271-286.

[8] SINGH S, ESTAN C, VARGHESE G, et al. Automated worm fingerprinting[A]. Proceedings of the 6th USENIX OSDI[C]. San Francisco,CA, 2004. 45-60.

[9] NEWSOME J, KARP B, SONG D. Polygraph: automatically generating signatures for polymorphic worms[A]. Proceedings of IEEE Symposium on Security and Privacy[C]. Washington, DC, USA, 2005.226-241.

[10] LI Z, SANGHI M, CHEN Y, et al. Hamsa: fast signature generation for zero-day polymorphic worms with provable attack resilience[A].Proceedings of IEEE Symposium on Security and Privacy[C]. Washington, DC, USA, 2006. 32-47.

[11] YEGNESWARAN V, GIFFIN J T, BARFORD P, et al. An architecture for generating semantics-aware signatures[A]. Proceedings of the 14th USENIX Security Symposium[C]. Baltimore, MD, USA, 2005.97-112.

[12] 唐勇, 盧錫城, 胡華平等. 基于多序列聯配的攻擊特征自動提取技術研究[J]. 計算機學報, 2006, 29(9): 1533-1541.TANG Y, LU X C, HU H P, et al. Automatic generation of attack signatures based on multi-sequence alignment[J]. Chinese Journal of computers, 2006, 29(9):1533-1541.

[13] TANG Y, LU X, XIAO B. Generating simplified regular expression Signatures for polymorphic worms[A]. Proceedings of the 4th International Conference on Autonomic and Trusted Computing (ATC-07)[C].2007. 478-488.

[14] TANG Y, LU X, XIAO B. Using a bioinformatics approach to generate accurate exploit-based signatures for polymorphic worms[J].Comput, Secur, 2009.

[15] 諸葛建偉, 韓心慧, 周勇林等. HoneyBow:一個基于高交互式蜜罐技術的惡意代碼自動捕獲器[J]. 通信學報, 2007, 28(12): 8-13.ZHUGE J W, HAN X H, ZHOU Y L, et al. HoneyBow: an automated malware collection tool based on the high-interaction honeypot principle[J]. Journal on Communications, 2007, 28(12): 8-13.

[16] LIPPMANN R, HAINES J W, FRIED D J, et al. The 1999 DARPA off-line intrusion detection evaluation[J]. Comput, Networks, 2000,34(4): 579-595.