一種應(yīng)用機(jī)器學(xué)習(xí)和D-S證據(jù)理論的Linux病毒檢測(cè)方案*

黃一峰，黃俊偉，吳戀

(重慶郵電大學(xué)新一代寬帶移動(dòng)通信終端研究所，重慶 400065)

?

一種應(yīng)用機(jī)器學(xué)習(xí)和D-S證據(jù)理論的Linux病毒檢測(cè)方案*

黃一峰，黃俊偉，吳戀

(重慶郵電大學(xué)新一代寬帶移動(dòng)通信終端研究所，重慶 400065)

設(shè)計(jì)了一種應(yīng)用機(jī)器學(xué)習(xí)和D-S證據(jù)理論來進(jìn)行Linux病毒檢測(cè)的方案。主要包括方案的總體框架、樣本特征選擇方法、分類器選擇、檢測(cè)效果融合以及方案驗(yàn)證與結(jié)果分析等。在樣本特征選擇時(shí)引入了控制流程圖的概念，在檢測(cè)效果融合時(shí)使用了D-S證據(jù)理論的方法。最后在基于Weka軟件的機(jī)器學(xué)習(xí)平臺(tái)上實(shí)現(xiàn)和測(cè)試了該方案。驗(yàn)證結(jié)果表明，該Linux病毒檢測(cè)方案具有良好的檢測(cè)率和可靠性，可以應(yīng)用于實(shí)際的商業(yè)產(chǎn)品中。

Linux系統(tǒng)；病毒檢測(cè)；機(jī)器學(xué)習(xí)；D-S證據(jù)理論；控制流程圖

引 言

計(jì)算機(jī)病毒檢測(cè)可以看作是機(jī)器學(xué)習(xí)理論中的二分類問題。機(jī)器學(xué)習(xí)理論在病毒檢測(cè)中已經(jīng)得到應(yīng)用，但目前的研究多數(shù)是針對(duì)于Windows操作系統(tǒng)平臺(tái), 對(duì)Linux平臺(tái)少有涉及。參考文獻(xiàn)[1]介紹了機(jī)器學(xué)習(xí)在病毒檢測(cè)中的一般流程。這些研究表明，機(jī)器學(xué)習(xí)在病毒檢測(cè)中的表現(xiàn)優(yōu)于傳統(tǒng)的基于特征碼對(duì)比的檢測(cè)方式。

近年來，隨著Android等基于Linux核心的衍生操作系統(tǒng)的流行，Linux操作系統(tǒng)平臺(tái)下病毒檢測(cè)與防治的重要性日益凸顯。大致來說，Windows平臺(tái)下的病毒檢測(cè)思路可以為L(zhǎng)inux下病毒檢測(cè)提供借鑒。但兩種操作系統(tǒng)在可執(zhí)行文件格式、系統(tǒng)調(diào)用方式、內(nèi)核空間劃分等方面存在差異，因此有必要對(duì)Linux下的病毒檢測(cè)進(jìn)行具體的研究。

本文結(jié)合機(jī)器學(xué)習(xí)理論中分類問題的處理框架，提出了一種Linux病毒檢測(cè)方案。包括檢測(cè)系統(tǒng)的整體框架設(shè)計(jì)，特征選擇預(yù)處理流程、以及基于D-S理論的對(duì)檢測(cè)結(jié)果的整合流程。

在基于Weka軟件的機(jī)器學(xué)習(xí)平臺(tái)上實(shí)現(xiàn)本文提出的方案，在檢測(cè)準(zhǔn)確率、誤判率等方面都得到較好的實(shí)驗(yàn)結(jié)果，驗(yàn)證了本文設(shè)計(jì)的可靠性和可行性。

1 檢測(cè)系統(tǒng)方案設(shè)計(jì)

1.1 檢測(cè)系統(tǒng)總體框架

本文提出的Linux病毒檢測(cè)方案主要包括規(guī)則生成和病毒檢測(cè)兩個(gè)部分，如圖1所示。

圖1 Linux病毒檢測(cè)方案整體框架

在生成判決規(guī)則時(shí)，首先需要獲取一定量的訓(xùn)練樣本(包括病毒和正常文件)，然后從這些樣本中提取出代表其特性的樣本特征，最后將這些樣本特征輸入到機(jī)器學(xué)習(xí)分類器中，生成病毒判決規(guī)則。在這個(gè)過程中樣本特征的提取方法和分類器的選擇對(duì)系統(tǒng)的檢測(cè)性能有重要影響，因此是規(guī)則生成模塊的主要關(guān)注點(diǎn)。

病毒檢測(cè)部分則是在提取待檢測(cè)文件的樣本特征后，利用前面生成的規(guī)則對(duì)其進(jìn)行判決(病毒還是正常文件)，這里的側(cè)重點(diǎn)是對(duì)系統(tǒng)檢測(cè)性能的評(píng)估。

1.2 樣本特征提取

對(duì)于樣本特征的提取選擇動(dòng)態(tài)(dynamic)和靜態(tài)(static)兩種方式。這樣可以最小化兩種檢測(cè)方式的關(guān)聯(lián)性，提高最后檢測(cè)結(jié)果融合的效果。

這里動(dòng)態(tài)特征選擇的是程序流程控制圖(CFG)，靜態(tài)特征選擇為ELF代碼段特征。

1.2.1 基于CFG的特征

現(xiàn)代的軟件工程學(xué)把軟件的內(nèi)部拓?fù)浣Y(jié)構(gòu)視為一個(gè)有序的網(wǎng)絡(luò)(network)，代表了軟件的內(nèi)部控制流程和語義結(jié)構(gòu)等信息[2]。通過CFG，可以表示軟件內(nèi)部的拓?fù)渚W(wǎng)絡(luò)，提取出所需要的特征向量，進(jìn)而作為病毒判決的依據(jù)。具體操作如下：

① 使用反匯編工具IDA Pro，將文件的二進(jìn)制代碼轉(zhuǎn)換成匯編語言，并且生成其軟件CFG。將函數(shù)作為CFG的最小組織單位，一個(gè)函數(shù)為一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，節(jié)點(diǎn)之間的連線表示函數(shù)間的調(diào)用關(guān)系。

② 根據(jù)每個(gè)函數(shù)在虛擬內(nèi)存中的位置為其編號(hào)，作為CFG中節(jié)點(diǎn)的標(biāo)識(shí)。

③ 定義需要從CFG提取的特征，包括節(jié)點(diǎn)數(shù)量(開始節(jié)點(diǎn)、結(jié)束節(jié)點(diǎn)、孤立節(jié)點(diǎn)等),連線數(shù)量,孤立子圖數(shù)量等。

④ 使用一定的統(tǒng)計(jì)學(xué)方法從CFG中提取出特征，在本文中使用鄰接表(adjacency list)保存CFG中的特征。

最后獲得的部分特征如表1所列。從表中可以得到一些有用的信息，如正常文件的連線數(shù)和節(jié)點(diǎn)總數(shù)均大于病毒，表明正常文件內(nèi)部函數(shù)間的交流要大于病毒文件。

最后，從軟件的CFG中共得到了48種特征作為后續(xù)分類器的輸入。

1.2.2 ELF代碼段特征

在Linux操作系統(tǒng)中的可執(zhí)行文件和庫文件均采用ELF(Executable and Linking Format)格式來進(jìn)行組織[3]。典型的ELF文件格式視如圖2所示，包括ELF文件頭、程序文件頭、代碼段等，其中的Segment和Section字段分別包含了可執(zhí)行文件和庫文件的主要代碼信息。

圖2 ELF文件格式示意圖

作為一種特殊可執(zhí)行文件(具有破壞性)，Linux操作系統(tǒng)下的病毒文件同樣必須符合ELF文件格式的標(biāo)準(zhǔn)。與此同時(shí)，為了完成其破壞功能，病毒文件的代碼段中必定包含一些與正常文件不同的特殊代碼。因此，可以使用ELF文件中的Segment和Section字段的代碼特征作為病毒檢測(cè)系統(tǒng)的特征向量。具體操作如下：

① 使用Linux下的反匯編工具objdump將文件反匯編，得到其代碼段的十六進(jìn)制形式，圖3為ls命令的十六進(jìn)制代碼截圖。

② 使用N-gram[4]方法從十六進(jìn)制代碼段中提取特征向量，這里選用3-gam，共獲得13 847個(gè)特征。

③ 由于特征比較龐大，使用信息增益的方法(IG)[4]的方法消除特征冗余，最后得到768個(gè)特征作為分類器的輸入。

圖3 ls命令反匯編后代碼段截圖

1.3 分類器算法選擇

在機(jī)器學(xué)習(xí)理論中已經(jīng)提出了多種經(jīng)典的分類器算法。包括決策樹算法、貝葉斯網(wǎng)絡(luò)算法、支持向量機(jī)(SVM)、人工神經(jīng)網(wǎng)絡(luò)(ANN)等。

本文的重點(diǎn)不在于對(duì)各種分類算法的細(xì)節(jié)討論，因此在此不對(duì)分類器算法的細(xì)節(jié)進(jìn)行介紹。同時(shí)，圖1的Linux病毒檢測(cè)方案也不依賴于特定的分類器算法，具有較大的靈活性。為了討論方便，選擇決策樹和人工神經(jīng)網(wǎng)絡(luò)(ANN)作為本文的分類器算法。

2 檢測(cè)效果整合

對(duì)于檢測(cè)效果的整合屬于機(jī)器學(xué)習(xí)中集成學(xué)習(xí)的范疇，其目的是整合多個(gè)子分類器的結(jié)果，使集成后的檢測(cè)效果優(yōu)于各個(gè)子分類器的檢測(cè)效果。D-S證據(jù)理論被廣泛應(yīng)用于集成學(xué)習(xí)中[5]，結(jié)合D-S理論后Linux病毒檢測(cè)系統(tǒng)如圖4所示，這是圖1的另一種表示方式。

圖4 結(jié)合D-S理論的病毒檢測(cè)系統(tǒng)框圖

其具體流程如下：

① 將包含正常文件和病毒文件的樣本集隨機(jī)劃分為樣本子集1、樣本子集2……樣本子集n。

② 對(duì)于每個(gè)樣本子集，分別提取其十六進(jìn)制代碼段特征和CFG特征，作為分類器的輸入。

③ 將每個(gè)樣本子集的兩類特征分別作為每個(gè)子分類器的輸入得到分類結(jié)果。譬如對(duì)樣本子集1，將其十六進(jìn)制代碼段特征作為ANN分類器1至ANN分類器m的輸入，得到m種分類結(jié)果，再將十六進(jìn)制代碼段特征作為決策樹分類器1至決策樹s分類器的輸入，得到s種分類結(jié)果；對(duì)于樣本子集1的CFG特征，采用同樣的方式處理。因此，對(duì)于每個(gè)樣本集，最后得到(m+s)種分類結(jié)果；整個(gè)系統(tǒng)得到(m+s)·n種分類結(jié)果。

④ 將得到的(m+s)·n種分類器進(jìn)行基于D-S理論的結(jié)果整合，得到最終的判決結(jié)果。

在使用D-S理論融合各種分類器結(jié)果的過程時(shí)，將各個(gè)分類器的分類表現(xiàn)作為基本的概率分配函數(shù)。在參考文獻(xiàn)[5]中的手寫字識(shí)別過程研究中，提出了一種基于識(shí)別率、拒絕率的概率分配方法，實(shí)驗(yàn)表明這種方法具有穩(wěn)定性并且優(yōu)于表決法。

但在參考文獻(xiàn)[5]中提出的方法在病毒檢測(cè)中具有局限性，因?yàn)槠洳]有考慮各子分類器在不同的分類選項(xiàng)中的表現(xiàn)。對(duì)其改進(jìn)如下：

① 在病毒檢測(cè)中，檢測(cè)結(jié)果只有正常和病毒兩種，所以命題空間為Ω={N,﹁ N,A,﹁ A},其中N表示對(duì)樣本判定為正常的信任，﹁ N對(duì)樣本判定為正常的不信任，A表示對(duì)樣本判定為病毒的信任，﹁ A對(duì)樣本判定為病毒的不信任。

② 據(jù)此，建立以命題組合為基礎(chǔ)的概率映射M:2{N,﹁ N,A,﹁ A}→[0,1],其中M(φ)=0,M{N,﹁ N,A,﹁ A}=1-M(N)-M(﹁ N)-M(A)-M(﹁ A)。

③ 對(duì)于一個(gè)給定的測(cè)試樣本x，每個(gè)子分類器n都會(huì)作出對(duì)這個(gè)樣本類型的判斷，即信任其正常(N)、信任其不正常(﹁ N)、信任其為病毒(A)、信任其不為病毒(﹁ A)。對(duì)于每種情況的置信函數(shù)定義為：

(1)

其中，TP、FP、TN、FN分別是病毒被正確分類、正常文件被正確分類、病毒被錯(cuò)誤分類、正常文件被錯(cuò)誤分類的比例。

④ 對(duì)由m個(gè)ANN分類器和s個(gè)決策樹分類器的組合，一個(gè)樣本的命題基本概率BPA賦值函數(shù)為：

M=mann(1)⊕…mann(m)⊕mdecison tree(1)⊕…mdecison tree(s)

⑤ 最后，最終判決結(jié)果表示為：

E(x)=θjif bel(θj)=arg max Bel(θi)

3 實(shí)驗(yàn)結(jié)果與分析

從專門提供病毒樣本的vxheaven.org網(wǎng)站上得到共949個(gè)Linux文件樣本，其中正常文件503個(gè)，病毒文件446個(gè)。兩種文件大小的信息如表2所列。

表2 實(shí)驗(yàn)樣本大小數(shù)據(jù)

除了驗(yàn)證本文提出的方案外，還測(cè)試了單獨(dú)使用ELF代碼段和CFG特征的檢測(cè)效果。在實(shí)驗(yàn)中使用了10折交叉驗(yàn)證的方法來減少系統(tǒng)誤差。

實(shí)驗(yàn)結(jié)果如表3所列，從中可以得到如下結(jié)論：

① 程序的內(nèi)部拓?fù)浣Y(jié)構(gòu)能很好地表示一個(gè)程序的特征，使用CFG方法的病毒檢測(cè)率在96.88%以上，具有較高的檢測(cè)率。

② 使用CFG方法獲得的特性維數(shù)要明顯低于N-gram等方法獲得的特征維數(shù)，相同的樣本集，CFG方法獲得48種特征。N-gram方法得到768種特征，二者的檢測(cè)效果相當(dāng)。這說明CFG方法能在維持檢測(cè)效果的情況下降低系統(tǒng)的運(yùn)算負(fù)荷。

③ 結(jié)合了ELF代碼段特征和CFG特征的檢測(cè)器的效果優(yōu)于單一的檢測(cè)器。因?yàn)镋LF代碼段特征和CFG特征具有無關(guān)性，基于D-S證據(jù)理論的集成分類器的性能得到了最大程度的融合。

表3 三種檢測(cè)器效果對(duì)比

結(jié) 語

本文提出的Linux病毒檢測(cè)方案已經(jīng)在Weka開源機(jī)器學(xué)習(xí)平臺(tái)上實(shí)現(xiàn)。

本文方案的設(shè)計(jì)結(jié)合了機(jī)器學(xué)習(xí)和D-S證據(jù)理論的研究方法。在樣本特征提取時(shí)選擇了動(dòng)態(tài)調(diào)用和靜態(tài)代碼段特征，減少了二者的耦合性，提高了最后結(jié)果融合的效果；使用CFG獲得的特征反映了程序的內(nèi)部拓?fù)浣Y(jié)構(gòu)，得到的特征維數(shù)較小，能夠提高系統(tǒng)的運(yùn)行效率。最后，在應(yīng)用D-S理論進(jìn)行結(jié)果融合時(shí)，使用子分類器的檢測(cè)效果作為其置信函數(shù)，恰當(dāng)?shù)胤磻?yīng)了各子分類器的檢測(cè)能力，提高了整個(gè)系統(tǒng)的檢測(cè)性能。

[1] Gavrilut D，Cimpoesu M，Anton D, et al. Malware detection using machine learning[C] //Computer Science and Information Technology, 2009. IMCSIT '09. International Multiconference on.IMCSIT, 2009: 735-741.

[2] Zongqu Zhao. A virus detection scheme based on features of Control Flow Graph[C]// Artificial Intelligence, Management Science and Electronic Commerce (AIMSEC), 2011 2nd International Conference on AIMSEC, 2011:943 - 947.

[3] 朱裕祿. Linux系統(tǒng)下的ELF文件分析[J].電腦知識(shí)與技術(shù), 2006(8):111-113.

[4] 張小康，帥建梅，史林.基于加權(quán)信息增益的惡意代碼檢測(cè)方法[J].計(jì)算機(jī)工程, 2010, 6(36):149-151.

[5] 雷蕾,王曉丹.結(jié)合SVM與DS證據(jù)理論的信息融合分類方法[J].計(jì)算機(jī)工程與應(yīng)用, 2013(11):114-117.

[6] Xu L. Methods of combining multiple classifiers and their applications to handwriting recognition[J]. IEEE Transactions on Systems,Man and Cybernetics Society, 1992(5/6):418-435.

黃一峰(碩士)，研究方向?yàn)長(zhǎng)inux應(yīng)用軟件開發(fā)；黃俊偉 (正高級(jí)工程師)，研究方向?yàn)門D-SCDMA移動(dòng)通信終端開發(fā);吳戀(碩士)，研究方向?yàn)榍度胧絃inux終端設(shè)備開發(fā)。

參考文獻(xiàn)

[1] 董超,李立偉,張洪偉.新型電動(dòng)汽車鋰電池管理系統(tǒng)的設(shè)計(jì)[J].通信電源技術(shù)，2012(29)：33-35.

[2] 張金頂,王太宏,龍澤,等.基于MSP430單片機(jī)的12節(jié)鋰電池管理系統(tǒng)[J].電源技術(shù)，2011(35)：514-516.

[3] Paul Horowitz, Winfield Hill.電子學(xué)[M] .2版.吳利民,等譯. 北京: 電子工業(yè)出版社, 2011:749-754.

[4] 沈建華,楊艷琴,翟驍曙.MSP430系列16位超低功耗單片機(jī)原理與應(yīng)用[M].北京: 清華大學(xué)出版社, 2004.

[5] 林成濤,王軍平,陳全世.電動(dòng)汽車SOC 估計(jì)方法原理與應(yīng)用[J].電池,2004(35):336-338.

[6] 李文江,張志高,莊益詩.電動(dòng)汽車用鉛酸電池管理系統(tǒng)SOC算法研究[J].電源技術(shù),2010(34):1266-1268.

[7] 李哲,盧蘭光,歐陽明高.提高安時(shí)積分法估算電池SOC精度的方法比較[J]. 清華大學(xué)學(xué)報(bào)：自然科學(xué)版,2010(50):1293-1296.

陳翰沫(碩士研究生)，主要從事儀表與測(cè)量技術(shù)的研究。

(責(zé)任編輯：高珍 收稿日期：2013-11-02)

A Linux Virus Detection Method Using Machine Learning and D-S Theory

Huang Yifeng，Huang Junwei, Wu Lian

(Next Generation Mobile Communication Terminal Laboratory，Chongqing University of Posts and Telecommunications，Chongqing 400065，China)

This paper mainly designs and realizes a Linux virus detection method using machine learning and D-S theory. It includes the design’s general framework, feature selection method, classifier selection method, detection result fusion and the design verification and result analysis. It intrdouces the control flow graph while doing feature selection, and introduces D-S theory while doing detection result fusion. Then it implements and test the method on the platform of Weka software. The results of implementation show that this design to detect Linux virus has high efficiency and good reliability, and it is adequate for commercial products.

Linux operating system; virus detection; machine learning; D-S theory; CFG

國家重大專項(xiàng)“TD-SCDMA增強(qiáng)型多媒體手機(jī)終端的研發(fā)和產(chǎn)業(yè)化”(2009ZX03001-002-01)。

TP36.2

A

珍

2013-11-11)