Хочешь проверить свои знания по JS?
Подпишись на наш канал с тестами по JS в Telegram!
Решать задачи
Регулярные выражения или RegEx широко используются в веб-разработке для поиска по шаблону и валидации ввода. Но практическое использование регулярок связано с определенными рисками по части безопасности и производительности.
В этой статье я расскажу о двух фундаментальных проблемах, о которых вы должны помнить, используя регулярные выражения в JavaScript.
Катастрофический бэктрекинг
Есть два алгоритма регулярных выражений:
- Детерминированный конечный автомат (англ. deterministic finite automaton, DFA) проверяет символ в строке только один раз
- Недетерминированный конечный автомат (англ. nondeterministic finite automaton, NFA) проверяет символ многократно, пока не будет найдено наилучшее соответствие.
JavaScript в своем RegEx-движке использует NFA-подход, а это — причина такого явления как катастрофический бэктрекинг (или катастрофический возврат).
Чтобы лучше это понять, давайте рассмотрим пример регулярного выражения.
/(g|i+)+t/
Это выражение довольно простое. Но не нужно его недооценивать: оно может дорого вам обойтись. Давайте разберем его механизм.
(g|i+)— эта группа проверяет, начинается ли строка с «g» или «i» (причем «i» может встречаться как один раз, так и несколько).- Следующий «+» проверяет, встречается ли предыдущая группа один или более раз.
- Строка должна заканчиваться буквой «t».
Этому шаблону будут соответствовать следующие строки:
git giit gggt gigiggt igggt
Теперь давайте измерим время, которое потребовалось для выполнения этого регулярного выражения с валидной строкой. Я буду использовать метод console.time().
Мы видим, что выполнение кода было довольно быстрым, несмотря на то, что строка длинновата.
Но вы удивитесь, когда увидите, сколько времени потребуется на проверку невалидного текста.
В примере, приведенном ниже, строка заканчивается на букву «v», что, согласно нашему RegEx, невалидно. Работа кода продолжалась 429 миллисекунд, что примерно в 400 раз медленнее, чем проверка валидной строки.
Основная причина такой разницы в производительности — использование в JavaScript алгоритма NFA.
RegEx-движок в JavaScript проверяет последовательность символов при первой успешной попытке валидации и продолжает работу. Потерпев неудачу в какой-либо конкретной позиции, он возвращается к предыдущей позиции и ищет альтернативный путь.
Когда бэктрекинг (возврат) становится слишком сложным, алгоритм начинает потреблять больше вычислительной мощности, что приводит к катастрофическому бэктрекингу.
Примечание. Чтобы узнать сложность бэктрекинга, вы можете зайти на сайт regex101.com и протестировать свое регулярное выражение. Если говорить о нашем выражении, regex101.com показывает, что для валидации giiiit необходимо сделать 10 шагов, а для валидации giiiiv — 189.
ReDoS-атака на окружение NodeJS
При ReDoS-атаке катастрофический бэктрекинг используется для эксплойта NodeJS-серверов.
Поскольку JavaScript — однопоточный, ReDoS-атаки могут исчерпать цикл событий, что приведет к зависанию сервера до завершения запроса.
Для демонстрации я использую библиотеку Moment.js. В ее версиях до 2.15.2 есть известная ReDoS-уязвимость.
var moment = require('moment');
moment.locale("be");
moment().format("D MMN MMMM");
В этом примере формат даты предполагает 40 символов с 31 дополнительным пробелом. Из-за катастрофического бэктрекинга дополнительные пробелы будут удваивать время выполнения. В моей локальной среде выполнение заняло больше 4 минут.
Виной всему было излишнее использование оператора «+» в регулярном выражении /D[oD]?(\[[^\[\]]*\]|\s+)+MMMM?/. Именно оно было причиной уязвимости Moment.js.
К счастью, эта проблема была обнаружена благодаря Snyk (инструмент для отслеживания уязвимостей) и исправлена в следующих версиях библиотеки.
Как избежать уязвимостей, связанных с использованием RegEx в JavaScript
1. Пишите простые регулярные выражения
Катастрофический бэктрекинг может случиться, когда в выражении есть как минимум три символа с двумя или более включениями *, +, }, стоящими близко друг к другу.
Если вы упростите свои RegEx в JavaScript и будете избегать описанного выше паттерна, вы избежите и катастрофического бэктрекинга.
2. Для задач валидации пользуйтесь библиотеками
Для наиболее частых задач валидации существуют сторонние библиотеки, например, validator.js или express-validator.
На них вполне можно положиться, ведь за ними стоит большое сообщество.
3. Используйте анализаторы RegEx
Вы можете написать собственные RegEx без всяких уязвимостей, пользуясь такими инструментами, как safe-regex и rxxr2. Они проверяют ваше выражение на уязвимости и возвращают его валидность (true / false).
var safe = require('safe-regex');
var regex = /(g|i+)+t/;
console.log(safe(regex)); //false
4. Старайтесь не пользоваться дефолтным RegEx-движком Node
Поскольку этот движок уязвим для ReDoS-атак, лучше им не пользоваться. Переключитесь на альтернативный вариант, например, re2 от Google. Его использование аналогично дефолтному RegEx-движку Node, но при этом вы будете в большей безопасности.
var RE2 = require('re2');
var re = new RE2(/(g|i+)+t/);
var result = 'giiiiiiiiiiiiiiiiiiit'.search(re);
console.log(result); //false
Здесь выражение оценено как false, потому что оно подвержено катастрофическому бэктрекингу.
Ключевые выводы
Катастрофический бэктрекинг — самая распространенная проблема безопасности регулярных выражений. И дело не только в производительности: бэктрекинг также открывает двери ReDoS-атакам для эксплойта NodeJS-серверов.
В этой статье мы разобрали, как работает катастрофический бэктрекинг и ReDoS-атаки, а также — как избежать этих уязвимостей.
Надеюсь, эта статья поможет вам защитить ваше приложение.
Перевод статьи «Threats of Using Regular Expressions in JavaScript».
