>> But using non-__builtin__.str objects (such as UserString) would expose the
>> user to an attack?
>
> Not necessarily: only if they use these strings as dictionary keys, and only
> if they do so in contexts where arbitrary user input is consumed. In these
> cases, users need to rewrite their code to replace the keys. Using dictionary
> wrappers (such as UserDict), this is possible using only local changes.

Could the AVL tree approach be extended to apply to dictionaries
containing keys of any single type that supports comparison?  That
approach would autodetect UserString or similar and support it
properly.

I expect that dictionaries with keys of more than one type to be very
rare and highly unlikely when it comes to values generated directly
via user input.

(and on top of all of this I believe we're all settled on having per
interpreter hash randomization _as well_ in 3.3; but this AVL tree
approach is one nice option for a backport to fix the major
vulnerability)

-gps