IAli
Tüm Yazılar
ReDoS Geri İzleme Açıkları ve Google RE2 Doğrusal Zamanlı Motoru

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:

TEXT
KURAL: ^(a+)+$

Bu ifade aaaaX gibi sonunda eşleşmeyen bir karakter bulunan bir metne uygulandığında motorun attığı adımları inceleyelim:

TEXT
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:

TEXT
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:

TEXT
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ı:

TEXT
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 tepki

Fikirlerinizi tek tıkla paylaşarak geri bildirim bırakın.

Bu teknik notu çevrenizle paylaşın

Ali Purtaş

@alipurtas • Hey, This is Ali!

İletişime Geç

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

İç Bağlantılı Mimari
Yorumlar yükleniyor...