Всем привет! Я Даниил, java разработчик в Just AI, и в этой статье я расскажу, как мы столкнулись с проблемой backtracking’а в регулярных выражениях и как ее решили с помощью библиотеки re2j.
Вот что будет в статье:
каким образом проблема бэктрекинга в регулярных выражениях настигла и нас
как мы с ней боролись, используя бибилотеку re2j
какие сложности и неочевидные нюансы работы с re2j вас могут ожидать
Что такое этот ваш бэктрекинг?
В двух словах, это проблема, возникающая при определенных условиях, когда мы начинаем выполнять полный перебор, что приводит в экспоненциальному росту времени выполнения поиска.
Чаще всего проблема встречается в случаях, когда регулярное выражение приходит извне, т.е. его задает клиент, а мы исполняем и соответственно не контролируем то, что там будет написано.
По теме рассказано и написано много, но уверен, что я не последний, кто поднимает ее.
В статье ребята подробно разобрали, откуда берется эта проблема движков регулярных выражений, и включили ссылки на хорошие материалы, так что рекомендую ее прочитать.
Как мы столкнулись с этой проблемой
Мы делаем JAICP - платформа, позволяющая создавать чат-ботов и удобно работать с информацией, проходящей через них. Через ботов могут проходить чувствительные данные, поэтому мы тщательно следим, что они не попали не в те руки. Для этого мы маскируем / обфусцируем информацию.
Для наглядности результат обфускации выглядит примерно следующим образом:
Ключевым моментом является то, что клиенты могут самостоятельно задавать регулярные выражения
. Тем самым указывая, какие данные являются чувствительными и на что нужно эти данные заменить.
Ловим проблему
Теперь мы знаем, что у нас за задача. Для решения мы будем использовать всем привычные регулярные выражения в Java, но вот подойдут ли они нам под все условия в стандартном виде?
Давайте посмотрим на один достаточно безобидный пример, который у нас является базовым сценарием использования. А именно сокрытие email адреса в сообщениях пользователей:
Т.е. мы заменяем найденные email адреса на xxxx@xxxx.xx, все просто. Используем для поиска email’ов следующее регулярное выражение:
[a-z0-9!#$%&'*+/=?^_{|}~-]+(?:\\.[a-z0-9!#$%&'*+/=?^_{|}~-]+)*@(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\\\\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?
Вместо данного примера пользователь может добавить любое регулярное выражение, какое захочет.
Посмотрим, сколько будет выполняться следующий код, использующий стандартный java движок:
String inputText = TestUtils.getRandomLongWord("test@test.com");
Matcher matcher = Pattern.compile(TestUtils.emailRegex).matcher(inputText);
matcher.replaceAll("XXX@XXX.XX");
В данном и последующих примерах мы будем генерировать рандомный длинный текст, встраивая туда искомый фрагмент. В примере выше это вымышленный email адрес.
...+UUID.randomUUID()+"test@test.com"+UUID.randomUUID()
Вызов randomUUID делаем в нашем примере 500 раз, а искомый текст вставляем после каждого 10ого вызова. Замеры времени производились на i7-10510U CPU 1.80GHz × 8 и jdk 1.8
Время выполнения-36 милисекунд
Ничего страшного не произошло, выполнилось быстро, без каких-либо проблем, но давайте на всякий случай сделаем поиск в тексте, в котором нет email адреса.
Все то же самое, но
UUID.random()+UUID.random()
String inputText = TestUtils.getRandomLongWord("test@test.com");
Matcher matcher = Pattern.compile(TestUtils.emailRegex).matcher(inputText);
matcher.replaceAll("XXX");
Время выполнения-8879 милисекунд
???? кажется, мы поймали проблему backtracking’а.
Решение проблемы с email
Для решения возникшей проблемы мы воспользуемся библиотекой Re2j.
Эта библиотека позволяет выполнять регулярные выражения за линейное время, используя в своей основе не стандартный NFA подход для построения движков регулярных выражений, а DFA вместо него.
Не хочется повторяться и заострять внимание на теоретических моментах, поэтому приложу ссылки для тех, кому будет интересно покопать глубже в эту область: ссылка 1 и ссылка 2
Здесь хочется отметить, что эта библиотека была создана для случаев, когда мы не знаем, какое регулярное выражение придет нам на вход, а это как раз и есть наш случай!
Неужели Re2j действительно поможет нам избежать наших 9 секунд
? Давайте посмотрим! Для проверки нам достаточно лишь заменить стандартный Pattern
на com.google.re2j.Pattern
com.google.re2j.Pattern.compile(emailRegex)
.matcher(TestUtils.getRandomLongWord(""))
.replaceAll("XXX")
Теперь наше время выполнения примерно 88 милисекунд
????????????
Выглядит круто!
Но давайте, перед тем как делать поспешные выводы и начинать во всю использовать данную библиотеку, проведем пару экспериментов и замеров, чтобы понять, для каких же кейсов эта библиотека подходит лучше всего.
Что там по производительности?
Для этих целей мы будем использовать JMH benchmark - популярный инструмент для замера времени выполнения java кода.
Сама логика внутри бенчмарка по сути своей ничем не отличается от примеров выше:
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@Fork(value = 1)
@Warmup(iterations = 2)
@Measurement(iterations = 5)
public void standartRegexWithEmailDataBenchmark(MyState myState, Blackhole blackhole) {
myState.standartEmailRegex
.matcher(myState.emailInputTextWords)
.replaceAll("XXX");
}
Где standartEmailRegex
это java.util.regex.Pattern.compile(TestUtils.emailRegex)
Среднее время работы replaceAll для паттерна с email:
Стандартный java pattern -
0.004 секунды
Re2j pattern -
0.002 секунды
Видно, что re2j показал результат даже немного лучше стандартного варианта, но главное, что не хуже, а значит, можно не бояться использовать его и для случаев, когда нагрузка велика.
Как насчет кейса с большим словарем?
Re2j на практике выглядит впечатляюще, но для поставленной задачи также стоит рассмотреть кейс, когда понадобится найти сопоставление с большим словарем.
Посмотрим на примере словаря американских городов: Бостон, Чикаго, Вашингтон... Он в свою очередь превращается в регулярное выражение: Бостон|Чикаго|Вашингтон...
Мы используем другие данные, не города, но для примера я достал все города США с сайта вот таким страшным или не очень js выражением:
Array.from(document.getElementsByClassName("topic-content pt-sm-15")[0].getElementsByTagName("section")).slice(1).flatMap(x => Array.from(x.children[1].children)).map(x => x.outerText)
Итого получился словарь размером1950
элементов, меньше, чем у нас в словаре, но все же выглядит внушительно.
Получается у нас есть классический java.util.regex
Pattern
java.util.regex.Pattern.compile(String.join("|", TestUtils.usCitiesAndTowns))
И com.google.re2j
Pattern
com.google.re2j.Pattern.compile(String.join("|", TestUtils.usCitiesAndTowns));
Во всех наших примерах паттерны выглядят полностью одинаково, но re2j не полноценно заменяет интерфейс стандартных регулярных выражений в java, поэтому нужно проверять github библиотеки.
Здесь мы также воспользуемся JMH для замера времени выполнения.
Среднее время работы replaceAll для паттерна с городами:
Стандартный java pattern -
0.147 секунды
Re2j pattern -
0.625 секунды
Они говорят нам о том, что вариант с Re2j
в 4 с лишним раза медленнее
, чем стандартный java regex????
А что там с размером паттерна?
Еще одним неочевидным показателем, который стоит проверить, является размер нашего скомпилированного патерна.
Когда мы пишем, например, Pattern.compile("\\\\d{2}")
, то даже не задумываемся, что размер такого объекта может быть проблемой.
А может ли?
Для замера мы будем использовать ObjectSizeCalculator.getObjectSize
из пакета nashorn
, который уже не доступен в версиях JDK новее, чем 8, но в JDK 8 его вполне можно использовать.
А замерять мы будем вот такую конструкцию:
Pattern.compile(String.join("|", TestUtils.usCitiesAndTowns)
где TestUtils.usCitiesAndTowns
- это огромный словарь из примера выше
Итого финальный вызов выглядит следующим образом: ObjectSizeCalculator.getObjectSize(Pattern.compile(String.join("|", TestUtils.usCitiesAndTowns)))
com.google.re2j.Pattern
- 1026872 bytes (~1mb)java.util.regex.Pattern
- 197608 bytes (~0.2mb)
Получил разницу в 5 раз!!! ????
Паттерн на re2j занимает места в 5 раз больше
, чем стандартный.
Даже наш все-таки не огромный словарь занимает 1 мегабайт памяти, а словарь может быть больше на порядки. Также может понадобиться держать наш паттерн в нескольких компонентах, и тогда будет тратиться достаточно много лишней памяти.
Заключение
Мы рассмотрели возможности библиотеки re2j с разных сторон и подсветили важные и порой неочевидные ее недостатки.
И главное, показали, что с помощью re2j можно решить проблему backtreking’а в регулярных выражениях и какой ценой это дается.
Подводя итог:
Главной задачей данной библиотеки является защита от долгого выполнения регулярных выражений в случаях, когда регулярные выражения задаёт пользователь извне.
При использовании re2j стоит учитывать тот тип данных, который у вас есть. А также те условия, для которых вы собираетесь использовать библиотеку, потому что:
Производительность решения может показывать противоположные результаты
Скомпилированный Pattern будет занимать в разы больше места, и это может стать проблемой.
Re2j не поддерживает весь синтаксис регулярных выражений, который поддерживает стандартная java реализация.
P.S. Весь код доступен на github.
Комментарии (10)
OldNileCrocodile
29.06.2022 22:56Если ревнивые квантификаторы не поддерживаются, Вы можете использовать атомарные группы. Атомарные группы = не ссылаемые группы, которые делают позиции, которые подходят под эту группу НЕВОЗВРАТНЫМИ.
Синтаксис: (?>group)
Для строки ".*+"x надо писать
"(?>.*)"x
Conung_ViC
30.06.2022 08:52-1так проблема в том, что эти регэкспы пишут не прогеры, а пользователи системы. И они явно не будут заморачиваться с жадными квантификаторами или группами...
aleksandy
30.06.2022 09:08+2Как тут не вставить бессмертную цитату Фридла?
У вас есть проблема. Вы решили использовать регулярные выражения, чтобы её решить. Теперь у вас две проблемы.
Beholder
30.06.2022 09:59+2Re2j не поддерживает весь синтаксис регулярных выражений, который поддерживает стандартная java реализация
Вот это надо выделить особо, потому что у конечных автоматов есть свои непреодолимые ограничения.
Ну а вообще позволять клиентам по сути выполнять свой код - это "ой".
OldNileCrocodile
А почему бы не отключить backtracking с помощью "ревнивых" Possessive quantifiers? Просто добавьте плюс к квантификатору. Пример: ".*+" сопоставит только строки, обрамлённые двойными кавычками и только их. Для строки "abc"x не вернёт ничего. А с жадным ".*" получим подстроку "abc". Ниже скинул их синтаксис. Также в догонку скинул ленивые.
Ревнивые:
*+, ?+, ++.
Ленивые:
*?, ??, +?
BugM
Иногда текст регэкспа вводит пользователь. Это очень удобная фича в интерфейсе для продвинутых пользователей.
Re2j нужен если вы хотите быть уверены что ваш код гарантированно отработает за конечное время.
ris58h
Конечное или линейное?
BugM
Если мне не изменяет память там квадрат. Длина регэкспа умножить на длину строки в которой ищем. Так что скорее конечное, а не линейное.
OldNileCrocodile
С backtracking и grouping вполне, время может быть экспоненциальным, или же 2^n. Это если начать сканить все подмножества множества символов строки.
OldNileCrocodile
Если Вы имеете в виду под конечным временем "постоянное", то нет. И даже квадрат уже не линейное время, а полиномиальное.