Кровавый случай, вызванный регулярным выражением, делает онлайн-процессор на 100% ненормальным!

автор:Чен Шуи| Эта статья взята изОблако Tencent + сообщество Чен Шуистолбец

Несколько дней назад информация о мониторинге онлайн-проекта внезапно сообщила о сбое.После загрузки на машину я проверил использование связанных ресурсов и обнаружил, что загрузка ЦП составляет почти 100%. С помощью инструмента дампа потока, который поставляется с Java, мы экспортировали информацию о стеке проблемы.

Мы видим, что все стеки указывают на метод с именем validateUrl, и в стеке более 100 таких сообщений об ошибках. Проверяя код, мы знаем, что основная функция этого метода — проверить, является ли URL-адрес законным.

Странно, как регулярное выражение может вызвать высокую загрузку ЦП. Чтобы выяснить проблему воспроизведения, мы извлекли код ключа и провели простой модульный тест.

public static void main(String[] args) {
    String badRegex = "^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\\\/])+$";
    String bugUrl = "http://www.fapiao.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf";
    if (bugUrl.matches(badRegex)) {
        System.out.println("match!!");
    } else {
        System.out.println("no match!!");
    }
}

Когда мы запускаем приведенный выше пример, мы видим через монитор ресурсов, что существует процесс с именем java. Загрузка ЦП резко возрастает до 91,4%.

Увидев это, мы можем в основном сделать вывод, что это регулярное выражение является убийцей, из-за которого загрузка ЦП остается высокой!

Итак, мы сосредоточим наше устранение неполадок на этом регулярном выражении:

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\/])+$

Это регулярное выражение выглядит нормально и может быть разделено на три части:

Первая часть соответствует протоколам http и https, вторая часть соответствует символу www., а третья часть соответствует многим символам. Я долго смотрел на это выражение в оцепенении, но серьезных проблем не нашел.

На самом деле ключевой причиной высокой загрузки ЦП здесь является следующее: ** Реализация механизма, используемая регулярными выражениями Java, представляет собой автоматы NFA, и этот механизм регулярных выражений будет выполнять поиск с возвратом при сопоставлении символов. ** Как только происходит возврат, время, затрачиваемое на него, становится очень большим, что может составлять минуты или часы, в зависимости от количества и сложности возврата.

Увидев это, вы можете не знать, что такое возврат, и можете немного запутаться. Не беда, начнем немного с принципа регулярных выражений.

Механизм регулярных выражений

Регулярные выражения — это очень удобный символ сопоставления, но для достижения такого сложного и мощного синтаксиса сопоставления необходимо реализовать набор алгоритмов, и то, что реализует этот алгоритм, называется механизмом регулярных выражений. Проще говоря, есть два способа реализовать механизм регулярных выражений:Автоматы DFA(детерминированные конечные автоматы) иавтомат NFA(Недетерминированный конечный автомат).

У этих двух видов автоматов есть свои отличия, и я не собираюсь здесь вдаваться в их принципы. Проще говоря, временная сложность автоматов DFA линейна и более стабильна, но их функциональность ограничена. Временная сложность NFA относительно нестабильна, иногда она очень хороша, иногда не очень, хороша она или нет, зависит от регулярного выражения, которое вы пишете. Но преимущество в том, что NFA является более мощным, поэтому языки, включая Java, .NET, Perl, Python, Ruby, PHP и другие языки, используют NFA для реализации своих регулярных выражений.

Так как же автодобавление NFA соответствует? Проиллюстрируем следующими символами и выражениями.

text="Today is a nice day."
regex="day"

Важно помнить, что NFA основан на сопоставлении регулярных выражений. То есть, NFA будет автоматически считывать символы регулярного выражения один за другим, а затем сопоставлять их с целевой строкой.Если совпадение успешно, заменить следующий символ регулярного выражения, в противном случае продолжить сравнение со следующим символ целевой строки. Может быть, вы не очень хорошо это понимаете, ничего страшного, давайте разберем это пошагово на приведенном выше примере.

Сначала получите первое совпадение с регулярным выражением: d. Так он сравнивается с символами строки.Первый символ строки это Т, если он не совпадает, то он будет заменен на следующий. Второй — o, и он тоже не совпадает, а затем замените его следующим. Третий — d, если он совпадает, то читаем второй символ регулярного выражения: a.
Прочитайте второе совпадение регулярного выражения: a. Затем продолжите сравнение с четвертым символом a строки и снова сопоставьте. Затем прочитайте третий символ регулярного выражения: y.
Читается третье совпадение регулярного выражения: y. Затем продолжите сравнение с пятым символом y строки и снова сопоставьте. Попытаться прочитать следующий символ регулярного выражения и обнаружить, что его нет, после чего совпадение заканчивается.

Вышеприведенный процесс сопоставления является процессом сопоставления автомата NFA, но фактический процесс сопоставления будет намного сложнее, чем этот, но принцип остается неизменным.

Откат автоматов NFA

Зная, как NFA выполняет сопоставление строк, мы можем поговорить о фокусе этой статьи: поиске с возвратом. Чтобы лучше объяснить возврат, мы также используем следующий пример для объяснения.

text="abbc"
regex="ab{1,3}c"

Цель приведенного выше примера относительно проста: сопоставить строки, начинающиеся с a, заканчивающиеся на c и содержащие 1–3 символа b между ними. Процесс разбора NFA выглядит следующим образом:

Сначала прочитайте первый символ совпадения a регулярного выражения, сравните первый символ a строки и найдите совпадение. Итак, прочитайте второй символ регулярного выражения.
Прочитайте второй символ соответствия b{1,3} регулярного выражения, сравните его со вторым символом b строки и найдите совпадение. Но из-за того, что b{1,3} представляет 1-3 строки b, и из-за жадной природы автоматов NFA (то есть, чтобы соответствовать как можно большему количеству), он не будет читать следующее регулярное выражение в это время. использует b{1,3} для сравнения с третьим символом b строки и обнаруживает, что он все еще соответствует. Поэтому продолжайте использовать b{1,3} для сравнения с четвертым символом c строки и обнаружите, что совпадений нет. В этот момент происходит возврат.
Как работает возврат? После того, как произойдет возврат, четвертый символ c прочитанной нами строки будет выплюнут, а указатель вернется на позицию третьей строки. После этого программа считывает следующий оператор c регулярного выражения, считывает для сравнения следующий символ c текущего указателя и находит совпадение. Итак, следующий оператор читается, но он здесь.

Давайте вернемся и посмотрим на предыдущее регулярное выражение, которое проверяет URL:

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\/])+$

Рассматриваемый URL-адрес:

http://www.fapiao.com/dzfp-web/pdf/download?request=6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf

Разделим это регулярное выражение на три части:

Первая часть: протокол проверки.^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://).
Вторая часть: проверьте доменное имя.(([A-Za-z0-9-~]+).)+.
Третья часть: параметры проверки.([A-Za-z0-9-~\\/])+$.

Мы можем найти протокол проверки регулярных выраженийhttp://С этой частью проблем нет, но при проверке www.fapiao.com он используетxxxx.Проверьте таким образом. Таким образом, процесс сопоставления на самом деле выглядит так:

соответствует www.
соответствует фапяо.
соответствоватьcom/dzfp-web/pdf/download?request=6e7JGm38jf....., вы обнаружите, что из-за жадного сопоставления программа всегда будет читать следующую строку для соответствия и, наконец, обнаружит, что точки нет, поэтому она возвращается одна за другой.

Это первая проблема с этим регулярным выражением.

Другая проблема заключается в том, что в третьей части регулярного выражения мы обнаружили, что рассматриваемый URL-адрес имеет подчеркивание (_) и знак процента (%), а регулярное выражение, соответствующее третьей части, — нет. Это приведет к тому, что длинная строка символов будет сопоставляться раньше, а затем будет найдено несоответствие и, наконец, выполнено откат.

Это вторая проблема с этим регулярным выражением.

решение

Поняв, что возврат является причиной проблемы, он на самом деле уменьшает возврат.Вы обнаружите, что если я добавлю подчеркивание и знак процента в третьей части, программа работает нормально.

public static void main(String[] args) {
    String badRegex = "^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~_%\\\\/])+$";
    String bugUrl = "http://www.fapiao.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf";
    if (bugUrl.matches(badRegex)) {
        System.out.println("match!!");
    } else {
        System.out.println("no match!!");
    }
}

Запуск вышеуказанной программы немедленно распечатаетmatch!!.

Но этого недостаточно.Если в будущем появятся другие URL-адреса, содержащие случайные символы, мы должны изменить их снова. Конечно не реально!

На самом деле в регулярных выражениях есть три шаблона:Жадный режим, ленивый режим, эксклюзивный режим.

В сопоставлении о количестве есть+ ? * {min,max}Четыре раза, если только использовать в одиночку, то они жадный режим.

**Если вы добавите после них лишний символ ?, исходный жадный режим станет ленивым, то есть будет соответствовать как можно меньшему количеству совпадений. ** Но возврат все равно будет происходить в ленивом режиме.TODOНапример следующий пример:

text="abbc"
regex="ab{1,3}?c"

Первый оператор a регулярного выражения соответствует первому символу a строки, соответствующему as . Таким образом, второй оператор b{1,3}? регулярного выражения соответствует второму символу b строки, и совпадение успешно. Из-за принципа минимального соответствия третий оператор c регулярного выражения сопоставляется с третьим символом b строки, и совпадение не найдено. Итак, вернитесь назад и используйте второй оператор b{1,3}? регулярного выражения для сопоставления с третьим символом b строки, и совпадение будет успешным. Затем возьмите третий оператор c регулярного выражения для сопоставления с четвертым символом c строки, и совпадение будет успешным. Итак, все кончено.

Если вы добавите после них знак +, то первоначальный жадный режим станет эксклюзивным режимом, то есть совпадет с максимально возможным количеством, но не откатится.

Поэтому, если проблема должна быть полностью решена, необходимо убедиться, что при сохранении функции не происходит возврата. Я добавил знак + ко второй части приведенного выше регулярного выражения для проверки URL, то есть он становится таким:

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)
(([A-Za-z0-9-~]+).)++    --->>> （这里加了个+号）
([A-Za-z0-9-~\\/])+$

После этого нет проблем с запуском оригинальной программы.

Наконец, я рекомендую веб-сайт, который может проверить, не возникнут ли проблемы, когда написанное вами регулярное выражение совпадает с соответствующей строкой.

Online regex tester and debugger: PHP, PCRE, Python, Golang and JavaScript

Например, URL-адрес, о котором идет речь в моей статье, проверяется с помощью этого веб-сайта, и он подскажет: катастрофический возврат назад (катастрофический возврат назад).

Когда вы нажмете на «отладчик регулярных выражений» в левом нижнем углу, он сообщит вам, сколько всего шагов было проверено, и перечислит все шаги и укажет, где произошел возврат.

Регулярное выражение в этой статье автоматически останавливается после 110 000 попыток. Это показывает, что с этим регулярным выражением действительно есть проблема, и его необходимо улучшить.

Но когда я тестирую его с нашим модифицированным регулярным выражением, то, что ниже.

^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~\\\/])+$

Подсказка была проверена всего за 58 шагов.

Разница в одном символе, разница в производительности в десятки тысяч раз.

Шуи есть что сказать

Удивительно, как маленькое регулярное выражение может снизить нагрузку на ЦП. Это также предупреждение нам, обычно пишущим программы: встречая регулярные выражения, мы должны обращать внимание на жадный режим и проблемы с возвратом, иначе каждое выражение, которое мы напишем, будет миной.

Просматривая онлайн-материалы, я обнаружил, что студенты LAZADA в Шэньчжэньском центре Али также столкнулись с этой проблемой в 2017 году. Они также не обнаружили проблем в тестовой среде, но когда они вышли в интернет, они столкнулись со 100% проблемами процессора, проблемы, с которыми они столкнулись, были почти такими же, как и у нас. Заинтересованные друзья могут щелкнуть, чтобы прочитать исходный текст, чтобы просмотреть их более поздние обобщенные статьи:Кровавый случай, вызванный регулярными выражениями - Mingzhijian Zhiyuan - Blog Park

Хотя эта статья закончена, принцип автоматов NFA, особенно объяснение ленивого режима и монопольного режима, все еще недостаточно объяснен. Поскольку автоматы NFA действительно не так просты для понимания, в этом отношении необходимо постоянное обучение и укрепление. Добро пожаловать, друзья, у которых есть знания и опыт, чтобы учиться, общаться и продвигать друг друга.

вопросы и ответы

Как понимать регулярные выражения?

Связанное Чтение

регулярное выражение

Регулярные упражнения на растяжку

Регулярное выражение С#

Эта статья была разрешена автором для публикации сообщества Tencent Cloud +, исходная ссылка: https://cloud.tencent.com/developer/article/1148472?fromSource=waitui.

Приветствую всех вОблако Tencent + сообществоИли обратите внимание на общедоступную учетную запись WeChat сообщества Yunjia (QcloudCommunity) и как можно скорее получите больше массовой технической практики галантерейных товаров ~