基于子圖同構(gòu)的XFA壓縮算法設(shè)計(jì).pdf

1、網(wǎng)絡(luò)入侵檢測(cè)與防御(Network Intrusion Detection/Prevention，NIDP)是信息安全領(lǐng)域一個(gè)重要的技術(shù)手段。NIDP的基本原理是預(yù)先制定一定的安全策略，并將安全策略與其檢測(cè)到的內(nèi)容進(jìn)行匹配，如果檢測(cè)到安全策略不允許的內(nèi)容，則攔截或作其他處理。而深度包檢測(cè)(Deep Packet Inspection，DPI)是實(shí)現(xiàn)NIDP的重要技術(shù)。由于正則表達(dá)式靈活、高效的特點(diǎn)，其常用于網(wǎng)絡(luò)安全的DPI。傳統(tǒng)的正則表

2、達(dá)式匹配算法實(shí)現(xiàn)方式主要基于非確定有限自動(dòng)機(jī)(NFA，Nondeterministic Finite Automaton)和確定有限自動(dòng)機(jī)(DFA，Deterministic FiniteAutomaton)。
　　上述兩種實(shí)現(xiàn)方式在匹配效率和存儲(chǔ)空間優(yōu)化上很難兼得。NFA所需存儲(chǔ)空間很小但是匹配速度很慢;DFA由于匹配速度很快使得DFA方法成為了實(shí)現(xiàn)正則表達(dá)式匹配的普遍選擇，但DFA的高匹配速度是以可呈指數(shù)膨脹的狀態(tài)空間為代價(jià)的

3、。最近研究者們提出了擴(kuò)展有限自動(dòng)機(jī)(Extended Finite Automata，XFA)，XFA的主要思想是在某些狀態(tài)后附加一些額外的指令，對(duì)DFA實(shí)現(xiàn)壓縮。附加的指令有寄存器置位復(fù)位、計(jì)數(shù)器累加復(fù)位等操作。針對(duì)一些包含通配符“.*”的數(shù)據(jù)具有很大的優(yōu)化作用。
　　本文在分析傳統(tǒng)正則表達(dá)式匹配算法NFA和DFA無(wú)法滿足高性能需求的原因的基礎(chǔ)上，試圖進(jìn)一步優(yōu)化XFA。根據(jù)對(duì)于實(shí)際正則表達(dá)式數(shù)據(jù)集的研究，通過(guò)其生成的XFA當(dāng)中會(huì)

4、包含很多相似的結(jié)構(gòu)。本文嘗試?yán)米訄D同構(gòu)的原理，提出將XFA進(jìn)行分塊處理后，對(duì)其進(jìn)行合理的編碼，從而進(jìn)一步存儲(chǔ)壓縮存儲(chǔ)空間，提升吞吐量。
　　文中以星形結(jié)構(gòu)為例，使用通過(guò)開(kāi)源正則表達(dá)式工具regex轉(zhuǎn)換得到的數(shù)據(jù)，進(jìn)行了三態(tài)內(nèi)容可尋址存儲(chǔ)器(Ternary Content Addressable Memory，TCAM)的仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本方法對(duì)于一些數(shù)據(jù)集可以將存儲(chǔ)空間壓縮至26.8％，而相同存儲(chǔ)量的吞吐量則提高到2.6