algorithm - que - quicksort recursivo
¿Es Quicksort un riesgo potencial de seguridad? (6)
Creo que esta es una cuestión de dónde se está usando la clasificación rápida. Usar los algoritmos O (n ^ 2) es perfectamente correcto cuando trabaja con matrices de 5 elementos, por ejemplo. Por otro lado, cuando existe la posibilidad de que los datos puedan ser significativamente grandes, temiendo un DoS no es el primer problema al que te enfrentarás, el primer problema será obtener un mal rendimiento antes de enfrentar un problema real. Dada la gran cantidad de otros algoritmos disponibles, simplemente sustitúyalos si están en una ubicación crítica.
Simplemente me pregunté si (con cierta paranoia y en ciertas circunstancias) el uso del algoritmo QuickSort puede considerarse un riesgo de seguridad en una aplicación.
Tanto su implementación básica como las versiones mejoradas como 3-median-quicksort tienen la peculiaridad de comportarse de manera desviado 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 mencionar la posibilidad de un stackoverflow.
Por lo tanto, vería el potencial de causar daño al proporcionar datos ordenados previamente a un programa que hace que el algoritmo se comporte de esta manera, lo que podría tener consecuencias impredecibles, por ejemplo, para una aplicación web de múltiples clientes.
¿Este caso extraño merece alguna consideración de seguridad (y, por lo tanto, nos obligaría a utilizar Intro o Mergesort en su lugar)?
Edición: sé que hay formas de prevenir los peores casos de Quicksort, pero ¿qué pasa con el tipo de lenguaje integrado (como el 3-Median de .NET). ¿Serían tabúes?
Eche un vistazo a esta pregunta (y la respuesta marcada) que analiza las formas de reducir el peor de los casos de QuickSort:
Es, pero solo en casos muy, muy improbables, todos los cuales son fáciles de evitar para un algoritmo adecuadamente diseñado.
Pero si quiere estar súper seguro, puede usar algo como introsort , que comienza como QuickSort pero cambia a Heap Sort si detecta a partir de la profundidad de la recursión que el algoritmo está empezando a ser cuadrático.
Edit: veo que Pavel me venció a Introsort.
En respuesta a la pregunta editada: no he probado personalmente todas las bibliotecas de Quicksort, pero me siento seguro apostando a que casi todas tienen comprobaciones para evitar el peor de los casos.
Muchas implementaciones de quicksort se realizan utilizando una versión aleatoria del algoritmo . Esto significa que un ataque DoS con entrada especialmente diseñada no es posible.
Además, incluso sin esto, la mayoría de los conjuntos de datos son demasiado pequeños para tener importancia O (nlog) frente a O (n ^ 2). El tamaño del conjunto a ordenar tendría que ser bastante grande 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 que use quicksort es mucho más probable que tenga otras flaws security .
Sí, es un riesgo de seguridad (DoS, para ser específico) que se mitiga de manera trivial al agregar una verificación de la profundidad de la recursión en su expedición rápida, y cambiar a otra cosa si se alcanza una cierta profundidad. Si cambia a introsort , obtendrá introsort , que es lo que realmente usan muchas implementaciones de STL.
Alternativamente, simplemente aleatoriza la selección del elemento de pivote.
Si el rendimiento es algo que importa, entonces QuickSort parecería una mala elección en la mayoría de las circunstancias, por razones de seguridad o no. ¿Hay algo que haga que te alejes de algoritmos como Heapsort o Mergesort?