Java编程：正则表达式引发谋杀，电子CPU百分百异常！

前几天，网上的一个项目监控信息突然报出异常。到机器上查看相关资源的使用情况后发现CPU使用率几乎是100%。通过Java自带的线程转储工具，我们导出了问题的堆栈信息。

我们可以看到所有的堆栈都指向一个名为validateUrl的方法，并且堆栈中存在超过100条这样的错误消息。通过查看代码我们知道该方法的主要作用是验证URL是否合法。

正则表达式怎么会导致CPU利用率高，这很奇怪。为了澄清重放问题，我们提取了关键代码并创建了一个简单的单元测试。

public static void main(String[] args) {
    String badRegex = "^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\\\/])+$";
    String bugUrl = "http://www.fapiao.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf";
    if (bugUrl.matches(badRegex)) {
        System.out.println("match!!");
    } else {
        System.out.println("no match!!");
    }
}
复制代码

当我们运行上面的例子时，通过资源监视器可以看到一个叫java的进程的CPU利用率直接上升到了91.4%。

看到这里，我们基本可以断定这个正则表达式是凶手导致CPU占用率高的！

于是我们把调试重点放在了正则表达式上：

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\/])+$
复制代码

这个正则表达式看起来没有问题，可以分为三部分：

第一部分匹配http和https协议，第二部分匹配www 。字符，第三部分匹配很多字符。我看着这个表情愣了半天，却没有发现什么大问题。

其实，这里CPU占用率高的主要原因是： **Java正则表达式使用的引擎实现是NFA自动机。这个正则表达式引擎在字符匹配时会导致回溯。 **当发生回溯时，所花费的时间会很长，可能是几分钟，也可能是几小时。需要多长时间取决于回溯的次数和复杂程度。

看到这里，你可能不知道什么是回溯，还有些困惑。没关系，我们先一点一点开始了解正则表达式的原理。

正则表达式引擎

正则表达式是一种非常方便的匹配符号，但是要实现如此复杂而强大的匹配语法，必须有一套算法来实现，而实现这套算法的东西叫做正则表达式引擎。简单来说，正则表达式引擎的实现有两种方式：DFA自动机（Deterministic Final Automata确定性有限自动机）和NFA自动机不确定性有限（Non metric）。

对于这两类自动机来说，它们有各自的区别，我们不打算在这里深究它们的原理。简单来说，DFA自动机的时间复杂度是线性的，比较稳定，但功能有限。 NFA的时间复杂度比较不稳定。有时很好，有时不太好。好不好取决于你写的正则表达式。但NFA更强大，所以像Java、.NET、Perl、Python、Ruby、PHP等语言都使用NFA来实现其正则表达式。

NFA如何进行自动加法匹配？我们以下列标志和表达方式为例。

text="Today is a nice day."
regex="day"
复制代码

需要记住的非常重要的一点是NFA基于正则表达式进行匹配。换句话说，自动NFA机器会一一读取正则表达式中的字符，然后将其与目标字符串进行匹配。如果匹配成功，则更改为正则表达式中的下一个字符。否则，它将继续与目标字符串中的下一个字符进行比较。也许你还不太理解，没关系，我们用上面的例子来一步步分析。

• 首先获取正则表达式中第一个匹配的字符：d.然后将其与字符串中的字符进行比较。字符串中的第一个字符是 T。如果不匹配，则将其替换为下一个字符。第二个是 o，它也不匹配，因此将其替换为下一个。第三个是d，如果匹配，则读取正则表达式中的第二个字符：a.
• 读取正则表达式中的第二个匹配字符：a.然后继续与字符串中的第四个字符a进行比较，得到再次比赛。然后读取正则表达式中的第三个字符：y。
• 读取正则表达式中的第三个匹配字符：y。然后继续与字符串中的第五个字符 y 进行比较，它再次匹配。尝试读取正则表达式中的下一个字符，发现没有，则匹配结束。

上面的匹配过程是NFA机器的匹配过程，但是匹配过程本身会比这个复杂很多，但是原理是一样的。

回溯NFA自动机

现在我们了解了NFA如何进行字符串匹配，现在我们可以谈谈本文的重点：回溯。为了更好的解释回溯，我们还用下面的例子来解释。

text="abbc"
regex="ab{1,3}c"
复制代码

上面例子的目的比较简单。它匹配以a开头、以c结尾、中间有1-3个b字符的字符串。 NFA解析的过程如下：

• 首先读取正则表达式中第一个匹配的字符a，与字符串中的第一个字符a进行比较，匹配。然后读取正则表达式中的第二个字符。
• 读取正则表达式中的第二个匹配字符b{1,3}，与字符串中的第二个字符b进行比较，匹配。但由于 b{1,3} 代表 1-3 个 b 串，以及 NFA 自动机的贪婪特性（即尽可能多地匹配），因此此时不会读取下一个正则表达式。公式中没有使用匹配字符，而是仍然使用b{1,3}与字符串中的第三个字符b进行比较，发现仍然匹配。于是我继续用b{1,3}与字符串中的第四个字符c进行比较，发现没有匹配。此时就会发生回溯。
• 发生回溯时如何操作？回溯发生后，我们读到的字符串中的第四个字符c将被吐出，指针将返回到第三个字符串的位置。之后，程序读取正则表达式中的下一个运算符c，读取当前指针中的下一个字符c，并进行比较以找到匹配项。所以读取下一个操作符，但到这里就结束了。

我们回过头来看看之前的URL验证正则表达式：

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\/])+$
复制代码

有问题的URL是：

http://www.fapiao.com/dzfp-web/pdf/download?request=6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf
复制代码

我们把这个正则表达式分为三部分：

• 第一部分：验证协议。 ^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)。
• 第 2 部分：验证域名。 (([A-Za-z0-9-~]+).)+。
• 第 3 部分：验证参数。 ([A-Za-z0-9-~\\/])+$。

我们可以找到正则表达式验证协议http://这部分没有问题，但是验证www.fapiao.com时，它使用的是xxxx。♸❀❀路。所以实际上匹配过程是这样的：

• 匹配www.
• 匹配发票.
• 匹配com/dzfp-web/pdf/download?request=6e7...会发现由于贪心匹配时，程序会继续读取后面的字符串进行匹配，最终发现没有点，所以会逐个字符地返回。

这是这个正则表达式的第一个问题。

另一个问题出在正则表达式的第三部分。我们发现有问题的URL有一个下划线（_）和一个百分号（%），但是在第三部分对应的正则表达式中没有这个东西。这将导致在发现不匹配之前匹配一长串字符，并最终返回。

这是这个正则表达式的第二个问题。

解决方案

了解回溯是问题的原因后，实际上减少了这种回溯。你会发现，如果我在第三部分加上下划线和百分号，程序就正常了。

public static void main(String[] args) {
    String badRegex = "^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~_%\\\\/])+$";
    String bugUrl = "http://www.fapiao.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf";
    if (bugUrl.matches(badRegex)) {
        System.out.println("match!!");
    } else {
        System.out.println("no match!!");
    }
}
复制代码

运行上面的程序，它会立即打印match!!。

但这还不够。如果以后还有其他网址含有乱码，我们就得重新修改了。这绝对不现实！

其实正则表达式有三种模式：贪婪模式、惰性模式、独占模式。

匹配的数量是+？ * {min,max} 四种类型两次。如果单独使用，它们是贪婪模式。

**如果再加一张呢？符号后面，原来的贪婪模式就会变成懒惰模式，即尽可能少的匹配。 **但是在懒惰模式下仍然会发生回溯。 TODO例如下面的例子：

text="abbc"
regex="ab{1,3}?c"
复制代码

正则表达式中的第一个运算符a匹配字符串中的第一个字符a，匹配为。那么第二个运算符 b{1,3} 呢？正则表达式的匹配字符串中的第二个字符b，匹配成功。由于最小匹配原则，正则表达式中的第三个运算符c与字符串中的第三个字符b进行匹配，没有找到匹配项。那么我们回去匹配第二个运算符b{1,3}？匹配字符串中第三个字符b的正则表达式，匹配成功。于是我们将正则表达式中的第三个运算符c与字符串中的第四个字符c进行匹配，匹配成功。就这样结束了。

如果在它们后面多加一个+号，原来的贪婪模式就会变成独占模式，即尽可能多的匹配而不走回头路。

所以，想要彻底解决问题，就需要在保证功能的情况下，保证不发生回溯。我在正则表达式的第二部分后面额外添加了一个+号来验证上面的URL，它是这样的：

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)
(([A-Za-z0-9-~]+).)++    --->>> （这里加了个+号）
([A-Za-z0-9-~\\/])+$
复制代码

这样，运行原来的程序就没有问题了。

最后推荐一个网站。该网站可以检查您输入的正则表达式与相应的字符串匹配是否存在问题。

在线正则表达式测试器和调试器：PHP、PCRE、Python、Golang 和 JavaScript

例如我文章中存在问题的 URL 使用此网站检查后会提示：灾难性的 backgracking。

当您点击左下角的“正则表达式调试器”时，它会告诉您已经完成了多少步骤，并会列出所有步骤并指示发生回溯的位置。

本文中的正则表达式在尝试 110,000 次后自动停止。这说明这个正则表达式确实存在问题，需要改进。

但是当我用我们修改后的正则表达式（以下正则表达式）测试它时。

^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~\\\/])+$
复制代码

Tooltip 只用了58步就完成了检查。

一个字符的差异，意味着性能差异数万倍。

舒毅有话要说

一个小小的正则表达式就能让CPU变慢，真是太神奇了。这也给我们这些平时写程序的人一个警示。当我们遇到正则表达式的时候，一定要考虑到贪心模式和回溯问题，否则我们写的每一个表达式都会是一个惊喜。

网上查阅资料，发现深圳阿里中心LAZADA的同学在2017年也遇到过这个问题，他们在测试环境下也没有发现问题，但是刚上线的时候，100%出现了CPU问题。他们面临的问题和我们几乎一模一样。