Условие
Инженер отдела информационной безопасности Иван разработал новую систему защиты от DDoS-атак. Ему выдали два сервера для тестов. На каждый из них Иван может отправить одновременно от 1 000 до 100 000 запросов (их количество всегда кратно тысяче). Если их окажется слишком много, сервер выйдет из строя и его больше нельзя будет использовать для тестов. Если сервер выдержит, эксперимент можно будет продолжить.
Задача
Какое минимальное количество DDoS-атак необходимо, чтобы гарантированно определить порог уязвимости системы защиты?
Решение
Кажется, что для начала можно отправить на сервер половину возможных запросов, то есть 50 000, и надеяться, что сервер выдержит. Если так и произойдет, можно будет перейти к алгоритму бинарного поиска и найти лимит за наименьшее количество атак.
Двоичный (бинарный) поиск — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины.
Итак, Иван отправил 50 000 запросов на сервер. Ничего не произошло. Прибегнув к алгоритму бинарного поиска, от отправил на него уже 75 000 запросов. Допустим, сервер вышел из строя. Продолжать в том же духе слишком рискованно, потому что у Ивана оставлся лишь один сервер. Теперь придется перебирать варианты в диапазоне от 51 000 до 74 000 по порядку. Но мы же хотим найти минимальное количество попыток, которое гарантирует достоверный результат. Выходит, бинарный поиск нам не подойдет.
Важно: у нас всегда есть лучший и худший варианты. Худшим будет вариант, когда мы начинаем с 50 000 запросов, а сервер выдерживает 49 000. После отключения первого сервера, останется только второй. В таком случае бинарный алгоритм не сможет гарантировать результат. А чтобы по порядку проверить запросы в диапазоне от 1 000 до 49 000, придется сделать 50 попыток. Это уже много! В лучшем варианте мы в первой попытке отправляем 1 000 запросов и сервер выходит из строя.
Получается, нам нужно найти наилучший случай из наихудших.
Алгоритм оптимального решения
Чтобы минимизировать максимальное число атак, используем следующую стратегию. С помощью первого сервера определяем диапазон значений:
- Начинаем атаку только на выбранных уровнях, чтобы определить диапазон, в котором находится критический уровень уязвимости.
- Если сервер выдержал атаку, переходим к следующему уровню.
На втором сервере уточняем уровень уязвимости: последовательно повышаем условный уровень уязвимости в диапазоне, найденном на первом этапе.
Если сервер падает после первой атаки, нам нужно будет проводить их, начиная только с первой группы (1 000 запросов). Значит, нужно рассчитывать, что после успешной атаки необходимо совершить атаку на меньшее количество запросов.
В этом случае, если сервер не отключился на уровне Х групп запросов, у нас останется Х-1 атак. Соответственно, нам нужно провести атаки так, чтобы их общее количество не превысило Х-1 до момента отключения сервера. Значит, нужно провести атаку на Х-1 групп запросов больше.
Таким образом мы выделим потенциальные уровни, с которых сервер может выйти из строя. Если он держится, можно провести следующую атаку на Х-2 групп больше. И так далее.
В результате мы получим последовательность:
Х + (Х — 1) + (Х — 2) + … +1
Для получения уравнения достаточно сравнить последовательность с максимальным количеством групп запросов — 100 (где будет 100 000 запросов).
Х + (Х — 1) + (Х — 2) + … +1 ≥ 100
То, что мы видим в левой части представляет собой формулу суммы арифметической прогрессии. Она выглядит следующим образом:
(Х * (Х + 1))/2 ≥ 100
Решив неравенство, получим: X ≥ 14
Соответственно, минимальное количество атак будет равно 14.
Пример
Тестирование первого сервера проводится на уровнях 14 000, 27 000, 39 000, 50 000 запросов и т. д. На 50-м уровне сервер выходит из строя. В таком случае нужно проверить диапазон от 40 000 по 49 000 запросов.
Тестирование второго сервера проводится по порядку на уровнях: 40, 41, …, 49. На 49-м уровне сервер выходит из строя. Критический уровень уязвимости найден.
