改进的Sunday模式匹配算法

改进的Sunday模式匹配算法 $ང ?$øщ?:1000—3428(2009)07—0125—$? ?:TP?pA?$A 30902 ?: 改进的模式匹配算法Sunday 万晓榆，杨 波，樊自甫 (重庆邮电大学下一代网络应用技术研究所，重庆 400065) 摘 要:在基于模式匹配的检测方法中，匹配效率是检测技术的瓶颈，间接影响入侵检测系统的实时性能。该4 文对种模 式匹配算法进行 分析后，选择最优的S unday 算法进行改进。该算法进行匹配前先找到模式串中的特征字符(出现概率最小的字符)，进行特征字符与尾字符 双重匹配，失败则移动尽可能远的距离。实验结果证明匹配效率比 Sunday 算法有一定的提高。 关键词:字符串,模式匹配,特征字符,计算复杂度 Improved Sunday Pattern Matching Algorithm WAN Xiao-yu, YANG Bo, FAN Zi-fu (Next Generation Network Technology Institute, Chongqing University of Post and TelecommunicationC, hongqing 400065) 【Abstract】Pattern matching algorithm is an important method in intrusion detection. The matching efficiency is the bottleneck of intrusion detection, which indirectly affects the real-time performance of the system. By analyzing four pattern matching algorithms, this paper proposes an improved Sunday algorithm. It finds the character- word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 in the pattern string before matching, and then compares the character-word and the last word of the pattern string with the text. If the matching fails, the character-word will be moved as far as possible. Experiment of result proves that its match efficiency is better than Sunday algorithm. 【Key words】character string; pattern matching; character-word; computationacol mplexity 动一个字符的位置，右移也不是必须从模式串起点处重新 试1 概述 匹配，即模式串一次可以右移多个字符的位置，右移后可以 随着网络的发展，越来越多的安全问题对网络应用造成 从模式串起点后的某处开始试匹配。特点是效率高但不易 理巨大威胁，每年全球因计算机网络的安全系统被破坏而造成 解。算法的复杂度很小，为O (m+n。) 的经济损失达数百亿美元。入侵检测系统(Intrusion Detection [2-3 ] BM(Boyer-Moore 算)法 的 特点在于 P[0,1, ,m-1] 与 System, IDS)由于可以为网络安全提供实时的入侵检测并采 T[s,s+1, ,s+m-1匹配]时为从右到左，也可以在得到部分匹配 取相应的防护手段而备受青睐。网络技术的快速发展使得如 时充分利用部分匹配所隐含的、可帮助跳过不必要的测试、 何让 IDS 在高速网络环境下实时有效地进行检测成为研究 重 提高算法效率的信息。特点是效率高、较易理解，计算复杂 点。入侵检测包括特征检测和异常检测，其中，特征检测建 度为 O((n-m×)m+|Σ|)，其中，Σ为字符集的字符数，在最坏 立在了解各种已知网络入侵方法和系统缺陷知识的基础之 的情况下，计算复杂度为 O(n×m)，但由于实际应用中这种 上，它需要解决 2 个问题:(1)如何充分可靠地描述入侵行为, 情况极少出现，因此 BM 算法仍然得到广泛应用。 (2)使用何种模式匹配算法快速准确地检测入侵行为。本文主 [4]Sunday算 法在匹配过程中并不严格要求从左到右或从 要针对第(2)个问题进行研究，首先引入模式匹配的形式化 定[1]右到左进行比较，在发现不匹配时，算法跳过尽可能多的字 义:(1)T 为待匹配的主串，标识为t ext[0,1, ,n-1],(2)P 为 符进行下一次匹配，从而提高了匹配效率。发生不匹配时 待匹配的模式串，标识为pa tt[0,1, ,m-1]。如果对于 0?s? (T[i]?P[j])，找到字符串最后一个字符所对应的主串位置的 n-m，存在 text[s,s+1, , s+m-1]=patt[0,1, ,m-1]，则模式串 P 下一个字符，然后确定其是否在模式串中出现，如果出现 ，在文本 T 中出现，即模式与文本匹配。字符串模式匹配问题 则移动到相应位置，如果没有出现，则将整个字符串的首字 就是查找 P 是否在 T 中出现以及出现的位置。本文首先对几 符移动到此字符后面的一个字符继续进行首字符的匹配。该 种常见算法进行分析比较，选择其中最优的Sund a y 算法进行 算法在最坏情况下的计算复杂度为O (n×m)，对于短模式串 改进，最后进行仿真实验和性能分析。 的匹配问题，该算法执行速度较快。 2 相关算法 [2-3] 通过以上分析可知，一般情况下，BF 匹配算法的效率最 BF(B rute Force算)法是效率最低的算法。从主串的第 低， KMP 算法最不易理解但是复杂度最低，Sunday 算法的 1 个字符起与模式串的第1 个字符比较，若相等，则逐个比 较后续字符，否则，从主串第 2 个字符起重新和模式串第 基金项目:信息产业部软科学基金资助项目(2008-R-85,2008 -R-14), 重庆市教委科学技 术研究基金 资助项目 (KJ060514, KJ070512, 1 个字符比较。算法特点是简单易理解，但计算复杂度较大， KJ070515, KJ080523) 作者简介:万晓榆(1963,)，男，教授、博为 O(m×n)。 [2-3 ]士，主研方向:下一代网 KMP(Knuth M-orris-Pratt算法)在从左到右的扫描过程 络技术,杨 波，硕士研究生,樊自甫，讲师、硕士 中，正文不需要回朔，利用模式串部分匹配结果，将模式串 收稿日期:2008-11-13 E-mail:yangbuo@21cn.com 右移尽可能远的距离，继续进行比较。模式串不一定向右移 —125— 执行速度最快。但Sund a y 算法每次都是从首字符进行比较， 中出现:若没有出现，i=i+p_len+1,否则，i=i+p_len- pat[text[i +而首字符一般在整个字符串中出现的概率比较高，这样就增 p_len -pos]]+1。循环执行，直到整个主串匹配完成。算法实 加了算法进行无效匹配的次数，影响了字符串匹配的效率。 现如下: 针对 Sunda y 算法存在的缺陷，文本提出改进的Sund a y 算法。 for(size_it=po s;i 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 P 字符串中字符出现的位置: 式串中出现:如果出现，则将模式串移动 p_len-pat[text[ i+char pat[256]={0}; p_len- pos]]+，继续进行比较。1 for(size_tt=0 ;t=0) break; } 此处代码将得到 chk=”f”, pos=2。 5 结束语 (2)模式匹配算法 改进的 Sunday 算法在原算法的基础上增加了一个按字 在预处理阶段找到了特征字符ch k 及其位置 pos，然后对 符概率排序的字符串，用于在模式字符串中查找特征字符， 主串 T 中 i 位的字符 text[i]与匹配串 P 中的 pos 位进行比较， 在一定程度上减小了字符匹配的概率。实验结果表明，改进 并将模式串的尾字符t ext[i+p_len-pos-与1]主串进行比较，若 的算法在效率上有了一定程度的改进。因此，提高了入侵 检两者均匹配成功，则从左到右进行整个模式串的匹配。若整 测系统的处理速度，为进一步设计更高效的ID S 打下良好的 个字符串匹配成功，则说明已经在主串中找到模式串,若不 基础。 匹配，则判断主串中的第 i，p_len-pos 个字符是否在模式串 ,下转第 129 页, —126— 考虑安全机制所引入的时延开销，特别是对比分析不同的 安A, ps=32 210 B, ps=32 全 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 所引入的时延开销。其中，安全机制所引入的数据开 A, ps=128 B, ps=128180 销可从 2 个方面来体现:(1)增加额外的交互数据包,(2)将安 A, ps=256 B, ps=256 全信息附加到原有通信数据包中，影响每个数据包的大小。 150 s 通过上述 2 种安全协议的理论分析结果可以看出，在大量数 /m 120据传输时，安全机制引入的开销还是相当大的，特别是采 用 时延 影响每个数据包的安全协议时。 由于卫星网络用途广 平均90 泛，为卫星网络设计安全策略和选 择安全协议时须充分考虑实际应用情况。在传输如遥感遥测、 60 图像地图等 GB 级大数据量时，采用影响每个数据包尺寸的 30 安全协议将会产生很大的影响。在这种情形下，协议A 是最 1 2 3 4 5 数据包个数 好的选择。当然，由于其他因素的考虑，不得不选择可以 图 2 协议 A 和协议 B 的平均时延变化趋势 影 响每个数据包尺寸的安全协议时，应该选择影响最小的协议。 随着数据包数的增加，SPN 模型的规模呈指数增加，与 SPN 同构的马尔可夫链也呈指数增长，导致模型无法求得解。 6 结束语 本文采用 SPN 对 LEO 卫星网络的通信过程进行建模和 从图 2 中可看出，协议 A 和协议 B 中平均时延随数据包数大 仿真，针对 2 种安全协议——IKE/ISAKMP的野 蛮交换模式 致呈线性增长，因此，本文采用对特殊点进行采样的方法， 和 SCPS-SP，对比分析卫星网络的各种性能参数，为进一 步依据直线特征点进行协议的趋势外推，分别求出协议A、协 改进协议和增强安全性提供了思路。该建模仿真方法还可 以议 B 之间的大概交汇位置。 扩展到空间通信协议 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 (SCPS的其他)协议集中，从性能指 以数据包 ps=32 和 ps=256为例 ，取得采样点，可以大致 标开销角度对它们进行 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 和分析，为不同星座结构下卫星 推测出直线间交点，交点坐标体现了不同协议在平均时延方 网络的进一步性能优化提供了指导和参考。 面的性能对比参考点。 参考文献 采用 2 点式确定直线交点的方法，选取 p s=32 时，安全 [1] Ekici E, Chen Chao. BGP-S: A Protocol for Terrestrial and Satellite 协议平均时延变化趋势线的特征点: Network Integration in Network Layer[J]. Wireless Networks, 2004, 协议 A:(1, 96.291 8和)(5, 173.2484 ), 10(5): 595-605. 协议 B:(1, 39.410 5和)(5, 116.2710 )。 [2] 原菊梅, 侯朝桢, 王小艺, 等. 基于随机 Petri 网的可修系统可 用求得协议 A 所在直线与协议 B 所在直线间的交点坐标 性模糊评价[J]. 计算机工程, 2007, 33(8): 17-19. (-2 367.5879 , -45 454.087 5)，说明了协议A 对应的拟合直线 [3] Chang H S, Kim B W, Lee C G, et al. Topological Design and 斜率大于协议B 对应的拟合直线斜率，且随着数据包数的增 Routing for Low Earth Orbit Satellite Networks[C]//Proceedings of 加，协议 A 对应的拟合直线始终位于协议B 对应的拟合直线 GLOBECOM'95. Singapore: [s. n.], 1995. 上方。由于 3 次交互所产生的额外增量时延比较大，在这 种[4] Ereau J F, Saleman M. Modeling & Simulation of a Satellite 情况下，协议B 优于协议 A。 同理，Constellation Based on Petri Nets[C]//Proceedings of IEEE Annual 选取 ps=256 时的特征点: Reliability and Maintainability Symposium. Las Vegas, USA: [s. n.], 协议 A:(1, 117.588 9和)(5, 208.0261 ), 1996. 协议 B:(1, 60.758 1和)(5, 151.6338 )。 [5] Consultative Committee for Space Data Systems. CCSDS 713.5-B- 求得协议 A 所在直线与协议 B 所在直线间的交点坐标 1-1999 Space Communication Protocol Specification(SCPS)——(518.4109 , 11 838.497 5)?(5181,1 8 38)。在这种情况下，当每 Security Protocol[S]. 1999. 个安全联合的数据传送量较少时，特别是在兆级以下时，采 [6] Hirel C, Tuffin B, Trivedi K S. SPNP: Stochastic Petri 用协议 B 要略好于协议A ,当安全联合间的数据传送量一旦 Nets(V6.0)[C]//Proc. of International Conf. on Computer 69达到兆级(10)、吉级(10)时，采用协议 A 将明显优于协议B 。 Performance Evaluation: Modeling Tools and Techniques. 5.3 模型仿真结果分析 从安全策略设计和安全协议选择的Schaumburg, IL, USA: [s. n.], 2000. 角度来说，重点应该 编辑 顾姣健 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ,上接第 126 页, 参考文献 机工程与设计, 2008, 29(7): 1652-1654, 1683. [4] Sunday D M. A Very Fast Substring Search Algorithm[J]. [1] 曾慧惠, 袁世忠, 胡 鹏. 入侵检测系统中高效模式匹配算法的 Communications of ACM, 1990, 33(8): 132-142. 研究[J]. 计算机应用与软件, 2008, 25(4): 226-227. [2] 王 成, 刘金刚. 一种改进的字符串匹配算法[J]. 计算机工程, [5] 李贤平, 卞国瑞, 吴立鹏. 概率论与数理统计简明教程[M]. 北 2006, 32(2): 62-64. 京: 高等教育出版社, 1988. [3] 周延森, 汪永好. 网络入侵检测系统模式匹配算法研究[J]. 计算编辑 张 帆 —129—