并行串匹配算法研究

《并行串匹配算法研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文第1章緒論字符串匹配問題由來已久，最簡單的例子就是從文本集合中找出給定的字符串。隨著信息技術(shù)的蓬勃發(fā)展，網(wǎng)絡(luò)流量的快速增長，防火墻和網(wǎng)絡(luò)入侵檢系統(tǒng)等網(wǎng)絡(luò)安全設(shè)備需要處理的數(shù)據(jù)越來越大。而傳統(tǒng)的以串行方式執(zhí)行的串匹配算法的處理能力不足以應(yīng)對高速的網(wǎng)絡(luò)環(huán)境，提高串匹配算法的性能迫在眉睫，以并行代替串行成為提高串匹配算法性能的有效方式之一。因此，并行串匹配算法成為了研究的熱點(diǎn)。本文旨在研究并行串匹配算法，使之適用于大規(guī)模網(wǎng)絡(luò)內(nèi)容的檢測。1.1課題背景及研究目的和意義隨著網(wǎng)絡(luò)的普及和發(fā)展，特別是移動互聯(lián)網(wǎng)的

2、興起，需要處理的網(wǎng)絡(luò)流量不斷增長，同時(shí)網(wǎng)絡(luò)上潛在的安全隱患越來越嚴(yán)重，如何快速高效地處理大規(guī)模數(shù)據(jù)是網(wǎng)絡(luò)安全領(lǐng)域亟需解決的問題之一，因此對網(wǎng)絡(luò)內(nèi)容的檢測尤為重要。而字符串匹配算法正是網(wǎng)絡(luò)內(nèi)容檢測的核心技術(shù)，如何提高串匹配算法的性能成為了當(dāng)前網(wǎng)絡(luò)安全領(lǐng)域研究的重點(diǎn)。目前，即時(shí)通訊已經(jīng)成為我國使用最廣泛的上網(wǎng)應(yīng)用，用戶使用率不斷攀升，同時(shí)電子商務(wù)類應(yīng)用快速發(fā)展，淘寶、京東、亞馬遜等網(wǎng)絡(luò)購物的用戶規(guī)模不斷增長。2014年的中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[1]中指出，2013年12月，我國的國際出口帶寬為3406824Mbps，年增長率達(dá)

3、到79.3%，IPv4地址總量達(dá)到3.3億，擁有域名總數(shù)1844萬個(gè)。通過以上的直觀數(shù)據(jù)，可見我國網(wǎng)絡(luò)數(shù)據(jù)的增長之快，不僅我國，全球的網(wǎng)絡(luò)數(shù)據(jù)流量正在以指數(shù)級的速度增長，在移動互聯(lián)網(wǎng)的推動下，無線數(shù)據(jù)的增長尤其迅猛。思科在2014年2月公布的《視覺網(wǎng)絡(luò)指數(shù)》中指出，2013年的全球移動數(shù)據(jù)流量增長了81%，其中，僅無線數(shù)據(jù)流量就有18艾字節(jié)，而在2000年，全球所有的互聯(lián)網(wǎng)流量的總和僅僅為1艾字節(jié)。也就是說，僅2013年這一年的無線數(shù)據(jù)流量相當(dāng)于2000年全球互聯(lián)網(wǎng)流量的18倍。隨著計(jì)算機(jī)網(wǎng)絡(luò)和移動互聯(lián)網(wǎng)的發(fā)展，系統(tǒng)需要實(shí)時(shí)處理

4、的數(shù)據(jù)規(guī)模越來越大，給信息安全系統(tǒng)帶來了嚴(yán)峻的挑戰(zhàn)，急需高性能的串匹配算法的支持。隨著網(wǎng)絡(luò)的迅猛發(fā)展，病毒也在迅速的繁殖和傳播，網(wǎng)絡(luò)安全隱患日漸暴露。根據(jù)2014年網(wǎng)絡(luò)安全信息與動態(tài)周報(bào)[2]的信息，2014年4月7日至2014年4月13日，僅這一周的時(shí)間內(nèi)，我國境內(nèi)感染網(wǎng)絡(luò)病毒的主機(jī)數(shù)量大約101.9萬個(gè)，被篡改網(wǎng)站數(shù)量為8124個(gè)?？上攵?，每時(shí)每刻網(wǎng)絡(luò)中都存在病毒的攻擊，這些病毒大多隱藏在某些非法網(wǎng)頁中，可能用戶打開就某個(gè)植入病毒的網(wǎng)頁，計(jì)算機(jī)即被-1-萬方數(shù)據(jù)哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文感染。因此在網(wǎng)絡(luò)流量如此巨大的今

5、天，對網(wǎng)絡(luò)數(shù)據(jù)內(nèi)容的檢測尤為重要。如何有效地防止網(wǎng)絡(luò)病毒的攻擊已經(jīng)成為了目前信息安全領(lǐng)域的主要研究問題之一。尤其是目前移動互聯(lián)網(wǎng)盛行，移動操作系統(tǒng)Android、蘋果，無線業(yè)務(wù)等都缺乏完善的網(wǎng)絡(luò)安全系統(tǒng)，開發(fā)高性能的網(wǎng)絡(luò)入侵檢測系統(tǒng)[3]起到了舉足輕重的作用。網(wǎng)絡(luò)入侵檢測系統(tǒng)通過收集和分析互聯(lián)網(wǎng)關(guān)鍵點(diǎn)上的數(shù)據(jù)內(nèi)容，檢查網(wǎng)絡(luò)中是否存在攻擊現(xiàn)象或者有悖安全策略的行為。Snort檢測系統(tǒng)[3]作為目前流行的一款開源的網(wǎng)絡(luò)入侵檢測系統(tǒng)，其檢測的原理就是多模式匹配技術(shù)，通過對每個(gè)網(wǎng)絡(luò)數(shù)據(jù)包在規(guī)則集合內(nèi)進(jìn)行字符串匹配技術(shù)，搜索并檢測出惡意的

6、攻擊行為，保障網(wǎng)絡(luò)的安全運(yùn)行。隨著電子商務(wù)的興起和普及，出現(xiàn)了“釣魚網(wǎng)站”等問題?！搬烎~網(wǎng)站”把自己偽裝成銀行或者電子商務(wù)的網(wǎng)絡(luò)主頁，竊取用戶的私人信息，如銀行賬號、身份證號和密碼等，從而進(jìn)行欺詐或者騙錢等不法行為?！搬烎~網(wǎng)站”網(wǎng)址往往與真實(shí)網(wǎng)絡(luò)地址相似，但存在細(xì)微的差別，如果用戶不留意，便難以區(qū)分，導(dǎo)致消費(fèi)者上當(dāng)受騙，采用字符串匹配技術(shù)即可解決該問題。收集已知的“釣魚網(wǎng)站”的URL地址并將其創(chuàng)建為數(shù)據(jù)庫，每當(dāng)用戶訪問一個(gè)網(wǎng)絡(luò)地址，計(jì)算機(jī)自動與數(shù)據(jù)庫中的URL地址進(jìn)行匹配，查詢是否是“釣魚網(wǎng)站”。通過以上的字符串匹配技術(shù)，可以很

7、好的解決“釣魚網(wǎng)站”問題。隨著互聯(lián)網(wǎng)和硬件技術(shù)的不斷發(fā)展，傳統(tǒng)的串匹配技術(shù)已經(jīng)不能滿足高速網(wǎng)絡(luò)的處理需求。一方面，網(wǎng)絡(luò)安全系統(tǒng)需要實(shí)時(shí)處理的數(shù)據(jù)越來越大，需要強(qiáng)大的計(jì)算能力。另一方面，模式集合早已超過了成千上萬的規(guī)模，面對如此巨大的模式集，需要更多的內(nèi)存存儲空間，硬件的支持是必不可少的。經(jīng)典傳統(tǒng)的以串行方式執(zhí)行的模式匹配算法的性能難以提高，為適應(yīng)于當(dāng)前高速多變的網(wǎng)絡(luò)環(huán)境，迫切地需要擁有強(qiáng)大計(jì)算能力以及更大存儲空間的高性能算法。許多串匹配算法被開發(fā)出來，在實(shí)踐中獲得了亞線性的性能。這些算法中，Boyer-Moore[4]算法值得特

8、別提出，因其激發(fā)了后續(xù)的研究工作。最有效的基于比較的算法，不得不提的是著名的Horspool[5]和Quick-Search[6]算法，雖然它們最壞時(shí)間復(fù)雜性達(dá)到了平方級，但是在實(shí)際應(yīng)用中展現(xiàn)出了亞線性的性能?；谧詣訖C(jī)的解決方案也已開發(fā)設(shè)計(jì)，且具有最佳的平均線