Post by Thomas KlausnerAnalysis of worst cases for libc's qsort() on various operating
http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html
I don't think there's much to do here, really, since we know that
qsort has a n^2 worst case :)
The author has a strange concept of an "attack". Of course qsort(3) can
demonstrate O(n^2) behaviour. It is there by definition, because.. you
know, it is quicksort. It delivers what it promises and the "analysis"
is merely an illustration of the already known worst case behaviour.
The C standard does not require qsort(3) to be quicksort and perhaps the
author expects us to provide "the most efficient" general purpose sorting
algorithm. However, the C standard does not define any bounds for the
algorithmic complexity either (it may as well be impemented as bubblesort).
These bounds are doomed to differ amongst libc implementations.
I think that libc should provide more efficient sorting algorithms (what
is "efficient" really depends on the problem, though); we already provide
heapsort(3), mergesort(3) and radixsort(3). However, I do not see much
point in adding some heuristics to come up with somewhat better looking
general purpose sorting algorithm under the function name of "qsort".
In any case, the sensible attack target is the application, not qsort()
itself. Ultimately, it is the responsibility of the programmer to think
about the efficiency requirements (computational vs space complexity),
security implications and choose a sensible sorting algorithm.
Post by Thomas KlausnerExcept if we want to improve it based on FreeBSD's version, that
switched to insertion sort in some cases and improves the best case
this way.
There is a reason why it was removed (also mentioned in the article).
--
Mindaugas