深入浅出 Hyperscan:高性能正则表达式算法原理与设计

目　　录
第 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　非确定性有限状态自动机 28
2．2．1 定义 28
2．2．2 运算优先级 29
2．2．3 Thompson构造法 31
2．2．4 ε-NFA的简化 34
2．2．5 Glushkov构造法 36
2．3　确定性有限状态自动机 40
2．3．1 定义 40
2．3．2 从NFA到DFA 40
2．3．3 DFA的状态规模 46
2．3．4 DFA的状态*小化 52
2．4　本章参考 55
第3章　正则表达式匹配库 56
3．1　PCRE 56
3．1．1 语法支持 56
3．1．2 设计概述 57
3．1．3 基本API和示例代码 58
3．2　RE2 60
3．2．1 语法支持 60
3．2．2 设计概述 60
3．2．3 基本API和示例代码 60
3．3　Hyperscan 61
3．3．1 语法支持 61
3．3．2 匹配模式 62
3．3．3 设计概述 63
3．3．4 基本API和示例代码 64
3．4　正则表达式匹配库的比较 65
3．4．1 概述 65
3．4．2 语法支持 65
3．4．3 设计原理 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 流状态压缩 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设计原理 92
5．1　设计原则 92
5．1．1 实用性优先 92
5．1．2 极端情况可用 93
5．1．3 流模式支持 93
5．1．4 大规模可扩展 93
5．1．5 小规模高性能 94
5．1．6 性能优先 94
5．1．7 平衡开销 94
5．1．8 渐进主义 95
5．1．9 可测试性设计和自动可测试性设计 96
5．2　运行原理 96
5．2．1 匹配组件 97
5．2．2 匹配原则 100
5．2．3 运行期实现 103
5．2．4 运行期优化 108
5．3　图分解 112
5．3．1 支配路径分析 114
5．3．2 支配区域分析 115
5．3．3 网络流分析 116
5．3．4 图分解流程 117
5．4　图优化 122
5．4．1 节点冗余 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 搜索小规模单字符集的加速 136
6．1．4 搜索大规模单字符集的加速 140
6．1．5 环视机制 143
6．2　纯字符串匹配 148
6．2．1 纯字符串匹配在Hyperscan中的作用 148
6．2．2 单字符串匹配器“Noodle” 148
6．2．3 大规模多字符串匹配器“FDR” 150
6．2．4 小规模多字符串匹配器“Teddy” 156
6．3　正则引擎 160
6．3．1 NFA引擎 160
6．3．2 DFA引擎 168
6．3．3 重复引擎 186
6．3．4 Tamarama 197
第7章　Hyperscan性能优化 199
7．1　Hyperscan性能测试 199
7．1．1 性能测试目的 199
7．1．2 基于性能的硬件和GRUB配置 199
7．1．3 hsbench测试 201
7．2　Hyperscan性能调优技巧 205
7．2．1 正则表达式构造 206
7．2．2 软件库的使用 207
7．2．3 块模式 207
7．2．4 数据库分配 209
7．2．5 scratch内存分配 209
7．2．6 锚定规则 211
7．2．7 随处匹配的规则 212
7．2．8 流模式下的重复语义 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 基于内存的性能测试 225
8．2　Suricata 229
8．2．1 介绍 229
8．2．2 Hyperscan集成 229
8．2．3 基于内存的性能测试 234
8．3　垃圾邮件检测 238
8．4　深度报文检测 242
8．4．1 nDPI 242
8．4．2 UDPI 245
8．5　数据库 247
8．5．1 整合概述 248
8．5．2 实验结果与分析 250
8．6　Web应用防火墙 254