（信息与通信工程专业论文）序列固有模式理论与应用.pdf

摘要 摘要 随着数据库的迅速发展，网络及其他信息技术的广泛应用，生产生活中存储 的数据量迅速增加。数据挖掘作为一种在大量的数据中寻找有价值信息的数据分 析工具，受到越来越广泛的关注。数据挖掘旨在从海量数据中发现隐藏着的、先 前未知的并潜在有用的模式和信息，以帮助人们正确理解和认识数据并做出科学 决策。并且，由于序列在数据集中普遍存在，通过对序列进行数据挖掘，发现其 异常行为和预测其未来趋势己成为当前研究的焦点之一。 异常挖掘常常应用于金融、医疗、网络等重要领域，漏报与错报必然会带来 巨大的困扰甚至损失。目前已有的各种异常序列挖掘算法在检测的准确率和挖掘 的效率上都不尽人意。因此，有必要对异常序列挖掘算法进行更深入研究，开拓 新思路，提出新算法，以提高准确率，降低漏报错报率，进而能够更加快速高效 地挖掘出数据中的异常行为，提供更有价值的信息。 本文从入侵检测和e c g 异常检测两个现实问题出发，通过对国内外各种数据 挖掘算法，特别是异常序列挖掘相关研究，针对已有异常序列挖掘算法的不足， 首次提出固有子序列模式和固有趋势子序列模式的概念，并基于这两个概念对异 常序列挖掘问题进行分析研究，提出了新的算法和解决方案，取得了以下成果： 1 ) 根据系统进程w i n d o w sn a t i v ea p i 序列以及网络连接序列出现某操作时， 总是表现为很强的整体性的特征，本文首次提出固有子序列模式的概念，并在此 基础上提出了基于图的固有子序列模式挖掘算法以及基于固有子序列模式分解的 异常检测算法。上述算法分别应用于w i n d o w s 平台和l i n u x 平台网络和主机的入 侵检测系统中，取得了较好的效果。 2 ) 根据e c g 序列随心脏活动变化反应不同趋势的本质特征，本文首次提出 固有趋势予序列模式的概念。并在此基础上提出了固有趋势子序列模式挖掘算法 以及基于固有趋势子序列模式分解的异常检测算法。上述算法应用于e c g 信号的 异常检测中，实验证明该算法在e c g 异常检测中具有较高效率和准确率。 关键字：序列，固有子序列模式，固有趋势子序列模式，异常检测，系统调用， w i n d o w sn a t i v ea p i ，e c g a b s t r a c t a bs t r a c t w i t ht h eb o o m i n gg r o w t ho fd a t a b a s e ，i n t e r a c tn e t w o r k sa n do t h e rk i n d so f i n f o r m a t i o nt e c h n o l o g i e s ，t h e r ei sag r o w i n gn e e df o rt u r n i n gt h ec o l l e c t e dd a t ai n t o u s e f u li n f o r m a t i o na n dk n o w l e d g e a sar e s u l t ，d a t am i n i n gh a sa t t r a c t e dag r e a td e a lo f a t t e n t i o n d a t am i n i n gh e l p st od i s c o v e rh i d d e nk n o w l e d g ef r o mv o l u m e so fd a t a , s o t h a tw ec o u l dh a v eat h o r o u g hc o m p r e h e n s i o no ft h ed a t aa n dm a k er i g h td e c i s i o n s f u r t h e r m o r e ，t h em i n i n go fs e q u e n t i a ld a t a , e s p e c i a l l yt h ed e t e c t i o no fa n o m a l i e si n s e q u e n c e si sa l li m p o r t a n td a t am i n i n gi s s u ew i t hb r o a da p p l i c a t i o n s a g o o da n o m a l yd e t e c t i n ga l g o r i t h m sc o u l db ev a l i d a t e di nm a n yf i e l d s ，s u c ha s f i n a n c e ，p h y s i c sa n di n t e m e tn e t w o r k s h o w e v e r ，t h ee x i s t i n ga l g o r i t h m so fa n o m a l y d e t e c t i o ns u b j e c tt oh i g hf a l s ea l a r mr a t e sa n dl o wd e t e c t i o nr a t e s t h u s ，i ti sv a l u a b l et o d e v e l o pn e wa l g o r i t h m st os l o v et h ea n o m a l yd e t e c t i o np r o b l e m si no t h e re f f e c t i v e w a y s t h i st h e s i sb r i e f l yi n t r o d u c e st h ew o r ki nt h ef i e l do fd a t am i n i n g ，e s p e c i a l l yt h e r e s e a r c ho nt h ea n o m a l yd e t e c t i o ni nt i m es e r i e si nt h ef i r s tp l a c e t h ef o r m a ln o t a t i o n s o fi n t r i n s i cs u b s e q u e n c e sa n di n t r i n s i c 订e n ds u b s e q u e n c e sa r ef i r s tp r o p o s e di nt h i s w o r k t h e n , s o m ea l g o r i t h m sb a s e d0 1 1t h ed e f i n i t i o n so fi n t r i n s i cs u b s e q u e n c e sa n d i n t r i n s i ct r e n ds u b s e q u e n c e sa r ed e v e l o p e dt os o l v et h ep r o b l e m so fa n o m a l yd e t e c t i o n i ns e q u e n c e t h ee x p e r i m e n tr e s u l t sd e m o n s t r a t et h e u t i l i t ya n de f f i c i e n c yo ft h i s a p p r o a c h a n d t h em a i nc o n t r i b u t i o n so fo u rw o r ka r el i s t e da sf o l l o w s ： f i r s t l y ，c o n s i d e r i n gt h ei n t r i n s i cn a t u r eo ft h es e q u e n c e so fw i n d o w sn a t i v ea p i a n dn e t w o r kc o n n e c t i o n s ，t h eo r i g i n a ld e f i r f i t i o no fi n t r i n s i cs u b s e q u e n c ea n dt h ei d e ao f d e c o m p o s i t i o no fs e q u e n c ea r ei n t r o d u c e di nt h i sp a p e r ，w h i c hc o u l db ev a l i d a t e di n d i v e r s ed o m a i n s a ni n t r i n s i c s u b s e q u e n c ei s t h e l o n g e s ts u b s e q u e n c ew h o s e s u b s e q u e n c e sa p p e a rt h es a m et i m e si nt h es e q u e n c e a ni n t r i n s i cs u b s e q u e n c em e a n s t h a ta l li t e m si ni ta r ea l w a y sp r e s e n tt o g e t h e ra saw h o l ei ns e q u e n c e t h e yc o u l dn o tb e s e p a r a t e df r o me a c ho t h e rb e c a u s eo ft h es t r o n gi n t e g r i t yo ft h ei n t r i n s i cs u b s e q u e n c e i n f a c t , s u c hd e f i n i t i o no fi n t r i n s i cs u b s e q u e n c ei ss i g n i f i c a n ti nt h es e q u e n c eo fs y s t e m c a l l so fas y s t e mp r o c e s s w h e nap r o c e s si sr u n n i n g ，s o m eo p e r a t i o n sa r ee x e c u t e di n a b s t r a c t c e r t a i no r d e ri n s y s t e mc a l l s i fa l lo p e r a t i o n i se x e c u t e di nt h e p r o c e s s ，t h e c o r r e s p o n d i n gs u b s e q u e n c ew i l la p p e a ri nt h es e q u e n c eo fs y s t e mc a l l so ft h ep r o c e s s s u c hs u b s e q u e n c ei sc o n s i d e r e da sa ni n t r i n s i cs u b s e q u e n c ei nt h es y s t e mc a l ls e q u e n c e a n dt h e nw ed e m o n s t r a t et h eu t i l i t ya n de f f i c i e n c yo fo u rn e w a p p r o a c ho nt h ed a t as e t s o fi n t r u s i o n so nb o t hl i n u xa n dw i n d o w s o p e r a t i n gs y s t e m s 2 c o n s i d e r i n gt h ep e c u l i a r i t yo ft h ee c gs e q u e n c e ，t h ef o r m a ln o t a t i o no fi n t r i n s i c t r e n ds u s b e q u e n c ei sp r o p o s e df o rt h ef i r s tt i m e a ni n t r i n s i ct r e n ds u b s e q u e n c ei st h e s u b s e q u e n c et h a ta l li t e m sh a v es i m i l a rt r a n s f o r m a t i o nt r e n d a c t u a l l y ，t h ed e f i n i t i o no f i n t r i n s i ct r e n ds u b s e q u e n c ei s s i g n i f i c a n ti ne c gs i g n a l s i nt h ec o n t i n u o u se c g s e q u e n c e ，t h e r ei san e a r l ys t a b l et r a n s f o r mt r e n di nas m a l lr a n g e 1 1 1 ed a t ai nt h i ss t a b l e t r a n s f o r mt r e n dr a n g eh a v es i m i l a rt r a n s f o r mc h a r a c t e r i s t i c a n dt h e ya r en e a r l ys t a b l e c o m p a r e dt ot h ed a t ao u to ft h i sr a n g e t h e r e f o r e ，t h es u b s e q u e n c ew i t hs t a b l et r a n s f o r m t r e n di sc o n s i d e r e da sa i li n t r i n s i ct r e n ds u b s e q u e n c e a st h ej u m pc h a n g eo fd a t a a l w a y ss h o w sac h a n g i n gs i t u a t i o ni nt h ea c t i 、，i 够o fh e a r tm u s c l e ，t h es t a b l es e g m e n t a l s or e p r e s e n t sas t a b l es t a g ei nh e a r ta c t i v i t i e s t h u s ，t h ed e f i n i t i o no fi n t r i n s i ct r e n d s u b s e q u e n c ee x a c t l yc o i n c i d e s 丽n lt h es t a b l ea c t i v i t yo fh e a r tm u s c l e f i n a l l y ，w e d e m o n s t r a t et h eu t i l i t ya n de f f c i e n c yo fo u rn e wa p p r o a c ho nt h ed a t as e t so ft h e m i t o b i ha r r h y t h m i ad a t a b a s e ，e u r o p e a ns t td a t a b a s e ，q td a t a b a s ea n db i d m c c o n g e s t i v eh e a r tf a i l u r ed a t a b a s e k e y w o r d s ：s e q u e n c e ，i n t r i n s i cs u b s e q u e n c e ，i n t r i n s i ct r e n ds u b s e q u e n c e ，a n o m a l y d e t e c t i o n ，s y s t e mc a l l ，w i n d o w sn a t i v ea p i ，e c g i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意 签名：日期：2 0 0 9 年歹肛多日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 第一章绪论 第一章绪论 数据挖掘( d a t am i n i n g ，简称d m ) 是一种重要的数据分析方法，旨在从海 量数据中发现隐藏着的、先前未知的并潜在有用的模式和信息，以帮助人们正确 理解和认识数据，并利用这些数据进行科学决策。 数据挖掘处理的数据种类很多，序列数据是最常见的一种。它是指用数字或 符号表示的有序数据集，也特指由连续的实值数据元素组成的序列。因此，对序 列数据所进行的序列数据挖掘( s e q u e n c ed a t am i n i n g ) 是数据挖掘中研究最早也是 最活跃的领域之一。 序列数据挖掘包含高维数据的可视化、相似性挖掘和聚类、序列模式挖掘、 周期模式挖掘、异常挖掘等重要方面，其中，序列数据异常挖掘在视频监控、产 品检测、化学分析、网络入侵、病毒检测、医学分析等各个领域有极其广泛的应 用。如何通过对序列数据快速准确的分析处理，检测数据中存在的异常状况，预 测数据未来走向，成为一个越来越重要的研究课题。 1 1 课题背景 1 1 1 序列挖掘的意义 大多数生产、医疗、经济、金融等领域的序列数据都以时间为基准、呈序列 状排列，是随着时间连续变化的数据，其反映的大都是某个待观察过程在一定时 期内的状态或表现。据调查，从1 9 7 4 年到1 9 8 9 年间出版的1 5 种世界性报纸中抽 样出的4 0 0 0 副图表中，有超过7 5 都是用于显示时间序列。对这些数据的研究， 目的主要是以下两个方面：其一是学习待观察过程过去的行为特征；其二是预测 未来该过程的可能状态或表现。这两个目的直接带来了序列数据挖掘中的两个问 题：一个是查找相似的行为模式；而另一个显然更重要的问题就是异常活动检测。 异常检测就是找出大量数据中少数与其他数据不相符合的部分，在应用中经 常涉及到错误检测或入侵检测等方面，通过序列的比较或者是数据出现概率等方 式来实现的。比较简单是对正常的序列建模，再通过检测与模型不符的数据来发 现异常。但这一方法前提是需要获得关于正常的序列的知识，于是也可变通为对 电子科技大学硕士学位论文 所有拥有的数据进行建模，再用这个模型对数据进行筛选。异常挖掘展示出序列 数据以时间轴方向发生的异常变化，对分析数据内含的信息，研究数据的趋势和 走向，定位问题所在，进行正确决策有重要的意义。 1 1 2 异常挖掘的方法和问题 由于异常挖掘的重要意义，从数据挖掘被提出起，就是国内外学者的研究热 点。结合现实中的问题，提出了各种各样关于异常挖掘的方法，在计算机科学和 生物医学等各个领域上有很多成功的应用。 1 1 2 1 基于人工免疫模型的异常挖掘 人工免疫从提出起就被应用于各个领域，异常挖掘也不例外【5 3 】【5 4 】【5 5 】。f o r r e s t 曾在人工免疫思想的基础上提出基于系统调用序列来检测系统异常入侵【5 6 】。对于 正常的系统调用序列建立自体集，根据系统调用序列和自体集( 正常的系统调用 序列) 的差异来检测系统是否出现异常或入侵 2 3 】f 1 0 1 。该算法首次提出基于系统调 用序列检测的思想，开创了入侵检测的一个新思路，相对于传统的特征码的检测 方法，该算法在检测未知异常和新异常取得了较好的效果。 但是，自体集的建立需要收集大量的正常序列数据，自体集的建立对于算法 起决定作用，在实际应用中，收集无噪声的正常序列存在着很多问题。同时由于 其只是基于与自体集比较差异来判断是否异常，其误报率相对较高。另外，该算 法只能检测到是否异常，却不能确定异常的类型，为异常的下一步分析造成了一 定的困难。 1 。1 2 2 基于马尔科夫模型的异常挖掘 马尔可夫模型也常用于分析和预测系统调用序列，从而检测系统是否出现异 常入侵【l9 】【3 。他们通过建立隐马尔科夫链模型通过对已知的系统调用序列的观察 来预测正常的系统调用序列，从而检测系统是否出现了异常情况。 该方法一定程度的弥补了前面f o r r e s t 算法的缺点，但是其隐马尔科夫链对于 系统调用序列的预测只能预测其临近的一些系统调用，其对于系统调用序列不能 整体的预测，因此其对于一些隐藏的活动时间长的异常调用序列检测准确率很低。 1 1 2 3 基于神经网络的异常挖掘 神经网络【7 】【2 4 】【3 2 】同样可以用于序列异常挖掘领域，基于神经网络的异常检测 2 第一章绪论 方法通过建立正常序列的特征轮廓来检测异常。该方法用正常序列来对神经网络 进行训练，并通过在训练的过程中执行梯度度下降、反向传播( b a c k p r o p a g a t i o n ，b p ) 等算法对初始权值进行调整并使其最终收敛，从而实现对正常序 列的建模，而后又将训练好的神经网络应用于检测异常序列。基于神经网络技术 的异常入侵检测系统一般都具有较好的实时性能。 其主要缺点在于初始权值的确定全凭经验，而不合适的取值可能导致神经网 络学习的时间过长，并且神经网络的需要的训练数据量较大。 1 1 2 4 基于图的异常挖掘 c a l e bc n o b l e 提出一个基于图的异常序列检测算法【4 】。该算法将序列映射到 图中，然后通过挖掘异常的特征子图，根据异常特征子图检测出异常序列。该算 法应用于网络入侵检测取得了一定的效果并证明了基于图的序列异常检测方向有 很大的发展空间。 但是，该算法在序列转换为图以后，对图的子图结构进行挖掘过程很复杂， 算法的效率不高。并且其只有对一定长度的序列生成的图挖掘其子图才有意义， 因此其实时性不强，与实际异常检测需求存在一定差距。 1 1 2 5 d i s c o r d s 的异常挖掘 e a m o n nk e o g h 提出了一个基于d i s c o r d s 6 异常序列检测算法，该方案利用 d i s c o r d s 检测异常序列。d i s c o r d s 为在一个序列中与该序列的其他子序列差异最大 的子序列，该定义具有很强的直观性，应用范围很广。他还提出了一个简单有效 的d i s c o r d s 挖掘算法，并将该算法应用与许多领域的异常检测证明了该算法的有效 性，诸如工业，医学，航天等。 虽然该算法具有很强的实用性，但是其对于杂乱无规律的序列适应性不强， 算法的效率受数据的规律性影响非常大。当序列的规律性不强或异常序列与正常 序列差异很小的时候，该算法需要几乎对所有的序列进行比较，遍历所有的子序 列，其运行时间非常长，并且漏报可能比较大。 1 1 3 与异常挖掘相关的挖掘方法和问题 异常检测不仅仅依赖于异常挖掘算法，其他数据挖掘算法甚至是其他学科的 发展，也对异常检测有重要的影响。 电子科技大学硕士学位论文 1 1 3 1 m o t i f s 模式挖掘 生物计算学中有一种通过统计学原理发现的具有生物学意义的一些重要模式 ( m o t i f s ) 【2 6 1 1 2 7 1 。该重要模式( m o t i f s ) 在不同的生物种群的基因组中具有显著不 同的分布特点，因此不同的生物种群基因组能够被区分开来。在生物的进化过程 中，不同的生物的基因慢慢的积累了不同的特性，因此他们的基因组会偏向或者 背离一些特定的重要模式( m o t i f s ) 。j e s s i c al i n 在2 0 0 2 年将生物计算学领域中的 m o t i f s 概念拓展到序列数据挖掘领域中，定义序列中重复出现的序列模式为m o t i f s l 2 【5 】【1 3 】【3 们。此后，序列m o t i f s 挖掘成为了众多科学家研究的热点，并迅速被应用于异 常挖掘【5 7 】【5 8 】。 但基于m o t i f s 的异常挖掘算法都集中在找出序列中频繁出现的子序列，同时 m o t i f s 的长度需要经过多次实验确定，然后人工设置，长度的不同设置会对最终结 果造成一定影响。此外，m o t i f s 仅考虑了频繁的子序列，没有对非频繁子序列进行 考察，存在漏报的可能。 1 1 3 2 闭合模式的挖掘 闭合模式( c l o s e dp a t t e r n s ) 的提出是为了提高对频繁模式( f r e q u e n tp a t t e r n s ) 的挖掘效率和并使得频繁模式挖掘的结果更加紧密没有冗余。其定义如下，如果 一个模式没有出现次数与之相同的并且包含其在内的模式，则此模式是一个闭合 模式( c l o s e dp a t t e r n s ) 【9 】【1 4 】【1 5 】【1 6 】【2 2 1 1 2 9 1 。 闭合模式的提出为异常挖掘开辟了新的思路，但它只考虑了数据的子集，对 于序列本身的有序性考虑的不足。同时，闭合模式也仅仅针对于频繁的具有闭合 性的模式，其对于非频繁的模式不予考虑，忽略了非频繁模式以及非频繁闭合模 式。然而，非频繁模式对于序列挖掘中的分类，聚类，异常检测等问题也有非常 关键的作用。 1 2 本文的内容和意义 1 2 1 研究内容 异常挖掘一直都是研究的热点，研究人员提出了很多异常检测相关的算法。 但迄今为止，序列异常检测问题仍然没有得到很好的解决，以上的方法都存在着 各种问题，诸如效率，准确率等等。 4 第一章绪论 本文通过对长序列异常检测的研究，结合模式挖掘的知识，创造性地提出了 固有子序列模式、固有趋势子序列模式的概念以及基于固有子序列模式和固有趋 势子序列模式的序列分解和异常检测算法，并将该异常检测方案应用于各个领域， 取得了较好的效果。 固有子序列模式是在一个序列中，包含与它在该序列中出现次数相等的子序 列的最长子序列。从固有子序列模式的定义可以看出其在序列中是以一个整体出 现并且是不能分解的，具有很强的整体性。固有子序列模式的定义在w i n d o w s n a t i v e a p i 序列中具有实际的意义。当一个进程执行某个确定的操作时，会按照一 定顺序调用相应的w i n d o w sn a t i v ea p i 从而形成一个序列。因此，在一个进程的 执行过程中，如果进行了该操作，其对应的w i n d o w sn a t i v ea p i 序列就会出现在 该进程的w i n d o w sn a t i v ea p i 序列中。该操作产生的w i n d o w sn a t i v ea p i 序列正 好符合了固有子序列模式的定义。同样计算机网络在进行某种活动时，也会产生 相应的序列，该序列也对应于固有子序列模式。 固有趋势子序列模式是在一个序列中，其包含与之变化趋势相同的子序列的 最长子序列。从固有趋势子序列模式的定义可以看出其在序列中是以一个趋势不 变的整体出现的，具有很稳定的趋势性。固有趋势子序列模式在e c g 信号中也具 有实际的意义。心电图的变化反应心脏的活动，在心脏处于某种活动之下时，心 电图具有某种稳定变化趋势，当心脏活动改变之后，心电图则反应出另外一种稳 定变化的趋势，这种稳定变化趋势的序列则符合了本文对于固有趋势子序列模式 的定义。 1 2 2 研究的意义 固有子序列模式，考虑数据先后排列顺序，即考虑的是有严格顺序关系的序 列不是集合。同时，其长度是由数据本身的闭合性所决定的。另外，固有趋势子 序列也考虑了非频繁子序列，非频繁子序列同样是序列的重要特征，对异常序列 检测具有非常重要的意义。固有子序列模式即是出现频率具有闭合性的最长子序 列，其提出对于解决序列异常挖掘问题有重要作用，同时为序列数据挖掘提供了 新的方向【4 9 】【5 0 1 。同时，在固有子序列模式的基础上，本文提出固有趋势子序列模 式的概念。固有趋势子序列模式即连续变化趋势具有闭合性的最长子序列【5 。固 有趋势子序列模式解决了连续序列异常挖掘问题，同时为连续序列挖掘的提供了 新思路。 5 电子科技大学硕士学位论文 固有子序列模式和固有趋势子序列模式具备以下意义： 1 ) 固有子序列模式或固有趋势子序列模式的长度由数据本身的闭合性决定， 其反应数据本质特征，具有很强的自适应性。 2 ) 考虑非频繁子序列的重要性，该类子序列同样反映了序列的重要特征，对 序列异常检测有非常关键的作用。非频繁固有子序列模式或非频繁固有趋 势子序列模式对于序列的异常检测，尤其是前面的算法不能很好检测到的 微小异常非常有效。 3 ) 基于固有子序列模式或固有趋势子序列模式的序列分解算法，即分解了序 列和噪声，同时不会因为分解削弱非频繁子序列，因而能够有效检测微小 异常。 1 。3 本文的研究成果 本文致力于从序列中挖掘固有子序列模式和固有趋势子序列模式，对序列按 照固有子序列模式或固有趋势子序列模式分层，然后根据其各层子序列与其对应 层的正常子序列的差异检测异常。本文将该研究成果应用到网络入侵检测和主机 行为异常检测以及e c g 信号的异常检测中取得了较好的效果。 本文通过从实际问题到理论研究，再到应用实现的研究方法，提出具有实际 应用意义的两种典型的子序列概念，并以这两种序列的挖掘算法研究为核心，做 出了两项问题创新，两项算法创新，两项应用创新以及一个原型系统实现，具体 如下： 一、问题创新：固有子序列模式 本文根据系统进程w i n d o w sn a t i v ea p i 序列以及网络数据序列的特征，提出 了固有子序列模式的概念。固有子序列模式是在一个序列中，包含与它在序列中 出现次数相等的子序列的最长子序列。从固有子序列模式的定义可以看出其在序 列中是以一个不变的整体出现的，具有很强的整体性。固有子序列模式的定义具 有实际的含义，当进程中出现某操作总是表现为固定的n a t i v ea p i 序列，该序列 就是固有子序列模式。类似地，当出现某网络行为时，也会产生相应的网络数据 序列，该序列也符合固有子序列模式的定义。 二、 问题创新：固有趋势子序列模式 本文根据e c g 序列的本质特征，提出固有趋势子序列模式的概念。固有趋势 子序列模式是在一个序列中，其包含与之变化趋势相同的子序列的最长子序列。 6 第一章绪论 从固有趋势子序列模式的定义可以看出其在序列中是以一个变化趋势不变的整体 出现的，具有很稳定的变化趋势性。固有趋势子序列模式在e c g 序列中也是具有 实际意义的。因为心电图的变化反应了心脏的活动，在心脏处于某种活动之下时， 心电图具有某种稳定变化趋势，当心脏活动改变之后，心电图则反应出另外一种 稳定变化的趋势，这种具有稳定变化趋势的子序列就是固有趋势子序列模式。 三、算法创新：基于图的固有子序列模式挖掘算法以及基于固有子序列模式的 异常检测算法。 本文提出基于图的固有子序列模式挖掘算法t 1 ) 对序列建立一个序列图； 2 ) 找出序列图中的封闭路径作为固有子序列模式的候选序列； 3 ) 在原序列中找出构成每个候选序列的固有子序列模式。 4 ) 当找出所有的固有子序列模式后，本方案根据固有子序列模式出现的频度 对其分层，然后将正常序列和测试的序列分层匹配其固有子序列模式，计 算其匹配程度，从而判断测试序列中是否包含异常子序列。 四、算法创新：固有趋势子序列模式挖掘算法以及基于固有趋势子序列模式的 异常检测算法。 本文提出挖掘固有趋势子序列模式的算法： 1 ) 找出序列t 中所有的局部最大值和局部最小值以及其在t 中对应的位置； 2 ) 找出序列t 中以局部最大值和局部最小值作为起点或者终点的子序列作为 固有趋势子序列模式。异常检测算法是将序列分解得到的固有趋势子序列 模式按照其趋势值分解为层，然后通过计算正常的序列部分和未检测的序 列部分对应层的固有趋势子序列模式的差异来判断是否异常。 五、应用创新 本文将基于固有子序列模式的异常检测算法分别应用于w i n d o w s 平台和 l i n u x 平台的网络和主机的入侵检测中，取得了很好的效果，并实现了四门i 省科技 厅项目数字免疫网络入侵检测系统( 2 0 0 6 j 1 3 0 6 5 ) ；此外，本文将基于固有趋 势子序列模式的异常检测算法应用于e c g 序列的异常检测中，试验证明其能准确 有效的检测出e c g 序列的异常子序列。 1 4 本文章节安排 本文按照如下的章节形式组织论文内容： 7 电子科技大学硕士学位论文 第一章，绪论。概述了关于序列挖掘尤其是异常序列挖掘的相关研究工作， 并对本文的主要工作简要介绍。 第二章，基于图的固有子序列模式挖掘算法以及基于固有子序列模式的异常 检测算法。提出基于图得固有子序列模式挖掘算法以及基于固有子序列模式分解 的异常检测算法。 第三章，固有趋势子序列模式的挖掘算法以及基于固有趋势子序列模式的异 常检测算法。提出固有趋势子序列模式挖掘算法以及基于固有趋势子序列模式分 解的异常检测算法。 第四章，基于固有子序列模式的异常检测算法在网络入侵检测中的应用。对 基于固有子序列模式的异常检测算法在入侵检测中的应用展开研究，将该算法分 别应用于w i n d o w s 平台和l i n u x 平台的网络和主机入侵检测中。 第五章，基于固有趋势子序列模式分解的异常检测算法在e c g 序列异常检测 中的应用。在分析e c g 序列的基础上，将基于固有趋势子序列模式分解的异常检 测算法应用于e c g 序列的异常检测中，并在m a t l a b 平台上仿真实验。 第六章，结束语。总结本文的研究工作并展望未来研究工作。 最后是致谢和参考文献。 8 第二章固有子序列模式理论与算法 第二章固有子序列模式理论与算法 本章主要研究和解决的问题如下： 1 ) 设计固有子序列模式挖掘算法，解决从序列中挖掘出其所有的固有子序列 模式的问题。该算法首先将序列映射到序列图中，然后通过挖掘图中的权 值相等的相邻边找出其固有子序列模式的候选序列，然后再回到原序列中 找出这些候选序列中真正的固有子序列模式。 2 ) 设计基于固有子序列模式分解的异常检测算法，解决序列异常检测的问 题。该算法分别将正常序列和测试序列分解为相应的固有子序列模式，并 将这些固有子序列模式分别按照其出现次数组成相应的层，然后将测试序 列和正常序列按照相应层计算其固有子序列模式的匹配程度，最后根据匹 配程度判断待检测序列是否包含异常子序列【4 9 】【5 0 】。 本文主要包含以下两个方面：首先，找出序列的所有固有子序列模式；其次， 设计一个基于固有子序列模式和分层的思想来检测出异常子序列的算法。 2 1 基本概念定义以及相关定理 2 1 1 基本概念定义 在介绍方法之前首先给出相关的概念和定义： 定义2 - 1 ：序列：一个序列t = t 1 , t 2 ，t l i 是一个按照一定顺序排列的有序数据 集合【6 1 。 定义2 - 2 ：子序列：长度为n 的序列t - t l ，t 2 ，t n ) ，长度为m 的序列 c = t p ，t p + 1 ，铀1 ，m n ，1 = p = n - m + l ，如果c 是t 中连续位置的m 个抽样数据按 照原顺序排列得到的序列，则c 是t 的子序列【6 】。 定义2 3 ：母序列：长度为n 的序列t - t l , t 2 ，t n ) ；其长度为m 的子序列 c 2 t p ，坼l ，h 1 ) 和长度为k 的子序列s = t q ，t q + l ，t p ，铀1 ，t q + k - 1 ) ，1 主q - - n - k + l ，1 耋p = n - m + l ，且m ，s 3 = 1 ，2 ， 3 ，6 ) 在t 中的支持度为1 ，小于s 的支持度，而同时s 的子序列$ 4 - - 1 ，2 ) ，s 5 = 2 ，3 ) 在t 中的支持度都等于s 的支持度3 ，则根据定义5 ，s 为t 的一个固有子序列模 式。 根据固有子序列模式的定义，我们可以得出固有子序列模式是在序列任何位 置都整体出现的子序列，其具有很强的整体性和不可分解性。由于固有子序列模 式极强的整体性，其包含的序列具有不可分解的特点。本文研究的固有子序列模 式的最小长度大于等于2 ，显然，对于长度为1 的序列研究其整体性是没有意义的。 固有子序列模式的定义是具有很强的物理意义的，例如对于进程的系统调用序列， 当进程执行某中特定操作的时候，其将对应于相应的系统调用序列来完成该操作， 则中会在其调用序列中出现该特定的序列，这样的序列对应于固有子序列模式的 定义。 前面已经定义了固有子序列模式以及其支持度，下面将定义固有子序列模式 的支持度率，用以表示一个固有子序列模式在一个固有子序列模式集中的密度。 定义2 - 6 ：支持度率( s u p p o r tr a t i o ) ：s 为一个包含n s 个固有子序列模式的 序列集合，这些固有子序列模式在s 中的总数量为n l ，i s 为s 中的一个固有子序 列模式，i s s ，i s 在s 中的总数量为p 则i s 在s 中的支持度率是p n i ，用s r s ( i s ) 表示。 基于以上固有子序列模式和支持度的定义，以下我们将定义对于异常检测算 法的关键定义层( l a y e r ) 。具有相同支持度的固有子序列模式构成一个层。 定义2 7 ：层( l a y e r ) ：序列t 以及t 的所有固有子序列模式，其中具有相同 1 0 第二章固有子序列模式理论与算法 的支持度的固有子序列模式构成t 的一层。 同上例，支持度为3 的s l = 1 ，2 ，3 ) ，以及支持度为1 的 s 2 = 3 ，4 ) ，s 3 = 3 ，5 ) ，s 4 = 3 ，6 ) ，则s l 为一层，s 2 ，s 3 ，s 4 为另外一层。由于一个序列的固 有子序列模式会分成许多层，为了区分这些不同的层下面给出新的定义。 定义2 8 ：k 层( k：如果序列t的某层，满足构成该层的固有子序列layer) 模式的支持度是序列t 所有固有子序列模式支持度的第k 大，则该层为t 的k 层。 基于以上固有子序列模式和层的定义，序列t 能够被分解为一些固有子序列 模式以及这些固有子序列模式构成的层，因为我们定义分解如下： 定义2 - 9 ：分解( d e c o m p o s i t i o n ) ：序列t 和其所有固有子序列模式，序列t 的分解即是将t 分解为固有子序列模式构成的层，即t 能够被这些包含相同支持 度的固有子序列模式的层组成。 为了设计找出固有子序列模式的算法，下面需要定义序列图等相关概念。 定义2 1 0 ：序列图( s e q u e n c eg r a p h ，s g ) 是序列t 的关系图，它是一个四元 组，即s g = ，其中： ( 1 ) v 是图中的结点集，v