Use-after-free in dict/list

@methane

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']

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

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

Sure ,but how can i pull my fix code ?

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;
    }

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

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

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

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

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?

This makes list comparison 2x slower.

This is affected by PR 17734? or PyObject_RichCompare patched?

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;
 }

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

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.

Sorry, I meant that I reviewed PR 17766.

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

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

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

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!

Navigation Menu

Repository navigation

Use-after-free in dict/list #82769

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Use-after-free in dict/list #82769

Description

Activity

LCatro commented on Oct 25, 2019

serhiy-storchaka commented on Oct 25, 2019

LCatro commented on Oct 28, 2019

methane commented on Dec 30, 2019

methane commented on Dec 30, 2019

pablogsal commented on Dec 31, 2019

pablogsal commented on Dec 31, 2019

methane commented on Dec 31, 2019

pablogsal commented on Dec 31, 2019

corona10 commented on Dec 31, 2019

corona10 commented on Dec 31, 2019

methane commented on Dec 31, 2019

pablogsal commented on Dec 31, 2019

pablogsal commented on Dec 31, 2019

methane commented on Dec 31, 2019

pablogsal commented on Dec 31, 2019

pablogsal commented on Dec 31, 2019

pablogsal commented on Dec 31, 2019

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions