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

趙躍華，林聚偉

江蘇大學計算機科學與通信工程學院，江蘇鎮江 212013

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

趙躍華，林聚偉

江蘇大學計算機科學與通信工程學院，江蘇鎮江 212013

1 引言

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

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

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

2 可伸縮性聚類方法

2.1 聚類算法的選擇

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

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

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

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

表1 常見聚類算法特征

2.2 可伸縮聚類方法的結構

該方法是一種由粗到細的雙算法結構，首先使用局部敏感哈希索引技術進行初次快速聚類，然后使用擴展K均值算法進行二次細致聚類。方法結構如圖1所示。

圖1 可伸縮性聚類方法結構

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

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

3 實現描述

3.1 預處理

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

本文根據行為日志的內容定義了一個三級結構，而從這個三級結構中抽取的信息稱之為特征。例如下面的三級結構代表了沙盒日志內容的一部分：

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

3.2 二級聚類處理

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

在文獻[7]中提到，LSH算法存在固有的缺點：索引結構依賴于r，ε和n的參數k和l。因此，建立LSH索引的過程需要對參數進行調整，并且隨著數據的變化還需要對索引結構進行調整。本文使用文獻[7]的方法實現LSH參數自動調整。

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

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

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

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

圖2顯示了LSH索引后擴展K均值算法一個工作實例的部分過程。

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

圖2 擴展K均值一個實例的部分過程

LSH索引和擴展K均值共同組成可伸縮性方法的聚類核。樣本經由聚類核處理完畢后，將由調整模塊進行優化調整。

3.3 簇的優化

簇的優化包括兩個部分：調整病毒家族的數量和修正病毒家族通用行為向量集。

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

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

4 測試

為了測試本文所設計的可伸縮性方法，本文使用了2 704個已知樣本作為測試輸入，將測試輸出同標準相比較。

測試環境為惠普xw4600計算機（主要配置為一個Intel酷睿2四核Q9550處理器，4 GB內存，Windows 2003操作系統）。被測軟件是本文設計的聚類系統mcs（malware clustering system）和按文獻[3]設計的凝聚層次聚類系統。

4.1 有效性測試

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

其中，集合A是測試輸出，集合B是標準。在本次實驗中共生成54個病毒家族，表2顯示了測試結果中前8個病毒家族的純度。

表2 測試輸出純度表

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

本文將所有的2 704個樣本聚類為54個病毒家族，平均純度為0.91。實驗數據證明了由于經過預處理時高維特征的選取與優化，二級聚類模塊的擴展K均值聚類以及簇的優化，最終聚類達到一個較高的準確度。

4.2 對比測試

本節首先使用縱向對比測試，如圖3所示。在均使用擴展K均值的前提下，分別在使用和不使用LSH索引的情況下計算聚類所花費的時間以及聚類的純度。然后再通過橫向對比測試將本文設計的聚類方法和文獻[3]中設計的聚類方法作對比。

圖3 縱向對比測試方法

經過計算，對比測試結果如表3所示。

表3 對比測試結果

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

5 結束語

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

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

后期的工作是在確保時間效率的前提下進一步提高聚類的準確性，同時提高病毒樣本在沙盒等模擬環境中的爆破率。

[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].計算機科學，2009，36（8）：201-204.

[7]盧炎生，饒祺.一種LSH索引的自動參數調整方法[J].華中科技大學學報，2006，34（11）：38-40.

[8]Tan Pangning，Steinbach M，Kumar V.數據挖掘導論[M].北京：人民郵電出版社，2006：310-311.

[9]朱明旱，羅大庸，易勵群.一種廣義的主成分分析特征提取方法[J].計算機工程與應用，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

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

病毒家族；可伸縮性聚類；局部敏感哈希；擴展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—），男，教授，主要研究方向為信息安全；林聚偉（1987—），男，碩士研究生，主要研究方向為計算機反病毒和漏洞挖掘。E-mail：zhaoyh@ujs.edu.cn

2012-10-19

2012-12-18

1002-8331（2014）18-0118-04

CNKI網絡優先出版：2013-01-11，http://www.cnki.net/kcms/detail/11.2127.TP.20130111.0953.018.html