classification
Title: deque.index() overruns deque boundary
Type: security Stage: resolved
Components: Versions: Python 3.6, Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: larry Nosy List: Arfrever, JohnLeitch, brett.cannon, brycedarling, larry, python-dev, rhettinger, skrah
Priority: release blocker Keywords: patch

Created on 2015-08-21 23:09 by JohnLeitch, last changed 2015-09-08 18:36 by Arfrever. This issue is now closed.

Files
File name Uploaded Description Edit
newblock_Uninitialized_variable.patch JohnLeitch, 2015-08-21 23:08 patch
newblock_Uninitialized_variable.py JohnLeitch, 2015-08-21 23:10 repro
fix_deque_overrun.diff rhettinger, 2015-08-26 06:16 Patch to fix overrun review
fix_deque_overrun2.diff rhettinger, 2015-08-26 08:52 Revised patch to fix overrun review
Messages (15)
msg248985 - (view) Author: John Leitch (JohnLeitch) * Date: 2015-08-21 23:08
Python 3.5 suffers from a vulnerability caused by the behavior of the newblock() function used by the collections.deque module. When called, newblock() allocates memory using PyMem_Malloc() and does not initialize it:

static block *
newblock(Py_ssize_t len) {
    block *b;
    if (len >= MAX_DEQUE_LEN) {
        PyErr_SetString(PyExc_OverflowError,
                        "cannot add more blocks to the deque");
        return NULL;
    }
    if (numfreeblocks) {
        numfreeblocks--;
        return freeblocks[numfreeblocks];
    }
    b = PyMem_Malloc(sizeof(block)); <<<< Memory allocation.
    if (b != NULL) {
        return b; <<<< Buffer returned without initialization.
    }
    PyErr_NoMemory();
    return NULL;
}

Because PyMem_Malloc does not initialize the memory, the block may contain garbage data. In some cases, this can lead to memory corruption which could be exploitable to achieve code execution. The following exception analysis is an example of EIP corruption:

 *******************************************************************************
*                                                                             *
*                        Exception Analysis                                   *
*                                                                             *
*******************************************************************************

*** The OS name list needs to be updated! Unknown Windows version: 10.0 ***

FAULTING_IP:
python35!PyUnicode_Type+0
696f60d8 a800            test    al,0

EXCEPTION_RECORD:  ffffffff -- (.exr 0xffffffffffffffff)
ExceptionAddress: 696f60d8 (python35!PyUnicode_Type)
   ExceptionCode: c0000005 (Access violation)
  ExceptionFlags: 00000000
NumberParameters: 2
   Parameter[0]: 00000008
   Parameter[1]: 696f60d8
Attempt to execute non-executable address 696f60d8

CONTEXT:  00000000 -- (.cxr 0x0;r)
eax=696f60d8 ebx=00000002 ecx=00d9492c edx=00000002 esi=019b4e58 edi=0337b970
eip=696f60d8 esp=00bcf7dc ebp=00bcf7fc iopl=0         nv up ei pl nz na pe nc
cs=0023  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00010206
python35!PyUnicode_Type:
696f60d8 a800            test    al,0

PROCESS_NAME:  pythonw.exe

ERROR_CODE: (NTSTATUS) 0xc0000005 - The instruction at 0x%p referenced memory at 0x%p. The memory could not be %s.

EXCEPTION_CODE: (NTSTATUS) 0xc0000005 - The instruction at 0x%p referenced memory at 0x%p. The memory could not be %s.

EXCEPTION_PARAMETER1:  00000008

EXCEPTION_PARAMETER2:  696f60d8

WRITE_ADDRESS:  696f60d8

FOLLOWUP_IP:
python35!PyUnicode_Type+0
696f60d8 a800            test    al,0

FAILED_INSTRUCTION_ADDRESS:
python35!PyUnicode_Type+0
696f60d8 a800            test    al,0

APP:  pythonw.exe

ANALYSIS_VERSION: 6.3.9600.17029 (debuggers(dbg).140219-1702) x86fre

FAULTING_THREAD:  000009dc

DEFAULT_BUCKET_ID:  SOFTWARE_NX_FAULT_CODE

PRIMARY_PROBLEM_CLASS:  SOFTWARE_NX_FAULT_CODE

BUGCHECK_STR:  APPLICATION_FAULT_SOFTWARE_NX_FAULT_CODE_SOFTWARE_NX_FAULT_FALSE_POSITIVE

LAST_CONTROL_TRANSFER:  from 69505ad3 to 696f60d8

STACK_TEXT:
00bcf7fc 69505ad3 00000002 00bcf840 694253fc python35!PyUnicode_Type
00bcf808 694253fc 0337b970 019b4e58 00000002 python35!PyObject_RichCompare+0x53
00bcf840 695031c3 03a1a8f0 03a21878 00f83340 python35!deque_index+0xac
00bcf85c 69564433 03a21120 03a21878 00000000 python35!PyCFunction_Call+0x113
00bcf890 695618d8 00e23a08 00000000 00000040 python35!call_function+0x303
00bcf908 6956339f 00e23a08 00000000 00f83000 python35!PyEval_EvalFrameEx+0x2318
00bcf954 6959a142 00e40f58 00000000 00000000 python35!_PyEval_EvalCodeWithName+0x82f
00bcf990 69599fd5 00e40f58 00e40f58 00bcfa5c python35!run_mod+0x42
00bcf9bc 6959904a 00f801f0 00e366f0 00000101 python35!PyRun_FileExFlags+0x85
00bcfa00 6946f037 00f801f0 00e366f0 00000001 python35!PyRun_SimpleFileExFlags+0x20a
00bcfa2c 6946f973 00bcfa5c 00000000 6ecb2100 python35!run_file+0xe7
00bcfad4 1ce31279 00000002 00f79eb0 1ce3c588 python35!Py_Main+0x913
00bcfae4 1ce3145f 1ce30000 00000000 00f71c68 pythonw!wWinMain+0x19
00bcfb30 74ed3744 7f174000 74ed3720 5c8b59d2 pythonw!__scrt_common_main_seh+0xfd
00bcfb44 775aa064 7f174000 a81800d2 00000000 kernel32!BaseThreadInitThunk+0x24
00bcfb8c 775aa02f ffffffff 775cd7c3 00000000 ntdll!__RtlUserThreadStart+0x2f
00bcfb9c 00000000 1ce3150a 7f174000 00000000 ntdll!_RtlUserThreadStart+0x1b


STACK_COMMAND:  ~0s; .ecxr ; kb

SYMBOL_STACK_INDEX:  0

SYMBOL_NAME:  python35!PyUnicode_Type+0

FOLLOWUP_NAME:  MachineOwner

MODULE_NAME: python35

IMAGE_NAME:  python35.dll

DEBUG_FLR_IMAGE_TIMESTAMP:  5598ccc2

FAILURE_BUCKET_ID:  SOFTWARE_NX_FAULT_CODE_c0000005_python35.dll!PyUnicode_Type

BUCKET_ID:  APPLICATION_FAULT_SOFTWARE_NX_FAULT_CODE_SOFTWARE_NX_FAULT_FALSE_POSITIVE_BAD_IP_python35!PyUnicode_Type+0

ANALYSIS_SOURCE:  UM

FAILURE_ID_HASH_STRING:  um:software_nx_fault_code_c0000005_python35.dll!pyunicode_type

FAILURE_ID_HASH:  {aa94d074-8f9b-b618-df4f-eaad15f84370}

Followup: MachineOwner
---------

To fix the issue, it is recommended that newblock use PyMem_Calloc instead of PyMem_Malloc. A proposed patch has been attached.

Credit: John Leitch (johnleitch@outlook.com), Bryce Darling (darlingbryce@gmail.com)
msg249126 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-08-25 15:12
I'm find the "exception analysis" to be unreadable.  Have you found any place in the deque code where the uninitialized memory actually gets accessed?
msg249130 - (view) Author: John Leitch (JohnLeitch) * Date: 2015-08-25 15:54
The "exception analysis" is output from the WinDbg !analyze command run on a crash where access to the uninitialized memory ultimately corrupted the instruction pointer, leading to a data execution prevention crash. That's why the disassembly is junk--the IP is not pointing to valid instructions. This crash was provided as an example because it demonstrates that the issue is likely exploitable, and can probably be used to achieve code execution.

Here is an example of a crash where execution halts immediately upon attempted to dereference a corrupted pointer. Note that the pointer is 0xC0C0C0C0--a fill pattern indicative of uninitialized memory. 

0:000> r
eax=000002a2 ebx=551160a8 ecx=c0c0c0c0 edx=07e538e0 esi=07e538e0 edi=c0c0c0c0
eip=54f25a55 esp=004cf6e4 ebp=004cf6f4 iopl=0         nv up ei ng nz na pe cy
cs=0023  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00010287
python35!do_richcompare+0x15:
54f25a55 8b4704          mov     eax,dword ptr [edi+4] ds:002b:c0c0c0c4=????????
0:000> k
ChildEBP RetAddr  
004cf6f4 54f25be3 python35!do_richcompare+0x15 [c:\build\cpython\objects\object.c @ 659]
004cf700 54e453fc python35!PyObject_RichCompare+0x53 [c:\build\cpython\objects\object.c @ 718]
(Inline) -------- python35!PyObject_RichCompareBool+0x14 [c:\build\cpython\objects\object.c @ 739]
004cf738 54f232d3 python35!deque_index+0xac [c:\build\cpython\modules\_collectionsmodule.c @ 933]
004cf754 54f8442f python35!PyCFunction_Call+0x113 [c:\build\cpython\objects\methodobject.c @ 109]
004cf788 54f818ec python35!call_function+0x2ff [c:\build\cpython\python\ceval.c @ 4651]
004cf800 54f8339f python35!PyEval_EvalFrameEx+0x232c [c:\build\cpython\python\ceval.c @ 3184]
004cf84c 54fba0b2 python35!_PyEval_EvalCodeWithName+0x82f [c:\build\cpython\python\ceval.c @ 3962]
(Inline) -------- python35!PyEval_EvalCodeEx+0x21 [c:\build\cpython\python\ceval.c @ 3983]
(Inline) -------- python35!PyEval_EvalCode+0x21 [c:\build\cpython\python\ceval.c @ 777]
004cf888 54fb9f45 python35!run_mod+0x42 [c:\build\cpython\python\pythonrun.c @ 970]
004cf8b4 54fb8fba python35!PyRun_FileExFlags+0x85 [c:\build\cpython\python\pythonrun.c @ 923]
004cf8f8 54e8f1f7 python35!PyRun_SimpleFileExFlags+0x20a [c:\build\cpython\python\pythonrun.c @ 396]
(Inline) -------- python35!PyRun_AnyFileExFlags+0x4e [c:\build\cpython\python\pythonrun.c @ 80]
004cf924 54e8fb33 python35!run_file+0xe7 [c:\build\cpython\modules\main.c @ 318]
004cf9c8 1cd4143f python35!Py_Main+0x913 [c:\build\cpython\modules\main.c @ 768]
(Inline) -------- python!invoke_main+0x1d [f:\dd\vctools\crt\vcstartup\src\startup\exe_common.inl @ 89]
004cfa14 75463744 python!__scrt_common_main_seh+0xff [f:\dd\vctools\crt\vcstartup\src\startup\exe_common.inl @ 264]
004cfa28 76f0a064 KERNEL32!BaseThreadInitThunk+0x24
004cfa70 76f0a02f ntdll!__RtlUserThreadStart+0x2f
004cfa80 00000000 ntdll!_RtlUserThreadStart+0x1b
0:000> !analyze -v -nodb
*******************************************************************************
*                                                                             *
*                        Exception Analysis                                   *
*                                                                             *
*******************************************************************************


FAULTING_IP: 
python35!do_richcompare+15 [c:\build\cpython\objects\object.c @ 659]
54f25a55 8b4704          mov     eax,dword ptr [edi+4]

EXCEPTION_RECORD:  ffffffff -- (.exr 0xffffffffffffffff)
ExceptionAddress: 54f25a55 (python35!do_richcompare+0x00000015)
   ExceptionCode: c0000005 (Access violation)
  ExceptionFlags: 00000000
NumberParameters: 2
   Parameter[0]: 00000000
   Parameter[1]: c0c0c0c4
Attempt to read from address c0c0c0c4

CONTEXT:  00000000 -- (.cxr 0x0;r)
eax=000002a2 ebx=551160a8 ecx=c0c0c0c0 edx=07e538e0 esi=07e538e0 edi=c0c0c0c0
eip=54f25a55 esp=004cf6e4 ebp=004cf6f4 iopl=0         nv up ei ng nz na pe cy
cs=0023  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00010287
python35!do_richcompare+0x15:
54f25a55 8b4704          mov     eax,dword ptr [edi+4] ds:002b:c0c0c0c4=????????

FAULTING_THREAD:  00004a48

DEFAULT_BUCKET_ID:  INVALID_POINTER_READ

PROCESS_NAME:  python.exe

ERROR_CODE: (NTSTATUS) 0xc0000005 - The instruction at 0x%p referenced memory at 0x%p. The memory could not be %s.

EXCEPTION_CODE: (NTSTATUS) 0xc0000005 - The instruction at 0x%p referenced memory at 0x%p. The memory could not be %s.

EXCEPTION_PARAMETER1:  00000000

EXCEPTION_PARAMETER2:  c0c0c0c4

READ_ADDRESS:  c0c0c0c4 

FOLLOWUP_IP: 
python35!do_richcompare+15 [c:\build\cpython\objects\object.c @ 659]
54f25a55 8b4704          mov     eax,dword ptr [edi+4]

NTGLOBALFLAG:  2000000

APPLICATION_VERIFIER_FLAGS:  0

APP:  python.exe

ANALYSIS_VERSION: 6.3.9600.17029 (debuggers(dbg).140219-1702) x86fre

PRIMARY_PROBLEM_CLASS:  INVALID_POINTER_READ

BUGCHECK_STR:  APPLICATION_FAULT_INVALID_POINTER_READ

LAST_CONTROL_TRANSFER:  from 54f25be3 to 54f25a55

STACK_TEXT:  
004cf6f4 54f25be3 00000002 004cf738 54e453fc python35!do_richcompare+0x15
004cf700 54e453fc c0c0c0c0 07e538e0 00000002 python35!PyObject_RichCompare+0x53
004cf738 54f232d3 07e31d18 07e50e40 08e78b48 python35!deque_index+0xac
004cf754 54f8442f 08e78b48 07e50e40 00000000 python35!PyCFunction_Call+0x113
004cf788 54f818ec 0586eab0 00000000 00000040 python35!call_function+0x2ff
004cf800 54f8339f 0586eab0 00000000 08910ff0 python35!PyEval_EvalFrameEx+0x232c
004cf84c 54fba0b2 0588ff80 00000000 00000000 python35!_PyEval_EvalCodeWithName+0x82f
004cf888 54fb9f45 0588ff80 0588ff80 004cf954 python35!run_mod+0x42
004cf8b4 54fb8fba 06a90fc8 0581bc70 00000101 python35!PyRun_FileExFlags+0x85
004cf8f8 54e8f1f7 06a90fc8 0581bc70 00000001 python35!PyRun_SimpleFileExFlags+0x20a
004cf924 54e8fb33 004cf954 71902100 71902108 python35!run_file+0xe7
004cf9c8 1cd4143f 00000002 05b46f08 05b4cf48 python35!Py_Main+0x913
004cfa14 75463744 7ecee000 75463720 fbb4cf67 python!__scrt_common_main_seh+0xff
004cfa28 76f0a064 7ecee000 949593e0 00000000 KERNEL32!BaseThreadInitThunk+0x24
004cfa70 76f0a02f ffffffff 76f2d7ec 00000000 ntdll!__RtlUserThreadStart+0x2f
004cfa80 00000000 1cd414f7 7ecee000 00000000 ntdll!_RtlUserThreadStart+0x1b


STACK_COMMAND:  .cxr 0x0 ; kb

FAULTING_SOURCE_LINE:  c:\build\cpython\objects\object.c

FAULTING_SOURCE_FILE:  c:\build\cpython\objects\object.c

FAULTING_SOURCE_LINE_NUMBER:  659

FAULTING_SOURCE_CODE:  
   655:     PyObject *res;
   656:     int checked_reverse_op = 0;
   657: 
   658:     if (v->ob_type != w->ob_type &&
>  659:         PyType_IsSubtype(w->ob_type, v->ob_type) &&
   660:         (f = w->ob_type->tp_richcompare) != NULL) {
   661:         checked_reverse_op = 1;
   662:         res = (*f)(w, v, _Py_SwappedOp[op]);
   663:         if (res != Py_NotImplemented)
   664:             return res;


SYMBOL_STACK_INDEX:  0

SYMBOL_NAME:  python35!do_richcompare+15

FOLLOWUP_NAME:  MachineOwner

MODULE_NAME: python35

IMAGE_NAME:  python35.dll

DEBUG_FLR_IMAGE_TIMESTAMP:  55c83105

FAILURE_BUCKET_ID:  INVALID_POINTER_READ_c0000005_python35.dll!do_richcompare

BUCKET_ID:  APPLICATION_FAULT_INVALID_POINTER_READ_python35!do_richcompare+15

ANALYSIS_SOURCE:  UM

FAILURE_ID_HASH_STRING:  um:invalid_pointer_read_c0000005_python35.dll!do_richcompare

FAILURE_ID_HASH:  {9d923c37-6c51-89af-91c6-b0039172374e}

Followup: MachineOwner
---------
msg249132 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2015-08-25 16:15
I guess that in the test case the stop parameter is set to 4 in
deque_index(), but it should be clamped to 3.
msg249181 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-08-26 06:19
Larry, this may need to go into 3.5 if there is still an opportunity.
msg249197 - (view) Author: Larry Hastings (larry) * (Python committer) Date: 2015-08-26 14:23
Please create a pull request at your earliest convenience.
msg249201 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2015-08-26 15:10
New changeset ae8ec66adc7f by Raymond Hettinger in branch '3.5':
Issue #24913: Fix overrun error in deque.index().
https://hg.python.org/cpython/rev/ae8ec66adc7f
msg249202 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-08-26 15:12
> Please create a pull request at your earliest convenience.

I'm not sure what that entails.  Can you just apply ae8ec66adc7f and take it from here?
msg249203 - (view) Author: Larry Hastings (larry) * (Python committer) Date: 2015-08-26 15:19
https://docs.python.org/devguide/devcycle.html#release-candidate-rc

https://mail.python.org/pipermail/python-dev/2015-August/141167.html
msg249570 - (view) Author: Larry Hastings (larry) * (Python committer) Date: 2015-09-02 20:50
Assigning to Brett, who has agreed to do the merge to 3.5.0 that Raymond has declined to do.
msg249594 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-09-03 02:39
Thanks Brett :-)
msg249678 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2015-09-03 17:27
PR created, Larry.
msg249684 - (view) Author: Larry Hastings (larry) * (Python committer) Date: 2015-09-03 20:00
Merged.  Please do a (null) merge forward into 3.5.1 and 3.6.  Thanks!
msg249700 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2015-09-03 22:36
New changeset 9f8c59e61594 by Brett Cannon in branch '3.5':
Issue #24913: Fix overrun error in deque.index().
https://hg.python.org/cpython/rev/9f8c59e61594

New changeset d093d87e449c by Brett Cannon in branch '3.5':
Merge from 3.5.0 for issue #24913
https://hg.python.org/cpython/rev/d093d87e449c

New changeset c6e0c29913ec by Brett Cannon in branch 'default':
Merge from 3.5 for issue #24913
https://hg.python.org/cpython/rev/c6e0c29913ec
msg249701 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2015-09-03 22:37
OK, that should cover 3.5.0 and then null merge through 3.5 and default. I thus consider my favour to Larry done and Raymond now owes me one.
History
Date User Action Args
2015-09-08 18:36:57Arfreversetnosy: + Arfrever
2015-09-03 22:37:15brett.cannonsetmessages: + msg249701
2015-09-03 22:36:01python-devsetmessages: + msg249700
2015-09-03 20:00:57larrysetstatus: open -> closed
resolution: fixed
messages: + msg249684
2015-09-03 17:27:08brett.cannonsetassignee: brett.cannon -> larry
messages: + msg249678
stage: resolved
2015-09-03 02:39:56rhettingersetmessages: + msg249594
2015-09-02 20:50:40larrysetassignee: larry -> brett.cannon

messages: + msg249570
nosy: + brett.cannon
2015-08-26 15:19:01larrysetmessages: + msg249203
2015-08-26 15:12:14rhettingersetmessages: + msg249202
2015-08-26 15:10:18python-devsetnosy: + python-dev
messages: + msg249201
2015-08-26 14:23:56larrysetpriority: high -> release blocker

messages: + msg249197
2015-08-26 08:52:02rhettingersetfiles: + fix_deque_overrun2.diff
2015-08-26 06:19:03rhettingersetpriority: low -> high

assignee: rhettinger -> larry

title: newblock() Uninitialized Variable -> deque.index() overruns deque boundary
nosy: + larry
versions: + Python 3.6
messages: + msg249181
2015-08-26 06:16:14rhettingersetfiles: + fix_deque_overrun.diff
2015-08-25 16:15:25skrahsetnosy: + skrah
messages: + msg249132
2015-08-25 15:54:54JohnLeitchsetmessages: + msg249130
2015-08-25 15:12:08rhettingersetpriority: normal -> low

messages: + msg249126
2015-08-25 15:05:21rhettingersetassignee: rhettinger
2015-08-23 22:52:46brycedarlingsetnosy: + brycedarling
2015-08-22 00:45:06r.david.murraysetnosy: + rhettinger
2015-08-21 23:10:29JohnLeitchsetfiles: + newblock_Uninitialized_variable.py
2015-08-21 23:09:06JohnLeitchcreate