網(wǎng)絡(luò)數(shù)據(jù)流的正則表達(dá)式匹配技術(shù)研究.pdf

1、正則表達(dá)式是一種包含普通字符和通配符的模式串，它具有很靈活的的表達(dá)能力，其豐富的語(yǔ)義和強(qiáng)大的表達(dá)能力賦予了它對(duì)各種特征有效的描述能力，也就是具有這樣的能力使得正則表達(dá)式匹配技術(shù)占據(jù)了網(wǎng)絡(luò)內(nèi)容過(guò)濾分析系統(tǒng)和網(wǎng)絡(luò)入侵監(jiān)測(cè)系統(tǒng)中的核心地位。隨著互聯(lián)網(wǎng)的快速發(fā)展，尤其是移動(dòng)互聯(lián)網(wǎng)的崛起，新型網(wǎng)絡(luò)應(yīng)用的井噴，網(wǎng)絡(luò)信息量呈指數(shù)級(jí)增長(zhǎng)，帶來(lái)了待檢測(cè)數(shù)據(jù)量以及正則表達(dá)式的規(guī)則數(shù)目的急增，這對(duì)正則表達(dá)式匹配技術(shù)的匹配性能提出了巨大的挑戰(zhàn)。國(guó)內(nèi)外的研究者目

2、前對(duì)正則表達(dá)式匹配技術(shù)的研究工作主要集中在將其轉(zhuǎn)化為自動(dòng)機(jī)進(jìn)行匹配時(shí)的匹配效率和空間存儲(chǔ)兩方面。本文選擇正則表達(dá)式匹配算法的匹配效率作為研究方向進(jìn)行了一系列的研究，主要的研究工作可以分為以下的兩個(gè)部分：
　　研究了空間高效，時(shí)間低效的非確定型自動(dòng)機(jī)（NFA）匹配算法，對(duì)基于Glushkov構(gòu)造方法的NFA進(jìn)行改進(jìn)，提出了基于激活狀態(tài)過(guò)濾的正則表達(dá)式匹配算法，通過(guò)多加載一個(gè)待匹配字符進(jìn)入自動(dòng)機(jī)從而降低激活狀態(tài)集的大小，減少驗(yàn)證次數(shù)的

3、方式來(lái)提升基于Glushkov NFA的正則表達(dá)式匹配算法的匹配效率。
　　研究了正則表達(dá)式的結(jié)構(gòu)以及實(shí)際互聯(lián)網(wǎng)中目標(biāo)數(shù)據(jù)的分布情況和基于后綴搜索的字符串匹配算法，提出了基于預(yù)檢的正則表達(dá)式匹配算法。因?yàn)閷?shí)際互聯(lián)網(wǎng)數(shù)據(jù)中目標(biāo)數(shù)據(jù)只占有很少的比例，很多都是不相關(guān)數(shù)據(jù)，原始的正則表達(dá)式匹配算法依次對(duì)待匹配數(shù)據(jù)全部進(jìn)行匹配從而降低了匹配的效率。本文提出的算法通過(guò)從正則表達(dá)式中提取確定字符串，使用具有跳躍特性的基于后綴搜索的字符串匹配算法