On 01/18/2016 09:21 PM, Ivan Kazmenko wrote:
On Tuesday, 19 January 2016 at 00:11:40 UTC, Andrei Alexandrescu wrote:
4. sort was and is attackable before all of these changes
No, sort utilizes Introsort (Quicksort but switch to Heapsort if recurse
too deep): see
https://github.com/D-Programming-Language/phobos/blob/2.067/std/algorithm/sorting.d#L1048-L1053.
This improvement happened a year or two ago, when algorithm.d was not
even separated into sub-modules.
My adversary program (change "topN (a, MAX_N / 2)" to "sort (a)") admits
that by not being able to slow the sort down. But, if I comment out
line 1053 to disable the switching, things go quadratic as expected.
L1053: depth = depth >= depth.max / 2 ? (depth / 3) * 2 : (depth * 2)
/ 3;
The same remedy can help for topN: if we called partition more than log
(length) in base (3/2) times, switch to the heap implementation of topN
regardless of whether n is close to the edge.
Do you think sort and topN would be attackable if they used a
per-process-seeded RNG as per Xinok's idea? -- Andrei
