Is there no catastrophic backtracking in Go regex?

user_7643942 0
Viewed 400

While testing this regex today on regex101.com, ^([a-z0-9]+(-)*)*([a-z0-9])$ I got "catastrophic backtracking" error when I tested it on this string:

with flavor PHP:

aaaaaaaaaaa-aaaaT

with flavor Python:

aaaaaaaaaaa-aaaaT

with flavor ECMAScript this longer string got a timeout that 'may be an indication of catastrophic backtracking'

aaaaaaaaaaa-aaaaaaaaaaaaaaaaaT

with flavor Java 8 timeout with string

aaaaaaaaaaa-aaaaaaaaaaaaaT

but flavor Go gave no error or timeout event with much longer such strings. Instead it shows no match (0.0ms)

So can I ignore that error/warning when my regex is being used in Go?

I am interested in the reason for this too, but above is my key question.

backtracking go regex
1 Answers

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, ...

user_76439420
Related