节点文献
支持向量机及其在入侵检测中的应用研究
Study of Support Vector Machines and Its Application in Intrusion Detection Systems
【作者】 董春曦;
【导师】 杨绍全;
【作者基本信息】 西安电子科技大学 , 通信与信息系统, 2004, 博士
【摘要】 随着计算机和网络的日益普及,有关系统或网络的安全问题也日益突出。入侵检测系统是对传统计算机安全机制的一种补充,增大了对系统与网络安全的保护范围。入侵检测系统的研究始于上世纪80年代,虽有长足的发展,但还未成为网络或系统的主要安全保护措施。目前入侵检测研究的主要问题在于需要计算的数据量特别大,而这些数据对于检测率和虚警率的要求来说又是不充分和不完备的。 支持向量机是自上世纪90年代提出的一种基于统计学习理论的机器学习算法。与传统统计学研究样本产生的规律或样本数目趋于无穷大时的渐进性能不同,它更注重研究样本本身所提供的信息,所以特别适合于小样本问题。本论文的目的是研究将支持向量机应用于入侵检测系统的有关问题,结合入侵检测系统的特点和要求,对支持向量机算法做了一些研究工作。 论文主要涉及四方面研究内容:支持向量机改进算法、支持向量机推广能力估计、支持向量机参数选择和构造基于支持向量机的入侵检测系统。 1.在算法改进方面,给出了基于紧互对模型的支持向量预选方法和支持向量机的分步训练方法。由于支持向量机训练时要在所有样本上寻找对应二次规划问题的最优解,所以运算量和存储空间的要求都很大。但在得到的支持向量机中,只有支持向量影响分类性能,而通常支持向量只占样本的很少一部分,所以存在大量的浪费。通过分析发现,紧互对样本和支持向量距离分类超平面最近的性质有许多相似之处。通过将紧互对模型推广到特征空间,给出了一种基于紧互对模型的支持向量预选方法。这种方法能够有效预选样本集中的支持向量;使用紧互对集合训练的支持向量机性能与在全部训练集上得到的支持向量机性能相当,而运算时间和存储空间都有较大程度的减小。通过分析支持向量机求解二次规划中的KKT条件,根据样本的判决值,可以将训练集中的样本划分为不同的类别。应用于测试样本时,同样可以将测试样本划分为不同的类别。这些不同类别的样本不但对应了支持向量机分类超平面中的不同位置,还对应了特征空间中样本与分类超平面法向量间的角度关系。从而可以估计不同性质的样本加入到训练集后对支持向量机分类面的影响,进而得到支持向量机的分步训练方法。这种方法不但能够积累支持向量机的判决结果进行再学习,而且可以根据具体问题选择再学习的效果,使支持向最机的分类面向期望的方向变化。 2.在支持向量机推广能力估计中,给出了使用跨度估计推广能力时的线性规划求解方法。在求解跨度的二次规划中,目标函数定义了一个向量的椭圆范数。证明了它和约束条件一起,定义了一个凸规划。根据凸规划的收敛性质以及范数的等西女.匕子卞}技人学博卜论文:支持向量{儿及J〔丫i一入侵检测中的{、谈用朔·究价性,可以使用无穷范数来代替目标函数中的椭圆范数。同时证明,新的规划仍然是凸规划,而且两者寻优过程互为收敛,有数值上的依赖关系。对新的规荆做适当变换,就可以使用线性规划方法来求解跨度。这种方法与原方法在估计推广能力时的误差月卜常小,而计算时间有很大的降低。 3.在支持向量机的参数选择中,给出了支持向量机参数的最优化选择方法和试探法选择方法。通过分析核参数和惩罚因子对性能的不同影响,可以将支持向量机的参数分为敏感参数和不敏感参数,从而能够使用不同的参数更新规则来寻找最佳参数一。在更新核参数的准则方面,不再寻求随参数变化连续、可微的推广能力估计表达武,而是选择计算简单的支持向量率来衡量推广能力的变化,使用间接的方式指导参数更新。对不敏感的惩罚因子则采用宽松的边界支持向量数目和在所有支持向量中的比例作为更新准则,进而给出一种选择支持向量打L参数的最优化方法。由于在最常用核函数的标准表达形式中,只有一个核参数需要一调整,根据参数选择的不同更新准则,还可以使用试探法来选择支持向量机的参数,最后给出了试探法选择支持向量机参数的流程图。无论是使用最优化方法还是试探法,这些准则都能有效地选择一组较好的支持向量机参数。 4.在应用支持向量机实现入侵检测方面,分析了应用支持向量机实现入侵检测的方法,数据归一化、支持向量机参数对检钡小性能的影响,以及分步一训练法应用于入侵检测、简化支持向量机判决准则等问题。通过分析支持向量机中边界支持向量和非边界支持向量对分类性能的影响,证明了支持向量机中,去掉边界支持向量的训练集是可分的,分析了在此训练集上训练的支持向量机的分类超平而与在原4训练集_仁得到的支持向量机的分类超平面间的异同以及带来的误差,从而给出了支持向量机的分类准则简化方法。在入侵检测中,简化分类准则在保持检测性能儿一乎相!司的情况下,大大减小了检测时f司。最后给出了构建基于支持向量机的入侵检测模型,它是基于网络的入侵检测系统,既能检测异常行为,也能检测误用行为,而且包含了支持向量机的再学习功能。关键i司;支持向量机,算法改进,支持向量预选,分步训练法,判决准则简化,扣广能川古计,跨度,线性规划,参数选择,最优化方法,试探法,入侵检测,KDD99,
【Abstract】 Along with the wide application of computer and Internet, the security problem about systems or network becomes more and more important. Intrusion Detection Systems (IDS) are complementarities to security mechanism of network and computer systems, and enhance the protection depth of security. The research of IDS began in 80’s of last century, although there is quite great progress, there is no effective mean to protecting the network and computer systems yet. The key problem of IDS is that there are too many data need to be dealt with, and these data are not sufficient and self-contained to the requirement of detection and false alarm rates.Support Vector Machines (SVM) is a novel algorithm of machine learning issued in 90’s of last century, which is based on the statistic learning theory. It puts more attention to the information provided by the samples, and fits to solving the small sample problem.The aim of the dissertation is to research the applications of SVM to IDS. The dissertation contains four parts: the improvement of SVM algorithm, the estimation algorithm of the generalization performance of SVM, the method for selecting the parameters of SVM and the IDS based on the SVM.For the improvement of SVM, the tight mutual pair method for pre-extracting support vectors and step method for training SVM are proposed. Since the training procedure of SVM searches the optimal solution of a quadratic program on all the training samples, it requires huge computation and memory space. In fact, only few samples determine the performance of SVM, which are named support vectors. There are many similar characteristics between tight mutual pair in traditional pattern recognition and support vector. Generalized the tight mutual pair to the feature space by Mercer theorem, it can pre-extract support vectors efficiently, and the performance of the SVM trained on the tight mutual pair set is comparable with that trained on all the training samples, while the required computation and memory space of the former decrease sharply. By the KKT condition of solution procedure, samples in training set can be divided into three categories. For the testing samples, there are also three categories divided by the determination value, and the categories corresponds the position of samples to the classification hyper-plane and the angle to the normal vector of the hyper-plane. The effect of different category samples appended on the hyper-plane can be studied, it leads step method for training SVM. The method can not only make the SVM to relearn from the new samples, but also make classification hyper-plane change in an expect direction according with the certain problem.In the estimation of generalization performance, a linear program procedure forSpan method is presented. In the quadratic program solution procedure of Span, the objective function defines an elliptic norm of vectors. It is proved that the function and the constraint condition define a convex program. According with the convergence of convex program and equivalence of norm, it is also proved that the elliptic norm can be substituted by the infinite norm, the new program is still convex, and both optimal procedures are convergent mutually. After certain transformation, a linear program method can be obtained to solve the Span. The error between two methods is very little, and the computation decreases sharply.In the selection of the parameters, optimal and trials-and-errors methods are proposed. According with the affections of support vector to the classification performance, they can be categorized into sensitive and insensitive parameters. So the parameters are updated with different rules. For kernel parameters, the ratio of the number of support vectors to that of training samples is used to measure the variation of generalization performance, and updates the parameters indirectly. For penalty factor, the ratio of the number of bound support vectors to that of support vectors is not the critical rule. So an optimal method for selecting the parameters can be obtained. Exce
【Key words】 Support Vector Machines (SVM); Intrusion Detection Systems (IDS); algorithm improvement; pre-extract support vectors; step training method; classification rule simplification; generalization performance estimation; Span; linearly program; parameters selection; optimal method; method of trails and errors; KDD99; system model.;