18

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?

ks1322
  • 33,961
  • 14
  • 109
  • 164
Dario
  • 48,658
  • 8
  • 97
  • 130
  • 1
    "under certain circumstances" has to mean that this is the worst remaining circumstance where a user can trick you into doing a lot of work. They would have to be sending you a lot of data before an O(n^2) sort is more of a DoS than other typical things that websites do with data that users send them (e.g. saving it). Then (and only then) would I consider a hand-rolled introsort perhaps having a security advantage over a "builtin" quicksort. – Steve Jessop Oct 06 '09 at 18:32

6 Answers6

26

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.

Pavel Minaev
  • 99,783
  • 25
  • 219
  • 289
9

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.

Ben S
  • 68,394
  • 30
  • 171
  • 212
  • 8
    Yes, after coding it in my first-year CS class, but I've never built a website that allowed users to upload a data set of a million elements for me to sort with _any_ algorithm. – Ben S Oct 06 '09 at 18:16
5

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

Why is quicksort better than mergesort?

Community
  • 1
  • 1
gahooa
  • 131,293
  • 12
  • 98
  • 101
1

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?

Adam Robinson
  • 182,639
  • 35
  • 285
  • 343
1

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.

Eran
  • 21,632
  • 6
  • 56
  • 89
1

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.

rtperson
  • 11,632
  • 4
  • 29
  • 36