[Python-bugs-list] [ python-Bugs-793826 ] using itertools.izip to mutate tuples

Sat Aug 30 08:06:25 EDT 2003

Bugs item #793826, was opened at 2003-08-23 17:24
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=793826&group_id=5470

Category: Python Interpreter Core
Group: Python 2.3
Status: Closed
>Resolution: Fixed
Priority: 5
Submitted By: Armin Rigo (arigo)
Assigned to: Raymond Hettinger (rhettinger)
Summary: using itertools.izip to mutate tuples

Initial Comment:
Not sure how crucial this exactly is, but the
itertools.izip() can be abused to create a tuple that
can be mutated once. I couldn't find a way to crash
anything, however, but I wouldn't leave such a
possibility open in the Python interpreter nevertheless.

. from itertools import imap, izip
.
. def mutatingtuple(tuple1, f, tuple2):
.     # this builds a tuple t which is a copy of tuple1,
.     # then calls f(t), then mutates t to be equal to
tuple2
.     # (needs len(tuple1) == len(tuple2)).
.     def g(value, first=[1]):
.         if first:
.             del first[:]
.             f(z.next())
.         return value
.     items = list(tuple2)
.     items[1:1] = list(tuple1)
.     gen = imap(g, items)
.     z = izip(*[gen]*len(tuple1))
.     z.next()
.
. def f(t):
.     global T
.     T = t
.     print T
.
. mutatingtuple((1,2,3), f, (4,5,6)) # print T -> (1, 2, 3)
. print T                            # print T -> (4, 5, 6)

----------------------------------------------------------------------

>Comment By: Armin Rigo (arigo)
Date: 2003-08-30 14:06

Message:
Logged In: YES
user_id=4771

Moving the Py_INCREF(result) at the beginning seems to fix
all issues at once and even probably makes the "olditem=...
Py_DECREF(olditem)" dance unnecessary, but it looks fine as
it is now.

I'd be interested in knowing if you actually measured how
much of a performance gain it is to cache the resulting
tuple, given that PyTuple_New() is already quite optimized.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-08-30 00:17

Message:
Logged In: YES
user_id=80475

Applied code to replace the tuple entry before decreffing it.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-08-30 00:01

Message:
Logged In: YES
user_id=80475

Does a further change need to be made or is it sound as it
stands now?

-                       Py_DECREF(PyTuple_GET_ITEM(result, i));
+                      olditem = PyTuple_GET_ITEM(result, i);
PyTuple_SET_ITEM(result, i, item);
+                       Py_DECREF(olditem);

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-08-29 23:14

Message:
Logged In: YES
user_id=80475

Fixed.

See:
Modules/itertoolsmodule.c 1.20 and 1.18.6.1
Lib/test/test_itertools.py 1.18 and 1.15.6.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-08-29 20:22

Message:
Logged In: YES
user_id=80475

Please do submit a patch (attached to this report) and I'll
take a look at it.

In your judgement, is this a problem that would negatively
impact real code or does it only involve deliberate contortions
and mischief?

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2003-08-28 13:13

Message:
Logged In: YES
user_id=4771

Ah ! I knew there was a flaw ! Attached is a script
(iziptest4.py) that uses all the above plus yet another
minor hole to actually decrement the reference counter of an
arbitrary object. Have you already seen  Python dying on you
with 'Fatal Python error: deallocating None' ?  :-)

The original idea came from lurking at izip_next(), when I
was thinking about using gc.get_referrers() to grab the
internally stored tuple (see bug report #793822). Then I
realized that the recursion trick would be sufficient for
izip_next(). Finally, the attached script exploits the
common problem of DECREF'ing an object that is still in the
tuple *before* actually storing something new at that
position, which is only a problem if one can actually see
the tuple from the __del__ method...

I can make a patch if you wish.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-08-27 06:00

Message:
Logged In: YES
user_id=80475

The bit about "only working when the tuple is not being
used" relates to the dependency on the C code that checks
that the refcount is one:
d = {(1,2,3):value} # Create a tuple with one reference
# now try to mutate it so that "value" becomes inaccessible

I'm curious about how the original idea arose and what was
the thought process you used to develop the clever,
exploitation script.

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2003-08-26 16:22

Message:
Logged In: YES
user_id=4771

I agree with your general analysis : it doesn't seem
harmful. I don't understand the bit about "only works when
the tuple is not being used", however. In the example script
the function 'f' stores a copy of the tuple; any number of
references can be hold accross the mutation. Here is another
example:

g = {}
def f(t): global T; T=t; g[T] = 'a'
mutatingtuple((1,2,3), f, (4,5,6)) # print T -> (1, 2, 3)
g[T] = 'b'
print g

This prints {(4, 5, 6): 'a', (4, 5, 6): 'b'}.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-08-24 19:17

Message:
Logged In: YES
user_id=80475

After more thought, I think this should be closed because the
attached tuple mutation script only works when the tuple is
not being used (there can be no other references to it) and in
that situation, it doesn't matter if a deliberate contrived

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-08-23 23:30

Message:
Logged In: YES
user_id=80475

technique appears elsewhere in the code base and has not

The exploitation script is impressive and it makes clear that
mutation requires combining a number of rare, deliberate
steps that don't occur in practice, i.e. the intensional
assignment to a tuple inside a self-referential iterator that
refers to itself by the name in an enclosing scope.

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2003-08-23 17:28

Message:
Logged In: YES
user_id=4771

Assigned to Raymond on the rationale that he's the author of
itertoolsmodule.c. I can propose a patch to
itertoolsmodule.c if you wish.

Also attached above example in a file.

----------------------------------------------------------------------

You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=793826&group_id=5470