MongoDB ReDOS测试

Question

我在读有关ReDOS的文章。 https://zh.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 文档

\n\n

\n

MongoDB 使用 Perl 兼容的正则表达式（即 \xe2\x80\x9cPCRE\xe2\x80\x9d ）版本 8.41，支持 UTF-8。

\n

\n\n

此处还说明了处理用户提供的正则表达式

\n\n

\n

PCRE 引擎允许您设置递归限制。限制越低，针对 ReDoS 的保护就越好，但中止合法正则表达式的风险就越高，这些正则表达式在稍微多一点的时间下就能找到有效的匹配项。低递归限制可能会阻止长正则表达式匹配。超时时间过短可能会过早中止对大文件的搜索。

\n

\n\n

根据维基百科，PCRE 对迭代次数使用硬限制

\n\n

\n

PCRE 对递归深度有硬性限制，Perl 没有

\n\n

使用默认构建选项 "bbbbXcXaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /.X(.+)+X/ 将由于堆栈溢出而无法匹配，但 Perl 会正确匹配。Perl 使用堆进行递归，并且对递归深度没有硬性限制，而 PCRE 有编译时间硬性限制。

\n

\n\n

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

\n\n

有关 PCRE 递归深度的更多详细信息，请检查此答案

\n