Use-after-free in dict/list #82769

LCatro · 2019-10-25T13:25:51Z

BPO	38588
Nosy	@methane, @serhiy-storchaka, @corona10, @pablogsal
PRs	bpo-38588: Fix possible crashes in dict and list when calling PyObject_RichCompareBool #17734 [3.8] bpo-38588: Fix possible crashes in dict and list when calling P… #17764 [3.7] bpo-38588: Fix possible crashes in dict and list when calling P… #17765 bpo-38588: Optimize list comparison. #17766

^{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 = None
closed_at = <Date 2019-12-31.04:16:45.105>
created_at = <Date 2019-10-25.13:25:50.889>
labels = ['interpreter-core', '3.7', '3.8', '3.9', 'type-crash']
title = 'Use-after-free in dict/list'
updated_at = <Date 2019-12-31.04:16:45.104>
user = 'https://bugs.python.org/LCatro'

bugs.python.org fields:

activity = <Date 2019-12-31.04:16:45.104>
actor = 'pablogsal'
assignee = 'none'
closed = True
closed_date = <Date 2019-12-31.04:16:45.105>
closer = 'pablogsal'
components = ['Interpreter Core']
creation = <Date 2019-10-25.13:25:50.889>
creator = 'LCatro'
dependencies = []
files = []
hgrepos = []
issue_num = 38588
keywords = ['patch']
message_count = 18.0
messages = ['355366', '355367', '355514', '359023', '359025', '359076', '359077', '359078', '359079', '359080', '359082', '359083', '359087', '359088', '359090', '359094', '359095', '359096']
nosy_count = 5.0
nosy_names = ['methane', 'serhiy.storchaka', 'LCatro', 'corona10', 'pablogsal']
pr_nums = ['17734', '17764', '17765', '17766']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue38588'
versions = ['Python 2.7', 'Python 3.7', 'Python 3.8', 'Python 3.9']

LCatro · 2019-10-25T13:25:51Z

Code :

The varanit bval forget call Py_INCREF to add reference in dict_equal()

    b->ma_keys->dk_lookup(b, key, ep->me_hash, &bval);  <--- ...
    if (bval == NULL) {
        Py_DECREF(key);
        Py_DECREF(aval);
        if (PyErr_Occurred())
            return -1;
        return 0;
    }
    cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);

PoC 1 :

class poc() :
    def __eq__(self,other) :
        dict2.clear()
        return NotImplemented

dict1 = {0:poc()}
dict2 = {0:set()}
dict1 == dict2   ##  dict_equal() -> PyObject_RichCompareBool

Crash Detail :

(gdb) run ../python_poc_info/dict_poc_1.py
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/fuzzing/Desktop/Python-3.8.0/python ../python_poc_info/dict_poc_1.py
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x000000000046e445 in do_richcompare (v=v@entry=0x7ffff7e767d0, w=w@entry=0x7ffff6dd88c0, op=op@entry=2)
at Objects/object.c:725
725 if (!checked_reverse_op && (f = w->ob_type->tp_richcompare) != NULL) {

======

Code :

The varanit wl->ob_item[i] forget call Py_INCREF to add reference in list_richcompare()

    for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {
        int k = PyObject_RichCompareBool(vl->ob_item[i],
                                         wl->ob_item[i], Py_EQ);  <

PoC 2 :

class poc() :
    def __eq__(self,other) :
        list1.clear()
        return NotImplemented


list1 = [poc()]
list2 = [1]
list1 == list2  #  list_richcompare() -> PyObject_RichCompareBool

Crash Detail :

(gdb) run ../python_poc_info/list_poc_1.py
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/fuzzing/Desktop/Python-3.8.0/python ../python_poc_info/list_poc_1.py
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x000000000044bd07 in long_richcompare (self=0x961200 <small_ints+192>, other=0x7ffff7e767d0, op=2)
at Objects/longobject.c:3083
3083 CHECK_BINOP(self, other);

======

Code :

The varanit PyList_GET_ITEM(a, i) forget call Py_INCREF to add reference in list_contains()

list_contains(PyListObject *a, PyObject *el)
{
    Py_ssize_t i;
    int cmp;

for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
    cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
                                       Py_EQ);   <\----

PoC 3 :

class poc() :
    def __eq__(self,other) :
        list1.clear()
        return NotImplemented

list1 = [ set() ]
poc() in list1  #  list_contains() -> PyObject_RichCompareBool

Crash Detail :

(gdb) run ../python_poc_info/list_poc_2.py
Starting program: /home/fuzzing/Desktop/Python-3.8.0/python ../python_poc_info/list_poc_2.py
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x000000000046e445 in do_richcompare (v=v@entry=0x7ffff7e766e0, w=w@entry=0x7ffff6dd88c0, op=op@entry=2)
at Objects/object.c:725
725 if (!checked_reverse_op && (f = w->ob_type->tp_richcompare) != NULL) {

serhiy-storchaka · 2019-10-25T13:29:52Z

Thank you for your investigation LCatro! Do you mind to create a pull request?

LCatro · 2019-10-28T05:50:36Z

Sure ,but how can i pull my fix code ?

methane · 2019-12-30T07:33:20Z

Would you benchmark the performance?

How about calling Py_INCREF and Py_DECREF in PyObject_RichCompare or do_richcompare?

It is safer than checking all caller of the PyObject_RichCompare and PyObject_RichCompareBool.
And it would be faster when PyObject_RichCompareBool is called with v == w and op == Py_EQ.

    /* Quick result when objects are the same.
       Guarantees that identity implies equality. */
    if (v == w) {
        if (op == Py_EQ)
            return 1;
        else if (op == Py_NE)
            return 0;
    }

methane · 2019-12-30T08:03:00Z

If we can not add INCREF and DECREF in the PyObject_RichCompare, we can add v == w check in the caller side.

pablogsal · 2019-12-31T01:04:29Z

New changeset 2d5bf56 by Pablo Galindo (Dong-hee Na) in branch 'master':
bpo-38588: Fix possible crashes in dict and list when calling PyObject_RichCompareBool (GH-17734)
2d5bf56

pablogsal · 2019-12-31T01:17:49Z

How about calling Py_INCREF and Py_DECREF in PyObject_RichCompare or do_richcompare?

Apologies, I had missed this suggestion before merging the PR :(

If we decide to add the check to PyObject_RichCompare or do_richcompare we should also adapt the fix for https://bugs.python.org/issue38610

methane · 2019-12-31T01:19:09Z

$ ./python -m pyperf timeit -s 'a = ["a"]*100; b = ["a"]*100;' -- 'a == b'

master : Mean +- std dev: 276 ns +- 1 ns
patched: Mean +- std dev: 572 ns +- 3 ns

This makes list comparison 2x slower.

pablogsal · 2019-12-31T01:21:09Z

This makes list comparison 2x slower.

Would you like to revert PR 17734? Calling Py_INCREF and Py_DECREF in PyObject_RichCompare or do_richcompare will take the same effect, no?

corona10 · 2019-12-31T01:21:34Z

This makes list comparison 2x slower.

This is affected by PR 17734? or PyObject_RichCompare patched?

corona10 · 2019-12-31T01:37:30Z

Master
Mean +- std dev: 1.08 us +- 0.02 us

Before PR-17734
Mean +- std dev: 584 ns +- 12 ns

New suggested
.....................
Mean +- std dev: 578 ns +- 14 ns

diff --git a/Objects/object.c b/Objects/object.c
index 6fc1146..b42f41a 100644
--- a/Objects/object.c
+++ b/Objects/object.c
@@ -865,6 +865,8 @@ PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
             return 0;
     }

+    Py_INCREF(v);
+    Py_INCREF(w);
     res = PyObject_RichCompare(v, w, op);
     if (res == NULL)
         return -1;
@@ -873,6 +875,8 @@ PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
     else
         ok = PyObject_IsTrue(res);
     Py_DECREF(res);
+    Py_DECREF(v);
+    Py_DECREF(w);
     return ok;
 }

methane · 2019-12-31T01:43:01Z

> This makes list comparison 2x slower.

This is affected by PR 17734? or PyObject_RichCompare patched?

Caused by PR 17734.

Would you like to revert PR 17734? Calling Py_INCREF and Py_DECREF in PyObject_RichCompare or do_richcompare will take the same effect, no?

Moving INCREF and DECREF is a huge change. It is just a future idea to prevent same type of bugs. I think it can not be backported.

To fix this issue with minimum performance regression, I think PR 17766 is the best solution. So no need to revert PR 17734.

pablogsal · 2019-12-31T01:47:35Z

Moving INCREF and DECREF is a huge change. It is just a future idea to prevent same type of bugs. I think it can not be backported.

Now I am wondering how many other APIs are affected by the same pattern other than PyObject_RichCompareBool....

To fix this issue with minimum performance regression, I think PR 17766 is the best solution. So no need to revert PR 17734.

Thanks for the quick fix and the analysis. I reviewed PR 17734.

pablogsal · 2019-12-31T01:48:08Z

Sorry, I meant that I reviewed PR 17766.

methane · 2019-12-31T01:58:40Z

New changeset dfef986 by Inada Naoki in branch 'master':
bpo-38588: Optimize list comparison. (GH-17766)
dfef986

pablogsal · 2019-12-31T04:15:14Z

New changeset 53f11ba by Pablo Galindo (Dong-hee Na) in branch '3.7':
[3.7] bpo-38588: Fix possible crashes in dict and list when calling P… (GH-17765)
53f11ba

pablogsal · 2019-12-31T04:15:40Z

New changeset 2ee8791 by Pablo Galindo (Dong-hee Na) in branch '3.8':
[3.8] bpo-38588: Fix possible crashes in dict and list when calling P… (GH-17764)
2ee8791

pablogsal · 2019-12-31T04:16:45Z

Closing this for now, let's open another issue if we plan to discuss calling Py_INCREF and Py_DECREF in PyObject_RichCompare or do_richcompare in the future.

Thanks to everyone involved!

LCatro mannequin added type-security A security issue 3.8 only security fixes labels Oct 25, 2019

serhiy-storchaka added interpreter-core (Objects, Python, Grammar, and Parser dirs) 3.7 (EOL) end of life 3.9 only security fixes type-crash A hard crash of the interpreter, possibly with a core dump and removed type-security A security issue labels Oct 25, 2019

pablogsal closed this as completed Dec 31, 2019

ezio-melotti transferred this issue from another repository Apr 10, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Use-after-free in dict/list #82769

Use-after-free in dict/list #82769

LCatro mannequin commented Oct 25, 2019

LCatro mannequin commented Oct 25, 2019

serhiy-storchaka commented Oct 25, 2019

LCatro mannequin commented Oct 28, 2019

methane commented Dec 30, 2019

methane commented Dec 30, 2019

pablogsal commented Dec 31, 2019

pablogsal commented Dec 31, 2019

methane commented Dec 31, 2019

pablogsal commented Dec 31, 2019

corona10 commented Dec 31, 2019

corona10 commented Dec 31, 2019

methane commented Dec 31, 2019

pablogsal commented Dec 31, 2019

pablogsal commented Dec 31, 2019

methane commented Dec 31, 2019

pablogsal commented Dec 31, 2019

pablogsal commented Dec 31, 2019

pablogsal commented Dec 31, 2019

Use-after-free in dict/list #82769

Use-after-free in dict/list #82769

Comments

LCatro mannequin commented Oct 25, 2019

LCatro mannequin commented Oct 25, 2019

serhiy-storchaka commented Oct 25, 2019

LCatro mannequin commented Oct 28, 2019

methane commented Dec 30, 2019

methane commented Dec 30, 2019

pablogsal commented Dec 31, 2019

pablogsal commented Dec 31, 2019

methane commented Dec 31, 2019

pablogsal commented Dec 31, 2019

corona10 commented Dec 31, 2019

corona10 commented Dec 31, 2019

methane commented Dec 31, 2019

pablogsal commented Dec 31, 2019

pablogsal commented Dec 31, 2019

methane commented Dec 31, 2019

pablogsal commented Dec 31, 2019

pablogsal commented Dec 31, 2019

pablogsal commented Dec 31, 2019