基于肯定選擇分類算法的惡意代碼檢測方法*

張福勇，趙鐵柱

(東莞理工學(xué)院 計算機(jī)學(xué)院，廣東 東莞 523808)

?

基于肯定選擇分類算法的惡意代碼檢測方法*

張福勇，趙鐵柱

(東莞理工學(xué)院 計算機(jī)學(xué)院，廣東 東莞 523808)

針對惡意代碼，尤其是頑固、隱匿的未知惡意代碼危害日益加劇的問題，提出一種基于肯定選擇分類算法的惡意代碼檢測方法.將樣本文件轉(zhuǎn)換成十六進(jìn)制格式，提取樣本文件的所有n-gram，計算具有最大信息增益的N個n-gram的詞頻，并做歸一化處理，采用改進(jìn)的肯定選擇分類算法進(jìn)行分類.該方法保留了肯定選擇分類算法高分類準(zhǔn)確率的優(yōu)點(diǎn)，優(yōu)化了分類器訓(xùn)練過程，提高了訓(xùn)練和檢測效率.結(jié)果表明，該方法的檢測效果優(yōu)于樸素貝葉斯、貝葉斯網(wǎng)絡(luò)、支持向量機(jī)和C4.5決策樹等算法.

網(wǎng)絡(luò)與信息安全；入侵檢測；惡意代碼；惡意代碼檢測；肯定選擇分類算法；機(jī)器學(xué)習(xí)；特征選擇；靜態(tài)分析

惡意代碼，尤其是頑固、隱匿的未知惡意代碼的危害日益加劇[1]，吸引了大批工業(yè)界和學(xué)術(shù)界的科研人員對其進(jìn)行檢測研究.針對惡意代碼的靜態(tài)自動分析方法和動態(tài)自動分析方法是目前的研究熱點(diǎn).

靜態(tài)分析方法指在不執(zhí)行二進(jìn)制程序的情況下，對樣本的靜態(tài)特征和功能進(jìn)行分析[2].常見的靜態(tài)分析方法有：基于靜態(tài)行為的系統(tǒng)調(diào)用序列分析方法[3]，基于抽象語義的惡意代碼分析方法[4]，提取樣本文件的n-gram字節(jié)特征的檢測方法[5-6]及通過挖掘PE文件靜態(tài)格式信息實(shí)現(xiàn)惡意代碼檢測的方法[7]等.

動態(tài)行為分析方法主要是對代碼運(yùn)行過程中系統(tǒng)基本屬性、系統(tǒng)調(diào)用、I/O請求、控制流、網(wǎng)絡(luò)行為、寄存器值及內(nèi)存中變量值的變化等幾個方面進(jìn)行監(jiān)控，進(jìn)而分析惡意代碼的行為.常見的動態(tài)分析方法有：基于系統(tǒng)基本屬性的分析方法[8]，基于動態(tài)行為的系統(tǒng)調(diào)用序列分析方法[9]，基于IRP序列的檢測方法[10]，基于控制流的檢測方法[11]，基于網(wǎng)絡(luò)行為的檢測方法[12]，基于寄存器值及內(nèi)存中變量值變化的檢測方法[13-15]及靜態(tài)特征和動態(tài)特征相結(jié)合的檢測方法[16]等.

惡意代碼的自動分析檢測方法雖然近年有了長足的發(fā)展，但依然存在一些缺陷，對惡意代碼實(shí)時檢測的研究還不夠成熟，還需要更多創(chuàng)新性的工作[17].

本文提出一種基于肯定選擇分類算法惡意代碼檢測方法，該方法提取樣本文件具有最大信息增益的N個n-gram字節(jié)，計算每1 000字節(jié)中每個n-gram的詞頻，并做歸一化處理，得到一個N維特征向量，然后，采用改進(jìn)的肯定選擇分類算法判斷其類別.實(shí)驗結(jié)果表明，該方法可實(shí)現(xiàn)惡意代碼的快速準(zhǔn)確檢測.

1　特征選擇方法

基于n-gram字節(jié)的惡意代碼檢測方法[5]已經(jīng)被廣泛采用，且取得了較好的檢測效果.目前采用最廣泛的基于n-gram字節(jié)的檢測方法是Jeremy等人[5]提出的，該方法提取樣本文件信息增益最大的N個n-gram作為特征數(shù)據(jù).檢測時，逐一判斷待測文件中是否存在N個n-gram中的某一個，如果存在則將對應(yīng)屬性值置為1，否則置為0，最終得到一個N維的特征向量.然后，選用合適的分類算法進(jìn)行類別判斷，這種方法最終得到的是N維特征向量，向量中屬性的取值為0或1.而僅包含0和1的數(shù)據(jù)并不利于分類算法學(xué)習(xí)得到最佳的分類器，因此，考慮在提取的具有最大信息增益的N個n-gram的基礎(chǔ)上，計算每個n-gram的詞頻，并對詞頻數(shù)據(jù)做歸一化處理，這樣得到的特征數(shù)據(jù)就不再是僅有0和1的數(shù)據(jù)，而是取值范圍在[0，1]的數(shù)據(jù)，這樣的數(shù)據(jù)更有利于分類算法的學(xué)習(xí)和樣本的識別.特征向量生成算法如下：

1) 提取樣本文件的所有n-gram，這里的n-gram指的是將樣本文件轉(zhuǎn)成十六進(jìn)制后的連續(xù)n個字節(jié).假設(shè)n=4，一個樣本文件轉(zhuǎn)成十六進(jìn)制后的字節(jié)序列為：4D 5A 90 00 03 00，則該文件的所有n-gram為：4D5A9000、5A900003、90000300.

2) 計算所有n-gram的信息增益，并提取具有最大信息增益的N個n-gram.

3) 針對具有最大信息增益的N個n-gram，計算樣本文件中包含的每個n-gram的數(shù)量，并除以樣本文件長度，不足1 kB按1 kB處理.例如，一個樣本文件長度為1 124 B，則其表示的文件長度為2 kB，最終得到的是一個N維向量，向量屬性值為樣本文件每1 kB包含的n-gram數(shù)量.

4) 對步驟3)得到的N維向量做歸一化處理，處理后的N維向量中屬性的取值范圍為[0，1].例如，取N=5，最后得到的N維向量形式為：0.012 085、0.024 169、0.048 338、0.012 085、0.012 085.

2　改進(jìn)的肯定選擇分類算法

肯定選擇分類算法(positive selection classification algorithm，PSCA)[18-19]是基于人工免疫系統(tǒng)中肯定選擇原理和克隆選擇原理提出的一種分類算法，該算法在一些基準(zhǔn)數(shù)據(jù)集上測試取得了很好的實(shí)驗結(jié)果.但其在選擇最優(yōu)分類器時采用克隆選擇原理，導(dǎo)致算法訓(xùn)練時間過長，而經(jīng)過大量實(shí)驗發(fā)現(xiàn)，克隆選擇原理在選擇最優(yōu)分類器時幫助并不大，為了保證惡意代碼檢測的高時效性，本文對肯定選擇分類算法進(jìn)行了一些改進(jìn)，去除了不必要的克隆選擇過程，并優(yōu)化了算法實(shí)現(xiàn)流程，確保在不降低分類準(zhǔn)確率的前提下，進(jìn)一步提高分類效率.下面給出改進(jìn)后算法中用到的符號定義：

D：樣本集；

d：樣本數(shù)據(jù)，d∈D；

da：d的屬性向量；

dai：da的第i個屬性值；

df：d的識別標(biāo)志；

mc：樣本中的類別個數(shù)；

Di：第i個類別的樣本集，Di?D，D={D1∪D2∪…∪Dmc}；

C：分類器集合；

Ci：第i個類別的分類器集合，Ci?C，C={C1∪C2∪…∪Cmc}；

c：分類器，c∈C；

ca：c的屬性向量；

cr：c的識別半徑(如果d到c的距離小于cr，則認(rèn)為c能夠識別d，本文的距離采用歐幾里得距離公式計算)；

cs：c的識別值(cs指僅被分類器c識別的樣本數(shù))；

chs：c的半識別值(chs指同時被分類器c和至少一個其它分類器識別的樣本數(shù)).

2.1學(xué)習(xí)過程

學(xué)習(xí)過程分別對每個類別的樣本進(jìn)行學(xué)習(xí)，將正在學(xué)習(xí)的該類別樣本作為自體，其它類別的樣本作為非自體，最終訓(xùn)練得到各個類別樣本的分類器.學(xué)習(xí)過程的符號定義及相關(guān)函數(shù)描述如下：

S：自體樣本集，S=Di；

s：自體樣本，s∈S；

SN：非自體樣本集，SN={D1∪D2∪…∪Di-1∪Di+1∪…∪Dmc}；

sn：非自體樣本，sn∈SN；

distSort(S，SN)：將S中每個自體樣本到SN中所有非自體樣本距離的最小值，按從大到小進(jìn)行排序；

getClassifier(s，S，SN)：生成一個分類器，且該分類器類別與s相同；

setRadius(c，SN)：設(shè)置cr的值；

setStimulation(c，S)：設(shè)置cs和chs的值；

recognize(c，s)：如果s到c的距離小于cr，返回true；否則，返回false.

改進(jìn)的肯定選擇分類算法的學(xué)習(xí)過程見算法1.

算法1.學(xué)習(xí)過程

for each Di(S) in D

Ci←?；

distSort(S，SN)；

distant[k].f←flase；

end for

if distant[i].f←false

c←getClassifier(distant[i]，S，SN)；

Ci←Ci∪c；

end if

if recognize(c，distant [j])

distant [j].f←true；

end if

end for

end for

end for

學(xué)習(xí)過程首先計算每一個自體樣本s到所有非自體樣本sn距離的最小值，并根據(jù)這些值按由大到小的順序，將自體樣本集S進(jìn)行排序，并將這些樣本標(biāo)示為未識別.然后，選擇第一個未被識別的自體樣本作為分類器，并設(shè)置該分類器的屬性值、識別半徑、識別值及半識別值，同時將此分類器識別的自體樣本標(biāo)識為已識別，再選擇下一個未識別的自體樣本作為分類器，如此循環(huán)，直到所有自體樣本都被識別.

算法2描述了函數(shù)getClassifier(s，S，SN)的詳細(xì)過程，其中識別半徑的設(shè)置函數(shù)setRadius(c，SN)計算公式為

cr=minDist_c(c，SN)α

(4)

式中：minDist_c(c，SN)指分類器c到SN中所有非自體樣本距離的最小值；α為識別半徑控制參數(shù)，α∈(0，1).

算法2.getClassifier(s，S，SN)

ca←s；

cr←setRadius(c，SN)；

c←setStimulation(c，S)；

return c；

算法3描述了分類器識別值和半識別值設(shè)置函數(shù)setStimulation(c，S)的具體過程.

算法3.setStimulation(c，S)

cs←0；

chs←0；

for each s in S

if recognize(c，s)←true

if chs←chs+1；

else cs←cs+1；

end if

end if

end for

return c；

2.2分類過程

分類過程的處理方式與文獻(xiàn)[18]中的方法一致，對于分類過程中出現(xiàn)重疊的情況，采用臨時移動分類器至兩分類器相切的位置.對孔洞的處理采用k最近鄰算法，并選擇k=3.分類過程的處理流程為：

1) 選擇一個測試樣本，用學(xué)習(xí)過程生成的分類器進(jìn)行識別.

2) 若只有一個類別的分類器識別此樣本，則確定此樣本類別為識別它的分類器類別，轉(zhuǎn)步驟1)；若出現(xiàn)重疊情況，轉(zhuǎn)步驟3)；若出現(xiàn)孔洞情況，轉(zhuǎn)步驟4).

3) 重疊情況的識別過程.

4) 孔洞情況的識別過程.

3　實(shí)驗結(jié)果及分析

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

實(shí)驗中用到的樣本文件信息如表1所示.其中，惡意代碼樣本108個，正常文件樣本114個，均為Win32 PE格式.

表1　實(shí)驗數(shù)據(jù)

3.2檢測器半徑控制參數(shù)α的敏感性分析

本節(jié)隨機(jī)選擇了惡意代碼樣本88個，正常文件樣本83個來分析參數(shù)α取不同值時對分類結(jié)果的影響.采用10折交叉驗證進(jìn)行測試，圖1顯示了α取值范圍為0.05～0.95時的分類準(zhǔn)確率情況.從圖1可以看出，α的取值對分類準(zhǔn)確率的影響不大，得到分類準(zhǔn)確率的范圍為98.25%～99.42%，其中0.05≤α≤0.45時，可以得到最優(yōu)結(jié)果.

圖1　α對分類準(zhǔn)確率的影響

3.3實(shí)驗結(jié)果比較與分析

前期研究中，測試了N取值為2，3，4，5，6，7，8，9，10，15，20，50等數(shù)據(jù)，n取值為1，2，3，4等數(shù)據(jù)的各種組合形式，發(fā)現(xiàn)N取值為5，n取值為3時可得到最佳的檢測結(jié)果.因此，本文實(shí)驗中N和n取值分別為5和3，即提取最大信息增益的前5個3-gram字節(jié)生成特征向量，并將本文算法與樸素貝葉斯(Na?ve Bayes，NB)、貝葉斯網(wǎng)絡(luò)(Bayesian Networks，BN)、支持向量機(jī)(Support Vector Machine，SVM)和C4.5決策樹(C4.5 Decision Tree，DT)4種分類算法進(jìn)行比較.這4種分類算法方法均采用WEKA平臺，4種方法分別采用WEKA的Na?veBayes、BayesNet、SMO和J48實(shí)現(xiàn).

實(shí)驗中信息增益的計算以3.2節(jié)的171個樣本文件為依據(jù)，并比較從這171個樣本中提取的檢測結(jié)果，實(shí)驗結(jié)果如表2所示，所有結(jié)果均為10折交叉驗證的結(jié)果.本文方法的結(jié)果為α取0.05，0.1，0.15，…，0.9，0.95，19個數(shù)據(jù)實(shí)驗結(jié)果的平均值，其他4種方法的實(shí)驗結(jié)果均采用WEKA平臺的默認(rèn)參數(shù).

表2　實(shí)驗結(jié)果

從表2可以看出，本文方法得到的分類準(zhǔn)確率最高，并且擁有最低的誤檢率(FP).對惡意代碼的檢測率(TP)方面，本文方法與BayesNet最高均為96.3%，但BayesNet的FP高于本文方法.C4.5和Na?ve Bayes兩種方法的FP稍高，檢測結(jié)果不理想.值得注意的是SVM方法在實(shí)驗中獲得了100%的TP，但同時FP也高達(dá)26.3%，說明SVM方法不適用于該類特征的分類.

實(shí)驗結(jié)果表明，本文提出的基于肯定選擇分類算法的惡意代碼檢測方法具有較好的檢測結(jié)果，而且所需提取的特征數(shù)量少，可實(shí)現(xiàn)對惡意代碼的快速準(zhǔn)確檢測.

4　結(jié)　論

針對當(dāng)前惡意代碼數(shù)量大、檢測難的現(xiàn)狀，本文提出一種基于肯定選擇算法的惡意代碼檢測方法.該方法從訓(xùn)練樣本中提取5個具有最大信息增益的3-gram字節(jié)，并通過計算3-gram詞頻的方式生成特征向量，實(shí)現(xiàn)了較高的惡意代碼檢測率和較低的誤檢率，并且該方法僅需對少量樣本的學(xué)習(xí)即可實(shí)現(xiàn)對未知惡意代碼的準(zhǔn)確識別，是一種高效的檢測方法.

[1]360互聯(lián)網(wǎng)安全中心.2012年中國互聯(lián)網(wǎng)安全報告[EB/OL].北京：360互聯(lián)網(wǎng)安全中心，2013(2013-02-25) [2015-04-30].http://awuvsvkkjf.l5.yunpan.cn/lk/QUPZKyLbVTBTH.

(360 Internet Security Center.2012 China’s internet security report [EB/OL].Beijing：360 Internet Secu-rity Center，2013(2013-02-25) [2015-04-30].http://awuvsvkkjf.l5.yunpan.cn/lk/QUPZKyLbVTBTH.)

[2]李鵬，王汝傳，武寧.基于空間關(guān)系特征的未知惡意代碼自動檢測技術(shù)研究 [J].計算機(jī)研究與發(fā)展，2012，49(5)：949-957.

(LI Peng，WANG Ru-chuan，WU Ning.Research on unknown malicious code automatic detection based on space relevance features [J].Journal of Computer Research and Development，2012，49(5)：949-957.)

[3]Ding Y X，Yuan X B，Tang K，et al.A fast malware detection algorithm based on objective-oriented associa-tion mining [J].Computers & Security，2013，39：315-324.

[4]Silvio C，Yang X，Zhou W L.Control flow-based malware variant detection [J].IEEE Transactions on Dependable and Secure Computing，2014，11(4)：304-317.

[5]Kolter J Z，Marcus A.Learning to detect malicious executables in the wild [C]//Knowledge Discovery and Data Mining.New York，USA，2004：470-478.

[6]Nissim N，Robert M，Lior R，et al.Novel active learning methods for enhanced PC malware detection in windows OS [J].Expert Systems with Applications，2014，41(13)：5843-5857.

[7]Bai J R，Wang J F，Zou G Z.A malware detection scheme based on mining format information [J].The Scientific World Journal，2014，15(2)：1-11.

[8]Zhang M，Anand R，Niraj K.A defense framework against malware and vulnerability exploits [J].International Journal of Information Security，2014，13(5)：439-452.

[9]Forrest S，Hofmeyr S，Somayaji T.A sense of self for unix processes [C]//IEEE Symposium on Security and Privacy.Berlin，German，1996：120-128.

[10]張福勇，齊德昱，胡鏡林.終身學(xué)習(xí)的否定選擇算法 [J].沈陽工業(yè)大學(xué)學(xué)報，2012，34(3)：393-397.

(ZHANG Fu-yong，QI De-yu，HU Jing-lin.Negative selection algorithm for life-long learning [J].Journal of Shenyang University of Technology，2012，34(3)：393-397.)

[11]Shahid A，Nigel R.A framework for metamorphic malware analysis and real-time detection [J].Computers & Security，2015，48：212-233.

[12]Prakash M C，Lei L，Sabyasachi S.Combining supervised and unsupervised learning for zero-day malware detection [C]//32nd IEEE INFOCOM Conference.Turin，Italy，2013：2022-2030.

[13]Shahzad F，Shahzad M，F(xiàn)arooq M.In-execution dynamic malware analysis and detection by mining information in process control blocks of Linux OS [J].Information Sciences，2013，231：45-63.

[14]Mahboobe G，Ashkan S，Zahra S.Dynamic malware detection using registers values set analysis [C]//9th International ISC Conference on Information Security and Cryptology(ISCISC).Tabriz，Iran，2012：54-59.

[15]Nguyen V，Nguyen T C，Cao D T.Semantic set analysis for malware detection [C]//13th IFIP TC8 International Conference on Computer Information Systems and Industrial Management Applications(CISIM).Hochi Minh，Vietnam，2014：688-700.

[16]Rafiqul I，Lynn M.Classification of malware based on integrated static and dynamic features [J].Journal of Network and Computer Applications，2013，36(2)：646-656.

[17]趙剛，宮義山，王大力.考慮成本與要素關(guān)系的信息安全風(fēng)險分析模型 [J].沈陽工業(yè)大學(xué)報，2015，37(1)：69-74.

(ZHAO Gang，GONG Yi-shan，WANG Da-li.Information security risk analysis model considering costs and factors relevance [J].Journal of Shenyang University of Technology，2015，37(1)：69-74.)

[18]張福勇.面向惡意代碼檢測的人工免疫算法研究 [D].廣州：華南理工大學(xué)，2012：58-77.

(ZHANG Fu-yong.Research on artificial immune algorithms on malware detection [D].Guangzhou：South China University of Technology，2012：58-77.)

[19]Zhang F Y，Qi D Y.A positive selection algorithm for classification [J].Journal of Computational Information Systems，2012，8(1)：207-215.

(責(zé)任編輯：景勇英文審校：尹淑英)

Malware detection method based on positive selection classification algorithm

ZHANG Fu-yong,ZHAO Tie-zhu

(Computer Institute,Dongguan University of Technology,Dongguan 523808,China)

In order to solve the problem that the harm of malware,especially the persistent and stealthy unknown malware becomes more serious,a malware detection method based on positive selection classification algorithm was proposed.The sample files were converted into hexadecimal format,and all n-grams of sample files were extracted.The word frequency of N n-grams with maximum information-gain was calculated and normalized.The improved positive selection classification algorithm was used to perform the classification.The present method retains the high classification accuracy of positive selection classification algorithm,optimizes the training process of classifier,and improves the efficiency of training and detection.The results reveal that the detection efficiency of the present method is prior to that of such algorithms as Na?ve Bayes,Bayesian Networks,support vector machine and C4.5 decision tree.

network and information security; intrusion detection; malware; malware detection; positive selection classification algorithm; machine learning; feature selection; static analysis

2015-06-15.

國家自然科學(xué)基金資助項目(61402106)；廣東省教育科學(xué)規(guī)劃資助項目(14JXN029).

張福勇(1982-)，男，山東龍口人，講師，博士，主要從事網(wǎng)絡(luò)與信息安全等方面的研究.

10.7688/j.issn.1000-1646.2016.02.16

TP 309

A

1000-1646(2016)02-0206-05

*本文已于2015-09-15 00∶01在中國知網(wǎng)優(yōu)先數(shù)字出版.網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/21.1189.T.20150915.0001.008.html