什么是ReDoS

ReDoS(Regular expression Denial of Service) 正则表达式拒绝服务攻击。

开发人员使用了正则表达式来对用户输入的数据进行有效性校验, 当编写校验的正则表达式存在缺陷或者不严谨时, 攻击者可以构造特殊的字符串来大量消耗服务器的系统资源，造成服务器的服务中断或停止。

正则表达式实现原理

正则表达式是一个用正则符号写出的公式，程序对这个公式进行语法分析，建立一个语法分析树，再根据这个分析树结合正则表达式的引擎生成执行程序（这个执行程序我们把它称作状态机，也叫状态自动机），用于字符匹配。

这里的正则表达式引擎就是一套核心算法，用于建立状态机。目前实现正则表达式引擎的方式有两种：

DFA 自动机（Deterministic Final Automata 确定有限状态自动机）
NFA 自动机（Non deterministic Finite Automaton 非确定有限状态自动机）
DFA从匹配文本入手，从左到右，每个字符不会匹配两次，它的时间复杂度是多项式的，所以通常情况下，它的速度更快，但支持的特性很少，不支持捕获组、各种引用等等；

而NFA则是从正则表达式入手，不断读入字符，尝试是否匹配当前正则，不匹配则吐出字符重新尝试，通常它的速度比较慢，最优时间复杂度为多项式的，最差情况为指数级的。但NFA支持更多的特性，因而绝大多数编程场景下（包括java，js），我们面对的是NFA。

DFA、NFA有多种算法

Backtracking NFA 回溯NFA算法，最常见的算法大部分开发语言的正则引擎是用基于回溯的 NFA 来实现
Thompson-NFA re2j用的算法
Bitparallel-NFA
Graph-DFA
Tabled-DFA

灾难性回溯（Catastrophic Backtracking）

由于回溯NFA算法的存在，以下代码进行运行的时候，会把CPU跑到100%，从而造成线上服务的异常

public class RegDemo {

    public static void main(String[] args) {
        String matchStr = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        Pattern p1 = Pattern.compile("(a+)*");
        Pattern p2 = Pattern.compile("(a+)*s");

        long l = System.currentTimeMillis();
        System.out.println("p1 " + p1.matcher(matchStr).find() + " use time " + (System.currentTimeMillis() - l));

        l = System.currentTimeMillis();
        System.out.println("p2 " + p2.matcher(matchStr).find() + " use time " + (System.currentTimeMillis() - l));
    }
}