On Wed, Aug 6, 2014 at 9:18 AM, John Cochran <j69coch...@gmail.com> wrote: > So it seems to me that the vulnerability only exits if an attacker supplied > comparison function is permitted. For all other cases, assuming that only > vetted comparison functions are permitted, the selection of a random pivot > would make an attack on qsort using specially tailored input data > improbable.
Whether or not random pivot selection would make it more difficult for a malicious party to generate pre-processed data that will cause very bad performance is not all that relevant IMV, since we don't do that. There are good practical reasons to prefer median of medians pivot selection, which is what we actually do, and which is clearly affected to the extent that pre-processing malicious data that causes (at least) near worst-case performance is possible. It's possible to predict pivot selection. As the paper says, "An adversary can make such a quicksort go quadratic by arranging for the pivot to compare low against almost all items not seen during pivot selection". Random pivot selection will certainly result in more frequent lopsided partitions without any malicious intent. -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
