Тут у меня в rss-ленте недавно прошло нечто, что связано с предыдущим постом. Оказывается, некоторые устраивают "атаки" на знании хеш-фукнции. Так как часть софта открыта, то генерируется набор с равными хешами. Соответственно, добавление всего набора будет за квадрат.
В ruby типа даже реализацию словарей пофиксили. Только у некоторых приложения стали падать, так как они заложились на порядок добавления в словарь. foreach-итератор выдает не в том порядке, в котором элементы были добавлены. Можно ли вообще полагаться на порядок добавления в контейнер? Сложный философский вопрос... В интерфейсе/контракте это сложно описать. Документация/спецификация гарантий мало дает, это ж просто текст.
Не знаю ситуации насчет анти-qsort. В том же .нет антиКуСорт очевидным образом применим, там вообще выбирается средний элемент (и в куче других платформ, не только .нет). Оказывается, что если выбирать случайный разделяющий элемент, то все равно все плохо. Пытались выжать из этого спортивную задачку, через 15 минут пришли к выводу, что это уже халява. Что-то с этой идеи выжали, получилась средняя динамика за 4-ую (или 6?).
Вообще, атаки на алгоритмику по определению прикольны. Это вам не sql-injection пихать. Тут (увы, избитая фраза, но) думать надо. Причем в любой(!) маломальской области надо думать. И хеши, и сортировка, и регекспы и etc...
Не так страшны падающие самолеты, как софт написанный для самолетов.
В ruby типа даже реализацию словарей пофиксили. Только у некоторых приложения стали падать, так как они заложились на порядок добавления в словарь. foreach-итератор выдает не в том порядке, в котором элементы были добавлены. Можно ли вообще полагаться на порядок добавления в контейнер? Сложный философский вопрос... В интерфейсе/контракте это сложно описать. Документация/спецификация гарантий мало дает, это ж просто текст.
Не знаю ситуации насчет анти-qsort. В том же .нет антиКуСорт очевидным образом применим, там вообще выбирается средний элемент (и в куче других платформ, не только .нет). Оказывается, что если выбирать случайный разделяющий элемент, то все равно все плохо. Пытались выжать из этого спортивную задачку, через 15 минут пришли к выводу, что это уже халява. Что-то с этой идеи выжали, получилась средняя динамика за 4-ую (или 6?).
Вообще, атаки на алгоритмику по определению прикольны. Это вам не sql-injection пихать. Тут (увы, избитая фраза, но) думать надо. Причем в любой(!) маломальской области надо думать. И хеши, и сортировка, и регекспы и etc...
Не так страшны падающие самолеты, как софт написанный для самолетов.
Сообщения
Комментариев нет:
Отправить комментарий