Is there an exploit for this bug for python's sort implementation?
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "Questions asking us to break the security of a specific system for you are off-topic unless they demonstrate an understanding of the concepts involved and clearly identify a specific problem." – schroeder, Xander, Bob Brown, Eric G
That version also contains the bug and was intended to work for arrays with up to 2^64 elements. However, on current machines it is not possible to trigger an out-of-bounds error in the Python version: it allocates 85 elements for runLen, which suffices (following our analysis in the full paper) for arrays with less than 2^49 elements. For comparison, the current most powerful supercomputer http://en.wikipedia.org/wiki/Tianhe-2 has about 2^50 bytes of memory in total.
It is not currently possible to trigger the bug in CPython, since it requires a data set that does not fit in today's machines. Since the bug cannot be triggered, in cannot be exploited.
As the article mentions, some Java implementations of this algorithm use smaller arrays which can overflow with smaller datasets (a few hundred MB in the sample code, if I read it correctly). Since this is a buffer overflow, there is a fair chance that it is exploitable.