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.
