È QuickSort un potenziale rischio per la sicurezza?

Question

Mi chiedevo solo se (con un po 'di paranoia grave e in determinate circostanze) l'uso del QuickSort algoritmo può essere visto come un rischio per la sicurezza in un'applicazione.

Sia sua implementazione di base e versioni migliorate come 3-mediano-Quicksort hanno la peculiarità di comportarsi deviante per alcuni dati di ingresso, il che significa che la loro esecuzione può aumentare estremamente in questi casi (avente O(n^2) complessità) per non parlare della possibilità di uno StackOverflow.

Quindi vorrei vedere potenziale per fare del male, fornendo i dati pre-ordinato a un programma che fa sì che l'algoritmo a comportarsi in questo modo, che potrebbe avere conseguenze imprevedibili per esempio un'applicazione multi-client Web.

E 'questo strano caso merita alcuna considerazione la sicurezza? (E sarebbe quindi ci costringono a usare Intro - o Mergesort , invece)

Modifica: So che ci sono modi per prevenire i casi peggiori di Quicksort, ma per quanto riguarda i tipi di lingue integrato (come il 3-mediana della NET). Sarebbero tabù?

Answer 1

Sì, si tratta di un rischio per la sicurezza - DoS, per essere precisi - che è banalmente mitigato con l'aggiunta di un assegno di profondità di ricorsione in quicksort, e di passare a qualcos'altro se si raggiunge una certa profondità. Se si passa a heapsort, allora avrai introsort , che è quello che molte implementazioni STL effettivamente utilizzare .

In alternativa, è solo casuale l'selezione di pivot.

Answer 2

Molte implementazioni di Quicksort sono fatte usando un randomizzati versione dell'algoritmo . Ciò significa che un DoS attacco con ingresso appositamente predisposto non è possibile.

Inoltre, anche senza questo, la maggior parte degli insiemi di dati sono semplici troppo piccoli per avere O (nlog) vs O (2 ^ n) la materia. La dimensione del set di tipo dovrebbe essere abbastanza grande per avere un impatto. Anche con qualche milione di elementi, la differenza di tempo sarebbe probabilmente non sarà molto grande.

In generale, qualsiasi applicazione web utilizzando Quicksort è molto più probabilità di avere altri href="http://en.wikipedia.org/wiki/Sql_injection" difetti .

Answer 3

Date un'occhiata a questa domanda (e la risposta marcata), che discute i modi per ridurre caso peggiore di QuickSort:

Perché quicksort meglio di mergesort?

Answer 4

Se le prestazioni sono qualcosa che conta, quindi QuickSort sembrerebbe una scelta sbagliata nella maggior parte dei casi, la preoccupazione di sicurezza o no. C'è qualcosa che ti fa rifuggire da algoritmi come Heapsort o Mergesort?

Answer 5

Credo che questo sia molto una questione di dove si sta usando il quick sort. Utilizzando O (n ^ 2) algoritmi è perfettamente bene quando il lavora con array di 5 elementi, per esempio. D'altra parte, se c'è una possibilità che i dati possono essere significativamente grande, temendo un DoS non è il primo problema si faccia - il primo problema sarà sempre così cattiva performance prima che tu sia di fronte a un problema reale. Dato il gran numero di altri algoritmi disponibili, basta farlo sostituire se è in una posizione critica.

Answer 6

E ', ma solo in casi molto, molto improbabile - che sono tutti facili per un algoritmo adeguatamente progettato per evitare.

Ma se si vuole essere super-sicuro, si consiglia di usare qualcosa come Introsort , che inizia come QuickSort ma passa alla Heap Sort se rileva dalla profondità di ricorsione che l'algoritmo comincia ad andare quadratica.

Modifica che vedo Pavel mi ha battuto a Introsort.

In risposta alla domanda Modificato: non ho testato personalmente ogni singola biblioteca Quicksort, ma mi sento di scommesse sicuro che quasi tutti loro hanno controlli in atto per evitare il caso peggiore