Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Avoid catastrophic backtracking when parsing #97

Closed
jr22 opened this issue Sep 30, 2021 · 11 comments · Fixed by #100
Closed

Avoid catastrophic backtracking when parsing #97

jr22 opened this issue Sep 30, 2021 · 11 comments · Fixed by #100

Comments

@jr22
Copy link

jr22 commented Sep 30, 2021

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
Copy link
Member

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
Copy link

dnsmob commented Oct 11, 2021

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
Copy link
Member

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
Copy link

dnsmob commented Oct 14, 2021

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
Copy link

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
Copy link
Member

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
Copy link

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
Copy link
Member

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

@mbostock mbostock reopened this Mar 27, 2022
@mbostock
Copy link
Member

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

@mbostock mbostock changed the title Prioritize d3-color DDoS fix Avoid catastrophic backtracking in regular expressions when parsing colors Mar 27, 2022
@mbostock mbostock changed the title Avoid catastrophic backtracking in regular expressions when parsing colors Avoid catastrophic backtracking when parsing Mar 27, 2022
@mbostock
Copy link
Member

mbostock commented Mar 27, 2022

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.

This was referenced Mar 27, 2022
@mbostock
Copy link
Member

mbostock commented Mar 28, 2022

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+

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

Successfully merging a pull request may close this issue.

5 participants