TLDR

Если вы пишете на питоне, используете set или dict и хотите избежать взломов -- можете читать только последний раздел.

Введение

Большинство людей, интересующихся взломами знают про метод создания тестов, нацеленных против unordered контейнеров в C++. Подробнее этот метод описан в посте. Однако гораздо хуже освещено создание подобных тестов для set и dict в python, что я и решил исправить данным постом.

Немного теории о хеш-таблицах

Я не буду вдаваться в подробные описания и доказательства, поскольку их полно в открытых источниках. Разберем только то, что нас интересует в данном случае.

Хеш-таблица c открытой адресацией -- это структура данных, которая хранит набор элементов в массиве заведомо большего размера, определяя позицию очередного элемента, как его хеш, взятый по модулю размера массива. Если хеши нескольких элементов дают одну и ту же ячейку в массиве, то хеш-таблица пытается взять другую ячейку по некоторому правилу, которое зависит от конкретной реализации таблицы. Обычно это правило сводится к проверке ячеек $$$f(x), f(f(x)), f(f(f(x)))$$$ и так далее, пока не найдется пустая. В качестве функции $$$f$$$ часто берется линейное преобразование $$$(a * x + b) \% size$$$, где $$$size$$$ -- размер массива, а $$$a$$$ и $$$b$$$ взаимно просты с ним.

Python

В Python для реализации dict используется хеш-таблица с размером массива, равным степени двойки, а преобразование чуть сложнее простого линейного -- $$$f(x) = (5x + 1 + pertrub) \% size$$$, где $$$pertrub$$$ изначально равен хешу, но на каждом шаге уменьшается в 32 раза. Подробную реализацию можно посмотреть в репозитории.

Кроме того, хеш функция для чисел в питоне очень предсказуема, это просто само число.

Таким образом, для составления контртеста достаточно найти последовательность индексов, которые будут перебираться для конкретного числа и заранее занять их, а затем спровоцировать поиск этого числа в словаре, что довольно легко сделать для большинства задач.

Реализация set в Python3 чуть сложнее, там проверяется не одна ячейка, а 10 последовательных, что можно наблюдать тут. Однако построить тест в этом случае тоже не очень сложно, достаточно вместо одного числа $$$x$$$ добавлять $$$x, x + 1, x + 2, ..., x + 9$$$.

Проверка

Для проверки я использовал посылки 153032429 (Спасибо turkids за нее) и 153408991 c Codeforces Round 781 (Div. 2). Результат можно найти в виде взломов номер 796358 и 796362. Судя по результату "Неизвестный вердикт", все пошло слишком хорошо и я заодно сломал авторское решение. Подробнее могут знать shishyando и Kirill22.

Как защититься?

В отличие от C++, Python не предоставляет возможности определить свою хеш-функцию для существующего типа (или я о ней просто не знаю), однако никто не мешает определить свой тип c другой хеш-функцией:

from random import getrandbits

RANDOM = getrandbits(32)

class Wrapper(int):
    def __init__(self, x):
        int.__init__(x)
    def __hash__(self):
        return super(Wrapper, self).__hash__() ^ RANDOM

Пример использования такого типа можно найти в 153409562. К сожалению, пока авторское решение ломается на моих тестах я не смогу проверить устойчивость своего решения с классом Wrapper. Однако локально оно работает достаточно быстро.