Se QuickSort un riesgo?

Question

Me preguntaba si (con un poco de paranoia grave y bajo ciertas circunstancias) el uso de la QuickSort algoritmo puede ser visto como un riesgo de seguridad en una aplicación.

Tanto su implementación básica y versiones mejoradas como 3-mediana-ordenación rápida tienen la peculiaridad de comportarse desviada para ciertos datos de entrada, lo que significa que su tiempo de ejecución puede aumentar extremadamente en estos casos (con O(n^2) complejidad) por no hablar de la posibilidad de un stackoverflow.

Por lo tanto, me gustaría ver el potencial de hacer daño al proporcionar los datos pre-ordenar en una Programm que hace que el algoritmo de comportarse de esta manera, lo que podría tener consecuencias impredecibles para, por ejemplo, una aplicación web multi-cliente.

¿Es este extraño caso digno de cualquier consideración de seguridad? (Y por lo tanto nos obligan a utilizar Intro - o por fusión en su lugar)

Editar: Sé que hay maneras de prevenir peores casos de ordenación rápida, pero qué pasa con las clases de lenguaje integrado (como el 3-La mediana de .NET). ¿Serían tabú?

Answer 1

Sí, es un riesgo de seguridad - DoS, para ser específico - que es trivialmente mitigado mediante la adición de un cheque por nivel de recursividad en su clasificación rápida, y el cambio a otra cosa en su lugar si se llega a una cierta profundidad. Si cambia a HeapSort, entonces obtendrá introsort , que es lo que muchas implementaciones usan STL realidad .

Como alternativa, sólo aleatoriamente la selección de elemento de pivote.

Answer 2

Muchas implementaciones de ordenación rápida se realiza mediante una aleatorizados versión del algoritmo . Esto significa un ataque DoS con entrada especialmente diseñado no es posible.

Además, incluso sin esto, la mayoría de los conjuntos de datos son simples demasiado pequeña para tener O (n log) vs O (^ 2 n) materia. El tamaño del conjunto de tipo tendría que ser bastante grande como para tener un impacto. Incluso con unos pocos millones de elementos, la diferencia de tiempo probablemente no sería muy grande.

En general, cualquier aplicación web dada usando la clasificación rápida es mucho más propensos a tener otros href="http://en.wikipedia.org/wiki/Sql_injection" seguridad defectos .

Answer 3

Tome un vistazo a esta pregunta (y respuesta marcada), que analiza la forma de reducir peor de los casos de QuickSort:

¿Por qué es mejor que la clasificación rápida mergesort?

Answer 4

Si el rendimiento es algo que importa, entonces QuickSort parecería una mala elección en la mayoría de las circunstancias, la preocupación de seguridad o no. ¿Hay algo que le hace a alejarse de los algoritmos como heapsort o por fusión?

Answer 5

Creo que esto es en gran medida una cuestión de dónde realmente está utilizando el tipo rápido. El uso de O (n ^ 2) algoritmos es perfectamente bien cuando su trabajo con matrices de 5 elementos, por ejemplo. Por otro lado, cuando hay una posibilidad de que los datos pueden ser significativamente más grande, por temor a una denegación de servicio no es el primer problema que se enfrentará - el primer problema será conseguir mala manera el rendimiento antes de que esté frente a un problema real. Dado el gran número de otros algoritmos disponibles, sólo tiene que sustituir si es en un lugar crítico.

Answer 6

Es, pero sólo en casos muy, muy improbables - todos los cuales son fáciles para un algoritmo diseñado adecuadamente a evitar.

Pero si quieres ser súper seguro, es posible que desee utilizar algo como Introsort , que comienza como QuickSort pero cambia a la pila de clasificación si detecta desde el nivel de recursividad que el algoritmo está empezando a ir cuadrática.

Editar Veo Pavel me adelantó Introsort.

En respuesta a la pregunta Editado: no he probado personalmente cada biblioteca única ordenación rápida, pero me siento segura de apuestas que más o menos todos ellos tienen controles en su lugar para evitar el peor de los casos