Crash when deleting slices from duplicated bytearray

[johan]

BPO	23985
Nosy	@terryjreedy, @pitrou, @tjguk, @ned-deily, @vadmium, @zware, @serhiy-storchaka, @wm75
Files	bytearray_bug.py: Program demonstrating the problem linux-x86-64.py bytearray-fix.patch: Fixes the bug bytearray-resize.patch: Stop del expanding buffer bytearray-fixes.v2.patch: Both fixes + tests

^{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 2015-05-19.19:06:47.560>
created_at = <Date 2015-04-17.06:37:48.883>
labels = ['interpreter-core', 'type-crash']
title = 'Crash when deleting slices from duplicated bytearray'
updated_at = <Date 2015-05-21.18:01:32.997>
user = 'https://bugs.python.org/johan'

bugs.python.org fields:

activity = <Date 2015-05-21.18:01:32.997>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2015-05-19.19:06:47.560>
closer = 'pitrou'
components = ['Interpreter Core']
creation = <Date 2015-04-17.06:37:48.883>
creator = 'johan'
dependencies = []
files = ['39086', '39094', '39098', '39099', '39432']
hgrepos = []
issue_num = 23985
keywords = ['patch']
message_count = 20.0
messages = ['241316', '241321', '241323', '241325', '241327', '241330', '241376', '241382', '241399', '241400', '241402', '241594', '241611', '243161', '243162', '243596', '243618', '243619', '243768', '243772']
nosy_count = 11.0
nosy_names = ['terry.reedy', 'pitrou', 'tim.golden', 'ned.deily', 'python-dev', 'martin.panter', 'zach.ware', 'serhiy.storchaka', 'wolma', 'alexei.romanov', 'johan']
pr_nums = []
priority = 'high'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue23985'
versions = ['Python 3.4', 'Python 3.5']

[johan]

Python 3.4.3 crashes after some time when running the attached program under Windows 7.

The program appends a fixed bytes "string" to two independent bytearray buffers.
If slices are removed from the beginnging of the two buffers and the two buffers are print:ed, the program will crash at some random occation.

[ned-deily]

Reproduced with top of trunk default branch on OS X (so, not Windows-specific). With debug enabled:

$ ./bin/python3.5 /tmp/b/bytearray_bug.py
buf2: 13 5 bytearray(b'1234567890123')
buf1: 13 3 bytearray(b'1234567890123')
buf2: 21 2 bytearray(b'678901231234567890123')
buf1: 23 5 bytearray(b'45678901231234567890123')
buf2: 32 28 bytearray(b'89012312345678901231234567890123')
buf1: 31 21 bytearray(b'9012312345678901231234567890123')
buf2: 17 10 bytearray(b'01231234567890123')
buf1: 23 9 bytearray(b'45678901231234567890123')
buf2: 20 3 bytearray(b'78901231234567890123')
buf1: 27 14 bytearray(b'312345678901231234567890123')
buf2: 30 22 bytearray(b'012312345678901231234567890123')
buf1: 26 17 bytearray(b'12345678901231234567890123')
buf2: 21 1 bytearray(b'678901231234567890123')
buf1: 22 12 bytearray(b'5678901231234567890123')
buf2: 33 13 bytearray(b'789012312345678901231234567890123')
buf1: 23 4 bytearray(b'45678901231234567890123')
buf2: 33 23 bytearray(b'789012312345678901231234567890123')
buf1: 32 4 bytearray(b'89012312345678901231234567890123')
buf2: 23 19 bytearray(b'45678901231234567890123')
buf1: 41 36 bytearray(b'23123456789012312345678901231234567890123')
buf2: 17 3 bytearray(b'01231234567890123')
buf1: 18 3 bytearray(b'901231234567890123')
buf2: 27 23 bytearray(b'312345678901231234567890123')
buf1: 28 22 bytearray(b'2312345678901231234567890123')
buf2: 17 2 bytearray(b'01231234567890123')
buf1: 19 5 bytearray(b'8901231234567890123')
buf2: 28 10 bytearray(b'2312345678901231234567890123')
buf1: 27 2 bytearray(b'312345678901231234567890123')
buf2: 31 7 bytearray(b'9012312345678901231234567890123')
buf1: 38 2 bytearray(b'23456789012312345678901231234567890123')
buf2: 37 23 bytearray(b'3456789012312345678901231234567890123')
buf1: 49 2 bytearray(b'4567890123123456789012312345678901231234567890123')
buf2: 27 21 bytearray(b'312345678901231234567890123')
buf1: 60 1 bytearray(b'678901231234567890123123456789012312345678901231234567890123')
Debug memory block at address p=0x10bd238e0: API 'o'
    61 bytes originally requested
    The 7 pad bytes at p-7 are FORBIDDENBYTE, as expected.
    The 8 pad bytes at tail=0x10bd2391d are not all FORBIDDENBYTE (0xfb):
        at tail+0: 0x33 *** OUCH
        at tail+1: 0x00 *** OUCH
        at tail+2: 0xfb
        at tail+3: 0xfb
        at tail+4: 0xfb
        at tail+5: 0xfb
        at tail+6: 0xfb
        at tail+7: 0xfb
    The block was made by call python/issues-test-cpython#44842 to debug malloc/realloc.
    Data at p: 34 35 36 37 38 39 30 31 ... 35 36 37 38 39 30 31 32
Fatal Python error: bad trailing pad byte

Current thread 0x00007fff70e18300 (most recent call first):
File "/tmp/b/bytearray_bug.py", line 25 in <module>
Abort trap: 6

[ned-deily]

Above was in 64-bit mode (x86_64). Same run in 32-bit (i386):

$ ./bin/python3.5-32 /tmp/b/bytearray_bug.py
buf2: 13 2 bytearray(b'1234567890123')
buf1: 13 11 bytearray(b'1234567890123')
buf2: 24 16 bytearray(b'345678901231234567890123')
buf1: 15 4 bytearray(b'231234567890123')
buf2: 21 16 bytearray(b'678901231234567890123')
buf1: 24 3 bytearray(b'345678901231234567890123')
buf2: 18 1 bytearray(b'901231234567890123')
buf1: 34 28 bytearray(b'6789012312345678901231234567890123')
buf2: 30 21 bytearray(b'012312345678901231234567890123')
buf1: 19 8 bytearray(b'8901231234567890123')
buf2: 22 6 bytearray(b'5678901231234567890123')
buf1: 24 11 bytearray(b'345678901231234567890123')
buf2: 29 23 bytearray(b'12312345678901231234567890123')
buf1: 26 15 bytearray(b'12345678901231234567890123')
buf2: 19 15 bytearray(b'8901231234567890123')
buf1: 24 4 bytearray(b'345678901231234567890123')
buf2: 17 7 bytearray(b'01231234567890123')
buf1: 33 21 bytearray(b'789012312345678901231234567890123')
buf2: 23 13 bytearray(b'45678901231234567890123')
buf1: 25 20 bytearray(b'2345678901231234567890123')
buf2: 23 8 bytearray(b'45678901231234567890123')
buf1: 18 7 bytearray(b'901231234567890123')
buf2: 28 3 bytearray(b'2312345678901231234567890123')
buf1: 24 8 bytearray(b'345678901231234567890123')
buf2: 38 1 bytearray(b'23456789012312345678901231234567890123')
buf1: 29 7 bytearray(b'12312345678901231234567890123')
buf2: 50 38 bytearray(b'34567890123123456789012312345678901231234567890123')
buf1: 35 7 bytearray(b'56789012312345678901231234567890123')
buf2: 25 4 bytearray(b'2345678901231234567890123')
buf1: 41 20 bytearray(b'23123456789012312345678901231234567890123')
buf2: 34 24 bytearray(b'6789012312345678901231234567890123')
buf1: 34 19 bytearray(b'6789012312345678901231234567890123')
buf2: 23 1 bytearray(b'45678901231234567890123')
buf1: 28 18 bytearray(b'2312345678901231234567890123')
buf2: 35 20 bytearray(b'56789012312345678901231234567890123')
buf1: 23 13 bytearray(b'45678901231234567890123')
buf2: 28 16 bytearray(b'2312345678901231234567890123')
buf1: 23 19 bytearray(b'45678901231234567890123')
buf2: 25 16 bytearray(b'2345678901231234567890123')
buf1: 17 4 bytearray(b'01231234567890123')
buf2: 22 18 bytearray(b'5678901231234567890123')
buf1: 26 18 bytearray(b'12345678901231234567890123')
buf2: 17 14 bytearray(b'01231234567890123')
buf1: 21 18 bytearray(b'678901231234567890123')
buf2: 16 14 bytearray(b'1231234567890123')
buf1: 16 11 bytearray(b'1231234567890123')
buf2: 15 10 bytearray(b'231234567890123')
buf1: 18 2 bytearray(b'901231234567890123')
buf2: 18 2 bytearray(b'901231234567890123')
buf1: 29 3 bytearray(b'12312345678901231234567890123')
buf2: 29 11 bytearray(b'12312345678901231234567890123')
buf1: 39 9 bytearray(b'123456789012312345678901231234567890123')
buf2: 31 23 bytearray(b'9012312345678901231234567890123')
buf1: 43 31 bytearray(b'0123123456789012312345678901231234567890123')
Debug memory block at address p=0x7aec88: API 'o'
    49 bytes originally requested
    The 3 pad bytes at p-3 are FORBIDDENBYTE, as expected.
    The 4 pad bytes at tail=0x7aecb9 are not all FORBIDDENBYTE (0xfb):
        at tail+0: 0x31 *** OUCH
        at tail+1: 0x32 *** OUCH
        at tail+2: 0x33 *** OUCH
        at tail+3: 0x00 *** OUCH
    The block was made by call python/issues-test-cpython#44809 to debug malloc/realloc.
    Data at p: 31 32 33 34 35 36 37 38 ... 33 34 35 36 37 38 39 30
Fatal Python error: bad trailing pad byte

Current thread 0xa0ddc1d4 (most recent call first):
File "/tmp/b/bytearray_bug.py", line 25 in <module>
Abort trap: 6

[wm75]

Also happening with Python 3.4.0 on Ubuntu 14.04 (after ~ half a minute and A LOT of output):

[skipping lots of lines]
buf2: 29 13 bytearray(b'12312345678901231234567890123')
buf1: 25 9 bytearray(b'2345678901231234567890123')
buf2: 29 2 bytearray(b'12312345678901231234567890123')
buf1: 29 5 bytearray(b'12312345678901231234567890123')
buf2: 40 8 bytearray(b'3123456789012312345678901231234567890123')
buf1: 37 10 bytearray(b'3456789012312345678901231234567890123')
buf2: 45 31 bytearray(b'890123123456789012312345678901231234567890123')
buf1: 40 7 bytearray(b'3123456789012312345678901231234567890123')
buf2: 27 3 bytearray(b'312345678901231234567890123')
buf1: 46 9 bytearray(b'7890123123456789012312345678901231234567890123')
buf2: 37 6 bytearray(b'3456789012312345678901231234567890123')
buf1: 50 15 bytearray(b'34567890123123456789012312345678901231234567890123')
buf2: 44 5 bytearray(b'90123123456789012312345678901231234567890123')
buf1: 48 27 bytearray(b'567890123123456789012312345678901231234567890123')
buf2: 52 3 bytearray(b'1234567890123123456789012312345678901231234567890123')
buf1: 34 1 bytearray(b'6789012312345678901231234567890123')
buf2: 62 16 bytearray(b'45678901231234567890123123456789012312345678901231234567890123')
buf1: 46 13 bytearray(b'7890123123456789012312345678901231234567890123')
*** Error in `python3': realloc(): invalid pointer: 0x00007f2a45580000 ***

[wm75]

Surprisingly, a much simpler version with just one bytearray seems to run stably (for several minutes at least), but when you wait a while then hit Ctrl-C, you are getting a Segmentation fault:

Python 3.4.0 (default, Apr 11 2014, 13:05:11) 
[GCC 4.8.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import random
>>> buf1 = bytearray()
>>> data = b"1234567890123"
>>> 
>>> while True:
...     buf1 += data
...     l = len(buf1)
...     n = random.randrange(1, l-1)
...     del buf1[:n]
... 

^CSegmentation fault (core dumped)

The same code crashes spontaneously (without attempting a keyboard interrupt) when run in IDLE.

[alexeiromanov]

No problem with python 2.7.6 on Ubuntu 14.04.2 LTS amd64. Attached script was working about 2 hours - no crash.

[terryjreedy]

Win7, 64 bit, 3.5.0a3: crash in about 10 seconds.

[vadmium]

Here is a reduced version without using random numbers that reliably crashes for me on 64-bit Linux. Hopefully it also crashes for others, and they can investigate further. Crashes for me with the standard Arch Linux binary:

Python 3.4.3 (default, Feb 26 2015, 23:01:07)
[GCC 4.9.2 20150204 (prerelease)] on linux

and my recently built v3.5 version:

Python 3.5.0a3+ (default:0b3027a2abbc, Apr 11 2015, 23:27:07)
[GCC 4.9.1] on linux

It does not crash on 32 bit computer I tried though.

[vadmium]

After cleaning my build and rebuilding with “./configure --with-pymalloc --with-pydebug”, I reduced my script to these four lines:

b1 = bytearray(b"abcdefghij")  # 10 bytes
del b1[:1]
del b1[:1]
b1 += b"klmnopq"  # 7 bytes

Patch bytearray-fix.patch fixes the bug by taking account fact that ob_start is offset into the allocated memory buffer when checking if a reallocation is necessary.

Explanation with the unpatched code and my four-line script above:

1. First line allocates 11 bytes of memory (10 for the byte string + 1 NUL terminator)

2. First “del” reduces the bytearray length to 9 bytes, but actually reallocates an expanded memory buffer of 16 bytes! (quirky but not the bug)

3. Second “del” reduces the bytearray length to 8 bytes, and increments an internal ob_start offset without any memory copying or reallocation. (Fine.)

4. Appending step needs to add 7 bytes to the 8-byte array. 7 + 8 + 1 is 16 bytes total required for bytearray and NUL terminator, but since ob_start is offset from the start of the allocated memory buffer, we overwrite past the end of the buffer.

Memory debugging output and extra debug printfs of my own:

Resizing to size 10 (current log. offset 0 alloc 0)
=> Major upsize, new alloc = 11
Assigning to linear slice

• Shifting ob_start for negative growth -1
  Resizing to size 9 (current log. offset 1 alloc 11)
  => Moderate upsize, new alloc = 16
• Done assigning to linear slice
  Assigning to linear slice
• Shifting ob_start for negative growth -1
  Resizing to size 8 (current log. offset 1 alloc 16)
  => Minor downsize
• Done assigning to linear slice
  Debug memory block at address p=0x7f1af630a0d0: API 'o'
  16 bytes originally requested
  The 7 pad bytes at p-7 are FORBIDDENBYTE, as expected.
  The 8 pad bytes at tail=0x7f1af630a0e0 are not all FORBIDDENBYTE (0xfb):
  at tail+0: 0x00 *** OUCH
  at tail+1: 0xfb
  at tail+2: 0xfb
  at tail+3: 0xfb
  at tail+4: 0xfb
  at tail+5: 0xfb
  at tail+6: 0xfb
  at tail+7: 0xfb
  The block was made by call bpo-32897 to debug malloc/realloc.
  Data at p: 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70 71
  Fatal Python error: bad trailing pad byte

[vadmium]

Posting bytearray-resize.patch which stops “del” from expanding the allocated buffer. This one is not necessary to fix the reported bug, but avoids the separate quirk identified in step 2.

[vadmium]

This bug might have been caused by the changes for bpo-19087, so I left a note there. It looks like that issue added the ob_start field to bytearray() objects, so that deleting from the start does not require memory copying.

[vadmium]

A test case for this that would trigger when memory debugging is enabled could look something like the following. Would it be appropriate to add it to the test suite?

a = bytearray(10)
size = sys.getsizeof(a)
a.pop()  # Defeat expanding buffer off-by-one quirk
self.assertEqual(sys.getsizeof(a), size, "Quirk not defeated")
del a[:1]
# Or a.pop(0)  # Does not trigger bug
# Or a[:1] = ()  # Triggers bug
self.assertEqual(sys.getsizeof(a), size, "Test assumes buffer not resized")
a += bytes(2)  # Add exactly the number of free bytes in buffer
# Or a.extend(bytes(2))  # Unaffected
# Or a.append(0); a.append(0)  # Unaffected
# Or a[8:] = bytes(2)  # Unaffected
del a  # Trigger memory buffer to be freed, with verification

[johan]

Thank you all for working really fast on this issue!
I'm happy to see that a fix is already being tried out.

[vadmium]

Antoine, would you have a chance to review my patches? I assume you were responsible for adding the ob_start field.

It would be nice to see this bug fixed in the next 3.4 and 3.5 releases. As well as the original poster’s problem, I suspect this bug may be the cause of some occasional strange behaviour I have seen in my own bytearray() FIFO type code.

[pitrou]

Sorry. I'll take a look!

[vadmium]

Posting a new patch which combines both fixes and adds some test cases. However the test needs Python to be built with “./configure --with-pydebug” to detect the buffer overrun; without this the test will probably silently pass.

I removed the offending buffer space check, and let it always call PyBufferArray_Resize(). I also looked around the bytearray module for similar errors for other operations but I couldn’t find any. The other cases already tend to always call PyByteArray_Resize().

[python-dev]

New changeset 98c1201d8eea by Antoine Pitrou in branch '3.4':
Issue bpo-23985: Fix a possible buffer overrun when deleting a slice from the front of a bytearray and then appending some other bytes data.
https://hg.python.org/cpython/rev/98c1201d8eea

New changeset 06fab9093973 by Antoine Pitrou in branch 'default':
Issue bpo-23985: Fix a possible buffer overrun when deleting a slice from the front of a bytearray and then appending some other bytes data.
https://hg.python.org/cpython/rev/06fab9093973

[pitrou]

I've committed the patch. Thanks, Martin!

[python-dev]

New changeset 274c1b0a2494 by Serhiy Storchaka in branch '2.7':
Issue bpo-23985: Fixed integer overflow in iterator object. Original patch by
https://hg.python.org/cpython/rev/274c1b0a2494

New changeset 5b86a1abc8c3 by Serhiy Storchaka in branch '3.4':
Issue bpo-23985: Fixed integer overflow in iterator object. Patch by
https://hg.python.org/cpython/rev/5b86a1abc8c3

New changeset 9f2a1d9d7164 by Serhiy Storchaka in branch 'default':
Issue bpo-23985: Fixed integer overflow in iterator object. Patch by
https://hg.python.org/cpython/rev/9f2a1d9d7164

[serhiy-storchaka]

Sorry, it was related to bpo-22939.