28 karakterlik bir girdi, felaket seviyesindeki regex geri izlemesiyle Node.js'i 3,6 saniye kilitliyor

Bir geliştirici, 28 karakterlik bir string'in Node.js sürecini yalnızca regex eşleştirmesi yaparak 3,6 saniye boyunca meşgul edebildiğini gösteren somut bir benchmark yayınladı. dev.to'da yazan yazar, /^(a+)+$ desenini Node 22 (V8) üzerinde, "a" harfinin tekrarlanıp sonuna tek bir "X" eklenmesiyle oluşturulan girdilere karşı zamanlamış; bu yapı eşleşmenin kesin olarak başarısız olmasını garanti ediyor.

Her karakterle ikiye katlanma

Gönderiye göre reddetme süreleri eklenen her karakterle kabaca iki katına çıktı: 20 karakterde 8,6 ms, 22'de 34,2 ms, 24'te 136,6 ms, 26'da 553,7 ms, 27'de 1.103,8 ms ve 28'de 3.586,4 ms. Her ek karakter işi ikiye katladığından, on iki karakter daha eklemek süreyi 4.096 kat artırırdı; yazar, 40 karakterlik bir girdinin dört saat civarında süreceğini tahmin ediyor.

Tetikleyici başarısızlık

Patlama yalnızca eşleşme başarısız olduğunda ortaya çıkıyor. Aynı desen, sonunda "X" olmayan 5.000 "a" karakterine karşı çalıştırıldığında 0 ms'de eşleşme döndürüyor. Gönderinin açıkladığı gibi, neden iç içe geçmiş bir niceleyicideki belirsizlik: (a+)+ ifadesi motora bir "a" dizisini olası her yoldan bölme imkanı veriyor; n karakter için kabaca 2^(n-1) farklı bölme söz konusu ve başarısız bir eşleşme, motor pes etmeden önce hepsini denemesini zorunlu kılıyor.

Yazar, desenin egzotik olmadığına dikkat çekiyor. Sıradan bir e-posta doğrulayıcı, 16 karakterlik bir girdide 0,4 ms, 24 karakterde 12,5 ms ve sonuna bir ünlem işareti eklendiğinde 28 karakterde 200,7 ms sürmüş — sıradan kullanıcıların her gün yazdığı uzunluklarda aynı yapının aynı hata modunu üretmesi.

İşe yaramayan çözümler

Ölçümlere göre üç sezgisel çözüm başarısız oluyor:

• Uzunluk sınırlaması yeterli değil, çünkü 28 karakter kısadır ve birçok meşru girdi daha uzundur.
• Üst sınır işleri kötüleştiriyor: ^(a+){1,64}$ deseni 26 karakterde 4.414 ms sürdü; sınırsız sürüm ise 553,7 ms idi. Sınırlı dış döngü, derinliği sınırlamak yerine olası bölme sayısını çoğaltıyor.
• Possessive quantifier'lar JavaScript'te mevcut değil; new RegExp('^a++$') bir "Nothing to repeat" hatası fırlatıyor. Gönderi, Perl ve PCRE'nin a++ desteklediğini, .NET'in Regex.MatchTimeout sunduğunu, PHP'nin varsayılanı 1.000.000 olan pcre.backtrack_limit ile geldiğini belirtiyor; V8 ise ne bir sınır ne de bir timeout sunuyor ve olay döngüsünü (event loop) düpedüz bloke ediyor.

İşe yarayan yöntemler

Yazarın işe yarayan alternatifleri:

• Tekrarı tam olarak tek bir eşleşme yolu kalacak şekilde yeniden yazın. ^a+$ deseni, başarısız senaryoyu 1.000.000 karakterlik bir girdide 3,2 ms'de reddetti; bu, 35.000 kat daha uzun bir girdide kabaca bin kat daha hızlı demek.
• Bir atomic group'u lookahead ve backreference ile taklit edin: /^(?=(a+)) 1$/ deseni, 1.103,8 ms süren aynı girdide 0 ms'de çalışırken "aaa", "a", "" ve "aab" için hâlâ doğru sonuçlar döndürdü.
• Hasarı sınırlayın: girdi uzunluğuna üst sınır koyun, güvenilmeyen desenleri timeout'lu bir worker thread içinde çalıştırın ya da doğrusal zamanda tamamlanmak üzere tasarlanmış bir motor olan RE2'ye geçin.

Neden önemli

Node.js, JavaScript'i tek bir event loop üzerinde çalıştırıyor; dolayısıyla tek bir patolojik eşleşme tek bir isteği değil, sunucunun tamamını durdurabiliyor. Ve yavaşlama yalnızca başarısız eşleşmelerde tetiklendiği için, geçerli veriyle beslenen test paketleri geçerken üretim ortamı bozuk bir sorgu parametresi, kesilmiş bir alan ya da beklenmedik bir karakter içeren bir isim üzerinde devre dışı kalıyor. Yazarın kapanış tavsiyesi, hata yolunu bilinçli olarak test etmek — uzun bir geçerli önek artı sona eklenmiş tek bir geçersiz karakter — ve donan bir regex test aracı sekmesini sunucunun ne yapacağının bir önizlemesi olarak görmek.