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

版 权

内容提要

前 言

资源与支持

第1章 正则表达式简介

1.1 正则表达式的语法

正则表达式的元字符

1.2 正则表达式的流派与标准

1.2.1 PCRE简介

1.2.2 POSIX标准

1.3 本章参考

第2章 正则表达式匹配算法

2.1 纯字符串匹配

2.1.1 单字符串匹配KMP算法

2.1.2 单字符串匹配BM算法

2.1.3 多字符串匹配AC算法

2.1.4 AC算法与单字符串匹配

2.1.5 SHIFT-OR算法

2.2 非确定性有限状态自动机

2.2.1 定义

2.2.2 运算优先级

2.2.3 Thompson构造法

2.2.4 ε-NFA的简化

2.2.5 Glushkov构造法

2.3 确定性有限状态自动机

2.3.1 定义

2.3.2 从NFA到DFA

2.3.3 DFA的状态规模

2.3.4 DFA的状态最小化

2.4 本章参考

第3章 正则表达式匹配库

3.1 PCRE

3.1.1 语法支持

3.1.2 设计概述

3.1.3 基本API和示例代码

3.2 RE2

3.2.1 语法支持

3.2.2 设计概述

3.2.3 基本API和示例代码

3.3 Hyperscan

3.3.1 语法支持

3.3.2 匹配模式

3.3.3 设计概述

3.3.4 基本API和示例代码

3.4 正则表达式匹配库的比较

3.4.1 概述

3.4.2 语法支持

3.4.3 设计原理

3.4.4 性能

3.5 本章参考

第4章 Hyperscan特性

4.1 Hyperscan的语义

4.2 编译期和运行期

4.2.1 编译期

4.2.2 运行期

4.3 Hyperscan高级特性

4.3.1 流状态压缩

4.3.2 近似匹配

4.3.3 逻辑组合

4.3.4 Chimera

4.4 Hyperscan工具

4.4.1 hsbench

4.4.2 hscheck

4.4.3 hscollider

4.4.4 hsdump

第5章 Hyperscan设计原理

5.1 设计原则

5.1.1 实用性优先

5.1.2 极端情况可用

5.1.3 流模式支持

5.1.4 大规模可扩展

5.1.5 小规模高性能

5.1.6 性能优先

5.1.7 平衡开销

5.1.8 渐进主义

5.1.9 可测试性设计和自动可测试性设计

5.2 运行原理

5.2.1 匹配组件

5.2.2 匹配原则

5.2.3 运行期实现

5.2.4 运行期优化

5.3 图分解

5.3.1 支配路径分析

5.3.2 支配区域分析

5.3.3 网络流分析

5.3.4 图分解流程

5.4 图优化

5.4.1 节点冗余

5.4.2 边冗余

5.5 本章参考

第6章 Hyperscan引擎

6.1 SIMD加速

6.1.1 搜索单字符的加速

6.1.2 搜索双字符序列的加速

6.1.3 搜索小规模单字符集的加速

6.1.4 搜索大规模单字符集的加速

6.1.5 环视机制

6.2 纯字符串匹配

6.2.1 纯字符串匹配在Hyperscan中的作用

6.2.2 单字符串匹配器“Noodle”

6.2.3 大规模多字符串匹配器“FDR”

6.2.4 小规模多字符串匹配器“Teddy”

6.3 正则引擎

6.3.1 NFA引擎

6.3.2 DFA引擎

6.3.3 重复引擎

6.3.4 Tamarama

第7章 Hyperscan性能优化

7.1 Hyperscan性能测试

7.1.1 性能测试目的

7.1.2 基于性能的硬件和GRUB配置

7.1.3 hsbench测试

7.2 Hyperscan性能调优技巧

7.2.1 正则表达式构造

7.2.2 软件库的使用

7.2.3 块模式

7.2.4 数据库分配

7.2.5 scratch内存分配

7.2.6 锚定规则

7.2.7 随处匹配的规则

7.2.8 流模式下的重复语义

7.2.9 青睐字符串

7.2.10 DOTALL标志

7.2.11 单次匹配标志

7.2.12 Start of Match标志

7.2.13 近似匹配

第8章 Hyperscan实际案例学习

8.1 Snort

8.1.1 介绍

8.1.2 Hyperscan集成

8.1.3 基于内存的性能测试

8.2 Suricata

8.2.1 介绍

8.2.2 Hyperscan集成

8.2.3 基于内存的性能测试

8.3 垃圾邮件检测

Rspamd

8.4 深度报文检测

8.4.1 nDPI

8.4.2 UDPI

8.5 数据库

8.5.1 整合概述

8.5.2 实验结果与分析

8.6 Web应用防火墙

ModSecurity