Open
Bug 1391654
Opened 7 years ago
Updated 4 months ago
Endless loop in RegExp matching - Non-backtracking Regexps
Categories
(Core :: JavaScript Engine, enhancement, P3)
Core
JavaScript Engine
Tracking
()
NEW
Tracking | Status | |
---|---|---|
firefox57 | --- | affected |
People
(Reporter: mayhemer, Unassigned)
References
(Blocks 1 open bug)
Details
(Whiteboard: [js:correctness])
Attachments
(1 file)
993 bytes,
application/x-javascript
|
Details |
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•7 years ago
|
||
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.
Priority: -- → P3
Whiteboard: [js:correctness]
Comment 2•7 years ago
|
||
(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•4 years ago
|
||
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•4 years ago
|
||
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•2 years ago
|
||
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.
Severity: critical → --
Updated•1 year ago
|
Severity: -- → S3
Updated•1 year ago
|
Blocks: sm-runtime
Severity: S3 → N/A
Type: defect → enhancement
Summary: Endless loop in RegExp matching → Endless loop in RegExp matching - Non-backtracking Regexps
You need to log in
before you can comment on or make changes to this bug.
Description
•