classification
Title: use after free in key sharing dict
Type: crash Stage: resolved
Components: Interpreter Core Versions: Python 3.7, Python 3.6, Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: inada.naoki Nosy List: Mark.Shannon, audric, benjamin.peterson, inada.naoki, rhettinger, serhiy.storchaka, tim.peters, vstinner, xiang.zhang
Priority: normal Keywords: 3.3regression, patch

Created on 2017-02-04 00:52 by audric, last changed 2017-10-23 17:48 by serhiy.storchaka. This issue is now closed.

Files
File name Uploaded Description Edit
minimal_crash.py audric, 2017-02-04 00:52 minimal code to reproduce
29438-sharedkey-useafterfree.patch inada.naoki, 2017-02-04 10:12 review
29438-minimum.py inada.naoki, 2017-02-04 18:56
29438-sharedkey-useafterfree-py35.patch inada.naoki, 2017-02-05 04:13 patch for python 3.5 review
29438-sharedkey-useafterfree-py36.patch inada.naoki, 2017-02-07 08:30 review
29438-sharedkey-useafterfree-py36-2.patch inada.naoki, 2017-02-08 06:20 review
29438-sharedkey-useafterfree-py35-2.patch inada.naoki, 2017-02-10 18:18 review
Pull Requests
URL Status Linked Edit
PR 17 inada.naoki, 2017-02-11 03:32
PR 703 larry, 2017-03-17 21:00
Messages (25)
msg286902 - (view) Author: Audric Schiltknecht (audric) Date: 2017-02-04 00:52
I've managed to create a minimal test file that causes python to crashe when run with python 3.6.0 (packaged in my distribution or from hg repository), 3.6 branch from hg repository and 3.7 branch from hg repository, but works fine on 3.5.3 and 3.5 branch.

It also does not crash when python is compiled with '--with-pydebug' option (3.6/3.7)

$ uname -a
Linux 4.8.13-1-ARCH #1 SMP PREEMPT Fri Dec 9 07:24:34 CET 2016 x86_64 GNU/Linux

$ python --version
Python 3.6.0

$ pip freeze
appdirs==1.4.0
packaging==16.8
pyparsing==2.1.10
python-dateutil==2.6.0
six==1.10.0
SQLAlchemy==1.1.5

To reproduce, use the attached file (minimal_crash.py):

$ virtualenv3  venv
$ source venv/bin/activate
$ pip install sqlalchemy

Run once to create DB and insert some stuff into it (no crash):
$ ./minimal_crash.py -d sqlite:///crash.db -v -c

Then re-run same thing WITHOUT re-creating the base:
$ ./minimal_crash.py -d sqlite:///crash.db -v
INFO:__main__:Connecting to DB 'sqlite:///crash.db'
Segmentation fault (core dumped)


Runing with GDB: https://gist.github.com/audricschiltknecht/5564034c5aac78d881e03f29e069a8f5
msg286904 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2017-02-04 03:40
I could reproduce this using Audric's command. And yes, debug build doesn't suffer from this crash. Nosy Victor.

DEBUG:root:Called with: ['/tmp/minimal_crash.py', '-d', 'sqlite:///crash.db', '-v']
INFO:__main__:Connecting to DB 'sqlite:///crash.db'
INFO:sqlalchemy.engine.base.Engine:SELECT CAST('test plain returns' AS VARCHAR(60)) AS anon_1
INFO:sqlalchemy.engine.base.Engine:()
INFO:sqlalchemy.engine.base.Engine:SELECT CAST('test unicode returns' AS VARCHAR(60)) AS anon_1
INFO:sqlalchemy.engine.base.Engine:()
INFO:sqlalchemy.engine.base.Engine:BEGIN (implicit)
INFO:sqlalchemy.engine.base.Engine:SELECT table_name.id AS table_name_id, table_name.att_1 AS table_name_att_1, table_name.att_2 AS table_name_att_2, table_name.att_3 AS table_name_att_3, table_name.date_1 AS table_name_date_1, table_name.date_2 AS table_name_date_2 
FROM table_name 
WHERE table_name.id = ? AND table_name.att_1 = ? AND table_name.att_2 = ? AND table_name.att_3 = ?
INFO:sqlalchemy.engine.base.Engine:('12345678912345', '123456789123456', 2, 4)
DEBUG:__main__:No item found, new item
DEBUG:__main__:Documents processed
INFO:sqlalchemy.engine.base.Engine:INSERT INTO table_name (id, att_1, att_2, att_3, date_1, date_2) VALUES (?, ?, ?, ?, ?, ?)
INFO:sqlalchemy.engine.base.Engine:('12345678912345', None, None, None, None, None)
INFO:sqlalchemy.engine.base.Engine:ROLLBACK

Program received signal SIGSEGV, Segmentation fault.
_PyObject_Alloc (ctx=0x0, elsize=296, nelem=1, use_calloc=0) at Objects/obmalloc.c:1258
1258	            if ((pool->freeblock = *(block **)bp) != NULL) {
(gdb) bt
#0  _PyObject_Alloc (ctx=0x0, elsize=296, nelem=1, use_calloc=0) at Objects/obmalloc.c:1258
#1  _PyObject_Malloc (ctx=0x0, nbytes=296) at Objects/obmalloc.c:1437
#2  0x000055555564082c in new_keys_object (size=<optimized out>) at Objects/dictobject.c:536
#3  dictresize (mp=mp@entry=0x7ffff7e36510, minsize=<optimized out>) at Objects/dictobject.c:1242
#4  0x000055555564456f in insertion_resize (mp=0x7ffff7e36510) at Objects/dictobject.c:1094
#5  insertdict (value=<optimized out>, hash=<optimized out>, key=<optimized out>, mp=<optimized out>) at Objects/dictobject.c:1142
#6  PyDict_SetItem (value=0x7ffff39f5d68, key=0x7ffff66f9260, op=0x7ffff7e36510) at Objects/dictobject.c:1564
#7  dict_ass_sub (mp=0x7ffff7e36510, v=0x7ffff66f9260, w=0x7ffff39f5d68) at Objects/dictobject.c:2148
#8  0x00005555555af8d4 in _PyEval_EvalFrameDefault (f=<optimized out>, throwflag=<optimized out>) at Python/ceval.c:1673
#9  0x00005555555ab211 in PyEval_EvalFrameEx (throwflag=0, f=0x7ffff3487da0) at Python/ceval.c:664
#10 _PyFunction_FastCall (co=<optimized out>, args=<optimized out>, nargs=2, globals=<optimized out>) at Python/ceval.c:4926
#11 0x00005555555b30ff in call_function (kwnames=0x0, oparg=<optimized out>, pp_stack=<synthetic pointer>) at Python/ceval.c:4868
#12 _PyEval_EvalFrameDefault (f=<optimized out>, throwflag=<optimized out>) at Python/ceval.c:3290
#13 0x00005555556e37b0 in PyEval_EvalFrameEx (throwflag=0, f=0x555555eb0ce8) at Python/ceval.c:664
#14 _PyEval_EvalCodeWithName (_co=0x7ffff7e34300, globals=<optimized out>, locals=locals@entry=0x0, args=<optimized out>, argcount=2, kwnames=0x7ffff7e360f0, kwargs=0x555555eaf210, kwcount=3, kwstep=1, 
    defs=0x0, defcount=0, kwdefs=0x7ffff7e36480, closure=0x0, name=0x7ffff7e30420, qualname=0x7ffff7e31f60) at Python/ceval.c:4165
#15 0x00005555556e395b in fast_function (func=<optimized out>, stack=<optimized out>, nargs=<optimized out>, kwnames=<optimized out>) at Python/ceval.c:4987
#16 0x00005555555b22a8 in call_function (kwnames=0x7ffff7e360d8, oparg=<optimized out>, pp_stack=<synthetic pointer>) at Python/ceval.c:4868
#17 _PyEval_EvalFrameDefault (f=<optimized out>, throwflag=<optimized out>) at Python/ceval.c:3336

...
msg286925 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-04 07:48
valgrind output is here.
https://gist.github.com/methane/3c010daba71a374fd0b6a41a0d98e3ff

It seems another bug relating to key-sharing dict...
msg286927 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-04 08:03
4385             int was_shared = cached == ((PyDictObject *)dict)->ma_keys;         
4386             res = PyDict_SetItem(dict, key, value);                             
4387             if (was_shared && cached != ((PyDictObject *)dict)->ma_keys) {      
4388                 /* PyDict_SetItem() may call dictresize and convert split table 
...
4401                  */                                                             
4402                 if (cached->dk_refcnt == 1) {                                   
4403                     CACHED_KEYS(tp) = make_keys_shared(dict);                   
4404                 }                                                               
4405                 else {                                                          
4406                     CACHED_KEYS(tp) = NULL;                                     
4407                 }

L4402 accessed free `cached` object.
At PyDict_SetItem() in L4386, some callback is called through weakref callback,
and the callback inserts something into this dict.  shared key object (cached) is freed.

So right way to fix it may be DK_INCREF() before PyDict_SetItem().
msg286937 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-02-04 09:23
You may try to reproduce with a release build and PYTHONMALLOC=debug
to check for buffer over/underflow.
msg286949 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-04 10:12
This is use after free, not overflow.
This patch is based on Python 3.6, but I think 3.5 has same issue.
I'll check it.
msg286951 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-04 10:15
(PYTHONMALLOC=malloc valgrind find it soon. :)
msg286966 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-02-04 14:43
Please update the issue title.
msg286981 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-04 18:56
I can reproduce it on Python 3.5 with attached script.
I think this bug is from Python 3.3, since key-sharing dict is implemented.

"Trigger key sharing dict resize while callbacks (weakref or __del__) called from setitem" is step to reproduce.
It's not easy to exploit because external input (JSON, form, etc) doesn't use key-sharing dict.

Should I fix it for 3.3~ (security fix only) or 3.5~ (bugfix)?
msg286982 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-02-04 19:04
Is it related to issue27945?
msg286983 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-04 19:15
It's similar to issue27945, but different.

I confirmed this issue is in 3.4 too.
https://github.com/python/cpython/blob/3.4/Objects/dictobject.c#L3798

    // _PyObjectDict_SetItem()
    if ((tp->tp_flags & Py_TPFLAGS_HEAPTYPE) && (cached = CACHED_KEYS(tp))) {
    ...
            res = PyDict_DelItem(dict, key);  // <- may run arbitrary code.  CACHED_KEYS(tp) can be changed and cached can be freed here.
            if (cached != ((PyDictObject *)dict)->ma_keys) {
                CACHED_KEYS(tp) = NULL;
                DK_DECREF(cached);  // !!!
            }
        } else {
            res = PyDict_SetItem(dict, key, value); // Same to DelItem().
            if (cached != ((PyDictObject *)dict)->ma_keys) {
                /* Either update tp->ht_cached_keys or delete it */
                if (cached->dk_refcnt == 1) { // !!!
msg287255 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-02-07 20:00
PyDict_SetItem() can trigger destructor which first call _PyObjectDict_SetItem() which change CACHED_KEYS(tp) and then call PyDict_SetItem() which call dictresize(). At the end it may be possible that cached != ((PyDictObject *)dict)->ma_keys and cached != CACHED_KEYS(tp) and CACHED_KEYS(tp) != ((PyDictObject *)dict)->ma_keys.

Wouldn't be better to just update the cached variable after calling PyDict_SetItem()?

    if (was_shared && (cached = CACHED_KEYS(tp)) != NULL && cached != ((PyDictObject *)dict)->ma_keys)
msg287274 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2017-02-08 04:14
> if (was_shared && (cached = CACHED_KEYS(tp)) != NULL && cached != ((PyDictObject *)dict)->ma_keys)

+1 on this and I think the deletion should also use

if ((cached = CACHED_KEYS(tp) != NULL)
msg287280 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2017-02-08 06:26
I left one review about the comment on Rietvied last patch. :-)
msg287281 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-02-08 07:22
Could you please write tests Inada? It would be nice to test also the case that fails with 29438-sharedkey-useafterfree-py36.patch. Actually I don't know if this is easy to reproduce, it was just my guessing.
msg287282 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-08 07:41
to: Serhiy

I can reproduce the issue by 29438-minimum.py, on Python 3.7 with pydebug.
But since this issue is "use after free", it may and may not crash.
It's up to how freed memory block is used from another part of Python.
Deterministic test which doesn't tied specific python version is difficult.
msg287285 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-02-08 08:42
Okay, if there is no way to test this with certainty, tests may be omitted.

Why res == 0 is added? If PyDict_SetItem() triggers recursive calling of _PyObjectDict_SetItem() which calls PyDict_SetItem() it may be possible that the first PyDict_SetItem() is failed while the dict is changed by the second PyDict_SetItem() and CACHED_KEYS(tp) becomes outdated.
msg287286 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-08 08:55
> Why res == 0 is added? If PyDict_SetItem() triggers recursive calling of _PyObjectDict_SetItem() which calls PyDict_SetItem() it may be possible that the first PyDict_SetItem() is failed while the dict is changed by the second PyDict_SetItem() and CACHED_KEYS(tp) becomes outdated.

To avoid hiding error raised in PyDict_SetItem().
But it seems I was too nervous.  The error will be hidden only when make_keys_shared() raise exception.
I'll remove the check.

BTW, how about -py35.patch?  It is minimum patch to avoid "use after free".  It skip 
CACHED_KEYS(tp) = NULL entirely.  But I think I can apply same patch to Python 3.5 too.
msg287288 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-02-08 09:03
I think same patch should be applied to Python 3.5 too.
msg287564 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-10 18:18
Since Python 3.5's key sharing dict allows deletion, py35-2.patch is slightly different from py36-2.patch.

Since dictresize won't happen in normal (no weakref/__del__ callback)  deletion,
I removed `CACHED_KEYS(tp) = NULL` entirely.
msg287565 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-10 18:19
I'll send PR to github.  Please continue there.
msg287733 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-14 03:48
All pull requests are merged.
https://github.com/python/cpython/pull/17 (master)
https://github.com/python/cpython/pull/39 (3.6)
https://github.com/python/cpython/pull/40 (3.5)
msg290438 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-03-25 00:21
New changeset 89ddffbe9dcb38b79f99563b0d4d594d1105a192 by INADA Naoki in branch '3.6':
bpo-29438: fixed use-after-free in key sharing dict (#39)
https://github.com/python/cpython/commit/89ddffbe9dcb38b79f99563b0d4d594d1105a192
msg290439 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-03-25 00:21
New changeset 06a4fcb2458c5904968b5c8fe6b64940ba83a50d by INADA Naoki in branch '3.5':
bpo-29438: Fixed use-after-free in key sharing dict (#40)
https://github.com/python/cpython/commit/06a4fcb2458c5904968b5c8fe6b64940ba83a50d
msg290452 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-03-25 00:33
New changeset 2294f3aee14a6074b17c67ef936c607430bb3c7a by INADA Naoki in branch 'master':
bpo-29438: fixed use-after-free in key sharing dict (#17)
https://github.com/python/cpython/commit/2294f3aee14a6074b17c67ef936c607430bb3c7a
History
Date User Action Args
2017-10-23 17:48:04serhiy.storchakasetpull_requests: - pull_request960
2017-03-31 16:36:22dstufftsetpull_requests: + pull_request960
2017-03-25 00:33:14inada.naokisetmessages: + msg290452
2017-03-25 00:21:22inada.naokisetmessages: + msg290439
2017-03-25 00:21:01inada.naokisetmessages: + msg290438
2017-03-17 21:00:36larrysetpull_requests: + pull_request621
2017-02-14 03:48:22inada.naokisetstatus: open -> closed
resolution: fixed
messages: + msg287733

stage: patch review -> resolved
2017-02-11 03:32:45inada.naokisetpull_requests: + pull_request30
2017-02-10 18:19:32inada.naokisetmessages: + msg287565
2017-02-10 18:18:19inada.naokisetfiles: + 29438-sharedkey-useafterfree-py35-2.patch

messages: + msg287564
2017-02-08 09:05:50serhiy.storchakasetnosy: + tim.peters, rhettinger, benjamin.peterson, Mark.Shannon

versions: + Python 3.5
2017-02-08 09:03:04serhiy.storchakasetmessages: + msg287288
2017-02-08 08:55:08inada.naokisetmessages: + msg287286
2017-02-08 08:42:35serhiy.storchakasetassignee: inada.naoki
messages: + msg287285
2017-02-08 07:41:35inada.naokisetmessages: + msg287282
2017-02-08 07:22:40serhiy.storchakasetmessages: + msg287281
2017-02-08 06:26:18xiang.zhangsetmessages: + msg287280
2017-02-08 06:20:58inada.naokisetfiles: + 29438-sharedkey-useafterfree-py36-2.patch
2017-02-08 04:14:06xiang.zhangsetmessages: + msg287274
2017-02-07 20:00:51serhiy.storchakasetmessages: + msg287255
2017-02-07 19:37:32serhiy.storchakasetcomponents: + Interpreter Core
stage: patch review
2017-02-07 08:30:38inada.naokisetfiles: + 29438-sharedkey-useafterfree-py36.patch
2017-02-05 04:13:21inada.naokisetfiles: + 29438-sharedkey-useafterfree-py35.patch
keywords: + patch
2017-02-04 19:15:48inada.naokisetmessages: + msg286983
2017-02-04 19:04:57serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg286982
2017-02-04 18:56:09inada.naokisetkeywords: + 3.3regression, - patch, 3.6regression
files: + 29438-minimum.py
messages: + msg286981

title: SIGSEGV in PyObject_Malloc on python 3.6 and 3.7 -> use after free in key sharing dict
2017-02-04 16:45:40ned.deilysetkeywords: + patch
2017-02-04 16:45:06ned.deilysetkeywords: + 3.6regression, - patch
2017-02-04 14:43:49vstinnersetmessages: + msg286966
2017-02-04 10:15:04inada.naokisetmessages: + msg286951
2017-02-04 10:12:05inada.naokisetfiles: + 29438-sharedkey-useafterfree.patch
keywords: + patch
messages: + msg286949
2017-02-04 09:23:46vstinnersetmessages: + msg286937
2017-02-04 08:03:21inada.naokisetmessages: + msg286927
2017-02-04 07:48:21inada.naokisetnosy: + inada.naoki
messages: + msg286925
2017-02-04 03:40:54xiang.zhangsetnosy: + vstinner, xiang.zhang
messages: + msg286904
2017-02-04 00:52:56audriccreate