Java 8 wprowadziła przekształcanie w HashMap, aby złagodzić ataki typu denial-of-service oparte na kolizjach. Próg 8 pochodzi z rozkładu Poissona z współczynnikiem obciążenia wynoszącym 0,75, gdzie prawdopodobieństwo, że pojedynczy koszyk zawiera 8 lub więcej elementów, wynosi około 0,00000606 (6 × 10⁻⁶). Ta statystyczna rzadkość zapewnia, że konwersja powiązanej listy na drzewo czerwono-czarne (które zużywa mniej więcej dwa razy więcej pamięci niż standardowy Node) następuje tylko wtedy, gdy jest to absolutnie konieczne, aby zachować złożoność wyszukiwania O(log n).
Wdrożenie równoważy wydajność pamięci z odpornością na ataki. Obiekt TreeNode wymaga 48 bajtów w porównaniu do standardowego Node's 32 bajtów w 64-bitowych JVM z kompresowanymi OOP, przede wszystkim z powodu dodatkowych odniesień do rodzica, lewego, prawego i poprzedniego węzła oraz flagi koloru. Próg ten reprezentuje punkt infleksji, w którym koszt przeszukiwania O(n) podczas złośliwych kolizji przewyższa przeszłość pamięciową struktur drzewiastych.
// Definiowanie stałych w HashMap.java static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64;
Wysokozasięgowa platforma e-commerce doświadczyła katastrofalnych szczytów opóźnienia podczas wyprzedaży błyskawicznych. Śledztwo wykazało, że napastnicy przesyłali żądania HTTP z tysiącami stworzonych parametrów zapytania zaprojektowanych w celu uzyskania identycznych wartości hashCode(), co spowodowało, że instancje HashMap używane do analizy parametrów degenerowały się w powiązane listy z czasami dostępu O(n).
// Symulacja ataku HashDoS Map<String, String> vulnerableMap = new HashMap<>(); for (int i = 0; i < 10000; i++) { // Stworzone klucze produkujące identyczne kody hash vulnerableMap.put(createCollidingKey(i), "malicious_value"); } // Czas wyszukiwania: O(n) w JDK 7, O(log n) w JDK 8+
Oceniono kilka strategii naprawczych.
Ograniczenie stawki na poziomie serwera WWW rozważano jako sposób na tłumienie podejrzanych wzorców ruchu. Jednak to podejście okazało się nieskuteczne, ponieważ legalny ruch podczas wyprzedaży błyskawicznych generował również wysokie wolumeny żądań, co uniemożliwiało różnicowanie, a jednocześnie mogło blokować prawidłowych klientów w okresach szczytowych.
Walidacja wejściowa ograniczająca liczbę parametrów do 100 została zaproponowana jako proste rozwiązanie zapobiegające zalewaniu hasha. To rozwiązanie zostało odrzucone przez kierowników produktów, którzy wymagali wsparcia dla skomplikowanych matryc filtrów w interfejsie wyszukiwania swojego katalogu, a inżynierowie ds. bezpieczeństwa zauważyli, że napastnicy nadal mogli osiągnąć kolizje przy nawet 50 starannie dobranych parametrach.
Migracja do ConcurrentHashMap była na chwilę rozważana pod założeniem, że jej struktura współbieżna może inaczej obsługiwać kolizje. To nie przyniosło ulgi, ponieważ ConcurrentHashMap stosuje identyczne mechanizmy przekształcania i ucierpiało z podobnym O(n) zepsuciem podczas ataku, działając poniżej progu przekształcania.
Zespół inżynieryjny wybrał podejście dwutorowe. Zaktualizowali platformę do JDK 8, wykorzystując automatyczny mechanizm przekształcania, który zamienia powiązane listy na czerwono-czarne drzewa w momencie, gdy kolizje przekraczają próg 8. Zapewniło to, że nawet złośliwe dane wejściowe dawały wydajność wyszukiwania O(log n), a nie liniowe pogorszenie. Dodatkowo wdrożyli filtr serwletu, który obliczał entropię rozkładu hasha na przychodzących żądaniach, odrzucając te z podejrzanymi wzorcami kolizji przed skonstruowaniem mapy.
Metryki po wdrożeniu wykazały stałe czasy odpowiedzi poniżej 50 ms nawet w warunkach ciągłego ataku. Wykorzystanie CPU pozostawało poniżej 40% podczas szczytowego ruchu, podczas gdy wcześniejsza implementacja saturacji wszystkich rdzeni w ciągu kilku minut od rozpoczęcia ataku. Platforma pomyślnie przetworzyła wyprzedaż błyskawiczną bez degradacji usług, co potwierdziło decyzję architektoniczną, aby polegać na wewnętrznej obsłudze kolizji JVM zamiast zewnętrznego ograniczenia stawki.
Dlaczego próg wraca do powiązanej listy przy 6 elementach zamiast 7 lub 8?
UNTREEIFY_THRESHOLD wynoszący 6 zapobiega oscylacji między strukturami danych podczas fluktuujących obciążeń. Jeśli operacje usuwania zmniejszą drzewo do 7 elementów, utrzymanie struktury drzewa unika natychmiastowych kosztów ponownej konwersji. Granica 6 elementów zapewnia histerezę, zapewniając, że koszt budowy drzewa (który wymaga alokacji nowych obiektów TreeNode i przegrupowania) jest rozłożony na wystarczająco długie okresy.
Jak rozkład Poissona uzasadnia konkretne liczby 8?
Przy domyślnym współczynniku obciążenia wynoszącym 0,75, oczekiwana liczba elementów na koszyk podążająca za rozkładem Poissona ma λ wynoszącą 0,5. Funkcja masy prawdopodobieństwa daje P(0) = 0,6065, P(1) = 0,3033, P(2) = 0,0758, malejąc wykładniczo. Prawdopodobieństwo osiągnięcia 8 elementów wynosi 0,5⁸/8! × e^(-0,5) ≈ 6,0 × 10⁻⁶. To oznacza szansę na sześć w milionie, co oznacza, że kara pamięciowa obiektów TreeNode wpływa na mniej niż 0,0006% koszyków w normalnej eksploatacji.
Jakie są dokładne koszty pamięci związane z utrzymywaniem przekształconego koszyka w porównaniu do powiązanej listy?
Standardowy HashMap.Node zużywa 32 bajty (nagłówek obiektu, hash int, odniesienie do klucza, odniesienie do wartości, odniesienie do następnego). TreeNode rozszerza LinkedHashMap.Entry, która rozszerza Node, dziedzicząc dodatkowe pola: rodzic, lewy, prawy, poprzedni i flagę boolean czerwony. Skutkuje to 48 bajtami na wpis w 64-bitowych JVM z kompresowanymi OOP, plus narzut LinkedHashMap. Dla koszyka zawierającego dokładnie 8 elementów struktura przekształcona wymaga około 384 bajtów w porównaniu z 256 bajtami dla powiązanej listy, co stanowi wzrost o 50%, który pozostaje akceptowalny, biorąc pod uwagę rzadkość takich kolizji.