Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use-after-free in dict/list #82769

Closed
LCatro mannequin opened this issue Oct 25, 2019 · 18 comments
Closed

Use-after-free in dict/list #82769

LCatro mannequin opened this issue Oct 25, 2019 · 18 comments
Labels
3.7 only security fixes 3.8 only security fixes 3.9 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) type-crash A hard crash of the interpreter, possibly with a core dump

Comments

@c106af3c-62ac-4166-a20a-6841b3ef7481
Copy link
Mannequin

LCatro mannequin commented Oct 25, 2019

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

    @c106af3c-62ac-4166-a20a-6841b3ef7481
    Copy link
    Mannequin Author

    LCatro mannequin commented Oct 25, 2019

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

    @c106af3c-62ac-4166-a20a-6841b3ef7481 LCatro mannequin added type-security A security issue 3.8 only security fixes labels Oct 25, 2019
    @serhiy-storchaka
    Copy link
    Member

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

    @serhiy-storchaka serhiy-storchaka added interpreter-core (Objects, Python, Grammar, and Parser dirs) 3.7 only security fixes 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
    @c106af3c-62ac-4166-a20a-6841b3ef7481
    Copy link
    Mannequin Author

    LCatro mannequin commented Oct 28, 2019

    Sure ,but how can i pull my fix code ?

    @methane
    Copy link
    Member

    methane commented Dec 30, 2019

    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
    Copy link
    Member

    methane commented Dec 30, 2019

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

    @pablogsal
    Copy link
    Member

    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
    Copy link
    Member

    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
    Copy link
    Member

    methane commented Dec 31, 2019

    $ ./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
    Copy link
    Member

    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
    Copy link
    Member

    This makes list comparison 2x slower.

    This is affected by PR 17734? or PyObject_RichCompare patched?

    @corona10
    Copy link
    Member

    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
    Copy link
    Member

    methane commented Dec 31, 2019

    > 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
    Copy link
    Member

    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
    Copy link
    Member

    Sorry, I meant that I reviewed PR 17766.

    @methane
    Copy link
    Member

    methane commented Dec 31, 2019

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

    @pablogsal
    Copy link
    Member

    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
    Copy link
    Member

    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
    Copy link
    Member

    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!

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    3.7 only security fixes 3.8 only security fixes 3.9 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) type-crash A hard crash of the interpreter, possibly with a core dump
    Projects
    None yet
    Development

    No branches or pull requests

    4 participants