Mailing List Archive: [issue2778] set_swap_bodies is unsafe

[issue2778] set_swap_bodies is unsafe

May 6, 2008, 7:19 PM

Post #1 of 17 (1183 views)

New submission from Adam Olsen <rhamph@gmail.com>:

set_swap_bodies() is used to cheaply create a frozenset from a set,
which is then used for lookups within a set. It does this by creating a
temporary empty frozenset, swapping its contents with the original set,
doing the lookup using the frozenset, then swapping the contents back
and releasing the temporary frozenset.

Unfortunately, the lookup can invoke arbitrary code, which may examine
the original set and find it empty (until the lookup completes). The
lookup may also save a reference to the temporary frozenset, which
mutates to being empty after the lookup completes.

The purpose seems to be allowing "someset in someotherset" to
automatically convert someset to a frozenset. A brief search didn't
reveal a rationale for this, and in fact PEP 218's history section
claims the opposite: "Auto-conversion between mutable and immutable sets
was dropped." Perhaps this is a forgotten vestige of that?

set_intersection_update uses set_swap_bodies for a different purpose and
it may be safe. It depends on whether subclasses of set may retain a
reference to the tmp set somehow.

----------
files: brokensetswap.py
messages: 66349
nosy: Rhamphoryncus
severity: normal
status: open
title: set_swap_bodies is unsafe
type: behavior
Added file: http://bugs.python.org/file10204/brokensetswap.py

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 6, 2008, 7:36 PM

Post #2 of 17 (1179 views)

Changes by Benjamin Peterson <musiccomposition@gmail.com>:

----------
assignee: -> rhettinger
nosy: +rhettinger

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 7, 2008, 5:07 AM

Post #3 of 17 (1172 views)

Raymond Hettinger <rhettinger@users.sourceforge.net> added the comment:

set_swap_bodies() is fine as it involves pure C with no possible
callbacks. The issue is in its use in the __contains__() check. I'll
take a look at it and see what if anything needs to be changed.

Am lowering the priority because you really have to be trying to create
this behavior.

----------
priority: -> low

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 7, 2008, 1:11 PM

Post #4 of 17 (1162 views)

Adam Olsen <rhamph@gmail.com> added the comment:

The intended use is unsafe. contains, remove, and discard all use it
for a lookup, which can't be fixed.

Upon further inspection, intersection_update is fine. Only a temporary
set (not frozenset!) is given junk, which I don't see as a problem.

If someone can confirm that contains/remove/discard's usage is an
artifact I'll submit a patch that removes it.

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 7, 2008, 8:10 PM

Post #5 of 17 (1155 views)

Adam Olsen <rhamph@gmail.com> added the comment:

I decided not to wait. Here's a patch.

Several of set's unit tests covered the auto-conversion, so I've
modified them.

----------
keywords: +patch
Added file: http://bugs.python.org/file10217/python-setswap.diff

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 7, 2008, 9:06 PM

Post #6 of 17 (1157 views)

Raymond Hettinger <rhettinger@users.sourceforge.net> added the comment:

Rejecting this patch which simply disables a feature that some users
consider to be important.

I will look at it further. Right now, I'm inclined to simply document
that the three temporary autoconversions deny meaningful
contemporaneous access to a set used as a key.

The set_swap_bodies() function itself is fine -- it behaves just like
an atomic version of the pure python sequence: t=set(a); a.clear();
a.update(b); b.clear(); b.update(t); del t.

The issue is simply that the swap/search/swap dance allows the
possibility that a determined user could graft onto the search step and
access but not modify the temporary swapped-in frozenset. It doesn't
crash; it simply produces an undefined result. I'm not losing sleep
over this scenario.

I'm am entertaining an alternative where contains/discard/remove would
duplicate instead of swap the set bodies; however, that approach may do
more harm than good.

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 7, 2008, 9:29 PM

Post #7 of 17 (1167 views)

Adam Olsen <rhamph@gmail.com> added the comment:

PEP 218 explicitly dropped auto-conversion as a feature. Why should
this be an exception?

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 7, 2008, 9:52 PM

Post #8 of 17 (1158 views)

Raymond Hettinger <rhettinger@users.sourceforge.net> added the comment:

If needed, I'll update the PEP to be more clear. The sets.py module
had two protocols: __as_immutable__() and __as_temporarily_immutable__
(). The first protocol was the one that was dropped -- it triggered
with something like "s1.add(s2)" and it automatically created a
frozenset copy of s2. The second protocol is used in
contains/remove/discard. Alex Martelli successfully lobbied for its
retention.

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 8, 2008, 10:21 AM

Post #9 of 17 (1155 views)

Raymond Hettinger <rhettinger@users.sourceforge.net> added the comment:

Added documentation in r62873. Leaving the code as-is.

----------
resolution: -> fixed
status: open -> closed

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 8, 2008, 10:29 AM

Post #10 of 17 (1156 views)

Adam Olsen <rhamph@gmail.com> added the comment:

I've been unable to find any discussion on this feature. If anything, I
think when PEP 218 was discussed and accepted (and PEP 351 rejected),
the assumption was it didn't exist. Adding it now should be regarded as
a new feature and discussed on python-dev.

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 8, 2008, 10:31 AM

Post #11 of 17 (1156 views)

Adam Olsen <rhamph@gmail.com> added the comment:

Nevermind that the current implementation *is* broken, even if you
consider fixing it to be a low priority. Closing the report with a doc
tweak isn't right.

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 8, 2008, 10:38 AM

Post #12 of 17 (1154 views)

Raymond Hettinger <rhettinger@users.sourceforge.net> added the comment:

Sorry, you don't like the search with autopromotion feature. It has
been around since sets were first coded in C. It is a natural
extension/consequence of the idea that frozenset('abc')==set('abc').

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 8, 2008, 10:43 AM

Post #13 of 17 (1150 views)

Adam Olsen <rhamph@gmail.com> added the comment:

So why doesn't set() in {} work? Why was PEP 351 rejected when it would
do this properly?

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 12, 2008, 11:31 PM

Post #14 of 17 (1118 views)

Adam Olsen <rhamph@gmail.com> added the comment:

Here's another approach to avoiding set_swap_bodies. The existing
semantics are retained. Rather than creating a temporary frozenset and
swapping the contents, I check for a set and call the internal hash
function directly (bypassing PyObject_Hash).

I even retain the current semantics of PySet_Discard and PySet_Contains,
which do NOT do the implicit conversion (and have unit tests to verify
that!)

I do have some concern that calling PySet_Check on every call may be too
slow. It may be better to only call it on failure (which is
more-or-less what the old code did.)

set_swap_bodies has only one remaining caller, and their use case could
probably be significantly simplified.

Added file: http://bugs.python.org/file10315/python-setswap-2.diff

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 14, 2008, 10:08 AM

Post #15 of 17 (1117 views)

Adam Olsen <rhamph@gmail.com> added the comment:

Revised again. sets are only hashed after PyObject_Hash raises a TypeError.

This also fixes a regression in test_subclass_with_custom_hash. Oddly,
it doesn't show up in trunk, but does when my previous patch is applied
to py3k.

Added file: http://bugs.python.org/file10321/python-setswap-3.diff

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 14, 2008, 1:59 PM

Post #16 of 17 (1115 views)

Raymond Hettinger <rhettinger@users.sourceforge.net> added the comment:

By replacing temporary immutability with temporary hashability, does
this approach create the possibility that someone could mutate the key-
set during a search? Is it possible to get the __eq__ check out-of-
sync with the __hash__ value?

Also, after a quick look at the patch, I'm not too keen on any
modifications to set_swap_bodies() nor with changing the signature of
set_contains_key().

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue2778] set_swap_bodies is unsafe [ In reply to ]

May 14, 2008, 3:11 PM

Post #17 of 17 (1097 views)

Adam Olsen <rhamph@gmail.com> added the comment:

There is no temporary hashability. The hash value is calculated, but
never stored in the set's hash field, so it will never become out of
sync. Modification while __hash__ or __eq__ is running is possible, but
for __eq__ that applies to any mutable type.

set_contains_key only has two callers, one for each value of the
treat_set_key_as_frozen argument, so I could inline it if you'd prefer that?

set_swap_bodies has only one remaining caller, which uses a normal set,
not a frozenset. Using set_swap_bodies on a frozenset would be visible
except in a few special circumstances (ie it only contains builtin
types), so a sanity check against that seems appropriate. The old code
reset ->hash to -1 in case one of the arguments was a frozenset -
impossible now, so I sanity check that it's always -1.

__________________________________
Tracker <report@bugs.python.org>
<http://bugs.python.org/issue2778>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com