MongoDB ReDOS test

Question

I was reading about ReDOS. https://en.wikipedia.org/wiki/ReDoS

It seems if you run this code in Node.js:

console.time('aaa');
/^(a+)+$/.test('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!')
console.timeEnd('aaa');

it takes around 7821ms to run.

But if I add the same value to MongoDB:

db.users.insert({name: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!"});
db.users.findOne({name: { '$regex': '^(a+)+$'}});

This gets evaluated immediately and it returns null.

Any idea how MongoDB is able to evaluate it so fast?

Answer 1

According to MongoDB Docs

MongoDB uses Perl compatible regular expressions (i.e. “PCRE” ) version 8.41 with UTF-8 support.

Also it's stated here for Handling Regexes Provided by The User

The PCRE engine allows you to set recursion limits. The lower your limits the better the protection against ReDoS, but higher the risk of aborting legitimate regexes that would find a valid match given slightly more time. Low recursion limits may prevent long regex matches. Low timeouts may abort searches through large files too early.

PCRE uses hard limit on number of iterations according to Wikipedia

PCRE has a hard limit on recursion depth, Perl does not

With default build options "bbbbXcXaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /.X(.+)+X/ will fail to match due to stack overflow, but Perl will match this correctly. Perl uses the heap for recursion and has no hard limit for recursion depth, whereas PCRE has a compile time hard limit.

Unfortunately I couldn't get what actual hard limit does Mongo apply on PCRE recursion depth.

for more details on PCRE recursion depth check this answer