use after free found at micropython/py/objarray.c:509 [micropython@a5bdd39127]

[zeroone-kr]

Hi all, I'm Wonil Jang, from the research group S2Lab in UNIST.
We found a use after free bug from micropython by our custom tool. The detailed information is as follows.

Environment

• OS: Ubuntu 22.04
• Version: micropython at commit a5bdd39
• Build: unix ports
• Bug Type: use-after-free
• Bug Location: micropython/py/objarray.c:509
• Credits: Junwha Hong and Wonil Jang, from S2Lab in UNIST

Proof-of-Concept (PoC)

b = bytearray(b'1234567')
for i in range(3):
     b[-1:] = b

Problem Statement

By PoC,

STATIC mp_obj_t array_subscr(mp_obj_t self_in, mp_obj_t index_in, mp_obj_t **value**) {
...
size_t src_len;
void *src_items;
size_t item_sz = mp_binary_get_size('@', o->typecode & TYPECODE_MASK, NULL);
if (mp_obj_is_obj(value) && MP_OBJ_TYPE_GET_SLOT_OR_NULL(((mp_obj_base_t *)MP_OBJ_TO_PTR(value))->type, subscr) == array_subscr) {
    // value is array, bytearray or memoryview
    **mp_obj_array_t *src_slice = MP_OBJ_TO_PTR(value);**
    if (item_sz != mp_binary_get_size('@', src_slice->typecode & TYPECODE_MASK, NULL)) {
    compat_error:
        mp_raise_ValueError(MP_ERROR_TEXT("lhs and rhs should be compatible"));
    }
    **src_len = src_slice->len;**
    **src_items = src_slice->items;**
    #if MICROPY_PY_BUILTINS_MEMORYVIEW
    if (mp_obj_is_type(value, &mp_type_memoryview)) {
        src_items = (uint8_t *)src_items + (src_slice->memview_offset * item_sz);
    }
    #endif
}
...
if ((size_t)len_adj > o->free) {
    // TODO: alloc policy; at the moment we go conservative
    **o->items = m_renew(byte, o->items, (o->len + o->free) * item_sz, (o->len + len_adj) * item_sz);**
    o->free = len_adj;
    dest_items = o->items;
}
mp_seq_replace_slice_grow_inplace(dest_items, o->len,
    slice.start, slice.stop, **src_items**, src_len, len_adj, item_sz);

If you run the PoC, self_in and value can be same in array_subscr function. This is because when subscr() function is called, It just uses reference without copying. and then, if the address is rebased after calling realloc, only self_in changed and value(src) becomes a dangling pointer. So when copying it, the use after free bug occurs.

Patch

It should keep source before calling fixed realloc().

Log

    #1 0x5555557340a4 in array_subscr /home/qbit/testing-2023/micropython/ports/unix/../../py/objarray.c:509:21
    #2 0x555555731de6 in mp_obj_subscr /home/qbit/testing-2023/micropython/ports/unix/../../py/obj.c:536:24
    #3 0x555555781d05 in mp_execute_bytecode /home/qbit/testing-2023/micropython/ports/unix/../../py/vm.c:487:21
    #4 0x55555574261b in fun_bc_call /home/qbit/testing-2023/micropython/ports/unix/../../py/objfun.c:273:42
    #5 0x555555903f3d in execute_from_lexer /home/qbit/testing-2023/micropython/ports/unix/main.c:161:13
    #6 0x555555902ad5 in do_file /home/qbit/testing-2023/micropython/ports/unix/main.c:310:12
    #7 0x555555902ad5 in main_ /home/qbit/testing-2023/micropython/ports/unix/main.c:722:19
    #8 0x7ffff7c29d8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
    #9 0x7ffff7c29e3f in __libc_start_main csu/../csu/libc-start.c:392:3
    #10 0x555555593a34 in _start (/home/qbit/testing-2023/micropython/ports/unix/build-standard/micropython+0x3fa34)

Thank you for reading my report.

[projectgus]

Hi @zeroone-kr,

Thanks for submitting these security issue reports.

You're correct that there is potential for the Python heap-allocated buffer inside Python object value to be accessed after it is freed when self_in == value. Specifically, local variable src_items can become "dangling pointer" for the period of time between the call to m_renew() at objarray.c:505 and subsequent use in mp_seq_replace_slice_grow_inplace() at objarray.c:509.

However, in MicroPython a scoped use-after-free like this isn't necessarily a bug in the same way it is for C. This is my understanding of the behaviour:

1. MicroPython has a global interpreter lock (GIL), so no other code may access the Python heap while array_subscr() is executing.
2. Therefore, no other code can allocate from the Python heap at this time. And array_subscr() doesn't perform any additional heap operation.
3. Therefore, the only possible memory pointed to by src_items will be the previous buffer bytes still present in the heap.
4. After line 509, src_items is not used again so it's impossible for the invalid pointer to be dereferenced after the GIL is released and other code might have written there.

[projectgus]

Spoke to @dpgeorge and he reminded me there are port configurations with threading but no GIL, in which the use-after-free becomes an issue.

[zeroone-kr]

Thank you, @projectgus for taking the time to check this issue.

By the way, the root cause is not the GIL, because we had compiled micropython with GIL with:

sed -i 's/CFLAGS += -DMICROPY_PY_THREAD=1 -DMICROPY_PY_THREAD_GIL=0/CFLAGS += -DMICROPY_PY_THREAD=1 -DMICROPY_PY_THREAD_GIL=1/' ports/unix/Makefile
sed -i 's/#define MICROPY_ASYNC_KBD_INTR         (1)/#define MICROPY_ASYNC_KBD_INTR         (0)/' ports/unix/variants/mpconfigvariant_common.h

Also, we checked again that regardless of the presence of GIL, we can trigger the heap use after free.
And to provide more details and the value at runtime, I would like to provide you with more explanation by debugging it again.

if (len_adj > 0) {
    if ((size_t)len_adj > o->free) {
        // TODO: alloc policy; at the moment we go conservative
        o->items = m_renew(byte, o->items, (o->len + o->free) * item_sz, (o->len + len_adj) * item_sz); <== [1]
        o->free = len_adj;
        dest_items = o->items; <== [2]
    }
    mp_seq_replace_slice_grow_inplace(dest_items, o->len,
        slice.start, slice.stop, src_items, src_len, len_adj, item_sz); <== [3]
}

If you run the given PoC, with GIL applied micropython, at [1], m_renew function will be called three times before the uaf bug occurrence. Here, the return value of m_renew() is changing as: 0x7fffef006d00 ⇒ 0x7fffef006d00 ⇒ 0x7fffef006e80 (it calls new_ptr = realloc()). It means that now 0x7fffef006d00 is freed and o->items is reallocated in the new place 0x7fffef006e80.

and After [2], The dest_items has same value as o->items (0x7fffef006e80).
and at [3], it calls mp_seq_replace_slice_grow_inplace() with dest_items, src_items and the other arguments.
However, src_items still points to freed chunk (0x7fffef006d00) containing prior data(1234561234561234561234567).

// Note: dest and slice regions may overlap
#define mp_seq_replace_slice_grow_inplace(dest, dest_len, beg, end, slice, slice_len, len_adj, item_sz) \
  memmove(((char *)dest) + (beg + slice_len) * (item_sz), ((char *)dest) + (end) * (item_sz), ((dest_len) + (len_adj) - ((beg) + (slice_len))) * (item_sz)); \
  memmove(((char *)dest) + (beg) * (item_sz), slice, slice_len * (item_sz));

It means mp_seq_replace_slice_grow_inplace() writes freed data(slice, which is src_items) to dest + beg * items_sz.
By PoC, dest + beg * items_sz indicates last index(24) in 1234561234561234561234567.
And freed data has value 1234561234561234561234567

Thus, it is Use-After-Free.

Thank you for reading our security report and responding.
I would appreciate it if you could confirm that again when you have time.

[projectgus]

I agree with your description of the sequence of events, and also agree that this is a bug. I actually have a fix for this in testing, hope to push it very soon.

If you run the given PoC, with GIL applied micropython
Thus, it is Use-After-Free.

My point was that something has to write into the freed region (pointed to by src_items) before the use-after-free causes any incorrect behaviour. If no other code can write to the freed region then it's still technically use-after-free because src_items is a dangling pointer to freed data, but no consequences will result from the bug as nothing else will access that region.

The GIL prevents other code from running until after the array_subscr returns. If there is no GIL, then it may be possible for other code to run concurrently at the same time as array_subscr which means this bug can cause incorrect behaviour.