（生物医学工程专业论文）基于生物信息学方法的系统异常诊断.pdf

中国科学技术大学硕士学位论文 。 a b s t r a c t s y s t e mc a l ls e q u e n c e sh a v eb e e nw i d e l yu s e df o ra n o m a l yd i a g n o s i s u s u a l l y ，i n o p e r a t i n gs y s t e m ，t h e r ea r eas e to fs u b r o u t i n e st h a ti su s e dt oi m p l e m e n ts y s t e m o p e r a t i o n ，t h e s es u b r o u t i n e sa r eb u i l ti nt h ek e r n e l ，a n di su s e dt oi m p l e m e n ts y s t e m l e v e lf u n c t i o n ，t h eo p e r a t i o ns y s t e ms u p p l yt h ei n t e r f a c et ou s e r ，i ti sc a l l e ds y s t e m c a l l s w h e nu s e rn e e d ss e r v i c ei no p e r a t i o ns y s t e m ，t h e yc a nu s et h e s es y s t e mc a l lt o c a l lt h a tf u n c t i o n s y s t e mc a l li st h eb r i d g eb e t w e e nu s e ra p p l i c a t i o na n dk e r n e li n o p e r a t i o ns y s t e m m a n yt r a d i t i o n a lm e t h o d sr e l yo np a t t e r n so fs y s t e mc a l l so rr u l e st om o d e l d i f f e r e n tb e h a v i o r sf o rap r o g r a m h o w e v e r ，t h e s et e c h n i q u e sa r ea l lb a s e do ns o m e s i m p l em a t h e m a t i c a lr u l e s ，t h ep a t t e r n s o rr u l e se x t r a c t e da r eo n l yo p t i m a li n m a t h e m a t i c sp o i n to fv i e w , t h e s ep a t t e r n sa r er e d u n d a n t ，a n ds o m eo ft h e mh a v en o s y s t e mm e a n i n g i nt h i sp a p e rw eu s et h es e q u e n c ea l i g n m e n tm e t h o d si nb i o i n f o r m a t i c s ，a l o n g w i t ht h es e m a n t i c so ft h ee v e n t sw h i c hm i g h ti n d i c a t eb o u n d a r i e so fp r o g r a m f u n c t i o n s ，a n dp r e s e n ta na p p r o a c ht ol e v e r a g et h e s es y s t e mc a l ls e m a n t i c st oe x t r a c t m o t i f sa sc h a r a c t e r i z a t i o no fp r o g r a mb e h a v i o r am o t i fi sac o n s e r v e dr e g i o no f c o n s e c u t i v es y s t e mc a l l si n s e q u e n c ew h i c hm i g h tb ec o r r e s p o n d e n tt oap r o g r a m f u n c t i o n w es t u d yt w oe a s e so ni n t r u s i o nd e t e c t i o na n da u t o m a t i cp r o b l e md i a g n o s i s t h e p r e l i m i n a r yr e s u l t s d e m o n s t r a t ei m p r o v e d 刍e r f o r m a n c ea n dm o r ec o m p a c tf e a t u r e s p a c eo v e re x i s t i n gm a t h e m a t i c s b a s e dm e t h o d s t h i sp r o v e st h a tt h ep r e s e n c e so f s e q u e n c em o t i f sa r eh i g h l yd i s c r i m i n a t i v ef e a t u r e sf o ri d e n t i l y i n gt h ed i f f e r e n ts y s t e m b e h a v i o r s ，a n di ti si na g r e e m e n tw i t ht h es y s t e mt h i n k i n gt h a tc o n s i d e r sm o t i f st ob e t h eb u i l d i n gb l o c k so f s y s t e mc a l ls e q u e n c e s t h i sr e s e a r c hp r o j e c ti ss u p p o s e db ym i c r o s o f ta n dm i n i s t r yo fe d u c a t i o nk e y l a b o r a t o r yo fm u l t i m e d i ac o m p u t i n ga n dc o m m u n i c a t i o n u n i v e r s i t yo fs c i e n c e & t e c h n o l o g yo f c h i n a 。 k e yw o r d s ：b i o i n f o r m a t i c s ，s e q u e n c ea l i g n m e n t ，s y s t e mc a l ls e q u e n c e ，a u t o m a t i c p r o b l e md i a g n o s i s 中国科学技术大学硕十学位论文 第1 章绪论 1 1 蓬勃发展的生物信息学 近二十年来，分子生物学发展的一个显著特点是生物信息的剧烈膨胀，且迅 速形成了巨量的生物信息库“1 。生物信息包括了多种的数据类型，如d n a 序列， 蛋白质序列，蛋白质二级结构和三维结构数据等等。迅速膨胀的生物信息给科学 家们提出了一个新问题：如何有效管理、准确解读、充分利用这些信息? 生物信 息学便是在生物信息的急剧膨胀的压力下诞生的。一般意义上，生物信息学是研 究生物信息的采集、处理、存储、传播、分析和解释等各方面的一门学科，它通 过利用生物学、计算机学和信息技术而揭示大量而复杂的生物数据所赋有的生物 的奥秘。具体而言，生物信息学是把基因组dna 序列信息分析作为源头，在获 得蛋白质编码区的信息后进行蛋白质空间结构模拟和预测，然后依据特定蛋白质 的功能进行必要的药物设计。 虽然生物信息学的历史不长，但正像生物信息的迅猛发展一样，生物信息学 已经发展了大量有效实用的分析理论和分析方法。例如，当获得了大量序列数据 以后，可以进行序列家族或同源性分析；进行序列的聚类，建立进化树并确定序 列间的进化关系；进行代谢途径相关基因的同源性分析，以及获取其它生物代谢 途径的相关信息等。这些方法已经成为生物学家获取信息的重要途径。随着高效 实验新技术，特别是测序技术的不断进步，用于序列分类、相似性搜索、d n a 序 列编码区识别等方面的计算工具已成为理解生物序列，探索生命本质和进化过程 的重要组成部分。 1 2 日趋严重的系统异常自动诊断 计算机系统的发展是有目共睹的，随着计算机及网络应用的日心月异，信息 化程度的日渐提高，计算机与人们的生活之间的关系变得越来越为密切。人们开 始利用计算机进行办公，科研，娱乐，也出现了诸如网络银行，电子商务，电子 政务等。与此同时，计算机系统的正常运行也越发显得重要，大到国家、政府， 小到企业，个人，无不受到日益严重的计算机故障及网络入侵的困扰。 中国科学技术大学硕= 卜学位论文 1 2 ，1 计算机故障 计算机故障是指由于计算机的配置出现问题从而使系统无法正常工作。以 w i n d o w s 中最常用到的i n t e r n e te x p l o r e r ( i e ) 为例，用户在上网时经常遇到 “t h ep s g ec c 3 n n o tb ed i s p l a y e d ”，通过分析我们找出了1 1 种故障原因： l 。 b a d d n s ：域名鼹务器地址无效 2 8 a d i p ：i p 地址无效 3 b d d p o ，t ：钎指定的暇务器端口地址无效 4 b a d p r o s s q u t n c c s 挑q u e c r l l i 脚d d t m i cp r o g r i e a m m g a l i g n m e n t ff l 1 一，。一 图2 2p r o g r e s s i v e 算法多序列比对示意图 该算法的基本思想是构造一棵指导树用于指导多序列比对，每一个参与比对 的序列对应指导树上的一个叶子节点，并根据指导树进行渐进式比对。具体步骤 如下： 中国科学技术大学硕士学位论文 1 对所有序列进行两两比对，并得到一个距离矩阵。 2 根据距离矩阵计算得到一个进化树，、 树的每一个叶子节点对应于一个参 与比对的序列。 3 以进化树作指导，首先从所有比对中相似性最好的两条序列开始，然后 是剩余比对中相似性最好的两条序列，一次类推，直到多序列比对结束。 一旦两条序列的比对被列入，则序列的位置就被固定。 2 3 系统调用序列的分析模型 通常，在操作系统的核心中都设置了一组用于实现各种系统功能的子程序， 这些函数可以完成一些系统级别的功能，操作系统将它们提供给用户调用，称之 为系统调用。当用户进程需要操作系统提供某种服务时，便可利用系统调用。它 一般运行在核心态，是沟通用户进程和操作系统内核的桥梁。 每个进程自启动到运行结束都会产生一系列的系统调用。不同的执行路径产 生的系统调用也是不同的。对于进程的每一类行为，由于它们的配置或环境不同， 执行的路径是不同的，产生的系统调用序列也有很大的差异。因此可以从系统调 用序列中提取有用的信息来描述此类的行为。通过研究发现系统调用子序列具有 很强的一致性，可以将它们作为系统行为特征。 系统调用序列的产生取决于进程的执行流程，而进程执行流程受很多系统因 素的影响，如进程的输入参数及系统的状态。进程的执行可以看成是在这些因素 决定下各种功能操作的集合，例如有访问系统文件的操作，有从端口接收数据的 操作，有更改注册表键值的操作等。我们观察到这些操作的起始或是终止都由一 些特殊的系统调用指示，例如当进程要读取某个文件时，它需要先打开这个文件， 然后进行读取的操作，最后关闭该文件：当系统需要从某个端口发送数据时，它 先初始化该端口，之后进行发送的操作，最后关闭该端口。这些具有打开及关闭 语义的调用可以作为不同功能操作的分隔符，表1 中列举出了具有系统操作分隔 符语义的系统调用。可以用图l 的执行流程图来描述进程所有可能的执行。图中 节点表示在进程执行过程中的分支节点，即不同功能操作的分割符，有向边表示 从一个分支节点到下一个分支节点所经历的系统调用，图中有一个起始节点及若 干个中止节点。进程正常执行的流程是从图中的起始节点到正常的终止节点，而 1 2 2 中国科学技术大学硕士学位论文 非正常的执行流程则从起始节点到某一个异常终止节点。系统调用序列就是从起 始节点沿着有向边一直到终止节点所经过的系统调用。 表21 特殊语义的系统调用 w i n d o w sl i n u x o p e n * o p e n ， c l o s e w a i t f o r * w a i ts o c k e t c a l l c 1 0 s e # s i g b l o c k o p e n 调用用于将指定的一处路径的文件打开，如果成功它将返回一个文件描 述符，这个描述符用于以后对该文件的操作。c t o s e 用于将指定描述符代表的文 件关闭，它通常用于文件操作结束。这两个调用通常用于读写系统的文件或者设 备的开始和结束。l f a i t f o r 用于将当前的进程挂起，直到某个等待的操作完成， 它同样可以指示操作的边界。7 0 c t 用语控制对设备不同的操作，后面通常跟随 着对设备操作的函数。与之类似，s o c k e t c a t 是一个通用的插口函数的内核入 口，它决定后面将进行的操作。s i g r e t u r n 用于从信号处理中返回，并清理调用 。 栈。 从理论分析，进程不同的执行所完成的操作是不同的，从图中看从起始节点 到每个结束节点所经过的路径都是有差异的，如果能找出这些差异，就可以找到 不同行为之间具体操作的差异，从而利用这些差异对序列进行分类。利用表1 中系统调用( 图中黑体的系统调用) 的功能分割的语义可以分割出不同的操作的 界限，从而有效的提取出这些不同的操作。下节我们将详细描述如何运用系统调 用的语义来提取出不同功能的m o t i f s 。 。 中国科学技术大学硕l 学位论文 奄l a 伟 o p e n f i l e 。 r e a d f i l e ： c l o s e f i l e o p e nk e y _ _ 、 q u e r y v a l u e jc m t h m _ d + ? 、c l o s ek e y o u e q n m m m i o n m m 目击- 。 。j ：；一一一。o m 。n k e y je ；= 一一一 ? 、 一l ? ，。、i 。o p e 。n f 。i l e ；6 0 u e p e - n k e ye i ，? ” ：i “ “” 孤e 帆。 、| 分”j j ；罢勿二 吞赫l o p e nk e y 0 0 “”曼。w 删u e 。 o p e n f i l e 。 一、一 。o u e 。r y i n f 。“a m “”，一一0 。i i n 、o r m a “l lo m 。嘣 、g i 忙a 口n o 丌n 铷e i m 图2 3 进程执行流程图 2 , 4m q t i f s 的提取算法 对于系统调用序列，由于系统环境的复杂性，即使是同一功能的操作在不同 机器上产生的系统调用也是不同的，这可能是由不同的运行环境或不同的版本造 成的，在序列上则体现为同样功能的序列有的会多出一些调用，有的会缺失一些 调用，有的会替换一些调用。为了减少这些原因造成的序列的差异，我们引入了 基于n e e d l e m a n 序列比对的方法“”来度量序列相似度，它通过动态规划的方法来 找出两个序列最大程度的匹配。 比对中匹配的个数 比对后的总长度 有了相似性的度量，下面我们给出m o t i f 的定义： 莨义t 在给定的k 条系统调萌守殉中。女7 0 t i f 是一殴系统调甬子亭矾，它至少在 这k 条亭确中魄c 条中出现， 2 4 中国科学技术大学硕士学位论文 这里的“出现”与否是基予止述的相似性度量的，若m o t i f 与某条序列中的 一个予序列的相似度大于一定的闽值，则认为m o t i f 在该序列中出现，因此相似 度阈值的选取将控制着m o t i f 的保守程度。结合系统调用序列的模型及m o t i f 的定义，我们提出了一个快速的从同类序列集合中找出m o t i f 的方法，图2 中给 出了具体算法。 p r o c e d u r e ：f i n d m o t i fi s ，t h c o u n t 。t h _ s i m ) s ：as e to fs y s t e mc a l ls e q u e n c e si nt h es a m ec l a s s t h c o u n t ：t h ec o u n tt h r e s h o l d t h _ s i m ：t h es i m i l a r i t yt h r e s h o l d r e t u r n ：as e to fm o t i f s l e tg sb eas e to fg r o u p s - i n i t i a l l yb ee m p t y , ag r o u pi sas e to fs u b r o u t i n e s f o re a c hs e q u e n c ei ns e x t r a c tt h es e g m e n t so fs y s t e mc a l l sb e t w e e nt h es p e c i a ls y s t e mc a l l si nt a b l e1 a ss u b r o u t i n e sa n dt h es e g m e n t sw h i c ha r es i m i l a rt oe x i s t i n gs e g m e n t sw i t h d e g r e eo v e rt h _ s i ma r ed i s c a r d e d ” f o re a c hs u b r o u t i n es 。 f o re a c hs u b r o u t i n eti ne a c hg r o u pgo fg s i ft h es i m i l a r i t yo rsa n dti sa b o v et h _ s i m ，t h e np u ti ti n t oga n dc o n a n u ef o r n e x ts u b m e t i n es e n d f o r： i fsi sn o ts i m i l a rt oa n ys u b r o q t i n e ，p u ti ti n t oan e wg r o u pha n da d dht og s e n d f o r e n d f o r 、 f o r e a c hg r o u pg i ng s i ft h en u m b e ro fs u b r o u t i n e si ngi sm o r et h a nt h c o u n t ，t h e na l i g na l lt h e s e s u b r o u t i n e sw i t hm u l t i p l es e q u e n c ea l i g n m e n ta n de x t r a c tt h em o t i fb yt a k i n gt h e m o s tf r e q u e n ti t e mf r o me a c hp o s i t i o no fa l i g n m e n t o t h e r w i s egi sd i s c a r d e d e n d f o r r e t u r nt h ee x t r a c t e dm e t i f s 图24 提取m o t i f 的算法 算法中通过多序列比对来分析多条序列的结构和功能的相似性”，它通过在 序列中插入适当的空格来使序列的每个位置尽可能匹配。多条序列最优比对的复 2 5 中国科学技术大学硕十学位论文 杂度是o “) ，对于月条长度为的序列。因此目前常用的算法都是通过两两比 对不断迭代进行的。本文采用了c l u s t a l 算法“，它通过两两比对来计算出任意 两个序列间的相似度，根据这些相似度建立一棵进化树，然后按照进化树自底向 上来不断迭代的进行比对。多序列比对之后，就可以得到这些序列每一个位置不 同调用发生的频率，从每一个位置提取出现频率最高的元素就构成了m o t i f 。下 图给出了一个多序列比对及m o t i f 提取的例子。 acba a l l a n a 。 abab a 一二。a b bcba 一一一一一_ b abcba ab ( a ) cba aba cba cba 0 7 5、d0 0 0 上5 、 0 0 01 0 0 b0 0 00 7 50 6 0 ：1 0 0o 0 0 00 0 0 0 0 0 7 5 0 0 0o 0 0 0 2 50 2 5o o o0 0 00 o o m o t i fbb 、 ( b )、 图2 5 ( a ) 4 条序列的比对，每一行代表一条序列 ( b ) b e 对猪果的统计及m o t i f 的提取 中图科学技术大学硕士学位论文 第3 章系统调用序列的分类 序列的分类主要有两个关键的步骤：特征提取及分类器的建立。通常序列的 长度是不相同的，为了能够把序列表示在同一的一个空间中，常用的做法是从序 列中提取特征，然后出这些特征来表示序列，并用这些被特征化了的序列进行分 类器的训练。特征提取是信息处理中种最常用的关键技术，可以说任何模式识 别问题结果的好坏都在很大程度上受到特征提取的影响。提取的特征应该能最好 的反映数据的属性，并使同类别的数据在特征空间中尽可能的接近，不同类别的 数据之间尽可能的分离。有了前面的m o t i f s 作为特征，我们便可以在m o t i f s 组成的空间中建立分类器。 对于系统自动诊断，一个进程的故障可能有多种原因，例如对于i e ，我们就 找了1 0 个经常发生的故障。因此故障与原因并非完全一一对应，我们的目标是 从这些不同原因的序列中提取特征并建立分类器来区分不同的故障原因。 对于系统异常检测，一个进程只有正常或异常两种可能的情况，因此一共只 有两类，我们的目标是利用系统正常时的行为特点对进程进行建模，并以这个模 型作为标准来监测进程的行为。 本章的主要工作就是利用上一章提出的提取m o t i f s 的算法来对序列进行分 类。 3 1 系统故障自动诊断 3 1 1 序列的表示 按照2 4 节提取m o t i f s 的算法分别从每一类故障原因对应的序列中提取 m o t i f s ，然后将这些m o t i f s 组成一个集合肮 对于每一条序列s ，我们可以将它表示为由一组m o t i f s 集合埘组成的特征空 r 间中的一个矢量： o ( s ) = 中。，( j ) ) 。m 其中 中国科学技术大学硕士学位论文 f 中。i s ) = 1 ，当脚在序列5 中出现 i 中。( s ) = o ，其它情况 为了快速的找到序列中的所有m o t i f s ，我们首先将序列按照上面所述的方 法，用指示性的系统调用切分成一些操作，然后再将这些操作与m o t i f s 集合中 的每个做比对，如果与某个m o t i f 的相似度大于一定的闽值，就认为该处出现了 一个m o t i f 。 假定训练数据中的每一条序列均按以上公式转化n y 由m o t i f s 组成的特征 空间中，接下来，我们便可以利用一些分类模型建立分类器。 3 1 2 分类器的建立 支持向量机( s u p p o r tv e c t o rm a c h i n e ) 。”是建立在计算学习理论的结构风 险最小化的原则之上的。其主要思想是针对两类分类问题，在高维空间中寻找一 个超平面作为两类的分割，以保证最小的分类错误率。实验结果证明，它在很多 领域都取得了很好的分类效果，包括文本分类，图象识别，基因表达数据分析， 蛋白质相互关系预测等。 + 使用支持向量机进行分类的一个重要步骤是确定最优分界面和支持向量。如 图3 1 所示，h 为样本空间的最优分界面，它满足： 1 i 能完全分开样本。 2 h 使得h 1 ，h 2 之间的距离最大。：其中h i ，h 2 为各类样本中离h 最近的且 平行于h 的直线。 当进行两类分类时，支持向量机使用一个超平面将多维空间训l 练数据分成 正、负两类样本；然后将测试数据放在同样的空间中，通过判断与超平面的位置 关系来判断它们是正类还是负类。 3 1 3 线性分类 图3 1 所示的是线性可分情形，我们将训练样本表示为： 中国科学技术大学硕士学位论文 s u p p o r tv e c t o r w + x + b = 0 r 、 l ：m a r g i n 图31 二类线性可分情况 d = ( x ly 1 ) ( x 。，y 。) ) ，x ，r n ，y ， - 1 ，+ 1 ) 其中1 3 为样本空间中的样本个数， ，为特征向量空间的维数，表示第，个特征 向量所属的类别，这里是两类问题的分类，我们用+ l 和一1 来表示两类。 如图3 1 所示，给定特征向量w 和参数6 ，特征空间的超平面满足 w x + b = 0 ，空间中的样本满足： 。 搿1 4 ；b 嚣- 1 w 们h e 8 n 筹 - “1 ， x + = 因此，分类问题转化为求一组最优化的w 和b ，即确定最优分界面，使得+ 1 ， l 两类样本之间的最近距离( 图中m a r g i n ) 最大。假设d 和d 一分别表示最优分 界面到正负样本的最小距离，由图3 1 可知m a r g i n = d + d ，很容易推导出 m a r g i ”2 新。 j 至此，最优分界面可以通过在公式3 1 约束下求解使2 11 w 最大而得到， 令而( i = l ，2 - n ) 为n 个非负拉格郎日乘子，以上最优问题等价于求解以下方程的 鞍点： 印= 圭w w 一掌d 肌( w x j + b ) 一， ( s - 2 ) 中国科学技术大学硕士学位论文 对w 和b 分别求偏导数，可以得到 面o l = 羔邶，= 。 从而得到 乩 告。 丽2 ”二q 一刮 ( 3 3 ) ( 3 4 ) w = q y ，一 ( 3 5 ) 以及 6 ：一妻沁 ( ”一) m 。 + 坳( ”q ) 。 ( 3 6 ) 将( 3 1 3 ) 代入( 3 - 1 0 ) ，方程等价于求印= ，一q q y ，y ，( ，_ ) 在条件 ， z , j d ，y ，= 0 下的最大值，其中所有包含非零系数的向量被称为支持向量( s u p p o r t v e c t o r ) 。在确定了支持向量和参数b 之后，分类的决策函数可以表示为( 3 7 ) ， 这样将新来的样本向量带入( 3 - 7 ) 就可以判断它所属的类别了。 厂( x ) = s i g n z d 。y x ，x + 6 】 ( 3 7 ) 3 1 4 非线性分类 现实世界中的问题通常是线性不可分的，上面介绍的方法不适用于非线性可 分的情形，为了解决这一问题，可以引用核函数( k e r n e lf u n c t i o n ) ，将在低维 空间中不可分的样本映射到一个高维空间中，使得样本在这个高维空间中线性可 分。”。图3 2 给出了二维空间向三维空间映射的示例，通过核函数的映射，原 本在二维空间中线性不可分的情况变成了三维空间线性可分的情况。这时决策方 程变形为 厂( j ) = s 劬 d ，y ，k ( x ，x ) + 明 ( 38 ) 仁i 中国科学技术大学硕士学位论文 此时 y 2 图3 2 二维特征空间向三维特征空间映射示例 6 ：一； 埘h a j y j k ( b i ，_ ，旷m a x a y j k ( x ，) ，】) ( 3 - 9 ) is vs 7 常用的核函数有以下几种： ， 1 多项式核函数女( b x ，) = l + ( t 一) “ 2 高斯径向基函数k ( x i , x j ) = e x p ( - i ix , 一_ l 哆菇： 3 指数径向基函数“t j ) 2 e x “一卜i 一。步乏： 4 s i g m o i d 核函数，也称为多层神经网络核 3 1 5 多类的支持向量机 s v m 是定义在两类问题上的，对于系统故障诊断来讲，一个进程有可能有很 多种故障，这就需要我们建立一个多类别的分类器。对于一个多类的模式识别问 题，比如说k 类问题，我们的目标是把模式空间划分为k 个区域，每一个区域对 应着k 个模式中的一个。多类问题是只把模式空间划分成两个子空间的问题的推 广。对于借助于两类问题来推广到多类问题的分类器通常要解决如下三个问题： 1 要有一种有效的学习方法。 2 要有一种方法把多类问题划分成一系列的两类问题。 中国科学技术大学硕士学位论文 3 找出一种合理的判决方法来处理这一系列两类分类器的输出结果。 常用的解决方法有一对多( o n e a g a i n s t r e s t ) 的方法，一对一 ( o n e a g a i n s t o f l e ) 的方法，和二叉树的方法等等”。 1 一对多( o n ea g a i n s t r e s t ) ：其基本思想是把某一类的样本做为一 个类别，其余类别的样本当作另一个类别。这样就变成了一个两类问 题。第j 个s v m 是将第j 类作为正例，其余的全部做负例训练得到的， 最终的输出结果是在这斤个s 州中找到最大输出值的那个做为最终类 别。 2 一对一( o n e a g a i n s to r l e ) ：其基本思想是对每两个不同的类的样本 训练一个s v m 分类器，这样对k 类样本就需要训练k ( k 1 ) 2 个分 类器。训练每一个分类器时只用了相关那两类的数据。最终的输出结 果是所有的分类器通过投票决定，其票数最多的那个就是最终的分类 t 结果 3 二叉树：其基本思想是采用多级的结构，即在每一级把问题再划分成 两个子问题，这样在其最后的一层就可以完全解决多类问题的分类。 3 1 5 1 一对多组合方法( o n e a g a i n s t r e s t ) 如图3 3 所示，图中的四个圆圈代表4 个类，每一条直线都代表一个超平面。 从图中可以看出每一个类同其他的所有的类都存在一个超平面，这种方法对于k 类问题需要个s v m ，每个s v m 的两个子集按照如下的规则构成：对于第k 个s v m ， 令a 。= ( c ， ，b 。= c a ，其中k 表示第k 个s v m ，那么第k 个s v m 的两个训练 子集为五= ( x ，c ，) 旧a k ) ，口= ( x ，c 川c ，b ，则每个训练样本对于第k 个s v m 的理想输出为：一矿( 工) 一l 一( 曲。分别训练每个$ v m ，对于第七个s v m ， 我们可以得到一个判别函数，。( x ) ，最终的分类输出有两种形式，第一种为： 0 ( x ) = k ，当s g n 。( x ) = l 第二种为取判别函数的输出为最大的s v m ，即： 中国科学技术大学硕士学位论文 ( x ) = a r g m a x f ( x ) ( 3 1 0 ) | h 4 图3 3 一对多形式构成的分类器示例 一对多形式构成的多类分类器的分类性能的分析：对于第一种判别分类方 ： 式，由图3 3 中可以看到样本a 同时处于超平面h 1 ，h 2 的正侧，即s g n f 1 ( z ) 】与 s g n 厂2 ( x ) 】同时为正值。按照分类决策准则这时无法判断样本a 属于第一类还是 第二类。再看样本b 所处的位置，样本b 位于所有的超平面的负侧，这时无法对 b 进行分类。对于第二种分类的决策方式，当a 位于图中的位置可以被分类，但 是这时能否被正确的分类值得怀疑，即若a 属于第一类时，但离超平面h 1 的距 ： 离大于离超平面h 2 的距离时，这时决策输出的结果为第二类，为错误的分类结 果。对于样本b ，这种分类决策方式同样存在无法分类的情况。由图3 4 可以看 出l 对多的方式产生分类错误的根本原因是，各个超平面的分类结果存在交叠的 区域。例如当一个属于第一类的样本用第一个超平面分类时显示为第一类，当用 第二个超平面分类时如果也输出正值，就会产生无法正确分类的情况。实际上， 对于第一类的样本只有第一个超平面对这个样本分类才有意义，而其它的超平面 的分类结果可以看作是分类噪声，但是我们无法在分类之前就知道该样本到底属 于哪一类，所以在分类判别中只好对各个超平面的分类结果平等对待，这样也就 无法去除或抑制分类噪声，所以不能得到满意的分类结果。 中国科学技术大学硕士学位论文 3 1 5 2 一对一的组合方法( o n e - a g a i n s t o n e ) ( 百、卜一l 一俞 、r f 、一7 。 。 l ， 一t x o 7 b a p f t x i 、， 长二_ 一 + 戈 g f ( x ) 时才能产生错误的分类结果。由第j 类的 样本对于第k 类有关的分类器可以看成是随机的输入，通常第j 类的样本对于 类有关的分类器产生的f j ( x ) 都很小，所以要使，( z ) 厂( z ) ，这样的概率是很 小的。只有当样本比较接近第j 类的中心时，此时与第j 类有关的分类器往往显 示这个样本为第j 类的样本，这样才导致了最终的分类错误。所以总体上这种由 两类分类器组成的多类分类器的效果较好，但是需要由麒萨1 ) 2 个二类分类器 构成。 3 ，1 。5 3 二叉树的组合方式 由于s v m 只可以用来解决两类问题的分类问题，当要把s v m 用于多类问题时， 很容易想到采用多级的结构，即在每一级把问题再划分成两个子阃题，这样在其 最后的一层就可以完全解决多类问题的分类。这一解决问题的方法就是采用y - 叉树的方法。用s v m 采用二叉树的方法来解决多类的问题通常可以采用两种结 构，一种是对称的结构，另外一种是非对称的结构，如图3 5 所示。 a b 图35 二叉树结构 图3 5 a 中是对称的结构，它在每一级中尽量把问题划分成规模相当的两个 j 子问题，这样划分问题的意义是可以通过用最少的级数来解决问题，从图中可以 看到，如果要解决一个k 类问题需要有k = 1 0 9 。k 个级数划分来解决，共需要 中国科学技术大学硕士学位论文 k 1 个s v m 分类器。 图3 5 b 中的结构为非对称的方式，在它的每一级都可能得到一个最终的分 类结果，这种方法同样需要k - 1 个分类器，但是却要有k - 1 级划分。这种结构在 扩展时，只要在最后的一个节点上继续添加分类器就可以了。 二叉树方法是一种非常直观的解决问题的方法，它的解决问题的思路是不断 的把问题划分成更小的规模的问题来解决。但是采用二叉树来构造s v m 多类问题 也不可避免决策树的一些缺点。比如错误是自顶向下传播的，也就是前一级产生 的错误分类将导致最终的分类错误。所以在构造二叉树时通常要尽量避免过多的 级数划分。图3 5 中a 的结构通常能产生比图b 结构更好的分类效果。再者，每 一级划分中的两类的不同组合产生的分类效果是不同的，由于其分类效果的传播 性，所以各个分类器就要精心的调整其所分的两类的组合方式，在实际运用中这 种调整是相当麻烦的。 3 1 5 4 二类s v m 构成多类分类器的总结 以上是由二类s v i v l 分类器构成多类分类器的常用方法。其中一对一的方法具 有最强的分类能力，能够产生最好的分类效果，但是需要的s v m 分类器也最多， 对于一个k 类的问题需要k ( k 一1 ) 2 个s v m 。由于这种方法所需要的s v m 的个数 与k 成平方的关系增长，当k 达到了一定的规模时就需要训练大量的s v m ，这一 点限制了这种方法的应用。一对多的方法对于k 类问题只需要k 个s 勘，但是由 于各个分类器存在交叠的区域，即使所有的分类器都输出正确的分类结果，最终 的分类结果也不一定正确，所以这类分类器的效果不理想。二叉树方法虽然只需 要 1 0 9 ：k 个分类器就可以解决k 类问题的分类，但是这组分类器中一旦某个s v m 给出错误结果，将导致最终的分类错误。二叉树的方法是一种通过二类问题解决 多类问题的一种最直观的方法，但是由于其误差的自上而下的传播，以及各级的 不同组合方式对最终结果的影响而限制了二叉树的构建及最终的分类效果。 3 2 入侵检测 根据着眼点的不同，对入侵检测系统有多种分类方法。 ( 1 ) 数据来源 中国科学技术大学硕士学位论文 按照数据来源不同，可以将入侵检测系统分为3 类： a 基于主机：系统获取数据的依据是系统运行所在的主机j 保护的目标 也是系统运行所在的主机。 b 基于臃络：系统获取的数据来源是网络传输的数据包，保护的目标是 网络的运行和子网的安全。 c 混合型：就是既基于主机也基于网络。混合型一般也是分布式的。 ( 2 ) 分析方法 根据数据分析方法的不同，入侵检测系统分为2 类： a 误用检测模型( m i s u s ed e t e c t i o nm o d e l ) ：误用检测是指运用己知的攻 击方法，根据已定义好的入侵模式，通过判断这些入侵模式是否出现来检测 入侵。这种方法由于依据具体特征库进行判断，所以检测准确度很高，并且 因为检测结果有明确的参照，也为系统管理员做出相应措旌提供了方便。主 要缺陷在于只能检测已知的攻击模式，当出现针对新漏洞的攻击手段或针对 旧漏洞的新攻击方式时，需要由人工或者其它机器学习系统得出新攻击的特 征模式，添加到误用模式库中，才能使系统具备检测新的攻击手段的能力。 图3 6 是典型的误用检测模型。 掺投已有规刚 时荆储患 图3 6 误用检测模型示意图 b 异常检测模型( m i s u s ed e t e c t i o nm o d e l ) ： 异常检测是目前入侵检测系统的主要研究方向，它是指根据使用者的行为或 资源使用状况来判断是否入侵，而不依赖于具体行为是否出现来检测，所以也被 ： ! 旦型兰垫查丕兰塑主兰焦笙苎 称为基于行为的检测。异常检测基于统计方法，使用系统或用户的活动轮廓来检 测入侵活动。活动轮廓由一组统计参数组成，通常包括c p u 和i o 利用率、文件 访问、出错率、网络连接等。这类i d s 先考生主体的活动轮廓，系统运行时，异 常检测程序产生当前活动轮廓并同原始轮廓比较，同时更新原始轮廓，当发生显 著偏离时即认为是入侵。可以看出，按照这种模型建立的系统需要一定的人工智 能，该技术的关键是特征的选择及序列f 刚的相似性比较。图3 7 是典型的异常检 测模型。 望新 动态产。生糯 的行为持摄 图3 7 异常检测模型示意图 这种基于行为的检测与系统相对无关，通用性较强。它甚至有可能检测出以 前从未出现过的攻击方法，不像基于知识的检测那样受已知脆弱性的限制。但因 为不可能对整个系统内的所有用户进行全面的描述，况且每个用户的行为是经常 改变的，所以它的主要缺陷在于误检率很高。尤其在用户活动较多，或工作目的 经常改变的环境中。其次由于统计简表要不断更新，入侵者如果知道系统在检测 器的监视之下，他们可能慢慢地训练检测系统，以至于最初认为是异常的行为， 、 经一段时间训练后也认定是e 常的了。 在异常检测方式中，主要包括量化分析、统计分析、非参量化统计分析和神 经网络等方法，其中最广泛使用的是概率统计分析方法。 异常检测系统的效率取决于正常行为模型的完整性以及对正常行为的描述。 本文巾我们通过从正常系统调用序列中提取有意义的模式来对正常行为进行建 模，系统调用序列可以描述系统的文件访问、网络使用等核心行为，因此从系统 调用序列中提取特征可以很好的描述系统的行为。 中国科学技术人学硕士学位论文 ( 3 ) 时效性 按照数据分析发生的时间不同，可以分为： a 脱机分析：就是在行为发生后，对产生的数据进行分析。如对日志的审核、 系统文件完整性的检查等都属于这种。 b 联机分析：就是在数据产生或发生改变的同时对其进行检查，以发现攻击 行为。这种方式可以实时的检测，对系统资源要求比较高。 本文主要研究的是基于主机的异常检测模型，我们通过监视在主机运行的进 程调用系统调用的情况来进行联机分析，从而检测入侵。与故障自动诊断不同， 在异常检测系统的训练过程中，我们只用正常行为的序列，通过2 4 节中m o t i f - _ 的提取算法找出训练数据中所有的m o t i f s ，并将其存入数据库中作为特征来描 述系统的正常行为。对于一条新的序列，我们通过系统轮廓分析引擎来提取序列 中的特征，然后再由异常检测器来分析这些特征是否正常，并得出最终的结果， 当发生