开发 | 警觉！藏在正则表达式里的圈套(2)

时间：2019-02-20 21:07 来源：网络整理作者：网络浏览：次收藏挑错推荐打印

读取正则表达式第二个婚配符 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 是：

?request=6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf

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

第一部分：校验协议。^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)。

第二部分：校验域名。(([A-Za-z0-9-~]+).)+。

第三部分：校验参数。([A-Za-z0-9-~\/])+$。

我们可以发现正则表达式校验协议这部分是没有成绩的，但是在校验的时分，其运用了 xxxx. 这种方式去校验。那么其实婚配进程是这样的：

婚配到

婚配到 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 = "?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf";

if (bugUrl.matches(badRegex)) {

System.out.println("match!!");

} else {

System.out.println("no match!!");

}

运转下面的顺序，立刻就会打印出match!!。

但这是不够的，假设以后还有其他 URL 包含了乌七八糟的字符呢，我们难不成还再修正一遍。一定不理想嘛!

其真实正则表达式中有这么三种形式：贪心形式、懒散形式、独占形式。

在关于数量的婚配中，有 + ? * {min,max} 四种两次，假设只是独自运用，那么它们就是贪心形式。

假设在他们之后加多一个 ? 符号，那么原先的贪心形式就会变成懒散形式，即尽能够少地婚配。但是懒散形式还是会发作回溯现象的。例如下面这个例子：

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-~_%\/])+$

这样之后，运转原有的顺序就没有成绩了。

最后引荐一个网站，这个网站可以反省你写的正则表达式和对应的字符串婚配时会不会有成绩。

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

例如我本文中存在成绩的那个 URL 运用该网站反省后会提示：catastrophic backgracking(灾难性回溯)。

当你点击左下角的「regex debugger」时，它会通知你一共经过多少步反省终了，并且会将一切步骤都列出来，并标明发作回溯的位置。

本文中的这个正则表达式在停止了 11 万步尝试之后，自动中止了。这阐明这个正则表达式确实存在成绩，需求改良。

但是当我用我们修正过的正则表达式停止测试，即下面这个正则表达式。