Regexp with possible exponential backtracking in `package:http_parser`

[bkonyi]

The regexp defined here can possibly encounter exponential backtracking for certain strings. This was identified by this check on the webdev repo and is blocking DWDS and webdev changes from landing.

[brianquinlan]

@natebosch

The relevant regular expression:

final _quotedString = RegExp(r'"(?:[^"\x00-\x1F\x7F]|\\.)*"');

I'm not an expert in regular expressions but I don't see why any backtracking would be necessary.

I tested this expression in Chrome with " + <one thousand '!'> + " and it matched in <100ms. Changing the expression to include ten thousand '!' didn't seem to affect the runtime.

[bkonyi]

I've been told that @lrhn is our resident regular expression expert. Maybe he has some insights?

[brianquinlan]

Ah, I think that I understand this now - I was misreading the regex.

I think that the backtrack can happen because escape patterns (e.g. "\n") can be matched by both the [^"\x00-\x1F\x7F] expression and by \\..

[brianquinlan]

Is this expression actually correct? Because it will match strings such as "\", which presumably isn't a valid string. I haven't actually looked at the context for this code yet ;-)

[brianquinlan]

OK, here are the relevant RFC-2616 definitions:

   A string of text is parsed as a single word if it is quoted using
   double-quote marks.

       quoted-string  = ( <"> *(qdtext | quoted-pair ) <"> )
       qdtext         = <any TEXT except <">>

   The backslash character ("\") MAY be used as a single-character
   quoting mechanism only within quoted-string and comment constructs.

       quoted-pair    = "\" CHAR

       TEXT           = <any OCTET except CTLs,
                        but including LWS>

       CTL            = <any US-ASCII control character
                        (octets 0 - 31) and DEL (127)>

So that regex does seem to capture the RFC-2616 grammar. There is a proposed bug fix to this odd grammar here: https://greenbytes.de/tech/webdav/draft-ietf-httpbis-p1-messaging-16.html#rfc.section.3.2.3

[natebosch]

If we adopt part of the proposed changes could we resolve the backtracking issue?

Can you think of any negative side effects from changing the regex to not match \ without a second character?

final _quotedString = RegExp(r'"(?:[^"\x00-\x1F\x7F\x5C]|\\.)*"');

We would no longer match strings with a trailing \", but that's probably fine - no one should be doing that anyway.

[natebosch]

Just to make sure I'm following correctly - I think the pathological case for backtracking is thousands of adjacent \ wrapped in double quotes.

[brianquinlan]

@natebosch Yep.

@bkonyi Do you have an easy way to run your check with the slightly changed regex:

final _quotedString = RegExp(r'"(?:[^"\x00-\x1F\x7F\\]|\\.)*"');

I think that should disable backtracking because \ will only be matched in one place. But we will no longer match the string "\" ;-)

[brianquinlan]

I'm writing tests to validate that I don't break anything (and tests are good anyway). Here is an interesting case. Right now:

Input: r'"escaped: \" test"'
Parsed r'escaped: \'

But how?

1. The \ gets captured in the [^"\x00-\x1F\x7F] sub-pattern
2. The " following it matches the " at the end of the pattern

[lrhn]

The double matching of \ is indeed the problem.

On an input of, say

var input = r'\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\' + '\n';

the pattern can try to match each \ first using the [^"\x00-\x1F\x7F\x5C], then two at a time using the \\. which matches \\, but not \n.
(You can try the RegExp with a much smaller input, and try adding \s until it gets very slow.)
Using r'\n\n\n\n\n\n\n\n...\n'+'\n' also works (and might feel easier to reason about).

There is an exponential number of possible ways this input can be attempted matched, but none that will succeed (neither part can match the \n since . doesn't match newlines without the dotAll flag), so all the combinations will be attempted.

Adding the \\ to the negative range is a fine fix. That also avoids matching the \ of a \".
The current behavior for r'"escaped: \" test"' is wrong, it should not end at the escaped ". (So the existing RegExp is not correct.)

The RegExp does not seem to perfectly match the specification (with or without spec fix, or adding \\).
The quoted-pair is specified '\' CHAR, and CHAR is %x01-7F (https://www.rfc-editor.org/rfc/rfc5234.html#appendix-B.1), so it should accept newlines, and should not accept \x00. A . accepts \x00 and not \r or \n, and any number of non-ASCII characters too, but I guess we assume input is ASCII/Latin-1.

Then it should be

RegExp(r'(?:["\x00-\x20\x7f\\]|\\[\x01-\x8f])*')

(I understand why the fix wants to not match newlines either, or other weird control characters.)