Jeden źle napisany regex zużył niemal cały CPU globalnej sieci Cloudflare
2 lipca 2019 r. Cloudflare wdrożyło nową regułę Web Application Firewall. Zawierała wyrażenie regularne, które powodowało ogromny backtracking. Po globalnym rolloutcie procesy obsługujące HTTP/HTTPS zaczęły zużywać niemal 100% CPU na serwerach na całym świecie, a klienci zobaczyli błędy 502. Awaria trwała około 27 minut. Najważniejsze nie było jednak samo „złe regex”. Postmortem wskazał również brak testów wykrywających nadmierny koszt CPU i możliwość globalnego wdrożenia reguły bez stopniowego canary rollout.
Regex może mieć bardzo różną złożoność
Wyrażenia regularne wyglądają jak krótki zapis wzorca, ale sposób ich wykonania zależy od silnika. Silniki oparte na backtrackingu próbują wielu alternatywnych dopasowań, gdy wcześniejsza ścieżka zawodzi. Przy niektórych wzorcach liczba prób rośnie znacznie szybciej niż długość wejścia. Krótka reguła może więc zużyć ogromną ilość CPU.
Problematyczna reguła została wdrożona globalnie
Cloudflare używa WAF do szybkiego reagowania na nowe podatności. Ta cecha wymaga bardzo sprawnej dystrybucji reguł. 2 lipca mechanizm szybkości stał się jednak wzmacniaczem awarii: wadliwy wzorzec został rozesłany szeroko, zanim ktokolwiek zobaczył efekt w małej próbce ruchu.
CPU skoczyło prawie do 100%
Procesy obsługujące HTTP/HTTPS zaczęły spędzać ogromną ilość czasu na dopasowywaniu regexu. Nie był to brak pamięci ani awaria sieci; serwery wciąż działały, ale ich moce obliczeniowe były praktycznie pochłonięte przez jedną regułę. To dobry przykład resource exhaustion wywołanego pozornie niewinną operacją tekstową.
Zabezpieczenie przed drogimi regexami wcześniej zniknęło
Postmortem Cloudflare przyznał, że podczas wcześniejszego refaktoringu usunięto ochronę, która mogłaby ograniczyć nadmierne użycie CPU. Sam regex był więc tylko jednym ogniwem. Kolejne bariery — profilowanie wydajności, limit czasu, rollout etapowy — również nie zatrzymały problemu.
Rollback był wolniejszy, niż powinien
Procedura wycofania reguły wymagała przebudowania całego zestawu WAF, co opóźniało odzyskanie sprawności. Po incydencie firma zmieniła proces wdrożeń i zaczęła przenosić reguły na silniki z gwarancjami liniowego czasu działania, takie jak RE2/Rust regex.
Złożoność algorytmiczna jest problemem produkcyjnym
Programista uczy się notacji O(n), ale często traktuje ją jako teorię. Cloudflare pokazuje jej praktyczny sens: wzorzec działający świetnie dla małych danych testowych może zachować się katastrofalnie na realnym ruchu. Test poprawności powinien obejmować nie tylko wynik, ale także koszt obliczeniowy. Dodatkowy test powinien obejmować adversarial inputs, czyli teksty specjalnie skonstruowane tak, by wymusić najgorszą ścieżkę dopasowania. Benchmark na kilku typowych requestach nie daje informacji o zachowaniu w najgorszym przypadku, a WAF musi zakładać właśnie wejścia nieprzyjazne.
Dlaczego liniowy silnik regex zmienia klasę ryzyka
Nie wszystkie silniki wyrażeń regularnych muszą wykonywać backtracking. Implementacje oparte na automatach mogą gwarantować czas wykonania rosnący liniowo z długością wejścia dla obsługiwanego zestawu konstrukcji. Ograniczają w zamian część bardziej ekspresyjnych funkcji, takich jak niektóre backreferences. To klasyczny trade-off między mocą języka a przewidywalnością kosztu. W firewallu przetwarzającym każdy request przewidywalność ma ogromną wartość, bo nawet rzadki przypadek wykładniczego zachowania może zostać powtórzony miliony razy. Cloudflare po awarii rozszerzyło testy wydajności i inwestowało w rozwiązania eliminujące niekontrolowany backtracking. To pokazuje szerszą zasadę: jeśli użytkownik lub konfiguracja może dostarczać wzorzec wykonywany na masowym ruchu, trzeba analizować nie tylko semantykę wzorca, ale jego najgorszą złożoność. W przeciwnym razie krótki tekst staje się programem o nieprzewidywalnym czasie działania. To dlatego bezpieczny pipeline reguł powinien mierzyć nie tylko poprawność dopasowania, ale też czas CPU dla danych normalnych i specjalnie złośliwych.