16

My question, Is there no catastrophic backtracking in Go regex?, was closed as "not reproducible or was caused by typos" and I'm afraid I don't understand why. I don't believe there is a typo and the problem is certainly reproducible.

I had drafted an answer, based on comments and further reading, before I spotted that the question was closed and it seems a pity not to be able to post the answer.

I could add the answer as an addendum to the question or maybe in a comment, though I believe comments are transient.

Here is the draft answer in case there will be an objection to it.

Answer

Yes, the catastrophic backtracking warning can be safely ignored when using the regex in Go.

Go uses the RE2 algorithm for regex, and RE2 does not use backtracking so the problem does not arise in Go. https://en.wikipedia.org/wiki/Regular_expression#Implementations_and_running_times has more information about alternative implementations for regex matching. Go (RE2) has linear performance against input string length and regex string length: O(mn).

However other languages / libs that do use backtracking can have exponential running time, depending on the regex and the input string. regex101.com shows the number of steps to run a regex against an input string and you can see the number of steps increase exponentially as you increase the string length for a regex like (a*)*$ with a string like aaaaaaaaaaaaaaaaX. And the debugger on regex101.com can show the pattern match execution one step at a time, so you can see how backtracking has to handle an exponentially increasing number of alternatives.

@sln provided an alternative to my original regex that removed the exponential backtracking. Simplifying the before/after regex to a and X, for input string aaaaaaaaaaaaaaaaZ ^(a+X*)*a$ takes about 300,000 steps (doubling for each additional a) but ^(aX*)*a$ takes about 100 steps

I don't know any general way to map a vulnerable regex to a safe regex

  • unless @sln cares to provide a service ;-)

The purpose of the original regex was to check that an input string contains only [a-z0-9] and - while starting and ending with [a-z0-9]. a, a-b, ab--c, a-b--aa---bbb, ...

8
  • 22
    As much as I was expecting to downvote this as another ill-informed complaint from a new user about their question being closed, I turned out to be wrong. I have no idea why your question was closed, especially as a typo/no repro. Even if you made a fundamental error in expecting that Go's regex implementation supported some feature that it does not, that doesn't make the question unsuitable for this site. In fact, that makes having it asked and answered here very useful. I lack much expertise in this particular subject, so I'm not going to override experts, but I'm curious, too.
    – Cody Gray Mod
    Nov 14, 2021 at 18:48
  • 2
    @Cody Are we allowed to cast reopen votes on questions while they're being discussed on Meta (such as this one)? Nov 14, 2021 at 19:02
  • 5
    Yeah, close/reopen votes are fair game, in my opinion. The only thing I oppose is deleting a question that is under discussion out from under the people who are (or might be) trying to discuss it. That said, @AdrianMole, if you are casting a vote to reopen, that might be an indication that you should be posting an answer here with your reasoning.
    – Cody Gray Mod
    Nov 14, 2021 at 19:05
  • Hmm. My concern is that I don't want to participate in a tug-o-war/ping-pong reopen/close cycle. I guess it would be better to hold off on such votes (at least, for a while), to let the 'real' experts have their say here. Nov 14, 2021 at 19:07
  • 2
    The question has now been reopened, @DaveDeasy, so maybe you should post your answer there (it may get closed again, with all the attention its getting here). Both the Q and the A look good, to me. :-) Nov 14, 2021 at 19:11
  • 2
    I'm surprised this isn't a duplicate. The only other post I can find mentioning catastrophic backtracking in [go] is my own answer from many years ago to a question that's asking something a little different.
    – Laurel
    Nov 14, 2021 at 19:14
  • 2
    @Laurel That answer of yours actually explains why there is no CB with Go regexps, I believe that can be safely used to close the question. Nov 14, 2021 at 20:36
  • 20
    @WiktorStribiżew Perhaps you could post an answer explaining why you chose to close the question as "no-repro", or whatever reason you used? That's part of the OP's question, and it would be helpful to get an answer from one of the close voters.
    – cigien
    Nov 14, 2021 at 21:51

0

You must log in to answer this question.