深入淺出 Hyperscan：高性能正則表達式算法原理與設(shè)計

目　　錄
第 1章　正則表達式簡介 1
1．1　正則表達式的語法 1
1．2　正則表達式的流派與標準 7
1．2．1 PCRE簡介 7
1．2．2 POSIX標準 8
1．3　本章參考 10
第 2章　正則表達式匹配算法 11
2．1　純字符串匹配 11
2．1．1 單字符串匹配KMP算法 11
2．1．2 單字符串匹配BM算法 16
2．1．3 多字符串匹配AC算法 21
2．1．4 AC算法與單字符串匹配 24
2．1．5 SHIFT-OR算法 25
2．2　非確定性有限狀態(tài)自動機 28
2．2．1 定義 28
2．2．2 運算優(yōu)先級 29
2．2．3 Thompson構(gòu)造法 31
2．2．4 ε-NFA的簡化 34
2．2．5 Glushkov構(gòu)造法 36
2．3　確定性有限狀態(tài)自動機 40
2．3．1 定義 40
2．3．2 從NFA到DFA 40
2．3．3 DFA的狀態(tài)規(guī)模 46
2．3．4 DFA的狀態(tài)最小化 52
2．4　本章參考 55
第3章　正則表達式匹配庫 56
3．1　PCRE 56
3．1．1 語法支持 56
3．1．2 設(shè)計概述 57
3．1．3 基本API和示例代碼 58
3．2　RE2 60
3．2．1 語法支持 60
3．2．2 設(shè)計概述 60
3．2．3 基本API和示例代碼 60
3．3　Hyperscan 61
3．3．1 語法支持 61
3．3．2 匹配模式 62
3．3．3 設(shè)計概述 63
3．3．4 基本API和示例代碼 64
3．4　正則表達式匹配庫的比較 65
3．4．1 概述 65
3．4．2 語法支持 65
3．4．3 設(shè)計原理 66
3．4．4 性能 68
3．5　本章參考 70
第4章　Hyperscan特性 71
4．1　Hyperscan的語義 71
4．2　編譯期和運行期 71
4．2．1 編譯期 72
4．2．2 運行期 74
4．3　Hyperscan高級特性 77
4．3．1 流狀態(tài)壓縮 77
4．3．2 近似匹配 78
4．3．3 邏輯組合 79
4．3．4 Chimera 80
4．4　Hyperscan工具 82
4．4．1 hsbench 82
4．4．2 hscheck 84
4．4．3 hscollider 85
4．4．4 hsdump 88
第5章　Hyperscan設(shè)計原理 92
5．1　設(shè)計原則 92
5．1．1 實用性優(yōu)先 92
5．1．2 極端情況可用 93
5．1．3 流模式支持 93
5．1．4 大規(guī)?？蓴U展 93
5．1．5 小規(guī)模高性能 94
5．1．6 性能優(yōu)先 94
5．1．7 平衡開銷 94
5．1．8 漸進主義 95
5．1．9 可測試性設(shè)計和自動可測試性設(shè)計 96
5．2　運行原理 96
5．2．1 匹配組件 97
5．2．2 匹配原則 100
5．2．3 運行期實現(xiàn) 103
5．2．4 運行期優(yōu)化 108
5．3　圖分解 112
5．3．1 支配路徑分析 114
5．3．2 支配區(qū)域分析 115
5．3．3 網(wǎng)絡(luò)流分析 116
5．3．4 圖分解流程 117
5．4　圖優(yōu)化 122
5．4．1 節(jié)點冗余 123
5．4．2 邊冗余 129
5．5　本章參考 132
第6章　Hyperscan引擎 133
6．1　SIMD加速 133
6．1．1 搜索單字符的加速 133
6．1．2 搜索雙字符序列的加速 134
6．1．3 搜索小規(guī)模單字符集的加速 136
6．1．4 搜索大規(guī)模單字符集的加速 140
6．1．5 環(huán)視機制 143
6．2　純字符串匹配 148
6．2．1 純字符串匹配在Hyperscan中的作用 148
6．2．2 單字符串匹配器“Noodle” 148
6．2．3 大規(guī)模多字符串匹配器“FDR” 150
6．2．4 小規(guī)模多字符串匹配器“Teddy” 156
6．3　正則引擎 160
6．3．1 NFA引擎 160
6．3．2 DFA引擎 168
6．3．3 重復(fù)引擎 186
6．3．4 Tamarama 197
第7章　Hyperscan性能優(yōu)化 199
7．1　Hyperscan性能測試 199
7．1．1 性能測試目的 199
7．1．2 基于性能的硬件和GRUB配置 199
7．1．3 hsbench測試 201
7．2　Hyperscan性能調(diào)優(yōu)技巧 205
7．2．1 正則表達式構(gòu)造 206
7．2．2 軟件庫的使用 207
7．2．3 塊模式 207
7．2．4 數(shù)據(jù)庫分配 209
7．2．5 scratch內(nèi)存分配 209
7．2．6 錨定規(guī)則 211
7．2．7 隨處匹配的規(guī)則 212
7．2．8 流模式下的重復(fù)語義 213
7．2．9 青睞字符串 214
7．2．10 DOTALL標志 215
7．2．11 單次匹配標志 216
7．2．12 Start of Match標志 217
7．2．13 近似匹配 218
第8章　Hyperscan實際案例學習 221
8．1　Snort 221
8．1．1 介紹 221
8．1．2 Hyperscan集成 222
8．1．3 基于內(nèi)存的性能測試 225
8．2　Suricata 229
8．2．1 介紹 229
8．2．2 Hyperscan集成 229
8．2．3 基于內(nèi)存的性能測試 234
8．3　垃圾郵件檢測 238
8．4　深度報文檢測 242
8．4．1 nDPI 242
8．4．2 UDPI 245
8．5　數(shù)據(jù)庫 247
8．5．1 整合概述 248
8．5．2 實驗結(jié)果與分析 250
8．6　Web應(yīng)用防火墻 254