В ранних версиях Go хеширование карт использовало детерминированный алгоритм с фиксированным начальным значением. Это сделало приложения уязвимыми для атак с хеш-флудом, когда противник мог создать входные ключи, которые все коллизировались в одну и ту же корзину, что ухудшало производительность поиска с O(1) до O(n). Команда Go внедрила случайные хеш-семена для каждой карты в Go 1.12 (и дополнительно укрепила в последующих версиях), совместно с рандомизацией хеширования во время выполнения, чтобы гарантировать, что злоумышленники не могут предсказать размещение корзин.
Критическая проблема возникает, когда хеш-таблица сталкивается с враждебным вводом. Без мер предосторожности веб-сервисы, разбирающие ненадежные данные в картах (например, HTTP заголовки или JSON объекты), могут быть выведены из строя одной злонамеренной просьбой, содержащей тысячи коллизирующих ключей. Задача состояла в том, чтобы ввести непредсказуемость, не жертвуя скоростью и эффективностью памяти, которые делают карты Go подходящими для высокопроизводительных систем.
Время выполнения Go генерирует случайное начальное значение для каждого экземпляра карты во время инициализации с использованием runtime.fastrand. Он использует хеш-функцию (часто аппаратные инструкции AES на современных ЦП, переходя на memhash на других) с ключом, зависящим от этого значения. Например, когда вы пишете:
m := make(map[string]int) m[untrustedInput] = 1
Время выполнения внутренне вызывает специфичный для типа хешер, который комбинирует байты ключа с уникальным полем hash0 карты. Для обработки коллизий Go использует цепочку с переполнением корзин, а также постепенно эвакуирует записи в фазах роста. Эта конструкция гарантирует, что даже с враждебными вводами распределение по корзинам остается равномерным, сохраняя среднее время операции O(1).
Представьте, что вы создаете API шлюз с высокой нагрузкой, который агрегирует конфигурации от тысяч микросервисов. Каждый сервис сообщал о своем состоянии через полезную нагрузку JSON, содержащую динамические метки, хранящиеся в map[string]string. Злоумышленник обнаруживает ваш конечный пункт и отправляет плохо сформированную полезную нагрузку, где каждый ключ метки был спроектирован так, чтобы производить идентичные хеш-значения, заставляя вашу службу тратить секунды на обход одной корзины при разборе запроса, что приводит к каскаду таймаутов.
Рассматривалось несколько решений, чтобы укрепить систему.
Один из подходов заключался в замене карты на сбалансированное бинарное дерево поиска, такое как реализация красно-черного дерева. Это гарантировало бы O(log n) худший случай при поиске независимо от ввода, устраняя вектор отказа в обслуживании. Однако это привело бы к значительной сложности, потребовало бы импорта внешних библиотек или написания тяжелого кода и накладывало бы штраф на каждый законный запрос за счет более медленного доступа и больших затрат памяти по сравнению с родной картой.
Еще одно рассматриваемое решение заключалось в предварительной проверке, которая отклоняла запросы, содержащие подозрительные шаблоны, или просто ограничивала общее количество ключей до небольшого произвольного числа, например, ста. Хотя это уменьшает абсолютное воздействие атаки, это не устраняет основную уязвимость алгоритмической сложности; злоумышленник все еще мог бы нанести максимальный ущерб с меньшим количеством высоко оптимизированных коллизирующих ключей, а законные случаи использования, требующие множества меток, были бы неверно отклонены.
Выбранным решением стало полагаться на встроенное укрепление карт Go, одновременно добавив ограничение на частоту с помощью промежуточного программного обеспечения. Поскольку современные версии Go автоматически рандомизируют начальное значение хеша для каждого экземпляра карты, злоумышленник не может предсказать, какие ключи будут коллизироваться, эффективно нейтрализуя атаку хеш-флудом. Мы проверили это, проведя бенчмаркинг с злонамеренными полезными нагрузками и наблюдая последовательные времена разбора менее одной миллисекунды. Результатом стал устойчивый шлюз, который сохранял характеристики производительности O(1) без изменения основной структуры данных или компромисса в удобстве API.
Почему Go не использует криптографические хеш-функции, такие как SHA-256, для ключей карты, чтобы гарантировать равномерное распределение?
Криптографические хеши обеспечивают отличные свойства лавин и имеют непомерные вычислительные затраты. Карты Go отдают приоритет скорости для обычных операций, а применение криптографического хеширования ухудшит производительность на порядок величины для всех случаев использования только для защиты от конкретной атаки на крайний случай. Вместо этого Go использует быстрые некриптографические хеш-алгоритмы (оптимизированные с использованием инструкций AES-NI, где это возможно), которые обеспечивают достаточную случайность для распределения, сохраняя при этом пропускную способность, необходимую для системного программирования.
Как рост карты (удвоение) сохраняет действительность существующих хеш-семен и обеспечивает правильное перераспределение записей?
Когда карта растет (обычно, когда коэффициент загрузки превышает 6,5 корзин), время выполнения выделяет новый массив вдвое большего размера. Во время инкрементальной эвакуации время выполнения повторно хеширует каждую запись, используя исходное случайное значение, но с новой маской корзины (высокие биты). Поскольку хеш детерминирован для данного семени, но количество корзин меняется, записи естественным образом рассеиваются по разным корзинам. Кандидаты часто упускают, что значение семени остается постоянным в течение всего времени жизни карты; только маска битов, используемая для выбора индекса корзины, меняется, что обеспечивает, чтобы затратная операция повторной хеширования происходила только во время роста, а не при каждом поиске.
В чем разница между хеш-функцией, используемой для карт, и хеш-функцией, используемой runtime.memhash для других целей, и почему это различие имеет значение?
Хотя обе используют схожие алгоритмы, хеширование карты включает случайное семя для каждой карты и специфичные для типа alg функции (через runtime.typeAlg) для обработки различных типов ключей (строки, целые числа, структуры). В отличие от этого, runtime.memhash — это универсальное средство для хеширования сырых байтов памяти без учета типа. Это различие имеет значение, потому что хеширование карты должно учитывать семантику равенства Go — например, гарантируя, что различные поля структур правильно влияют на хеш — в то время как memhash предназначен исключительно для последовательностей байтов. Понимание этого разделения подчеркивает, как Go оптимизирует как безопасность типов, так и производительность.