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

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

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

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

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