面向深度數(shù)據(jù)包檢測(cè)的正則表達(dá)式匹配算法研究.pdf

1、隨著科技的發(fā)展，網(wǎng)絡(luò)應(yīng)用層出不窮，各種攻擊也日益猖獗，給網(wǎng)絡(luò)信息安全帶來了嚴(yán)重威脅。深度數(shù)據(jù)包檢測(cè)(Deep Packet Inspection，DPI)是網(wǎng)絡(luò)入侵檢測(cè)與防御系統(tǒng)(Network Intrusion Detection/Prevention System，NIDS/NIPS)的核心，常用正則表達(dá)式來描述攻擊規(guī)則的特征，不僅檢查數(shù)據(jù)包的頭部也檢查數(shù)據(jù)包的有效載荷。正則表達(dá)式匹配(Regular Expression Mat

2、ching，REM)是DPI的主要組成部分。傳統(tǒng)的正則表達(dá)式匹配算法常采用非確定有限自動(dòng)機(jī)(NondeterministicFinite Automaton，NFA)和確定有限自動(dòng)機(jī)(Deterministic Finite Automaton，DFA)來實(shí)現(xiàn)。NFA存儲(chǔ)空間需求小，但帶寬需求大；而DFA帶寬需求小，但存儲(chǔ)空間大。因此構(gòu)建時(shí)空高效的正則表達(dá)式匹配算法成為當(dāng)前深度數(shù)據(jù)包檢測(cè)的研究熱點(diǎn)之一。
　　為了對(duì)DFA的存儲(chǔ)空間

3、進(jìn)行有效的壓縮，本文提出一個(gè)簡(jiǎn)單新穎的基于行程累加長(zhǎng)度壓縮的正則表達(dá)式匹配算法(Run Accumulation Length Encoding DFA，RALE-DFA)。該算法引入正則表達(dá)式集的出現(xiàn)字符集對(duì)字母表進(jìn)行壓縮，并利用RALE算法對(duì)字母壓縮遷移表進(jìn)行進(jìn)一步壓縮，同時(shí)位圖被用來加快匹配過程。實(shí)驗(yàn)結(jié)果表明，RALE-DFA算法有效的減少了DFA的存儲(chǔ)空間開銷。與原始DFA算法、CSDFA(Character Substitut

4、ion DFA)算法和D2FA(Delayed Input DFA，D2FA)算法相比，RALE-DFA算法的存儲(chǔ)空間開銷分別減少了95.81％～98.56％、48.17％～73.34％和38.09％～76.15％。
　　在某些情況下，正則表達(dá)式中包含長(zhǎng)度限制子表達(dá)式會(huì)導(dǎo)致DFA狀態(tài)爆炸，并使得DFA無(wú)法構(gòu)建。為解決長(zhǎng)度限制帶來的問題，本文在計(jì)數(shù)自動(dòng)機(jī)(CountingFA，Counting-FA)的基礎(chǔ)上提出了跳躍計(jì)數(shù)自動(dòng)機(jī)(J