classification
Title: Stringlib fastsearch can read beyond the front of an array
Type: behavior Stage: resolved
Components: Interpreter Core Versions: Python 3.2, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: alex, benjamin.peterson, flox, pitrou, skrah
Priority: normal Keywords: patch

Created on 2010-04-25 18:05 by alex, last changed 2010-08-08 22:08 by flox. This issue is now closed.

Files
File name Uploaded Description Edit
issue8530_rfind.diff flox, 2010-04-25 18:35 Patch, apply to 2.x
Messages (10)
msg104149 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2010-04-25 18:05
In Objects/stringlib/fastsearch.h the lines:

                if (!STRINGLIB_BLOOM(mask, s[i-1]))

and

                if (!STRINGLIB_BLOOM(mask, s[i-1]))

can read beyond the front of the array that is passed to it when the loop enters with i = 0.

I originally noticed this when porting the algorithm to PyPy (which has bounds checking :)), all tests pass if I simple add `if i-1 >= 0` before the conditional.  This doesn't appear to actually cause the algorithm to ever break, but it is unsafe.
msg104150 - (view) Author: Florent Xicluna (flox) * (Python committer) Date: 2010-04-25 18:28
I guess we don't have the same issue with the find() implementation?

 if (!STRINGLIB_BLOOM(mask, s[i+m]))


Because:
 * len(s) = n = (w + m)
 * the loop condition is (i <= w)
  ==> s[w+m] is beyond the array, but it is '\0' probably

Is it correct?
msg104151 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2010-04-25 18:29
Yes, as the comment of the top of the file notes, reading to s[n] (where n == len(s)) is safe because strings are null padded.
msg104153 - (view) Author: Florent Xicluna (flox) * (Python committer) Date: 2010-04-25 18:35
This patch should fix it.
Since there's no failure, I don't find any test to add.
msg104155 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2010-04-25 18:40
I can't manage to trigger any crash on a Linux machine, so I think we'll live without a test.
msg104156 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2010-04-25 18:40
Of course your patch might slow down the loop, so perhaps you want to run some benchmarks.
msg104165 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2010-04-25 21:11
Why add a bounds check if it can't be caused to fail. How about just a comment?
msg104166 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2010-04-25 21:14
Well, the fact that it hasn't been shown to fail doesn't mean it can't fail.  It relies on reading undefined memory, which is usually bad ;).  However, since we're at i=0, regardless of what we add to the value it's going to end up terminating the loop, so I'm not sure if it can actually break in practice.
msg104169 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2010-04-25 21:34
It could read into an invalid page and segfault. It depends on specifics of the memory allocator.
msg113339 - (view) Author: Florent Xicluna (flox) * (Python committer) Date: 2010-08-08 22:08
Fixed with r83859 (on 3.2).
History
Date User Action Args
2010-08-08 22:08:01floxsetstatus: open -> closed
resolution: fixed
messages: + msg113339

stage: patch review -> resolved
2010-07-15 22:18:58skrahsetnosy: + skrah
2010-07-15 22:17:16skrahlinkissue9236 superseder
2010-04-25 21:34:21pitrousetmessages: + msg104169
2010-04-25 21:14:27alexsetmessages: + msg104166
2010-04-25 21:11:50benjamin.petersonsetnosy: + benjamin.peterson
messages: + msg104165
2010-04-25 18:41:13pitrousetversions: - Python 2.6, Python 3.1
2010-04-25 18:40:58pitrousetmessages: + msg104156
2010-04-25 18:40:07pitrousetnosy: + pitrou
messages: + msg104155
2010-04-25 18:35:43floxsetfiles: + issue8530_rfind.diff
keywords: + patch
messages: + msg104153

stage: needs patch -> patch review
2010-04-25 18:29:38alexsetmessages: + msg104151
2010-04-25 18:28:39floxsetmessages: + msg104150
2010-04-25 18:06:48pitrousetnosy: + flox
versions: + Python 2.6, Python 3.1, Python 2.7, Python 3.2
priority: normal
components: + Interpreter Core
type: behavior
stage: needs patch
2010-04-25 18:05:09alexcreate