面向海量病毒樣本家族聚類方法的研究

趙躍華，林聚偉

江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇鎮(zhèn)江 212013

面向海量病毒樣本家族聚類方法的研究

趙躍華，林聚偉

江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇鎮(zhèn)江 212013

1 引言

如今，惡意程序是互聯(lián)網(wǎng)遭受的主要威脅之一，僵尸網(wǎng)絡(luò)、釣魚網(wǎng)站、惡意郵件等等本質(zhì)上都是惡意程序，通常也簡單的將惡意程序稱為病毒。安全廠商每天都能收到成千上萬份病毒樣本，為了盡快處理這些安全威脅，安全廠商需要快速而準(zhǔn)確地從這些樣本中提取共性并家族化，從而以病毒家族為單位提供解決方案。

針對海量病毒樣本的家族聚類研究經(jīng)歷了三個(gè)階段，第一個(gè)階段重在時(shí)間效率，旨在短時(shí)間內(nèi)完成聚類工作，如2000年T.H.Haveliwala等人提出針對網(wǎng)絡(luò)海量數(shù)據(jù)的聚類方法[1]，可以在有限時(shí)間內(nèi)完成聚類工作，但準(zhǔn)確度偏低；第二個(gè)階段同時(shí)重視準(zhǔn)確度因素，如2007年M.Bailey和J.Oberheide等人介紹的如何自動(dòng)化鑒定以及分析互聯(lián)網(wǎng)惡意程序[2]，但文章也說明犧牲了部分時(shí)間效率；第三個(gè)階段則傾向于使用多算法的聚類方法，如2009年U.Bayer和P.M.Comparetti等人提出的大規(guī)模的、基于行為分析的病毒聚類系統(tǒng)[3]，具有一定的時(shí)間效率和準(zhǔn)確度，但其對病毒行為特征提取的維度較低，并且時(shí)間效率仍有待提高。

本文在分析現(xiàn)有方法的基礎(chǔ)上設(shè)計(jì)了一種面向海量病毒樣本的家族聚類方法，以幫助安全廠商解決近年來日益嚴(yán)重的病毒聚類問題。該聚類方法特色在于設(shè)計(jì)并實(shí)現(xiàn)了一種二級聚類模型，能夠繼承單一算法的優(yōu)點(diǎn)，從而快速高效地完成聚類工作。同時(shí)使用高維特征刻畫病毒行為以增強(qiáng)聚類的準(zhǔn)確性。

2 可伸縮性聚類方法

2.1 聚類算法的選擇

聚類算法的發(fā)展已經(jīng)比較成熟，常見的聚類算法如K均值、凝聚層次聚類、DBSCAN和局部敏感哈希等等。其中，K均值和局部敏感哈希算法是基于原型的、劃分的聚類技術(shù)；凝聚層次聚類是一種層次聚類算法；DBSCAN則是一種產(chǎn)生劃分聚類的基于密度的聚類算法，其屬于不完全聚類算法。

本文需要處理的數(shù)據(jù)是安全廠商每天接收到的成千上萬的病毒樣本，這些樣本需要在最短的時(shí)間內(nèi)處理完，從而生成以病毒家族為單位的解決方案推送給用戶。理想的，這些數(shù)據(jù)應(yīng)該被完全劃分聚類，即這些病毒樣本應(yīng)該被劃分成不重疊的子集，使得每個(gè)樣本恰好在一個(gè)子集中，同時(shí)，每個(gè)樣本都被處理到。顯然，K均值算法和局部敏感哈希算法符合這樣的要求。另外，最重要的一點(diǎn)是聚類處理要快速。從目前常見的病毒聚類系統(tǒng)[1-3]中可以發(fā)現(xiàn)，使用局部敏感哈希算法的系統(tǒng)時(shí)間效率最高，文獻(xiàn)[1]的實(shí)驗(yàn)表明，使用Pentium II 300 MHz的CPU和512 MB內(nèi)存的計(jì)算機(jī)，能夠在16 h內(nèi)處理2千萬的數(shù)據(jù)量。因此，選擇局部敏感哈希算法作為本文的聚類算法比較合適。

文獻(xiàn)[1]的實(shí)驗(yàn)同時(shí)也表明僅僅使用局部敏感哈希索引技術(shù)雖然具有很高的時(shí)間效率，但犧牲了準(zhǔn)確度，實(shí)驗(yàn)結(jié)果表明在同一簇中，有少數(shù)點(diǎn)與其他點(diǎn)相似度甚至少于20%。

表1概述了常見聚類算法的特征。選擇局部敏感哈希算法可以快速處理海量病毒樣本，但無法保證較高的準(zhǔn)確性。因此，本文在文獻(xiàn)[1]的基礎(chǔ)上，設(shè)計(jì)了一種由粗到細(xì)的聚類方法。使用局部敏感哈希算法快速、大規(guī)模地處理海量病毒樣本后，再使用K均值算法進(jìn)行邊緣顆粒的細(xì)化處理，以提高準(zhǔn)確度。

表1 常見聚類算法特征

2.2 可伸縮聚類方法的結(jié)構(gòu)

該方法是一種由粗到細(xì)的雙算法結(jié)構(gòu)，首先使用局部敏感哈希索引技術(shù)進(jìn)行初次快速聚類，然后使用擴(kuò)展K均值算法進(jìn)行二次細(xì)致聚類。方法結(jié)構(gòu)如圖1所示。

圖1 可伸縮性聚類方法結(jié)構(gòu)

圖1描述了完整的用于病毒聚類的處理結(jié)構(gòu)。首先使用沙盒技術(shù)從病毒樣本中提取特征向量，然后將這些向量作為輸入使用聚類模塊進(jìn)行聚類。聚類模塊主要包括使用LSH（局部敏感哈希）索引技術(shù)進(jìn)行初次快速聚類以及使用擴(kuò)展K均值算法進(jìn)行二次細(xì)致聚類。該聚類模塊繼承了單一LSH算法的優(yōu)點(diǎn)：快速處理海量數(shù)據(jù)的能力；處理高維數(shù)據(jù)的能力。同時(shí)也繼承了K均值算法高準(zhǔn)確性的優(yōu)點(diǎn)。

LSH算法[5]可以提供快速且支持高維度的聚類，極大地滿足了近實(shí)時(shí)性的要求。初次聚類后，由于LSH算法只計(jì)算了近似度，并不能保證所有結(jié)果相似值都在閥值內(nèi)，因此本文在進(jìn)行LSH索引后又使用了具有高準(zhǔn)確性的擴(kuò)展K均值算法進(jìn)行二次細(xì)致聚類。

3 實(shí)現(xiàn)描述

3.1 預(yù)處理

為有效地進(jìn)行二級聚類處理，需作預(yù)處理。由于病毒樣本經(jīng)沙盒技術(shù)分析所得到的行為日志信息過于冗余且不能直接被后面的聚類模塊識(shí)別，因此需要從行為日志中提取特征向量。

本文根據(jù)行為日志的內(nèi)容定義了一個(gè)三級結(jié)構(gòu)，而從這個(gè)三級結(jié)構(gòu)中抽取的信息稱之為特征。例如下面的三級結(jié)構(gòu)代表了沙盒日志內(nèi)容的一部分：

在這個(gè)例子中，本文定義的三級結(jié)構(gòu)為dll_handling_ section，load_dll和filename，然后為此特征條目賦值一個(gè)特征ID。使用這種方法處理整個(gè)日志內(nèi)容，可以得到一個(gè)特征ID集合作為二級聚類處理模塊的輸入。

3.2 二級聚類處理

LSH算法可以分為兩個(gè)部分[6]：LSH模型建立和LSH結(jié)果檢索。圖1中的LSH索引模塊實(shí)際上就是LSH模型建立的過程。LSH模型建立的過程如下：

在文獻(xiàn)[7]中提到，LSH算法存在固有的缺點(diǎn)：索引結(jié)構(gòu)依賴于r，ε和n的參數(shù)k和l。因此，建立LSH索引的過程需要對參數(shù)進(jìn)行調(diào)整，并且隨著數(shù)據(jù)的變化還需要對索引結(jié)構(gòu)進(jìn)行調(diào)整。本文使用文獻(xiàn)[7]的方法實(shí)現(xiàn)LSH參數(shù)自動(dòng)調(diào)整。

在使用LSH算法成功索引后，將會(huì)順序獲取每個(gè)桶的相似集合。首先選擇該桶的一個(gè)元素作為查詢元素進(jìn)行查詢，查詢完畢即獲得該桶的一個(gè)相似集合S。然后一邊將集合S傳給下一個(gè)模塊繼續(xù)處理，一邊繼續(xù)下一次查詢，直到遍歷完所有桶。

由于LSH索引只計(jì)算了相似度，并不能保證所有結(jié)果相似值都在理想閥值內(nèi)，所以可伸縮性方法的第二個(gè)模塊使用擴(kuò)展K均值算法對S集合進(jìn)行細(xì)致高準(zhǔn)確度的處理。

文獻(xiàn)[8]介紹了基本K均值算法，它是基于原型的、劃分的聚類技術(shù)，也是一種使用最為廣泛的聚類算法。基本K均值算法在處理高維的、大容量的數(shù)據(jù)時(shí)有其固有的缺陷，即時(shí)間效率低，不能滿足近實(shí)時(shí)性的要求。而本文設(shè)計(jì)的可伸縮性方法在完成LSH索引后，只是采用K均值算法對邊緣顆粒進(jìn)行修正，因此不會(huì)由于重復(fù)地計(jì)算每個(gè)點(diǎn)和每個(gè)質(zhì)心的相似度而明顯降低整個(gè)算法的時(shí)間效率。本文在基本K均值的基礎(chǔ)上作了一些擴(kuò)展以滿足對LSH索引的兼容以及對邊緣顆粒修正的要求。擴(kuò)展K均值算法定義如下：

在上述算法中，T即為LSH索引的桶的數(shù)量；Buffer集合是一個(gè)緩沖集合，用于保存離群點(diǎn)；J(*)即Jaccard系數(shù)，t為相似度閥值，由人工指定。該算法避免了基本K均值算法的大量重復(fù)計(jì)算，而只計(jì)算了每個(gè)桶和離群點(diǎn)的元素與該桶質(zhì)心的距離，不會(huì)計(jì)算桶元素與其他桶質(zhì)心的距離，即使用離群點(diǎn)規(guī)避了重復(fù)的大量計(jì)算。該算法的復(fù)雜度為O(Tn)，其中T是初次聚類后病毒家族的數(shù)量，n是每個(gè)桶的元素?cái)?shù)目。另外，此算法在選擇初始質(zhì)心時(shí)是確定的，不存在基本K均值選擇初始質(zhì)心的盲目性，即初始質(zhì)心為J(*)≥t所有元素的均值。

圖2顯示了LSH索引后擴(kuò)展K均值算法一個(gè)工作實(shí)例的部分過程。

在圖2中，LSH索引首先輸出一個(gè)集合S給擴(kuò)展K均值模塊處理，擴(kuò)展K均值將相似度超過閥值的兩個(gè)點(diǎn)（處理2中的黃點(diǎn)）判定為離群點(diǎn)劃到Buffer集合中；接著LSH索引繼續(xù)輸出另一個(gè)集合S′給擴(kuò)展K均值模塊處理，這個(gè)時(shí)候Buffer和S′組成新的集合重新聚類，從處理3中可以看到，黃色的點(diǎn)已經(jīng)被吸收進(jìn)了第二個(gè)簇中，并重新生成了一個(gè)離群點(diǎn)（黑色）到Buffer中。重復(fù)此過程，直到LSH索引不再輸出。最后刪除Buffer集合。

圖2 擴(kuò)展K均值一個(gè)實(shí)例的部分過程

LSH索引和擴(kuò)展K均值共同組成可伸縮性方法的聚類核。樣本經(jīng)由聚類核處理完畢后，將由調(diào)整模塊進(jìn)行優(yōu)化調(diào)整。

3.3 簇的優(yōu)化

簇的優(yōu)化包括兩個(gè)部分：調(diào)整病毒家族的數(shù)量和修正病毒家族通用行為向量集。

為了防止病毒家族膨脹，以及特定需求下需要更廣義的病毒家族，可以進(jìn)一步聚類以控制病毒家族的總體數(shù)量。進(jìn)一步聚類的方法是，從每一個(gè)病毒家族中選擇一個(gè)具有代表性的項(xiàng)，然后計(jì)算每個(gè)代表項(xiàng)之間的相似度，根據(jù)給定閥值將相似度高于閥值的家族歸并。經(jīng)過大量實(shí)驗(yàn)發(fā)現(xiàn)，該閥值等于0.7時(shí)具有良好的聚類效果。

聚類完成后，還需要修正病毒家族的通用行為向量集。本文引入了冗余特征消除的算法——主成分分析[9]，它是將多個(gè)變量通過線性變化以選出較少個(gè)數(shù)重要變量的一種多元分析方法，該方法的最優(yōu)性是從n個(gè)樣本中提取m個(gè)主要特征，達(dá)到降維的目的。

4 測試

為了測試本文所設(shè)計(jì)的可伸縮性方法，本文使用了2 704個(gè)已知樣本作為測試輸入，將測試輸出同標(biāo)準(zhǔn)相比較。

測試環(huán)境為惠普xw4600計(jì)算機(jī)（主要配置為一個(gè)Intel酷睿2四核Q9550處理器，4 GB內(nèi)存，Windows 2003操作系統(tǒng)）。被測軟件是本文設(shè)計(jì)的聚類系統(tǒng)mcs（malware clustering system）和按文獻(xiàn)[3]設(shè)計(jì)的凝聚層次聚類系統(tǒng)。

4.1 有效性測試

本文定義了純度的概念來刻畫可伸縮聚類方法的準(zhǔn)確性，其定義：

其中，集合A是測試輸出，集合B是標(biāo)準(zhǔn)。在本次實(shí)驗(yàn)中共生成54個(gè)病毒家族，表2顯示了測試結(jié)果中前8個(gè)病毒家族的純度。

表2 測試輸出純度表

在表2中，第一行顯示簇ID，第二行顯示每個(gè)簇的大小，而下面的每一行顯示該簇的組成中包含各種家族病毒的比例。例如，ID為7的簇，純度為0.98，大小為44，即意味著該簇由43個(gè)家族A的病毒和1個(gè)家族B的病毒組成，顯然，這1個(gè)家族B的病毒被誤判進(jìn)了簇7中。

本文將所有的2 704個(gè)樣本聚類為54個(gè)病毒家族，平均純度為0.91。實(shí)驗(yàn)數(shù)據(jù)證明了由于經(jīng)過預(yù)處理時(shí)高維特征的選取與優(yōu)化，二級聚類模塊的擴(kuò)展K均值聚類以及簇的優(yōu)化，最終聚類達(dá)到一個(gè)較高的準(zhǔn)確度。

4.2 對比測試

本節(jié)首先使用縱向?qū)Ρ葴y試，如圖3所示。在均使用擴(kuò)展K均值的前提下，分別在使用和不使用LSH索引的情況下計(jì)算聚類所花費(fèi)的時(shí)間以及聚類的純度。然后再通過橫向?qū)Ρ葴y試將本文設(shè)計(jì)的聚類方法和文獻(xiàn)[3]中設(shè)計(jì)的聚類方法作對比。

圖3 縱向?qū)Ρ葴y試方法

經(jīng)過計(jì)算，對比測試結(jié)果如表3所示。

表3 對比測試結(jié)果

從表3中可知，本文設(shè)計(jì)的病毒聚類方法使用LSH索引技術(shù)后，雖然聚類的純度（即準(zhǔn)確性）下降了4.2%，但時(shí)間消耗減少了94.5%，從而達(dá)到安全廠商近實(shí)時(shí)性處理的要求。另外，同文獻(xiàn)[3]中的聚類系統(tǒng)相比，純度下降了5.2%，但時(shí)間消耗減少了95.2%。因此，本文設(shè)計(jì)的方法在有限降低聚類準(zhǔn)確度的情況下，大為提高了聚類的時(shí)間效率。實(shí)驗(yàn)數(shù)據(jù)同時(shí)也證明了二級聚類模塊的有效性：由于使用了LSH索引技術(shù)，所以相比之下具有很高的時(shí)間效率；然而同時(shí)也降低了一定的準(zhǔn)確度。

5 結(jié)束語

本文介紹了一種新的針對大量病毒樣本聚類的方法。首先使用沙盒技術(shù)獲取病毒行為日志，然后從日志中提取特征向量作為聚類模塊的輸入，接著聚類模塊先后使用LSH索引和擴(kuò)展K均值算法由粗到細(xì)地對輸入的特征向量集聚類，最后由優(yōu)化模塊對結(jié)果進(jìn)行優(yōu)化處理。實(shí)驗(yàn)表明，這種雙算法結(jié)構(gòu)的可伸縮性聚類方法在犧牲有限準(zhǔn)確性的同時(shí)極大提高了病毒家族聚類的時(shí)間效率。

本文所設(shè)計(jì)的可伸縮性聚類方法和所有基于行為分析的聚類方法一樣具有一些局限性。獲取病毒運(yùn)行行為日志的前提是確保病毒完整地在沙盒中運(yùn)行，然而，有些病毒的行為具有條件依賴性，例如某些邏輯只有在網(wǎng)絡(luò)通順或者接收到特定指令的情況下才會(huì)執(zhí)行。

后期的工作是在確保時(shí)間效率的前提下進(jìn)一步提高聚類的準(zhǔn)確性，同時(shí)提高病毒樣本在沙盒等模擬環(huán)境中的爆破率。

[1]Haveliwala T H，Gionis A，Indyk P.Scalable techniques for clustering the web[C]//WebDB（Information Proceedings），2000：129-134.

[2]Bailey M，Oberheide J，Andersen J，et al.Automated classification and analysis of internet malware[C]//Proceedings of the 10th International Symposium on Recent Anvances in Intrusion Detection，2007：178-197.

[3]Bayer U，Comparetti P M，Hlauschek C，et al.Scalable，behavior-based malware clustering[C]//Proceedings of the Network and Distributed System Security Symposium，2009.

[4]Weber R，Schek H，Blott S.A quantitative analysis and performance study for similarity search methods in high dimensional spaces[C]//Proceedings of the 24th Intl Conf on Very Large Data Bases（VLDB），1998：194-205.

[5]Indyk P，Motwani R.Approximate nearest neighbors：towards removing the curse of dimensionality[C]//Jeffrey V.Proc of the 30th Annual ACM Symp on Theory of Computing. New York：ACM Press，1988：604-613.

[6]蔡衡，李舟軍，孫健，等.基于LSH的中文文本快速檢索[J].計(jì)算機(jī)科學(xué)，2009，36（8）：201-204.

[7]盧炎生，饒祺.一種LSH索引的自動(dòng)參數(shù)調(diào)整方法[J].華中科技大學(xué)學(xué)報(bào)，2006，34（11）：38-40.

[8]Tan Pangning，Steinbach M，Kumar V.數(shù)據(jù)挖掘?qū)д揫M].北京：人民郵電出版社，2006：310-311.

[9]朱明旱，羅大庸，易勵(lì)群.一種廣義的主成分分析特征提取方法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（26）：38-40.

ZHAO Yuehua，LIN Juwei

School of Computer Science and Telecommunication Engineering，Jiangsu University，Zhenjiang，Jiangsu 212013，China

Anti-malware companies receive thousands of malware samples every day,so it becomes more and more pressing to handle these samples timely and effectively.A scalable clustering approach is proposed to group these massive malware samples.LSH algorithm is used to cluster samples rapidly.ExtendedK-means algorithm is employed to perform accurately clustering.Experimental results show that this approach can improve malware clustering efficiency observably at the cost of little accuracy.

malware family;scalable clustering;Locality Sensitive Hash（LSH）algorithm;extendedK-means

計(jì)算機(jī)反病毒廠商每天接收成千上萬的病毒樣本，如何快速有效地將這些海量樣本家族化是一個(gè)亟待解決的問題。提出了一種可伸縮性的聚類方法，面對輸入海量的病毒樣本向量化特征集，使用局部敏感哈希索引技術(shù)進(jìn)行初次快速聚類，使用擴(kuò)展K均值算法進(jìn)行二次細(xì)致聚類。實(shí)驗(yàn)表明該聚類方法在有限犧牲準(zhǔn)確度的情況下，大為提高了病毒聚類的時(shí)間效率。

病毒家族；可伸縮性聚類；局部敏感哈希；擴(kuò)展K均值

A

TP309.5

10.3778/j.issn.1002-8331.1210-0202

ZHAO Yuehua，LIN Juwei.Research on familial clustering of massive malware samples.Computer Engineering and Applications,2014,50（18）：118-121.

趙躍華（1958—），男，教授，主要研究方向?yàn)樾畔踩?；林聚偉?987—），男，碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)反病毒和漏洞挖掘。E-mail：zhaoyh@ujs.edu.cn

2012-10-19

2012-12-18

1002-8331（2014）18-0118-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-01-11，http://www.cnki.net/kcms/detail/11.2127.TP.20130111.0953.018.html