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

1.由浅入深介绍正则表达式相关知识、Hyperscan算法库功能特性及总体设计原则 2.伪码源码相辅相成，方便读者学习基础算法及实现步骤 3.算法实例搭配图例表格，加深读者对算法的理解 4.理论与实践兼收并重学习Hyperscan与开源产品整合案例分析

本书系统、全面、循序渐进地介绍Hyperscan技术。全书共8章，主要介绍正则表达式、经典匹配算法和正则表达式匹配所依赖的自动机原理、正则表达式匹配库等，并重点介绍Hyperscan的功能特性、设计原理和性能调优技巧，以及匹配引擎的核心算法和SIMD加速技术的运用，还展示了Hyperscan多样化的应用场景。
本书既适合作为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