crash in str.rfind() with an invalid start value

[vstinner]

BPO	7458
Nosy	@pitrou, @vstinner, @florentx
Files	str_find-4.patch issue7458_rfind.diff: Patch, apply to trunk

^{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 2010-01-02.21:55:59.397>
created_at = <Date 2009-12-08.10:21:09.224>
labels = ['interpreter-core']
title = 'crash in str.rfind() with an invalid start value'
updated_at = <Date 2010-01-10.03:08:18.855>
user = 'https://github.com/vstinner'

bugs.python.org fields:

activity = <Date 2010-01-10.03:08:18.855>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2010-01-02.21:55:59.397>
closer = 'pitrou'
components = ['Interpreter Core']
creation = <Date 2009-12-08.10:21:09.224>
creator = 'vstinner'
dependencies = []
files = ['15497', '15501']
hgrepos = []
issue_num = 7458
keywords = ['patch']
message_count = 15.0
messages = ['96117', '96118', '96119', '96120', '96122', '96123', '96124', '96128', '96132', '96133', '96143', '96148', '96553', '97150', '97496']
nosy_count = 3.0
nosy_names = ['pitrou', 'vstinner', 'flox']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue7458'
versions = ['Python 2.6', 'Python 3.1', 'Python 2.7', 'Python 3.2']

[vstinner]

str.find() and str.rfind() reads non initialized memory (using
memcmp()) if start is bigger than end.

Attached patch fixes the issue and includes a patch.

[vstinner]

In my test, start=6287518193 is an arbitrary value, it may crash or
not. The test might use any random integer > 0.

[vstinner]

The bug was introduced in Python 2.5 during the needforspeed sprint:
r46469 (May 27 2006).
http://wiki.python.org/moin/NeedForSpeed

Python < 2.5 is not affected, Python 3.x is affected.

CRASH_rfind.py is more stable and should always crash if your Python
version has the bug.

[florentx]

This bug does not occur on Debian 64 bits.

~ $ uname -srvm
Linux 2.6.30-bpo.1-amd64 #1 SMP Mon Aug 17 08:42:50 UTC 2009 x86_64

Tested with variants:
from random import getrandbits
self.checkequal(-1, 'ab', 'find', 'xxx', getrandbits(64), 0)
self.checkequal(-1, 'ab', 'find', 'xxx', getrandbits(96), 0)
self.checkequal(-1, 'ab', 'rfind', 'xxx', getrandbits(64), 0)
self.checkequal(-1, 'ab', 'rfind', 'xxx', getrandbits(96), 0)

[vstinner]

This bug does not occur on Debian 64 bits.

It does, sometime :-) Read uninitiliazed memory doesn't always crash.

   $ python -c "'ab'.rfind('xxx', (1 << 63) + 10, 0)"
   Erreur de segmentation

Note: my 64 bits test in CRASH_rfind.py is wrong, ctypes.c_long should
be used instead of ctypes.c_int.

[vstinner]

New patch with a more stable test. test_unicode does also fail (error
or crash) without the patch on find.h.

[florentx]

I got it to crash (2.7):

~ $ ./python Lib/test/regrtest.py string_tests test_unicode test_str
test_unicode
test test_unicode failed -- Traceback (most recent call last):
AssertionError: -1 != -8276732

test_str
test test_str failed -- Traceback (most recent call last):
AssertionError: -1 != -255833

2 tests failed:
test_unicode test_str
[56425 refs]
~ $

Thank you haypo :)

[pitrou]

You shouldn't harcode 1 << 63 and 1 << 64, but calculate them based on
sys.maxsize instead.

[vstinner]

pitrou> You shouldn't harcode 1 << 63 and 1 << 64, but calculate
pitrou> them based on sys.maxsize instead.

(sys.maxint) Yes, you're right. Does str_find-3.patch looks better?
It's not easy to always detect an Heisenbug :-)

[vstinner]

sys.maxint/sys.maxsize: oops, sys.maxsize *does* exist (in Python >=
2.6), sorry. Here is a new patch using sys.maxsize.

Anyway, sys.maxsize sounds better because the integer overflow occurs
in a Py_ssize_t variable (j).

[florentx]

I reviewed the patch, and it seems partially redundant.

Actually the "find" method was not broken.
There is already a test "if (str_len < 0) return -1;" for this one.

See attached patch.

[vstinner]

flox> Actually the "find" method was not broken.

Oh, you're right, str.find() was already fixed by r66631 (related to
issue bpo-3967). I prefer your patch flox ;-)

I fixed this issue title.

[florentx]

I proposed a patch which solve this issue and improve performance of
str.rfind. See bpo-7462.