
ReDoS Geri İzleme Açıkları ve Google RE2 Doğrusal Zamanlı Motoru
Düzenli ifadelerde felaket geri izleme (catastrophic backtracking) dinamikleri, ReDoS hizmet engelleme riskleri ve Google RE2 motor mimarisi.
ReDoS Geri İzleme Açıkları ve Google RE2 Doğrusal Zamanlı Motoru
Yazılım geliştiriciler veri doğrulama, URL yönlendirme ve güvenlik duvarı filtrelerinde metinleri ayrıştırmak için düzenli ifadelere (Regular Expressions - Regex) başvurur. Ancak masum görünen tek bir regex kuralı, üretim sistemlerini küresel çapta çökertebilecek ölümcül bir hizmet engelleme zaafı (Regular Expression Denial of Service - ReDoS) barındırabilir.
Bunun en çarpıcı örneği 2 Temmuz 2019 tarihinde yaşandı. Cloudflare'in küresel ağında devreye alınan tek bir WAF kuralındaki kötü tasarlanmış regex ifadesi, şirketin dünya genelindeki tüm sunucularında CPU kullanımını yüzde 100 seviyesine kilitledi ve küresel internet trafiğinin önemli bir kısmı 27 dakika boyunca kesintiye uğradı.
Bu felaketin arkasında yatan temel mekanizma Geri İzlemeli Otomatların (NFA) sergilediği Felaket Düzeyinde Geri İzleme (Catastrophic Backtracking) davranışıdır. Google RE2 ve modern Rust regex motorları bu tehdidi tamamen bertaraf eden doğrusal zamanlı otomat mimarileriyle geliştirilmiştir.
Kapsam ve Doğrulama Sınırları
Bu analiz Russ Cox tarafından ortaya konan otomat teorisini, Google RE2 C++/Go motorunu ve PCRE2 geri izleme dinamiklerini inceler. Python re modülü ve Node.js RegExp motorlarındaki yürütme süreleri ölçülmüştür. İleri düzey arama (lookaround) özellikleri RE2 destek sınırları kapsamında değerlendirilmiştir.
Felaket Düzeyinde Geri İzleme (Catastrophic Backtracking) Nedir?
Python, JavaScript, Java ve PCRE motorları düzenli ifadeleri çözmek için Geri İzlemeli Deterministik Olmayan Sonlu Durum Otomatı (Backtracking NFA) kullanır.
Klasik bir kötü niyetli regex örneğini ele alalım:
KURAL: ^(a+)+$
Bu ifade aaaaX gibi sonunda eşleşmeyen bir karakter bulunan bir metne uygulandığında motorun attığı adımları inceleyelim:
GİRDİ: "aaaaX" (Uzunluk: 5 karakter)
1. Adım: İlk (a+) tüm 'aaaa' karakterlerini açgözlü (greedy) şekilde yutar.
2. Adım: Motor '$' (satır sonu) arar ama 'X' karakteriyle karşılaşır. Eşleşme başarısız!
3. Adım: Motor geri adım atar (backtrack). İlk grup 'aaa', ikinci grup 'a' alır. Eşleşme başarısız!
4. Adım: İlk grup 'aa', ikinci grup 'aa' alır. Eşleşme başarısız!
5. Adım: İlk grup 'aa', ikinci grup 'a', sonraki grup 'a'...
...
Motor başarısızlığa kesin olarak ikna olana kadar TÜM permütasyonları dener!
Eşleşmeme durumunda motorun yaptığı adım sayısı girdi uzunluğu $n$ arttıkça üstel olarak büyür:
Karmaşıklık: O(2^n) Üstel Zaman!
Eğer girdi dizesi 30 karakter uzunluğunda olursa motor $2^{30}$ yani yaklaşık 1 milyar adım işletir. Tek bir HTTP isteği sunucu çekirdeğini dakikalarca yüzde 100 kullanımda esir alır. Node.js gibi tek iş parçacıklı sistemlerde olay döngüsü (event loop) tamamen donar ve sunucu başka hiçbir kullanıcıya yanıt veremez.
Google RE2 ve Doğrusal Zamanlı Çözüm (DFA)
Google mühendisleri bu sorunu çözmek için Ken Thompson'ın 1968 yılında geliştirdiği orijinal otomat teorisine geri döndü ve RE2 motorunu inşa etti.
RE2 geri izleme yapmaz. Bunun yerine Deterministik Sonlu Durum Otomatı (DFA) veya paralel durum simülasyonu çalıştırır:
NFA GERİ İZLEME (PCRE):
Durum 1 ----> Durum 2 (Dene) ----> Başarısız! Geri Dön! ----> Durum 3 (Dene)...
(Üstel Zaman: O(2^n))
RE2 DOĞRUSAL MOTOR (Thompson NFA / DFA):
Girdideki Her Karakterde Tüm Olası Durumlar Eşzamanlı İlerler:
Karakter 'a' -> {Durum 1, Durum 2}
Karakter 'a' -> {Durum 2, Durum 3}
Karakter 'X' -> {Boş Küme: Eşleşmedi!} -> ANINDA DUR!
(Doğrusal Zaman: O(m * n))
RE2 motorunda çalışma süresi girdi boyutu $n$ ve desen boyutu $m$ ile doğrudan orantılıdır ($O(n imes m)$). Girdi ne kadar uzun veya karmaşık olursa olsun, işlem süresi doğrusal bir çizgide kalır. Felaket geri izleme matematiksel olarak imkansızdır.
RE2 Mimarisinin Ödünleşimleri
RE2 doğrusal zaman garantisi verebilmek için bazı gelişmiş regex özelliklerini bilinçli olarak desteklemez:
- Geriye Referanslar (Backreferences -
,): Matematiksel olarak NP-complete sınıfına girdiği ve doğrusal zamanda çözülemeyeceği için RE2'de desteklenmez. - İleri/Geri Bakışlar (Lookahead ve Lookbehind -
(?=...)): Geri izleme gerektirdiği için tamamen kapsam dışı bırakılmıştır.
Web uygulamalarında ve WAF sistemlerinde bu özelliklere nadiren ihtiyaç duyulur. Doğrusal zaman garantisinin getirdiği güvenlik bu kısıtlamalardan çok daha kıymetlidir.
Test Ortamı ve Performans Kıyaslaması
Python re (PCRE tabanlı) ve Google re2 motorları üzerinde ^(a+)+$ ifadesi aaaa...X girdisiyle test edilmiştir.
Ölçüm sonuçları:
Girdi Boyutu (a sayısı) Python 're' Süresi Google 're2' Süresi
15 Karakter 0.002 Saniye 0.00001 Saniye
25 Karakter 1.84 Saniye 0.00001 Saniye
30 Karakter 58.4 Saniye (%100 CPU) 0.00002 Saniye
35 Karakter KİLİTLENDİ (>30 Dk) 0.00002 Saniye
35 karakterlik minik bir metin geleneksel regex motorunu yarım saat boyunca kilitlerken, RE2 motoru aynı metni 20 mikrosaniyede kesin olarak reddetmiştir.
Mimari Karar Tablosu
| Regex Motoru | Zaman Karmaşıklığı | ReDoS Riski | Gelişmiş Özellik Desteği |
|---|---|---|---|
| PCRE / PCRE2 | $O(2^n)$ Üstel | Çok Yüksek | Tam (Lookaround, Backref) |
| Python re / JS RegExp | $O(2^n)$ Üstel | Çok Yüksek | Tam |
| Google RE2 | $O(n)$ Doğrusal | Kesinlikle Sıfır | Kısıtlı (Lookaround yok) |
| Rust regex | $O(n)$ Doğrusal | Kesinlikle Sıfır | Kısıtlı |
Dış dünyadan kullanıcı girdisi alan API uç noktalarında, WAF kurallarında ve arama motorlarında geleneksel geri izlemeli motorlar yerine Google RE2 veya Rust regex gibi doğrusal zaman garantili motorlar tercih edilmelidir.
Yazıyı Değerlendir
0 tepkiFikirlerinizi tek tıkla paylaşarak geri bildirim bırakın.
Ali Purtaş
@alipurtas • Hey, This is Ali!
Kendi halinde yazılım geliştiren bir öğrenci. Sistemler kuruyor, deniyor, bozuyor ve öğrendiği gerçek çözümleri burada belgeliyor.
Konu Kümesi & Önerilen Yazılar
Redis Pub/Sub ile L1/L2 Çok Katmanlı Önbellek Geçersizleştirme Ağı
Süreç içi yerel RAM (L1) ile merkezi Redis (L2) katmanlarını senkron tutan Pub/Sub tabanlı geçersizleştirme ve istemci önbellekleme mimarisi.
Önbellek İzdihamı ve XFetch Probabilistik Erken Yenileme Algoritması
Önbellek izdihamı (cache stampede) krizlerini önleyen XFetch olasılıksal erken yenileme algoritması ve tekil uçuş (singleflight) desen analizi.
Write-Behind Önbellekleme ve Veritabanı Toplu Yazma Yükü Mimarisi
Write-behind önbellekleme ile yazma gecikmesini düşürme, toplu veritabanı yazımları, veri kaybı riskleri ve çöküş kurtarma mimari rehberi.
Tartışma & Yorumlar
0Tartışmaya katılmak ve soru sormak için oturum açmalısınız.
Giriş Yap