node.js - MongoDB ReDOS 测试

Question

我正在阅读有关 ReDOS 的内容。 https://en.wikipedia.org/wiki/ReDoS

如果您在 Node.js 中运行此代码，似乎:

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

运行大约需要 7821 毫秒。

但是如果我向 MongoDB 添加相同的值:

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

这会立即得到评估并返回 null。

知道 MongoDB 如何能够如此快速地评估它吗？

Answer 1

根据 MongoDB Docs

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

也是stated here用于处理用户提供的正则表达式

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 根据 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.

不幸的是，我无法了解 Mongo 对 PCRE 递归深度应用的实际硬限制。

有关 PCRE 递归深度的更多详细信息，请查看此 answer