陳志鋒李清寶 張 平 馮培鈞

（解放軍信息工程大學(xué) 鄭州 450001）（數(shù)學(xué)工程與先進計算國家重點實驗室 鄭州 450001）

基于聚類分析的內(nèi)核惡意軟件特征選擇

陳志鋒*李清寶 張 平 馮培鈞

（解放軍信息工程大學(xué) 鄭州 450001）（數(shù)學(xué)工程與先進計算國家重點實驗室 鄭州 450001）

針對現(xiàn)有基于數(shù)據(jù)特征的內(nèi)核惡意軟件檢測方法存在隨特征的增多效率較低的問題，該文提出一種基于層次聚類的特征選擇方法。首先，分析相似度計算方法應(yīng)用于數(shù)據(jù)特征相似度計算時存在的困難，提出最長公共子集并設(shè)計兩輪Hash求解法計算最長公共子集；其次，設(shè)計基于最長公共子集的層次聚類算法，有效地將相似特征聚類成簇；在此基礎(chǔ)上，設(shè)計基于不一致系數(shù)的內(nèi)核惡意軟件特征選擇算法，大大減少特征數(shù)，提高檢測效率。實驗結(jié)果驗證了方法的有效性，且時間開銷在可接受的范圍內(nèi)。

數(shù)據(jù)特征；最長公共子集；層次聚類；特征選擇；內(nèi)核惡意軟件

1 引言

隨著計算機和互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，惡意軟件對計算機的危害性日益加重，內(nèi)核惡意軟件是針對內(nèi)核進行攻擊的惡意程序，對計算機系統(tǒng)造成的危害更底層、更徹底，攻擊具有隱蔽性、持久性等特點。內(nèi)核惡意軟件檢測已成為重要的研究方向之一。

現(xiàn)有的內(nèi)核惡意軟件檢測方法可分為基于啟發(fā)式的檢測和基于特征的檢測兩大類［1］。其中基于特征的檢測方法是當(dāng)前的主流方法。特征的描述能力決定了基于特征的檢測方法能否有效檢測內(nèi)核惡意軟件的能力［2］。

傳統(tǒng)的惡意代碼特征大多使用代碼特征和序列特征描述法。代碼特征主要是指靜態(tài)二進制特征，其本質(zhì)上是一段包含匯編指令等信息的二進制字符串。該特征對于已知的惡意軟件具有較好的效果，對于未知的惡意軟件無能為力。文獻［3～5］將惡意代碼映射到灰度圖片，通過對圖片進行分塊建立惡意代碼特征并通過特征相似性匹配進行惡意代碼檢測。該方法能夠檢測一些未知的惡意軟件及變種，但對于加殼的惡意軟件效果較差。序列特征描述法主要采用系統(tǒng)調(diào)用或者指令序列描述特征。如，Ding等人［6］將特征描述為基于控制流的操作碼序列，Wang等人［7］用系統(tǒng)調(diào)用數(shù)目描述特征。序列描述法針對代碼或行為的先后次序，易受代碼混淆手段的干擾。常用的還有控制流程圖（Control Flow Graph，CFG）描述法［8］。它以代碼的執(zhí)行流程描述特征，但因局限于代碼執(zhí)行順序，易受順序無關(guān)操作調(diào)換等混淆方法的干擾，適合于合法軟件的完整性檢測。為了克服這些特征描述方法存在的問題，研究人員針對內(nèi)核惡意軟件的攻擊對象，提出了內(nèi)核數(shù)據(jù)不變量特征［9，10］，基于該類特征能夠檢測一些未知的惡意軟件。但是并不是所有的內(nèi)核數(shù)據(jù)都具備不變量特征，一旦攻擊者攻擊這類數(shù)據(jù)，這種方法也將失效。為此，文獻［11］根據(jù)內(nèi)核數(shù)據(jù)訪問的一般性質(zhì)，提出了數(shù)據(jù)特征。該特征充分描述了惡意軟件運行過程中對內(nèi)核數(shù)據(jù)的篡改行為，能夠較好地用于內(nèi)核惡意軟件檢測。但文獻［11］通過特征匹配實現(xiàn)基于數(shù)據(jù)特征的檢測方法導(dǎo)致檢測效率隨著特征數(shù)量的增多而大幅度降低。

針對基于數(shù)據(jù)特征的內(nèi)核惡意軟件檢測方法存在的問題，本文提出了基于聚類分析的惡意軟件特征選擇方法。該方法在分析數(shù)據(jù)特征的組成和相似性計算方法不足的基礎(chǔ)上提出了最長公共子集（Longest Common Subset， LCS）的概念，并討論了基于最長公共子集的相似度計算方法。然后闡述了數(shù)據(jù)特征層次聚類和特征選擇過程，并給出了基于選擇特征的惡意軟件檢測方法。最后通過實際應(yīng)用中的內(nèi)核惡意軟件樣本對該方法進行功能和性能評估。

2 數(shù)據(jù)特征

2.1 數(shù)據(jù)特征描述方法

為了更好地說明基于數(shù)據(jù)特征的聚類分析以及特征選擇方法，本文首先對文獻［11］提出的數(shù)據(jù)特征作簡要介紹。

定義1［11］DBE（Data Behavior Element）是一個5元式（c，o，m，i，f），其中，c為訪問內(nèi)核數(shù)據(jù)的代碼；o為訪問內(nèi)核數(shù)據(jù)的操作，包括讀或?qū)懀?o=1表示寫操作，o = 0表示讀操作；m為數(shù)據(jù)對象類型，包括靜態(tài)數(shù)據(jù)或動態(tài)數(shù)據(jù)， m= 1表示動態(tài)數(shù)據(jù)，m= 0表示靜態(tài)數(shù)據(jù)；i為數(shù)據(jù)對象標(biāo)識，當(dāng) t=0時，i是基于編譯階段的符號信息賦予的編號；當(dāng)t= 1時，i是分配該數(shù)據(jù)的分配位置和數(shù)據(jù)類型；f為被訪問的數(shù)據(jù)對象字段的偏移值。

根據(jù)定義1，一個DBE給出了訪問一個內(nèi)核數(shù)據(jù)的過程。操作系統(tǒng)內(nèi)核中包含有成百上千種數(shù)據(jù)類型，這些數(shù)據(jù)類型又定義了成千上萬個內(nèi)核數(shù)據(jù)。因此，所有的DBE集合描述了內(nèi)核一次運行過程的數(shù)據(jù)訪問情況，詳見定義2。

定義 2［11］內(nèi)核一次運行實例的數(shù)據(jù)訪問可由序列）定義，其中m表示內(nèi)核的某一次運行。

由定義 2可知 Dm給出了內(nèi)核從開機到關(guān)機這一過程的所有內(nèi)核數(shù)據(jù)訪問模式，描述了內(nèi)核的某一次運行過程中所有內(nèi)核數(shù)據(jù)在生命周期內(nèi)的使用情況。通過分析良性內(nèi)核和含惡意軟件運行的內(nèi)核的數(shù)據(jù)訪問模式差異，即可構(gòu)建惡意軟件數(shù)據(jù)特征，從而可以基于該特征檢測惡意軟件。

假設(shè)內(nèi)核惡意軟件M在第i次運行中對應(yīng)的數(shù)據(jù)訪問序列是 DM，j，不含惡意軟件的內(nèi)核在第j次運行中對應(yīng)的數(shù)據(jù)訪問序列為 DB，j，那么對k次惡意軟件運行和 l次良性內(nèi)核運行收集的數(shù)據(jù)訪問序列應(yīng)用集合操作得到內(nèi)核惡意軟件M的數(shù)據(jù)特征為

式（1）中 SM表示在k次內(nèi)核惡意軟件運行中均出現(xiàn)，但在 l次良好內(nèi)核運行中從未出現(xiàn)的數(shù)據(jù)訪問序列集合。

2.2 問題分析

前文已指出，隨著內(nèi)核惡意軟件樣本的增多，數(shù)據(jù)特征庫也隨之增大，這將導(dǎo)致基于數(shù)據(jù)特征的檢測效率大打折扣。據(jù)統(tǒng)計，新出現(xiàn)的惡意代碼大部分是在原惡意代碼基礎(chǔ)上修改轉(zhuǎn)換而來［12］，它們對內(nèi)核對象的篡改行為本質(zhì)上不會發(fā)生變化。故通過分析數(shù)據(jù)特征相似性，從相似的特征中選取代表特征，減少特征數(shù)，提高檢測效率。

聚類是按照事物的某些屬性，把事物聚集成簇，使簇內(nèi)的對象之間具有較高的相似性，而不同簇的對象之間的相似度較差［13，14］。因此，將聚類分析技術(shù)應(yīng)用于數(shù)據(jù)特征選擇能夠解決所述問題。

根據(jù)提取特征模型的差異，特征相似性計算方法主要包括余弦相似度、歐氏距離、Jaccard系數(shù)、最長公共子序列（Longest Common SubseQuent，LCSQ）等［15］。不同的計算方法使用的場景不同。余弦相似度、歐氏距離主要用于向量化特征的距離計算，要求特征具有方向和長度，適用于線性的特征模型。編輯距離、最長公共子串（Longest Common SubsTring， LCST）適用于字符串相似性比較，編輯距離通過統(tǒng)計刪除、插入、替換操作的次數(shù)計算距離，最長公共子串計算過程中要求子串在源串中連續(xù)；Jaccard系數(shù)考慮了兩個樣本特征的交集和并集，適用于特征項定義明確的樣本相似性計算；最長公共子序列適用于具有先后順序的特征相似性計算，譬如系統(tǒng)調(diào)用序列等；圖相似性計算一般采用圖匹配技術(shù)實現(xiàn)，適用于特征元素之間具有相互關(guān)系的特征相似性計算。

根據(jù)數(shù)據(jù)特征模型可知，數(shù)據(jù)特征是由五元式項組成的集合，該集合中的每一項元素之間不存在必然的先后順序。譬如對于系統(tǒng)調(diào)用表篡改操作，攻擊者修改了系統(tǒng)調(diào)用表表項的3個入口地址，這3個操作先后順序不影響攻擊者實現(xiàn)攻擊。它不同于向量化特征，可以沒有方向，長度動態(tài)變化，故余弦相似度、歐氏距離不適用于數(shù)據(jù)特征相似度計算；并且特征中沒有重復(fù)元素存在，元素之間并沒有先后順序，故編輯距離、最長公共子序列、最長公共子串也不適用。進一步分析數(shù)據(jù)特征項，五元式中前4個屬性取值唯一，最后一個屬性因偏移值存在單一取值和多值兩種情況，導(dǎo)致即使特征項不一樣也可以認為它們是同一個特征項。譬如（η， 1， 0，0xffffffff8180320，624）和（η， 1， 0， 0xffffffff8180320，｛120，624｝），由于624∈｛120，624｝，且元素的前4項完全一樣，所以我們認為（η， 1， 0， 0xffffffff8180320，624）和（η， 1， 0， 0xffffffff8180320，｛120，624｝）是同一個特征項。因此，對于數(shù)據(jù)特征，計算它們的相似性不能單純考慮完全一樣的特征項，還需考慮特征項的偏移關(guān)系。針對這些問題，借鑒最長公共子序列和最長公共子串，我們提出了最長公共子集，用于計算數(shù)據(jù)特征的相似性。

3 最長公共子集

根據(jù)上節(jié)的問題分析，數(shù)據(jù)特征相似性分析時必須將特征的每一項分為兩部分進行處理，那么最長公共子集可定義為：

定義3對于數(shù)據(jù)特征 S1，S2，它們的最長公共子集，其中S1∩ S2是特征項完全一致的公共部分，Sother是 S1中元素與 S2中元素的前4項均一致且偏移值項存在屬于或者包含關(guān)系的元素。

借鑒最長公共子串和最長公共子序列的定義，我們給出了最長公共子集距離度量函數(shù)的定義，見式（2）。

定理1d（S1， S2）是 ∑*的度量函數(shù)。

證明根據(jù)距離度量方法的定義，要證明d（S1，S2）是一個度量函數(shù)，必須證明該函數(shù)滿足以下度量屬性。

圖1 特征的最長公共子集關(guān)系

證畢

根據(jù)度量函數(shù)，特征相似性函數(shù)定義為

如果每個特征的長度均一致（對于長度不一致的特征，可以加入非特征元素使得兩個特征長度一致），不妨設(shè)長度為λ，那么相似性函數(shù)式（3）可簡化為

從式（4）可以看出，相似性取值只與最長公共子集相關(guān)。

4 基于最長公共子集的特征選擇方法

4.1 求解最長公共子集

根據(jù)最長公共子集的定義，其值包括兩部分，一部分是兩個特征交集元素的總數(shù)，另一部分是特征元素的偏移部分滿足給定關(guān)系的元素個數(shù)。因此，在求解最長公共子集時需要分別計算這兩部分的值。

現(xiàn)有的交集求解主要有兩種方法，一種是求解集合的所有子集，然后比較子集的一致性；另一種是雙重循環(huán)遍歷法，對兩個集合的所有元素進行一一比較，若相同則加入一個新的集合中，最終新集合中的所有元素構(gòu)成交集。

假設(shè)數(shù)據(jù)特征的長度為n，那么第1種方法的時間復(fù)雜度為 O （2n），第 2種方法的時間復(fù)雜度為O（n2）。對于復(fù)雜的樣本特征，它們的開銷較大。為此，本文提出了兩輪Hash求解法，依據(jù)Hash表中元素的唯一性實現(xiàn)最長公共子集的求解，每一輪求解一部分值，具體過程如表1所示的算法1。

不妨設(shè) S1， S2的特征長度為 n，那么根據(jù)算法1可知，算法的第6～17行為第1輪Hash求解最長公共子集的第1部分組成，其中第6， 7行、第8， 9行分別對特征進行預(yù)處理，各需要 O（n）的時間，第10， 11行是求解特征 S1的Hash表，需要 O（n）的時間，第12～17行求解特征 S1和 S2的子集，需要 O（n）的時間；算法的第19～27行為第2輪Hash計算，主要用于特殊處理特征元素中的偏移值項，其中第19， 20行處理去除偏移值項的特征 S1，需要 O（n）的時間，第21～27行進行偏移值關(guān)系比較，需要 O（n）的時間。因此，本算法的時間復(fù)雜度為 O（n）。該時間復(fù)雜度為線性時間復(fù)雜度，僅與特征長度相關(guān)，相較于上述兩種方法大大降低了求解最長公共子集的時間開銷。

表1 最長公共子集求解算法

4.2 基于最長公共子集的聚類算法

本節(jié)將介紹如何利用最長公共子集和相似度函數(shù)進行特征聚類。據(jù)不完全統(tǒng)計，內(nèi)核惡意軟件僅占惡意軟件的4%，數(shù)量相對較少。為此，本文選擇了適用于規(guī)模數(shù)較小的層次聚類算法［16］。按層次聚類分析中的合并實現(xiàn)方式，將特征樣本根據(jù)層次結(jié)構(gòu)方式進行合并，直到終止條件滿足為止。這里我們選擇自底向上的合并方式，并采用類間平均聚合方法AL計算新生成的類與各個舊類之間的相似度。

由于算法2中在聚類時加入了閾值判斷，故最好情況下只需進行1輪相似度計算，最壞情況下需要進行 n- 1輪相似度計算。但是不管是 1輪還是n- 1輪相似度計算，時間復(fù)雜度均為 n2量級，只是量級系數(shù)不一樣而已?？偟膩碚f，由于內(nèi)核惡意軟件樣本數(shù)遠小于應(yīng)用層惡意軟件，故聚類分析所需的時間可接受。

4.3 特征選擇

算法2將特征集最終構(gòu)成一棵分層聚類樹，下面對聚類樹進行劃分，然后從劃分類中選擇特征代表。文獻［17］指出，對聚類樹進行劃分時存在聚類數(shù)量和聚類規(guī)模的權(quán)衡問題，也就是“一致性”問題。本文借鑒不一致系數(shù)［17］對聚類樹進行剪枝，對聚類樹進行劃分，確定最終的分類個數(shù)。在聚類過程中，若某一次聚類所對應(yīng)的不一致系數(shù)較上次有較大幅度的增加，則表明該次聚類效果較差，而上次的聚類效果較好。增加的幅度越大，上次的聚類效果就越好。

不一致系數(shù)的計算時需要考慮當(dāng)前鏈接處向下的深度，即參與計算涉及的鏈接的層數(shù)。假設(shè)經(jīng)算法 2計算得到的聚類樹用數(shù)組 Z［m - 1］［4］存儲，其中m為特征樣本數(shù)，是某一行的取值，Si，Sj是聚類簇的編號，Sij是聚類后簇的編號，simij是兩個簇的相似度；M （k）表示第k次聚類時涉及的所有鏈接長度（即聚類相似度）的均值；SD（k）表示第k次聚類時涉及的所有鏈接長度的標(biāo)準(zhǔn)差，那么對于第k次聚類得到的鏈接，不一致系數(shù)為

表2 基于LCS的聚類算法

對于聚類樹的葉子節(jié)點，由于它們向下沒有其它節(jié)點，故當(dāng)它們聚類時，對應(yīng)的不一致系數(shù)為0。非葉子節(jié)點處的聚類，不一致系數(shù)按照式（5）計算。下面給出基于不一致系數(shù)的聚類樹劃分特征選擇算法SigSelect，如表3所示的算法3。

算法3首先根據(jù)不一致系數(shù)的求解方法計算得到各個聚類鏈接處的不一致系數(shù)（第1～7行），然后通過分析不一致系數(shù)和閾值的關(guān)系對聚類樹進行劃分（第8～32行），最后從M分類集合中選擇每一類的代表特征存入SM中（第33～35行）。其中算法3的1～7行的時間復(fù)雜度為 O（m ），第8～32行的時間復(fù)雜度也為 O（m ），第 33～35行的時間復(fù)雜度為O（i）， i為劃分的類數(shù)，i ≤ m，故算法3的時間復(fù)雜度仍為 O（m ）。

表3 特征選擇算法

選定特征之后，基于選定特征的內(nèi)核惡意軟件檢測過程如下：

（1）對于待檢測的軟件樣本，按照文獻［11］的方法提取該樣本的特征S；

（2）根據(jù)基于最長公共子集的特征相似計算方法計算該特征與所選擇特征的相似度，從中選擇相似度最大的值 Ssim，若 Ssim＞ θ，那么可判定該樣本屬于內(nèi)核惡意軟件，并給出其所屬的類別；否則判定其為正常軟件。

文獻［11］中的檢測方法時間復(fù)雜度為 O（mn2），而本文的檢測方法時間復(fù)雜度為 O（in），其中 m為特征庫樣本特征數(shù)，n為特征的長度，i為劃分的類數(shù)，i ≤ m。因此，本文的檢測方法優(yōu)于文獻［11］的檢測方法。

5 實驗分析

本節(jié)從聚類分析有效性、特征選擇有效性和性能3個方面對本文提出的方法進行評測。實驗環(huán)境如下：主機CPU為Intel（R） Core（TM） i5-750 @ 2.67 GHz，內(nèi)存大小4 GB，操作系統(tǒng)采用的是 3.2.43-x86_64內(nèi)核的Ubuntu 12.04。選擇了620種linux內(nèi)核惡意軟件樣本作為測試用例，其中610種用于聚類分析，10種用于驗證特征選擇的有效性。

5.1 聚類有效性

我們采用通用的聚類算法評價度量標(biāo)準(zhǔn)來驗證算法2的有效性，一是準(zhǔn)確率P，二是召回率R。準(zhǔn)確率用于驗證聚類算法區(qū)分不同樣本的能力；召回率用于驗證聚類算法識別相似樣本的能力；值越大表明聚類結(jié)果與真實情況越相似，聚類效果越好。

令聚類相似度閾值為0.7，那么算法2的準(zhǔn)確率P為0.985，召回率R為0.942，兩者取值均較高，這表明了算法2的有效性。

為了進一步驗證選擇最長公共子集進行數(shù)據(jù)特征聚類分析的合理性，我們實現(xiàn)了基于最長公共子串和最長公共子序列的特征聚類算法，這兩者與算法2僅相似度計算方法不同，其余均一致。在相同測試樣本和計算環(huán)境下，它們的準(zhǔn)確率和查重率對比如圖2所示。

從圖2中我們可以看出，基于最長公共子集的聚類算法的準(zhǔn)確率和召回率均是最高的。因此，選擇最長公共子集計算相似度是合理的，它更適合于數(shù)據(jù)特征這種數(shù)據(jù)組成的相似度計算。

圖2 不同聚類算法的準(zhǔn)確率和召回率

相似度閾值決定了兩個樣本是否是相似的。選擇一個合適的閾值通常取決于預(yù)期的聚類粒度級別。例如，分析者可能想要得到一個較為粗的分類，那么閾值就可以設(shè)置得小一些；如果分析者想要得到一個細粒度的分類，那么閾值就需要設(shè)得大一些。

為了驗證閾值選取的合理性，我們對不同閾值的聚類效果進行了統(tǒng)計分析，即對準(zhǔn)確率和召回率進行分析。圖3給出了準(zhǔn)確率和召回率隨著不同閾值的選擇的變化趨勢。從圖3中可以看出，閾值范圍為0.6～0.9可以得到較好的準(zhǔn)確率和召回率。

圖3 準(zhǔn)確率和召回率與閾值關(guān)系

5.2 特征選擇有效性

特征選擇有效性分析主要用于驗證選擇的特征集能夠有效區(qū)分不同的惡意軟件。首先我們給出了基于特征選擇算法得到的劃分結(jié)果，然后我們選擇了10款內(nèi)核惡意軟件來驗證選擇的特征的有效性。實驗結(jié)果如表4，表5所示。

從表4可知，測試樣例經(jīng)聚類劃分為14類，每一類的個數(shù)和選擇的惡意軟件代表分別對應(yīng)表4的第2列和第3列。

特征選擇確定后，對于未知的樣本，通過與每一類特征代表進行相似度計算判斷該樣本的歸屬。表5給出了待測的10個內(nèi)核惡意軟件的歸屬類別，與該類特征的相似度值，能否有效檢測等信息。從表5可以看出，所有的惡意軟件均歸類到某一類別中，說明特征選擇算法和檢測方法是有效的。

表4 惡意軟件劃分

表5 特征選擇有效性測試

5.3 性能測試

性能測試主要測試了聚類算法、特征選擇算法在給定樣本下的時間開銷，并測試了隨著閾值變化，聚類算法運行時間的變化情況，隨樣本變化，整體算法的運行時間開銷，以及基于聚類分析的檢測方法的時間開銷。

（1）固定樣本下的時間開銷： 在閾值 θ=0.7時，該方法的運行時間為 6128 ms，各部分運行時間如表6所示。

表6 各關(guān)鍵步驟運行時間（ms）

（2）閾值與運行時間關(guān)系： 圖4表明，閾值在達到 0.6前，聚類算法運行時間波動不大。當(dāng)閾值大于等于該值后，聚類算法運行時間大幅度降低，并且在閾值達到 0.9之后，聚類算法運行時間趨于平穩(wěn)。這也與準(zhǔn)確率和召回率的變化情況相吻合，當(dāng)閾值小于0.6時，樣本之間進行合并的幾率較大，合并次數(shù)較多，故需要較多的時間；當(dāng)閾值大于0.9時，樣本進行合并的幾率已經(jīng)很小，故算法所需時間變化不大，逐步趨于平穩(wěn)。

（3）樣本與運行時間關(guān)系： 在聚類算法閾值θ= 0.7時，通過不同的樣本測試算法的時間開銷，實驗結(jié)果如圖5所示。

從圖5可知，隨著樣本的增加，聚類算法所需的時間增加幅度較大，呈指數(shù)級增長，與上文分析的時間復(fù)雜度一致，特征算法選擇時間變化較小，呈線性變化趨勢，與上文分析的時間復(fù)雜度也一致。盡管在聚類時花費了較多時間，但這將為惡意軟件檢測提供較高的檢測效率。

（4）檢測方法時間開銷對比： 通過對不同待檢測樣本情況下的檢測時間開銷統(tǒng)計（不包括特征提取時間開銷），對比檢測方法的時間開銷。實驗結(jié)果如圖6所示。

圖4 閾值變化與算法運行時間關(guān)系

圖5 算法運行時間與樣本變化關(guān)系

圖6 檢測方法時間開銷

根據(jù)圖 6，本文的檢測方法時間開銷遠小于文獻［11］的方法，這與時間復(fù)雜度分析是相符合的。在樣本特征長度n一致的情況下，文獻［11］的檢測方法時間復(fù)雜度 O（mn2）可視為 O（m），本文的檢測方法時間復(fù)雜度 O（in）可視為 O（i），i ≤ m，m為樣本特征數(shù)，它們均與樣本數(shù)呈線性關(guān)系，差異在于系數(shù)不一樣。

6 結(jié)束語

本文深入研究了內(nèi)核惡意軟件檢測方法，尤其是基于數(shù)據(jù)特征的檢測方法。數(shù)據(jù)特征描述了惡意軟件對內(nèi)核對象的篡改操作，能夠較好地適用于檢測內(nèi)核惡意軟件。但由于隨著樣本特征的增多，基于數(shù)據(jù)特征的檢測方法效率隨之降低，故研究了基于聚類分析的特征選擇方法。該方法首先分析了現(xiàn)有特征相似性計算方法用于數(shù)據(jù)特征計算時存在的不足，提出了最長公共子集算法，然后討論了基于最長公共子集的特征相似性計算和特征選擇算法，這使得該方法可快速地對未知樣本進行分析和分類，從而提高惡意軟件檢測效率。最后通過實驗驗證了該方法的有效性。下一步工作研究將基于最長公共子集的相似度計算應(yīng)用于其它聚類算法的有效性和性能。

［1］ Yin H， Song D， Egele M， et al.. Panorama: capturing systemwide information flow for malware detection and analysis［C］. Proceedings of the 14th ACM Conference on Computer and Communications Security， Alexandria， USA， 2007: 116-127.

［2］ 王蕊， 馮登國， 楊軼， 等. 基于語義的惡意代碼行為特征提取及檢測方法［J］. 軟件學(xué)報， 2012， 23（2）: 378-393. Wang Rui， Feng Deng-guo， Yang Yi， et al.. Semantics-based malware behavior signature extraction and detection method［J］. Journal of Software， 2012， 23（2）: 378-393.

［3］ Nataraj L， Karthikeyan S， Jacob G， et al.. Malware images: visualization and automatic classification［C］. Proceedings of the 8th International Symposium on Visualization for Cyber Security， Pittsburg， PA， USA， 2011: 4-10.

［4］ Nataraj L， Yegneswaran V， Porras P， et al.. A comparative assessment of malware classification using binary texture analysis and dynamic analysis［C］. Proceedings of the 4th ACM Workshop on Security and Artificial Intelligence，Chicago， USA， 2011: 21-30.

［5］ 韓曉光， 曲武， 姚宣霞， 等. 基于紋理指紋的惡意代碼變種檢測方法研究［J］. 通信學(xué)報， 2014， 35（8）: 125-136. Han Xiao-guang， Qu Wu， Yao Xuan-xia， et al.. Research on malicious code variants detection based on texture fingerprint［J］. Journal of Communications， 2014， 35（8）: 125-136.

［6］ Ding Yun-xin， Dai Wei， Yan Sheng-li， et al.. Control flowbased opcode behavior analysis for malware detection［J］. Computer & Security， 2014， 44: 65-74.

［7］ Wang X and Karri R. NumChecker: detecting kernel controlflow modifying rootkits by using hardware performance counters［C］. Proceedings of the 50th Annual DesignAutomation Conference， Austin， TX， USA， 2013: 79-86.

［8］ Debbabi M， Desharnais J， et al.. Static detection of malicious code in executable programs［J］. Intermational Journal of Requirement Engineering， 2001（184-189）: 79-86.

［9］ Baliga A， Ganapathy V， and Iftode L. Detecting kernel-level rootkits using data structure invariants［J］. IEEE Transactions on Dependable and Secure Computing， 2011，8（5）: 670-684.

［10］ Zhu F. Integrity-based kernel malware detection［D］. ［Ph.D. dissertation］， Florida International University， 2014.

［11］ Rhee J， Riley R， Lin Z Q， et al.. Data-centric OS kernel malware characterization［J］. IEEE Transactions on Information Forensics and Security， 2014， 9（1）: 72-87.

［12］ Tumer D， Entwisle S， Fossi M， et al.. Symantec Internet security thread report 2014［R］. Symantec Corporation， 2014.

［13］ 陳季夢， 陳佳俊， 劉杰， 等. 基于結(jié)構(gòu)相似度的大規(guī)模社交網(wǎng)絡(luò)聚類算法［J］. 電子與信息學(xué)報， 2015， 37（2）: 449-454. Chen Ji-meng， Chen Jia-jun， Liu Jie， et al.. Clustering algorithms for large-scale social networks based on structural similarity［J］. Journal of Electronics & Information Technology， 2015， 37（2）: 449-454.

［14］ Ciprian O， George C， and Gheorghe S. Malware clustering using suffix trees［J］. Journal of Computer Virology Hacking Techniques， 2014， DOI: 10.1007/s11416-014-0227-6.

［15］ 戚樹慧. 基于指令分析的惡意代碼分類與檢測研究［D］. ［碩士論文］， 杭州電子科技大學(xué)， 2012. Qi Shu-hui. Research into malware classification and detection based on instruction analysis［D］. ［Master dissertation］， Hangzhou Dianzi University， 2012.

［16］ 羅養(yǎng)霞， 房鼎益. 基于聚類分析的軟件胎記特征選擇［J］. 電子學(xué)報， 2013， 41（12）: 2334-2338. Luo Yang-xia and Fang Ding-yi. Feature selection for software birthmark based on cluster analysis［J］. Acta Electronica Sinica， 2013， 41（12）: 2334-2338.

［17］ Bailey M， Oberheide J， Andersen J， et al.. Automated classification and analysis of internet malware［C］. Proceedings of the 10th Symposium on Recent Advances in Intrusion Detection， Gold Coast， Australia， 2007: 178-197.

陳志鋒： 男，1986年生，博士生，研究方向為信息安全與可信計算.

李清寶： 男，1967年生，教授，研究方向為信息安全與可信計算.

張 平： 女，1969年生，副教授，研究方向為并行識別、信息安全.

馮培鈞： 男，1990年生，博士生，研究方向為信息安全.

Signature Selection for Kernel Malware Based on Cluster Analysis

Chen Zhi-feng Li Qing-bao Zhang Ping Feng Pei-jun
（PLA Information Engineering University， Zhengzhou 450001， China）（State Key Laboratory of Mathematical Engineering and Advanced Computing， Zhengzhou 450001， China）

As current kernel malware detection method based on data signature exists the problem that its efficiency decreases with the growth of the number of signatures， a signature selection method for kernel malware based on hierarchical cluster is presented. First， since current similarity calculation methods are difficult to be applied to data signature selection， a longest common subset based method and a 2-round Hash computation algorithm are introduced. Second， a longest common subset based hierarchical cluster algorithm is presented，thereby performing similar signature aggregation effectively. Finally， a signature selection algorithm based on inconsistent coefficient is designed to reduce the number of signatures. Experimental results show the effectiveness of the method， and performance evaluations indicate that algorithm runtime is acceptable.

Data signature； Longest common subset； Hierarchical cluster； Signature selection； Kernel malware

s: The National Science and Technology Major Project of China （2013JH00103）； The National 863 Program of China （2009AA01Z434）

TP316； TP309

A

1009-5896（2015）12-2821-09

10.11999/JEIT150387

2015-04-02；改回日期：2015-07-30；網(wǎng)絡(luò)出版：2015-10-16

*通信作者：陳志鋒 516975104@qq.com

核高基國家科技重大專項（2013JH00103）和國家863計劃目標(biāo)導(dǎo)向項目（2009AA01Z434）