4 ms·

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.

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.