（计算机软件与理论专业论文）基于日志数据挖掘的网络安全审计技术研究.pdf

山东师范大学硕士学位论文 摘要 随着计算机网络的飞速发展和普及，网络无所不在的影响着社会的政治、经济、 文化、军事和生活等方面，然而，网络在给我们的生活带来便利的同时，也产生了各 种安全问题。网络安全审计技术同防病毒、防火墙、入侵检测等安全技术一样成为网 络安全技术的重要组成部分。相对与网络外部的入侵行为，网络内部用户的异常操作 不易被发现，并能导致更大的损失。利用数据挖掘技术分析网络安全日志，挖掘出用 户行为的关联规则，进一步审计出异常行为，确保网络安全。 本文主要针对网络安全审计技术的相关问题，在如下几个方面进行了研究和探 讨： l 、介绍了网络安全审计系统的研究背景和意义，并阐述了网络安全审计相关领 域国内外的研究现状。 网络安全审计技术是网络安全技术的重要组成部分。国外专家首先提出了将数据 挖掘技术应用到安全审计的思想，我国对这方面也进行了大量的研究，提出的一些模 型，取得了不错的检测效果；但是如何根据用户日志行为记录的特点，在大数据量环 境中，找出一种占用内存比较少的高效率数据挖掘算法，以提取出反映用户行为特性 的频繁行为模式是要进一步研究的问题。 2 、研究了常见的网络安全审计系统的关键技术，详细阐述了日志获取技术、安 全保护技术、关联规则挖掘技术等，并改进了审计系统中挖掘日志记录的量化关联翘 则的算法。 本文从系统的安全架构层次和技术可操作性上，根据日志记录的可读但不可更凶 特性( 不可删除且不可修改) ，提出了日志记录的安全保护模型。该模型是按照从低 到高的安全性层次来设计的，其中的每个层次都提出了可行的解决思路。该模型为日 志记录的具体安全保护方法提供了参考。 在对日志记录的用户行为进行量化关联规则挖掘时，首先要找出满足最小置信废 的频繁谓词集。这里一般是采用基于栅格的方法，但是此方法在应用于审计日志的拄 掘时，占用了较大的内存空间。本文利用二叉排序树的数据结构来查找频繁谓词集， 较好的解决了占用内存空间大的问题。 3 、根据系统的设计目标，描述了一个完整的系统构架，给出了系统各个模块能 流程设计，并进行了相应实现。 该系统综合利用以上各种技术实现了用户行为的网络安全审计功能；系统能够柿 据审计出的用户异常行为的危险等级采取弹出对话框、发送邮件、响警告声音等不匾 的报警方式通知审计安全员；系统还支持审计规则的自动添加和手动添加，增加了豸 统的灵活性。 4 、最后，将所提出的量化关联规则挖掘算法在网络安全审计系统上进行了实骝 测试，并取得了令人满意的效果。 山东师范大学硕士学位论文 关键词：网络安全审计；量化关联规则；数据挖掘；日志 分类号：t p 3 9 3 山东师范大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n dt h ep o p u l a r i z a t i o no fn e t w o r k s ，i th a sh a dag r e a l i m p a c tu b i q u i t o u s l yo nt h ep o l i t i c s ，e c o n o m i c ，c u l t u r e ，m i l i t a r ya n dt h ew a yo fl i f e h o w e v e r , t h e r ec o u l db el o t s o fi s s u e sa b o u tt h es e c u r i t yw h i l ew ee n j o y e dt h e c o n v e n i e n c eo ft h ei n t e r n e t n l et e c h n o l o g yo fn e t w o r ks e c u r i t ya u d i ti sr e f e f r e dt oo n e o ft h ei m p o r t a n tp i l l a r so fn e t w o r ks e c u r i t yt e c h n o l o g y ，嬲w e l la sa n t i v i r u s ，f i r e w a l l ! i n t r u s i o ni n s p e c t i nc o n t r a s tw i t ht h ei n t r u s i o nf r o me x t e r i o ro ft h en e t w o r k a b n o r m a o p e r m i o no ft h ei n t e r i o rn e t w o r ku s e r sc o u l dn o tb ed i s c o v e r e de a s i l ya n dc o u l dl e a dt c m o r ed a m a g e t h u s ，u s et h et e c h n o l o g yo fd a t am i n i n gt oa n a l y z et h en e t w o r ks e c u r i t ) l o g t or e v e a lt h ea s s o c i a t i o nr u l e so fu s e r sb e h a v i o r t h e na u d i ta n df i n do u tt h ei l l e g a l i t 3 t oe n s u r et h en e t w o r ks e c u r i t y t 1 1 i sa r t i c l ed o e st h er e s e a r c hw o r kb a s e do n 廿l en e t w o r ks e c u r i t ya u d i ta l o n gw i 仕 o t h e rc o r r e l a t i v ei s s u e sa n dd i s c u s s e ss o m ep o i n t sw h i c ha r el i s t e db e l o w ： 1 ，n l ep a p e rf i s ti n t r o d u c e st h er e s e a r c h i n gb a c k g r o u n da n dt h em e a n i n go fn e t w o r s e c u r i t ya u d i ts y s t e m ，e x p o u n d st h ec u r r e n ts t a t eo fr e s e a r c h i n gw o r ki nt h ew o r l d n e t w o r ks e c u r i t ya u d i ti so n eo ft h ei m p o r t a n tc o m p o n e n t so fn e t w o r ks e c u r i t 3 t e c h n o l o g y f o r e i g ne x p e r t sf i r s t l yp u tf o r w a r dt h e i d e ao fa p p l y i n gd a t am i n i n $ t e c h n o l o g yt os e c u r i t ya u d i t , i nw h i c hf i e l do u rc o u n t r yh a sa l s oc a r r i e do u tas u b s t a n t i a ： a m o u n to fr e s e a r c ha n ds o m em o d e l so b t a i n e dg o o dd e t e c t i o nr e s u l t sa l eg i v e na sw e l l h o w e v e r , i nt h ee n v i r o n m e n tw i t hl a r g ea m o u n to fd a t a , h o wt of i n do u tad a t am i n i n l a l g o r i t h mw i t hl e s sm e m o r yb u th i g h e re f f i c i e n c yi na c c o r d a n c ew i t ht h ec h a r a c t e r i s t i co l t h eu s e rl o gr e c o r d st oe x t r a c tt h e 行e q u e n c yp a t t e r n so fu s e rb e h a v i o rs h o u l db ef u r t h e l s t u d i e d 2 s t u d i e st h ec o m m o nc r u c i a lt e c h n o l o g yo fn e t w o r ks e c u r i t ya u d i ts y s t e m e x p a t i a t e su p o nt h el o gg a i nt e c h n o l o g y ( l o ga c q u i s i t i o nt e c h n o l o g y ) ，s e c u r i t 3 p r o t e c t i o nt e c h n o l o g y a n da s s o c i a t i o nr u l e sm i n i n gt e c h n o l o g y , b r i n gf o r w a r d 廿l u p d a t e da l g o r i t h m so fq u a n t i t a t i v ea s s o c i a t i o nr u l e so fl o gm i n i n gi na u d i ts y s t e m o nt h eb a s i so fs y s t e ms e c u r i t ya r c h i t e c t u r ea n dt e c h n i c a lf e a s i b i l i t y ，as e c u r i t ym o d e o fl o gr e c o r d si sp r o p o s e di nt h i sp a p e ra c c o r d i n gt ot h ec h a r a c t e r i s t i co fl o gr e c o r d sw h i d c a nb er e a db u tn o tb ec h a n g e d ( c a nn o tb ed e l e t e da n dc a nn o tb ea m e n d e d ) t l l i sm o d e li ： al e v e la r c h i t e c t u r eo nt h es e c u r i t yf l o r al o wt oh i g hi nw h i c he a c hl e v e lh a sr a i s e dav i a b h s o l u t i o n s ot h i sm o d e lp r o v i d e sr e f e r e n c e s f o rt h es e c u r i t yp r o t e c t i o nm e t h o do fl o r e c o r d s w h e nw ee m p l o yq u a n t i t a t i v ea s s o c i a t i o nr u l e so nl o gr e c o r d st om i n eu s e rb e h a v i o r w es h o u l df i r i do u tt h em i n i m u mc o n f i d e n e el e v e lo ft h ef r e q u e n tp r e d i c a t es e t sf i r s t l ya n ( g r i d b a s e dm e t h o di sc o m m o nu s e d h o w e v e r t h i sm e t h o dw i l lo c c u p yl a r g em e m o r ，space w h e ni ti su s e di na u d i tl o gr e c o r d si nt h i sp a p e rw eu s eb i n a r ys o r tt r e ed a u s t r u c t u r et of i n dt h ef r e q u e n tp r e d i c a t es e t sa n dt h i si m p r o v e m e n tr e d u c e st h em e m o r s p a c eo c c u p i e d 3 1 1 l ep a p e rd e s c r i b e sa ni n t a c ts y s t e ma r c h i t e c t u r ea i m e d0 1 1t h eo b j e c t i v eo fs y s t e n d e s i g n i n g ，d e l i v e r st h ed e s i g na b o u t t h ew o r k f l o wo nt h em o d u l e so ft h es y s t e ma n dg i v e , , o u ti t si m p l e m e n t a t i o n i 】 瘗寒薅莛太学疆士攀整论文 t h i ss y s t e mu t i l i z e sa l lt e c h n o l o g i e sa b o v et oa c h i e v en e t w o r ks e c u r i t ya u d i tf u n c t k o fu s e rb e h a v i o r t h es y s t e mu s e sv a r i o u sw a y st on o t i f ys e c u r i 拉a u d i t o r , s u c ha sp o p ) ，b ，( 歹 1 ，刀) ) 是属性值对。关联规则xjy 解释为“满 足x 中条件的数据库元组多半也满足y 中条件”。规则的支持度( s u p p o r t ) 和置信 度( c o n f i d e n c e ) 是规则兴趣度的两种度量。它们分别反映所发现规则的有用性和确 定性。形式分别为s u p p o r t ( x 】，) = e ( x u d ，c o n f i d e n c e ( x y ) = p ( ylx ) ， 同时满足最小支持度阈值( m i n _ s u p ) 和最小置信度阈值( m i n _ c o n 0 的规则称为强规 则。关联分析算法常用的有a p f i o r i 、a p r i o r i t i d 、f p - g r o w t h 等算法。 2 3 2 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋 势，并对其建模。包括时间序列数据分析、序列或周期模式匹配和机遇类似性的 数据分析。序列模式挖掘( s e q u e n c ep a t t e mm i n i n g ) 是指挖掘相对时间或其他模 式出现频率高的模式。序列分析算法如a p r i o r i a l l ，a p r i o r i s o m e ，d y n a m i c s o m c 等。 2 3 3 聚类分析 聚类分析( c l u s t e r i n ga n a l y s i s ) 通过分析数据对象而不考虑已知的类标记。一般 情况下，训练数据中不提供类标记，因为不知道从何开始。通过最大化类内的相 似性、最小化类间的相似性形成聚类的对象。聚类分析算法如c l a r a n s ，b i r c h 在蟹 专宇o 2 3 。4 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或者模式不同。大 蠡东筛范大学矮圭学像论文 部分数据挖掘方法将这些孤立点视为噪声而丢弃。但是在一些比如欺骗检测等应 用中，孤立点事件的如现可能更有趣。 2 4 关联规则挖掘算法研究与改进 关联规则是数据挖掘的一个重要研究方向，也是数据挖掘中最成熟、最活跃 的研究领域。关联规则辨别事件之间的相互关系，并用利用这些关系进行分析， 以使褥数据的收集变得更加容易。本文简述了关联规则相关的一些概念、分类及 相关算法，并利用平衡二叉树的数据结构对应用在安全审计系统中量化关联规则 挖掘算法进行了改进，提高了原算法的空间复杂度。 2 4 1 关联规则的分类及经典算法介绍 关联规则可以分成若干类型，如； ( 1 ) 根据规则所处理的值的类型，关联规则可以分为布尔的和量化的。布 尔关联规慰表现离散对象之闻的联系。量化关联规则是多维关联规则，涉及动态 离散化的数值属性。它也可能涉及分类属性。 ( 2 ) 根据规则中数据涉及的维，关联规则可以分成单维和多维的。 ( 3 根据规则涉及的抽象层，关联规则可以分为单层和多层豹。在多层关 联规则中，项或谓词的挖掘考虑不同的抽象层，而多层关联规则考虑多个抽象层。 ( 4 ) 根据对关联挖掘的不同扩充，关联挖掘可以扩充为相关分析、最大频 繁模式和频繁闭项集挖掘：相关分析指出相关项的存在与否。最大模式是一个频 繁模式p ，使得p 的任何真超集都不是频繁的。频繁闭项集是指：若集合c 是闭的， 如果不存在c 的真超集c ，使得包含c 的子模式的每个事务也包含c 。 2 4 。1 。1 单维、单层、布尔关联规则挖掘算法以p r i o r i 算法和f p - 增长算法 1 9 9 3 年，a g r a w a l 等人首先提出了挖掘顾客交易数据库中项集间的关联规则 算法a 研o r i 算法，其核心方法是基于频繁理论的递推方法【3 4 】。a p r i o r i 算法是 发现关联规则领域的经典算法。该算法将发现关联规则的过程分为嚣个步骤：第 一步通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定 的阈值的项集；第二步利用频繁项集构造出满足用户最小信任度的规则【5 】。具体 徽法就是：首先我出频繁1 项集，记为l 1 ；然后利用l 1 来产生候选项集c 2 ，对 c 2 中的项进行判定挖掘出l 2 ，即频繁2 项集；不断如此循环下去直到无法发现更 多的频繁k 项集为止。每挖掘一层l k 就需要扫描整个数据库一遍。 在关联规则挖掘阀题中，第二步相对比较容易，可以直接产生出规则。第一 步却比较费时，对于大数据库来说计算代价很大，现实生产数据库更是如此。大 1 2 蠢客簿蔻大学磺士学像论文 的生产数据库中，项目记录上百万条，变量( 属性) 成百上千条，当数据包含有 n 个变量时，大项集的数目则可能会达到了，但实际上数据库中的大项圈集数目 会泷较小，所以就要耗费成指数倍的时阀来发现大项圈集。 针对a p f i o f i 算法的固有缺陷，j h a n 提出了不产生候选挖掘频繁项集的方法 f p 增长算法。f p 增长算法采用分而治之的策略，只需两次扫描数据库，而且不 用产生大量候选项集，将发现长频繁模式麓阀题转换力递归发现一些短模式，然 后连接后缀。在经过第一遍扫描之后，把数据库中的频繁项集压缩进一棵频繁模 式树( f p - t r e e ) ，同时依然保留其中的关联信息，随后再将f p t r e e 分化成一些条件 库，每个库和一个长度为l 的频繁顼集相关，然后再对这些条件库分别进行挖掘。 该方法大大降低了搜索开销，大约比a p r i o r i 算法快一个数量级【”l 。 2 4 1 2 量化关联规则挖掘算法 下面介绍量化关联规则挖掘算法，量化关联规则是多维关联规则，其中数值 属性动态离散化，以满足某种挖掘标准，如最大化挖掘规则的置信度或紧凑性。 传统的a r c s ( a s s o c i a t i o nr u l ec l u s t e r i n gs y s t e m ，关联规则聚类系统) 使用的方 法，其思想源于图像处理。本旗主，该方法将量化属性对映射到满足给定分类属 性条件的2 d 栅格上。然后，搜索栅格点的聚类，由此产生关联规则。下面是a r c s 涉及的步骤： ( 1 ) 分箱。量化属性可能具有很宽的定义它们域值的范围。为了使得裰格 压缩到可管理的尺寸，我们将量化属性的范围划分为区间。这些区间是动态的， 在挖掘期间它们可能进一步合并。这种划分过程称作分箱，即区间被看作“箱”。 三种常用的分箱繁略是： 等宽分箱：每个箱的区间长度相同； 等深分箱：每个箱赋予大致相同个数的元组： 基于同质的分箱：籍的大小这样确定，使 ! 孽每个箱中的元组一致分东。 在a r c s 中，使用等宽分箱，每个量化属性的箱尺寸囱用户输入。对于涉及 两个量化属性的每种可能的箱组合，创建一个2 - d 数组。每个数组单元存放规则 右部分类属性每个可能类的对应的计数分布。通过创建这种数据结构，任务相关 的数据只需要扫描一次。 ( 2 ) 找频繁谓词集。一照包含每个分类计数分布的2 d 数组设置好，就可 以扫描它，以找出也满足最小置信度的频繁谓词集( 满足最小支持度) 。然后， 由这些谓词集产生关联规则。 ( 3 ) 关联规则聚类。上步将会得到很多强关联规烫| j ，其中的某些关联规 山东师范大学硕士学位论文 则有可能进一步合并成更简单的数量更少的关联规则。a r c s 使用聚类算法做这 件事，首先将上一步褥到的强关联规则映射到2 d 橱格上，然居扫描栅格，搜索 规则的矩形聚类。用这种方法，出现在规则聚类中的量化属性的箱可能进一步合 并，从而对量化属性动态地离散化。 2 4 2 关联规则挖掘应用的优点 将关联规则挖掘技术应用予网络安全审计与取证领域需要注意“特定应 用”【3 6 1 。算法实现必须建立在特定应用的基础之上，并且需要具有足够的先验知 识，经研究表明，对系统安全的先验知识往往体现在对原始数据中有价值的变量 集的选择上，这既涉及到数据源的选择也涉及到待分析内容的选择蛰刀。与传统的 网络安全审计系统相比，将关联规则挖掘技术应用于网络安全审计系统将会有如 下几个优点： l 、准确率高 利用关联规煲| j 挖搌技术将训练数据转换成审计规则，既可以避免由于人为先 验知识的限制在推导规则过程中所产生的不确定因素，又可以避免由于数据量过 大而无法准确得出规则1 3 戤。 有些成功经过了系统审计的行为实际上可能是不合法的( 如系统管理员在深 夜登录) 。利用关联和序列挖掘技术对合法用户的行为模式加以推导，总结出用 户的正常行为模式，从而通过检验用户的当前行为来发现潜在的异常，避免了由 单纯的模式匹配方式审计时存在的漏报警闻题。 2 、大数据量下处理速度较快 目前，网络规模飞速增长和操作系统的日益复杂化，导致了待分析的行为日 志数据同样以惊人的速度倍增【3 9 】。通过综合运用多种挖掘技术对审计数据进行预 处理，大大精简了数据规模，从丽提高了分析的速度。通过黠数据进行预处理， 抽取数据中的有用部分，可以有效地减少数据处理量，提高检测效率。对于网络 上庞大数据流量来说，这一点是至关重要的删。 3 、囊适应能力强 善先从正常用户行为舀志中挖掘出正常行为模式，然后以此为据对当前网络 安全行为数据进行分析，当某用户行为不在正常行为之列时，我们就认定该行为 具有威胁。将这些彳亍为模式组成多个类，然后转变为规则添加到规则库中。这样 可以通过不断修改规则库，并进一步通过审计模块来发现异常行为。 2 5 审计系统中量化关联规则挖掘算法的改进 要对审计系统中的用户行为进行关联规则挖掘，就要弄清楚此关联规则的类 型。在圜恚记录中，一个用户行为涉及到多个满性，如事件记录的 c a t e g o r y n u m b e r 、i n s t a n c e i d 、t i m e g e n e r a t e d 、e v e n t n a m e 等属性。用户行为关 1 4 蠢客邸范大学硬圭学傻论文 联规则涉及到用户行为记录的多个属性，这样的规则是多维关联规则。下图是日 志中记录的某一个用户的某一段时闻行为。 臼鞠黼c a 嘲c a 魄p 翊豳；秘酚静辨 远程攫翻考曼禾登录j 注镑 ：翔i 阳氍 l 控捌台袅话啊井量录篷情2 鱼e 雌 j 糠 i 远程投嘲矗i i 囊鼍录，迮镝2 轴韩m i 謦改文件对象访胃 3 量“韩5 l i 蠡 i 謦改变搏鬻i 啭籍3 宴蠢端s 趣i 蠹 聱酸尊涤列蠢谚舞3 翔薛黼 l 蜂改j c 捧对妻访簿3 氯糕粥蚺l l 黛 l 惨改文件对童访屠 3量o 睇山点 i 俸改文件对童访阿 3j 唧蚋i ；另存为_ 个簧列童访目1 3 曩e 苗咖，喊 i 另存为一个囊礞谚舄 35 | 矗嚣柏蠢 l 曼夺蠢令囊，鬻羹谚筹3i 嚣薛噙i 蘸 i 男存隽令謦川辩重谚簿3 复数辑k i 蠢 另存为一个撕，对熏访博 3f l u c c e s c , a u 睫 ；另存为_ 个暂 对象访目3量吐蚋穗 i 另存为一个纂川对重访阿3 瓢伍 u 蠢 耪改文捧对象访舄 3 群苈 瞳 l 蓐蔽芟辩蔫蠢谚拜3 妻群葛触 跨酸变捧棘涛薅3知酵5u蘸 修改文棒列量访鳟 3 翱旺魄 t i 蠢 i 修改文件列量访筒。3s 呱蒉嘲糠 l 謦改文件对童访阿 3曼旺5ldt ；硼缎件耐妻访再 3i e 旧； i 蠢 ；l 凝交搏鬻囊滂霸z 罩量搿嚣柏矗 ；薹黼芰搏麓羹涛簿3 鬟瞄陈触 i 量融文件 对量访簿3 宴鼬睬；a u 蠢 ；删除文件对量访胃3 鱼“韩 u 糠 i 髓火埔撩博棋鹪改动6 鱼“苗m i 髓火墙攘伶镬鹪改动 ，6 知i 1 矗 撕建酌酬鹣| d 如晡妇糖翱e 凇琢的韵瞄增群黼礅相捌蠢 鞠冉q 回：翮砧斜瓣n - 抬譬：抖：撕：魁哪y 朝口臂 皤1 嘲螂】匀m r 姗1 1 豹9 ：篇：芷：埘眦n 归忡m ：i s 睇)：如m y 狮1 1 - 9 ：s 7 ：棚硼 哪啊“一1 5 q 5 】；翱哪r 册l i 箱9 ：静满： m 拍哪怕m 壕 ，1 s 6 7 嘏鞍：匀嘲2 0 0 8 - 1 1 - 2 3 9 1 努i 薹：髫弧即嘲嗤 酶 l ，尊鞠餐：知皤帮瓣l l 嚣辍嚣燃：难弱嚣扫n g 嘴豳鼯 1 5 甜真唧 ：s e c u 瞳y 瓣n - 器警：3 7 ：3 6：撑烈n 埘粕1 搴鸵球】：囊斜z 0 0 8 - t l - z 3 9 ：3 7 a 5 ：札d m y a 哪r 婚，l ，5 硭 螂】：翱呲y2 d o b _ l l 嚎3 9 ：3 7 ：筠：棚t 、埘甘h 1 锄蝤】：5 雌y2 0 0 8 - l l 豹9 ：3 7 ：3 6 ：m 拼t 、哪甘如 1 1 5 睇，j 翱瞅r0 b - i i 稳9 ：3 7 ：4 1 1：罐翻堍灌哪赫 1 s 瞳囊啕：复a l 盼嚣i 1 1 - 2 3 事：3 7 ：螺：鬣习嚣缸蠢州l 舔 l _ - 一 ”4 。掌囊电站i 钿竹鞠l l l 警：积档：越嘲即n 嘲将1 5 6 7 袄s 】：s e c u 吐v 狮“- 期譬：甜：舶：m m w 曩h 埔 1 5 甜帕卯：窝啾y2 1 1 1 8 - 1 1 嚣9 ：剪：锵：越帆y 神 咖a1 ，5 h q s 】 ：如咖q 摒“箱9 ：辩；帕 ： l t 、 哪r 簟h 埽 1 搴棚郾! 舅哦y 瓣1 1 - 2 3 掌：静l 鹄：棚翻砖膜 嘞糟 ；1 搴静戴瞄：寞瞅r2 b 1 l - 警= 嚣：蝣：鬣嘲弼啊潆妇瓣 1 掌皤敞站；轴c 注脚搬l l 2 3 警：嚣鹕7 矧d 霸舛啊漆 端1 铜 ，：勇酊睁l l 9 ：3 7 ：特：m n 懵v t 5 6 7 q s 】：s e c u r 印狮l l * 豹9 ：射：伯： l 哪朋e m 喃 1 5 醴 q 辩：翱叫却姗l i - 鼢9 ：辩；憾：棚科t 、”呻懈h 蛹 1 s q 卯i 舅嘛r0 b 1 1 街9 ：1 0：脚砌归川暇“糟 1 毒醴姆钌：翱灌舡摒l l 2 3 警：糟：嗣穰蠢饿擘。由碡 1 锹矗罄】：匀皤秘黪i i 2 3 零：l 彝：撵角匿嘲壤1 9 鲜 q ：s k u r l vz ( x 撼- l l - z 3 9 ：3 8 ：1 0 ：献烈n 叮。嘲嘴1 9 啦蜩辩：舅叫竹2 b 1 1 9 ：i o：棚t 、岬酬、膊1 8 铂 q 印如m yz 0 0 8 - 1 1 鹚 ：棚科n 归呻暇柏 1 嘲 + 蝤)翱却2 1 1 - 鹚9 ：*：棚n 哪1 图2 3 墨恚中某一用户的行为记录 网络安全审计系统一个主要的功能是判断当前操作的用户身份是否合法或者是 否被留用，这就需要我们建立正常用户行为模式的规则，然后对当前行为进行比 对，以检测异常行为。根据当前审计系统日志的特点，我们希望挖掘出如下形式 的关联规则，a ，a aa ljb ，其中薹和嚣是一般属性或维度，( f = l ，k ) ， 例如t i m e ( 9 1 1 ) 钗 1 9 2 1 6 8 0 2 ) a e n e n t ( 修改文件) 等淞州”t o m ) ，此规则表示从i p 地址为1 9 2 1 6 8 。0 。2 的机器登陆并且在9 点到l l 点进行文件修改的操作翔户可认 定为t o m 。目前为止，文献【挎, 2 3 j 3 】中网络安全审计的关联规则的结果形式都是上 面的形式，但他们大多采用a 】试嘶算法【4 1 1 或者f p g r 0 、础算法的改进方法1 4 2 】 4 3 4 4 1 并结合o l a p 操馆来挖掘的，这都是在没有元规则制导的情况下采用的算法，所 以挖掘的效率比较低。 挖掘上面语法形式的多维关联规则的算法一般采用a r c s 系统中采用的基 于栅格概念的量化关联规则挖掘高效算法，但是目前的文献中没发现此算法在网 终安全审计中的应用，本文推荐将此算法应用到审计系统的关联规则挖掘上，并 对其进行了改进。 1 5 山东师范大学硕士学位论文 基于栅格概念的量化关联规则挖掘算法在低维关联规则的挖掘上存在优势， 但是涉及到高维规则就存在占用内存空间太大的不足，因为在此算法中对于涉及 到的多维量化属性的每种可能的箱组合，要创建一个多维数组。假如，在初始状 态，i p 地址分成2 5 5 个箱，时间分成2 4 个箱，日期按礼拜分成7 个箱，行为被 分成1 0 0 0 种，用户隶属组分成1 0 个箱，通信协议分成1 0 箱，就这六维就要生 成一个2 5 5 * 2 4 * 7 * 1 0 0 0 1 0 1 0 = 4 2 8 4 g 的内存六维数组，当然用户行为还可能包 括其他属性。 本文提出一种利用二叉排序树数据结构找到满足最小置信度的频繁谓词集 的算法，该算法也是只扫描一遍数据库，却占用比a r c s 采用的算法较小的内存 空间，时间复杂度却只是o ( n l o g n ) t 4 5 1 。 量化关联规则的频繁谓词集的改进挖掘算法思想： 按照a r c s 系统中使用的方法首先对行为记录的量化属性进行等宽分箱，比 如时间属性可分为2 4 个区间，并将其符号化，转化为事物数据库的形式，下一 步就是要找满足最小支持度计数的频繁谓词集，算法采用基于二叉排序树的数据 结构，结点由关键字、指向下一个结点的指针，对应支持度计数三部分组成，其 中关键字是由某个用户行为记录的分类属性符号化字符串连接而成。算法一边读 取用户行为记录一边形成二叉排序树，某个结点如果能够找到，支持度计数加一， 如果不能找到，就生成新的结点，并初始化支持度计数为零。这样经过扫描一遍 数据库就可以把二叉排序树生成，最后遍历一遍此树，找出满足最小支持度计数 的结点，最后把这些结点中的关键字还原成日志的行为记录符号化属性即可。这 样所占用的空间比原来a r c s 系统中多维数组要小的多，因为一旦所挖掘的行为 的属性比较多的话，就会引起多维数组空间的急剧增长；改进算法的时间复杂度 是o ( n * l o g n ) ，在a r c s 中扫描一遍数据库就可以直接存储计数了，因此时间复 杂度是o ( n ) ，其中n 为数据库记录个数。 算法用到的数据结构 找频繁谓词集的二叉排序树数据结构 t y p e d e fs t r u c tn o d e s t r i n gr e c o r d ；存储符号化之后的事务数据库中的记录，作为查找的关键字 l o n gs u p p o r t ；支持度计数，初始化为零 s t r u c tn o d e * l c h i l d ；左孩子指针，左子树的所有结点的r e c o r d 值均小于它 的父结点的r e c o r d 值 s t r u c tn o d e * r c h i l d ；右孩子指针，右子树的所有结点的r e c o r d 值均大于它 的父结点的r e c o r d 值 n o d e ； 1 6 玉东麴范大学硬圭攀缎论文 算法采用经典的二叉排序树的生成算法，如果想进一步提高效率亦可使用平 衡二叉树的生成算法，当找到一个结点的时候，支持度计数加一，否则，生成新 的结点，支持度计数初始为零，插入位置按照平衡二叉树的经典算法进行郄可。 找到满足最小支持度计数的频繁谓词集之后，就很容易生成强关联规则了， 但是在量化关联规则的挖掘中往往产生大量的关联规则，这些关联规则不但增加 的审计系统的负担，焉且不容易理解，怎样聚类关联趣刘l 噬一委过合并相邻的 规则而得到概括性的一般规则，减少挖掘出的关联规则的数量，是下面要解决的 问题。 关联规则聚类比较直接的算法是把将规则集转化到多维栅格上进行矩形聚 集，僵需要较大的内存空闻，还有基于网格几何性质的数量关联规则聚类算法削。 本系统中还是采用二叉排序树的数据结构，帮助实现关联规则聚类。 本系统中审计关联规则聚类算法基本思想如下：我们只对规则右部相同的规 则进行合并，合并的基本思想就是考虑规则左部的每一个维上的点是否相邻繇 可。设从用户行为库中挖掘到的关联规则左部集是一个k 维( 包含k 个属性) 量 化关联规则左部集，算法进行k 次规则合并，每次合并过程都相似，以第i 次( 其 中 l 妯i ，第i + 1 次在上次合并之蜃的k 维关联规则集上继续合并，蛊到第k 维结束。算法借助：叉排序树数据结构实现。 二叉排序树数据结构定义如下： t y p e d e f s t r u e tn o d e s t r u c tl i n k l i s ti 确r u l e ；绷字储b l 维中间关联规则集在第i 维上的投影 s t r i n gk1 r u l e s ；存储除了第i 维属性的其他k - 1 维属性形成中间关联规则字 符串 s t r u c tn o d e 事l e 躐d ；赃孩子指针， 的父结点的n l r u l e s 值 s t r u c tn o d e * r c h i l d ；右孩予指针， 的父结点的nl r u l e s 值 n o d e 单链表数据结构定义如下： t y p e d e f s t r u c tl n o d e 左子树的所有结点的nl r u l e s 值均小于它 右子树的所有结点的n _ l r u l e s 值均大于它 s t r i n gb c g i m 存储规则的第k 维区间豹开始点 s t r i n ge n d ：存储规则的第k 维区间的结束点 1 7 山东师范大学矮学位论文 s t r u c tl n o d e * n e x t ；指向下一个投影区间 l n o d e ，l i n k l i s t ： 下面对改进算法进行实例分桥，为简便起见，在日志中我们只取a u d i t 域 中的y a n g r e n h u a 这一个用户的部分记录的e v e n t 和t i m e 属性来分析。见下图2 - 4 。 1 e n c n tt i l n o user 2 登黎注销2 0 0 8 - 1 1 吨31 5 ：1 3 ，a u d i t 、u v a n g r e n h u a 一 s 瑟象谤阚 2 0 0 8 q l 2 3l ? ：2 0 。、a u d i t y a n g r e r a h u a 4辩敲访同2 0 0 8 - 1 1 - 2 31 7 ：3 7 艇雄 b g r e 加a 5 对霖访问i 0 0 8 一l j 二主31 7 ：3 7 a u d i t y a n g r e n h u a 6 对象访问2 0 0 8 - 1 1 - 2 31 7 ：3 8 a u d i t y a n g r e n h u a ， 7 登承注销 2 0 0 8 - 1 1 - 2 31 7 ：4 0 一 _ u d 工t y a n g r 尊岫m 4 一 8 登索注销 2 0 0 8 - 1 i - 2 49 ：3 0 。，a u d i t y a n g r e n h u a 9 策略敬动2 0 0 8 - 1 1 - 2 49 ：3 8 一 u d i t y a n g r e n h l l a 韭 鲮晦改动一2 0 0 8 c l 量；瑾j ：3 8 a u d i t j t v a n g r e n h u a l l 登掌继销弋1 0 0 8 j 诩主一1 1 ；2 0a u d i t y a n s r e n h u a 1 2 璧豢注销 2 0 0 8 q 1 屹41 5 ：4 0 。+a u d i t v a n g r e n h u a 一 1 3 对黎访问 2 0 0 8 - 1 i - 2 41 5 ：3 0 。 a u d i t y a n g r e n h u a 1 4 对象访闩 2 0 0 8 - 1 1 - 2 41 5 ：3 1 。+ ，a u d i t y a n g r e n h u a 1 5 对豫访问 2 0 0 8 - 1 1 - 2 41 5 ：3 2 ：j u d ic 口a n g r e n h u a 1 6 对絮访问 2 0 0 8 - 1 1 - 2 41 5 ：3 3 a u d ! t y a n g r e n h u a 1 7 帐户鬻理 2 0 0 8 - 1 1 - 2 41 5 ：5 7 a u d i t y a n g r e n h u m ， 1 8 帐户警堙一 2 0 0 8 l - 2 41 5 ：5 9 蠢l 母z t y g r 擞赫壤 圭9 整雾注锈 2 0 0 8 - 1 1 - 2 41 7 ：3 4 一 王了、y 繇g r 茹蟥h 遇一 2 0 登黎注镑2 0 0 8 - 1 1 - 2 51 5 ：0 8 i t y 锄g r 样小培 2 l萍- 承访问2 0 0 8 - 1 1 - 2 51 6 ：0 8 a u d i r l y e a _ 1 s r e n h u a 2 2辩黎访问 _ 一2 0 0 8 - 1 1 - 2 51 6 ：0 9l i f a n 矗e 幽堵 2 3 爻_氰访问 2 0 0 8 - 1 1 - 2 51 6 ：0 9 ，a u d i t y a n g r e n h u a 一 2 4舜 。_ 彖访问一 2 0 0 8 - 1 i - 2 51 6 ：1 0 + ，a u d i t y a n g r e n h u a 2 5辩，敲访闻2 0 0 8 - 1 1 2 51 6 ：1 4 。a u d i t y a n g r e n h u a 2 6 登零渡镶一 2 0 0 8 7 1 - 2 5l ! ：3 5艇西i t b 强g r e 蜘l 强 2 7 登零注销上一2 0 0 8 - 1 1 - 2 6 8 ：5 0 a u d i 零讶a n g r e n h u b 2 8 帐户篱理 二二2 0 0 8 1 1 - 2 69 ：1 7a u d i t 一v a n g 。r e n h u a 2 9 帐户管理 2 0 0 8 - 1 1 2 69 ：3 0 a u d i t y a n g r e n h u a 3 0帐户管理2 0 0 8 - 1 1 - 2 69 ：3 2 u d i t y a n g r e m l u a 3 1 登黎；：生镝 2 0 0 8 - 1 1 - 2 69 ：4 0 a u d i t v a n g r e n h u a ，一 3 2 一登泶注销一