regex - 这个正则表达式是否容易受到 REDOS 攻击

Question

正则表达式:

^\d+(\.\d+)*$

我试图打破它:

1234567890.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1x]

即 200 倍“.1”

我已经阅读了有关 ReDos 攻击的信息:

Preventing Regular Expression Denial of Service (ReDoS)

Runaway Regular Expressions: Catastrophic Backtracking

但是，我对准备对表达式进行 ReDos 攻击的技能并不太自信。由于“嵌套量词”，我试图触发灾难性的回溯。

那个表情可以破解吗？应该使用什么输入，如果是，你是如何想出它的？

Answer 1

“嵌套量词”本质上不是问题。这只是一种简单的方式来指代一个实际上要复杂得多的问题。问题是“对子表达式进行量化，该子表达式本身可以在同一位置以多种方式匹配”。事实证明，您几乎总是需要在内部子表达式中使用量词来提供足够丰富的匹配项，因此量词内的量词充当了一个危险信号，表明可能出现问题。
(.*)*有问题，因为 .*具有最大对称性——它可以匹配输入的任何点的零和所有剩余字符之间的任何内容。重复这会导致组合爆炸。
([0-9a-f]+\d+)*是有问题的，因为在数字串中的任何一点，都有许多可能的方法在 [0-9a-f]+ 的初始子串之间分配这些数字。和 \d+ 的最后一个子串，所以它和 (.*)* 有同样的问题.
(\.\d+)*没有问题，因为 \.和 \d匹配完全不同的东西。数字不是点，点也不是数字。在输入中的任何给定点，只有一种可能的方式来匹配 \. ，并且只有一种可能的匹配方式 \d+这留下了再次重复的可能性(消耗所有数字，因为如果我们在一个数字之前停止，下一个字符肯定不是一个点)。因此 (\.\d+)*在回溯方面，并不比 \d* 差将在相同的上下文中，即使它包含嵌套的量词。