Блог пользователя I_love_natalia

Автор I_love_natalia, 12 лет назад, По-русски

После небольших обсуждений, мы решили все-таки выложить код генератора, который вызывает #TLE у коллекций HashSet и HashMap в Java.

Вот он — http://pastebin.com/qpyNcD3R

Идея: давайте заставим хеш-коллекции складывать все элементы в одну корзину.

Особенность реализации HashSet/HashMap в том, что они использует линейное преобразование хеша, а затем как номер корзины использует остаток от деления хеша на bucketsNumber.

Цитаты из оригинального кода:

    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    static int indexFor(int h, int length) { 
        return h & (length-1); /*length всегда степень двойки --- DK*/
    }

Собственно, вся сложность заключается в построении обратного преобразования — вот оно:

    int hashinv(int h) {
        h ^= (h >>> 4) ^ (h >>> 7) ^ (h >>> 8) ^ (h >>> 14) ^ (h >>> 15)
                ^ (h >>> 18) ^ (h >>> 19) ^ (h >>> 20) ^ (h >>> 21)
                ^ (h >>> 23) ^ (h >>> 26) ^ (h >>> 28);
        return h;
    }

Далее, просто выписываем числа:

    final int size = 100000;
    int[] s = new int[size];
    for (int i = 0, val = 0; i < size; i++) {
        s[i] = Integer.MAX_VALUE;
        while (s[i] > 1000000000)
            s[i] = hashinv(bitreverse(val++));
    }

Здесь bitreverse обращает порядок младших 31 бита в числе.

Этот генератор работает для версий Java 6 и Java 7 при любом не очень сложном преобразовании порядка ввода (сортировка, random_shuffle, и т.д.).

Удачных вам взломов!

  • Проголосовать: нравится
  • +79
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Заваливать библиотеки с уязвимостями — дело хорошее. В конечном счёте, если авторам библиотечной функции показать, что это реальная проблема, все от этого даже выигрывают.

Для пар и троек целых чисел, насколько я знаю, некоторые среды программирования умеют генерировать реализацию по умолчанию, так что тоже можно завалить.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Честно говоря, здесь вообще нет идей, как избежать возможного #TLE и не потерять при этом производительность в среднем случае.

    С философской точки зрения, СП содержит огромный перегиб в пункте "должно работать на всех тестах". Правильно — "должно работать на всех РАЗУМНЫХ тестах". Вряд ли когда-нибудь кто-нибудь сталкивался с проблемой, описанной выше, не создавая ее специально. Совершенно неясно, как использовать ее, как и проблему с #TLE в Arrays.sort, вне СП; то же самое (вероятно, такой генератор тоже сделаем) с известной полиномиальной хеш-функцией для String в Java. Весь мой опыт практического программирования протестует против учета столь редких возможных проблем на практике.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      Теоретически, можно заDoSить/заDDoSить что-нибудь, практически — сам этого не делал.

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Сами придумали обратное преобразование?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Кажется, что это не сложнее, чем обратить матрицу 32 × 32 — какие биты исходного вектора складываются в какие биты полученного. А потом внимательно посмотреть на результат, и он тоже окажется состоящим из диагоналей, на которых стоят единицы. Или не окажется?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Понадобилось 10 минут. Кажется, делал так:

    1. Очевидно, что оно имеет такой вид.
    2. Будем проверять hash(hashinv(x)) для степеней двойки 1,2,4,8, ...
    3. Как только hash(hashinv(2^k)) != 2^k, надо дописать компонент (h >>> k) в метод hashinv
»
12 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

По-хорошему, надо бы как-то запретить правилами юзать подобные "особенности" компиляторов...

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    А мне кажется, что это полностью логично. Захотел человек использовать такой язык/компилятор — изволь познакомиться с особенностями стандартной библиотеки.

    Отношение у меня к этому такое же, как и к просьбам поднять ограничение для Python'а в пару раз, когда авторское решение на C++ заходит с 5-кратным запасом.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Я думаю, можно просто не делать таких задач. Например, на 129 раунде ничто не мешало авторам ограничить значения чисел величиной 2n. Проверка на то, что участники умеют сжимать координаты, она глупая какая-то, по-моему.

    Массивы вполне можно давать уже отсортированными. А если приходится сортировать что-то сложное, надо писать классы, и Java их mergesort-ом сортирует, т.е. с этим проблем нет.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Проблемы как минимум в том, что:

    1. это будет очень сложно отсечь формальным правилом,

    2. то, что добавление такого правила ставит участников в более равные условия — спорно.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -15 Проголосовать: не нравится

      1. это будет очень сложно отсечь формальным правилом

      Формального правила конечно не нужно. Обычно во всех видах спорта подобные тонкие моменты обходятся правилом под названием "на усмотрение арбитра". Провозгласить что-то типа: "Запрещено использование уязвимостей стандартных функций". А разбираться уже по факту...

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

    Как вы себе это представляете?
    Давайте лучше запретим участникам делать выходы за границу массивов, потому что они в некоторых языках ловятся сложнее.
    Нравится писать на Java — пожалуйста. У нее более мощная библиотека — пользуйтесь. Но то что авторы не удосужились написать сортировку за NlogN не в среднем, а всегда, и их hash на ура ломается за 10 минут — это ваши проблемы. Тем более, что Prewritten code разрешен. Напишите свою сортировку и свой hashset которые будут без таких проблем.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А заодно и свою Java ... тошнить от такого начинает. Здесь в конце концов алгоритмы важны или теперь всё превращается в использование "косяков" в реализации определенного языка ? Давайте тогда и в С++ поищем... сразу подключим Питон с Руби... там медленное чтение, так давайте давать столько данных, чтобы на них не проходило... это же тоже вроде "уязвимости" ?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +48 Проголосовать: не нравится

        Если вы найдете тест, на котором валится std::sort я обещаю добавлять его во все задачи, которые делаю.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Питон, кстати, автоматически получается завален в половине задач.

        Например, какую-нибудь тривиальную динамику на двумерном массиве 2000 × 2000 в две секунды впихнуть уже довольно сложно.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +38 Проголосовать: не нравится

        Мое мнение: это соревнования по программированию, а не по дискретной математике, теории алгоритмов и проблемам вычислимости. Надо не только придумать решение, но и написать его так, чтобы работало быстро и не валилось (даже по глупым ошибкам). Причины взрыва шаттла через полторы минуты после старта мало волнуют космонавтов.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Если бы не было взломов, такое бы делалось неформальным "ай-яй, авторы так не делайте". Как это можно запретить на взломах — совсем не ясно.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

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

      P.S. Надеюсь написанное выше, не только мне кажется бредом.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ну и компилятор доступный только один, само собой лол

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Эм, а в этом языке запретить случайные коллизии хешей?

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          Обязательно. Если у тебя/в результате твоего взлома случилась коллизия хешей или вообще не общий случай чего-нибудь, то сразу дисквал. А лучше со всему участниками контеста. На всякий случай.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится -45 Проголосовать: не нравится

        Просто раздельные рейтинги по языкам.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    На самом деле это лечится за 4 минуты своим наследованием от HashMap/Set и похожей функцией хеширования, разве нет?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Адаптировать генератор к похожей функции хеширования — дело тех же нескольких минут...

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Можно константы для сдвига случайные брать попробовать.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          Тогда они случайно окажутся близки к нулю или размеру машинного слова, и тормозить будет уже на каком-нибудь совершенно обычном тесте (не взломе) — например, на числах, кратных большой степени двойки.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Ну скажем если генерить как +/- единицу от тех, что есть, мне кажется к совсем катастрофическим последствиям не должно приводить. В то же время, генератор с гарантией с первой попытки ломать уже вроде не должен.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Ну, это обходится — h ^ (h >> rand(2, 5)) ^ (h >> rand(6, 9)) ^ ...

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +11 Проголосовать: не нравится

          Можно солить хеш случайным числом, выбираемым при старте программы.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится

            Каким образом солить? Xor и сложение по модулю 2^32 не покатит точно. Сложение по некоторому другому модулю — крайне сомнительно. Если множить по модулю — надо писать лишнее деление по модулю.

»
12 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Спасибо! Значит будем использовать TreeMap : — )

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Well, then the question arises.. what should I use then?!

»
11 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

В Java 8 похоже решили эту проблему:

http://openjdk.java.net/jeps/180

Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    Alternative String hashing implementation
    http://hg.openjdk.java.net/jdk8/jdk8/jdk/rev/43bd5ee0205e

    Так что вроде бы не решили.

    А, это старое изменение. Для String теперь все должно быть надежно. Но они обещают что-то совсем непонятное. Деревья вместо списков? Это скорее всего на обычных (не имеющих целью ничего завалить) данных будет медленнее работать, чем текущая реализация.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      может и не будет медленнее — они ввели threshold в HashMap.java:

      /**
      * The bin count threshold for using a tree rather than list for a
      * bin.  Bins are converted to trees when adding an element to a
      * bin with at least this many nodes.
      ... */
      static final int TREEIFY_THRESHOLD = 8;
      
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It seems to take a lot of time to find enough numbers less than 100000 while it barely take time to find enough numbers less than 1000000000.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What about if I change the load factor?
As I know bucketsCount would be different and the code for hacking should be different (I guess).