Является ли Quicksort потенциальной угрозой безопасности?
Мне просто интересно, можно ли (с некоторой серьезной паранойей и при определенных обстоятельствах) использовать алгоритм QuickSort как угрозу безопасности в приложении.
Как его базовая реализация, так и улучшенные версии, такие как 3-median-quicksort, имеют особенность поведения, отклоняющегося для определенных входных данных, что означает, что их время выполнения может значительно увеличиться в этих случаях (имея O(n^2) сложность) не говоря уже о возможности стекопотока.
Следовательно, я мог бы увидеть потенциальный вред, предоставляя предварительно отсортированные данные программе, которая заставляет алгоритм вести себя так, что может иметь непредсказуемые последствия, например, для многопользовательского веб-приложения.
Стоит ли рассматривать этот странный случай с точки зрения безопасности (и поэтому заставит нас вместо этого использовать Intro- или Mergesort)?
Редактировать: Я знаю, что есть способы предотвратить наихудшие случаи Quicksort, но как насчет языковых интегрированных сортировок (например, 3-медиана.NET). Будут ли они табу?
6 ответов
Да, это риск для безопасности - точнее, DoS, который тривиально смягчается добавлением проверки глубины рекурсии в вашу быструю сортировку и переключением на что-то другое вместо достижения определенной глубины. Если вы переключитесь на heapsort, то вы получите introsort, который фактически используют многие реализации STL.
Кроме того, вы просто случайным образом выбираете элемент поворота.
Многие реализации быстрой сортировки выполняются с использованием рандомизированной версии алгоритма. Это означает, что DoS-атака со специально созданным вводом невозможна.
Кроме того, даже без этого большинство наборов данных слишком малы, чтобы иметь значение O(nlog) против O(n^2). Размер набора для сортировки должен быть достаточно большим, чтобы иметь влияние. Даже с несколькими миллионами элементов разница во времени, вероятно, будет не очень большой.
В целом, любое веб-приложение, использующее быструю сортировку, с большей вероятностью имеет другие недостатки безопасности.
Взгляните на этот вопрос (и помеченный ответ), в котором обсуждаются способы уменьшения наихудшего случая QuickSort:
Если производительность важна, то в большинстве случаев QuickSort может показаться плохим выбором, из соображений безопасности или нет. Есть ли что-то, что заставляет вас уклоняться от таких алгоритмов, как Heapsort или Mergesort?
Я думаю, что это очень большой вопрос, где вы на самом деле используете быструю сортировку. Использование алгоритмов O(n^2) прекрасно, например, при работе с массивами из 5 элементов. С другой стороны, когда есть вероятность, что данные могут быть значительно большими, опасаясь, что DoS - это не первая проблема, с которой вы столкнетесь, - первая проблема будет заключаться в том, чтобы добиться плохой производительности, прежде чем вы столкнетесь с реальной проблемой. Учитывая большое количество других доступных алгоритмов, просто замените его, если он находится в критическом месте.
Это так, но только в очень, очень маловероятных случаях - все это легко избежать с помощью правильно разработанного алгоритма.
Но если вы хотите быть супер-безопасным, вы можете использовать что-то вроде Introsort, который начинается как QuickSort, но переключается на Heap Sort, если он обнаруживает по глубине рекурсии, что алгоритм начинает работать квадратично.
Изменить: я вижу, Павел избил меня до интросорта.
В ответ на отредактированный вопрос: я лично не проверял каждую библиотеку Quicksort, но чувствую себя уверенно, что почти все они имеют проверки, чтобы избежать наихудшего случая.