Здравствуйте, gegMOPO4, Вы писали:

MOP>21.02.12 12:18, Nicht написав(ла):
>> Здравствуйте, gegMOPO4, Вы писали:
>> MOP>С этим, кстати, связана интересная уязвимость. Легко сгенерировать тысячи коротких строк, имеющих одинаковый хеш (по используемой в данном языке формуле). На сервер отправляется небольшой (десятки килобайт) запрос, содержащий эти строки в качестве имён параметров, сервер приложений/фреймворк разбирает его, складывая параметры в хештаблицу и благодаря O(N^2) загрузает на несколько минут. Очень малым трафиком организуется DOS.
>> Не понятно где там O(N^2), вроде в вырожденом случае хештейбл — это линкед лист и там поиск это O(N). Но в принципе, мысль интересная.

MOP>O(N) — для добавления N-го параметра. В сумме будет O(N^2).

Добавляется там за O(1). Добавление происходит в голову списка.
Единственное, что при большом количестве элементов, там несколько раз будет происходить ресайз таблицы, где происходит поэлеметное копирование. Но это все равно O(N)и он самортизирован на количество добавлений.

21.02.12 12:40, Nicht написав(ла):
> Здравствуйте, gegMOPO4, Вы писали:
> MOP>21.02.12 12:18, Nicht написав(ла):
>>> Здравствуйте, gegMOPO4, Вы писали:
>>> MOP>С этим, кстати, связана интересная уязвимость. Легко сгенерировать тысячи коротких строк, имеющих одинаковый хеш (по используемой в данном языке формуле). На сервер отправляется небольшой (десятки килобайт) запрос, содержащий эти строки в качестве имён параметров, сервер приложений/фреймворк разбирает его, складывая параметры в хештаблицу и благодаря O(N^2) загрузает на несколько минут. Очень малым трафиком организуется DOS.
>>> Не понятно где там O(N^2), вроде в вырожденом случае хештейбл — это линкед лист и там поиск это O(N). Но в принципе, мысль интересная.
> MOP>O(N) — для добавления N-го параметра. В сумме будет O(N^2).
> Добавляется там за O(1). Добавление происходит в голову списка.
> Единственное, что при большом количестве элементов, там несколько раз будет происходить ресайз таблицы, где происходит поэлеметное копирование. Но это все равно O(N)и он самортизирован на количество добавлений.

Добавление включает поиск.

Здравствуйте, Nicht, Вы писали:

N>Но в принципе, мысль интересная.
Это не просто интересная мысль, а реальная уязвимость в PHP и Tomcat. Сравнительно недавно только исправили.
Tomcat по-умолчанию принимает POST запросы размером до 2Мб и, напрямую, парсит POST параметры в HashMap.
Если параметры набить ключами с совпадающими String.hashCode(), то специально сформированый запрос в 2Мб укладывает одно ядро Core i5 на 40 минут!
Никакой распределенной атаки не нужно. С одного узла можно завалить таким образом почти любой сервер.

Здравствуйте, gegMOPO4, Вы писали:

MOP>21.02.12 12:40, Nicht написав(ла):
>> Здравствуйте, gegMOPO4, Вы писали:
>> MOP>21.02.12 12:18, Nicht написав(ла):
>>>> Здравствуйте, gegMOPO4, Вы писали:
>>>> MOP>С этим, кстати, связана интересная уязвимость. Легко сгенерировать тысячи коротких строк, имеющих одинаковый хеш (по используемой в данном языке формуле). На сервер отправляется небольшой (десятки килобайт) запрос, содержащий эти строки в качестве имён параметров, сервер приложений/фреймворк разбирает его, складывая параметры в хештаблицу и благодаря O(N^2) загрузает на несколько минут. Очень малым трафиком организуется DOS.
>>>> Не понятно где там O(N^2), вроде в вырожденом случае хештейбл — это линкед лист и там поиск это O(N). Но в принципе, мысль интересная.
>> MOP>O(N) — для добавления N-го параметра. В сумме будет O(N^2).
>> Добавляется там за O(1). Добавление происходит в голову списка.
>> Единственное, что при большом количестве элементов, там несколько раз будет происходить ресайз таблицы, где происходит поэлеметное копирование. Но это все равно O(N)и он самортизирован на количество добавлений.

MOP>Добавление включает поиск.

А, туплю. Ты прав. Проверяется существование такого ключа.

Здравствуйте, gegMOPO4, Вы писали:

MOP>Как максимум это Long.MAX_VALUE. А массив может расти по мере надобности.

С переаллокацией и копированием. Мы не в Win API с VirtualAlloc/MEM_RESERVE/MEM_COMMIT

MOP>Если множество ключей сгруппировано кластерами, с большими промежутками между ними, можно использовать многоуровневый массив — эдакое дерево фиксированной небольшой высоты (тоже O(1)). Но без этого дополнительного предположения — только линейный массив.

Ничего не сгруппировано, никаких зависимостей нет.

21.02.12 14:03, Pavel Dvorkin написав(ла):
> Здравствуйте, gegMOPO4, Вы писали:
> MOP>Как максимум это Long.MAX_VALUE. А массив может расти по мере надобности.
> С переаллокацией и копированием. Мы не в Win API с VirtualAlloc/MEM_RESERVE/MEM_COMMIT

Заполнение массива всё равно O(N) (где N — максимальный индекс), а доступ — O(1).

> MOP>Если множество ключей сгруппировано кластерами, с большими промежутками между ними, можно использовать многоуровневый массив — эдакое дерево фиксированной небольшой высоты (тоже O(1)). Но без этого дополнительного предположения — только линейный массив.
> Ничего не сгруппировано, никаких зависимостей нет.

Тогда эта задача имеет пустое множество решений. Но на самом деле зависимости есть, вы упоминали, что скорее всего индексы будут до Integer.MAX_VALUE (и наверняка есть другие предположения). Для реальных данных можно подобрать удовлетворяющее решение, если правильно переформулировать задачу. Сортированный массив, бинарное дерево, дерево фиксированной глубины — что-то при определённых условиях может подойти.

Здравствуйте, gegMOPO4, Вы писали:

>> MOP>Как максимум это Long.MAX_VALUE. А массив может расти по мере надобности.
>> С переаллокацией и копированием. Мы не в Win API с VirtualAlloc/MEM_RESERVE/MEM_COMMIT

MOP>Заполнение массива всё равно O(N) (где N — максимальный индекс), а доступ — O(1).

Хэш нет, там O(N) никогда не будет. А задерки не нужны.

>> MOP>Если множество ключей сгруппировано кластерами, с большими промежутками между ними, можно использовать многоуровневый массив — эдакое дерево фиксированной небольшой высоты (тоже O(1)). Но без этого дополнительного предположения — только линейный массив.
>> Ничего не сгруппировано, никаких зависимостей нет.

MOP>Тогда эта задача имеет пустое множество решений. Но на самом деле зависимости есть, вы упоминали, что скорее всего индексы будут до Integer.MAX_VALUE (и наверняка есть другие предположения). Для реальных данных можно подобрать удовлетворяющее решение, если правильно переформулировать задачу. Сортированный массив, бинарное дерево, дерево фиксированной глубины — что-то при определённых условиях может подойти.

Собственно, говоря, против мэпа (хешмэпа) я ничего против не имею. Вопрос был просто о том, нельзя ли его ускорить, сыграв на уникальности ключей.

В общем виде (есть произвольное множество хотя бы int, не говоря уж о long, надо O(1) на все операции) — конечно, не имеет решения ). Но я такого решения и не просил

И все же VirtualAlloc/MEM_RESERVE, с ее помощью можно на int (в x64) решение получить . Мне там 4GB адресного пространства не жалко, а реальной памяти понадобится максимум 4К * nKeys.

22.02.12 14:58, Pavel Dvorkin написав(ла):
> Здравствуйте, gegMOPO4, Вы писали:
>>> MOP>Как максимум это Long.MAX_VALUE. А массив может расти по мере надобности.
>>> С переаллокацией и копированием. Мы не в Win API с VirtualAlloc/MEM_RESERVE/MEM_COMMIT
> MOP>Заполнение массива всё равно O(N) (где N — максимальный индекс), а доступ — O(1).
> Хэш нет, там O(N) никогда не будет. А задерки не нужны.

Вообще-то, для заполнения коллекции N независимыми элементами всегда нужно по крайней мере O(N) времени (нужно добавить каждый элемент).

> Собственно, говоря, против мэпа (хешмэпа) я ничего против не имею. Вопрос был просто о том, нельзя ли его ускорить, сыграв на уникальности ключей.

Можно. Зависит от сценария использования. Если ключи гарантированно уникальны, то можно при добавлении не искать ключ в списке, а сразу добавлять в него. Возможно, выгоднее будет в bucket-е непрерывный массив, а не список (это нужно тестировать). Если коллекция сперва заполняется, а потом много используется без вставки/удаления (или очень редкими), то массивы в bucket-ах стоит отсортировать после заполнения и потом использовать бинарный поиск. И, разумеется, выгода будет от использования long вместо Long и тем более Object, — и по памяти, и по доступу, и по о�
�ерациям хеша и сравнения.

> В общем виде (есть произвольное множество хотя бы int, не говоря уж о long, надо O(1) на все операции) — конечно, не имеет решения ). Но я такого решения и не просил

Ну, ваши требования поначалу были довольно категоричны.

> И все же VirtualAlloc/MEM_RESERVE, с ее помощью можно на int (в x64) решение получить . Мне там 4GB адресного пространства не жалко, а реальной памяти понадобится максимум 4К * nKeys.

Кхм, если я правильно понимаю, о чём вы, то это то, что я упоминал с самого начала — дерево фиксированной высоты (2, 3 или 4, не помню, как в современных процессорах). То же можно реализовать и на Java — разрезать индекс на биты (по 16, например, или по 10) и использовать во вложенных массивах. Исходя из особенностей задачи практичнее для индексов меньше M1 хранить значения прямо в массиве, меньше M2 — в подмассивах (дерево высоты 2), меньше M3 — в подподмассивах (высоты 3) и т.д. Тогда для большинства ключей вложенность будет небольшой, быстрее доступ.

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

Здравствуйте, Blazkowicz, Вы писали:

B>Здравствуйте, Nicht, Вы писали:

N>>Но в принципе, мысль интересная.
B>Это не просто интересная мысль, а реальная уязвимость в PHP и Tomcat.

а где томкат там и Glassfish — тоже надо обновиться (на 3.1.2)

Здравствуйте, GarryIV, Вы писали:

B>>Это не просто интересная мысль, а реальная уязвимость в PHP и Tomcat.
GIV>а где томкат там и Glassfish — тоже надо обновиться (на 3.1.2)
У исследователей в документе длинный список был, там и RoR и груви и пр. Просто публичных сайтов на GlassFish не так много, как на Tomcat.

Здравствуйте, gegMOPO4, Вы писали:

>> Хэш нет, там O(N) никогда не будет. А задерки не нужны.

MOP>Вообще-то, для заполнения коллекции N независимыми элементами всегда нужно по крайней мере O(N) времени (нужно добавить каждый элемент).

Да, только заполнение идет по времени очень неторопливо, так что на одно заполнение там O(почти 1), а на все — несущественно. А вот переаллокация пройзойдет однажды, и не быстро, и именно при одном добавлении.

>> В общем виде (есть произвольное множество хотя бы int, не говоря уж о long, надо O(1) на все операции) — конечно, не имеет решения ). Но я такого решения и не просил

MOP>Ну, ваши требования поначалу были довольно категоричны.

Почему ? См. исходное письмо. Я там никого не просил дать O(1).

>> И все же VirtualAlloc/MEM_RESERVE, с ее помощью можно на int (в x64) решение получить . Мне там 4GB адресного пространства не жалко, а реальной памяти понадобится максимум 4К * nKeys.

MOP>Кхм, если я правильно понимаю, о чём вы, то это то, что я упоминал с самого начала — дерево фиксированной высоты (2, 3 или 4, не помню, как в современных процессорах). То же можно реализовать и на Java — разрезать индекс на биты (по 16, например, или по 10) и использовать во вложенных массивах. Исходя из особенностей задачи практичнее для индексов меньше M1 хранить значения прямо в массиве, меньше M2 — в подмассивах (дерево высоты 2), меньше M3 — в подподмассивах (высоты 3) и т.д. Тогда для большинства ключей вложенность будет небольшой, быстрее доступ.

Да, с одной разницей — это придется сделать, а в Win API это уже сделано.

MOP>Разумеется, в худшем случае (каждое число на отдельной странице) виртуальное пространство очень быстро станет физическим. Поэтому на совести предоставившего информацию о природе данных.

Конечно. На этом-то и вся игра : значения ключей произвольные от 0 до maxint, а самих их мало.