基于序列比對的勒索病毒同源性分析

龔 琪,曹金璇,蘆天亮

(中國人民公安大學(xué)信息技術(shù)和網(wǎng)絡(luò)安全學(xué)院,北京 100076)

0 引 言

勒索病毒加密受害人重要文件或系統(tǒng)向其索求支付贖金以獲得回報。病毒主要以郵件、exploit kits、網(wǎng)頁廣告嵌套等方式感染受害者[1]。近期影響頗大的WannaCrypt感染事件，病毒主要以社會工程學(xué)方式嘗試感染目標(biāo)環(huán)境,通過帶有惡意宏Office文檔附件的釣魚郵件，感染環(huán)境中電腦后，該變種會嘗試在內(nèi)網(wǎng)中主動傳播。據(jù)統(tǒng)計，勒索軟件攻擊從2015年380萬次增至2016年6.38億次。CTA報告[2]指出，勒索病毒新成員CryptoWall4在2016年造成了約1800萬美元損失。另一報告指出[3]，繼政府和商業(yè)，醫(yī)院已成為勒索軟件下一個攻擊目標(biāo)。勒索攻擊中，新出現(xiàn)家族并不多，多數(shù)為已有家族變種，所以研究勒索病毒的同源性能為對抗勒索病毒提供有力幫助。

檢測勒索病毒屬于惡意代碼檢測，目前的檢測方法主要分有靜態(tài)檢測、動態(tài)檢測。靜態(tài)分析通過逆向工程抽取程序特征，分析函數(shù)調(diào)用、程序指令等序列。而勒索病毒使用了內(nèi)存映射、混肴、花指令等手段躲避靜態(tài)分析，所以特征不明顯。為了克服這種困難，本文基于動態(tài)檢測捕獲勒索病毒行為，雖然它們的靜態(tài)特征不明顯，但是有相同的動態(tài)特征，如注冊表特征、文件行為特征等。所以，本文提出一種基于動態(tài)行為特征結(jié)合序列比對算法對勒索病毒進行同源性分析。動態(tài)行為特征中，API調(diào)用最具代表性，API調(diào)用序列是程序與系統(tǒng)交互最基本的接口，通過對API序列進行編碼，能全面捕獲勒索病毒的動態(tài)行為。n-gram算法是一種簡單序列比對算法，API調(diào)用序列中存在大量重復(fù)API序列調(diào)用，使用n-gram算法時，檢測效果不理想。此外，動態(tài)規(guī)劃算法以及多重序列比對算法已廣泛應(yīng)用于生物信息學(xué)領(lǐng)域。動態(tài)規(guī)劃算法中包含局部序列比對以及全局比對算法，2類算法都提供了一種對齊解決方案來匹配2個目標(biāo)序列最大公共序列。

本文首先對API調(diào)用序列分類，對API調(diào)用序列類別編碼，結(jié)合Clustalw等算法計算樣本之間最大公共序列進行建模，計算樣本之間相似度。實驗表明，本方法能很好地分析勒索病毒同源性，并能區(qū)分正常軟件。

1 序列比對算法

在生物信息學(xué)研究中,將未知序列與已知序列進行相似性比較較為成熟。序列比對分為全局序列比對和局部序列比對,局部序列比對對2個序列局部區(qū)域相似性進行考察,對于序列的未對齊部分沒有懲罰[4-5]，從而找出序列之間公共部分。全局序列比對對2個序列全局相似性進行考察，從序列開始至結(jié)束進行對齊、比對以找出最佳比對。

1.1 局部序列比對算法

Smith-Waterman算法，基于動態(tài)規(guī)劃思想比對過程包括初始化、計算打分矩陣、回溯3個步驟。給定2個序列A=a1a2a3…an和B=b1b2b3…bm，序列A和序列B中的元素相似度為s(a,b)，長度為k的插入損失為Wk,初始化打分矩陣H：

Hx0=H0y=0， 0≤x≤n,0≤y≤m

(1)

H(i,j)=max{

0

H(i-1,j-1)+s(ai,bj)

(2)

(3)

Wi=-i

(4)

其中H矩陣取4種情況下最大值，s(ai,bj)為序列a1a2a3…ai與b1b2b3…bj最大相似度，通過公式(3)進行計算。Wi為空位懲罰因子。

回溯尋找相似子序列過程為:在打分矩陣中找到數(shù)值最大元素,然后回溯找到該最大值上一個元素,重復(fù)以上過程,直至無法找到向上路徑,得到序列就是最大相似子序列。

1.2 全局序列比對算法

Needleman-Wunsch實現(xiàn)大致如下，取罰分函數(shù)w(a,b)=dH(a,b)為Hamming距離，如A,B為需比對序列，則將輸入序列A=(a1,a2,…,ana),B=(b1,b2,…,bnb)作為方陣第0行、第0列。再由A,B序列確定得分矩陣S=(Si,j),懲罰函數(shù)使用Hamming距離，打分函數(shù)定義如下,其中d為罰分值。

(5)

(6)

根據(jù)得分矩陣回溯確定最高得分對應(yīng)序列比對。得到最后一個s(n,m)值，此值為(A,B)比對后最高得分。同時s(n,m)為回溯起點。

1.3 多重序列比對Clustaw

Clustaw是一種基于動態(tài)規(guī)劃的算法，先對多重序列兩兩比對，得到最優(yōu)解。由比對結(jié)果計算各序列間相互距離，得到多重序列兩兩比對距離矩陣。由結(jié)果距離矩陣做多重序列聚類分析，產(chǎn)生向?qū)?。對向?qū)湎噜従仃囋僮霰葘Γ纱水a(chǎn)生多重序列比對結(jié)果。其中時間復(fù)雜度為O(m2n2)，m為輸入序列的條數(shù)，n為輸入序列的平均長度。

1.4 降低時間復(fù)雜度

Smith-Waterman算法搜索整個解空間，其計算時間復(fù)雜度為O(n2)，n為輸入序列的平均長度。Clustaw算法時間復(fù)雜度為O(m2n2)，兩者算法敏感性好，但時間復(fù)雜度隨著輸入序列的條數(shù)及長度而增長，計算時間較長。在研究API調(diào)用時發(fā)現(xiàn)調(diào)用序列包含許多重復(fù)子調(diào)用，重復(fù)調(diào)用通常發(fā)生于API調(diào)用陷入循環(huán)后，這類循環(huán)通常在一個家族中有不同表現(xiàn)，所以重復(fù)子序列應(yīng)該被移除，來提高勒索家族檢測率。此外，移除重復(fù)子序列也能減少API序列調(diào)用長度，同時提高算法執(zhí)行效率。

2 勒索病毒同源性分析設(shè)計

2.1 同源性分析架構(gòu)

勒索病毒使用API來執(zhí)行各種惡意行為。本文基于API調(diào)用類別相似度計算方法進行勒索病毒同源性分析，圖1為系統(tǒng)架構(gòu)流程圖。

圖1 勒索病毒同源性分析架構(gòu)圖

整個系統(tǒng)流程包括2部分。第1部分為選取模塊，選取各家族中代表性強的樣本作為比對樣本。第2部分為相似度計算模塊，包括4個子模塊:1)行為監(jiān)控模塊，使用沙箱監(jiān)控勒索病毒動態(tài)行為并提取API調(diào)用行為； 2)轉(zhuǎn)換模塊，對樣本的API調(diào)用進行分類轉(zhuǎn)換，再將調(diào)用類別編碼為API類別序列； 3)比對模塊，使用全局比對算法進行序列比對； 4)結(jié)果輸出模塊，計算相似度并輸出。

2.2 行為監(jiān)控

在行為監(jiān)控階段，本文基于開源沙箱cuckoo監(jiān)控勒索軟件行為并捕獲動態(tài)行為特征，從中提取樣本API調(diào)用行為。本實驗中，大部分樣本能被檢測到動態(tài)行為，小部分樣本如果檢測到在虛擬環(huán)境下不釋放異常行為，考慮到樣本在檢測是否在虛擬環(huán)境時可能API調(diào)用類別的序列也不一樣，所以本文將不釋放異常行為的樣本也包括在內(nèi)來檢測模型的效果。經(jīng)實驗，95.2%的樣本捕獲到API調(diào)用行為。

2.3 編碼與轉(zhuǎn)換

API由各種函數(shù)實現(xiàn)，如果對單個系統(tǒng)調(diào)用進行編碼，不但消耗的時間復(fù)雜度高，而且表征勒索軟件行為不明顯。結(jié)合API調(diào)用類別進行行為表征研究[6-7]，本文將API調(diào)用序列分為16類API調(diào)用類別，對API調(diào)用序列類別進行編碼，使用API調(diào)用類別表示勒索病毒行為，編碼表如表1所示。

表1 API調(diào)用類別與對應(yīng)編碼

API調(diào)用類別編碼API調(diào)用類別編碼certificateAprocessIcryptoBregistryJexceptionCresourceKfileDservicesLmiscEsynchronisationMnetapiFsystemNnetworkGuiOoleH＿＿notification＿＿P

提取樣本API調(diào)用序列后根據(jù)對應(yīng)編碼規(guī)則進行編碼，獲得API“基因”序列。

本文對重復(fù)子序列進行去重[8]，雖然去重會影響序列之間的相似度，但不會對分類結(jié)果造成很大影響，參考研究者們?nèi)ブ胤椒╗9-10]，本文設(shè)計去重算法去除重復(fù)調(diào)用的API子序列來降低時間復(fù)雜度。如下偽代碼為整個算法中去重部分,輸入為已編碼的API調(diào)用序列，a,b為訓(xùn)練樣本i中長度為n的第k、k+1個子序列。

輸入:訓(xùn)練集N；子序列長度n

輸出:去重后的訓(xùn)練集

1 For i in N:

2 if k≤len(i):

3 ak=ink，bk=ink+1, k∈N+

4 if ak==bk:

5 刪除bk，bk=bk+1

6 else：

7 ak=bk, bk=bk+1

8 Return已去重的序列

2.4 序列比對

完成編碼后，使用算法[11-12]排列編碼后的調(diào)用序列。對齊調(diào)用序列類似于圖2中示例。算法通過將間隙gap插入到序列中以使它們正確對齊。

圖2 序列對齊的例子

2.5 計算相似度

對齊后，從中提取匹配的子序列，計算相似度，相似度計算公式如下：

m=Length(A),n=Length(B)

(7)

其中，L為匹配的子序列長度，m，n分別為API類別調(diào)用序列A，B總長度，相似度取值范圍在(0,1)之間。Sim(A，B)越大，意味A，B序列越相似。

3 模型驗證與分析

3.1 實驗數(shù)據(jù)

公開網(wǎng)站(http://www.malware-traffic-analysis.net)下載近幾年勒索病毒，正常樣本集從360官網(wǎng)下載所得，如表2所示。

表2 使用的勒索樣本所屬家族及數(shù)量

勒索病毒家族數(shù)量正常樣本數(shù)量CryptFile10安全殺毒類8CryptoMIC12辦公軟件類11CryptoWall10音樂軟件類9CryptXXX16硬件檢測類13Locker10視頻軟件類7Spora19聊天工具類18總數(shù)77總數(shù)56

其中正常樣本集包含6類共56個樣本軟件。勒索樣本集中包含6類共77個勒索樣本，為了減少污染[13]，正常樣本集僅從360官方應(yīng)用商店，按軟件使用比例下載軟件。檢測所有數(shù)據(jù)在Virus Total上結(jié)果，選擇樣本集為已去除被污染樣本集。實驗環(huán)境如表3所示。

表3 實驗環(huán)境

實驗環(huán)境配置處理器Intel(R)Core(TM)i7?4810MQ主頻2．8GHz內(nèi)存8G操作系統(tǒng)Ubuntu14．04軟件環(huán)境VBox5．1，Python2．7沙箱操作系統(tǒng)WindowsXPSP2沙箱軟件環(huán)境WPS，QQ，微信，Chrome瀏覽器，Python2．7

3.2 實驗結(jié)果與分析

3.2.1 形成比對對象

本實驗中使用的樣本集為已知家族的樣本，在獲取所有樣本集的動態(tài)行為后，根據(jù)本文提出的編碼方式分別生成各家族“序列圖譜”和樣本集的“序列編碼”。圖3、圖4當(dāng)取子序列為1時，CryptoMic家族樣本集的“序列編碼”?？梢钥闯鋈ブ厍癈ryptoMic21.fasta序列大小為285.2 kB，去重后為20.4 kB。

圖3 未去重的“API調(diào)用行為類別序列”

圖4 去重后的“API調(diào)用行為類別序列”

3.2.2 進行比對

圖5為子序列為3時，CryptoFile家族的樣本與CryptoMic家族的“序列圖譜”的比對結(jié)果，其中相似度為1.1%,Gaps值為98.9%。

圖5 CryptoFile-CryptoMic比對結(jié)果

3.2.3 實驗結(jié)果

如表4～表7所示，橫軸為各家族，縱軸為已知所屬家族的樣本集。表示每類樣本集與各家族的相似度Sk：

其中k∈[1,6]，n表示樣本總量，xi表示樣本集中樣本i與家族k的相似度。

表4 子序列長度為1 /%

Len(1)CRYPTOFILECRYPTOMICCRYPTOWALLCRYPTOXXXLOCKERSPORACryptoFile643746465540CryptoMic445541413841CryptoWall261746465738CryptoXXX38958586361Locker272762626557Spora22356262476

表5 子序列長度為2 /%

Len(2)CRYPTOFILECRYPTOMICCRYPTOWALLCRYPTOXXXLOCKERSPORACryptoFile581831315137CryptoMic445028284642CryptoWall261135353730CryptoXXX17237374815Locker202437377040Spora272937375876

表6 子序列長度為3 /%

Len(3)CRYPTOFILECRYPTOMICCRYPTOWALLCRYPTOXXXLOCKERSPORACryptoFile71327114654CryptoMic3972363852CryptoWall18157394656CryptoXXX6210784744Locker16279127761Spora26388125180

表7 子序列長度為4 /%

Len(4)CRYPTOFILECRYPTOMICCRYPTOWALLCRYPTOXXXLOCKERSPORACryptoFile71345314152CryptoMic27691284642CryptoWall111768355351CryptoXXX11310695154Locker23318377758Spora18346376477

如表6所示，選取子序列長度為3時，檢測效果最好，檢測集與本家族平均相似度在75%以上，與其他家族的平均相似度在50%以下。本文樣本集都為勒索病毒，大部分存在同樣的勒索行為，如頻繁的文件讀寫操作、頻繁的注冊表操作等，都會增加與其他家族的相似度。同時本文比較的是勒索病毒每個家族存在變種以及進化的版本，所以系統(tǒng)調(diào)用上存在一定的差異，及相似度上會產(chǎn)生差異。

表8表示取子序列長度為3時各家族樣本間的gap值。Locker家族與Spora家族的勒索病毒”序列編碼”相似度為61%，但gap值90%?？梢缘贸?，基于序列比對算法,結(jié)合序列間相似度與gap值可以很好的分析勒索病毒同源性。

表8 子序列長度為3時與各家族gap值 /%

Len(3)CRYPTOFILECRYPTOMICCRYPTOWALLCRYPTOXXXLOCKERSPORACryptoFile275873928158CryptoMic633079966652CryptoWall921468959091CryptoXXX928992259092Locker858590913090Spora828690789122

如表9所示,子序列取3時，正常軟件與勒索家族相似度,可以看出硬件檢測類軟件與CryptoXXX家族的相似度最高，相似度為39%，說明該模型能很好地區(qū)分正常軟件與勒索病毒。

表9 正常軟件與各勒索家族的相似度 /%

Len(3)CRYPTOFILECRYPTOMICCRYPTOWALLCRYPTOXXXLOCKERSPORA安全殺毒類222115242730辦公軟件類10111419109音樂軟件類1317212298硬件檢測類303534393231視頻軟件類23193172917聊天工具類212830161822

4 結(jié)束語

針對勒索軟件，本文提出一種基于序列比對的方法進行同源性分析，通過使用API類別表述樣本行為， 能較好解決特征表征問題。此外，結(jié)合序列比對算法，在檢測勒索軟件同源性以及區(qū)分正常軟件與勒索病毒實驗中效果明顯。

在使用序列比對算法時，存在計算時間長、時間復(fù)雜度高的問題。本文使用去重的方式，較好解決了這些問題。將來繼續(xù)深入研究基于序列比對的方法，由于網(wǎng)絡(luò)安全威脅不僅是勒索軟件，因此希望能將該方法應(yīng)用于其他類型惡意軟件同源性分析中。

[1] Sgandurra D，Muoz-González L， Mohsen R, et al. Automated dynamic analysis of ransomware: Benefits, limitations and use for detection[J]. Computer Science, 2016: arXiv:1609.03020.

[2] Cyber Threat Alliance. Lucrative Ransomware Attacks: Analysis of the Cryptowall Version 3 Threat[EB/OL]. http://www.doc88.com/p-7714530017104.html, 2016-01-13.

[3] McAfee. Part of Intel Security. McAfee Labs Threats Report: September[EB/OL]. https://www.mcafee.com/us/resou-rces/reports/rp-quarterly-threats-sep-2016.pdf, 2016-09-30.

[4] Altschul S F, Gish W, Miller W, et al. Basic local alignment search tool[J]. Journal of Molecular Biology, 1990,215(3):403-410.

[5] Cohen J. Bioinformatics_an introduction for computer scientists[J]. ACM Computing Surveys (CSUR), 2004,36(2):122-158.

[6] Yakup K. Automated detection and classification of malware used in targeted attacks via machine learning[D]. Bilkent University, 2015.

[7] Kirda E. UNVEIL: A large-scale, automated approach to detecting ransomware (keynote)[C]// IEEE 24th International Conference on Software Analysis, Evolution and Reengineering. 2017:1.

[8] Cho I K, Kim T G, Shim Y J, et al. Malware similarity analysis using API sequence alignments[J]. Journal of Internet Service and Information Security, 2014,4(4):103-114.

[9] Kim H, Kim J, Kim I. Implementation of malware detection system based on behavioral sequences[C]// Security Technology 2016. 2016,139:348-353.

[10] Cho I K, Im E G. Malware family recommendation using multiple sequence alignment[J]. Journal of Molecular Evolution, 2016,43(3):289-295.

[11] 劉陽,王小磊,李江域,等. 局部序列比對算法及其并行加速研究進展[J]. 軍事醫(yī)學(xué), 2012,36(7):556-560.

[12] Smith T F, Waterman M S. Identification of common molecular subsequences[J]. Journal of Molecular Biology, 1981,147(1):195-197.

[13] Rossow C, Dietrich C J, Grier C, et al. Prudent practices for designing malware experiments: Status quo and outlook[C]// IEEE Security & Privacy. 2012:65-79.