classification
Title: crash in str.rfind() with an invalid start value
Type: Stage:
Components: Interpreter Core Versions: Python 3.1, Python 3.2, Python 2.7, Python 2.6
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: flox, pitrou, vstinner
Priority: normal Keywords: patch

Created on 2009-12-08 10:21 by vstinner, last changed 2010-01-10 03:08 by vstinner. This issue is now closed.

Files
File name Uploaded Description Edit
str_find-4.patch vstinner, 2009-12-08 16:06
issue7458_rfind.diff flox, 2009-12-08 17:33 Patch, apply to trunk
Messages (15)
msg96117 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2009-12-08 10:21
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.
msg96118 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2009-12-08 10:23
In my test, start=6287518193 is an arbitrary value, it may crash or
not. The test might use any random integer > 0.
msg96119 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2009-12-08 10:33
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.
msg96120 - (view) Author: Florent Xicluna (flox) * (Python committer) Date: 2009-12-08 10:43
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)
msg96122 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2009-12-08 11:05
> 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.
msg96123 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2009-12-08 11:11
New patch with a more stable test. test_unicode does also fail (error
or crash) without the patch on find.h.
msg96124 - (view) Author: Florent Xicluna (flox) * (Python committer) Date: 2009-12-08 11:21
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 :)
msg96128 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-12-08 15:01
You shouldn't harcode 1 << 63 and 1 << 64, but calculate them based on
sys.maxsize instead.
msg96132 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2009-12-08 15:59
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 :-)
msg96133 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2009-12-08 16:06
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).
msg96143 - (view) Author: Florent Xicluna (flox) * (Python committer) Date: 2009-12-08 17:33
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.
msg96148 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2009-12-08 18:07
flox> Actually the "find" method was not broken.

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

I fixed this issue title.
msg96553 - (view) Author: Florent Xicluna (flox) * (Python committer) Date: 2009-12-18 08:40
I proposed a patch which solve this issue and improve performance of
str.rfind. See issue 7462.
msg97150 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2010-01-02 21:55
Ok, I've committed the tests after the patch for issue7462 removed the offending code. Thanks!
msg97496 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2010-01-10 03:08
> Ok, I've committed the tests after the patch for issue7462 removed the offending code. Thanks!

r77241 and r77247 in trunk
History
Date User Action Args
2010-01-10 03:08:18vstinnersetmessages: + msg97496
2010-01-02 21:55:59pitrousetstatus: open -> closed
resolution: fixed
messages: + msg97150
2009-12-18 08:40:12floxsetmessages: + msg96553
2009-12-08 18:07:28vstinnersetmessages: + msg96148
title: crash in str.find() and str.rfind() with invalid start value -> crash in str.rfind() with an invalid start value
2009-12-08 17:33:49floxsetfiles: + issue7458_rfind.diff

messages: + msg96143
2009-12-08 16:07:26vstinnersetfiles: - str_find-2.patch
2009-12-08 16:07:18vstinnersetfiles: - CRASH_rfind.py
2009-12-08 16:07:15vstinnersetfiles: - str_find.patch
2009-12-08 16:07:01vstinnersetfiles: - str_find-3.patch
2009-12-08 16:06:54vstinnersetfiles: + str_find-4.patch

messages: + msg96133
2009-12-08 15:59:45vstinnersetfiles: + str_find-3.patch

messages: + msg96132
2009-12-08 15:01:03pitrousetnosy: + pitrou
messages: + msg96128
2009-12-08 11:21:37floxsetmessages: + msg96124
versions: + Python 2.6, Python 3.1, Python 3.2
2009-12-08 11:11:56vstinnersetfiles: + str_find-2.patch

messages: + msg96123
2009-12-08 11:05:33vstinnersetmessages: + msg96122
2009-12-08 10:43:10floxsetnosy: + flox
messages: + msg96120
2009-12-08 10:33:14vstinnersetfiles: + CRASH_rfind.py

messages: + msg96119
2009-12-08 10:23:38vstinnersetmessages: + msg96118
2009-12-08 10:21:48vstinnersetfiles: + str_find.patch
keywords: + patch
2009-12-08 10:21:09vstinnercreate