Java 8, çarpışma bazlı hizmet reddi saldırılarını azaltmak için HashMap'te ağaçlaştırmayı tanıttı. 8 eşiği, Poisson dağılımından kaynaklanmaktadır ve yük faktörü 0.75'dir; burada bir sepette 8 veya daha fazla öğe bulunma olasılığı yaklaşık olarak 0.00000606 (6 × 10⁻⁶)dır. Bu istatistiksel nadirlik, bağlı listeyi kırmızı-siyah ağaç'a dönüştürmenin (standart bir Node'dan yaklaşık iki kat daha fazla bellek tükettiği) yalnızca O(log n) arama karmaşıklığını korumak için kesinlikle gerekli olduğunda gerçekleşmesini sağlar.
Uygulama, bellek verimliliği ile saldırı dayanıklılığı arasında denge kurar. TreeNode nesnesi, 64 bit JVM'lerde sıkıştırılmış OOP'lerle standart Node'un 32 baytına kıyasla 48 bayt gerektirir; bu, esas olarak ebeveyn, sol, sağ ve önceki düğümler için ek referanslar ile bir renk bayrağı nedeniyle ortaya çıkar. Eşik, kötü niyetli çarpışmalar sırasında O(n) gezinti maliyetinin ağaç yapılarının bellek aşımından daha fazla olduğu noktayı temsil eder.
// HashMap.java'da sabitler tanımlanıyor static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64;
Yüksek trafik alan bir e-ticaret platformu, flaş satışlar sırasında felaket niteliğinde gecikme zirveleri yaşadı. Araştırma, saldırganların aynı hashCode() değerlerini üretmek için tasarlanmış binlerce sorgu parametresi ile HTTP istekleri gönderdiğini ortaya çıkardı ve bu durum, parametre ayrıştırmada kullanılan HashMap örneklerinin bağlı listelere dönüşmesine yol açarak O(n) erişim sürelerine neden oldu.
// HashDoS saldırısının simülasyonu Map<String, String> savunmasızHarita = new HashMap<>(); for (int i = 0; i < 10000; i++) { // Aynı hash kodlarını üreten tasarlanmış anahtarlar savunmasızHarita.put(createCollidingKey(i), "kötü_niyetli_değer"); } // Arama süresi: JDK 7'de O(n), JDK 8+'de O(log n)
Birçok iyileştirme stratejisi değerlendirildi.
Web sunucusu seviyesinde oran sınırlaması düşünülmüştü çünkü şüpheli trafik desenlerini yavaşlatabilirdi. Ancak, bu yaklaşım, meşru flaş satış trafiğinin de yüksek istek hacimleri ürettiği için etkisiz oldu ve geçerli müşterilerin zirve kazanç dönemlerinde engellenme riskiyle birlikte ayrıştırılmasını imkansız hale getirdi.
Parametre sayısını 100 ile sınırlayan girdi doğrulama, hash taşkınını önlemek için basit bir çözüm olarak önerildi. Bu çözüm, ürün yöneticileri tarafından katalog arama arayüzlerinde karmaşık filtre matrisleri desteği gerektirdiği için reddedildi ve güvenlik mühendisleri, saldırganların dikkatlice seçilmiş 50 parametre içinde bile çarpışmalar elde edebileceğini belirtti.
ConcurrentHashMap'e geçiş, çarpışmaları farklı bir şekilde ele alabileceği varsayımı altında kısa bir süre gündeme geldi. Ancak bu, ConcurrentHashMap'in aynı ağaçlaştırma mekanizmalarını kullanması ve ağaçlaştırma eşiğinin altında çalışırken benzer O(n) bozulmalarına maruz kalması nedeniyle rahatlama sağlamadı.
Mühendislik ekibi, iki yönlü bir yaklaşım seçti. 8'den fazla çarpışma gerçekleştiğinde bağlı listeleri kırmızı-siyah ağaç'lara dönüştüren otomatik ağaçlaştırma mekanizmasından faydalanarak platformu JDK 8'e yükselttiler. Bu, kötü niyetli girdilerin bile O(log n) arama performansı sağladığından emin oldu. Ayrıca, gelen taleplerde hash dağılım entropisini hesaplayan bir servlet filtresi uyguladılar ve şüpheli çarpışma desenlerine sahip olanları harita oluşturmadan önce reddettiler.
Dağıtım sonrası metrikler, sürekli saldırı koşullarında bile 50ms'nin altında yanıt sürelerini göstermeye devam etti. CPU kullanımı, zirve trafik sırasında %40'ın altında kaldı, oysa önceki uygulama saldırı başlatıldığında tüm çekirdekleri dakikalar içinde doyuma ulaştırmıştı. Platform, hizmet degrade olmadan flaş satışı başarıyla işledi ve JVM'in iç çarpışma yönetimine dayanma mimari kararını doğruladı.
Eşik, neden 7 veya 8 yerine 6 öğede bağlı listeye dönüşüyor?
UNTREEIFY_THRESHOLD'u 6 olarak belirlemek, dalgalanan iş yükleri sırasında veri yapıları arasında salınımı önler. Eğer kaldırma işlemleri bir ağacı 7 öğeye düşürürse, ağaç yapısını korumak, hemen yeniden dönüştürme maliyetlerini önler. 6 öğelik sınır, ağaç yapımı maliyetinin (yeni TreeNode nesneleri ayırmayı ve yeniden dengeleme gerektiren) yeterince uzun süre boyunca amorti edilmesini sağlamak için histerezis sağlar.
Poisson dağılımı, 8 sayısını özel olarak nasıl haklı çıkarıyor?
Varsayılan yük faktörü 0.75 ile, her sepet için beklenen öğe sayısı, λ'nin 0.5 olduğu bir Poisson dağılımı nasıl takip eder. Olasılık kütle fonksiyonu P(0) = 0.6065, P(1) = 0.3033, P(2) = 0.0758 değerlerini verir ve bu değerler üssel olarak azalır. 8 öğeye ulaşma olasılığı 0.5⁸/8! × e^(-0.5) ≈ 6.0 × 10⁻⁶'dır. Bu, altı milyonda bir şans anlamına gelir ve TreeNode nesnelerinin bellek maliyeti, normal çalışmada %0.0006'dan daha az sepeti etkiler.
Bir ağaçlandırılmış sepeti bağlı listeye kıyasla sürdürmenin kesin bellek maliyeti nedir?
Standart HashMap.Node, 32 bayt (nesne başlığı, hash int, anahtara referans, değere referans, bir sonraki elemana referans) tüketir. Bir TreeNode, LinkedHashMap.Entry'den türetilir ve bu da ek alanlar: ebeveyn, sol, sağ, önceki ve bir boolean kırmızı bayrağını içerir. Bu, 64 bit JVM'lerde sıkıştırılmış OOP'lerle her giriş için 48 bayta, ayrıca LinkedHashMap üzerindeki aşırı yükle ile sonuçlanır. Tam olarak 8 öğe içeren bir sepet için, ağaçlaştırılmış yapı yaklaşık 384 bayt, bağlı liste için ise 256 bayt gerektirir; bu da, böyle çarpışmaların nadirliği göz önüne alındığında kabul edilebilir bir %50 artış temsil eder.