Cloudflare лёг на 27 минут из-за одной регулярки, и ошибки в коде там не было

2 июля 2019 года edge-серверы Cloudflare упёрлись почти в 100% CPU, и сайты по всему миру перестали открываться.

Шаблон был устроен как (a+)+b: два вложенных квантификатора над одним классом символов. Дайте движку строку, которая почти совпадает, но в конце ломается, и он перебирает все способы разложить её между двумя плюсами. На 20 символах это полмиллиона попыток, на 40 — около 500 миллиардов, и одно ядро занято.

Ревью бессильно: регулярка компилировалась, тесты проходила, на обычном вводе работала. Это известный класс дыр, CWE-1333. Помогает выбор движка: re2, regexp в Go и regex в Rust собирают шаблон в детерминированный автомат и работают линейно, но обратные ссылки вроде 1 они не умеют.

В разборе на dev.to: как регулярка превращается в автомат и чего регуляркой не выразить.

#безопасность

Источник: Telegram