本科毕业论文---基于支持向量机的入侵检测系统与实现(论文)设计.doc

毕 业 论 文（设 计）

题 目基于支持向量机的入侵检测系统与实现
姓 名 端乐凯 学号 1109064004
所在院(系) 数学与计算机科学学院
专业班级 信息与计算科学1101班
指导教师 赵晖
完成地点 陕西理工学院

2015年 6 月6日

陕西理工学院毕业论文
基于支持向量机的入侵检测系统与实现
作者：端乐凯
（陕理工学院数学与计算机科学学院信息与计算科学专业1101班，陕西 汉中 723000）
指导教师：赵晖

[摘要]入侵检测技术是当今一种非常重要也非常有效的动态网络安全技术，它可与静态安全技术如防火墙等协同使用，可以使系统的安全防护能力得到极大的改善。本设计系统的介绍了入侵检测的基本概念、发展历史、与其他安全技术如防火墙等的紧密联系、基本工作原理、工作模式、分类以及发展趋势。当前入侵检测系统使用常规算法检测，不仅其检测效率低下，而且远远未能满足不了大规模和高带宽网络的安全防护要求，漏报率和误警率较高，很难检测分布式协同攻击等复杂的攻击手段；另外，预警水平过分依赖于攻击特征库导致其缺乏对未知入侵的预警能力。
统计学习理论最近兴起的最实用的部分是支持向量机(SVM)，同时控制经验风险和分类器的容量（用分类器的VC维衡量）两个参数是其核心思想，使分类器间隔达到最大，从而使真实风险最小。另外，在小样本学习的基础上发展起来的支持向量机分类器设计方法，专门针对小样本数据，并且对数据维数不敏感，分类精度和泛化能力极佳。本设计重点介绍了支持向量机的基本原理，同时也介绍了它的长处和不足。
首先，本设计考虑到大量冗余、噪声以及部分连续是入侵检测数据的特征，又为了提升网络检测的成效，因此，运用邻域粗糙集模型应用于对入侵数据的属性约简。该方法不需要将原数据离散化，这样就保证了入侵检测的准确性和原始数据的信息完整性。
其次在分类中我们又使用了和声搜索算法进行优化。经过反复调整记忆库中的解变量，使得函数值随着迭代次数的累加而趋近收敛，从而对支持向量机的参数完成优化。该算法避免了人们在SVM中参数选择的主观性而带来的精度的风险，增强了入侵检测的性能。并用相同的数据进行实验，得到了良好的效果，即本文算法的入侵检测率最优值达到95.42%，误警率到达0.81% ，仿真实验表明。这些算法提高入侵检测率并同时降低误警率，具有较强的泛化性能和鲁棒性，有者较好的实用价值。

[关键词]入侵检测；邻域粗糙集；和声搜索；支持向量机；

Intrusion detection system based on support vector machine and realization
Author: Duan Lekai
(Shaanxi Institute of Mathematics and Computer Science, Information and Computing Science 1101 class, Hanzhong, Shaanxi 723000)
Instructor: Zhao Hui
Abstract：With the rapid development of computer network technology, its applications continue to expand,Production of human life are increasingly dependent on computer networks,"Prism" incident is the increased emphasis on network security issues.Intrusion detection technology is today a very important and very effective dynamic security technology,It can be used with static security technologies such as firewalls and other common use,Can greatly improve the security level of the system.This paper describes the relationship between the system intrusion detection concept, development, and firewall technology, the basic principle, operation mode, classification and trends.Conventional algorithm detection efficiency of existing intrusion detection system used by the poor can not meet the security needs of large-scale and high-bandwidth networks,false negative rate and false alarm rate is higher,difficult to achieve distributed,accurately detect sophisticated attacks and other cooperative means of attack;In addition, early warning capability severely limited in the attack signature database for unknown intrusions lack of early warning capability.This paper uses a neighborhood based on rough set attribute reduction algorithm,positive domain neighborhood rough set determined to evaluate the importance of each attribute,descending order according to the importance of the attribute to set reduction,forming a plurality of attribute subset.The realization of a mixed type continuous data effectively addressed,avoiding important data that may occur when discrete or hidden information is lost.Second we use the harmonic search algorithm optimized.By repeatedly adjust the memory of the solution variables,so the function value increases the number of iterations continue convergence,so as to complete the optimization of support vector machine parameters.In addition, we also use Bagging classification algorithm integration. .Finally, we realize this intrusion detection system by programming, test results show that the performance of the system is an improvement over the current system are, of course, the follow-up work, we need to capture and to improve network security technologies and other aspects, thereby develop a comprehensive information security system.
Keywords intrusion detection; neighborhood rough set; harmony search; support vector machine; Integrated

目录
1. 绪论 4
1.1 引言 4
1.2 研究的背景及意义 4
1.3 入侵检测系统发展及研究现状 5
1.4 基本目标及主要内容 6
1.5 论文组织结构 6
2.入侵检测 7
2.1 入侵检测的概念 7
2.2 入侵检测的原理 7
2.3 入侵检测的分类 8
2.4 入侵检测技术的进展及发展趋势 11
3.支持向量机 13
3.1 支持向量机的基本原理 13
3.1.1 线性硬间隔分类器 13
3.1.2 线性软间隔分类器 14
3.1.3 非线性硬间隔分类器 15
3.2 支持向量机的优势与不足 16
3.2.1 支持向量机在入侵检测领域中的主要优势 16
3.2.2 支持向量机在入侵检测领域中的不足 16
3.3 小结 17
4.本文算法的描述 18
4.1 数据预处理——属性约简算法 18
4.2 基于和声搜索算法的支持向量机参数选择 20
4.2.1 支持向量机中核函数的选择 20
4.2.2 和声搜索算法（Harmony Search，HS） 20
4.2.3 基于和声搜索算法的 SVM 参数优化选择 22
4.3Bagging集成 23
4.4 小结 23
5.仿真实验及分析 24
5.1数据来源说明 24
5.2 算法评价标准 24
5.3 数据预处理 24
5.4 仿真实验 25
5.4.1 实验步骤 25
5.4.2 实验结论及分析 25
5.5 实验结论 28
致 谢 28
参考文献 29

1. 绪论
1.1 引言
计算机网络是上个世纪的人类文明的一项伟大的发明创造，它极大地丰富和方便了人们的生产和生活，尤其是近几十年来，计算机网络技术日新月异，使得其应用领域不断扩大，并且越来越来成为人们生活的重要工具和手段，同时人们也必将越来越依赖于计算机来处理和存储工作中的各种事务。这样，网络安全就不能不成为人们研究的热点问题。在这其中网络入侵检测就受到了人们的高度关注，因为它是一种积极主动的安全防护工具，其不仅提供了对内部攻击、外部攻击以及误操作的实时防护功能，与此同时入侵检测能在计算机网络和系统受到危害之前就进行报警拦截和响应，被认为是防火墙技术以外的第二道安全闸门，在网络性能无任何影响的情况下对网络进行监测。一方面，入侵检测补充了防火墙的不足，协助系统对付网络攻击，扩展了系统管理员的安全管理能力（包括安全审计、监管、进攻识别和响应），提高了信息安全基础结构的完整性；另一方面，网络入侵检测可以提高网络安全的能力，使得计算机网络的开放性和共享性得到更好的保障，也会使得计算机网络更好的服务于人们的生活和工作。同时，这对于一个国家的主权、政治、军事以及社会稳定也是有着相当的重要性，据调查，美国每年由于计算机网络安全问题所造成的经济损失高达上百亿美元。所以，保障信息网络安全已逐渐成为人们关注的一个焦点问题[1]。
1.2 研究的背景及意义
在互联网高速发展的今天，计算机网络已经成为人们生活和工作不可分割的一部分，人们习惯用网络来查询，交流，购物、理财和办公。当越来越多的政府机构运用计算机和互联网处理各种事件以及越来越多的公司将其关键、核心的业务转移至互联网时候，计算机网络安全就成为摆在人们面前的一个不可回避的问题。这些网络安全问题所造成的各种损失是非常巨大的，有时甚至会威胁到国家的主权、政治、安全以及社会的稳定。“棱镜门”事件更是为我国信息安全保护形势敲响了警钟。
随着网络攻击手段的多样化，黑客对网络的的攻击能力越来越强大，而现有的一些安全防御措施诸如防火墙、安全审计、数据加密、访问控制等，都会存在一些缺陷，而且功能过于单调，不可能构成一个完整的安全防御体系，使得网络安全的问题变得越来越突出。
目前，为应对网络中存在的各种安全隐患，发展最为成熟的技术是防火墙技术，但是防火墙技术的安全防护功能极为有限，首先伪造IP攻击它很难防止；其次防火墙很难应对应用层出现的后门、应用设计缺陷以及加密通道的攻击；同时防火墙只对外部网络的攻击比较有效，而面对来自网络内部的攻击时，防火墙便无能为力；而且防火墙不能有效应地对隐藏在正常数据包中的恶意代码。
防火墙技术除了上述的这些明显的缺陷外，还有一个严重问题就是防火墙的作用是保护不同的网络，而攻击者一旦突破了防火墙就可以直接对网络中所有的计算机发动攻击。因此，用入侵检测技术这种新的主动网络安全防御手段，来作为防火墙技术的补充，与其联合应用对加强网络安全有着十分重大的意义。
来自外部网络的攻击可以被入侵检测系统所应对，而且娶亲检测系统同样对来自网络内部的攻击也同样有效。它地工作原理是收集信息于计算机网络系统中的若干关键节点，并对进行统计、分析，用来检测本机和网络中是否有违反安全策略的现象，是不是出现受到袭击的迹象。入侵检测技术最大的特点就是采用了动态安全技术，并且可有效发现来自网络内部与外部的攻击，并发出警报，把它与静态防火墙技术等配合使用，可以大大提高系统的安全防护水平。
一般有有三个组成部分存在于入侵检测系统（Intrusion Detection System, IDS），它们分别是探测器、分析器和用户接口[2]。探测器的主要功能是从计算机网络中的关键点采集信息；分析器的主要功能是对已经收集到的信息进行有效地分析，通过分析确定是否存在非法入侵；用户接口的主要功能是为用户提供一个安全方便的操作平台，来完成相关操作[2]。
对数据进行分类是入侵检测的本质问题，即要通过某种检测手段将数据分为正常数据和异常数据两类，提高入侵检测系统(Intrusion Detection System, IDS)的检测率，降低误报率。在统计学习理论基础上发展起来的支持向量机(Support Vector Machine,SVM)[1-4]是新一代学习算法，由于其卓越的学习性能，已使当前国际机器学习界热点研究此算法，并且在图像分类、生物信息学等热门领域获得了出人意料的应用，并呈现出出巨大的优越性。本设计主要针对支持向量机这一种新型的结构化机器学习方法，将入侵数据进行分类，以尝试得到优于其他诸如聚类分类、遗传算法等更为理想的结果。
1.3 入侵检测系统发展及研究现状
在1980年，James Anderson提出了入侵检测的概念[3]开启了入侵检测的研究。他提出利用审计数据来发现、跟踪、监视来自网络的入侵威胁，把来源于不同类型的计算机系统安全威胁划分为三种类型：外部渗透、内部渗透和不法行为。在1987年，Denning博士提出了一种经典的异常检测抽象模型[4]。这就是入侵检测专家系统(IDES，Intrusion Detection Expert System)，一种实时的入侵检测系统，成为经典的异常检测抽象模型。1997年，有人将神经网络应用于入侵检测系统[5]。1999年WenkeLee博士第一次提出了基于数据挖掘技术的入侵检测技术[1]，从审计数据中自动生成攻击检测模型的新型入侵检测系统在利用智能算法的情况下实现了，使得智能化的特点渗入到传统的入侵检测系统中。
目前入侵检测技术的发展百花齐放，但比较突出的两个研究方向是分布式与智能化。在国际上，洛斯阿拉莫斯国家实验室、、加州大学戴维斯分校、普渡大学、哥伦比业大学、新墨西哥大学等科研机构在这些方面的研究代表了当前世界的最高水平。

概念诞生
1980年
产生模型
80年代中期
模型发展
80年代后期到90年代初期
网络IDS
90年代至今
异常检测
90年代至今
智能IDS
目前
基于主机

图1 IDS发展过程图
目前国内对于入侵检测技术的研究也非常火热，很多高校、科研院所、企业都展开了相关的技术研究，并提出了许多改进入侵检测技术的新方法。
在这些国内外进行的入侵检测技术的研究中，利用数据挖掘技术，可以有效地提高入侵检测的自适应性、有效性和可扩展性。但是这些研究都还没有达到一个理想的状态，因此，可以说整个的研究仍然处在进一步完善与发展的过程中。

1.4 基本目标及主要内容
在研究有限样本情况下的统计规律及学习方法的基础上发展起来的支持向量机(Support Vector Machine,SVM)是一种通用的学习算法。其在文本识别、人脸识别、函数回归等众多领域得到了很好的应用。本文分析了当前入侵检测系统中分类算法的不足，尝试将支持向量机的有关分类的优点引入入侵检测分类器中，以期望达到良好的效果。针对这些问题，本文做了如下工作：
1.介绍了当前有关网络安全的状况，并指出入侵检测在网络安全中的必要性和重要性；
2.通过分析有关的分类算法来指出它们的缺点和不足，并指出引入本文所采用的算法后所达到的改善的效果；
3.用KDD CUP 99数据进行仿真实验，作为改进后算法的有效性的验证。

2.入侵检测
2.1 入侵检测的概念
入侵(Intrusion)是指在没有得到授权的条件下，妄图存取、处理信息或破坏系统以使系统不可靠、不可用的故意行为。此外，入侵的概念含义也包括一切试图危害资源的完整性、保密性和可用性的活动集合。
网络入侵(Hacking)主要是指利用掌握的计算机程序设计技术，来获得非法的或者是未授权的网络访问权或者文件访问权。入侵的行为不仅仅可能是来自于外部的行为，也非常可能是来自于内部用户所进行的未授权行为。
入侵检测(Intrusion Detection)是一种通过收集和分析被保护系统信息来发现入侵的主动网络安全技术，其核心功能是对网络和计算机系统进行实时监控，发现和辨别系统中的入侵行为，发出入侵报警。入侵检测一般被视为系统状态是“正常”或“异常”的二分类问题[4]。
入侵检测系统(Intrusion Detection System)：是指可以执行入侵检测任务并且具有入侵检测功能的系统，它是由软件和硬件组成的。入侵检测系统是防火墙的合理补充，对网络的使用进行监控，在不影响网络性能的情况供对内部攻击、外部攻击和误操作的实时保护。

2.2 入侵检测的原理
实际上，入侵检测系统(Intrusion Detection System，IDS)事先会在网络上“默默”的收集所有相关的数据信息，在数据收集的基础上提取出相应的流量统计特征值，根据这些特征值在知识库中进行对比，匹配耦合度较高的报文流量将被认为是对网络的攻击信息，入侵检测系统的工作阶段可分为四个阶段：数据收集、数据处理、数据分析和响应处理。入侵检测系统工作原理如图2.1所示。
(1)数据收集：
通过分布的网络与主机上的若干监测点，收集主机日志、网络数据包、应用程序数据和防火墙日志，这些数据信息为其后进行的检测提供数据基础。
(2)数据处理：
通过数据收集得到的数据往往存在噪声，而且数据量也非常巨大，对收集到的数据进行标准化，格式化的处理，可以为后续进行的数据分析提供一个良好的基础。
(3)数据分析：
通过采用统计学方法或者其他的智能算法，对处理过的数据进行相关的分析，来发现其中是否存在非正常数据。
(4)响应处理：
入侵发生时，入侵检测系统一旦检测到异常，就会主动采取措施以进行防护、保存入侵证据并通知给管理员等。按照事先预设的异常处理程序，当入侵检测系统发现攻击信息后，可以自动完成诸如切断网络、记录日志，给管理员发信息等相关动作。
攻击者
数据收集
数据处理
数据分析
响应处理
具有脆弱性的系统和网络

图2 IDS的一般工作模式

2.3 入侵检测的分类
入侵检测系统有多重分类，包括从体系结构来分类可以分成集中式IDS、等级式IDS、分布式IDS；从同步性来分类可以分为实时连续式IDS、间隔批处理式IDS；从数据来源上分可以分成基于主机的IDS、基于网络的IDS、混合式IDS、文件完整性检查式IDS；从检测技术上来分可以分成异常检测式IDS、误用检测式IDS、协议分析IDS；从响应方式上可以分为主动响应式IDS、被动响应式IDS；从时效性上可以分为联机分析式IDS、脱机分析式IDS。入侵检测系统分类如图2.2所示。
集中式IDS
等级式IDS
分布式IDS
实时连续式IDS
间隔批处理式IDS
基于主机的IDS
基于网络的IDS
混合式IDS
文件完整性检查式IDS
异常检测式IDS
误用检测式IDS
主动响应式IDS
协议分析式IDS
被动响应式IDS
联机分析式IDS
脱机分析式IDS
体系结构
同步性
数据来源
检测技术
响应方式
时效性
入侵检测系统
(IDS)

图3 IDS分类
本文从入侵检测系统最常用的检测技术、数据来源、检测技术三种分类方法来分别探讨。
按照检测技术的IDS分类：
（1）误用入侵检测(Misuse Intrusion Detection)：误用入侵检测和入侵检测的方法，它是基于信息（知识，模式，等等）的已知的入侵攻击[9]。误用入侵检测的原理是它认为所有的入侵行为都可以用一种模式来代表，入侵检测系统的工作就是判定被检测对象是不是与这种模式相符合。这种工作模式决定了它只可检测到已知的攻击，而不能发觉新的攻击。但误用入侵检测系统具有误报率低的特点。图7给出了误用入侵检测的模型。
匹配
规则
审计数据
信息处理
攻击
状态
修改当前规则
修改当前规则
时间信息

图4 误用入侵检测的模型
（2）异常入侵检测(Anomaly Intrusion Detection)：异常入侵检测检测系统攻击的方法是认为正常活动与入侵活动的区别显著，根据这一认识，就可以得到系统正常状态下的特性，而把所有与正常轨迹不同的系统状态认为是可能的攻击信息。但是有一点不好确定，就是如何设置异常阈值，只有合理的阈值，才能有效区分正常状态与非正常状态。图8给出了异常入侵检测的模型。
背离
统计
审计数据
系统处理
攻击
状态
动态产生新特征
更新特征

图5 异常入侵检测的模型
（3）协议分析：协议分析式一种新的入侵检测技术，它的理论基础模式匹配。网络协议的一个特点就是高度有序性，而协议分析技术利用这个特点对数据包进行捕捉、协议分析和命令解析等技术，来确定某种攻击是不是存在。协议分析技术的特点就是计算量小，检测速度快[10]。
按照时效性的IDS分类：
（1）脱机分析：脱机分析顾名思义就是在攻击发生之后才进行的入侵检测手段，它不具有实时性。它的这一特点使得它不能够实时的响应，但是它也具有一些不可忽略的优点，就是实时分析占用系统资源大，而脱机分析就不存在这一问题，不会影响整个系统的性能，这一特点在网络数据量极大时尤为突出。
（2）联机分析：联机分析与脱机分析相反，具有实时性，早期的联机分析系统会严重影响系统性能，但是随着硬件技术的快速发展，越来越多的入侵检测系统采用了联机分析，可以对攻击行为进行实时监测和响应。
按数据源的IDS分类：
（1）基于主机的IDS(Host-based Intrusion Detection System,HIDS)：基于主机的入侵检测系统是指IDS在被保护的主机上安装，主机上的系统审计日志是主要的数据源，依据该数据源进行分析和检查。当系统受到攻击时，往往会首先破坏主机的审计数据，这就要赶在攻击者控制主机破坏审计数据与IDS之前，实时发出警报，采取相关措施。
（2）基于网络的IDS (Network-based Intrusion Detection System, NIDS)：基于网络的入侵检测系统在需要保护的网段之中安装，对网段中传输的数据包进行实时的监控，对收集的数据信息进行分析，从中发现攻击信息。它的最大优点就是和网络系统融为一体，不会因为入侵检测系统的运行而给网络与原系统增加负担；还有它对用户来说是透明的获取数据所用的监控器，这就使得攻击者不容易在网络中定位并破坏入侵检测系统。
（3）混合式IDS：集中了基于主机IDS和基于网络的IDS的优点，它可以发现攻击于系统主机日志，也可以发现攻击于网络中，是十分强大的主动防卫体系。图9给出了一种混合式IDS的布置。

2.4 入侵检测技术的进展及发展趋势
由于非线性和高维是入侵检测领域中所获得的数据具有的常见特点，而且数据往往不服从已知的某种分布，如果用传统统计学的方法检测将难以凑效，因此，神经网络、K领域、贝叶斯网络以及支持向量机等机器学习方法被用于入侵检测领域，其中算法支持向量机(Support Vector Machine,SVM)[14,15]是建立在统计学习理论基础上，是一种机器学习方法，以结构风险最小化作为其准则，以其具有结构简单、全局优化、训练时间短、泛化性能好等优点，可以较好的解决了高维、非线性、小样本等问题。有很多学者在这方面做了不少努力，文献[8,19,20]均是采用支持向量机进行入侵检测，获得了不错的效果，这进一步显示了支持向量机优于其他分类算法的性能。另外，还有一些学者将粗糙集理论和支持向量机理论结合来开发一些新的检测算法[8]，同样取得了较好的效果。
入侵检测技术是一种主动的网络安全防御手段，其不仅能应对网络外部的攻击，而且能够处理来自网络自身的攻击，这些特点是能够弥补防火墙技术的不足的。入侵检测系统的主要发展趋势有如下的几个方面：
(1)面向Ipv6的IDS：Ipv6标准时下一代互联网采用的协议标准，它与现有的IPv4协议相比，地址空间极大地扩充。地址空间的扩充，使得超大规模网络环境的出现成为可能。由于Ipv6协议本身就具有加密和认证的功能，这就使得入侵检测系统对网路数据包的监听更加困难了。为了解决这个问题，需要有面向Ipv6的入侵检测系统具有融合分布式体系结构和高性能计算技术。
(2)高速入侵检测：计算机网络的数据连接以及交换设备的速度越来越高，这些硬件设备性能的快速提升，带来了一个新的问题，就是入侵检测系统如何应对数量巨大的，且高速的数据交换环境。这就要求入侵检测系统需要具有强大的数据处理能力，以满足高速网络的需求，这有要求新的入侵检测系统要重新设计软件结构与算法。
(3)大规模、分布式的入侵检测：分布式入侵检测系统最典型的例子就是基于网络的入侵检测系统，这种入侵检测系统仍然具有单点失效的问题，这是由于基于网络的入侵检测系统存在一个中心模块管理入侵检测系统。获得安全信息在异构主机以及异构网络，使入侵检测系统中各模块的合作时间，并成为未来的重点。
(4)标准化的入侵检测：入侵检测系统对网络安全防护来说，是一个不可或缺的技术手段，越来越多的企业在开发入侵检测系统，并投放市场。这就带来了一个问题，不同企业开发的入侵检测系统之间的数据交换工作是非常困难的，各个企业的入侵检测系统不能协同工作，这就需要制定一个广大企业都能够接受的统一规范，使得各企业开发的入侵检测系统具有通用化和标准化。
(5)入侵检测系统与其他安全技术的配合使用：入侵检测系统相对于其他网络安全技术有不可替代的优势，但也不是万能的，也存在一些局限性。入侵检测系统与其他安全技术配合使用，可以取得更好的网络安全防护。这就需要入侵检测系统安全开放的数据接口，让入侵检测系统与其他网络安全技术能够进行安全的数据交换。这些安全措施都是受控制于系统统一的安全管理策略[3]。
2.5 小结
本章首先介绍了入侵检测的概念，指出了入侵检测的用途和目的；其次，通过介绍入侵检测的原理及其分类，指出了入侵检测系统的基本原理与工作模式；最后，本文作者在阅读相关文献的基础上总结了当前入侵检测技术的进展和发展趋势，指明了当前学界对入侵检测常用的方法和技术。

3.支持向量机
3.1 支持向量机的基本原理
建立在统计学习理论和结构风险最小化原理基础上的支持向量机是一种新型学习机器[2]。支持向量机的理论完备，并且具有较好的学习能力和推广能力，已经成为国内外研究的一个热点。其基本思想是通过非线性映射将输入空间映射到高维空间，在构造一个间隔最大的分类超平面，使得离分类超平面最近的样本之间的距离最大。
3.1.1 线性硬间隔分类器
支持向量机中最早提出的模型是最大间隔分类器，也称为线性硬间隔分类器。给定样本集其中为样本基数，是每个训练样本向量的维数，表示分类类别。图3.1中，方框点代表的训练样本，圆点表示的训练样本，中间的实线是最优超平面，其相邻的两个虚线分别为过各类中离分类超平面最近的样本且平行于最优超平面的平面，它们之间的距离就是分类间隔。位于两虚线上的样本称为支持向量。

分类间隔
分类超平面H

图6 两类线性分划的最优超平面

该超平面可表示为，其中，是超平面的法线方向。得到的分类函数为：
(3.1)
由图6可知，平面可表示为：
(3.2)
将式(3.2)进行归一化处理后，得到的约束条件，即样本集需满足下面的不等式：
(3.3)
在训练样本是线性可分的情形下，要求分类超平面不仅将各类样本没有错误的分开，而且要使分类间隔最大，前者是为了保证经验风险为最小，后者则是为了使置信区间是最小，从而使结构风险最小。分类超平面的分类间隔为，使间隔最大等价于最小，因此，在线性可分条件下构造最优超平面，就转化为下面的二次规划问题：
(3.4)
式(3.4)可以转化为一个较简单的对偶二次规划问题
(3.5)
其中，为每个样本对应的拉格朗日乘子，只有支持向量的拉格朗日乘子不为零。通过选择不为零的，解出。对于给定的未知样本，只需计算(3.1)便可以判断所属的分类器。
3.1.2 线性软间隔分类器
关于线性可分问题，可用线性硬间隔分类器来求出分类超平面，但是，线性硬间隔分类器只能用于特征空间中线性可分的训练集，然而在实际中，大多数情况下训练集会有噪声，不能满足线性可分性。线性硬间隔分类器的主要问题是它总是产生一个没有训练误差的分类超平面，当然数据不能完全分开时间隔为负数。也就是说，当训练样本线性可分的条件不满足时，原问题的可行区域为空集，而对偶问题是无界的目标函数，这样该优化问题无解。这时，必须对分类间隔进行“软化”，即不满足约束条件的样本点是允许存在的，因此引入一个松弛变量于约束条件中，它在一定程度上违反间隔约束是许可的，从而适当的将约束放宽：
(3.6)
此时，目标函数变为
(3.7)
其中，为可调参数，表示对错误的惩罚程度，越大惩罚越重。支持向量机就转化为在式(3.6)的约束下，最小化式(3.7)，这是一个二次规划问题，最优解为下面Lagrange函数的鞍点：
(3.8)
根据KTT定理，最优解满足：
(3.9)
构建最优超平面的问题可转化为下面的对偶二次规划问题：
(3.10)
可看出，线性可分情况和线性不可分情况的差别在于在线性可分的情况下约束条件为；而线性不可分的情况下约束条件变得更加严格。线性可分情况可看做是线性不可分情况的特例[19]。
3.1.3 非线性硬间隔分类器
在线性情况下，分类器可以寻找出一个使间隔最大的超平面，然而，对于非线性情况，在原输入空间已不存在能正确划分训练集的超平面，因此必须将原来输入空间映射到高维空间，使得训练集在该高维空间中线性可分，即存在能正确划分训练集的超平面。
非线性支持向量机，通过某些特定的非线性映射函数，将输入向量映射到某个高维特征向量，使其线性可分，再在高维空间寻求最优超平面，使间隔最大。这种特定的非线性映射函数也称为核函数。依据泛函分析有关知识，只要一种核函数，满足Mercer条件，它就对应某一变换空间中的内积，即核函数方法是通过定义特征变换样本在特征空间中的内积来实现一种特征变换，高维空间中特征向量的内积可以通过核函数用低维空间中的输入向量直接计算得到，从而特征空间维数的增加不会导致计算量呈指数增长。
定义非线性映射，它将输入向量映射到高维空间中，再定义核函数，那么非支持向量机变为
(3.11)
相应的分类函数变为
(3.12)
常用的几种核函数有：
(1)多项式函数
(2)径向基函数(RBF)
(3)Sigmoid函数

在线性硬间隔分类器的基础上引入松弛变量放松约束即得到线性软间隔分类器是，而非线性硬间隔分类器是在线性硬间隔分类的基础上引入从输入空间到高维空间的映射[20]。
3.2 支持向量机的优势与不足
3.2.1 支持向量机在入侵检测领域中的主要优势
统计学习理论中最年轻也是最实用的算法是支持向量机，可以同时控制经验风险和分类器的容量（用分类器的VC维衡量）两个参数是SVM的核心思想，使分类器间隔达到最大，从而使真实风险最小。另外，支持向量机是在小样本学习的基础上发展起来的分类器设计方法，专门用于小样本数据，而且对数据维数不敏感，具有较好的分类精度和泛化能力[6]。
有些学者通过实验已经发现，基于支持向量机的入侵检测模型具有以下优点，首先，它不需要全部的正常和异常的信息，在给出较少的正常和异常执行迹的情况下就能得到比较理想的检测效果；其次，该方法所需的训练时间和检测时间比其他方法短，因此该方法能够随时升级，并进行高效的实时检测[9]。
3.2.2 支持向量机在入侵检测领域中的不足
尽管支持向量机具有结构简单、全局优化、训练效率高、泛化性能好等优点，能够较好的解决高维、小样本、非线性等问题。但是，有研究表明，支持向量机性能与其核函数的类型、核函数参数和惩罚参数有着密切的联系，这些参数会影响SVM的分类精度及泛化性能。目前，人们往往凭经验并经过大量反复的试验获得较优的参数，这种方法不但低效费时，而且获得的参数往往不是最优的[10]。