integer overflow in iterator object

[httpsgithubcomhakril]

BPO	22939
Nosy	@rhettinger, @ronaldoussoren, @mdickinson, @vstinner, @bitdancer, @serhiy-storchaka, @https://github.com/hakril
Files	issue22939.patch: First try for the patch issue22939v2.patch: Second try for the patch

^{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/serhiy-storchaka'
closed_at = <Date 2015-05-21.18:00:05.944>
created_at = <Date 2014-11-25.10:56:33.086>
labels = ['interpreter-core', 'type-bug']
title = 'integer overflow in iterator object'
updated_at = <Date 2015-05-21.18:00:05.943>
user = 'https://github.com/httpsgithubcomhakril'

bugs.python.org fields:

activity = <Date 2015-05-21.18:00:05.943>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2015-05-21.18:00:05.944>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2014-11-25.10:56:33.086>
creator = 'hakril'
dependencies = []
files = ['37375', '37382']
hgrepos = []
issue_num = 22939
keywords = ['patch']
message_count = 24.0
messages = ['231651', '231659', '231660', '231664', '231669', '231676', '232250', '232267', '232269', '232282', '232284', '232285', '232362', '232365', '232367', '232368', '232385', '233021', '233203', '234233', '242960', '243568', '243769', '243771']
nosy_count = 8.0
nosy_names = ['rhettinger', 'ronaldoussoren', 'mark.dickinson', 'vstinner', 'r.david.murray', 'python-dev', 'serhiy.storchaka', 'hakril']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue22939'
versions = ['Python 2.7', 'Python 3.4', 'Python 3.5']

[httpsgithubcomhakril]

I found an interger overflow in the standard iterator object (Objects/iterobject.c)

The it_index attribute used by the iterator is a Py_ssize_t but overflow is never checked. So after the index PY_SSIZE_T_MAX, the iterator object will ask for the index PY_SSIZE_T_MIN.

Here is an example:

    import sys

    class Seq:
        def __getitem__(self, item):
            print("[-] Asked for item at <{0}>".format(item))
            return 0

    s = Seq()
    i = iter(s)
    # Manually set `it_index` to PY_SSIZE_T_MAX without a loop
    i.__setstate__(sys.maxsize)

    next(i)
    [-] Asked for item at <9223372036854775807>
    next(i)
    [-] Asked for item at <-9223372036854775808>

I would be really interested in writing a patch but first I wanted to discuss the expected behaviour and fix.

The iterator could stop after PY_SSIZE_T_MAX but it seems strange as other iterator (like enumobject) handle values bigger than PY_SSIZE_T_MAX.

Or the same technique used in enumobject could be used: adding a field PyObject* en_longindex (a python long) which would be used for values bigger than PY_SSIZE_T_MAX

[bitdancer]

For possibly relevant background information, see bpo-21444 and the issues linked from it, and bpo-14794.

[vstinner]

The it_index attribute used by the iterator is a Py_ssize_t but overflow is never checked.

Yes it is a bug. iter_iternext() must raises an OverflowError if it->it_index is equal to PY_SSIZE_T_MAX.

[serhiy-storchaka]

I think OverflowError is good for maintained releases, but for 3.5 Clement's idea with long index looks attractive to me. In any case an exception should be raised for negative argument in __setstate__(). Let split this issue on two parts. First fix the bug by raising exceptions, and then add long index (if anyone will need it).

[vstinner]

I think OverflowError is good for maintained releases, but for 3.5 Clement's idea with long index looks attractive to me.

What is your use case?

[serhiy-storchaka]

What is your use case?

Something like range(). I agree that it is very unlike to encounter this
problem in real work, and we can live with implementation-related limitation
(for which OverflowError exists).

[httpsgithubcomhakril]

Here is a first try for a patch.

There are two points I am not sure about:

1. The message for the OverflowError: is that explicit enough ?

2. The behaviour of the iterator after the raise of OverflowError.
   With this patch every call to next(it) where it have overflowed will raise OverflowError again.
   Does this behaviour seems correct our should it raise StopIteration after the first OverflowError ?

[vstinner]

You should not rely on undefined behaviour: check if the index is greater
or equal than PY_SSIZET_MAX - 1. __setstate__ must implement the same check.

You must always raise an error, not hide it in a second call to next (raise
StopIteration). Your unit test must check this behaviour.

[serhiy-storchaka]

check if the index is greater or equal than PY_SSIZET_MAX - 1.

Just PY_SSIZET_MAX.

Added other comments on Rietveld (look the email in the Spam folder).

[httpsgithubcomhakril]

Thanks for the comments.
I corrected the patch and updated the test. I also added a test that check the behavior of setstate with negative indice.

Just one question:

__setstate__ must implement the same check.

Why should __setstate__ check for PY_SSIZE_T_MAX (throwing OverflowError when unpickling) if the check will be done when calling next on the resulting iterator ?

[serhiy-storchaka]

__setstate__ should check that an index is not negative. All values from 0 to PY_SSIZE_T_MAX are acceptable.

[serhiy-storchaka]

Ah, __setstate__ already handles negative indices. Then the patch LGTM.

[rhettinger]

I would think that the PY_SSIZE_T_MAX check belongs inside the:

    if (result != NULL) {
        it->it_index++;
        return result;
    }

just before the increment which could cause the overflow. Also, PY_SSIZE_T_MAX is a valid value to pass to PySequence_GetItem(), so it shouldn't be blocked unless necessary.