1391654 - Endless loop in RegExp matching - Non-backtracking Regexps

Status: NEW

(Core :: JavaScript Engine, enhancement, P3)

Description

[Honza Bambas (:mayhemer)]

Attachment: Test case scratchpad

String:

HttpChannelParent RecvAsyncOpen [this=0x7f0a701db540 uri=https://www.google.com.tw/gen_204?atyp=i&ct=slh&cad=&ei=foqWWfWyJ8aE8gXcwoLIBQ&m=HV&t=C&s=1&v=2&pv=0.8723043228283538&me=1:1503038079533,x:1,V,0,0,1301,668:0,N,1,foqWWfWyJ8aE8gXcwoLIBQ:0,R,1,3,13,22,120,47:0,R,1,35,166,175,600,76:0,R,1,41,166,277,600,94:0,R,1,47,166,397,600,94:0,R,1,53,166,517,600,76:0,R,1,60,166,619,600,76:2,B,1610:84,h,1,35,o:1658,h,1,41,i:718,M,2,,1,1,41:73,c,194,283:1,e,C&zx=1503038082072]

Regexp:

^HttpChannelParent RecvAsyncOpen \[this=((?:(?:0x)?[A-Fa-f0-9]+)|(?:\(null\))|(?:\(nil\))) uri=((?:,?[^\s])*), gid=([\d]+) topwinid=((?:0x)?[A-Fa-f0-9]+)\]$

(no flags set on the regexp)


just do string.match(regexp) and the loop starts.

Note that the same issue happens in Chrome too, haven't tried any other browser.  This is likely not a regression, just an edge case.

Comment 1

[Naveed Ihsanullah [:naveed]]

Is there a Chrome bug we can reference for this? We share a regex implementation so a fix in one place can likely be applied in both.

Comment 2

[André Bargull [:anba]]

(In reply to Naveed Ihsanullah [:naveed] from comment #1)
> Is there a Chrome bug we can reference for this? We share a regex
> implementation so a fix in one place can likely be applied in both.

There are a few issues on the V8 bug tracker for catastrophic backtracking <https://bugs.chromium.org/p/v8/issues/list?can=1&q=catastrophic>, most are either closed as dups or won't fixed. 

The backtracking happens in `((?:,?[^\s])*)` (and because there's no match in the input string): [^\s] also matches ",", so the regular expression is similar to (if you squint a bit) `(a?[ab])*c`. And matching `/(a?[ab])*c/.exec("ab".repeat(30))` also takes some time.

Comment 7

[Tooru Fujisawa [:arai]]

https://bugs.chromium.org/p/chromium/issues/detail?id=1125234#c11

We are currently looking into non-backtracking engine to solve these kinds of issues, see https://crbug.com/v8/10765.

Comment 8

[Iain Ireland [:iain]]

Update: an experimental prototype of the non-backtracking engine has landed in V8. I'm keeping an eye on it. When it's mature, we will consider importing it.

Comment 12

[BugBot [:suhaib / :marco]]

In the process of migrating remaining bugs to the new severity system, the severity for this bug cannot be automatically determined. Please retriage this bug using the new severity system.

Comment 15

[Iain Ireland [:iain]]

Update: as of January 2026, the non-backtracking engine in upstream irregexp is still marked as experimental, which means that it isn't ready for fuzz testing yet.