ho visto una presentazione, l'altro giorno in cui l'altoparlante aveva usato la tecnica descritta in carta di McIlroy A Killer Adversary for Quicksort per generare un input per Arrays.sort per i tipi primitivi che farebbe scattare O (n) comportamento. La sequenza ha causato la scelta di pivot di ridurre sempre la dimensione dell'array di una costante, causando la funzione Java Arrays.sort per causare un overflow dello stack.Perché l'implementazione JDK di quicksort rischia un overflow dello stack?
In base a the source files from the JDK, la funzione di implementazione quicksort di Arrays.sort1 non ha protezioni per impedire lo stack overflow. È sempre possibile che quicksort non impili mai l'overflow facendo in modo che la routine di ordinamento non attivi due chiamate ricorsive, ma invece usi un ciclo while per riutilizzare lo stack frame corrente per il subarray più grande e solo una volta ricorsivamente (nel subarray più piccolo). Ciò causa una riduzione minima delle prestazioni e rende impossibile causare un overflow dello stack per qualsiasi input di dimensioni ragionevoli, poiché la profondità dello stack non supera mai i frame di stack O (log n) su un input di dimensione n. Gli autori potrebbero anche aver utilizzato l'algoritmo introsort, che modifica quicksort per passare a un algoritmo di ordinamento O (n log n) nel caso peggiore quando la profondità di ricorsione rapida supera un limite, per evitare ciò.
C'è qualche motivo per cui gli autori di Arrays.sort non hanno scelto di farlo? Sembra un problema serio che un algoritmo di ordinamento incorporato possa causare un overflow dello stack, in quanto consente di lanciare un attacco DoS contro un tale sistema attivando ripetuti overflow dello stack.
Per sapere con certezza, dobbiamo chiedere a Vladimir Yaroslavskiy, Jon Bentley o Josh Bloch. Tuttavia in java 1.7 il metodo sort1 viene rimosso e sostituito con un DualPivotQuicksort, ma non sono abbastanza bravo in questa roba per capire se questo è migliore del vecchio approccio. – mszalbach