4 ms·
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
by 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?"