W początkowych wersjach Go haszowanie map korzystało z deterministycznego algorytmu z ustalonym seedem. Sprawiło to, że aplikacje były narażone na ataki polegające na zalewaniu haszami, w których przeciwnik mógł opracować klucze wejściowe, które wszystkie kolidowały w tym samym kubełku, pogarszając wydajność wyszukiwania z O(1) na O(n). Zespół Go wprowadził losowe seedy haszowania dla każdej mapy w Go 1.12 (i jeszcze bardziej wzmocnił je w kolejnych wydaniach) w połączeniu z randomizacją haszowania w czasie wykonywania, aby zapewnić, że napastnicy nie mogą przewidzieć rozmieszczenia kubełków.
Krytyczny problem pojawia się, gdy tabela haszująca napotyka na wrogie wejście. Bez przeciwdziałania usługi internetowe przetwarzające niezaufane dane w mapach (takie jak nagłówki HTTP lub obiekty JSON) mogą zostać zaatakowane przez pojedyncze złośliwe zapytanie zawierające tysiące kolidujących kluczy. Wyzwanie polegało na wprowadzeniu nieprzewidywalności bez poświęcania szybkości i efektywności pamięci, które sprawiają, że mapy w Go są odpowiednie dla systemów o wysokiej wydajności.
Czas wykonania w Go generuje losowy seed dla każdej instancji mapy podczas inicjalizacji przy użyciu runtime.fastrand. Wykorzystuje funkcję haszującą (często instrukcje sprzętowe AES na nowoczesnych CPU, a w przypadku innych wraca do memhash), kluczowaną przez ten seed. Na przykład, gdy piszesz:
m := make(map[string]int) m[untrustedInput] = 1
Czas wykonania wewnętrznie wywołuje haszownik specyficzny dla typu, który łączy bajty klucza z unikalnym polem mapy hash0. Aby poradzić sobie z kolizjami, Go używa łańcuchów z kubełkami przepełnienia zamiast otwartego adresowania, a podczas faz wzrostu stopniowo ewakuują wpisy. Taki projekt zapewnia, że nawet przy wrogich danych rozkład w kubełkach pozostaje równomierny, zachowując średni czas operacji O(1).
Wyobraź sobie, że budujesz bramkę API o dużym ruchu, która agreguje konfigurację z tysięcy mikroserwisów. Każda usługa zgłasza swój stan zdrowia za pomocą ładunku JSON, zawierającego dynamiczne etykiety przechowywane w map[string]string. Napastnik odkrywa twój punkt końcowy i wysyła zniekształcony ładunek, w którym każdy klucz etykiety został zaprojektowany tak, aby produkować identyczne wartości haszy, co powoduje, że twoja usługa spędza sekundy na przejściu przez pojedynczy kubełek podczas analizowania żądania, co prowadzi do kaskady czasów oczekiwania.
Rozważano wiele rozwiązań mających na celu wzmocnienie systemu.
Jednym z podejść było zastąpienie map zrównoważonym drzewem poszukiwań binarnych, takim jak implementacja drzewa czerwono-czarnego. Gwarantowałoby to O(log n) w najgorszym przypadku niezależnie od danych wejściowych, eliminując wektor denial-of-service. Jednak wprowadziłoby to znaczną złożoność, wymagałoby importowania zewnętrznych bibliotek lub pisania ciężkiego kodu i obciążałoby każde legalne żądanie wolniejszymi czasami dostępu oraz większym zużyciem pamięci w porównaniu do natywnych map.
Innym rozważanym rozwiązaniem była wstępna walidacja, która odrzucała żądania zawierające podejrzane wzorce lub po prostu ograniczała całkowitą liczbę kluczy do małej, arbitralnej liczby, takiej jak sto. Chociaż zmniejsza to absolutny wpływ ataku, nie naprawia to podstawowej podatności na złożoność algorytmiczną; napastnik mógłby nadal wyrządzić maksymalne szkody przy mniejszej liczbie wysoce zoptymalizowanych kolidujących kluczy, a legalne przypadki użycia wymagające wielu etykiet byłyby niewłaściwie odrzucane.
Wybrane rozwiązanie polegało na poleganiu na wbudowanym w Go wzmocnieniu map przy jednoczesnym dodaniu ograniczenia przepustowości middleware. Ponieważ nowoczesne wersje Go automatycznie randomizują seed haszowania dla każdej instancji mapy, napastnik nie może przewidzieć, które klucze będą kolidowały, skutecznie neutralizując atak polegający na zalewaniu haszami. Sprawdziliśmy to, testując złośliwe ładunki i obserwując stałe czasy analizowania poniżej milisekundy. Wynikiem była odporna bramka, która zachowywała charakterystyki wydajności O(1) bez zmiany podstawowej struktury danych czy kompromisów w ergonomii API.
Dlaczego Go nie używa kryptograficznych funkcji haszujących, takich jak SHA-256, dla kluczy map w celu zapewnienia jednolitego rozkładu?
Funkcje haszujące kryptograficzne zapewniają doskonałe właściwości lawinowe, ale wiążą się z prohibicyjnym obciążeniem obliczeniowym. Mapy w Go priorytetowo traktują szybkość dla codziennych operacji, a haszowanie kryptograficzne pogarszałoby wydajność o rząd wielkości dla wszystkich zastosowań, tylko aby bronić się przed konkretnym atakiem krawędziowym. Zamiast tego, Go wykorzystuje szybkie, niekryptograficzne algorytmy haszujące (optymalizowane z instrukcjami AES-NI, gdy są dostępne), które zapewniają wystarczającą losowość do rozkładu, jednocześnie zachowując przepustowość wymaganą do programowania systemowego.
Jak wzrost mapy (podwajanie) zachowuje ważność istniejących seedów haszujących i zapewnia prawidłowe redistribucję wpisów?
Gdy mapa rośnie (zazwyczaj gdy współczynnik obciążenia przekracza 6,5 kubełka), czas wykonania przydziela nową tablicę o podwójnej wielkości. W trakcie inkrementalnej ewakuacji czas wykonania ponownie haszuje każdy wpis używając oryginalnego losowego seeda, ale z nową maską kubełków (wyższe bity). Ponieważ hasz jest deterministyczny dla danego seeda, ale liczba kubełków się zmienia, wpisy naturalnie rozpraszają się w różnych kubełkach. Kandydaci często umykają, że seed pozostaje stały przez całe życie mapy; tylko maska bitowa używana do wyboru indeksu kubełka zmienia się, zapewniając, że kosztowna operacja ponownego haszowania odbywa się tylko podczas wzrostu, a nie przy każdym wyszukiwaniu.
Jaka jest różnica między funkcją haszującą używaną dla map a funkcją haszującą używaną przez runtime.memhash w innych celach, i dlaczego ta różnica ma znaczenie?
Chociaż obie korzystają z podobnych algorytmów, haszowanie map zawiera losowy seed specyficzny dla mapy oraz funkcje alg specyficzne dla typu (poprzez runtime.typeAlg) do obsługi różnych typów kluczy (ciągów, liczb całkowitych, struktur). W przeciwieństwie do tego, runtime.memhash to uniwersalne narzędzie do haszowania surowych bajtów pamięci bez świadomości typu. Różnica ma znaczenie, ponieważ haszowanie map musi respektować semantykę równości Go; na przykład zapewniając, że różne pola struktury prawidłowo przyczyniają się do hasza, podczas gdy memhash jest czysto dla sekwencji bajtów. Zrozumienie tego rozdziału podkreśla, jak Go optymalizuje zarówno bezpieczeństwo typów, jak i wydajność.