基于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文件头表信息外的其他特征属性,如系统性能指标、网络流量指标等,以图像的方式来处理病毒,并引入深度学习研究病毒检测问题。