use after free in key sharing dict

[audric]

BPO	29438
Nosy	@tim-one, @rhettinger, @vstinner, @benjaminp, @methane, @markshannon, @serhiy-storchaka, @zhangyangyu
PRs	bpo-29438: fixed use-after-free in key sharing dict #17 [Do Not Merge] Sample of CPython life with blurb. #703
Files	minimal_crash.py: minimal code to reproduce 29438-sharedkey-useafterfree.patch 29438-minimum.py 29438-sharedkey-useafterfree-py35.patch: patch for python 3.5 29438-sharedkey-useafterfree-py36.patch 29438-sharedkey-useafterfree-py36-2.patch 29438-sharedkey-useafterfree-py35-2.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/methane'
closed_at = <Date 2017-02-14.03:48:22.343>
created_at = <Date 2017-02-04.00:52:56.670>
labels = ['interpreter-core', '3.7', 'type-crash']
title = 'use after free in key sharing dict'
updated_at = <Date 2017-10-23.17:48:04.376>
user = 'https://bugs.python.org/audric'

bugs.python.org fields:

activity = <Date 2017-10-23.17:48:04.376>
actor = 'serhiy.storchaka'
assignee = 'methane'
closed = True
closed_date = <Date 2017-02-14.03:48:22.343>
closer = 'methane'
components = ['Interpreter Core']
creation = <Date 2017-02-04.00:52:56.670>
creator = 'audric'
dependencies = []
files = ['46505', '46514', '46519', '46521', '46556', '46572', '46626']
hgrepos = []
issue_num = 29438
keywords = ['patch', '3.3regression']
message_count = 25.0
messages = ['286902', '286904', '286925', '286927', '286937', '286949', '286951', '286966', '286981', '286982', '286983', '287255', '287274', '287280', '287281', '287282', '287285', '287286', '287288', '287564', '287565', '287733', '290438', '290439', '290452']
nosy_count = 9.0
nosy_names = ['tim.peters', 'rhettinger', 'vstinner', 'benjamin.peterson', 'methane', 'Mark.Shannon', 'serhiy.storchaka', 'xiang.zhang', 'audric']
pr_nums = ['17', '703']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue29438'
versions = ['Python 3.5', 'Python 3.6', 'Python 3.7']

[audric]

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

[zhangyangyu]

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

...

[methane]

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

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

[methane]

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

[vstinner]

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

[methane]

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.

[methane]

(PYTHONMALLOC=malloc valgrind find it soon. :)

[vstinner]

Please update the issue title.

[methane]

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

[serhiy-storchaka]

Is it related to bpo-27945?

[methane]

It's similar to bpo-27945, 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) { // !!!