河南科技大学硕士学位论文入侵检测匹配过程与算法改进研究姓名：吕东伟申请学位级别：硕士专业：计算机应用技术指导教师：孟庆端;梁祖华20091201摘 要 论文题目：入侵检测匹配过程与算法改进研究 论文题目：入侵检测匹配过程与算法改进研究 专 业：计算机应用技术 专 业：计算机应用技术 研 究 生：吕东伟 研 究 生：吕东伟 指导教师：孟庆端 副教授 梁祖华 高级工程师 指导教师：孟庆端 副教授 梁祖华 高级工程师 摘 要 摘 要 网络的普及和广泛应用极大地方便了人们的日常工作和生活，与此同时各种网络攻击和网络犯罪活动也日益严重，网络的安全问题就显得尤为重要入侵检测技术作为一种能主动探测攻击、保护信息系统不被破坏的网络技术被广泛应用 Snort 是一典型的开源入侵检测系统，具有对网络流量进行实时分析、对网络数据包进行记录、对协议进行分析和对数据包内容进行搜索匹配等多种功能。
但随着网络带宽的不断提高，Snort 需要处理的网络流量日益增大，这就对 Snort的检测速度提出了更高的要求 本文系统分析了 Snort 的规则结构、检测流程和快速规则匹配引擎构建过程，提出了按规则中包含模式串的个数对规则进行分类的思路对仅包含单个模式串的规则，借助多模式匹配所得信息，用边界条件检查函数代替单模式重复匹配过程，使 Snort 入侵检测系统的检测速度提高了 1.28%另外分析研究了现有模式匹配算法的优缺点，提出了一种改进的 AC_BMH 多模式匹配算法改进算法利用双字符进行跳跃，在增大模式串失配概率的同时能跳过更大的距离，再结合 QS 算法的优点，进一步增大模式串匹配失败时的跳跃距离，同时借助压缩存储机制有效降低了算法的内存使用量在 VC6.0 环境下对改进算法的匹配速度和内存使用量进行了测试，测试结果表明该算法比原算法在模式匹配速度上提高了 29.30%-52.82%，在模式串较多时，内存使用量可减少 90%以上最后将该算法应用到 Snort 入侵检测系统中，使 Snort 入侵检测系统的检测速度提高了5.95%-25.54% 关 键 词：关 键 词：入侵检测，模式匹配，Snort，AC_BMH 算法 论文类型：论文类型：应用研究 摘要 IISubject: Research on Matching Process and Algorithm Improvement of Intrusion Detection Specialty: Technology of Computer Application Name: LV Dongwei Supervisor: Associate Professor Meng Qingduan Senior Engineer Liang Zuhua ABSTRACT Popularization of the Internet and the wide application of computer network bring great convenience to people's work and daily life. At the same time, various network attacks and network crimes have been increasing sharply. Protecting network security against hacker attacks is becoming more important. Intrusion detection, as a kind of network technology which can detect attack actively and protect information system against destroying, has been used widely. Snort is a typical open source intrusion detection system. It has multiple functions including traffic analysis, log network data package, protocol analysis, search content in the network data package, etc. As the increase of network broadband, snort has to deal with more and more network flow in unit time. To cope with the challenge of high-speed network, snort must be improved to have a faster detection speed. Firstly, this thesis analyses snort’s rule structure, detection process, the established process of fast rule matching engine, and then a rule classification ideas is proposed, which classifies the rules basing on the number of pattern strings contained in the rules. For the rules containing only one pattern string, the single pattern matching employed repeatedly in the matching process is replaced by a function detecting the boundary conditions, which is got from multiple patterns matching process executed previously. Experiment results show that the detection speed of snort intrusion detection system is improved by 1.28% by using the proposed method. After that, by analyzing the advantage and shortage of general pattern matching algorithm, an improved AC_BMH (Aho-Corasick_Boyer-Moore-Horspool) is proposed in this thesis. The improved AC_BMH algorithm utilizes double-character skip for both larger pattern strings mismatching possibility and further jumping distance, furthermore, combines advantages of QS (Quick Search) algorithm for even longer jumping distance when pattern strings matching fails, at the same time, employs 摘要 IIIcompact storage mechanism to decrease the amount of memory usage. A test was made on algorithm’s matching speed and memory usage using VC6.0. The test results show that the matching speed of pattern matching is improved about 29.30%-52.82% by using the proposed algorithm, and the amount of memory used reduces about 90% when many pattern strings existed. Finally, the improved algorithm was used to snort intrusion detection system. Experiment results show that the detection speed of snort intrusion detection system is improved by 5.95%-25.54% by using the improved algorithm. KEY WORDS: Intrusion Detection, Pattern Matching, Snort, AC_BMH Algorithm Dissertation Type: Application Research 第 1 章 绪论 1第1章 绪论 第1章 绪论 1.1 研究背景研究背景 随着网络信息技术的飞速发展，在第五次信息化革命浪潮的推动下，Internet 已经渗透到人类社会的各个领域，并逐渐成为人们日常生活中的一部分。
据中国互联网络信息中心(CNNIC)发布的《第 23 次中国互联网发展状况统计报告》[1]显示：截至 2008 年 12 月，中国互联网网民规模达到 2.98 亿人，跃居世界第一，较 2007 年增长 8800 万人，年增长率为 41.90%，其中 18.60%的网民通过网络进行求职，24.80%的网民通过网络进行购物，56.80%的网民通过网络发送电子邮件，67.70%的网民通过网络观看视频文件，78.50%的网民通过网络浏览新闻可以说网络正改变着我们工作和生活方式 网络就像一把双刃剑，在给人们带来诸多便利的同时，网络安全作为一个无法回避的问题也逐渐凸显出来据公安部公布的《2008 年全国信息网络安全状况与计算机病毒疫情调查分析报告》[2]显示：2007 年 5 月至 2008 年 5 月，62.70%的被调查单位发生过信息网络安全事件，感染计算机病毒、蠕虫和木马的情况尤为突出，其次是网络攻击、端口扫描、垃圾邮件和网页篡改在发生的安全事件中，攻击或传播涉及内部人员的达到 54%，比去年激增了 15%，未修补的软件漏洞仍然是导致安全事件发生的主要原因随着当前系统漏洞、软件漏洞和网络漏洞被发现的速度加快，攻击爆发时间变短，据国家反计算机入侵和防病毒研究中心发布的《我国信息网络安全状况和发展趋势》[3]显示：在所有新攻击方法中，64%的攻击是针对一年之内发现的漏洞，最短的大规模攻击距相应漏洞被公布的时间仅为 28 天。
同时攻击者所需的技术水平逐渐降低，攻击手段更加灵活，联合攻击急剧增多，而且很多攻击工具易于从网络下载 当前企业内部系统的联系越来越紧密，而且数据的价值也越来越高，导致来自内部的攻击有逐年增多的趋势，2004 年至 2006 年这个比例是 8%，2007 年下降为 5%，而 2008 年则激增至 23%同时各个利益集团为谋取利益，利用黑客工具。