并行串匹配算法研究

《并行串匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、哈尔滨工业大学工学硕士学位论文第1章绪论字符串匹配问题由来已久，最简单的例子就是从文本集合中找出给定的字符串。随着信息技术的蓬勃发展，网络流量的快速增长，防火墙和网络入侵检系统等网络安全设备需要处理的数据越来越大。而传统的以串行方式执行的串匹配算法的处理能力不足以应对高速的网络环境，提高串匹配算法的性能迫在眉睫，以并行代替串行成为提高串匹配算法性能的有效方式之一。因此，并行串匹配算法成为了研究的热点。本文旨在研究并行串匹配算法，使之适用于大规模网络内容的检测。1.1课题背景及研究目的和意义随着网络的普及和发展，特别是移动互联网的

2、兴起，需要处理的网络流量不断增长，同时网络上潜在的安全隐患越来越严重，如何快速高效地处理大规模数据是网络安全领域亟需解决的问题之一，因此对网络内容的检测尤为重要。而字符串匹配算法正是网络内容检测的核心技术，如何提高串匹配算法的性能成为了当前网络安全领域研究的重点。目前，即时通讯已经成为我国使用最广泛的上网应用，用户使用率不断攀升，同时电子商务类应用快速发展，淘宝、京东、亚马逊等网络购物的用户规模不断增长。2014年的中国互联网络发展状况统计报告[1]中指出，2013年12月，我国的国际出口带宽为3406824Mbps，年增长率达

3、到79.3%，IPv4地址总量达到3.3亿，拥有域名总数1844万个。通过以上的直观数据，可见我国网络数据的增长之快，不仅我国，全球的网络数据流量正在以指数级的速度增长，在移动互联网的推动下，无线数据的增长尤其迅猛。思科在2014年2月公布的《视觉网络指数》中指出，2013年的全球移动数据流量增长了81%，其中，仅无线数据流量就有18艾字节，而在2000年，全球所有的互联网流量的总和仅仅为1艾字节。也就是说，仅2013年这一年的无线数据流量相当于2000年全球互联网流量的18倍。随着计算机网络和移动互联网的发展，系统需要实时处理

4、的数据规模越来越大，给信息安全系统带来了严峻的挑战，急需高性能的串匹配算法的支持。随着网络的迅猛发展，病毒也在迅速的繁殖和传播，网络安全隐患日渐暴露。根据2014年网络安全信息与动态周报[2]的信息，2014年4月7日至2014年4月13日，仅这一周的时间内，我国境内感染网络病毒的主机数量大约101.9万个，被篡改网站数量为8124个。可想而知，每时每刻网络中都存在病毒的攻击，这些病毒大多隐藏在某些非法网页中，可能用户打开就某个植入病毒的网页，计算机即被-1-万方数据哈尔滨工业大学工学硕士学位论文感染。因此在网络流量如此巨大的今

5、天，对网络数据内容的检测尤为重要。如何有效地防止网络病毒的攻击已经成为了目前信息安全领域的主要研究问题之一。尤其是目前移动互联网盛行，移动操作系统Android、苹果，无线业务等都缺乏完善的网络安全系统，开发高性能的网络入侵检测系统[3]起到了举足轻重的作用。网络入侵检测系统通过收集和分析互联网关键点上的数据内容，检查网络中是否存在攻击现象或者有悖安全策略的行为。Snort检测系统[3]作为目前流行的一款开源的网络入侵检测系统，其检测的原理就是多模式匹配技术，通过对每个网络数据包在规则集合内进行字符串匹配技术，搜索并检测出恶意的

6、攻击行为，保障网络的安全运行。随着电子商务的兴起和普及，出现了“钓鱼网站”等问题。“钓鱼网站”把自己伪装成银行或者电子商务的网络主页，窃取用户的私人信息，如银行账号、身份证号和密码等，从而进行欺诈或者骗钱等不法行为。“钓鱼网站”网址往往与真实网络地址相似，但存在细微的差别，如果用户不留意，便难以区分，导致消费者上当受骗，采用字符串匹配技术即可解决该问题。收集已知的“钓鱼网站”的URL地址并将其创建为数据库，每当用户访问一个网络地址，计算机自动与数据库中的URL地址进行匹配，查询是否是“钓鱼网站”。通过以上的字符串匹配技术，可以很

7、好的解决“钓鱼网站”问题。随着互联网和硬件技术的不断发展，传统的串匹配技术已经不能满足高速网络的处理需求。一方面，网络安全系统需要实时处理的数据越来越大，需要强大的计算能力。另一方面，模式集合早已超过了成千上万的规模，面对如此巨大的模式集，需要更多的内存存储空间，硬件的支持是必不可少的。经典传统的以串行方式执行的模式匹配算法的性能难以提高，为适应于当前高速多变的网络环境，迫切地需要拥有强大计算能力以及更大存储空间的高性能算法。许多串匹配算法被开发出来，在实践中获得了亚线性的性能。这些算法中，Boyer-Moore[4]算法值得特

8、别提出，因其激发了后续的研究工作。最有效的基于比较的算法，不得不提的是著名的Horspool[5]和Quick-Search[6]算法，虽然它们最坏时间复杂性达到了平方级，但是在实际应用中展现出了亚线性的性能。基于自动机的解决方案也已开发设计，且具有最佳的平均线