bytearray.extend lacks overflow check when increasing buffer

[zhangyangyu]

BPO	27507
Nosy	@vadmium, @serhiy-storchaka, @ztane, @zhangyangyu, @AraHaan
Files	add_bytearray_extend_overflow_check.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 = None
closed_at = <Date 2016-07-18.09:57:33.670>
created_at = <Date 2016-07-13.17:12:28.083>
labels = ['interpreter-core', 'type-feature']
title = 'bytearray.extend lacks overflow check when increasing buffer'
updated_at = <Date 2016-07-18.10:00:24.338>
user = 'https://github.com/zhangyangyu'

bugs.python.org fields:

activity = <Date 2016-07-18.10:00:24.338>
actor = 'xiang.zhang'
assignee = 'none'
closed = True
closed_date = <Date 2016-07-18.09:57:33.670>
closer = 'martin.panter'
components = ['Interpreter Core']
creation = <Date 2016-07-13.17:12:28.083>
creator = 'xiang.zhang'
dependencies = []
files = ['43707']
hgrepos = []
issue_num = 27507
keywords = ['patch']
message_count = 17.0
messages = ['270327', '270328', '270331', '270362', '270366', '270391', '270394', '270395', '270400', '270564', '270568', '270602', '270603', '270622', '270726', '270742', '270743']
nosy_count = 6.0
nosy_names = ['python-dev', 'martin.panter', 'serhiy.storchaka', 'ztane', 'xiang.zhang', 'Decorater']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue27507'
versions = ['Python 2.7', 'Python 3.5', 'Python 3.6']

[zhangyangyu]

As the title, bytearray.extend simply use buf_size = len + (len >> 1) + 1; to determine next buf_size when increasing buffer. But this can overflow in theory. So I suggest adding overflow check.

[zhangyangyu]

Ohh, sorry for the disturb. I made a mistake. This is not needed and now close it.

[zhangyangyu]

Sorry, after checking again, this is still needed but maybe if (len == PY_SSIZE_T_MAX) part is not necessary since the iterable's length should not be larger than PY_SSIZE_T_MAX. But keep it to avoid theoretically bug is not a bad idea.

[vadmium]

It is possible to make an infinite iterable, e.g. iter(int, 1), so it is definitely worth checking for overflow. The patch looks okay to me. An alternative would be to raise the error without trying to allocate Py_SSIZE_T_MAX first, but I am okay with either way.

[zhangyangyu]

Nice to see the real example. I don't think of that.

[serhiy-storchaka]

Totally agreed with Martin.

[zhangyangyu]

So would you like to merge it like this or Martin's alternative way? But honestly speaking I don't get Martin's point, "without trying to allocate Py_SSIZE_T_MAX first", where is this place?

[ztane]

if (len == PY_SSIZE_T_MAX) is necessary for the case that the iterable is already PY_SSIZE_T_MAX items. However it could be moved inside the *other* if because if (len == PY_SSIZE_T_MAX) should also fail the overflow check.

However, I believe it is theoretical at most with stuff that Python supports that it would even be possible to allocate an array of PY_SSIZE_T_MAX pointers. The reason is that the maximum size of object can be only that of size_t, and Py_ssize_t should be a signed type of that size; and it would thus be possible only to allocate an array of PY_SSIZE_T_MAX pointers only if they're 16 bits wide.

In any case, this would be another place where my proposed macro "SUM_OVERFLOWS_PY_SSIZE_T" or something would be in order to make it read

if (SUM_OVERFLOWS_PY_SSIZE_T(len, (len >> 1) + 1)

which would make it easier to spot mistakes in the sign preceding 1.

[zhangyangyu]

Thanks for the analysis Antti. I don't think if (len == PY_SSIZE_T_MAX) can be moved inside the *other* if. Their handlings are different. if (len == PY_SSIZE_T_MAX) is True, it should exit immediately. But in the *other* if, you can still have a try to allocate PY_SSIZE_T_MAX memory.

As for your overflow macro, I think it's not very useful. First, not only Py_ssize_t can overflow, all signed types can. So a single SUM_OVERFLOWS_PY_SSIZE_T is not enough. Second, current overflow check pattern like a > PY_SSIZE_T_MAX - b is very obvious in my opinion.

[vadmium]

Not particularly related, but the special fast case in Objects/listobject.c:811, listextend(), also seems to lack an overflow check.

“An alternative would be to raise the error without trying to allocate Py_SSIZE_T_MAX first”: what I meant was removing the special case to allocate PY_SSIZE_T_MAX. As soon as it attempts to overallocate 2+ GiB of memory it fails. Something more like

addition = len >> 1;
if (addition > PY_SSIZE_T_MAX - len - 1) {
    /* . . . */
    return PyErr_NoMemory();
}
buf_size = len + addition;

Antti: in this case we are allocating an array of _bytes_, not pointers. So maybe it is possible to reach the limit with a 32-bit address space.