[Patches] [ python-Patches-645404 ] fix buffer overrun in pmerge
noreply@sourceforge.net
noreply@sourceforge.net
Tue, 31 Dec 2002 09:34:58 -0800
Patches item #645404, was opened at 2002-11-28 20:38
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=645404&group_id=5470
Category: Core (C code)
Group: Python 2.3
Status: Open
Resolution: Fixed
Priority: 3
Submitted By: Zooko O'Whielacronx (zooko)
Assigned to: Finn Bock (bckfnn)
Summary: fix buffer overrun in pmerge
Initial Comment:
It sometimes overruns the PyList "j_lst". I don't
understand the algorithm here, so my fix is just based
on the fact that when it *does* overrun, the data it
reads probably doesn't == candidate, so I changed it to
behave in the '!= candidate' way when it reaches the
end of j_lst.
Someone who actually knows what this function actually
does should probably have a look at this patch.
Python passes its unit tests both before and after this
patch. Presumably there is a very small chance (< 1 in
4 billion) that it will behave incorrectly when it
reads data that does happen to == candidate. Also I
think there is a very small chance that it could get a
memory protection violation.
This bug was found with valgrind. It's not your
father's memory debugger! Valgrind has an extremely
low occurrence of false alarms, since it keeps track of
validity status for *every* *bit* of data, while
running your program in valgrind's internal x86
interpreter. It does *not* complain unless you do
something that is extremely likely to be fatally wrong,
such as branching on uninitialized data or writing to
unallocated memory.
This is the only bug revealed by running valgrind
unstable snapshot on Python CVS HEAD's self-test.
Here is a "suppression" file to ignore one particularly
amazing stunt that Python pulls. This suppression file
is for valgrind v1:
# add the cmdline arg `--suppressions=thisfile' when
invoking valgrind
{
PyObject_Free_Cond_inblock_Cond_okay
Cond
fun:PyObject_Free
}
{
PyObject_Free_Cond_inblock_Value4_okay
Value4
fun:PyObject_Free
}
{
PyObject_Free_Cond_inblock_Addr4_okay
Addr4
fun:PyObject_Free
}
{
PyObject_Realloc_Cond_inblock_Cond_okay
Cond
fun:PyObject_Realloc
}
{
PyObject_Realloc_Cond_inblock_Value4_okay
Value4
fun:PyObject_Realloc
}
{
PyObject_Realloc_Cond_inblock_Addr4_okay
Addr4
fun:PyObject_Realloc
}
Here are the same suppression rules for the unstable
snapshot of valgrind 2:
# add the cmdline arg `--suppressions=thisfile' when
invoking valgrind
{
PyObject_Free_Cond_inblock_Cond_okay
Memcheck:Cond
fun:PyObject_Free
}
{
PyObject_Free_Cond_inblock_Value4_okay
Memcheck:Value4
fun:PyObject_Free
}
{
PyObject_Free_Cond_inblock_Addr4_okay
Memcheck:Addr4
fun:PyObject_Free
}
{
PyObject_Realloc_Cond_inblock_Cond_okay
Memcheck:Cond
fun:PyObject_Realloc
}
{
PyObject_Realloc_Cond_inblock_Value4_okay
Memcheck:Value4
fun:PyObject_Realloc
}
{
PyObject_Realloc_Cond_inblock_Addr4_okay
Memcheck:Addr4
fun:PyObject_Realloc
}
----------------------------------------------------------------------
Comment By: Samuele Pedroni (pedronis)
Date: 2002-12-31 18:34
Message:
Logged In: YES
user_id=61408
Sorry, my fault.
The fix is correct.
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2002-12-31 17:38
Message:
Logged In: YES
user_id=6380
Checked in essentially Zooko's 1st patch as typeobject.c:2.200.
I'm leaving this open and assigning to Samuele -- this bug
was in the original patch too. Samuele, do you understand
what was intended here?
(Oops, Samuele doesn't have project permission. I think he
should. In the interim, I'm assigning this to Finn Bock.)
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2002-12-31 16:27
Message:
Logged In: YES
user_id=6380
Yuck. I'll look into this.
----------------------------------------------------------------------
Comment By: Neal Norwitz (nnorwitz)
Date: 2002-12-31 13:29
Message:
Logged In: YES
user_id=33168
Guido, I don't know if this patch is correct, but I also get
an invalid memory read. Here's the stack trace:
Invalid read of size 4
at 0x8077F43: pmerge (Objects/typeobject.c:1070)
by 0x8078115: mro_implementation (Objects/typeobject.c:1150)
by 0x8078185: mro_internal (Objects/typeobject.c:1174)
by 0x807AC84: PyType_Ready (Objects/typeobject.c:2804)
by 0x806F5EB: _Py_ReadyTypes (Objects/object.c:1890)
by 0x80A824C: Py_Initialize (Python/pythonrun.c:125)
by 0x80548D6: Py_Main (Modules/main.c:376)
by 0x80542B0: (within /home/neal/build/python/clean/python)
Address 0x41104614 is 0 bytes after a block of size 4 alloc'd
at 0x40168A70: malloc (vg_clientfuncs.c:100)
by 0x8063B73: PyList_New (Objects/listobject.c:77)
by 0x8058D8B: PySequence_List (Objects/abstract.c:1458)
by 0x807808A: mro_implementation (Objects/typeobject.c:1131)
by 0x8078185: mro_internal (Objects/typeobject.c:1174)
by 0x807AC84: PyType_Ready (Objects/typeobject.c:2804)
by 0x806F5EB: _Py_ReadyTypes (Objects/object.c:1890)
by 0x80A824C: Py_Initialize (Python/pythonrun.c:125)
by 0x80548D6: Py_Main (Modules/main.c:376)
----------------------------------------------------------------------
Comment By: Zooko O'Whielacronx (zooko)
Date: 2002-11-29 13:54
Message:
Logged In: YES
user_id=52562
Well, instead of applying patch 36415, apply this new patch,
and run the Python self-test. (This patch replaces the call
to PyList_GET_ITEM with PyList_GetItem, so that overruns are
detected and aborted.)
When I do, I get this output:
./python -E -tt ./Lib/test/regrtest.py -l
Traceback (most recent call last):
File "./Lib/test/regrtest.py", line 74, in ?
from sets import Set
File
"/home/zooko/playground/python/python/dist/src/Lib/sets.py",
line 372, in ?
class Set(BaseSet):
IndexError: list index out of range
make: [test] Error 1 (ignored)
When I apply my patch, it passes unit tests. When I run
test on unpatched CVS HEAD under valgrind, valgrind
identifies that line as a read-from-unallocated-memory
error. When I run test on my patch under valgrind, it
reports no errors.
----------------------------------------------------------------------
Comment By: Martin v. Löwis (loewis)
Date: 2002-11-29 11:06
Message:
Logged In: YES
user_id=21627
Can you provide a source code example that triggers the
problem?
----------------------------------------------------------------------
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=645404&group_id=5470