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

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

Почему быстрая сортировка лучше, чем сортировка слиянием?

Answer 4

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

Answer 5

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

Answer 6

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

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

Редактировать: Я вижу, как Павел избил меня до интросорта.

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