On 11/17/13 2:20 AM, Ivan Kazmenko wrote:
On Sunday, 17 November 2013 at 03:58:58 UTC, Andrei Alexandrescu wrote:
On 11/16/13 5:07 PM, Ivan Kazmenko wrote:
The above is just my retelling of a great short article "A Killer
Adversary for Quicksort" by M. D. McIlroy here:
http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
Nice story, but the setup is a tad tenuous (albeit indeed
theoretically interesting). For starters, if the attacker has a hook
into the comparison function, they could trivially do a lot worse...
Actually, I was thinking about a two phase attack, and it is not at all
unlikely.
0. Say, the Sorter presents a library quicksort solution. It may be
closed source, but can take comparison function as argument.
1. On the preparation phase, the Attacker uses the tricky comparison
function described previously. What's important is that, besides
observing Theta(n^2) behavior once, he now gets a real array a[] such
that this behavior can be reproduced.
2. On the attack phase, the Attacker does not need access to the
comparison function. He just feeds the array obtained on the previous
step as plain data.
Ivan Kazmenko.
That won't do with randomized pivot selection.
Andrei
