2 июля 2019 года edge-серверы Cloudflare упёрлись почти в 100% CPU, и сайты по всему миру перестали открываться.
Шаблон был устроен как
(a+)+b: два вложенных квантификатора над одним классом символов. Дайте движку строку, которая почти совпадает, но в конце ломается, и он перебирает все способы разложить её между двумя плюсами. На 20 символах это полмиллиона попыток, на 40 — около 500 миллиардов, и одно ядро занято.Ревью бессильно: регулярка компилировалась, тесты проходила, на обычном вводе работала. Это известный класс дыр, CWE-1333. Помогает выбор движка: re2, regexp в Go и regex в Rust собирают шаблон в детерминированный автомат и работают линейно, но обратные ссылки вроде \1 они не умеют.
В разборе на dev.to: как регулярка превращается в автомат и чего регуляркой не выразить.
#безопасность