黃一峰，黃俊偉，吳戀

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

?

一種應用機器學習和D-S證據(jù)理論的Linux病毒檢測方案*

黃一峰，黃俊偉，吳戀

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

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

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

引 言

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

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

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

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

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

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

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

圖1 Linux病毒檢測方案整體框架

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

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

1.2 樣本特征提取

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

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

1.2.1 基于CFG的特征

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

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

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

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

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

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

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

1.2.2 ELF代碼段特征

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

圖2 ELF文件格式示意圖

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

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

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

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

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

1.3 分類器算法選擇

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

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

2 檢測效果整合

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

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

其具體流程如下：

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

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

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

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

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

但在參考文獻[5]中提出的方法在病毒檢測中具有局限性，因為其并沒有考慮各子分類器在不同的分類選項中的表現(xiàn)。對其改進如下：

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

② 據(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)。

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

(1)

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

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

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

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

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

3 實驗結(jié)果與分析

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

表2 實驗樣本大小數(shù)據(jù)

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

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

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

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

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

表3 三種檢測器效果對比

結(jié) 語

本文提出的Linux病毒檢測方案已經(jīng)在Weka開源機器學習平臺上實現(xiàn)。

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

[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ù), 2006(8):111-113.

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

[5] 雷蕾,王曉丹.結(jié)合SVM與DS證據(jù)理論的信息融合分類方法[J].計算機工程與應用, 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.

黃一峰(碩士)，研究方向為Linux應用軟件開發(fā)；黃俊偉 (正高級工程師)，研究方向為TD-SCDMA移動通信終端開發(fā);吳戀(碩士)，研究方向為嵌入式Linux終端設(shè)備開發(fā)。

參考文獻

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

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

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

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

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

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

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

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

(責任編輯：高珍 收稿日期：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

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

TP36.2

A

珍

2013-11-11)