基于模拟退火支持向量机的入侵检测系统


单建魁,赵雪峰:基于模拟退火支持向量机的入侵检测系统 2009,30 (21) 4851 0 引 言 入侵检测就是通过检查计算机网络或计算机系统中的信 息并对其进行分析,以判断系统中是否有违背安全策略或计 算机系统安全的行为。 在众多的入侵检测研究中,Forrest等人的研究思路受到了 广泛的关注,该思路就是将入侵检测看作分类问题,也就是将 正常数据和异常数据分辨出来,可见能够使用模式识别的方 法来检测[1]。基于免疫模型的入侵检测、神经网络入侵检测以 及利用挖掘技术的入侵检测都是基于这样的思路 [2]。然而上 述方法都存在一个前提,那就是需要大量的、甚至完备的审计 数据集作为样本,否则检测结果就不理想。然而采集和处理 大量的样本集需要更多的时间,不能很好地满足入侵检测的 实时性。 建立在统计学习理论基础之上的支持向量机 (support vector machines,SVM)在解决小样本集、非线性及高维数据处 理问题时表现出特有的优势。其最大的特点就是根据 Vapnik 结构风险最小化原则,尽量提高学习机的泛化能力,即由有限 的训练样本集得到小的误差,仍然能够保证对独立的测试样 本集保持小的误差[3]。另外,由于支持向量机算法是一个凸优 化问题,所以局部最优解一定是全局最优解,这是其它学习机 望尘莫及的。因此,在小样本集的入侵检测情况下,引入支持 向量机可以达到良好的检测效果。籍此,在参阅了很多支持 向量机入侵检测的算法 [4] 后,本文提出了一种基于支持向量 机的入侵检测模型。该模型针对支持向量机的 3 个关键参数, 利用模拟退火算法(simulate annealing algorithm)进行了优化处 理,从而使得基于支持向量机的入侵检测更加准确,并且检测 时间更短。 1 模拟退火支持向量机模型 (SA-SVM) 1.1 支持向量机 (SVM) 支持向量机是由 Vapnik 与其领导的贝尔实验室的研究小 收稿日期:2009-04-24;修订日期:2009-06-09。 基金项目:国家自然科学基金项目 (40806011)。 作者简介:单建魁 (1973-),男,河北玉田人,硕士,讲师,研究方向为网络安全、数据挖掘; 赵雪峰 (1976-),男,四川西充人,博士研究 生,讲师,研究方向为信息安全、计算机视觉。E-mail:shanjiankui@126.com 基于模拟退火支持向量机的入侵检测系统 单建魁 1, 赵雪峰 1,2 (1. 淮海工学院 计算机工程学院,江苏 连云港 222005;2. 四川大学 CAD/CAM 研究所,四川 成都 610065) 摘 要:为了提高入侵检测系统在小样本集条件下的检测效率,将支持向量机用于网络入侵检测。支持向量机的参数决定 了检测效率,然而难以选择合适的参数值,因此提出利用模拟退火算法来优化这些参数,并设计出基于参数优化的支持向 量机用于入侵检测。通过对样本数据集中的样本进行实验性检测,并与原始支持向量机入侵检测系统进行比较,结果表明 模拟退火支持向量机入侵检测系统检测率高、误报率低,并且缩短了训练时间和检测时间。 关键词:模拟退火算法; 入侵检测; 支持向量机; 检测率; 误码率 中图法分类号:TP393 文献标识码:A 文章编号:1000-7024 (2009) 21-4851-04 Intrusion detection system based on support vector machines with simulated annealing algorithms SHAN Jian-kui1, ZHAO Xue-feng1,2 (1. School of Computer Engineering, Huaihai Institude of Technology, Lianyungang 222005, China; 2. Graduate School of CAD/CAM, Sichuan University, Chengdu 610065, China) Abstract:In order to improve the detection efficiency of IDS (intrusion detection system) under the small sample conditions, SVM (support vector machine) is employed to IDS. The parameters of SVM are the Key factors of detection efficiency and difficult to choose appropriate parameter values. Therefore, SA (simulated annealing) algorithms are used in the proposed SVM model to optimize the parameter selection and SVM with optimized parameters for intrusion detection is designed. Through applied to treat the sample data and comparison of detection ability between the above detection method and the IDS based on original SVM, the results show that the intrusion detection system based on SVM with SA is efficient, lower false rate, and shorten the training time and detection time. Key words:simulated annealing algorithms; intrusion detection; support vector machines; detection rate; false rate 信息安全技术 计算机工程与设计 Computer Engineering and Design 4852 2009,30 (21) 计算机工程与设计 Computer Engineering and Design 组一起开发出来的一种机器学习技术。由于其出色的学习性能 以及同时最小化经验误差和最大化几何边缘区的特点,被广泛 应用于回归分析、模式识别、预测、综合评价和统计分类等方面。 给定样本集 ={( 1, 1 , , , , , , }有 l 个样本,样本为 N 维向量。样本 ,样本标签 {1,-1}。SVM 分类机就是把样 本集的向量以边缘最大分开的最优超平面。边缘最大意味着 距超平面最近的不同类向量之间的分类间隔最大。如图1 所示。 可将 SVM 用定义为如下函数 = + (1) 式中: ——高维特征空间,可以将输入样本空间 x 的非线性 特征映射到高维的线性特征。因为经验风险之和与高维空间 的|| ||影响 ,所以 和 b 由惩罚函数求得 = 1 = 1 , + 1 2 || ||2 (2) 该惩罚函数等式右边第一项为经验风险之和,第二项为 惩罚项。其中 C 是惩罚常数,用于调节上述两项,即 C 实质上 是对经验风险和惩罚项如何匹配的一个裁决。如果增大 C 的 值时,则增大经验误差相对于惩罚项的重要性。为了提高估 计的稳健性,以及保持算法的稀疏性,常选择 -不敏感损失函 数 L(d,y)来对经验风险进行估计。等式中的 C 和 都需要指定。 , ={ 0 > (3) 当预测准确无误时,损失函数值为 0 (即没有损失发生); 当预测有误差时,或者误差大到一定程度时,其损失函数值就 非 0。为了在模型中使用超平面进行划分,引入松弛变量 ≥ 0 (i=1,2,⋯ ,l)。式(2)变换为如下形式 , , * = 1 2 || ||2+ ( = 1 ( + *)) (4) 容易看出 = 1 ( + *)体现了经验风险,|| ||体现了表达能 力。式(4)的约束条件如下 { + + * + ( = 1,2,⋯ , , , *≥ 0) 使用 Lagrange 算子 和 *来优化约束,并将 the Karush- Kuhn-Tucker conditions引用到回归分析中,推导出最大化的对 偶方程式 Alh , * = = 1 * = 1 + * 1 2 = 1 = 1 * * , (5) 约束条件:{ = 1 * = 0 0 0 * ,= 1,2,⋯ , 。 式(5)中的 Lagrange 乘数满足 * = 0。计算出 Lagrange 的 乘数 和 *,超平面的优化期望权值向量 * = = 1 * , (6) 因此,原式(1)可表示为目标等式(7) , , * = = 1 * , + (7) 式中: , ——核函数。核函数的值等于特征空间 T 的向 量 x 和特征空间T 的向量 的内积,即是 , = T *T 。 任何满足 Mercer 条件的函数都可以做核函数,最常用的核函 数有多项式核、B-样条核、傅立叶核、Sigmoid 核和 Gauss 径向 基核等核函数。本文中选择 Gauss 径向基核,其中?为高斯核 函数的频宽,决定高斯核 exp ( || ||2/ 2)函数的性质。 从以上推演过程容易看出,要使SVM发挥出最佳的分类 效果,,和 C 等 3 个参数的选择非常关键。如果选择不合适, 将导致过学习或欠学习现象的发生。然而,至今未有一种行 之有效的选择方法,因此拟使用模拟退火算法(simulated annea- ling algorithm,SA)优化 SVM 模型的参数选择。 1.2 模拟退火支持向量机 (SA-SVM) 模拟退火算法(simulated annealing)来源于固体退火原理,类 似于物质的退火过程,是一种启发式的蒙特卡罗 (Monte Carlo) 方法。该算法是在给定的模型空间内搜索目标函数达到全局 极小值的最优模型,常用于各种最优化问题计算。如果系统在 温度T达到热平衡,Boltzmann给出系统在指定状态的概率 = exp / exp / (8) 式中: —— s 状态下的能量;k—— Boltzmann 常系数,S—— 所有可能状态的集合。在此基础上,Kirkpatrick 等在 1983 年 提出 Metropolis 模拟退火算法,该算法分两步交替进行计算: 第一步,随机扰动产生新状态并计算目标能量的增值;第二步 根据 Metropolis 准则判断新状态是否被接受。Metropolis 准则 描 述 当 系 统 由 原 状 态 (能 量 ) 产 生 新 状 态 (能 量 ),如果 ≤ ,则新状态被自动接受;否则,通过概 率函数来决定新状态被接受的概率 = exp ( )(9) 由以上分析容易得知,要应用Metropolis模拟退火算法来 优化SVM模型中 ,和C等 3 个重要参数,就必须选择合适的 变量作为 Metropolis 模拟退火算法惟一的系统初始状态。针 对此种情况,考虑将 SVM 模型中 ,和 C 联合起来,通过一定 的变换求得这样的系统初始状态,然后在该状态下计算目标 函数(即目标状态)。改进后的模拟退火算法描述如下: 步骤 1:给出 SVM 模型中 3 个参数 ,和 C 的最大值,并 生成这 3 个参数的初始值,代入 SVM 模型中,将所得预测误 差的绝对值定义为系统状态 E,即用 ,和 C 等 3 个参数来确 定系统状态。这样就得到系统的初始状态 0 。 步骤 2:经过随机的临时状态,该状态下能产生 3 个新的 正参数。 步骤 3:如果满足下式则接受该临时状态,否则不接受。 { > , < ,0≥ ≥1 (10) 图 1 两类线性分划的最优超平面 正样本 超平面 负样本 分类间隔 单建魁,赵雪峰:基于模拟退火支持向量机的入侵检测系统 2009,30 (21) 4853 式(9)中的 是用来判断是否接受临时状态的一个随机数。 如果临时状态被接受,则设置为当前状态。 步骤 4:如果临时状态没有被接受,则返回到步骤 2。此 外,如果当前状态不优于系统状态,那么重复步骤 2 和 3,直到 当前状态优于系统状态为止。最后,设置当前状态为新的系 统状态。为了避免死循环,需要设定一个最大循环次数,本算 法中设定为 300。 步骤 5:产生出新的系统状态后,通过下式来进行降温 Newtemperature = (Currenttemperature)× (0< <1) (11) 本算法给 赋值为 0.9。如果达到了期望温度,则退出算 法,最后的状态就是最优化的值。否则,返回步骤 2。 最后由式 (12)计算出绝对平均误差(MAPE),作为是否适 合用于 SA-SVM 模型的评价标准 = 1 = 1 × 100% (12) 式中:l— — 样本的个数; — — 第 i 个样本的真实值; — — 第 个样本的期望值。 Metropolis 模拟退火算法用来为 SVM 寻找一个更好的参 数,使得在每次迭代中都有较小的 MAPE。该算法的框架图 如图 2 所示。 2 基于 SA-SVM 的入侵检测系统 2.1 入侵检测模型 应用模拟退火算法得到的 3 个重要参数 、 和 生成优化 SVM。结合通用入侵检测模型 CIDF[5],设计出的“入侵检测模 型结构”如图 3 所示。其中样本数据库中存储的是实时网络 数据包数据和标准训练数据,而入侵检测结果在被响应的同 时,也被保存在检测结果数据库中,以备进一步的安全分析。 2.2 入侵检测算法 步骤 1:数据的采集。所能获取的输入数据数量和质量, 对入侵检测结果的输出有很大影响。为了提高入侵检测系统 的效率和性能,入侵检测的检测对象越来越丰富。基于主机 的入侵检测数据包括了系统调用、应用程序日志、站点访问日 志和注册表访问记录等一些系统信息 [6]。基于网络的入侵检 测数据虽然主要还是网络包,但是不再简单的只考虑某一类 型数据报,而是根据协议栈进行综合的分析[7]。网络包数据可 以通过抓包工具获取,譬如 Unix 下的 Tcpdump、Windows 下的 Libdump,也可以使用专业的软件 snort、Winpcap 等来捕获。 步骤 2:数据预处理。网络数据预处理的目的是将网络数 据转换为SVM的输入向量形式,SVM的分类器只能对维数相 同的数字向量进行分类。从得到的网络数据流中分析出网络 连接记录,对于每条连接记录,选择出 n 个属性特征,将选择 的属性长度和数据类型进行必要处理,然后用一维向量 x 表 示一次网络连接,={ 1,⋯ , ,⋯ , },= 1,2,⋯ , ;其中 是样本的 第 i 个特征值。为了消除不同属性特征之间的差别,使其在同 一个范围内可比较,对属性值进行归一化处理,使得 0≤ ≤ 1。 对于输出检测结果,定义输出量 Y。考虑到只判断每次网络连 接是否正常,故只需定义Y={+1,-1},当 = +1 时表示连接正常, 而当 y =-1 时表示连接异常。 步骤 3:SVM 分类器。SVM 分类器的工作过程分为“训练 态”和“检测态”两个阶段,是整个入侵检测系统的核心部分。 步骤 4:SVM 的训练。如果 SVM 处于训练态,向 SVM 分 类机输入样本支持向量,通过训练产生“分类超平面”,正是该 超平面构成检测单元。 步骤 5:SVM 分类机的入侵检测。如果SVM 处于预测状态, 则输入“待检测支持向量”。预测后的入侵检测结果,一方面输 送到响应单元,驱动相应的响应操作;另一方面存入数据库,对 于检测到的新攻击方式,将其反馈回样本数据库。根据更新后 的样本数据对SVM进行新的训练,重新产生新的“分类超平面”。 3 仿真实验及入侵检测结果分析 实验研究中,采用的训练样本数据和测试数据来源于 KDDCup99 中的网络入侵检测数据包kddcup_data_10peercent[8]。 该数据包覆盖4 种类型的攻击:Dos(拒绝服务攻击)、Probing(端 口扫描和漏洞扫描)、R2L(远程机器的非法访问)和 U2R(普通 用户对本地超级用户权限的非法访问)。数据包中每条连接 记录有 41 个固定特征属性,选择其中 31 个具有较强标识性的 特征属性进行分析,如表 1 所示。 为了更有效的进行检测实验,从网络入侵检测数据包抽 取出部分具有典型代表性的样本进行实验。前后抽取 5 次, 图 2 模拟退火支持向量机模型 Y N 退出条件 预测误差 计算预测误差 预测值 模拟退火 SA 优化后的 , 和 新的 , 和 支持向量机 SVM 输入 , 和 的 初始值 图 3 基于 SA-SVM 入侵检测模型结构 入侵检测系统的响应 SVM 待检测支持向量 数据预处理 数据采集 样本 数据库 学习样本 样本支持向量 检测结果 数据库 经SA-SVM优化所得的 参数 , 和 表 1 连接记录的 31 个选用特征属性 Protocol_type Duration Num_file_creations Srv_rerror_rate service flag land Logged_in Root_sheel Su_attempted Is_host_login Is_guest_login Src_bytes Dst_bytes Wrong_fragment Urgent Hot Num_failed_logins Num_compromised Num_root Num_shells Num_access_files Num_outbound_cmds Count Srv_count Serror_rate Srv_serror_rate Rerror_rate Same_srv_rate Diff_srv_rate Srv_diff_host_rate 4854 2009,30 (21) 计算机工程与设计 Computer Engineering and Design 每两次之间的样本重复率低于 10%,每次抽取的样本 50%用 于训练,另外 50%用于测试。为了进行对比,在使用 SA-SVM 进行实验检测后,也使用未进行参数优化的 SVM 对相同样本 集进行入侵检测。实验数据如表 2 所示。 入侵检测系统的检测率和误报率这两个指标分别从正、 反两方面标识系统的检测准确率,优秀的入侵检测系统应该 有尽量高的检测率和尽量低的误报率。对实验结果进行了检 测率和误报率统计分析。检测率和误报率的定义如下 = / (14) = / (15) 式中: — — 检测率, — — 被检测出的攻击样本数, — — 攻击样本总数; — — 误报率, — — 被误报为异常样本的 正常样本数, — — 正常样本数。此外,检测系统的实时性很 重要,能及时识别出入侵攻击、尽快隔离或阻止攻击、减少破 坏是良好检测系统的一个重要方面,所以对检测时间进行了 大致观察和比较,借此对检测系统的实时性进行评估。实验 过程中所得的数据记录如表 3 所示。 图 4、图 5 是分别基于 SVM 和 SA-SVM 两种算法的入侵 检测结果统计图。图 4 表明无论样本集大小,后者的检测率 均明显高于前者;图 5 也清楚的显示出后者的误报率低于前 者,随着样本集增大,后者的误报率增速大大减缓,而且未出 现前者的震荡现象。 4 结束语 基于SVM的入侵检测研究方兴未艾,它能在小样本集的 基础上完成入侵检测,为了有更好的检测效果,众多研究者提 出了多种对SVM进行改进的算法,推动该类算法的快速发展。 在现有算法的研究基础上,本文针对 SVM 关键参数难以进行 最佳选择的情况,提出了用模拟退火算法对相关参数进行优 化,设计出模拟退火支持向量机模型(SA-SVM)。从KDDCup99 的 10%数据包中抽取典型连接数据构成样本集,运用SA-SVM 模型进行入侵检测。本文同时以未优化参数的原始 SVM 对 相同样本集进行入侵检测,以便进行比较研究。比较研究结 果表明:基于SA-SVM模型的入侵检测系统具有检测率高、误 报率低以及训练检测时间短等优点。 参考文献: [1] Yi Ping, Jiang Xinghao,Wu Yue,et al. Distributed intrusion de- tection for mobile ad hoc networks[J].Journal of Systems Engi- neering and Electronics,2008,19(4):851-859. [2] 田俊峰,王惠然,傅玥.TCP/IP审计数据缩减技术在入侵检测中 的可行性研究[J].电子与信息学报,2007,29(9):2248-2251. [3] 李洋,方滨兴,郭莉,等.基于主动学习和 TCM-KNN 方法的有 指导入侵检测技术[J].计算机学报,2007,30(8):1464-1473. [4] 肖立中,邵志清,马汉华,等.网络入侵检测中的自动决定聚类数 算法[J].软件学报,2008,19(8):2140-2148. [5] 吴磊,杨世平.基于特征映射的入侵监测预处理方法[J].计算机 工程与设计,2008,29(23):5471-5479. [6] 陈泽茂,吴晓平,沈昌祥.基于操作系统安全的恶意代码防御研 究述评[J].计算机工程与设计,2008,29(21):5407-5410. [7] 殷丽华,方滨兴.入侵容忍系统安全属性分析[J].计算机学报, 2006,29(8):1505-1512. [8] Information and Computer Science, University of California, Iri- vine. KDD cup 1999 data[EB/OL]. http://kdd.ics.uci.edu//data- bases/kddcup99/kddcup99.html. 表 2 用于入侵检测的数据 样本集编号 样本总数 正常样本数 攻击样本数 1 2 3 4 5 500 1 000 2 000 3 000 4 000 126 189 464 697 956 374 811 1 536 2 303 3 044 表 3 实验结果数据 算法 样本集 编号 /% /% SVM 1 2 3 4 5 320 698 1 321 2 026 2 744 374 811 1 536 2 303 3 044 85.601 86.027 85.975 87.990 90.154 11 16 30 70 95 126 189 464 697 956 8.73 8.47 6.47 10.04 9.94 SA-SVM 1 2 3 4 5 347 724 1 415 2 170 2 885 374 811 1 536 2 303 3 044 92.678 89.311 92.100 94.231 94.761 9 19 32 61 70 126 189 464 697 956 7.14 10.05 6.9 8.75 7.32 样本集编号 SVM; SA-SVM 1 2 3 4 5 0.95 0.94 0.93 0.92 0.91 0.9 0.89 0.88 0.87 0.86 0.85 检 测 率 D R 图 4 检测率 样本集编号 SVM; SA-SVM 1 2 3 4 5 2.5 2 1.5 1 0.5 0 检 测 时 间 / s 图 5 误报率
还剩3页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

forestqqqq

贡献于2011-11-24

下载需要 5 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf