Avoid catastrophic backtracking when parsing

[jr22]

Hello!

Given the security vulnerability raised here, can the work in d3/d3-color#89 please be prioritized? I would like to fix the security vulnerability in my application ASAP.

Thank you!

[mbostock]

Is your application parsing user-specified color strings, i.e., are you passing user-generated content to d3-color parsing methods? Most applications do not, and so in practice, most of these security vulnerabilities are false positives.

[dnsmob]

considering they can consistently reproduce, it's hard to call false positive though :( i'm not really familiar with what is possible to do with these methods, but is it not the case of simply limiting the number of characters in the string that the method rgb can take?

[mbostock]

I wasn’t disputing that the regular expression is prone to catastrophic backtracking, just that most applications don’t pass user input to d3.color and related methods, and hence are not vulnerable.

[dnsmob]

cool, we're on the same page here -- but security warnings trigger the hair in the back of the neck of tech managers, so... ;)

does my suggestion of limiting the number of characters make sense tho? i'm sort of assuming that function deals with AARRGGBB values only, hence limiting the loop would be enough?

[stefferd]

Agreeing with both gives a security risk that could be considered as a false positive. But still pops up on most security scans. Would like that the suggested fix is adopted.

[mbostock]

My understanding is that limiting the input length is not sufficient to address the vulnerability, and that we probably need to fix this by abandoning regular expressions entirely say in favor of a tokenizer parser, which is a lot of work.

[EnsisAeternus]

I am also running into the problem of a security scanner flagging this issue, questionable though the severity of the issue is and unlikely that it can be exploited. It does appear that the vulnerability can be addressed by limiting the input string size though because the problem is in regex runtime exponentially increasing with input length.

[mbostock]

Duplicate of #89. We don’t need a separate issue to track the status of another issue.

[mbostock]

Whoops, that was a PR, not an issue. I’ll retitle this issue.

[mbostock]

I did a little debugging, and based on the report, the catastrophic backtracking may be limited to the percent-format regular expressions? Here’s an example that shows hundreds of steps before failing if you open the regex debugger:

https://regex101.com/r/GeakxZ/1

Edit: Nope, it’s not specific to the percent format. The reRgbInteger will also fail after hundreds of steps.

[mbostock]

The fix ended up being quite trivial. This part of the regular expression was causing the explosion since there are many valid ways it could match the same input (since both the \d* and \.? can match the empty string):

\d*\.?\d+

The fix is instead to enforce that there is only a single way of matching valid input:

(?:\d*\.)?\d+