Is Quicksort a potential security risk?

Question

I just wondered whether (with some serious paranoia and under certain circumstances) the use of the QuickSort algorithm can be seen as a security risk in an application.

Both its basic implementation and improved versions like 3-median-quicksort have the peculiarity of behaving deviant for certain input data, which means that their runtime can increase extremely in these cases (having O(n^2) complexity) not to mention the possibility of a stackoverflow.

Hence I would see potential to do harm by providing pre-sorted data to a programm that causes the algorithm to behave like this, which could have unpredictable consequences for e.g. a multi-client web application.

Is this strange case worth any security consideration (and would therefore force us to use Intro- or Mergesort instead)?

Edit: I know that there are ways to prevent Quicksort's worst cases, but what about language integrated sorts (like the 3-Median of .NET). Would they be taboo?

Answer 1

Yes, it is a security risk - DoS, to be specific - which is trivially mitigated by adding a check for recursion depth in your quicksort, and switching to something else instead if a certain depth is reached. If you switch to heapsort, then you'll get introsort, which is what many STL implementations actually use.

Alternatively, you just randomize the selection of pivot element.

Answer 2

Take a look at this question (and marked answer) which discusses ways of reducing QuickSort's worst case:

http://stackoverflow.com/questions/70402/why-is-quicksort-better-than-mergesort

Answer 3

Many implementations of quicksort are done using a randomized version of the algorithm. This means a DoS attack with specially-crafted input is not possible.

Also, even without this, most data sets are simple too small to have O(nlog) vs O(n^2) matter. The size of the set to sort would have to be quite large to have an impact. Even with a few million elements, the time difference would likely not be very large.

Overall, any given web-application using quicksort is much more likely to have other security flaws.

Answer 4

If performance is something that matters, then QuickSort would seem a poor choice in most circumstances, security concern or not. Is there something that causes you to shy away from algorithms like Heapsort or Mergesort?

Answer 5

I think this is very much a question of where you're actually using the quick sort. Using O(n^2) algorithms is perfectly fine when your working with arrays of 5 items, for instance. On the other hand, when there's a chance the data can be significantly large, fearing a DoS is not the first problem you'll face - the first problem will be getting bad performance way before you're facing a real problem. Given the large number of other algorithms available, just have it replaced if it's in a critical location.

Answer 6

It is, but only in very, very unlikely cases -- all of which are easy for a properly-designed algorithm to avoid.

But if you want to be super-safe, you may want to use something like Introsort, which starts out as QuickSort but switches over to Heap Sort if it detects from the recursion depth that the algorithm is starting to go quadratic.

Edit: I see Pavel beat me to Introsort.

In Response to Edited Question: I haven't personally tested every single Quicksort library, but I feel safe betting that pretty much all of them have checks in place to avoid the worst case.