Objects/setobject.c contains unsafe code

[abacabadabacaba]

BPO	8420
Nosy	@rhettinger, @merwok
Files	lookkey.diff: lookkey.diff repr.diff: patch for set_repr fix-set-crashers-2.7.diff

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/merwok'
closed_at = <Date 2011-03-23.04:10:56.486>
created_at = <Date 2010-04-16.15:43:34.047>
labels = ['interpreter-core', 'type-crash']
title = 'Objects/setobject.c contains unsafe code'
updated_at = <Date 2011-03-23.04:10:56.485>
user = 'https://bugs.python.org/abacabadabacaba'

bugs.python.org fields:

activity = <Date 2011-03-23.04:10:56.485>
actor = 'eric.araujo'
assignee = 'eric.araujo'
closed = True
closed_date = <Date 2011-03-23.04:10:56.486>
closer = 'eric.araujo'
components = ['Interpreter Core']
creation = <Date 2010-04-16.15:43:34.047>
creator = 'abacabadabacaba'
dependencies = []
files = ['16969', '16981', '21341']
hgrepos = []
issue_num = 8420
keywords = ['patch']
message_count = 24.0
messages = ['103333', '103424', '103473', '103486', '103505', '103510', '103516', '103524', '103541', '103543', '115430', '115667', '131610', '131757', '131783', '131784', '131789', '131801', '131804', '131821', '131832', '131835', '131849', '131852']
nosy_count = 4.0
nosy_names = ['rhettinger', 'eric.araujo', 'abacabadabacaba', 'python-dev']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue8420'
versions = ['Python 3.1', 'Python 2.7', 'Python 3.2']

[abacabadabacaba]

I've noticed that set_lookkey (in Objects/setobject.c) does some unsafe things:
Objects/setobject.c:

if (entry->hash == hash) {
startkey = entry->key;
Py_INCREF(startkey);
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
At this point, object pointed to by startkey could be deallocated, and then new object may be allocated at the same address.
if (cmp < 0)
return NULL;
if (table == so->table && entry->key == startkey) {
At this point, the table may be reallocated at the same address but with different (possibly smaller) size, so entry->key may be in deallocated memory. Also, entry->key may be equal to startkey but still point to an object other than one key was compared with.
if (cmp > 0)
return entry;
}
else {
/* The compare did major nasty stuff to the
* set: start over.
*/
return set_lookkey(so, key, hash);
This can lead to infinite recursion.
}

[abacabadabacaba]

I've found more unsafe code in Objects/setobject.c.
This code makes Python 3.1.2 segfault by using a bug in function set_merge:

class bad:
	def __eq__(self, other):
		if be_bad:
			set2.clear()
			raise Exception
		return self is other
	def __hash__(self):
		return 0
be_bad = False
set1 = {bad()}
set2 = {bad() for i in range(2000)}
be_bad = True
set1.update(set2)

Function set_symmetric_difference_update has a similar bug.

Another bug in set_symmetric_difference_update:

class bad:
	def __init__(self):
		print("Creating", id(self))
	def __del__(self):
		print("Deleting", id(self))
	def __eq__(self, other):
		print("Comparing", id(self), "and", id(other))
		if be_bad:
			dict2.clear()
		return self is other
	def __hash__(self):
		return 0
be_bad = False
set1 = {bad()}
dict2 = {bad(): None}
be_bad = True
set1.symmetric_difference_update(dict2)

[rhettinger]

Attaching a patch for set_lookkey() that does a DECREF only when the refcnt > 1 so that the DECREF won't trigger any state changes.

The merge crasher still needs a patch.

[abacabadabacaba]

This patch still assumes that if so->table didn't change then the table wasn't reallocated (see http://en.wikipedia.org/wiki/ABA_problem). One solution is to check that so->mask didn't change as well. Also, checking that refcnt > 1 is redundant because if entry->key == startkey then there are at least two references: one from entry->key and another from startkey.

These functions have a bug that may cause them to refer to deallocated memory when both arguments are sets: set_intersection, set_isdisjoint, set_difference_update_internal, set_difference, set_symmetric_difference_update, set_issubset.
These functions may also do the same if the first argument is a set and the second argument is a dict: set_difference, set_symmetric_difference_update.

Bugs in set_repr:

keys = PySequence_List((PyObject *)so);
if (keys == NULL)
goto done;

listrepr = PyObject_Repr(keys);
Py_DECREF(keys);
List pointed to by keys is already deallocated at this point.
if (listrepr == NULL) {
Py_DECREF(keys);
But this code tries to DECREF it.
goto done;
}
newsize = PyUnicode_GET_SIZE(listrepr);
result = PyUnicode_FromUnicode(NULL, newsize);
if (result) {
u = PyUnicode_AS_UNICODE(result);
*u++ = '{';
/* Omit the brackets from the listrepr */
Py_UNICODE_COPY(u, PyUnicode_AS_UNICODE(listrepr)+1,
PyUnicode_GET_SIZE(listrepr)-2);
u += newsize-2;
*u++ = '}';
}
Py_DECREF(listrepr);
if (Py_TYPE(so) != &PySet_Type) {
result may be NULL here.
PyObject *tmp = PyUnicode_FromFormat("%s(%U)",
Py_TYPE(so)->tp_name,
result);
I think PyUnicode_FromFormat won't like it.
Py_DECREF(result);
result = tmp;
}

[rhettinger]

One solution is to check that so->mask didn't
change as well.

I saw that and agree it would make a tighter check, but haven't convinced myself that it is necessary.

Also, checking that refcnt > 1 is redundant
because if entry->key == startkey then there
are at least two references: one from entry->key
and another from startkey.

It is a meaningful check. We have our own INCREF
and one for the key being in the table. If the
count is 1, then it means that the comparison
check deleted the key from the table or replaced
its value (see bpo-1517).

[rhettinger]

Bugs in set_repr:
> keys = PySequence_List((PyObject *)so);
> if (keys == NULL)
> goto done;
>
> listrepr = PyObject_Repr(keys);
> Py_DECREF(keys);
List pointed to by keys is already deallocated at this point.
> if (listrepr == NULL) {
> Py_DECREF(keys);
>But this code tries to DECREF it.
> goto done;
> }

I don't follow why you think keys is already deallocated.
When assigned by PySequence_List() without a NULL return, the refcnt is one. The call to PyObject_Repr(keys) does not change the refcnt of keys,
so the Py_DECREF(keys) is correct.

[abacabadabacaba]

> One solution is to check that so->mask didn't
> change as well.

I saw that and agree it would make a tighter check, but haven't convinced myself that it is necessary.

Without this check, it is possible that the comparison shrinks the table, so entry becomes out of bounds. However, if both so->table and so->mask didn't change then entry is still a pointer to one of table elements so it can be used safely.

> Also, checking that refcnt > 1 is redundant
> because if entry->key == startkey then there
> are at least two references: one from entry->key
> and another from startkey.

It is a meaningful check. We have our own INCREF
and one for the key being in the table. If the
count is 1, then it means that the comparison
check deleted the key from the table or replaced
its value (see bpo-1517).

If the comparison deleted or changed the key then the check entry->key == startkey would fail so refcnt check won't be reached. Checking refcounts is also bad because someone else may have references to the key.

I don't follow why you think keys is already deallocated.
When assigned by PySequence_List() without a NULL return, the refcnt is one. The call to PyObject_Repr(keys) does not change the refcnt of keys,
so the Py_DECREF(keys) is correct.
Look at the code again. If listrepr happens to be NULL, you do Py_DECREF(keys) twice (this bug is only present in py3k branch).

[rhettinger]

Fixed set_repr() issue in r80197 and r80196. Looks like someone futzed the unicode updates for 3.x.

[abacabadabacaba]

This code crashes python by using another bug in set_repr. This only affects py3k. This code relies on out-of-memory condition, so run it like:
$ (ulimit -v 65536 && python3 test.py)
Otherwise, it will eat all your free memory before crashing.

val = "a" * 10000
class big:
	def __repr__(self):
		return val
i = 16
while True:
	repr(frozenset(big() for j in range(i)))
	i = (i * 5) >> 2

[rhettinger]

Patch please.

[rhettinger]

Fixed in r84447