基于AdaBoost算法的Linux病毒檢測研究

吳 ,,,

(1.貴州師范學院 a.數學與計算機科學學院; b.大數據科學與智能工程研究院,貴陽 550018;2.重慶郵電大學 新一代寬帶移動通信終端研究所,重慶 400065; 3.北京大學深圳研究生院 信息工程學院,深圳 518055)

0 概述

隨著大數據及智能化時代的到來,穩定性好、性能高的Linux操作系統已逐漸成為當下應用主流,針對Linux的各種病毒攻擊也越來越頻繁。但是由于各種原因,Linux上的病毒檢測工具遠不如Windows平臺上的豐富和有效,而且相關的理論研究也不多[1-2]。因此,對于Linux病毒檢測技術的研究具有較大的現實意義。

本文以機器學習中分類和集成學習問題的處理框架為基礎,結合Linux操作系統的ELF文件特點,基于AdaBoost算法設計并實現了一種高性能的Linux病毒檢測方案。

1 基于AdaBoost的Linux病毒檢測方案

簡單的病毒檢測方案設計如圖1所示。采用特征提取方法從待測文件中得到樣本特征,然后通過某種分類算法進行判斷,最后得到檢測結果。但這種方案存在不足,單個分類器分類能力是有局限的,其檢測準確率不是太高,且容易對特定樣本產生過擬合性。

圖1 簡單的病毒檢測方案

為了解決上述方案的不足,本文在分類學習問題處理框架的基礎上,引入集成學習的思想,綜合多個分類器的檢測結果,通過整合的方式來提高檢測精度[3]。本文設計的Linux病毒檢測方案如圖2所示,總的檢測流程如下:

1)從待測文件中提取出樣本特征。

2)從基分類器1至基分類器n,每個基分類器都獨立地對待測樣本進行檢測,得到各自的檢測結果。

3)對所有基分類器的檢測結果進行整合,得到系統的最終檢測結果。

圖2 本文Linux病毒檢測方案

本文的病毒檢測方案是構建在簡單的病毒檢測方案之上的,從單個分類器變成了多個有差異的分類器集成組合,所以,涉及到的技術問題除了文件樣本特征提取、基分類器的設計外,還有一個關鍵的技術點就是關于基分類器的訓練和整合。

1.1 樣本特征的提取

樣本特征選擇的標準是要能最大程度地反映出病毒和正常文件的區別。本文的研究目標是Linux操作系統病毒,所以,在特征選取方面盡量考慮Linux操作系統獨有的特性。本文選擇了ELF文件的頭表信息作為樣本特征來源。

執行與連接格式(Executable and Linking Format,ELF)文件格式是Linux操作系統下一種主要的目標文件格式,Linux系統下所有的可執行文件和庫文件都必須符合ELF格式的標準。ELF頭表中描述了文件的整體結構,包括當前文件類型、版本號、節頭表和段頭表的偏移量等。節頭表(Section Header Table)記錄的是編譯器和鏈接器需要使用的每一個節的描述信息,包括指令節、數據節、符號表節等。段頭表(Program Header Table)記錄的是程序段的內容,包含著程序文件到內存的映射信息。以上的各部分頭表信息決定了目標文件如何與其他目標文件連接,載入內存以及如何執行等[4-5]。對于可執行文件型的Linux病毒而言,在將自身病毒體代碼插入寄主體之前,必須修改寄生體的頭、節頭表、段頭表里面的信息,否則是無法完成寄生宿主、駐留內存等工作的。而對于蠕蟲等能獨立運行的Linux病毒來說,為了完成其破壞行為,在其ELF文件信息中也必定包含一些與正常文件不同的地方,例如在代碼段中訪問非法的內存地址、反復讀取系統參數等,這些行為最終也會反映在頭表信息中。因此,可以使用ELF文件的頭表信息作為樣本特征來源。在Linux操作系統下,可以使用readelf工具讀取ELF文件的頭表信息,本文從中提取了可能和病毒檢測相關的78個特征屬性,如圖3所示。

屬性描述數據類型個數ELF headerInteger13SectionheadertableText headerInteger8Data headerInteger8BSS headerInteger8Symbol headerInteger9ProgramheadertablePT_LOAD1 headerInteger8PT_LOAD2 headerInteger8PT_DYNAMIC headerInteger8PT_INTERP headerInteger8

圖3提取的ELF文件頭表特征

1.2 BP神經網絡基分類器的設計

在有了待選的樣本特征來源之后,還需要確定基分類器。分類算法的選擇對分類結果有重大的影響,病毒的檢測實質上就是機器學習理論中的一個分類問題。分類問題的最終目的是要訓練得到一個分類器,以便使用這個分類器來對待分類的樣本進行分類。本文選用BP神經網絡作為基分類器,BP神經網絡在病毒的檢測應用上已有相關文獻證實其可行性和優越性[6-7]。神經網絡算法的結構特點使其比其他分類算法具有更好的容噪性和健壯性。本文的BP神經網絡網絡結構設計為36×20×12,學習算法為誤差反向傳播算法,學習率設為lr=0.1,最大學習次數為20 000次,學習目標誤差平方和為Err_goal=10-5。

1.3 基分類器的訓練和整合方案

系統的檢測結果是通過綜合多個基分類器的分類結果而得來的,所以,基分類器之間應該是各不相同的,否則對同一個樣本,基分類器的分類結果都差不多,便失去了整合的意義。根據集成學習理論,基分類器的產生方式有異態學習和同態學習2種。一般來說,異態集成學習需要實現多個不同的基分類器分類算法,系統開發的工作量是比較大的,因此,本文采用同態集成學習的方法來得到基分類器。在同態學習中,每個基分類器的分類算法是不變的,問題便轉化到如何調整基分類器分類算法的訓練過程上來。有一種思路是通過對樣本集進行某種處理,使得每次在對分類算法進行訓練時的樣本集都是不同的,從而得到不同的分類器[8]。本文采用了AdaBoost算法來實現基分類器的生成及整合,并對AdaBoost算法的基分類器權重計算及基分類器整合部分進行了算法改進,使之更契合于病毒檢測問題。

2 AdaBoost算法及其改進

2.1 原AdaBoost算法

Adaboost是一種迭代算法,其核心思想是針對同一個訓練集訓練不同的分類器(基分類器),然后把這些基分類器集合起來,構成一個更強的最終分類器(強分類器)[9]。在訓練過程中,每個訓練樣本被賦予一個初始權值,當一個基分類器訓練完成后,根據其在訓練集上的分類結果對所有的樣本權值進行調整,使得下一次訓練的基分類器更關注那些被識別錯誤的樣本。最后的強分類器的判決結果是所有分類器的判決結果的加權和。

AdaBoost算法的流程如下[7,9]:

步驟1給定訓練樣本集:

S={(x1,y1),(x2,y2),…,(xi,yi),…,(xm,ym)}

其中,xi是實例樣本,有xi∈X;yi是類別標志,yi∈Y={-1,+1},m表示當前訓練樣本有m個。

步驟2對樣本權重進行初始化:

Dt(i)=1/m

步驟3循環t=1,2,…,T(T表示設置了T個基分類器):

1)在當前的樣本權重分布Dt下,訓練得到基分類器:ht=H(x,y,Dt)。

2)計算該基分類器的錯誤率:

3)計算得到基分類器的權重:

at=ln(1-εt)/εt

4)更新樣本權重:

其中,Zt-為歸一化因子。

步驟4得到強分類器:

從算法流程可以看出,AdaBoost算法在每一輪中不僅更新了樣本的權重,還計算出了每輪生成的基分類器的權重,權重更高的基分類器將獲得更大的話語權。

2.2 AdaBoost算法改進

在AdaBoost算法中,基分類器的權重由分類錯誤率給出,如下:

at=ln(1-εt)/εt

(1)

其中,at為基分類器的權重,εt為該基分類器的分類錯誤率。

基分類器的分類錯誤率越大,其獲得的權重就越小。在病毒檢測中,分類錯誤也即是把病毒識別為了正常文件或是把正常文件識別成了病毒。對于病毒檢測來說,系統對正樣本(病毒)的識別率是比負樣本更為重要的,即所謂寧可錯殺,不可輕易放過。因此,如果能夠在基分類器權重計算時加入基分類器對正樣本識別能力強弱的考慮,則算法能更好地適用于病毒檢測應用場景[10-11]。為此,本文定義了對正樣本識別能力的變量φt如下:

而對基分類器權重重新定義為式(3),其中,ξ為正常數。

at=ln(1-εt)/εt+ξ·eφt

(3)

其中,φt是第t輪訓練時基分類器中所有被識別為正樣本的權重之和,它能夠反映基分類器對正樣本的識別能力。at是第t輪訓練時基分類器的權重,即第t個基分類器的權重(t∈[1,T])。

此外,原始的AdaBoost算法采用加權投票的方式來整合基分類器結果,但是由于訓練樣本通常是有限的,部分基分類器在被訓練時可能會存在過擬合現象,對此本文引入D-S理論的方法改進AdaBoost算法中基分類器的整合方式,降低那些存在過擬合現象的基分類器對整合結果的影響,進一步提高整合后的效果。

改進后的算法描述如下:

步驟1給定訓練樣本集

S={(x1,y1),(x2,y2),…,(xi,yi),…,(xm,ym)}

其中,xi是實例樣本,有xi∈X;yi是類別標志,yi∈Y={-1,+1},m表示當前訓練樣本有m個。

步驟2對樣本權重進行初始化:Dt(i)=1/m。

步驟3循環t=1,2,…,T(T表示設置了T個基分類器):

1)在當前的樣本權重分布Dt下,訓練得到基分類器:ht=H(x,y,Dt)。

2)計算該基分類器的錯誤率:

3)計算對正樣本的識別正確率:

4)計算得到基分類器的權重:

at=ln(1-εt)/εt+ξ·eφt

5)更新樣本權重:

其中,Zt為歸一化因子。

步驟4得到強分類器:

H(x)=D-Stheory(at,ht(x))

2.3 改進算法分析

通過上小節的討論可以看出,本文對AdaBoost算法的改進有2點:

1)對基分類器的權重計算進行了改進,將基分類器對正樣本(病毒)的分類能力考慮到基分類器權重分配中。

基分類器權重被重新定義為:

at=ln(1-εt)/εt+ξ·eφt

2)對基分類器的整合進行了改進,將帶權重投票的整合的方式改為D-S證據理論整合的方式。

基于D-S證據理論整合如圖4所示,主要包括證據空間和證據合成規則[12-14]。在D-S理論中,證據合成規則是固定的,所以,關鍵就在于怎么結合本文的病毒檢測系統來生成證據空間。

圖4 基于D-S證據理論的整合

在D-S證據理論應用到Linux病毒檢測的過程中,本文的定義如下[13-14]:

1)命題、傳感器和命題空間

病毒檢測系統共包括2個基本命題:(1)樣本為正常文件,記為N;(2)樣本為病毒,記為ΔN,且N∩ΔN=0。所以,命題空間為A={N,ΔN},其中,N表示對樣本判定為正常文件的信任,ΔN對樣本判定為病毒的信任。傳感器為基分類器,可以對基本命題做出判斷。對于一個給定的測試樣本,每個基分類器都會做出對其類型的判斷,即信任其正常文件(N)或者信任其為病毒(ΔN)。

2)證據空間

根據病毒檢測系統命題空間的定義,得出其基本概率函數有:

M:2{N,N}→[0,1]

(4)

其中:

M({N,N})=1-M(N)-M(N)

(5)

每個命題中不再包含子集,所以,命題的信任函數就是它的基本概率函數,反映了對它的基本信任度分配,即:

Bel(A)=M(A),A={N,N}

(6)

同時,似然函數為:

Pi(N)=1-Bel(N)=1-M(N)

(7)

從以上分析可以看出,對命題整合的關鍵在于對每個基分類器的基本概率函數的定義。在AdaBoost算法中,對每個基分類器都賦予了投票權重,作為對其分類表現的評價。因此,可以把每個將基分類器的權重作為其基本概率函數。例如2個基分類器m1、m2的權重分別為a1、a2,在一次檢測中,它們對待測樣本的判斷分別為N與N,則它們的基本概率函數定義如表1所示。同理,可以對多個基分類器的基本概率函數做出定義。

表1 2個基分類器的基本概率分配

3)合成規則

對由T個基分類器組成的檢測系統,采用Dempster正交合成規則來對命題的基本概率函數進行合成,得到檢測系統對該命題的信任度分配,如下:

M(A)=m1(A)⊕m2(A)⊕…⊕mT(A)

(8)

在D-S證據理論引入后,檢測系統對病毒的檢測從簡單的“是“與“否”的判斷轉化為可量化的數值輸出。例如當對檢測敏感度要求比較高時,可以把病毒判定的閾值調低,從而將更多可疑文件判定為病毒,反之亦然。通過這種方式,使系統更加適用于不同的檢測場景。

綜上所述,改進后的AdaBoost算法在基分類器權重計算中加入正樣本(病毒)識別能力的影響,讓AdaBoost算法變得更適用于病毒檢測的應用。其使得在分類錯誤率相同的情形下,那些具有更高正樣本識別能力的基分類器將被賦予更大的權重,整個檢測系統對正樣本的識別能力也因此提高。在AdaBoost算法的基分類器整合問題中改進引入D-S理論方法,進一步提高多個基分類器結果的整合效果,使最終的判決結果正確率更高。

3 實驗結果與分析

3.1 實驗樣本集

實驗的樣本集共包含1 200個樣本,其中,正常文件700個,病毒文件500個。病毒樣本是從專門提供病毒樣本的www.vxheaven.org網站上下載的[15],包括蠕蟲、后門、特洛伊木馬等病毒類型共500個,其各類型病毒占比情況如表2所示。正常文件樣本主要采集于Ubuntu和Android操作系統的系統文件,以及流行Linux應用程序的可執行文件和庫文件,共700個,其各類型分布情況如表3所示。正常樣本和病毒樣本的大小信息如表4所示。

表2 病毒樣本集中各類Linux病毒占比情況 %

表3 正常文件樣本集中各類正常文件占比情況 %

表4 正常樣本和病毒樣本的大小信息 KB

3.2 實驗內容

實驗內容具體如下:

1)本文病毒檢測方案的可行性驗證

將上述所述實驗樣本80%的樣本(病毒文件、正常文件均勻取80%)作為訓練集訓練基分類器BP神經網絡,剩下的20%樣本集作為測試集驗證本文病毒檢測方案的檢測效果。本文在Ubuntu操作系統上,用C語言編程實現了本文所述的病毒檢測方案。代碼主要分為2個部分,一個是用于訓練基分類器的訓練代碼,另一個是用于訓練完成后進行檢測的檢測代碼。訓練過程首先完成對訓練樣本集的特征表示,即提取每個樣本的ELF文件頭特征來代表每個樣本文件,將得到的訓練樣本特征集作為AdaBoost算法的樣本集,利用算法描述中的前3個步驟訓練得到T個BP基分類器,并得到各自權重。檢驗過程首先同樣先完成檢測樣本集的特征表示,然后用每個檢測樣本的ELF文件特征作為基分類器的輸入,分別由T個基分類器對同一樣本進行檢測,得到T個結果,應用算法中第4步D-S證據整合得到該樣本的最終判決結果。其實驗流程如圖5所示。

圖5 實驗運行流程

實驗測試了在設置不同數量基分類器情況下的檢測性能,表5為設置不同基分類器個數下的檢測正確率,本文中的正確率是指所有被正確分類的樣本在待測樣本中的比例,其計算公式為:

其中,TP表示病毒樣本被正確檢測出來的數目,TN表示正常文件被正確檢測出來的數目,FP表示正常文件被錯誤判定為病毒的數目,FN表示病毒樣本被誤判為正常文件的數目。

表5 設置不同數目基分類器的檢測準確性

2)改進后的AdaBoost算法檢測效果驗證

本文針對AdaBoost算法是否改進,編程實現了2套代碼,一套是采用原始AdaBoost算法思路實現的訓練代碼1和檢測代碼1,另一套是采用改進后的AdaBoost算法思路實現的訓練代碼2和檢測代碼2。訓練代碼1與訓練代碼2實現的區別在于每次循環中基分類器的權重計算時是否加入了對正樣本(病毒)的分類能力考慮,即計算中加上了ξ·eφt項;檢測代碼1和檢測代碼2實現的區別在于整合所有基分類器檢測結果的方式不同,檢測代碼1是簡單的將所有基分類器的檢測結果加權和作為整合結果(即最終的檢測結果),而檢測代碼2是采用D-S證據理論思想來整合所有基分類器結果的,代碼實現主要包括計算歸一化參數、計算證據空間(基分類器的基本概率函數)、證據合成3個步驟,代碼實現思路如下:

步驟1計算歸一化函數,定義為變量C:

步驟3正交合成規則來對命題的基本概率函數進行合成,公式如下:

M=m(1)⊕m(2)⊕…⊕m(T)

實驗將未改進的AdaBoost檢測方法和改進后的AdaBoost檢測方法其基分類器個數都設置為16個,實驗的訓練樣本和測試樣本均采用了如上所述的相同樣本集,其各自檢測效果如表6前兩行所示。

表6 本文檢測方法與其他殺毒軟件對比 %

同時,本文對市場上常見的2款Linux病毒檢測軟件(Avria Linux和F-PROT)[16]也進行了比對測試,表6中后兩行為Avria Linux和F-PROT的檢測結果。Linux版本的Avria殺毒軟件是Linux平臺上最受歡迎的殺毒軟件之一,是一款免費的殺毒軟件,它的使用模式基本上和平時在Windows平臺所使用的金山毒霸、KILL、瑞星等殺毒軟件的DOS版本的使用方法是一樣的,用戶選擇不同的掃描參數可以讓Avria執行不同的任務,在使用Avria掃描完系統后,Avria會顯示一個掃描清單,用戶可以清楚知道Avria的掃描結果。本文在Ubuntu系統下安裝了Linux版本的Avria殺毒軟件,并讓其掃描本文實驗樣本集中的測試樣本集文件夾,得到了其掃描結果,其正確率為96.2%。本文對比測試的另一款Linux殺毒軟件是F-PORT,對家庭用戶免費,它有使用克龍(cron)工具的任務調度的特性,能在指定時間執行掃描任務,同時它還可以掃描USB HDD、Pendrive、CD-ROM、網絡驅動、指定文件或目錄、引導區病毒掃描、鏡像。本文同樣在Ubuntu系統下安裝了該殺毒軟件,并指定讓其掃描本文實驗樣本集中的測試樣本集文件夾,得到其病毒識別正確率為94.8%。

3.3 結果分析

從表5可以看出:1)當基分類器數量為1個時,相當于沒有進行集成學習,此時的檢測系統正確率能達到85%以上,說明本文所選用的ELF文件特征、BP神經網絡分類算法是比較適用于Linux病毒檢測問題的;2)當基分類器數量從2個到16個依次遞增時,檢測系統的正確率有較大程度的提升,說明集成學習對系統檢測性能的提升起到了明顯的作用,本文的病毒檢測方案比傳統簡單的單分類器方案好;3)當基分類器數量從16增加到32個時,準確率不再有明顯的提升,說明基分類器數量的不斷增加并不能無限地提升系統的檢測性能,在性能不會再有明顯提升的情況下,無需犧牲大量計算量和時間來設置更大的基分類器數。

從表6可以看出,本文對AdaBoost算法進行改進后其在病毒檢測效果上有明顯提升,改進后的AdaBoost算法更適用于病毒檢測問題。本文提出的病毒檢測方案其檢測效果優于當前市場上已有的兩款Linux病毒檢測軟件。

4 結束語

本文設計一種Linux病毒檢測方案,選取了ELF文件的頭表信息作為樣本特征,分類器采用了BP神經網絡,通過AdaBoost算法利用有限的樣本集訓練出多個基分類器。在AdaBoost算法的基分類器整合問題中引入D-S理論,進一步提高整合效果。實驗結果表明,該檢測方法取得了較好的效果。下一步將嘗試使用除了ELF文件頭表信息外的其他特征屬性,如系統性能指標、網絡流量指標等,以圖像的方式來處理病毒,并引入深度學習研究病毒檢測問題。