深入淺出 Hyperscan：高性能正則表達(dá)式算法原理與設(shè)計(jì)
《深入淺出 Hyperscan：高性能正則表達(dá)式算法原理與設(shè)計(jì)》系統(tǒng)、循序漸進(jìn)地介紹Hyperscan技術(shù)。全書(shū)共8章，主要介紹正則表達(dá)式、匹配算法和正則表達(dá)式匹配所依賴的自動(dòng)機(jī)原理、正則表達(dá)式匹配庫(kù)等，并重點(diǎn)介紹Hyperscan的功能特性、設(shè)計(jì)原理和性能調(diào)優(yōu)技巧，以及匹配引擎的核心算法和SIMD加速技術(shù)的運(yùn)用，還展示了Hyperscan多樣化的應(yīng)用場(chǎng)景。
《深入淺出 Hyperscan：高性能正則表達(dá)式算法原理與設(shè)計(jì)》既適合作為Hyperscan開(kāi)發(fā)者的學(xué)習(xí)用書(shū)，也適合作為高等院校計(jì)算機(jī)相關(guān)專業(yè)的師生用書(shū)和相關(guān)培訓(xùn)學(xué)校的教材。
1.由淺入深介紹正則表達(dá)式相關(guān)知識(shí)、Hyperscan算法庫(kù)功能特性及總體設(shè)計(jì)原則
2.偽碼源碼相輔相成，方便讀者學(xué)習(xí)基礎(chǔ)算法及實(shí)現(xiàn)步驟
3.算法實(shí)例搭配圖例表格，加深讀者對(duì)算法的理解
4.理論與實(shí)踐兼收并重學(xué)習(xí)Hyperscan與開(kāi)源產(chǎn)品整合案例分析
王翔，英特爾數(shù)據(jù)中心網(wǎng)絡(luò)平臺(tái)部資深工程師，Hyperscan 項(xiàng)目主要技術(shù)負(fù)責(zé)人。昌昊，英特爾資深軟件工程師,負(fù)責(zé)Hyperscan算法開(kāi)發(fā)和性能調(diào)優(yōu)等相關(guān)工作。洪楊，英特爾資深軟件工程師,負(fù)責(zé) Hyperscan研發(fā)。張磊，英特爾網(wǎng)絡(luò)平臺(tái)部門(mén)軟件應(yīng)用工程師,主要負(fù)責(zé)DPDK、Hyperscan、QAT等網(wǎng)絡(luò)加速方案的技術(shù)支持。
目 錄
第 1章 正則表達(dá)式簡(jiǎn)介1
1.1 正則表達(dá)式的語(yǔ)法1
1.2 正則表達(dá)式的流派與標(biāo)準(zhǔn)7
1.2.1 PCRE簡(jiǎn)介7
1.2.2 POSIX標(biāo)準(zhǔn)8
1.3 本章參考10
第 2章 正則表達(dá)式匹配算法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)自動(dòng)機(jī)28
2.2.1 定義28
2.2.2 運(yùn)算優(yōu)先級(jí)29
2.2.3 Thompson構(gòu)造法31
2.2.4 ε-NFA的簡(jiǎn)化34
2.2.5 Glushkov構(gòu)造法36
2.3 確定性有限狀態(tài)自動(dòng)機(jī)40
2.3.1 定義40
2.3.2 從NFA到DFA40
2.3.3 DFA的狀態(tài)規(guī)模46
2.3.4 DFA的狀態(tài)小化52
2.4 本章參考55
第3章 正則表達(dá)式匹配庫(kù)56
3.1 PCRE56
3.1.1 語(yǔ)法支持56
3.1.2 設(shè)計(jì)概述57
3.1.3 基本API和示例代碼58
3.2 RE260
3.2.1 語(yǔ)法支持60
3.2.2 設(shè)計(jì)概述60
3.2.3 基本API和示例代碼60
3.3 Hyperscan61
3.3.1 語(yǔ)法支持61
3.3.2 匹配模式62
3.3.3 設(shè)計(jì)概述63
3.3.4 基本API和示例代碼64
3.4 正則表達(dá)式匹配庫(kù)的比較65
3.4.1 概述65
3.4.2 語(yǔ)法支持65
3.4.3 設(shè)計(jì)原理66
3.4.4 性能68
3.5 本章參考70
第4章 Hyperscan特性71
4.1 Hyperscan的語(yǔ)義71
4.2 編譯期和運(yùn)行期71
4.2.1 編譯期72
4.2.2 運(yùn)行期74
4.3 Hyperscan高級(jí)特性77
4.3.1 流狀態(tài)壓縮77
4.3.2 近似匹配78
4.3.3 邏輯組合79
4.3.4 Chimera80
4.4 Hyperscan工具82
4.4.1 hsbench82
4.4.2 hscheck84
4.4.3 hscollider85
4.4.4 hsdump88
第5章 Hyperscan設(shè)計(jì)原理92
5.1 設(shè)計(jì)原則92
5.1.1 實(shí)用性優(yōu)先92
5.1.2 情況可用93
5.1.3 流模式支持93
5.1.4 大規(guī)模可擴(kuò)展93
5.1.5 小規(guī)模高性能94
5.1.6 性能優(yōu)先94
5.1.7 平衡開(kāi)銷94
5.1.8 漸進(jìn)主義95
5.1.9 可測(cè)試性設(shè)計(jì)和自動(dòng)可測(cè)試性設(shè)計(jì)96
5.2 運(yùn)行原理96
5.2.1 匹配組件97
5.2.2 匹配原則100
5.2.3 運(yùn)行期實(shí)現(xiàn)103
5.2.4 運(yùn)行期優(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é)點(diǎn)冗余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)視機(jī)制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 Tamarama197
第7章 Hyperscan性能優(yōu)化199
7.1 Hyperscan性能測(cè)試199
7.1.1 性能測(cè)試目的199
7.1.2 基于性能的硬件和GRUB配置199
7.1.3 hsbench測(cè)試201
7.2 Hyperscan性能調(diào)優(yōu)技巧205
7.2.1 正則表達(dá)式構(gòu)造206
7.2.2 軟件庫(kù)的使用207
7.2.3 塊模式207
7.2.4 數(shù)據(jù)庫(kù)分配209
7.2.5 scratch內(nèi)存分配209
7.2.6 錨定規(guī)則211
7.2.7 隨處匹配的規(guī)則212
7.2.8 流模式下的重復(fù)語(yǔ)義213
7.2.9 青睞字符串214
7.2.10 DOTALL標(biāo)志215
7.2.11 單次匹配標(biāo)志216
7.2.12 Start of Match標(biāo)志217
7.2.13 近似匹配218
第8章 Hyperscan實(shí)際案例學(xué)習(xí)221
8.1 Snort221
8.1.1 介紹221
8.1.2 Hyperscan集成222
8.1.3 基于內(nèi)存的性能測(cè)試225
8.2 Suricata229
8.2.1 介紹229
8.2.2 Hyperscan集成229
8.2.3 基于內(nèi)存的性能測(cè)試234
8.3 垃圾郵件檢測(cè)238
8.4 深度報(bào)文檢測(cè)242
8.4.1 nDPI242
8.4.2 UDPI245
8.5 數(shù)據(jù)庫(kù)247
8.5.1 整合概述248
8.5.2 實(shí)驗(yàn)結(jié)果與分析250
8.6 Web應(yīng)用防火墻254
書(shū)單推薦
