[Patches] [ python-Patches-645404 ] fix buffer overrun in pmerge

Tue, 31 Dec 2002 07:27:51 -0800

Patches item #645404, was opened at 2002-11-28 14: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: None
>Priority: 7
Submitted By: Zooko O'Whielacronx (zooko)
Assigned to: Guido van Rossum (gvanrossum)
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: Guido van Rossum (gvanrossum)
Date: 2002-12-31 10:27

Message:
Logged In: YES 
user_id=6380

Yuck. I'll look into this.

----------------------------------------------------------------------

Comment By: Neal Norwitz (nnorwitz)
Date: 2002-12-31 07: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 07: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 05: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