正则表达式中隐藏的陷阱

jiezi

6 年前

几天前，一个在线项目的监控系统突然报告了一个例外。在检查相关资源的使用情况后，我们发现 CPU 利用率接近 100%。然后我们使用 Java 附带的 thread dump 工具导出问题的堆栈信息。

我们可以看到所有堆栈都指向一个被调用的方法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确定性最终自动机）和NFA（非确定性有限自动机）。

这两个自动机是不同的，我们不会深入研究它们的原理。简单地说，时间复杂度 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。让我们继续将它与字符串的第五个字符匹配，然后匹配。然后尝试读取正则表达式的下一个字符，发现没有，所以匹配结束。

以上是匹配过程，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

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

第 1 部分：验证协议。^([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。
匹配到fapiao。
匹配 com/dzfp-web/pdf/download?request=6e7JGm38jf.....，您将看到由于贪婪的性质，程序将始终尝试读取后续字符串以匹配，最后它发现没有点，因此它开始逐个字符回溯。

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

另一个问题是正则表达式的第三部分。可以发现有问题的 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!!。

如果将来还有其他包含杂乱字符的 URL 怎么办？再改一次？当然这不现实！

事实上，正则表达式有三种模式：贪婪模式 ， 不情愿模式 和占有模式。

如果? 在正则表达式中添加一个符号，则 Greedy 模式将变为 Reluctant 模式，也就是说，它将尽可能少地匹配。但是，在 Reluctant 模式下仍会发生回溯。例如：

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-~]+).)++    --->>>（added + here）([A-Za-z0-9-~_%\\\/])+$

现在运行该程序没有问题。

最后，我推荐一个网站，可以检查你写的正则表达式是否有问题以及相应的字符串匹配。

Online regex tester and debugger: PHP, PCRE, Python, Golang and JavaScript

例如，使用站点检查后将提示本文中存在问题的 URL：灾难性的回溯。

单击左下角的“正则表达式调试器”时，它将告诉您已检查了多少步骤，并将列出所有步骤并指出回溯发生的位置。

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

但是当我用修改后的正则表达式测试它时如下：

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

提示完成检查只需要 58 步。

一个字符的差异会导致巨大的性能差距。

令人惊讶的是，一个小的正则表达式可以让 CPU 死掉。当遇到正则表达式时它也给我们敲响了警钟，使用时应该注意贪婪模式和回溯问题。

正则表达式引擎

Backtracking(回溯)NFA

解释

最后