[Python-Dev] cpython (2.6): - Issue #13703: oCERT-2011-003: add -R command-line option and PYTHONHASHSEED

[Antoine Pitrou]

On Tue, 21 Feb 2012 02:44:32 +0100
barry.warsaw <python-checkins at python.org> wrote:
> +   This is intended to provide protection against a denial-of-service caused by
> +   carefully-chosen inputs that exploit the worst case performance of a dict
> +   insertion, O(n^2) complexity.  See
> +   http://www.ocert.org/advisories/ocert-2011-003.html for details.

The worst case performance of a dict insertion is O(n) (not counting
potential resizes, whose cost is amortized by the overallocation
heuristic). It's dict construction that has O(n**2) worst case
complexity.

> @@ -1232,9 +1233,9 @@
>      flags__doc__,       /* doc */
>      flags_fields,       /* fields */
>  #ifdef RISCOS
> +    17
> +#else
>      16
> -#else
> -    15
>  #endif

Changing the sequence size of sys.flags can break existing code (e.g.
tuple-unpacking).

Regards

Antoine.