正则表达式
正则表达式（regular expression）又称为规则表达式，就是用一个 “字符串” 来描述一个特征，然后去检索、替换另一个符合这个特征 “字符串”。
正则表达式引擎分类
正则表达式引擎分为两类：NFA 和 DFA。
- NFA：匹配过程面临很多的岔路，需要做出选择，一旦某条岔路失败，就需要回朔。类似于回溯法。执行复杂度最大为 O（2^n)。
- DFA：匹配过程是确定的，每个字母需要匹配一次。长度为 n 的正则表达式执行复杂度为 O（2^n),长度为 n 的字符串，执行复杂度为 O（n）
构造 DFA 的代价远大于 NFA，假设 NFA 的状态数为 K，那么等价 DFA 的状态数目理论上可达 2 的 k 次方，不过实际上几乎不会出现这么极端的情况，可以肯定的是构造 DFA 会消耗更多的时间和内存。
但是 DFA 一旦构造好了之后，执行效率就非常理想，如果一个串的长度是 n，那么匹配算法的执行复杂度是 O(n);而 NFA 在匹配过程中，存在大量的分支和回朔，假设 NFA 的状态数为 s，因为每输入一个字符可能达到的状态数做多为 s，那么匹配算法的复杂度及时输入串的长度乘以状态数 O(ns)。NFA 所支持的高级特性比 DFA 要多，所以 NFA 常被使用。
Redos 攻击
ReDoS(Regular expression Denial of Service) 正则表达式拒绝服务攻击。应用程序使用正则表达式对用户输入的数据进行有效性校验, 当正则表达式存在缺陷或者不严谨时, 攻击者可以通过构造特殊的字符串大量消耗服务器的系统资源，造成服务器的服务中断或停止。
不论是 DFA 还是 NFA 引擎，极端情况下执行复杂度可能达到 O(2^n),这就会导致执行正则教研的线程执行缓慢并占用大量 CPU 资源，有时可能会将 CPU 耗尽。
实例
正则表达式^(a+)+$的回溯匹配算法：
对于 aaaab，存在 16 种可能的路径（2^4），但是对于 aaaaaaaaaaaaaaaab，则存在 65536 种可能的路径（2^16）。
通过https://regex101.com/ 网站进行测试：
1) 测试字符串 aaaab
经过 54 步，耗时 1ms。
2) 测试字符串 aaaaab
经过 103 步，耗时 1ms
3) 测试字符串 aaaaaaaaaaaaaab
经过 49168 步，耗时 114ms。
什么样的正则表达式易受攻击
- 重复分组
- 重复分组内存在:
- 重复
- 交叉重叠
样例：
- (a+)+
- ([a-zA-Z]+)*
- (a|aa)+
- (a|a?)+
- (.*a){x} | for x > 10
哪些环节易受攻击
理论上网络系统的每一个环节都有正则表达式的存在，因此都有可能受到 ReDos 攻击。但实际上，黑客攻击自己的浏览器是没有意义的，因此除浏览器外使用正则表达式验证用户输入的其他设备上都应该经过准确的验证。
如何测试
使用微软测试工具Microsoft SDL Regex Fuzzer，测试^(a+)+$，测试结果是 Failed。点击下载。
如何防范
Redos 攻击很难完全消除，只能尽可能降低这种风险。常用的措施有：
- 尽量明确不可信输入的字符串长度。
- 避免使用分组、重复等。
- 充分的测试。
- 完善的性能监控工具。
参考资料：
《精通正则表达式》
《编译原理龙书第二版》
https://xz.aliyun.com/t/2723#toc-9
https://www.regular-expressions.info/catastrophic.html
https://www.andseclab.com/2018/04/19/owasp%E6%B1%89%E5%8C%96%E6%94%BB%E5%87%BB%E7%B3%BB%E5%88%97%E5%A4%A7%E5%85%A8%E4%BA%94%E5%8D%81%E4%B8%80%EF%BC%9A%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%8B%92%E7%BB%9D%E6%9C%8D%E5%8A%A1/
https://www.freebuf.com/articles/network/124422.html