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

Dav*_*asy 7

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

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

然而，其他使用回溯的语言/库可能具有指数运行时间，具体取决于正则表达式和输入字符串。regex101. 显示了针对输入字符串运行正则表达式的步骤数，您可以看到步数随着您增加正则表达式的字符串长度而呈指数增长，(a*)*$例如aaaaaaaaaaaaaaaaX. regex101. 上的调试器可以一次显示模式匹配执行的一个步骤，因此您可以看到回溯如何处理呈指数增长的备选方案。

@sln提供了我原来的正则表达式的替代方法，它消除了指数回溯。将输入字符串之前/之后的正则表达式简化为aand需要大约 300,000 步（每增加一倍），但 需要大约 100 步XaaaaaaaaaaaaaaaaZ ^(a+X*)*a$a^(aX*)*a$

我不知道将易受攻击的正则表达式映射到安全正则表达式的任何一般方法 - 除非@sln 关心提供服务;-)

原始正则表达式的目的是检查输入字符串是否仅包含 [a-z0-9] 并且-以 [a-z0-9] 开头和结尾。 a, a-b, ab--c, a-b--aa---bbb, ...