郭方方 王欣悅 王慧強 呂宏武 胡義兵 吳 芳 馮光升 趙 倩

1(哈爾濱工程大學計算機科學與技術學院 哈爾濱 150001) 2(哈爾濱商業(yè)大學計算機與信息工程學院 哈爾濱 150028)(guofangfang@hrbeu.edu.cn)

近年來由于惡意代碼攻擊事件發(fā)生頻率越來越高，危害性日益凸顯.高效率的惡意代碼識別方法對于保障主機運行時安全必不可少.現(xiàn)有識別惡意代碼方法按檢測時代碼是否在內(nèi)存中真實運行可分成2類：1)靜態(tài)分析方法;2)動態(tài)分析方法.動態(tài)分析方法相比較于靜態(tài)分析方法提取到的特征更加準確.因為，即使經(jīng)過混淆處理后的代碼，代碼在運行時特征是無法隱藏和改變的，具有更高的識別準確率.因此，使用動態(tài)分析方法識別惡意代碼已成為研究熱點.其中，最常用的技術是動態(tài)污點分析技術［1-2].動態(tài)污點分析方法首先通過污點標記、污點傳播、應用程序接口(application programming interface, API)進行中間截取污點文件，污點文件就是把污點傳播路徑記錄下來，最后使用得到的污點文件構建惡意代碼的行為依賴圖(malicious code behavior dependency graph, MBDG).目前具有代表性的動態(tài)分析工具包主要有CWSandbox［3]，TTAnalyze［4]，Norman Sandbox［5]，Anubis［6]等.

目前，國內(nèi)外研究重點關注的對象是動態(tài)污點分析方法的實現(xiàn)問題.Mchaisen等人［7-8]提出一種AMAL分類器，該分類器能夠根據(jù)惡意代碼的行為進行自動的分析.但該分類器忽視了程序的控制依賴關系，易造成漏報現(xiàn)象.Fattori等人［9]設計了一套惡意代碼行為檢測系統(tǒng)AccessMiner，實時檢測惡意行為，但該系統(tǒng)存在數(shù)據(jù)量過大、匹配時間過長的問題.Alam等人［10-11]提出了一種MARD框架，該框架主要是針對各種變異惡意代碼的檢測，能夠對變異惡意代碼實時快速檢測.此外，他們還提出了一種SWOD-CFWeight方法，該方法能夠根據(jù)惡意代碼的控制流語義對惡意代碼進行實時捕獲.但該方法依然存在存儲空間消耗過大問題.Ghiasi等人［12]提出一種基于寄存器內(nèi)容的惡意代碼檢測框架，但該框架受環(huán)境限制較大且存在存儲空間爆炸問題.Salehi等人［13]使用分類算法對惡意代碼的API調(diào)用和參數(shù)一起作為輸入特征對惡意代碼進行檢測，但該方法提取的特征較少，準確率不高.Qiao等人［14]假設頻繁API調(diào)用序列可以準確反映惡意代碼行為，通過聚類算法探索惡意代碼之間的內(nèi)部規(guī)律，此外，提出了一種使用聚類和分類相結合的技術來識別惡意代碼，該方法主要是計算各個二進制形式的文件來進行預測［15].Toderici等人［16]提出一種Chi-Squared方法，將隱Markov模型與卡方檢驗的統(tǒng)計框架相結合，用來檢測變形惡意代碼.但這2個方法都存在存儲空間消耗過大的問題.

綜上所述，目前的研究成果對依賴圖數(shù)量多、存儲空間消耗過大的問題描述較少甚至未加說明，而此問題已經(jīng)逐漸成為影響動態(tài)污點分析技術發(fā)展的重要瓶頸.因此，以減少依賴圖數(shù)量為切入點，力圖保證特征完整性，并削減行為依賴圖數(shù)量，從而進一步提高識別效率.

1 行為依賴圖的定義與生成

本文提出了基于最大頻繁子圖挖掘的動態(tài)污點分析方法.即根據(jù)每個惡意代碼家族具有共性的特點［17-19]，把每個惡意代碼家族的最大頻繁子圖挖掘出來，各個惡意代碼家族的依賴圖數(shù)量會大幅度減少.惡意代碼家族及其變種惡意代碼的主要特征都包含在挖掘出的最大頻繁子圖中，待測代碼只需和挖掘出的這些最大頻繁子圖進行匹配就可得出結論，這樣提高了識別效率.最大頻繁子圖方法采用基于生成樹的挖掘(spanning tree based maximal graph mining， SPIN)方法.下面對該方法進行詳細介紹.

1.1 行為依賴圖定義

在介紹具體方法之前，先給出行為依賴圖的定義：Gbeh={V,DE,CE,φ,L}，Gbeh表示行為依賴圖.其中，V表示圖的頂點，DE(DE?V×V)表示數(shù)據(jù)關聯(lián)邊，控制關聯(lián)邊用CE(CE?V×V)表示，標號集為φ，集合內(nèi)部有相應API名稱、必要的輸入性參數(shù)、某些輸出參數(shù)和結果的返回值，L為V和φ間的一種映射關系，具體為L:V→φ.動態(tài)污點分析方法主要依靠分析污點文件，污點文件中包括在執(zhí)行一段惡意代碼過程中，該段代碼在執(zhí)行過程中調(diào)用的重要API以及相應重要指令返回值，當執(zhí)行一段程序后，根據(jù)污點文件生成許多行為依賴圖，這些依賴圖被記入一個集合中，稱為總行為依賴圖集合，表示為GG,在這里把集合GG記為

GG={Gbeh1,Gbeh2,…,Gbehi,…,Gbehn},1≤i≤n.

1.2 生成行為依賴圖

生成行為依賴圖包括4個主要部分：頂點添加部分、數(shù)據(jù)關聯(lián)邊添加部分、控制關聯(lián)邊添加部分和生成結束判斷部分.其中行為依賴圖采用鄰接矩陣的形式存儲，而頂點間的數(shù)據(jù)關聯(lián)邊用1表示，控制關聯(lián)邊用2表示，無相應依賴邊用0表示.詳細步驟描述為：

1) 添加頂點.首先分析污點文件，對于某一API來說，污點參數(shù)存在該API中，那么該API為鄰接矩陣中的一個頂點.

3) 添加控制關聯(lián)邊.某段代碼在運行時，會出現(xiàn)新的API被調(diào)用的情況，這時必須考慮這個API是否存在于某個污點數(shù)據(jù)使用控制轉移指令所能抵達范圍之內(nèi).如果使用控制轉移指令可以到達，那么鄰接矩陣某對應位置記為2，代表控制關聯(lián)關系存在于它們之間.

4) 判斷結束條件.當有2種情況出現(xiàn)時，行為依賴圖被終止生成：①污點文件分析完成.對污點文件不斷分析，行為依賴圖中的頂點數(shù)量以及邊的數(shù)量都不斷增多.當某污點文件被分析完成，鄰接矩陣中所有空位被補上0，據(jù)此鄰接矩陣生成最終行為依賴圖.②當未污染的數(shù)據(jù)重新覆蓋目前已存在的污點數(shù)據(jù)時.

由鄰接矩陣生成對應行為依賴圖的方法由算法1表示：

算法1.生成行為依賴圖.

輸入:鄰接矩陣A；

輸出:行為依賴圖G.

① for each API inA

② 向G中添加頂點;

③ end for

⑧ end if

2 最大頻繁子圖生成

最大頻繁子圖生成算法是核心與重點，其名稱是SPIN-MGM(MBDG mining method on spin).該方法首先從獲得的行為依賴圖集中使用FFSM(fast frequent subgragh mining)方法獲得候選頻繁子圖集，再通過擴展方法進行候選數(shù)據(jù)關聯(lián)邊和控制關聯(lián)邊的添加生成最大頻繁子圖集.

2.1 FFSM方法

FFSM方法使用規(guī)范鄰接矩陣CAM(canonical adjacency matrix, CAM)，通過該矩陣能夠得到規(guī)范編碼，通過使用CAM矩陣就不需要直接計算同構子圖，既可以唯一的表示圖，又能降低時間復雜度.要想得到有向圖的規(guī)范編碼需要遍歷鄰接矩陣，這是因為行為依賴圖是有向圖.

FFSM方法首先使用FFSM_Join函數(shù)和FFSM_Extension函數(shù)產(chǎn)生候選子圖.其次，對產(chǎn)生的候選子圖進行剪枝，這是為了篩選掉非頻繁子圖以及CAM不是次優(yōu)的子圖，最終達到減少候選子圖數(shù)量的目的.FFSM方法具體過程由算法2表示：

算法2.FFSM.

輸入:行為依賴圖集GG、最小支持度SUPmin；

輸出:候選頻繁子圖集W.

①S←{頻繁頂點的CAM集合};

②P←{頻繁邊的CAM集合};

③ for eachp∈Pdo

④ if (pis CAM) then

⑤W←W∪{p},D←?；

⑥ forq∈Pdo

⑦D←D∪FFSM_Join(p,q);

⑧ end for

⑨D←D∪FFSM_Extension(p,q);

⑩ 剪枝去掉候選子圖中非頻繁子圖或

CAM不是次優(yōu)的；

2.2 SPIN-MGM方法

SPIN-MGM方法對由FFSM方法產(chǎn)生的候選頻繁子圖集進行剪枝和擴展處理來獲得最大頻繁子圖集.SPIN-MGM方法由算法3表示：

算法3.SPIN-MGM.

輸入:行為依賴圖集GG、最小支持度SUPmin；

輸出:最大頻繁子圖集EG.

①Trees←{T|T是GG中的一棵頻繁樹};

②F←{EG|EG∈Expansion(T) andT∈Trees};

③ return {EG|EG∈FandEGis maximal}.

其中擴展方法Expansion由算法4表示：

算法4.擴展方法Expansion.

輸入:頻繁子樹T；

輸出:頻繁子圖集EG′.

①D←{de|de是T中的候選數(shù)據(jù)關聯(lián)邊};

②F←SearchGraphs(T,D);

③C←{ce|ce是T中的候選控制關聯(lián)邊};

④F←SearchGraphs(T,C);

⑤ Return{EG′|EG′∈F,EG′是頻繁的,EG′和T有相同的正則生成樹}.

其中SearchGraphs方法由算法5表示：

算法5.SearchGraphs方法.

輸入:頻繁子樹、候選控制依賴邊(T,C)或候選數(shù)據(jù)依賴邊(T,D)；

輸出:M.

①M←?;

② for eachei∈Cor eachei∈Ddo

③M←M∪SearchGraphs(G⊕ei,{ei+1,ei+2,…,en});

④ end for

⑤ returnM.

2.3 最大頻繁子圖的應用

最大頻繁子圖的作用主要體現(xiàn)在實際匹配過程中.設計的匹配方法主要實現(xiàn)過程是：挖掘出所有惡意代碼家族行為依賴圖中的最大頻繁子圖后，生成特征庫，然后實時跟蹤惡意代碼，繪制出依賴圖.通過匹配方法來得到行為依賴圖之間的相似度.

匹配方法將目標行為依賴圖Gtarget與特征庫中行為依賴圖集GG中每個最大頻繁子圖都進行匹配，得到1組匹配結果，得到的結果被存儲到數(shù)組中.當進行匹配時，對數(shù)組進行一次遍歷，遍歷得到的最大值就是最終的匹配結果.由算法6表示：

算法6.匹配方法.

輸入:GG，Gtarget；

輸出:匹配結果.

① for eachg∈GG

②m←0;

③n←0;

④i←0;

⑤ for eache∈g

⑥ ife∈Gtarget

⑦m++;

⑧ else

⑨n++;

⑩ end if

3 實驗結果與分析

3.1 實驗指標

實驗對提出的基于最大頻繁子圖挖掘的動態(tài)污點分析方法進行實驗，并通過實驗數(shù)據(jù)對該方法可行性進行研究.此外，與傳統(tǒng)面向惡意代碼識別的動態(tài)污點分析法以及文獻［9,16]中提到的一些方法進行性了對比實驗，突出本文所提出方法的有效性.

實驗結果的測量使用準確率、誤報率、漏報率、最小支持度和識別時間進行度量.這些度量標準主要是由下列4個檢驗指標來計算，它們的含義如表1所示：

Table 1 Inspection Metric表1 涉及的檢驗指標

(1)

PR(precision rate)，代表能夠按樣本真實類別分類的樣本個數(shù)占總樣本個數(shù)的比率，值越高，代表方法分類效果越好：

(2)

FPR(false positive rate)，代表把正常樣本錯誤地識別為惡意樣本的比率，對樣本進行了誤判.如果誤報率越低，那么代表這個方法識別效果就越好:

(3)

FNR(false negative rate)，是方法做出了錯誤的判斷，把原本為正常的惡意樣本，錯誤地識別為惡意的.誤報率越低代表誤判的樣本越少，方法效果更好：

(4)

識別時間，表示從方法開始運行到識別實驗所用全部樣本所需的時間.

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

實驗所用的惡意代碼的來源為http://malware.lu網(wǎng)站，該網(wǎng)站是一個巨大的惡意代碼站，目前是由美國進行維護.該網(wǎng)站現(xiàn)有4 963 698個惡意代碼樣本.在這個網(wǎng)站上可以自由進行惡意代碼的下載，并可根據(jù)惡意代碼的名字和惡意代碼的Hash值進行惡意代碼搜索.

實驗抽取了6類典型惡意代碼家族，共6 410個惡意樣本，具體如表2所示：

Table 2 Samples of Malicious Code Family表2 惡意代碼家族樣本

所抽取的6類惡意代碼家族是目前最突出且最具代表性的.這些惡意代碼大多數(shù)以上都經(jīng)過加殼處理，因此在進行識別之前，要先對惡意代碼進行查殼與脫殼處理.

使用的正常樣本數(shù)據(jù)均來自于常見的應用程序，并通過殺毒軟件進行驗證，如360云盤、QQ音樂、網(wǎng)易云音樂、WPS、GoogleChrome、騰訊視頻等，共16 065個.

3.3 實驗結果分析

首先，針對SPIN-MGM方法的SUPmin進行實驗分析，分析識別準確率PR、誤報率FPR和漏報率FNR隨最小支持度SUPmin的變化情況，結果如圖1所示：

Fig.1 Recognition results varies with SUPmin圖1 識別結果隨SUPmin變化情況

從圖1可以看出，當SUPmin<0.045時，準確率PR逐漸上升，漏報率FNR和誤報率FPR都逐漸下降.這是由于支持度變大，SPIN-MGM方法挖掘出的行為依賴圖包含更多的共同特征；當SUPmin=0.045時，PR達到92.15%，F(xiàn)PR達到5.64%，F(xiàn)NR為14.67%；當SUPmin>0.045時，PR，F(xiàn)PR，F(xiàn)NR基本保持平穩(wěn).當SUPmin=0.045時，識別時間、PR、FPR和FNR達到不錯的結果.因此，據(jù)以上分析后，SPIN-MGM的最小支持度設置為0.045.

其次，研究SUPmin對識別時間和識別效率的影響.將最小支持度SUPmin依次設置為0.02，0.025，0.03，0.035，0.04，0.045，0.05，0.055，0.06.如圖2和圖3所示，可以清楚地看到行為依賴圖數(shù)量以及識別時間隨最小支持度變化趨勢.

從圖2和圖3中可以發(fā)現(xiàn)，當最小支持度SUPmin從0.02變化至0.045時，經(jīng)過SPIN-MGM方法不斷挖掘，行為依賴圖數(shù)量不斷地在減少.與此同時，識別時間不斷削減.這種現(xiàn)象存在的原因是隨著SUPmin逐漸增加，符合該支持度的最大頻繁子圖數(shù)量會越來越少，也即特征庫中需要進行匹配的行為依賴圖越少.因此，識別樣本所需時間也越來越少；當SUPmin=0.045時，行為依賴圖數(shù)量為216個，識別時間約為401 s；當SUPmin>0.045時，行為依賴圖數(shù)量和識別時間基本不在變化.由上面的分析可以推斷出這時挖掘出的行為依賴圖數(shù)量不再變化.相比之下，傳統(tǒng)未經(jīng)挖掘的識別方法，其識別時間為2 201.3 s.因此，可以得出結論，使用SPIN-MGM方法后可縮短樣本識別時間，提高識別效率.

Fig.2 Number of behavior dependency graphs varies with SUPmin圖2 行為依賴圖數(shù)量隨SUPmin變化情況

Fig.3 Recognition time varies with SUPmin圖3 識別時間隨SUPmin變化情況

傳統(tǒng)基于動態(tài)污點分析技術的惡意代碼識別方法，以跟蹤API參數(shù)的傳播路徑，找出API之間的依賴關系，挖掘出惡意代碼的行為為目的，生成行為依賴圖，對惡意代碼進行分類.即使用API函數(shù)參數(shù)提取和基于函數(shù)參數(shù)的污點分析方法.但是，由于需要與惡意代碼家族進行頻繁的比對，導致這種傳統(tǒng)的方法識別時間過長，識別效率較低.從圖2可以看出當SUPmin=0.045時，SPIN-MGM方法特征庫中的行為依賴圖數(shù)量減少到216個.但是，傳統(tǒng)行為依賴圖污點分析方法中的行為依賴圖始終為1 210個左右.因此，SPIN-MGM方法也解決了文獻［9,16]中傳統(tǒng)動態(tài)污點分析方法存儲空間消耗過大的問題.

此外，就準確率、誤報率和漏報率把提出的SPIN-MGM方法與文獻［9,16]中提到的一些惡意代碼識別方法進行了性能對比，如圖4～6所示.Access-Miner［9]是1個以系統(tǒng)為中心的行為惡意軟件檢測器，提供了1個通用的檢測解決方案，不需要對惡意樣本進行訓練，因此它的準確率不及SPIN-MGM.Chi-Squared［16]將隱Markov模型與卡方檢驗的統(tǒng)計框架相結合，用來檢測變形惡意代碼.SVM［20]是一種常見的分類學習方法，但是這種方法對變種惡意代碼的識別準確率相對較差，因為該方法通過樣本訓練模型，一旦出現(xiàn)一種新型變種惡意代碼，它的識別準確率就會降低.

Fig.4 Comparison of recognition accuracy PR offour analysis methods圖4 4種分析方法的識別準確率對比

Fig.5 Comparison of alarm failure FPR of four analysis methods圖5 4種分析方法漏報率FPR對比

Fig.6 Comparison of false alarm rate FNR offour analysis methods圖6 4種分析方法誤報率FNR對比

從圖4～6中可以看出，SPIN-MGM方法在準確率、誤報率上相比于AccessMiner，Chi-Squared，SVM方法達到了更好的效果，在漏報率上優(yōu)于AccessMiner和Chi-Squared方法.SVM在漏報率上低于SPIN-MGM方法.

4 結 論

惡意代碼識別方法是抵御惡意代碼攻擊的重要方法.動態(tài)污點分析方法是現(xiàn)階段研究的熱點，但存在依賴圖數(shù)量大的問題.據(jù)此，本文提出了基于最大頻繁子圖挖掘的動態(tài)污點分析方法，減少了行為依賴圖的數(shù)量，解決了上述問題，提高了識別速度.1)SUPmin越大，滿足該支持度的最大頻繁子圖越少，即特征庫中行為依賴圖越少，識別樣本集時間也隨之變短；2)支持度越大，SPIN-MGM方法挖掘出的行為依賴圖越能代表惡意代碼家族間的共性特征；3)在本文的實驗中，當最小支持度SUPmin=0.045時，行為依賴圖數(shù)量減少了82%，識別效率提高了81.7%，準確率PR達到92.15%，誤報率FPR達到5.64%、漏報率FNR為14.67%.下一步的工作將采用更多類型的惡意代碼，進一步提升識別準確率.