Issue 38588: Use-after-free in dict/list

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 2d5bf568eaa5059402ccce9ba5a366986ba27c8a by Pablo Galindo (Dong-hee Na) in branch 'master':
bpo-38588: Fix possible crashes in dict and list when calling PyObject_RichCompareBool (GH-17734)
https://github.com/python/cpython/commit/2d5bf568eaa5059402ccce9ba5a366986ba27c8a

> 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 dfef986f12dd92bd6434117bba0db3cbb4e65243 by Inada Naoki in branch 'master':
bpo-38588: Optimize list comparison. (GH-17766)
https://github.com/python/cpython/commit/dfef986f12dd92bd6434117bba0db3cbb4e65243

New changeset 53f11ba7b1498133ce3ff8173d5ae2e0182a3603 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)
https://github.com/python/cpython/commit/53f11ba7b1498133ce3ff8173d5ae2e0182a3603

New changeset 2ee87913dde038436a25f1db13ee3fddd2bcc983 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)
https://github.com/python/cpython/commit/2ee87913dde038436a25f1db13ee3fddd2bcc983

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!

stage: patch review -> resolved