classification
Title: Use-after-free in dict/list
Type: crash Stage: resolved
Components: Interpreter Core Versions: Python 3.9, Python 3.8, Python 3.7, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: LCatro, corona10, inada.naoki, pablogsal, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2019-10-25 13:25 by LCatro, last changed 2019-12-31 04:16 by pablogsal. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 17734 merged corona10, 2019-12-29 10:15
PR 17764 merged corona10, 2019-12-31 01:14
PR 17765 merged corona10, 2019-12-31 01:18
PR 17766 merged inada.naoki, 2019-12-31 01:31
Messages (18)
msg355366 - (view) Author: (LCatro) Date: 2019-10-25 13:25
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) {
msg355367 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2019-10-25 13:29
Thank you for your investigation LCatro! Do you mind to create a pull request?
msg355514 - (view) Author: (LCatro) Date: 2019-10-28 05:50
Sure ,but how can i pull my fix code ?
msg359023 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-12-30 07:33
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;
    }
msg359025 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-12-30 08:02
If we can not add INCREF and DECREF in the PyObject_RichCompare, we can add v == w check in the caller side.
msg359076 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2019-12-31 01:04
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
msg359077 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2019-12-31 01:17
> 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
msg359078 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-12-31 01:19
$ ./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.
msg359079 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2019-12-31 01:21
> 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?
msg359080 - (view) Author: Dong-hee Na (corona10) * (Python committer) Date: 2019-12-31 01:21
> This makes list comparison 2x slower.

This is affected by PR 17734? or PyObject_RichCompare patched?
msg359082 - (view) Author: Dong-hee Na (corona10) * (Python committer) Date: 2019-12-31 01:37
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;
 }
msg359083 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-12-31 01:43
>> 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.
msg359087 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2019-12-31 01:47
> 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.
msg359088 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2019-12-31 01:48
Sorry, I meant that I reviewed PR 17766.
msg359090 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-12-31 01:58
New changeset dfef986f12dd92bd6434117bba0db3cbb4e65243 by Inada Naoki in branch 'master':
bpo-38588: Optimize list comparison. (GH-17766)
https://github.com/python/cpython/commit/dfef986f12dd92bd6434117bba0db3cbb4e65243
msg359094 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2019-12-31 04:15
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
msg359095 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2019-12-31 04:15
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
msg359096 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2019-12-31 04:16
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!
History
Date User Action Args
2019-12-31 04:16:45pablogsalsetstatus: open -> closed
resolution: fixed
messages: + msg359096

stage: patch review -> resolved
2019-12-31 04:15:40pablogsalsetmessages: + msg359095
2019-12-31 04:15:13pablogsalsetmessages: + msg359094
2019-12-31 01:58:40inada.naokisetmessages: + msg359090
2019-12-31 01:48:07pablogsalsetmessages: + msg359088
2019-12-31 01:47:35pablogsalsetmessages: + msg359087
2019-12-31 01:43:00inada.naokisetmessages: + msg359083
2019-12-31 01:37:29corona10setmessages: + msg359082
2019-12-31 01:31:24inada.naokisetpull_requests: + pull_request17202
2019-12-31 01:21:33corona10setnosy: + corona10
messages: + msg359080
2019-12-31 01:21:09pablogsalsetmessages: + msg359079
2019-12-31 01:19:09inada.naokisetmessages: + msg359078
2019-12-31 01:18:08corona10setpull_requests: + pull_request17201
2019-12-31 01:17:48pablogsalsetmessages: + msg359077
2019-12-31 01:14:32corona10setpull_requests: + pull_request17200
2019-12-31 01:04:29pablogsalsetnosy: + pablogsal
messages: + msg359076
2019-12-30 08:02:59inada.naokisetmessages: + msg359025
2019-12-30 07:33:20inada.naokisetnosy: + inada.naoki
messages: + msg359023
2019-12-29 10:15:06corona10setkeywords: + patch
stage: patch review
pull_requests: + pull_request17179
2019-10-28 05:50:36LCatrosetmessages: + msg355514
2019-10-25 13:29:51serhiy.storchakasettype: security -> crash
messages: + msg355367
components: + Interpreter Core
versions: + Python 2.7, Python 3.7, Python 3.9
2019-10-25 13:25:50LCatrocreate