python / python/cpython

Use-after-free in several `OrderedDict` operations via re-entrant `__eq__`

Đang mở
#142,637 1 bình luận 0 reaction 0 người được giao Xem trên GitHub

Chưa có ai nhận issue này.

extension-modules type-crash
Ngôn ngữ chính
Python
Star
77.2k
Fork
35.9k
Chỉ số pull request đang chờ

Mô tả

What happened?

OrderedDict.__delitem__ (PyObject_DelItem) locates key using hash/equality. A re-entrant __eq__ that calls od.clear() during lookup frees/reshapes the table (ma_keys/od_fast_nodes) while _odict_clear_node() continues using stale pointers, causing a heap-use-after-free in _odict_get_index_raw.

The same bug also is also shown in other OrderedDict operations, like pop and move_to_end.

Proof of Concept:

from collections import OrderedDict

class Original:
    def __hash__(self):
        return 1

class Trigger:
    def __hash__(self):
        return 1
    def __eq__(self, other):
        od.clear()
        return True

od = OrderedDict()
od[Original()] = None
del od[Trigger()]

from collections import OrderedDict

class Original:
    def __init__(self):
        pass

    def __hash__(self):
        return 1

class Trigger:
    def __hash__(self):
        return 1

    def __eq__(self, other):
        # re-entrant mutation while move_to_end() is searching for the key
        od.clear()
        return True

od = OrderedDict()
od[Original()] = None
od.move_to_end(Trigger())

from collections import OrderedDict

class Original():
    def __hash__(self):
        return 1

class Trigger:
    def __hash__(self):
        return 1
    def __eq__(self, other):
        global od
        od.clear()
        return True

od = OrderedDict()
od[Original()] = None
od.pop(Trigger())

Affected Versions:

Python Version Status Exit Code
Python 3.9.24+ (heads/3.9:9c4638d, Oct 17 2025, 11:19:30) Assert -6
Python 3.10.19+ (heads/3.10:0142619, Oct 17 2025, 11:20:05) [GCC 13.3.0] Assert -6
Python 3.11.14+ (heads/3.11:88f3f5b, Oct 17 2025, 11:20:44) [GCC 13.3.0] ASAN 1
Python 3.12.12+ (heads/3.12:8cb2092, Oct 17 2025, 11:21:35) [GCC 13.3.0] ASAN 1
Python 3.13.9+ (heads/3.13:0760a57, Oct 17 2025, 11:22:25) [GCC 13.3.0] ASAN 1
Python 3.14.0+ (heads/3.14:889e918, Oct 17 2025, 11:23:02) [GCC 13.3.0] ASAN 1
Python 3.15.0a1+ (heads/main:fbf0843, Oct 17 2025, 11:23:37) [GCC 13.3.0] ASAN 1

Sanitizer Output:

=================================================================
==977233==ERROR: AddressSanitizer: heap-use-after-free on address 0x510000058d68 at pc 0x5957660a36fa bp 0x7fffafd9d500 sp 0x7fffafd9d4f0
READ of size 8 at 0x510000058d68 thread T0
    #0 0x5957660a36f9 in _odict_get_index_raw Objects/odictobject.c:550
    #1 0x5957660a39a6 in _odict_get_index Objects/odictobject.c:615
    #2 0x5957660a456a in _odict_clear_node Objects/odictobject.c:775
    #3 0x5957660a72d5 in PyODict_DelItem_LockHeld Objects/odictobject.c:1669
    #4 0x5957660a730d in PyODict_DelItem Objects/odictobject.c:1680
    #5 0x5957660a7328 in odict_mp_ass_sub Objects/odictobject.c:877
    #6 0x595765fd5046 in PyObject_DelItem Objects/abstract.c:271
    #7 0x5957662992d7 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:5281
    #8 0x5957662c6e54 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #9 0x5957662c7148 in _PyEval_Vector Python/ceval.c:2001
    #10 0x5957662c73f8 in PyEval_EvalCode Python/ceval.c:884
    #11 0x5957663be507 in run_eval_code_obj Python/pythonrun.c:1365
    #12 0x5957663be723 in run_mod Python/pythonrun.c:1459
    #13 0x5957663bf57a in pyrun_file Python/pythonrun.c:1293
    #14 0x5957663c2220 in _PyRun_SimpleFileObject Python/pythonrun.c:521
    #15 0x5957663c24f6 in _PyRun_AnyFileObject Python/pythonrun.c:81
    #16 0x59576641374d in pymain_run_file_obj Modules/main.c:410
    #17 0x5957664139b4 in pymain_run_file Modules/main.c:429
    #18 0x5957664151b2 in pymain_run_python Modules/main.c:691
    #19 0x595766415842 in Py_RunMain Modules/main.c:772
    #20 0x595766415a2e in pymain_main Modules/main.c:802
    #21 0x595766415db3 in Py_BytesMain Modules/main.c:826
    #22 0x595765e99645 in main Programs/python.c:15
    #23 0x71bb5942a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #24 0x71bb5942a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #25 0x595765e99574 in _start (/home/jackfromeast/Desktop/entropy/tasks/grammar-afl++-latest/targets/cpython/python+0x2dd574) (BuildId: ff3dc40ea460bd4beb2c3a72283cca525b319bf0)

0x510000058d68 is located 40 bytes inside of 184-byte region [0x510000058d40,0x510000058df8)
freed by thread T0 here:
    #0 0x71bb598fc4d8 in free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:52
    #1 0x5957660cb96d in _PyMem_RawFree Objects/obmalloc.c:91
    #2 0x5957660cdcd9 in _PyMem_DebugRawFree Objects/obmalloc.c:2955
    #3 0x5957660cdd1a in _PyMem_DebugFree Objects/obmalloc.c:3100
    #4 0x5957660f5348 in PyMem_Free Objects/obmalloc.c:1070
    #5 0x59576608dd52 in free_keys_object Objects/dictobject.c:823
    #6 0x59576608dfba in dictkeys_decref Objects/dictobject.c:473
    #7 0x59576609e4e9 in clear_lock_held Objects/dictobject.c:2947
    #8 0x59576609e680 in _PyDict_Clear_LockHeld Objects/dictobject.c:2969
    #9 0x5957660a4f71 in OrderedDict_clear_impl Objects/odictobject.c:1226
    #10 0x5957660a4f93 in OrderedDict_clear Objects/clinic/odictobject.c.h:353
    #11 0x595766024571 in method_vectorcall_NOARGS Objects/descrobject.c:448
    #12 0x595766004e7f in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169
    #13 0x595766004f72 in PyObject_Vectorcall Objects/call.c:327
    #14 0x595766283056 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:1620
    #15 0x5957662c6e54 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #16 0x5957662c7148 in _PyEval_Vector Python/ceval.c:2001
    #17 0x5957660049b8 in _PyFunction_Vectorcall Objects/call.c:413
    #18 0x59576611756b in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169
    #19 0x5957661339a6 in vectorcall_unbound Objects/typeobject.c:3033
    #20 0x5957661339a6 in maybe_call_special_one_arg Objects/typeobject.c:3175
    #21 0x595766133ad3 in _PyObject_MaybeCallSpecialOneArg Objects/typeobject.c:3190
    #22 0x595766133b19 in slot_tp_richcompare Objects/typeobject.c:10729
    #23 0x5957660c4762 in do_richcompare Objects/object.c:1065
    #24 0x5957660c493d in PyObject_RichCompare Objects/object.c:1108
    #25 0x5957660c49ad in PyObject_RichCompareBool Objects/object.c:1130
    #26 0x59576608e589 in compare_generic Objects/dictobject.c:1110
    #27 0x59576608b340 in do_lookup Objects/dictobject.c:1010
    #28 0x59576608b3db in dictkeys_generic_lookup Objects/dictobject.c:1129
    #29 0x595766094833 in _Py_dict_lookup Objects/dictobject.c:1295
    #30 0x5957660a3678 in _odict_get_index_raw Objects/odictobject.c:547

previously allocated by thread T0 here:
    #0 0x71bb598fd9c7 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0x5957660cc284 in _PyMem_RawMalloc Objects/obmalloc.c:63
    #2 0x5957660cb655 in _PyMem_DebugRawAlloc Objects/obmalloc.c:2887
    #3 0x5957660cb6bd in _PyMem_DebugRawMalloc Objects/obmalloc.c:2920
    #4 0x5957660ccf3b in _PyMem_DebugMalloc Objects/obmalloc.c:3085
    #5 0x5957660f5204 in PyMem_Malloc Objects/obmalloc.c:1041
    #6 0x59576608ebde in new_keys_object Objects/dictobject.c:784
    #7 0x59576609ab28 in insert_to_emptydict Objects/dictobject.c:1948
    #8 0x59576609d1c7 in _PyDict_SetItem_KnownHash_LockHeld Objects/dictobject.c:2723
    #9 0x5957660a4ece in _PyODict_SetItem_KnownHash_LockHeld Objects/odictobject.c:1626
    #10 0x5957660a4f4e in PyODict_SetItem_LockHeld Objects/odictobject.c:1648
    #11 0x5957660a7298 in PyODict_SetItem Objects/odictobject.c:1656
    #12 0x5957660a7321 in odict_mp_ass_sub Objects/odictobject.c:879
    #13 0x595765fd4be7 in PyObject_SetItem Objects/abstract.c:237
    #14 0x5957662c02f6 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:11245
    #15 0x5957662c6e54 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #16 0x5957662c7148 in _PyEval_Vector Python/ceval.c:2001
    #17 0x5957662c73f8 in PyEval_EvalCode Python/ceval.c:884
    #18 0x5957663be507 in run_eval_code_obj Python/pythonrun.c:1365
    #19 0x5957663be723 in run_mod Python/pythonrun.c:1459
    #20 0x5957663bf57a in pyrun_file Python/pythonrun.c:1293
    #21 0x5957663c2220 in _PyRun_SimpleFileObject Python/pythonrun.c:521
    #22 0x5957663c24f6 in _PyRun_AnyFileObject Python/pythonrun.c:81
    #23 0x59576641374d in pymain_run_file_obj Modules/main.c:410
    #24 0x5957664139b4 in pymain_run_file Modules/main.c:429
    #25 0x5957664151b2 in pymain_run_python Modules/main.c:691
    #26 0x595766415842 in Py_RunMain Modules/main.c:772
    #27 0x595766415a2e in pymain_main Modules/main.c:802
    #28 0x595766415db3 in Py_BytesMain Modules/main.c:826
    #29 0x595765e99645 in main Programs/python.c:15

SUMMARY: AddressSanitizer: heap-use-after-free Objects/odictobject.c:550 in _odict_get_index_raw
Shadow bytes around the buggy address:
  0x510000058a80: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x510000058b00: fa fa fa fa fa fa fa fa 00 00 00 00 00 00 00 00
  0x510000058b80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x510000058c00: fa fa fa fa fa fa fa fa 00 00 00 00 00 00 00 00
  0x510000058c80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x510000058d00: fa fa fa fa fa fa fa fa fd fd fd fd fd[fd]fd fd
  0x510000058d80: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fa
  0x510000058e00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x510000058e80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x510000058f00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x510000058f80: fa fa fa fa fa fa fa fa fa fa fa 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
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  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
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==977233==ABORTING

Hướng dẫn đóng góp

Mở hướng dẫn đóng góp

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Hướng nghiên cứu

Bắt đầu bằng cách tái hiện ba trường hợp OrderedDict re-entrant dưới ASAN, sau đó đọc Objects/odictobject.c quanh _odict_get_index_raw và _odict_clear_node. Truy vết các đường dẫn lookup và cleanup được deletion, pop và move_to_end sử dụng; công việc được xem là hoàn tất khi các trường hợp này không còn truy cập vào vùng lưu trữ bảng hoặc node đã được giải phóng và có coverage hồi quy.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Đánh giá

Công nghệ
c, python
Lĩnh vực
backend
Loại issue
Lỗi
Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức độ hoạt động
Đình trệ
Độ rõ ràng
Khá rõ ràng
Mức phù hợp với người mới
35/100

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.