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

Potential catastrophic backtracking #10002

Comments

@davisjam
Copy link
Contributor

@davisjam davisjam commented Feb 22, 2018

One of the regexes in eslint is vulnerable to catastrophic backtracking.

@nzakas says this isn't a problem as used in eslint:

Oh yeah, that’s basically just used to insert data into placeholders for our error messages. So we can have a message like this:

“Expected {{count}} spaces.”

And be able to insert a value for “count” without doing string concatenation.

We did this in order to avoid pulling in a whole library like Mustache. Given that there are whole templating libraries on the server, I can’t imagine why someone would want to use this.

Perhaps a comment to warn future copy/pasters might be in order, however.

Here's a description of the problematic pattern and an attack string.

{
"pattern" : "\{\{\s*([^{}]+?)\s*\}\}",
"nPumpsFor10Sec" : "48325",
"filesIn" : [
[
"lib/util/interpolate.js"
]
],
"blowupCurve" : {
"r2" : 0.996141596724248,
"parms" : [
3.10391182858704e-08,
1.82075786106333
],
"type" : "POWER"
},
"attackFormat" : {
"suffix" : "{\t{",
"pumpPairs" : [
{
"pump" : "a",
"prefix" : "{{\t"
},
{
"pump" : "\t",
"prefix" : "a"
}
]
},
"stringLenFor10Sec" : 96657
}

@eslint eslint bot added the triage label Feb 22, 2018
@ljharb

This comment has been minimized.

Copy link
Contributor

@ljharb ljharb commented Feb 22, 2018

Since this would have to be caused by a malicious rule, and the "victim" of the attack would have to enable the rule (or the shared config providing it) themselves, this doesn't seem worrying at all.

@davisjam

This comment has been minimized.

Copy link
Contributor Author

@davisjam davisjam commented Feb 22, 2018

Agreed, not a problem as currently used in eslint. But since people like to copy/paste regexes, thought I would let you know about it.

@platinumazure

This comment has been minimized.

Copy link
Member

@platinumazure platinumazure commented Feb 24, 2018

Can the regex be improved to prevent catastrophic backtracking without changing the function at all? If so, I would love to see a pull request.

If not, though, I agree that this isn't worth worrying about.

davisjam added a commit to davisjam/eslint that referenced this issue Feb 24, 2018
Change template substitution regex to exclude fields with whitespace.
This addresses possible O(n^2) catastrophic backtracking behavior.

Very unlikely to be exploited. For eslint#10002.
@davisjam

This comment has been minimized.

Copy link
Contributor Author

@davisjam davisjam commented Feb 24, 2018

Sure. See #10019.

davisjam added a commit to davisjam/eslint that referenced this issue Feb 24, 2018
Change template substitution regex to exclude fields with whitespace.
This addresses possible O(n^2) catastrophic backtracking behavior.

Very unlikely to be exploited. For eslint#10002.
davisjam added a commit to davisjam/eslint that referenced this issue Feb 24, 2018
Change template substitution regex to exclude fields with whitespace.
This addresses possible O(n^2) catastrophic backtracking behavior.

Very unlikely to be exploited. For eslint#10002.
@not-an-aardvark not-an-aardvark added bug core accepted and removed triage labels Feb 25, 2018
This was referenced Mar 22, 2018
@eslint eslint bot locked and limited conversation to collaborators Aug 28, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
You can’t perform that action at this time.