适用于实时网络使用分析的快速模糊关联规则产生方法

1、适用于实时网络使用分析的快速模糊关联规则产生方法摘要对于网络安全的运用中，许多的网络入侵检测工具都必须藉由分析网络流量来完成，对于动态新增数据库(网络流量)信息而言，所设计的算法必须快速且准确的分析网络信息。本文提出了一个快速的模糊关联规则算法，适用于分析实时动态的网络流量，能针对大量的网络流量做实时、动态且准确的分析。 摘要为了达到实时分析，系统设定 3秒钟统计一笔网络流量的信息，针对 6种特征，且各特征分低、中、高， 3种程度做挖掘，经过测试，系统处理一笔新进数据平均只需要 秒，可以有效的支持在线实时探勘的需求。系统也可以针对于不同的环境如地点、时间点以及不同的网络行为做特征选取上的更动。

2、 背景知识关联规则算法-Apriori模糊关联规则渐进式模糊关联规则探勘-Real-Time关联规则算法-Apriori在关联规则算法中，目前以Apriori算法为基础所推导出的各种数据探勘技术为最具代表性的方法之一，其设计为针对静态的数据做探勘的动作，而从中撷取出对使用者有兴趣的相关法则。Apriori算法中主要包含以下两个主要的步骤：1、重复的产生候选项目组(candidate itemset)并且搜寻整个数据库，直到找出所有大型项目组(large itemset)。2、利用上述所找出的大型项目组进行拆解，并且推倒出所有的关联法则。关联规则算法-Apriori在步骤 1之中，候选项目组(c

3、andidate itemset)必须大于使用者所设定的最小支持门坎值(minimal support)才能成为大项目组(large itemset) 。同样在步骤 2之中，所产生的关联法则也必须大于使用者所设定的最小可靠门坎值(minimal confidence)才能成为一条有效的法则。Apriori算法推导过程TIDItems1234ACDBCEABCEBEItemsetSupABCDE23313C1ItemsetABCDE23313Scan DSupItemsetABCE2333L1ItemsetSupABACAEBCBECE121232Scan DC2ItemsetSupACBCBE

4、CE2232L2ItemsetItemsetItemsetSupSupSupC3C3L3BCEBCEBCE222Scan DDataBaseSupApriori 所面临问题由于Apriori算法牵涉到多次数据库的扫描，或者产生大量的项目组，因此，当数据库产生变动时，必须从头的扫描来产生项目组以产生新的关联法则，当数据库庞大时，搜索的动作便成了耗时的工作，因此，对于使用在动态的网络流量的探勘中，很显然的Apriori算法并不适用。模糊关联规则Apriroi 算法之support(X)是以项目集X中的项目同时出现在资库D中记的笔计算，而用在网络入侵检测上，每个项目在每笔记中会出现，因此每个项目会有

5、一个化的值。如下图：资料网络封包特征纪录 1特征1=50 特征2=35 特征3=34 特征4=45 特征5=96纪录 2特征1=64 特征2=68 特征3=65 特征4=12 特征5=87纪录 3特征1=86 特征2=32 特征3=64 特征4=43 特征5=34纪录 4特征1=24 特征2=12 特征3=27 特征4=44 特征5=56纪录 5特征1=75 特征2=89 特征3=70 特征4=37 特征5=67模糊关联规则很显然，对于化的资库，传统的Apriori算法并适用。资探勘域中对于这种项目化的问题也有干方法被提出，而对化资库探勘最直接简单的方法，就是对于每个项目的值给予明确的割以判定

6、等级，我们用重要性(significance)及稳定度(certainty)分别取代传统Apriori算法中的支持度(support)以及信赖度(confidence)我们融入了模糊理论的观念，套用模糊理论的术语，每个项目名称改称为模糊变量(fuzzy Variable)，每个项目名称的分改称为模糊集合(fuzzy Sets)，如low，medium，high，个别用一个续函式，称为成员函式(membership function)，描述之 。模糊关联规则将切割的等级分成不同程度(低、中、高)带入模糊函式，取自于MATLAB Fuzzy Tool Box的预设函如下，其中a, b, c为可调整

7、之常，右图为不同程度所代表的模糊函数分类。Low ：f ( x ) = 1 / ( 1 + exp( a ( x - c) ) )Medium：f ( x ) = 1 / ( 1 + | ( x - c) / a | 2b )High ：f ( x ) = 1 / ( 1 + exp( -a ( x - c) ) )渐进式关联规则网络数据(流量)的更新是随时进行的，因此，数据库中的数据也必须随着交易的新增而动态的纪录新的数据。但由于一般所谓的动态数据并不适用于用在网络使用分析上，因为适用于网络中的动态数据，其对于实时更为关键，所设计的算法必须快速的处理一笔新增的数据，且在下一笔新增数据进入之前

8、完成探勘，并产生关联法则。渐进式关联规则设计想法考虑到不需要针对数据库做重复的扫描，融合了渐进式关联规则(incremental)的观念，其算法设计的方式，只需要针对上一笔数据的结果加入新进数据做结合来处理。不同于传统关联规则必须针对数据库重复的扫描，渐进式关联规则能针对新的数据处理，大大的改进重复搜索数据库所浪费的时间与资源，因此，动态的关联规则便能有效率的提高实时探勘的速度。实际应用例子我们预计使用四台计算机(如下页)，每台计算机各自分担不同工作，其主要目的为减少每台计算机的负担，以达到最有效率的Mining，来完成在线实时侦测。计算机A:撷取封包并且统计特征。计算机B:将计算机A传送的数

9、据带入算法进行 Mining，产生Rules。计算机C:从数据库去读取每一笔Training出来的records。计算机D:将计算机B及计算机C所收到的Rules进行比对并计算相似度。 应用例子(图解)撷取封包并且统计特征计算机A计算机B进行实时在线Mining计算机C自数据库(MySQL)读取正常的record计算机D进行模糊关联规则相似度的比对于动态数据中快速的模糊关联规则产生算法传统关联规则探勘的技术中，假若数据库有异动的数据时，就必须重复扫描数据库计算关联规则的过程，如此大量且耗时的方法，对于目前实时动态在线探勘并不适用，因为对于所挖掘的特征无法达到实时的分析，因此如何设计出一套快速运

10、用于网络(段)中的探勘算法便成为我们所研究的重点。 设计动机为了改进用于在线侦测实时关联规则程序的效率与正确性，我们加入了动态的观念。为了解决关联规则最大的问题，是其必须不断的重新扫描数据库来产生Rule，然而这项过程与工作往往是关联规则最大的问题，其所需要的时间以及执行步骤将无法实时且有效率的在特定的时间内完成。因此为了能有效的运用在网络上，我们必须找出一套方式来更快速的处理大量的封包数据。设计想法由于目前计算机的处理效能以及内存空间相当大，所以我们将牺牲空间来换取时间，也就是利用大量的内存空间位置来记录庞大的项目组。程序将纪录到长度为 8的item-set，也将会花费上万笔数据的内存空间，

11、所以如何有效的处理内存空间便成为首先面对的问题，我们考虑用动态配置的方式，在系统一开始便将所以内存的位置依序的产生。设计想法为了更有效率的处理在线实时更新的动态数据，首先面临必须能快速的处理一笔新进数据，我们采用动态配置内存的技术来产生各种不同程度(low、medium、high)的项目组，分别用链结串行的方式将其分别储放在内存空间。右图为系统开始时所建立的内存空间，并且照顺序排列。 AD 0010ADG00.10.20A 00B 01C 02AE00,11R 52AF00,12OR42,52ADH00.10.21AFI00.10.22LOR32.42.52ADG 0010AEH00,11AF

12、I00,12LOR42,52项目组Itemset 1项目组Itemset 2项目组Itemset 3项目组Itemset n结构建立方式为了将来所产生的关联法则，系统必须要知道每个结构里面所代表的意义(low、med、high)，所以我们采用 2维数组的方式来建立内存空间，给予标记。Low Med High Low Med Highf 1 1 A B C f 2 1 D E F f 3 = G H I f 4 J K L f 5 M N O f 6 P Q R 节点产生透过 1的个数来跑，不断的呼叫函式来产生，例如项目组1的时候，结构建立的方式就是f1-lowf1-medf1-highf2-l

13、ow.项目组 2的时候产生两个1，一个1固定在f1-low，另外一个放在f2-low然后去呼叫函式，结构建立的方式变为f1-low,f2-lowf1-low,f2-med下图为系统在处理产生长度为 2的项目组时所产生的节点。1111111111“1”在这 1 5个格子内依序移动“1”在这 15 个格子内依序移动“1”在这 15 个格子内依序移动“1”在这 12 个格子内依序移动“1”在这 3 个格子内依序移动长度为2的项目组(2-itemset)For example:产生所有长度为2的candidate itemset，共有18C2个节点节点标记目前为止，我们建立了所有项目组所产生可能性，为

14、了加入模糊化(Fuzzy)的观念，在结构中加入了一个用来存放模糊之后的值(number)。此外，为了考虑到数组无法快速的做分析及拆解以及必须明白各节点所代表的意义(为了将来产生关联法则)，因此我们必须将各个节点做标记。我们透过上面介绍的英文字母以及所对应的英文字母做配对，来产生不同程度的配对。BCDOADDDGP“A”依序从D开始以下的15个格子做配对：ADAR“B”依序从D开始以下的15个格子做配对：BDBR“C”依序从D开始以下的15个格子做配对：CDCR“D”依序从D开始以下的12个格子做配对：DGDR“O”依序从P开始以下的3个格子做配对：OPOR长度为2的项目组(2-itemset)

15、For example:将会产生ADAR、BDBR、CDCR、DCDR、OPOR这些长度为2的candidate itemset 。关联规则的问题为了用于在线动态的侦测，其讲究的不外乎是执行的效率，也就是再下一笔拆解分析的资料进来之前，是否能将之前的数据结束，否则将再同一时间延后分析的效率，影响其结果。但是关联规则最大的问题就是必需重复的扫描数据库来建立项目组，这是一项费时的工作，因为前项-项目组有可能会影响之后所结合的项目组。(4-itemset是由3-itemset与2-itemset来建立)解决方法此外，为了不需要再去重复的搜索数据库浪费庞大的计算时间，将采用上列建立数据结构的方法来解决

16、。我们加入了incremental(动态数据处理)的方式，利用动态改变数据库的内容，再每一笔新数据进入之前，我们保存之前的数据结果在一起计算。便可以不需要从头搜索数据库一遍，只需针对上几笔数据的结果来运算。结构中的值改变1-itemset对应的英文Support值000102101112202122ABCDEFGHI0.320.530.240.450.560.620.230.350.27经过第2笔数据带入，其结构中的以及变化。交易笔数：1 项目组 1-itemset1-itemset英文Support值(旧)Support值(新)结果旧+新/count000102101112202122ABC

17、DEFGHI0.320.410.240.450.560.620.230.350.270.340.650.600.250.380.240.650.230.330.330.550.420.350.470.430.440.290.30交易笔数：2结果：Support(旧)+Support值(新)/交易笔数结构中2-itemset的值2-itemset英文Support00,1000,1100,1200,2000,2142,5042,5142,52ADAEAFAGAHOPOQOR0.320.410.240.450.560.270.820.35此时，结构中将会把所有可能产生的项目组的组合都建立出来，需要

18、注意的是，相同一层的程度是不可能同时出现的，也就是A(f1-low)不可能跟相同一层的B(f1-med)跟C(f1-high)做组合成AB跟AC。改进方式需要强调的是，带入模糊运算以及结构中值的改变是每次都必须的，也就是不管成不成立与否，都必须改变结构中的值，才能保证下笔数据进入前的数据是正确的。上页的例子，只针对1-itemset来做解释，在同时n-itemset(n从16)都必须做改变，如此并解决重复搜索数据库的问题了，因此只需要针对前一笔的数据来做处理。Rule产生每个项目组都会产生满足的项目如：BE、 ADG、CFHK等等。接下来Rule的产生就必须针对满足支持度的项目去做拆解。BEB

19、EEBADGADGDAGGADDGAAGDADGCFHK CFHK FHKCFCHK CHKFHCFK CFKHKCFH CFHKCFHK HKCFCHFK FKCHCKFH FHCK此外，拆解完成所有可能的集合同时，必须去计算confidence值，满足大于等于才能判断是一条可以参考的Rule。Confidence值补充confidence值的计算： ADG：confidence=ADG(support)/A(support) DGA ：confidence=ADG(support)/DG(support) 我们发现计算confidence只用到箭头右边的英文字，所以我们必须要纪录并且回到数

20、据库去搜寻位于箭头左边英文字所对应的结构中support值。而这个support值必须回到所宣告的数组结构之中搜索，也就是当初所设计的将数组转换成字符串，因为字符串的拆解比较方便、容易解读。confidence必须大于等于所设定的范围才能称为一条可信赖的Rule。可行性分析目前CPU的计算及硬件I/O的考虑，数据存放的空间已经不再是一个严重的问题，因此我们采用易失存储器配置的技术来将所有项目组的可能产生，我们采用 8个特征， 3种程度，而所花费的内存空间如下页图，对于应用在网络流量的探勘中，太高的项目组所代表意义可能被大量且不同类型的封包给掩盖掉，因此，本系统只产生到项目组 8，而大约花费 M

21、B的内存空间，可针对不同的环境做项目组的改变。内存空间项目组长度节点个数所花空间(bytes)Itemset-124406Itemset-22524284Itemset-3151225704Itemset-45670144585Itemset-513608231336Itemset-620412347004Itemset-717496297432Itemset-86561111537实时网络使用分析算法特性 本文所设计的实时动态关联规则算法中主要包含以下主要的步骤：Step 1.系统进行初始化并设定最小支持度(minimum support)。Step 2.动态配置内存，建立所需的Link-l

22、ist，根据项目组长度建立数据所存放空间。Step 3.每单位时间读入新增封包纪录，并与每个节点计算此笔纪录之fuzzy值(high、medium、low)，更新内存中的数据。实时网络使用分析算法特性Step 4.计算其支持度是否符合，若大于所设定的最小支持度，则找出此点之Rule，进行分析，小于则淘汰，纪录该节点数据。Step 5.计算Rule之信赖度，将大于最小信赖度之Rule印出。Step 6.自算法系统中取出实时在线探勘的关联法则与数据库中正常封包的关联法则进行交叉比对，判断是否遭受攻击。效能评估在失一般情况下，我们使用随机产生每笔交资的项目，做为评估前面章节算法之执效能的资源。实验平台为P4-3.0 G、RAM为512M、操作系统为Windows XP Sever，使用C+撰写程序。 假设项目共有6项，且各分为低、中、高三种不同的等级，每笔交资所包含的项目以产生(每次新增交资就须重新计算)，来评估执效能。我们初始以1000笔交资为探勘的资源，在设定最小支持为及最小信赖为的条件下，然后以每次新增1000笔交资，且每次皆重新执行，评估我们算法的执时间。 效能评估在每次新增交资时，本算法于