fix: Fix ReDoS vulnerability CVE-2021-35065 #49

sttk · 2021-06-24T02:38:32Z

We received a report of ReDoS vulnerability and a suggestion to fix this.
I've sent this pr based on the report.

sttk · 2021-06-24T02:39:06Z

This is the performance test code from the reporter.

const { performance } = require("perf_hooks")
const globParent = require("glob-parent")

const measure = fn => {
  let s = performance.now();
  fn();
  return performance.now() - s;
};

for (const n of [5_000, 10_000, 20_000, 40_000, 80_000, 160_000]) {
  const input = "{" + "/".repeat(n);
  const time = measure(() => globParent(input));

  // if the runtime is O(n^2), then this ration will be roughly constant
  const ration = time / (n * n);

  console.log(`${n}:\t${time}ms\t${ration.toExponential(3)}`);
}

sttk · 2021-06-24T02:40:25Z

And the followings are the results on my machine.

Before:

% node -v
v14.15.0
% npm -v
6.14.8
% node perf_test.js 
5000: 32.4567289352417ms  1.298e-6
10000:  103.04731607437134ms  1.030e-6
20000:  382.97598814964294ms  9.574e-7
40000:  1525.007022857666ms 9.531e-7
80000:  6095.382986068726ms 9.524e-7
160000: 24153.12740111351ms 9.435e-7
%

After:

% node -v
v14.15.0
% npm -v
6.14.8
% node perf_test.js 
5000: 0.7545621395111084ms  3.018e-8
10000:  5.009187936782837ms 5.009e-8
20000:  2.1224639415740967ms  5.306e-9
40000:  0.5203690528869629ms  3.252e-10
80000:  1.0246939659118652ms  1.601e-10
160000: 2.1865968704223633ms  8.541e-11

phated · 2021-06-24T02:44:33Z

Let's add a test! cc @RunDevelopment @Trott

sttk · 2021-06-24T04:36:38Z

@phated I've added a test case for this!

Trott · 2021-06-24T04:57:37Z

Oof, looks like I introduced this problem in 32f6d52. Sorry about that.

This fix looks like an improvement to me, and the test results certainly seem to bear that out. But I don't know offhand if it is a partial fix or a complete fix. I'll probably go re-educate myself (yet again) on ReDoS but in the meantime, I wouldn't mind pulling in someone who actually knows about this stuff in detail, if he doesn't mind me tapping him on the shoulder for something that's probably sufficiently mundane that I should be able to figure it out myself. /ping @davisjam Does this change look like a complete fix for the ReDoS here or only a partial one?

Trott · 2021-06-24T05:02:07Z

index.js

@@ -6,7 +6,7 @@ var isWin32 = require('os').platform() === 'win32';

 var slash = '/';
 var backslash = /\\/g;
-var enclosure = /[{[].*\/.*[}\]]$/;
+var enclosure = /[{[][^/\r\n\u2028\u2029]*\/.*[}\]]$/;


Would this suffice (and be a fair bit easier to read as well)?

Suggested change

var enclosure = /[{[][^/\r\n\u2028\u2029]*\/.*[}\]]$/;

var enclosure = /[{[][^/]*\/.*[}\]]$/;

If not, we should probably add a test case that shows it not working.

@Trott The direct solution of this issue is the way as you suggested. But the reporter suggested this solution and we agree with it because we can't accept newlines in a filepath.

If the decision is "we won't accept newlines in a path", then OK. But if the belief is "newlines cannot legitimately appear in a path", then I do not believe that is correct. See https://superuser.com/a/129532/81159. Or try this (which is basically the same thing as in that linked answer):

$ touch 'foo quote> bar' $ ls -lbd foo* -rw-r--r-- 1 trott staff 0 Jun 24 07:04 foo\nbar $

(The quote> thing is zsh console output. Here's basically the same thing in Bourne shell instead.)

sh-3.2$ touch 'foo > bar' sh-3.2$ ls foo* foo?bar sh-3.2$ ls -ldb foo* -rw-r--r-- 1 trott staff 0 Jun 24 07:08 foo\nbar sh-3.2$

As a onetime file system tester, I'm with @Trott here: newlines are valid path elements in many file systems.

This regex is much improved in its performance. However. I did not check the context in which it is used, but if one of the "match a substring within this string" APIs is used then the performance can still be problematic.

Try for example:

let match = '{'.repeat(10*10*10*10*5); console.log('matching'); var res = /[[{[][^/\r\n\u2028\u2029]*\/.*[}\]]$/.exec(match); console.log('done matching') console.log(res)

(This is slow in a Node v12 REPL I found on the web).

The slow performance is because:

The "match anywhere" will basically try starting from each of n open-braces

There is a reachable quantifier that also matches a { (the first *'d group).

So the regex engine will match O(n) of them before rejecting each time -- that makes for O(n^2) behavior.

So, food for thought:

How long are the strings that this regex processes? (In the example above, I'm using a string with 50K characters in it. For shorter strings, the performance is "not great", but perhaps not catastrophic).
2.Are there any additional constraints on the input we could add in? (e.g. enforcing a maximum length, or additional properties that the regex can check) I think there is a possibly-illegible refactoring that would do the trick, but it would be nicer if there is a more maintainable option.

I looked at the project again and it seems like the regex /(^|[^\\])([{[]|\([^)]+$)/ has the same problem for all inputs "(".repeat(n).

Whatever solution is chosen for /[[{[][^/\r\n\u2028\u2029]*\/.*[}\]]$/ should also be applied to /(^|[^\\])([{[]|\([^)]+$)/.

I imagine that ideally, this wouldn't be doing regex matching at all but would instead use some module that does proper parsing for globs. Although I guess there really isn't a single globbing standard to adhere to. Anyway, if no one's looked yet, it might be worth looking at what's out there (to make sure they just don't do regexp matching under the hood).

Another option is to use a linear-time regex engine. For example, you could add re2 as a (somewhat heavy, alas) dependency. It supports all of the features used in these regexes.

(Please @ me if you want further opinions)

@RunDevelopment I think that regex has no problem.

% cat test.js var performance = require('perf_hooks').performance; var globby = /(^|[^\\])([{[]|\([^)]+$)/; var st = performance.now(); globby.test("{" + "/".repeat(500000)); var ed = performance.now(); console.log(ed - st); % node test.js 0.7820440530776978 %

Trott · 2021-06-24T05:38:06Z

OK, brushed up a bit and this looks like a complete fix although this is based on a few minutes of reading and I really wouldn't mind a more knowledgable eye on this.

davisjam · 2021-06-24T14:05:43Z

I am examining.

Edit: After coffee.

davisjam · 2021-06-24T14:34:41Z

test/index.test.js

@@ -224,6 +226,26 @@ describe('glob2base test patterns', function () {

    done();
  });
+
+  it('should not increase calc. time exponentially by \'/\' count [CVE-2021-35065]', function (done) {


Comment says "exponential". This regex will exhibit polynomial growth, not exponential growth.

~~Got it. I'll modify it.~~

I'll remove this case and add a new case to check absolute time.

davisjam · 2021-06-24T15:10:06Z

test/index.test.js

+
+    [50000, 500000].forEach(function(n) {
+      var result1 = measure(n);
+      expect(result1 / result0).toBeLessThan(0.9);


Possibly you should also check for a "reasonable" absolute matching time, instead of just checking for a low-enough relative increase. For example, you could also assert that the 500K string finishes in under 1 second.

~~Got it. I'll add that assertion.~~

I'll remove this case and add a new case to check absolute time.

davisjam · 2021-06-24T15:10:22Z

I left comments @Trott @sttk

phated · 2021-06-26T03:00:31Z

@sttk I believe we should support newlines as are allowed within paths. I wasn't aware they could exist in a path!

sttk · 2021-06-26T03:11:10Z

@phated I was just about to ask you it. I'm also considering about ~~the issue from @RunDevelopment above.~~ '{'.repeat(n) and '['.repeat(n).

sttk · 2021-06-26T05:00:45Z

Mmm, /[{[][^/]*\/.*[}\]]$/.test('{'.repeat(500_000)) also takes a lot of time...

--
This is already mentioned in this comment.

sttk · 2021-06-26T06:08:31Z

I've modified the codes.

Modify the target regex to accept newlines and to avoid ReDoS by '{'.repeat(n) too.
Remove a test case to check relative time.
Add new test cases to check absolute time for '{' + '/'.repeat(n), '{'.repeat(n), and '('.repeat(n).

Trott · 2021-06-26T06:51:18Z

It might be worth considering getting rid of the regular expression altogether and replacing it with rudimentary parsing code like this:

 var lastChar = str.slice(-1);
 var enclosureStart;
 if (lastChar === '}') {
   enclosureStart = '{';
 }

 if (lastChar === ']') {
   enclosureStart = '[';
 }

 if (enclosureStart && str.includes(enclosureStart) &&
     str.indexOf(slash) > str.indexOf(enclosureStart)) {
       str += slash
 }

This code has some shortcomings, but (without thinking about it too hard) I don't think it has any that aren't already present in the regular expression. It even has some modest improvements, like ensuring that brace styles match. (The regexp will match on [/} for example, but this will not.)

Trott · 2021-06-26T07:00:44Z

I rather liked the use of the performance API to check the performance difference, but sure, this works too.

There is at least one more ReDoS lurking somewhere still, even with this change. I'll email you the string that causes it.

phated · 2021-06-29T17:11:11Z

@sttk I think this new RegExp is incorrect. It doesn't account for escaped brackets in a string, such as "{\{abc\/}"

phated · 2021-06-29T17:13:39Z

I'm wondering if we need to take @Trott's recommendation in #49 (comment) to match the start/end brackets correctly 🤔

sttk · 2021-07-03T02:14:41Z

I think there is no definitive solution for ReDoS and the best way is not to use RegExp for repeatable subexpression.
I agree to use @Trott's recommendation above.

sttk · 2021-07-03T02:57:15Z

@phated About escaped brackets, the original and new RegExp of enclosure return same result for your example.
Please tell me the exact specification for enclosure.

$ node
> var enclosureOrig = /[{[].*\/.*[}\]]$/;
undefined
> enclosureOrig.test("{\{abc\/}")
true
> var enclosureNew = /[{[][^/{[]*\/.*[}\]]$/;
undefined
> enclosureNew.test("{\{abc\/}")
true
>

sttk · 2021-07-03T03:11:52Z

I've modified the codes with reference to @Trott's code above.

fix: Fix ReDoS vulnerability CVE-2021-35065

d16d629

sttk force-pushed the fix-redos-vulnerability branch from 2e53333 to da6f8af Compare June 24, 2021 04:28

test: Add a test case for ReDoS vulnerability

723eed9

sttk force-pushed the fix-redos-vulnerability branch from da6f8af to 723eed9 Compare June 24, 2021 04:30

Trott reviewed Jun 24, 2021

View reviewed changes

Trott approved these changes Jun 24, 2021

View reviewed changes

RunDevelopment approved these changes Jun 24, 2021

View reviewed changes

davisjam reviewed Jun 24, 2021

View reviewed changes

fix: Modify regex to accept newlines and to avoid ReDoS by '{'.repeat(n)

9bc351f

fix: Modify to get rid of RegExp enclosure

468dde3

This was referenced Jan 10, 2022

CVE-2021-35065 (High) detected in glob-parent-5.1.2.tgz - autoclosed opensearch-project/sql#369

Closed

CVE-2021-35065 (High) detected in glob-parent-5.1.2.tgz - autoclosed opensearch-project/observability#367

Closed

mend-bolt-for-github bot mentioned this pull request Jan 10, 2022

CVE-2021-35065 (High) detected in glob-parent-5.1.2.tgz three11/accordion#103

Closed

mend-for-github-com bot mentioned this pull request Jan 11, 2022

CVE-2021-35065 (High) detected in multiple libraries - autoclosed snowdensb/dependabot-core#430

Closed

This was referenced Jan 11, 2022

CVE-2021-35065 (High) detected in glob-parent-5.1.2.tgz - autoclosed dreamboy9/spark#21

Closed

CVE-2021-35065 (High) detected in glob-parent-5.1.2.tgz - autoclosed interserver/mailbaby-api-samples#171

Closed

mend-for-github-com bot mentioned this pull request Jan 11, 2022

CVE-2021-35065 (High) detected in glob-parent-5.1.1.tgz, glob-parent-2.0.0.tgz - autoclosed VividCortex/grafana-datasource#77

Closed

1 task

mend-bolt-for-github bot mentioned this pull request Feb 11, 2022

CVE-2021-35065 (High) detected in glob-parent-6.0.0.tgz kapseliboi/eodiro#5

Open

mend-bolt-for-github bot mentioned this pull request Mar 15, 2022

tailwindcss-2.2.2.tgz: 1 vulnerabilities (highest severity is: 7.5) husnuljahneer/next-js-cartio#7

Open

This was referenced Jul 18, 2022

glob-parent before 6.0.1 vulnerable to Regular Expression Denial of Service (ReDoS) timlrx/tailwind-nextjs-starter-blog#505

Closed

Upgrade glob-parent to fix security issue timlrx/tailwind-nextjs-starter-blog#506

Closed

llpaul mentioned this pull request Jan 13, 2023

There is no CVE-2021-35065, Chokidar is not vulnerable paulmillr/chokidar#1191

Open

	var enclosure = /[{[][^/\r\n\u2028\u2029]\/.[}\]]$/;
	var enclosure = /[{[][^/]\/.[}\]]$/;

fix: Fix ReDoS vulnerability CVE-2021-35065 #49

fix: Fix ReDoS vulnerability CVE-2021-35065 #49

Conversation

sttk commented Jun 24, 2021

sttk commented Jun 24, 2021 • edited

sttk commented Jun 24, 2021

phated commented Jun 24, 2021

sttk commented Jun 24, 2021 • edited

Trott commented Jun 24, 2021

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Trott Jun 24, 2021 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

davisjam Jun 24, 2021 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Trott commented Jun 24, 2021

davisjam commented Jun 24, 2021 • edited

Choose a reason for hiding this comment

sttk Jun 26, 2021 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

sttk Jun 26, 2021 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

davisjam commented Jun 24, 2021

phated commented Jun 26, 2021

sttk commented Jun 26, 2021 • edited

sttk commented Jun 26, 2021 • edited

sttk commented Jun 26, 2021

Trott commented Jun 26, 2021 • edited

Trott commented Jun 26, 2021

phated commented Jun 29, 2021

phated commented Jun 29, 2021

sttk commented Jul 3, 2021

sttk commented Jul 3, 2021

sttk commented Jul 3, 2021

sttk commented Jun 24, 2021 •

edited

sttk commented Jun 24, 2021 •

edited

Trott Jun 24, 2021 •

edited

davisjam Jun 24, 2021 •

edited

davisjam commented Jun 24, 2021 •

edited

sttk Jun 26, 2021 •

edited

sttk Jun 26, 2021 •

edited

sttk commented Jun 26, 2021 •

edited

sttk commented Jun 26, 2021 •

edited

Trott commented Jun 26, 2021 •

edited