4 ms·

There are still inputs that will make it go quadratic, that just obscures it slightly. A proper fix is to fall back on a different sort if it looks like quicks

by Freaky 12y ago

There are still inputs that will make it go quadratic, that just obscures it slightly. A proper fix is to fall back on a different sort if it looks like quicksort is doing that: https://en.wikipedia.org/wiki/Introsort https://en.wikipedia.org/wiki/Introsort

thaumasiotes 12y ago
> There are still inputs that will make it go quadratic Can you elaborate on this? To force quicksort into a quadratic running time, you need to ensure that each pivot splits off a bounded number of elements (e.g. no more than three, or no more than twenty million) from the rest of the list. If the pivot is being chosen at random, then it looks to me like the guarantee you'd need to make is "every single element of this list [because any of them might be chosen] is larger, and smaller, than no more than k other elements of the list". But as the size of the list grows, that condition forces it to be mostly composed of the same element repeated over and over again, which is really easy to sort, and in particular is really easy for quicksort to handle.
- nightcracker 12y ago
  See my bug report on libc++: http://llvm.org/bugs/show_bug.cgi?id=20837 http://llvm.org/bugs/show_bug.cgi?id=20837 .
  - thaumasiotes 12y ago
    But that adversary works by causing the sorting agent to run arbitrary, adversary-supplied code every time it makes a comparison. It has to do that because it invents the values in its list on the fly when it detects them being accessed by the sort (also, in order to detect them being accessed by the sort). That's not really the same thing. I mean, if you want to tie up a process, and you can already make it run arbitrary code that you supply, just give it something like while(1); . If this adversary were forced to realize all the values it fed to the sorter before the sorter did any work, or if it were unable to supply its own code to the sorter, random pivot selection would be a defense. edit: I feel like pointing out that a quicksort implementation could defeat this adversary, without hurting its O(n log n) running time, by just comparing the first element of the sublist it was working with to every other element in the sublist -- and throwing away the results -- and then proceeding as normal. This is O(n) comparisons, which violates the vulnerability criterion of making only O(1) comparisons per call, but doesn't affect the big-O running time at all. What it does do, with an eye to this particular adversary, is realize all the values before doing any sorting work. It still doesn't fix the actual vulnerability the paper identifies, which is that you're running adversary-supplied code. I'm growing to feel like your bug report was frivolous.
    - nightcracker 12y ago
      What you fail to realize is that this attack is simply an academic proof that shows the libc++ implementation is broken and can have quadratic performance. This is a bug, because the C++ standard mandates a worst case of O(n log n). What you also don't seem to realize is that this attack merely uses a comparison function to find the worst case. Once the worst case is found you can feed this input to any program using libc++'s std::sort, without comparison function, and trigger the worst case. So no, this is not frivolous at all.
      - tveita 12y ago
        > This is a bug, because the C++ standard mandates a worst case of O(n log n). Specifically, this is a requirement in C++11. Earlier C++ standards only require it to be average-case O(n log n).
      - thaumasiotes 12y ago
        > What you also don't seem to realize is that this attack merely uses a comparison function to find the worst case. Once the worst case is found you can feed this input to any program using libc++'s std::sort, without comparison function, and trigger the worst case. This is true iff pivots are selected deterministically. In which case, why did you post it as a response to "how can an adversary force quadratic behavior when pivots are chosen randomly?"
  - scythe 12y ago
    libc++ doesn't use randomized quicksort so that bug is irrelevant. It is an attack on a clever pivot selection method, but the exploit derives from the fact that the pivot isn't actually random, but deterministically pseudorandom. A truly random quicksort isn't vulnerable (since the pivots will be chosen in a different order every time). The real problem with random quicksort is that randomness is really, really hard, and good RNGs are slow. Also, timsort is adaptive, while quicksort is not.
  - deleted 12y ago
    [deleted]
  - netheril96 12y ago
    So, another algorithmic complexity bug in libc++. I found one about `std::make_heap` before when testing one of my codes before (http://llvm.org/bugs/show_bug.cgi?id=20161 http://llvm.org/bugs/show_bug.cgi?id=20161). So much about the bug always being in your own code nowadays.
- deleted 12y ago
  [deleted]
- beagle3 12y ago
  Depends on how you interact with the quicksort, really. If you have control of the comparison routine, there's Doug McIlroy's classic "quicksort killer"[0]. If you have information about the state of the random number generator used to pick the pivot, then you can do the same without having to actually interact through the comparison routine. Many libraries use an LCG[1] with 32 to 64 bit state, which is trivial to reconstruct through a small sample of its output not much longer than the internal state. I don't know about you, but requiring my sort() routine to have access to a cryptographically secure random number generator doesn't seem right; I much prefer any algorithm (e.g. HeapSort, Mergesort or TimSort) that can guarantee n\*log(n) behavior with deterministic (and especially, no secure random generator requirement!) behavior. [0] http://www.cs.dartmouth.edu/~doug/mdmspe.pdf http://www.cs.dartmouth.edu/~doug/mdmspe.pdf [1] http://en.wikipedia.org/wiki/Linear_congruential_generator http://en.wikipedia.org/wiki/Linear_congruential_generator
  - nightcracker 12y ago
    You might be interested in my new sorting algorithm, Pattern-defeating Quicksort (pdqsort): https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort It's fully deterministic, as fast as Quicksort in the average case, O(n) in the best case (all equal, but it scales smoothly as the number of unique elements decreases), is optimized for common inputs like ascending/descending (both O(n)) and uses a novel idea of guaranteeing O(n log n) worst case, that guarantees the worst case is no slower than three times the average case, assuming heapsort is twice as slow as Quicksort. I'm still tweaking the final details and working on the paper, so it's not ready for a full release yet, but a sneak peek here and there is nice :) This is a benchmark comparing pdqsort against introsort (std::sort), heap sort and timsort: http://i.imgur.com/TSvXnG5.png http://i.imgur.com/TSvXnG5.png .
    - beagle3 12y ago
      Which timsort implementation did you compare to? (your profile.cpp on github doesn't include it). Heapsort implementation vary widely in their cache coherence. The vast majority are extremely simple but result in essentially complete incoherence. I was once able to speed a heapsort about 2x by rearranging the scan order into a cache-oblivious one (Mostly the heap building part; I'm not aware of a way to make the extraction part cache-friendy). Heapsorts, quicksorts and bubble sorts have the ability to sort just the "top-n" and stop there (unlike mergesort), which is often useful, and a significat speed up (goes from nlog(n) to n+mlog(n) to get top m, or from n^2 to n times m for bubble sort) - I wish library routines actually provided that as part of a standard interface. Perhaps you could be the torchbearer in your publication? Personally, I think just about every standard library except APL/J/K got sorting wrong. The primary sort operation should be "compute stable ordering permutation", with "sort this array" (basically only available operation in most libraries) being at most a shortcut when you don't care about the permutation.

by Freaky 12y ago

thaumasiotes 12y ago

> There are still inputs that will make it go quadratic Can you elaborate on this? To force quicksort into a quadratic running time, you need to ensure that each pivot splits off a bounded number of elements (e.g. no more than three, or no more than twenty million) from the rest of the list. If the pivot is being chosen at random, then it looks to me like the guarantee you'd need to make is "every single element of this list [because any of them might be chosen] is larger, and smaller, than no more than k other elements of the list". But as the size of the list grows, that condition forces it to be mostly composed of the same element repeated over and over again, which is really easy to sort, and in particular is really easy for quicksort to handle.

nightcracker 12y ago
See my bug report on libc++: http://llvm.org/bugs/show_bug.cgi?id=20837 http://llvm.org/bugs/show_bug.cgi?id=20837 .
- thaumasiotes 12y ago
  But that adversary works by causing the sorting agent to run arbitrary, adversary-supplied code every time it makes a comparison. It has to do that because it invents the values in its list on the fly when it detects them being accessed by the sort (also, in order to detect them being accessed by the sort). That's not really the same thing. I mean, if you want to tie up a process, and you can already make it run arbitrary code that you supply, just give it something like while(1); . If this adversary were forced to realize all the values it fed to the sorter before the sorter did any work, or if it were unable to supply its own code to the sorter, random pivot selection would be a defense. edit: I feel like pointing out that a quicksort implementation could defeat this adversary, without hurting its O(n log n) running time, by just comparing the first element of the sublist it was working with to every other element in the sublist -- and throwing away the results -- and then proceeding as normal. This is O(n) comparisons, which violates the vulnerability criterion of making only O(1) comparisons per call, but doesn't affect the big-O running time at all. What it does do, with an eye to this particular adversary, is realize all the values before doing any sorting work. It still doesn't fix the actual vulnerability the paper identifies, which is that you're running adversary-supplied code. I'm growing to feel like your bug report was frivolous.
  - nightcracker 12y ago
    What you fail to realize is that this attack is simply an academic proof that shows the libc++ implementation is broken and can have quadratic performance. This is a bug, because the C++ standard mandates a worst case of O(n log n). What you also don't seem to realize is that this attack merely uses a comparison function to find the worst case. Once the worst case is found you can feed this input to any program using libc++'s std::sort, without comparison function, and trigger the worst case. So no, this is not frivolous at all.
    - tveita 12y ago
      > This is a bug, because the C++ standard mandates a worst case of O(n log n). Specifically, this is a requirement in C++11. Earlier C++ standards only require it to be average-case O(n log n).
    - thaumasiotes 12y ago
      > What you also don't seem to realize is that this attack merely uses a comparison function to find the worst case. Once the worst case is found you can feed this input to any program using libc++'s std::sort, without comparison function, and trigger the worst case. This is true iff pivots are selected deterministically. In which case, why did you post it as a response to "how can an adversary force quadratic behavior when pivots are chosen randomly?"
- scythe 12y ago
  libc++ doesn't use randomized quicksort so that bug is irrelevant. It is an attack on a clever pivot selection method, but the exploit derives from the fact that the pivot isn't actually random, but deterministically pseudorandom. A truly random quicksort isn't vulnerable (since the pivots will be chosen in a different order every time). The real problem with random quicksort is that randomness is really, really hard, and good RNGs are slow. Also, timsort is adaptive, while quicksort is not.
- deleted 12y ago
  [deleted]
- netheril96 12y ago
  So, another algorithmic complexity bug in libc++. I found one about `std::make_heap` before when testing one of my codes before (http://llvm.org/bugs/show_bug.cgi?id=20161 http://llvm.org/bugs/show_bug.cgi?id=20161). So much about the bug always being in your own code nowadays.
deleted 12y ago
[deleted]
beagle3 12y ago
Depends on how you interact with the quicksort, really. If you have control of the comparison routine, there's Doug McIlroy's classic "quicksort killer"[0]. If you have information about the state of the random number generator used to pick the pivot, then you can do the same without having to actually interact through the comparison routine. Many libraries use an LCG[1] with 32 to 64 bit state, which is trivial to reconstruct through a small sample of its output not much longer than the internal state. I don't know about you, but requiring my sort() routine to have access to a cryptographically secure random number generator doesn't seem right; I much prefer any algorithm (e.g. HeapSort, Mergesort or TimSort) that can guarantee n\*log(n) behavior with deterministic (and especially, no secure random generator requirement!) behavior. [0] http://www.cs.dartmouth.edu/~doug/mdmspe.pdf http://www.cs.dartmouth.edu/~doug/mdmspe.pdf [1] http://en.wikipedia.org/wiki/Linear_congruential_generator http://en.wikipedia.org/wiki/Linear_congruential_generator
- nightcracker 12y ago
  You might be interested in my new sorting algorithm, Pattern-defeating Quicksort (pdqsort): https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort It's fully deterministic, as fast as Quicksort in the average case, O(n) in the best case (all equal, but it scales smoothly as the number of unique elements decreases), is optimized for common inputs like ascending/descending (both O(n)) and uses a novel idea of guaranteeing O(n log n) worst case, that guarantees the worst case is no slower than three times the average case, assuming heapsort is twice as slow as Quicksort. I'm still tweaking the final details and working on the paper, so it's not ready for a full release yet, but a sneak peek here and there is nice :) This is a benchmark comparing pdqsort against introsort (std::sort), heap sort and timsort: http://i.imgur.com/TSvXnG5.png http://i.imgur.com/TSvXnG5.png .
  - beagle3 12y ago
    Which timsort implementation did you compare to? (your profile.cpp on github doesn't include it). Heapsort implementation vary widely in their cache coherence. The vast majority are extremely simple but result in essentially complete incoherence. I was once able to speed a heapsort about 2x by rearranging the scan order into a cache-oblivious one (Mostly the heap building part; I'm not aware of a way to make the extraction part cache-friendy). Heapsorts, quicksorts and bubble sorts have the ability to sort just the "top-n" and stop there (unlike mergesort), which is often useful, and a significat speed up (goes from nlog(n) to n+mlog(n) to get top m, or from n^2 to n times m for bubble sort) - I wish library routines actually provided that as part of a standard interface. Perhaps you could be the torchbearer in your publication? Personally, I think just about every standard library except APL/J/K got sorting wrong. The primary sort operation should be "compute stable ordering permutation", with "sort this array" (basically only available operation in most libraries) being at most a shortcut when you don't care about the permutation.