在Go正则表达式中没有灾难性回溯吗？

Question

在regex101.com上测试这个正则表达式时，当我在以下字符串上测试时，出现了“灾难性回溯”的错误:

使用PHP风格：

aaaaaaaaaaa-aaaaT

使用Python风格：

aaaaaaaaaaa-aaaaT

使用ECMAScript风格，这个更长的字符串超时了，可能是“灾难性回溯”的迹象：

aaaaaaaaaaa-aaaaaaaaaaaaaaaaaT

使用Java 8风格，字符串超时：

aaaaaaaaaaa-aaaaaaaaaaaaaT

但是Go风格没有出现任何错误或超时事件，即使是更长的字符串也是如此。相反，它显示“无匹配（0.0ms）”。

那么当我的正则表达式在Go中使用时，我可以忽略该错误/警告吗？

我也对此原因感兴趣，但以上是我的关键问题。

- Dave Deasy

---

Go标准库中的正则表达式引擎不支持回溯，因此不可能发生灾难性回溯。 - Adrian

还有更多关于https://en.wikipedia.org/wiki/RE2_(software)的信息。 - The fourth bird

将其更改为 ^(?:[a-z0-9]-?)*[a-z0-9]$，您就不会遇到任何回溯溢出问题。 - sln

Golang 使用 RE2，就像 Google Sheets、Gmail 和 G Suite 一样。RE2 是一个非回溯库，具有线性时间执行 - O(n)。 - Szczerski

这个问题正在元社区上讨论。 - cigien

Answer 1

是的，在使用Go中的正则表达式时，可以安全地忽略“灾难性回溯”警告。

Go使用RE2算法进行正则表达式匹配，而RE2不使用回溯，因此在Go中不存在这个问题。https://en.wikipedia.org/wiki/Regular_expression#Implementations_and_running_times有关于正则表达式匹配的替代实现的更多信息。Go(RE2)针对输入字符串长度和正则表达式字符串长度具有线性性能：O(mn)。

然而，其他使用回溯的语言/库可能会出现指数级运行时间，这取决于正则表达式和输入字符串。regex101.com显示了运行正则表达式与输入字符串的步骤数，您可以看到类似于(a*)*$的正则表达式与像aaaaaaaaaaaaaaaaX这样的字符串增加字符串长度时步骤数呈指数级增长。regex101.com上的调试器可以逐步显示模式匹配执行情况，因此您可以看到回溯如何处理指数级增加的选择数量。

@sln 提供了一个替代我原来的正则表达式的方法，这种方法可以消除指数回溯。对于输入字符串 aaaaaaaaaaaaaaaaZ，将之前/之后的正则表达式简化为a和X，^(a+X*)*a$需要大约300,000步（每增加一个a就会翻倍），但是^(aX*)*a$只需要大约100步。

我不知道有没有通用的方法可以将一个易受攻击的正则表达式映射到一个安全的正则表达式 - 除非@sln愿意提供服务;-)

原始正则表达式的目的是检查输入字符串是否仅包含[a-z0-9]和-，同时以[a-z0-9]开头和结尾。a、a-b、ab--c、a-b--aa---bbb等都符合条件。

- Dave Deasy