基于TCM-KNN和遗传算法的网络异常检测技术.doc

第12期李洋等：基于TCM-KNN和遗传算法的网络异常检测技术53基于TCM-KNN和遗传算法的网络异常检测技术李洋1,2，方滨兴1，郭莉1，田志宏1，张永铮1，姜伟1（1.中国科学院 计算技术研究所，北京 100080；2.中国科学院 研究生院，北京 100039）摘 要：提出了一种基于TCM-KNN的网络异常检测新方法，并采用遗传算法选择使用少量高质量的训练样本进行建模，从而有效地对入侵进行检测。大量基于著名的KDD Cup 1999数据集的实验表明：其相对于传统的异常检测方法在保证较高检测率的前提下，有效地降低了误报率；并且，在采用选择后的训练集优化处理后，其性能没有明显的削减，因而相对于传统方法更为适用于现实的网络应用环境。关键词：网络安全；异常检测；TCM-KNN算法；遗传算法；样本选择中图分类号：TP309 文献标识码：A 文章编号：1000-436X(2007)12-0048-05Network anomaly detection based on TCM-KNN and genetic algorithmLI Yang1,2, FANG Bin-xing1, GUO Li1, TIAN Zhi-hong1, ZHANG Yong-zheng1, JIANG Wei1(1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China;2. Graduate School of Chinese Academy of Sciences, Beijing 100039, China)Abstract: A network anomaly detection scheme based on TCM-KNN algorithm was proposed. Moreover, genetic algorithm (GA) based instance selection was introduced to boost the detection performance, meanwhile reduce the computational cost for TCM-KNN. A series of experimental results demonstrate the proposed method is effective, the instance selection mechanism also improves TCM-KNN and makes it be a good candidate for anomaly detection in practice.Key words: network security; anomaly detection; TCM-KNN algorithm; generic algorithm; instance selection1 引言收稿日期：2007-09-22；修回日期：2007-12-03基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB311100）Foundation Item: The National Basic Research Program of China (973 Program) (2007CB311100)入侵检测系统是网络安全防御体系的一个重要组成部分，它通过对网络和主机上某些关键信息进行收集分析，检测其中是否有违反安全策略的事件或攻击事件发生，并对检测到的事件发出警报。目前常用的入侵检测技术主要有两种：误用检测和异常检测1。误用检测是建立在使用某种模式或者特征描述方法对任何已知攻击进行表达这一理论基础上的。误用检测系统是将已知的攻击特征和系统弱点进行编码，存入知识库中，入侵检测系统（IDS）将所监视的事件与知识库中的攻击模式进行匹配，当发现有匹配时，认为有入侵发生，从而触发相应机制。这种技术的优点是可以有针对性地建立高效的入侵检测系统，误报率低；缺点是对未知的入侵活动或已知入侵活动的变异无能为力，攻击特征提取困难，需要不断更新知识库。异常检测基于已掌握了被保护对象的正常工作模式，并假定正常工作模式相对稳定，有入侵发生时，用户或系统的行为模式会发生一定程度的改变。一般方法是建立一个对应“正常活动”的系统或用户的正常轮廓，检测入侵活动时，异常检测程序产生当前的活动轮廓并同正常轮廓比较，当活动轮廓与正常轮廓发生显著偏离时即认为是入侵，从而触发相应机制。异常检测与系统相对无关，通用性较强。它最大的优点是有可能检测出以前从未出现过的攻击方法，不像误用检测那样受已知脆弱性的限制，然而其误报率过高。网络异常检测技术在20世纪90年代末至2002年备受网络安全领域专家和研究者的关注。哥伦比亚大学的Eskin2等提出的基于聚类的估计算法、改进的K近邻方法以及one-class SVM方法是其中最为著名和具有影响力的3种方法。然而，异常检测技术在2002至今，没有太大的发展，主要原因在于当前的方法都具有较高的误报率，并且由于计算量过大而导致其实用性不强。针对这些情况，本文提出了一种新型的基于TCM-KNN算法的异常检测方法，其相对于传统的方法具有较高的检测率和较低的误报率；并且，通过引入遗传算法，对算法的训练集进行样本选择，从而减少算法的运算量，来提升其在真实网络环境中的实用性。2 基于TCM-KNN算法的异常检测2.1 TCM-KNN原理直推信度机(TCM, transductive confidence machines)3则使用Kolmogorov的算法随机性理论建立了一种适应范围较广的机器学习置信度（confidence）机制。它被用来衡量一个样本分别属于已经存在的几个类别的可信程度。TCM中所采用的置信度机制基于随机性检测。然而，Martin-Lof证明4，这种检测是不可计算的，因此，必须采用一种可计算且满足Kolmogorov的算法随机性理论的随机性检测函数来对该置信度进行估算。这种检测函数的值称为P值。TCM-KNN（transductive confidence machines for K-nearest neighbor）将经典的分类算法K近邻结合在TCM中，采用距离计算的方法根据已分类的数据集对观测点进行分类。因此，在TCM-KNN中，为了计算待检测样本的值，定义一种称为奇异值（strangeness）的指标：定义1 待检测样本i相对于类别y的奇异值定义为 (1)其中，表示样本i与类别y中所有样本的距离的序列，则表示该序列中第个最短的距离；同理，则代表样本与其他类别中（除类别y外）所有样本的距离序列，同样表示该序列中第j个最短的距离。参数则表示所要考虑的最近邻的数目。结合定义1，可以给出TCM-KNN中，P值的计算方法如下所示。定义2 待检测样本相对于类别y的P值计算为 (2)其中，表示集合的“势”，通常计算为有限集合的元素个数；为待检测样本的奇异值；n为集合的个数；a j表示集合中任意样本的奇异值。因此，P值可以计算为（j为类别y中奇异值大于待检测样本i奇异值的样本个数）。并且，在计算过程中，通常一次处理一个样本。不难看出，P值取值区间为0,1，并且其值越大，表明样本i归属于类别y的可能性越大。2.2 基于改进TCM-KNN的异常检测算法上节所述的经典的TCM-KNN算法在本质上来说是一种分类方法，它假设一个样本属于多个类别中的某一个。而对于网络异常检测应用来说，它只是一个二类问题，即只需要确定样本是属于正常类别还是异常类别，那么，就有必要对其进行改进5。因而，下面对定义1进行了重新定义，并给出了基于改进TCM-KNN得异常检测方法（见算法1）。定义3 待检测样本i相对于正常类别y的奇异值定义a iy为 (3)其中各个符号的含义与式（1）中的完全相同，此处不再赘述。使用改进的TCM-KNN算法进行异常检测的流程可以简单描述为：给定正常训练集和一批待检测样本，通过其奇异值的计算以及事先计算好的正常训练集中所有样本的奇异值，可以得到待检测样本相对于正常训练集的值，如果该值小于预定义的阈值（通常为0.05），则可以以置信度为1（通常情况下为95%）来判定其为异常；否则认为其正常。算法1 改进的用于异常检测的TCM-KNN算法算法参数说明: k（最短距离参数）、m（训练集样本数目），设定的置信度阈值输入: （待检测样本）输出: normal或者abnormal/*算法开始*/for = 1 to 根据定义1为训练集中的每个样本计算并存储;根据式(3)计算训练集中每个样本的奇异值并存储;根据式(3)计算待检测样本的奇异值;根据式(2)计算待检测样本的值;if (P)以置信度(1)判定样本为异常，return abnormal;else以置信度(1)判定样本为正常， return normal;/*算法结束*/不难看出，影响本算法的时间开销的主要因素集中在数据集的规模上，在实践中可以加以控制来降低时间开销。本文第4节将会对此以实验说明对本方法采用选择后的样本进行训练和检测的可行性。3 基于遗传算法（GA）的训练样本选择3.1 遗传算法(GA)简述遗传算法（genetic algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法6。在自然界的演化过程中，生物体通过遗传（传种接代，后代与父辈非常相像）、变异（后代与父辈又不完全相像）来适应外界环境，一代又一代地优胜劣汰，发展进化。GA则模拟了上述进化现象。它把搜索空间（欲求解问题的解空间）映射为遗传空间，即把每一个可能的解编码为一个向量（二进制或十进制数字串），称为一个染色体（chromosome）或个体，向量的每一个元素称为基因（genes）。所有染色体组成群体（population）或集团。并按预定的目标函数（或某种评价指标，如商业经营中的利润、工程项目中的最小费用、最短路径等）对每个染色提进行评价，根据其结果给出一个适应度的值。算法开始时先随机地产生一些染色体（欲求解问题的侯选解），计算其适应度，根据适应度对诸染色体进行选择、交换、变异等遗传操作，剔除适应度低（性能不佳）的染色体，留下适应度高（性能优良）的染色体，从而得到新的群体。由于新群体的成员是上一代群体的优秀者，继承了上一代的优良性态，因而在总体上明显优于上一代。GA就这样反复迭代，向着更优解的方向进化，直至满足某种预定的优化指标。在使用遗传算法的过程中，如下几个方面需要根据实际情况进行选择和确定7：1) 编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。2) 适应性值评估检测：适应度函数表明个体或解的优劣性。不同的问题，适应度函数的定义方式也不同。另外，遗传算法具有如下3个算子，实际的应用需要对他们进行确定：1) 选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。2) 交叉：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。3) 变异：变异首先在群体中随机选择个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.0010.01。变异为新个体的产生提供了机会。3.2 基于遗传算法的样本选择根据3.1节所述的遗传算法的基本概念，将其应用于针对TCM-KNN算法的样本选择任务中，首先从编码表示以及适应度函数的选择两方面进行了如下的定义：1) 编码方式：对于TCM-KNN算法的训练集（只包含正常数据），将其表示为TR。不难看出，所有与样本选择相关的搜索空间都为TR的子集。那么，将使用染色体来表示这些子集，并且采用二进制的编码方式，也就是说，每条染色体由表示子集中训练样本的每个基因组成。如果训练集中的样本被选中，则表示该样本的基因则置为“1”，否则置为“0”。在进行基于此编码方式的遗传算法选择后，剩下的染色体所表示的训练样本则为进行样本选择后得到的精简训练集。2) 适应度函数：对于本文所述的针对TCM-KNN算法的样本选择任务来说，需要考虑3个重要的衡量指标：检测率、误报率以及样本的减少规模。检测率表示TCM-KNN算法对网络流量的检测正确程度；误报率表示该算法将正常流量检测为恶意流量的比率；而样本的减少规模则代表通过样本选择后得到的训练样本的数量相对于未经选择前的减少比率。从现实效果来说，这3个指标是相互矛盾的（也就是说，需要在保证较高的检测率和较低的误报率的前提下，尽可能地提高样本的减少比率），因而适应度函数就是力求取得他们的折衷，达到一个相对较好的结果。因此，定义如下适应度函数：(4)其中，detect_rate表示检测率，fal_rate表示误报率，reduce_rate表示样本的减少比率，C为一个可调的参数，通常通过实验来对其进行调整以取得较好的实践效果，在本文所述的实验中，调整其最佳值为0.6。另外，对于该遗传算法的3个基本算子的，选择使用了文献8中提供的3种较为著名的搜索策略的基本算子进行实验。他们分别是GGA （generational genetic algorithm）、SGA （steady-state genetic algorithm）、CHC（heterogenious recombination and cataclysmic mutation）以及PBIL （population-based incremental learning）方法。为了考察这几类方法的基本算子对于TCM-KNN算法的样本选择效果的影响，在第4节通过具体的实验对其进行了详细地说明。4 实验结果在本节，将对本文提出的入侵检测方法的有效性进行验证。为了保证实验的说服力和方便性起见，采用研究领域共同认可及广泛使用的基准评测数据集KDD Cup 1999数据集进行测试。该数据集5包括大约4 900 000条数据记录，每条都是从军方网络环境中模拟攻击所得的原始网络数据中根据设定的41个特征提取出来的，它们都是描述网络连接统计信息的特征向量。它们包含5类数据：DoS，Probe，R2L，U2R 4类攻击数据（共包含24种攻击类型）以及正常数据。本文所述实验的实验平台的环境为：Pentium 4 3GHz CPU，512MB DDR内存，80GB+7200转硬盘；操作系统为WindowsXP+SP2。TCM-KNN方法相对于其他几种方法的有效性在文献5中已经有了定性和定量的分析，因而本文主要关注于采用基于GA算法的样本选择方法后，其对检测效果以及性能的影响程度。表1给出了采用4种经典搜索策略的GA算法基于TCM-KNN算法的样本选择的具体参数设置。表2给出了本实验的数据集的详细情况：采用5个独立的训练集对4种算法进行了分别实验，使用一个独立的测试集进行效果测试，并且使用这几个测试的平均效果对4种算法的效果进行了评价和分析，结果如表3所示。发现使用CHC搜索策略的实验效果较为理想：检测率高达99.38%，误报率相对较低（1.87%），而样本减少率也达到了95.78%，减少比率仅次于PBIL策略，因此，在实践中推荐使用该搜索方法。表1GA算法搜索策略参数设置搜索策略参数设置GGAPm=0.001, Pc=0.6, pop=100, Eval=10 000SGAPm=0.001, Pc=0.1, pop=100, Eval=1 000CHCPop=100, Eval=10 000PBILPm=0.02, Pc=0.1, pop=100, Eval=10 000, LR=0.1, Mult_shift=0.05, Negative_LR=0.075表2实验数据集构成数据集样本数目样本构成1 （训练集）9 864正常数据2 （训练集）10 038正常数据3 （训练集）9 273正常数据4 （训练集）8 647正常数据5 （训练集）8 993正常数据6 （测试集）5 829正常数据（1 061）+异常数据（4 768）表3采用各种搜索策略的实验结果算法检测率/%误报率/%样本减少率/%TCM-KNN+GGA89.357.4695.54TCM-KNN+SGA87.4811.2888.33TCM-KNN+CHC99.381.8795.78TCM-KNN+PBIL98.735.4796.33特别值得强调的是，由于本文使用GA算法对TCM-KNN算法建模所使用的数据集进行了较大幅度地选择和精简，并且保证了较好的检测效果，因而对于该算法的性能提升度也是相当大的，从而将其优化为一种实用的网络异常检测方法。表4给出了采用样本选择后的TCM-KNN算法性能的实验结果。结果也表明：使用样本选择对TC-KNN进行性能优化后，其建模时间和检测时间都有了很大程度地下降（建模时间降低了98.65%，检测时间下降了66.45%），而检测率和误报率都能维持在相当低的水平，这也大大地证明了本文所述方法对于TCM-KNN算法优化和合理性和可行性。表4 采用样本选择后的TCM-KNN算法性能实验结果算法建模时间/s检测时间/s检测率/%误报率/%TCM-KNN (原始的)4 173.431 024.2999.481.76TCM-KNN (最优化的)56.21343.6699.371.835 结束语本文提出的TCM-KNN算法是一种非常有前途的数据挖掘方法，特别适应于分类学习领域。本文将其应用于异常检测领域，并引入遗传算法对其训练数据进行选择和规模限制，不但保证了较好的检测性能，并且极大地降低了较大的训练集规模给算法带来的过大计算开销，极大地提升了其在现实网络环境中的可用性。本文所提出的方法在实践中还需根据实际应用情况作进一步的改进，以提高其性能：主要包括如如何将本文所述方法应用于实际的网络环境中并加以优化，以及将其应用于大流量网络环境下检测DoS攻击以及检测Web服务器的异常情况将是我们下一步的工作重点。参考文献：1BYKOVA M, OSTERMANN S, TJADEN B. Detecting network intrusions via a statistical analysis of network packet characteristicsA. Proc of the 33rd Southeastern Symposium on System TheoryC. 2001. 309-314.2ESKIN E, ARNOLD A, PRERAU M, et al. A geometric framework for unsupervised anomaly detection: detecting intrusions in unlabeled dataA. Applications of Data Mining in Computer SecurityC. 2002. 78-99.3PROEDRU K, NOURETDINOV I, VOVK V, et al. Transductive confidence machine for pattern recognitionA. Proc of the 13th European Conference on Machine LearningC. 2002. 381-390.4BARBARA D, DOMENICONI C, ROGERS J P. Detecting outliers using transduction and statistical testingA. Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Dta MiningC. 2006. 55-64.5LI Y, FANG B X, GUO L, et al. Network anomaly detection based on TCM-KNN algorithmA. Proceedings of ACM Symposium on InformAtion, Computer and Communic