Re: algorithmic complexity attacks and libc qsort()

[Mindaugas Rasiukevicius <rmind%netbsd.org@localhost>]

Thomas Klausner <tk%giga.or.at@localhost> wrote:
> Analysis of worst cases for libc's qsort() on various operating
> systems, including NetBSD:
> 
> 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.

> Except 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