Issue 29438: use after free in key sharing dict

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

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

...

valgrind output is here.
https://gist.github.com/methane/3c010daba71a374fd0b6a41a0d98e3ff

It seems another bug relating to key-sharing dict...

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().

You may try to reproduce with a release build and PYTHONMALLOC=debug
to check for buffer over/underflow.

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.

(PYTHONMALLOC=malloc valgrind find it soon. :)

Please update the issue title.

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)?

Is it related to issue27945?

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) { // !!!

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)

> 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)

I left one review about the comment on Rietvied last patch. :-)

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.

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.

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.

> 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.

I think same patch should be applied to Python 3.5 too.

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.

I'll send PR to github.  Please continue there.

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)

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

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

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

stage: patch review -> resolved

messages: + msg287564

versions: + Python 3.5

title: SIGSEGV in PyObject_Malloc on python 3.6 and 3.7 -> use after free in key sharing dict