MongoDB ReDOS тест - PullRequest
       41

MongoDB ReDOS тест

0 голосов
/ 26 октября 2018

Я читал о 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+)+$'}});

Это оценивается немедленно и возвращает ноль.

Есть идеи, как MongoDB может так быстро это оценить?

1 Ответ

0 голосов
/ 25 апреля 2019

Согласно Документам MongoDB

MongoDB использует Perl-совместимые регулярные выражения (т.е. «PCRE») версии 8.41 с поддержкой UTF-8.

Также здесь указано для обработки регулярных выражений, предоставленных пользователем

Механизм PCRE позволяет вам установить пределы рекурсии . Чем ниже ваши пределы, тем лучше защита от ReDoS, но тем выше риск прерывания законных регулярных выражений, которые найдут действительное совпадение, если будет немного больше времени. Низкие пределы рекурсии могут помешать длинным регулярным выражениям. Малое время ожидания может прервать поиск в больших файлах слишком рано.

PCRE использует жесткое ограничение на число итераций в соответствии с Википедия

PCRE имеет жесткое ограничение глубины рекурсии, Perl не

С параметрами сборки по умолчанию "bbbbXcXaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" = ~ /.X(.+)+X/ не будет соответствовать из-за переполнения стека, но Perl будет соответствовать этому правильно. Perl использует кучу для рекурсии и не имеет жесткого ограничения для глубины рекурсии, тогда как PCRE имеет жесткое ограничение времени компиляции.

К сожалению, я не смог понять, какой фактический жесткий предел применяет Mongo для глубины рекурсии PCRE.

для получения более подробной информации о глубине рекурсии PCRE, проверьте этот ответ

...