Является ли Quicksort потенциальной угрозой безопасности?

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

Как в базовой реализации, так и в улучшенных версиях, таких как 3-медиа-quicksort, есть особенность поведения девиантных для определенных входных данных, что означает, что их время выполнения может значительно увеличиться в этих случаях (с O(n^2) сложностью), не говоря уже о возможности потока stackoverflow.

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

В этом странном случае стоит вопрос безопасности (и поэтому заставит нас использовать Intro- или Mergesort)?

Изменить: Я знаю, что есть способы предотвратить худшие случаи Quicksort, но что касается языковых интегрированных ролей (например, 3-медиана .NET). Будут ли они табу?

Ответ 1

Да, это риск безопасности - DoS, чтобы быть конкретным - это тривиально смягчается добавлением проверки глубины рекурсии в вашей быстрой сортировке и переключением на что-то другое, если достигается определенная глубина. Если вы переключитесь на heapsort, вы получите introsort, что на самом деле использует многие реализации STL.

В качестве альтернативы вы просто производите выбор из элемента сводной таблицы.

Ответ 2

Многие реализации quicksort выполняются с помощью рандомизированной версии алгоритма. Это означает, что DoS-атака с помощью специально созданного ввода невозможна.

Кроме того, даже без этого большинство наборов данных слишком малы, чтобы иметь значение O (nlog) vs O (n ^ 2). Размер набора для сортировки должен быть довольно большим, чтобы иметь влияние. Даже с несколькими миллионами элементов разница во времени, вероятно, не будет очень большой.

В целом, любое данное веб-приложение, использующее quicksort, с большей вероятностью будет иметь другую безопасность недостатки.

Ответ 3

Взгляните на этот вопрос (и выделенный ответ), в котором обсуждаются способы сокращения наихудшего случая QuickSort:

Почему quicksort лучше, чем mergesort?

Ответ 4

Если производительность - это что-то важное, то QuickSort будет казаться плохим выбором в большинстве случаев, проблема безопасности или нет. Есть ли что-то, что заставляет вас уклоняться от алгоритмов, таких как Heapsort или Mergesort?

Ответ 5

Я думаю, что это очень вопрос о том, где вы на самом деле используете быструю сортировку. Использование алгоритмов O (n ^ 2) отлично подходит для работы с массивами из 5 элементов, например. С другой стороны, когда вероятность того, что данные могут быть значительно большими, опасаясь DoS - это не первая проблема, с которой вы столкнетесь - первая проблема будет плохой, если вы столкнулись с реальной проблемой. Учитывая большое количество других доступных алгоритмов, просто замените его, если он находится в критическом месте.

Ответ 6

Это, но только в очень, очень маловероятных случаях - все это легко для корректно разработанного алгоритма.

Но если вы хотите быть супербезопасным, вы можете использовать что-то вроде Introsort, которое начинается как QuickSort, но переключается на Heap Sort, если он обнаруживает на глубине рекурсии, что алгоритм начинает идти квадратично.

Изменить: Я вижу, что Павел избил меня в Introsort.

В ответе на отредактированный вопрос: Я лично не тестировал каждую библиотеку Quicksort, но я чувствую себя уверенно в том, что почти все из них имеют чеки, чтобы избежать худшего случая.