[CVE-2022-48560] Use-after-free in heappushpop() of heapq module

[Dk0n9]

BPO	39421
Nosy	@vstinner, @ned-deily, @alex, @methane, @corona10, @pablogsal, @miss-islington, @Dk0n9
PRs	bpo-39421: Fix posible crash in heapq with custom comparison operators #18118 [3.8] bpo-39421: Fix posible crash in heapq with custom comparison operators (GH-18118) #18144 [3.7] bpo-39421: Fix posible crash in heapq with custom comparison operators (GH-18118) #18145 [3.6] bpo-39421: Fix posible crash in heapq with custom comparison operators (GH-18118) #18146 [3.8] bpo-39421: Fix posible crash in heapq with custom comparison operators (GH-18118) #18149

^{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 2020-01-23.15:23:27.929>
created_at = <Date 2020-01-22.15:11:46.489>
labels = ['extension-modules', '3.7', '3.8', '3.9', 'type-crash']
title = 'Use-after-free in heappushpop() of heapq module'
updated_at = <Date 2020-01-23.15:23:27.928>
user = 'https://github.com/Dk0n9'

bugs.python.org fields:

activity = <Date 2020-01-23.15:23:27.928>
actor = 'pablogsal'
assignee = 'none'
closed = True
closed_date = <Date 2020-01-23.15:23:27.929>
closer = 'pablogsal'
components = ['Extension Modules']
creation = <Date 2020-01-22.15:11:46.489>
creator = 'dk0n9'
dependencies = []
files = []
hgrepos = []
issue_num = 39421
keywords = ['patch', 'security_issue']
message_count = 10.0
messages = ['360474', '360475', '360477', '360478', '360479', '360484', '360557', '360558', '360561', '360564']
nosy_count = 8.0
nosy_names = ['vstinner', 'ned.deily', 'alex', 'methane', 'corona10', 'pablogsal', 'miss-islington', 'dk0n9']
pr_nums = ['18118', '18144', '18145', '18146', '18149']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue39421'
versions = ['Python 3.7', 'Python 3.8', 'Python 3.9']

[Dk0n9]

The variable heap in heappushpop does not add a reference count

    cmp = PyObject_RichCompareBool(PyList_GET_ITEM(heap, 0), item, Py_LT);
    if (cmp < 0)
        return NULL;
    if (cmp == 0) {
        Py_INCREF(item);
        return item;
    }

POC：

import heapq

class h(int):
    def __lt__(self, o):
        list1.clear()
        return NotImplemented

list1 = []

heapq.heappush(list1, h(0))
heapq.heappushpop(list1, 1)

Crash detail with asan:

==62141==ERROR: AddressSanitizer: heap-use-after-free on address 0x6060000fd778 at pc 0x00000049cdce bp 0x7ffe9690f650 sp 0x7ffe9690f640
READ of size 8 at 0x6060000fd778 thread T0
#0 0x49cdcd in long_richcompare Objects/longobject.c:3047
#1 0x4f9495 in do_richcompare Objects/object.c:802
#2 0x4f9495 in PyObject_RichCompare Objects/object.c:846
#3 0x4f9495 in PyObject_RichCompareBool Objects/object.c:868
#4 0x7ff74c523594 in _heapq_heappushpop_impl /home//Python-3.9.0a2/Modules/_heapqmodule.c:267
#5 0x7ff74c523594 in _heapq_heappushpop /home//Python-3.9.0a2/Modules/clinic/_heapqmodule.c.h:109
#6 0x854c30 in cfunction_vectorcall_FASTCALL Objects/methodobject.c:366
#7 0x443885 in _PyObject_VectorcallTstate Include/cpython/abstract.h:111
#8 0x443885 in _PyObject_Vectorcall Include/cpython/abstract.h:120
#9 0x443885 in call_function Python/ceval.c:4850
#10 0x443885 in _PyEval_EvalFrameDefault Python/ceval.c:3306
#11 0x5e1d76 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:43
#12 0x5e1d76 in _PyEval_EvalCode Python/ceval.c:4142
#13 0x5e2207 in _PyEval_EvalCodeWithName Python/ceval.c:4174
#14 0x5e2207 in PyEval_EvalCodeEx Python/ceval.c:4190
#15 0x5e2207 in PyEval_EvalCode Python/ceval.c:717
#16 0x6862fc in run_eval_code_obj Python/pythonrun.c:1125
#17 0x6862fc in run_mod Python/pythonrun.c:1147
#18 0x6862fc in PyRun_FileExFlags Python/pythonrun.c:1063
#19 0x6867b2 in PyRun_SimpleFileExFlags Python/pythonrun.c:428
#20 0x446495 in pymain_run_file Modules/main.c:369
#21 0x446495 in pymain_run_python Modules/main.c:553
#22 0x446495 in Py_RunMain Modules/main.c:632
#23 0x446f86 in pymain_main Modules/main.c:662
#24 0x446f86 in Py_BytesMain Modules/main.c:686
#25 0x7ff74f34882f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
#26 0x444478 in _start (/home/***/Python-3.9.0a2/python+0x444478)

0x6060000fd778 is located 24 bytes inside of 56-byte region [0x6060000fd760,0x6060000fd798)
freed by thread T0 here:
#0 0x7ff7500b72ca in __interceptor_free (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x982ca)
#1 0x52a5d9 in subtype_dealloc Objects/typeobject.c:1291
#2 0x4222a6 in _Py_DECREF Include/object.h:478
#3 0x4222a6 in frame_dealloc Objects/frameobject.c:636
#4 0x422088 in _Py_DECREF Include/object.h:478
#5 0x422088 in function_code_fastcall Objects/call.c:335
#6 0x53aac6 in _PyObject_VectorcallTstate Include/cpython/abstract.h:111
#7 0x53aac6 in vectorcall_unbound Objects/typeobject.c:1459
#8 0x53aac6 in slot_tp_richcompare Objects/typeobject.c:6703
#9 0x4f921d in do_richcompare Objects/object.c:796
#10 0x4f921d in PyObject_RichCompare Objects/object.c:846
#11 0x4f921d in PyObject_RichCompareBool Objects/object.c:868
#12 0x7ff74c523594 in _heapq_heappushpop_impl /home//Python-3.9.0a2/Modules/_heapqmodule.c:267
#13 0x7ff74c523594 in _heapq_heappushpop /home//Python-3.9.0a2/Modules/clinic/_heapqmodule.c.h:109
#14 0x854c30 in cfunction_vectorcall_FASTCALL Objects/methodobject.c:366
#15 0x443885 in _PyObject_VectorcallTstate Include/cpython/abstract.h:111
#16 0x443885 in _PyObject_Vectorcall Include/cpython/abstract.h:120
#17 0x443885 in call_function Python/ceval.c:4850
#18 0x443885 in _PyEval_EvalFrameDefault Python/ceval.c:3306
#19 0x5e1d76 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:43
#20 0x5e1d76 in _PyEval_EvalCode Python/ceval.c:4142
#21 0x5e2207 in _PyEval_EvalCodeWithName Python/ceval.c:4174
#22 0x5e2207 in PyEval_EvalCodeEx Python/ceval.c:4190
#23 0x5e2207 in PyEval_EvalCode Python/ceval.c:717
#24 0x6862fc in run_eval_code_obj Python/pythonrun.c:1125
#25 0x6862fc in run_mod Python/pythonrun.c:1147
#26 0x6862fc in PyRun_FileExFlags Python/pythonrun.c:1063
#27 0x6867b2 in PyRun_SimpleFileExFlags Python/pythonrun.c:428
#28 0x446495 in pymain_run_file Modules/main.c:369
#29 0x446495 in pymain_run_python Modules/main.c:553
#30 0x446495 in Py_RunMain Modules/main.c:632
#31 0x446f86 in pymain_main Modules/main.c:662
#32 0x446f86 in Py_BytesMain Modules/main.c:686
#33 0x7ff74f34882f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

previously allocated by thread T0 here:
#0 0x7ff7500b7602 in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x98602)
#1 0x6dbfd5 in _PyObject_GC_Alloc Modules/gcmodule.c:2146
#2 0x6dbfd5 in _PyObject_GC_Malloc Modules/gcmodule.c:2173
#3 0x527d20 in PyType_GenericAlloc Objects/typeobject.c:1014
#4 0x4b890b in long_subtype_new Objects/longobject.c:5132
#5 0x4b890b in long_new_impl Objects/longobject.c:5075
#6 0x4b890b in long_new Objects/clinic/longobject.c.h:36
#7 0x52f606 in type_call Objects/typeobject.c:973
#8 0x462b46 in _PyObject_MakeTpCall Objects/call.c:189
#9 0x436b70 in _PyObject_VectorcallTstate Include/cpython/abstract.h:109
#10 0x436b70 in _PyObject_Vectorcall Include/cpython/abstract.h:120
#11 0x436b70 in call_function Python/ceval.c:4850
#12 0x436b70 in _PyEval_EvalFrameDefault Python/ceval.c:3337
#13 0x5e1d76 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:43
#14 0x5e1d76 in _PyEval_EvalCode Python/ceval.c:4142
#15 0x5e2207 in _PyEval_EvalCodeWithName Python/ceval.c:4174
#16 0x5e2207 in PyEval_EvalCodeEx Python/ceval.c:4190
#17 0x5e2207 in PyEval_EvalCode Python/ceval.c:717
#18 0x6862fc in run_eval_code_obj Python/pythonrun.c:1125
#19 0x6862fc in run_mod Python/pythonrun.c:1147
#20 0x6862fc in PyRun_FileExFlags Python/pythonrun.c:1063
#21 0x6867b2 in PyRun_SimpleFileExFlags Python/pythonrun.c:428
#22 0x446495 in pymain_run_file Modules/main.c:369
#23 0x446495 in pymain_run_python Modules/main.c:553
#24 0x446495 in Py_RunMain Modules/main.c:632
#25 0x446f86 in pymain_main Modules/main.c:662
#26 0x446f86 in Py_BytesMain Modules/main.c:686
#27 0x7ff74f34882f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

SUMMARY: AddressSanitizer: heap-use-after-free Objects/longobject.c:3047 long_richcompare
Shadow bytes around the buggy address:
0x0c0c80017a90: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c0c80017aa0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c0c80017ab0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c0c80017ac0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c0c80017ad0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c0c80017ae0: fd fd fd fd fd fd fd fa fa fa fa fa fd fd fd[fd]
0x0c0c80017af0: fd fd fd fa fa fa fa fa fd fd fd fd fd fd fd fa
0x0c0c80017b00: fa fa fa fa fd fd fd fd fd fd fd fd fa fa fa fa
0x0c0c80017b10: 00 00 00 00 00 00 00 00 fa fa fa fa fd fd fd fd
0x0c0c80017b20: fd fd fd fa fa fa fa fa fd fd fd fd fd fd fd fa
0x0c0c80017b30: fa fa fa fa fd fd fd fd fd fd fd fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Heap right redzone: fb
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack partial redzone: f4
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
==62141==ABORTING

[corona10]

Reproducible.

It looks similar to bpo-38588.
We will apply the same solution as we did at bpo-38588?
or do we plan to apply the solution which is suggested on msg359023?

[pablogsal]

To be honest, given how many ways this bug happens I think its time to consider msg359023.

[corona10]

To be honest, given how many ways this bug happens I think its time to consider msg359023.

+1 to me also

[pablogsal]

AS this discussion will take a while and likely will have deeper consequences, in the meantime I created PR18118 to specifically fix this.