Re: algorithmic complexity attacks and libc qsort()

[Patrick Welche <prlw1%cam.ac.uk@localhost>]

On Thu, Jun 12, 2014 at 01:14:59PM +0200, Thomas Klausner 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 :)
> 
> 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.

I note that NetBSD's "killer input" looks rather unlikely.

P