5

Regex :

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

I tried to break it with :

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]

that is 200x".1"

I have read about ReDos attacks from :

However, I am not too confident in my skills to prepare a ReDos attack on an expression. I tried to trigger catastrophic backtracking due to "Nested Quantifiers".

Is that expression breakable? What input should be used for that and, if yes, how did you come up with it?

5
  • 1
    What are you trying to accomplish with that regex? Is there a specific use-case you're looking to achieve?
    – ctwheels
    Oct 11, 2019 at 16:22
  • @ctwheels the regex looks like a version number Oct 11, 2019 at 16:38
  • If you want to prevent performance issues and use a regex flavor that supports possessive quantifiers, just use eg ^\d++(?:\.\d+)*+$ - This will prevent excessive backtracking and your regex is safe. Further your dot needs to be escaped by backslash to match literally, else it matches (almost) any character. Oct 11, 2019 at 17:00
  • It would be helpful to know the programming language to be able to provide corrections if necessary. For example, possessive quantifiers as proposed by @bobblebubble won't work with python's re module, you'd have to use the PyPi regex module instead.
    – ctwheels
    Oct 11, 2019 at 17:31
  • this is for a java applications and i did remove the extra java escapes ^\\d+(\\.\\d+)*$
    – Belun
    Oct 14, 2019 at 7:05

2 Answers 2

7

"Nested quantifiers" isn't inherently a problem. It's just a simple way to refer to a problem which is actually quite a bit more complicated. The problem is "quantifying over a sub-expression which can, itself, match in many ways at the same position". It just turns out that you almost always need a quantifier in the inner sub-expression to provide a rich enough supply of matches, and so quantifiers inside quantifiers serve as a red flag that indicates the possibility of trouble.

(.*)* is problematic because .* has maximum symmetry — it can match anything between zero and all of the remaining characters at any point of the input. Repeating this leads to a combinatorial explosion.

([0-9a-f]+\d+)* is problematic because at any point in a string of digits, there will be many possible ways to allocate those digits between an initial substring of [0-9a-f]+ and a final substring of \d+, so it has the same exact issue as (.*)*.

(\.\d+)* is not problematic because \. and \d match completely different things. A digit isn't a dot and a dot isn't a digit. At any given point in the input there is only one possible way to match \., and only one possible way to match \d+ that leaves open the possibility of another repetition (consume all of the digits, because if we stop before a digit, the next character is certainly not a dot). Therefore (\.\d+)* is no worse, backtracking-wise, than a \d* would be in the same context, even though it contains nested quantifiers.

3
  • 2
    Very well explained. "Back-to-back quantifiers that match the same pattern" is the phrase I'll have in mind from now on when I'm checking my own regex. +1
    – Nick Reed
    Oct 11, 2019 at 19:12
  • interesting. so, nested quantifiers could cause problems with overlapping expressions; the message here (for the newbies) : "do not panic just because you saw some nested quantifiers"
    – Belun
    Oct 14, 2019 at 7:21
  • @Belun be aware, be concerned... never panic :)
    – hobbs
    Oct 14, 2019 at 12:40
3

Your regex is safe, but only because of "\."

Testing on regex101.com shows that there are no combinations of inputs that create runaway checks - but your regex is VERY close to being vulnerable, so be careful when modifying it.

As you've read, catastrophic backtracking happens when two quantifiers are right next to each other. In your case, the regex expands to \d+\.\d+\.\d+\.\d+\. ... and so on. Because you make the dot required for every single match between \d+, your regex grows by only three steps for each period-number you add. (This translates to 4 steps per period-number if you put an invalid character at the end.) That's a linear growth rate, so your regex is fine. Demo

However, if you make the \. optional, accidentally forget the escape character to make it plain ol' ., or remove it altogether, then you're in trouble. Such a regex would allow catastrophic backtracking; an invalid character at the end approximately doubles the runtime with every additional number you add before it. That's an exponential growth rate, and it's enough to crash time out the regex101 engine's default settings with just 18 digits and 1 invalid character. Demo

As written, your regex is fine, and will remain so as long as you ensure sure there's something "solid" between the first \d+ and the second \d+, as well as something "solid" between the second \d+ and the * outside its capture group.

3
  • 2
    regex101 doesn't crash, it just runs into a timeout in a very controlled manner. Oct 12, 2019 at 0:31
  • i did notice that increase (of 4 steps) for each an extra group of .1 ; i thought somebody more versed in this kind of stuff can make it worse :P
    – Belun
    Oct 14, 2019 at 7:18
  • interesting this idea of "expanding the regex"
    – Belun
    Oct 14, 2019 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.