Skip to content

RegExp: alternation OOM causes a heap out-of-bounds write

High
saghul published GHSA-rxpx-wj25-jhqq Jul 31, 2026

Package

quickjs-ng

Affected versions

>= 0.15.1

Patched versions

0.16.0

Description

regexp-disjunction-oom-oob-write-poc.js

Summary

The RegExp compiler writes a four-byte branch offset after growing the bytecode buffer for it fails.

With the tested memory limit, the buffer is full after the branch opcode. Allocation for the four-byte operand fails, but re_parse_disjunction() still writes it past the end.

Affected Version

Tested on QuickJS-NG commit a07a918103269fbd7732a9565996907ad116fa21 using Ubuntu 24.04 arm64.

Steps to Reproduce

Build QuickJS-NG with ASan:

cmake -S . -B build-asan -G Ninja \
  -DCMAKE_BUILD_TYPE=RelWithDebInfo \
  -DQJS_ENABLE_ASAN=ON

cmake --build build-asan --parallel

Run the attached PoC:

ASAN_OPTIONS=abort_on_error=1:detect_leaks=0:halt_on_error=1 \
  ./build-asan/qjs \
  -C \
  --memory-limit 111616b \
  regexp-disjunction-oom-oob-write-poc.js

The exact limit depends on the build. The value above is for the tested build.

Expected Result

RegExp compilation should throw an out-of-memory exception without writing past the bytecode buffer.

Actual Result

ASan reports the four-byte heap out-of-bounds write:

=================================================================
==191009==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x50d0000019ff at pc 0xaaaae202b9cc bp 0xfffff2e70e80 sp 0xfffff2e70e70
WRITE of size 4 at 0x50d0000019ff thread T0
    #0 0xaaaae202b9c8 in memcpy /usr/include/aarch64-linux-gnu/bits/string_fortified.h:29
    #1 0xaaaae202b9c8 in put_u32 /src/cutils.h:299
    #2 0xaaaae202b9c8 in re_parse_disjunction /src/libregexp.c:2451
    #3 0xaaaae202b9c8 in re_parse_disjunction /src/libregexp.c:2417
    #4 0xaaaae202c094 in lre_compile /src/libregexp.c:2579
    #5 0xaaaae1f10948 in js_compile_regexp /src/quickjs.c:48834
    #6 0xaaaae1f5eb3c in js_regexp_constructor /src/quickjs.c:48989
    #7 0xaaaae1f5b618 in js_call_c_function /src/quickjs.c:17854
    #8 0xaaaae1fb96b0 in JS_CallConstructorInternal /src/quickjs.c:21013
    #9 0xaaaae1e8439c in JS_CallInternal /src/quickjs.c:18504
    #10 0xaaaae1e93890 in JS_CallFree /src/quickjs.c:20907
    #11 0xaaaae2004498 in JS_EvalFunctionInternal /src/quickjs.c:38027
    #12 0xaaaae2008874 in __JS_EvalInternal /src/quickjs.c:38162
    #13 0xaaaae1f2fb74 in JS_EvalInternal /src/quickjs.c:38188
    #14 0xaaaae1f2fb74 in JS_EvalThis2 /src/quickjs.c:38243
    #15 0xaaaae1f2fb74 in JS_Eval /src/quickjs.c:38257
    #16 0xaaaae1e42ca8 in eval_buf /src/qjs.c:139
    #17 0xaaaae1e42ef4 in eval_file /src/qjs.c:172
    #18 0xaaaae1e41a34 in main /src/qjs.c:700
    #19 0xffff955b84c0 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #20 0xffff955b8594 in __libc_start_main_impl ../csu/libc-start.c:360
    #21 0xaaaae1e421ec in _start (/src/build-linux-asan/qjs+0x321ec) (BuildId: 2447509c950a65bf917e06cfb98409eba3e0472e)

0x50d0000019ff is located 0 bytes after 143-byte region [0x50d000001970,0x50d0000019ff)
allocated by thread T0 here:
    #0 0xffff958e646c in realloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:85
    #1 0xaaaae1e75618 in js_arena_realloc /src/quickjs.c:1885
    #2 0xaaaae1e75618 in js_realloc_rt /src/quickjs.c:2043
    #3 0xaaaae2028e6c in dbuf_claim /src/cutils.h:779
    #4 0xaaaae2028e6c in dbuf_put /src/cutils.h:793
    #5 0xaaaae2028e6c in __dbuf_putc /src/cutils.h:818
    #6 0xaaaae2028e6c in dbuf_putc /src/cutils.h:465
    #7 0xaaaae2028e6c in dbuf_putc /src/cutils.h:462
    #8 0xaaaae2028e6c in re_emit_op_u16 /src/libregexp.c:684
    #9 0xaaaae2028e6c in re_emit_char /src/libregexp.c:1282
    #10 0xaaaae2028e6c in re_emit_char /src/libregexp.c:1279
    #11 0xaaaae2028e6c in re_parse_term /src/libregexp.c:2200
    #12 0xaaaae2028e6c in re_parse_alternative /src/libregexp.c:2397
    #13 0xaaaae202b57c in re_parse_disjunction /src/libregexp.c:2446
    #14 0xaaaae202b57c in re_parse_disjunction /src/libregexp.c:2417
    #15 0xaaaae202c094 in lre_compile /src/libregexp.c:2579
    #16 0xaaaae1f10948 in js_compile_regexp /src/quickjs.c:48834
    #17 0xaaaae1f5eb3c in js_regexp_constructor /src/quickjs.c:48989
    #18 0xaaaae1f5b618 in js_call_c_function /src/quickjs.c:17854
    #19 0xaaaae1fb96b0 in JS_CallConstructorInternal /src/quickjs.c:21013
    #20 0xaaaae1e8439c in JS_CallInternal /src/quickjs.c:18504
    #21 0xaaaae1e93890 in JS_CallFree /src/quickjs.c:20907
    #22 0xaaaae2004498 in JS_EvalFunctionInternal /src/quickjs.c:38027
    #23 0xaaaae2008874 in __JS_EvalInternal /src/quickjs.c:38162
    #24 0xaaaae1f2fb74 in JS_EvalInternal /src/quickjs.c:38188
    #25 0xaaaae1f2fb74 in JS_EvalThis2 /src/quickjs.c:38243
    #26 0xaaaae1f2fb74 in JS_Eval /src/quickjs.c:38257
    #27 0xaaaae1e42ca8 in eval_buf /src/qjs.c:139
    #28 0xaaaae1e42ef4 in eval_file /src/qjs.c:172
    #29 0xaaaae1e41a34 in main /src/qjs.c:700
    #30 0xffff955b84c0 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #31 0xffff955b8594 in __libc_start_main_impl ../csu/libc-start.c:360
    #32 0xaaaae1e421ec in _start (/src/build-linux-asan/qjs+0x321ec) (BuildId: 2447509c950a65bf917e06cfb98409eba3e0472e)

SUMMARY: AddressSanitizer: heap-buffer-overflow /usr/include/aarch64-linux-gnu/bits/string_fortified.h:29 in memcpy
Shadow bytes around the buggy address:
  0x50d000001700: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x50d000001780: fd fa fa fa fa fa fa fa fd fd fd fd fd fd fd fd
  0x50d000001800: fd fd fd fd fd fd fd fd fd fa fa fa fa fa fa fa
  0x50d000001880: fa fa fa fa fd fd fd fd fd fd fd fd fd fd fd fd
  0x50d000001900: fd fd fd fd fd fd fa fa fa fa fa fa fa fa 00 00
=>0x50d000001980: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00[07]
  0x50d000001a00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x50d000001a80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x50d000001b00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x50d000001b80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x50d000001c00: 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
==191009==ABORTING

Root Cause

re_emit_op_u32() writes the opcode and its four-byte operand separately:

// libregexp.c
static int re_emit_op_u32(REParseState *s, int op, uint32_t val)
{
    int pos;

    // In this trigger, the opcode uses the last available byte.
    dbuf_putc(&s->byte_code, op);

    // Save the position where the four-byte operand should begin.
    pos = s->byte_code.size;

    // This allocation fails and leaves the buffer size unchanged.
    dbuf_put_u32(&s->byte_code, val);
    return pos;
}

In the PoC, the opcode uses the last available byte. Growing the buffer for the operand fails, so pos points just beyond the RegExp bytecode.

re_parse_disjunction() does not check the buffer error before writing the branch offset:

// libregexp.c
static int re_parse_disjunction(REParseState *s, bool is_backward_dir)
{
    int start, len, pos;

    // ...
    while (*s->buf_ptr == '|') {
        // ...

        // The opcode can fit even when allocation of its operand fails.
        pos = re_emit_op_u32(s, REOP_goto, 0);

        // There is no byte_code error check here.
        if (re_parse_alternative(s, is_backward_dir))
            return -1;

        // pos points past the buffer after the failed allocation.
        len = s->byte_code.size - (pos + 4);
        put_u32(s->byte_code.buf + pos, len);
    }
    return 0;
}

Because the buffer did not grow, len is 0xfffffffc. On little-endian systems, put_u32() writes:

fc ff ff ff

In the ASan build, the bytecode has its own allocation. The write begins 0 bytes after a 143-byte region, so all four bytes are outside the allocation.

Impact

In a normal build, the bytecode comes from the small-block allocator. The four-byte write crosses into the next block's header.

Build a normal binary:

cmake -S . -B build -G Ninja \
  -DCMAKE_BUILD_TYPE=RelWithDebInfo

cmake --build build --parallel

Run the attached PoC:

./build/qjs \
  -C \
  --memory-limit 114834b \
  regexp-disjunction-oom-oob-write-poc.js

The exact limit depends on the build. The value above is for the tested build.

The PoC catches the RegExp out-of-memory exception and creates two strings. When the program exits, freeing the 110-character B string stored in victim1 causes a SIGSEGV:

Program received signal SIGSEGV, Segmentation fault.
__list_add (next=0x0, prev=<optimized out>, el=0xaaaaaabcaf30)
    at /src/list.h:58
58          next->prev = el;
#0  __list_add at /src/list.h:58
#1  list_add at /src/list.h:64
#2  js_arena_free at /src/quickjs.c:1842
#3  free_object at /src/quickjs.c:7052
#4  free_gc_object at /src/quickjs.c:7090
#5  gc_free_cycles at /src/quickjs.c:7443
#6  JS_RunGC at /src/quickjs.c:7473
#7  JS_FreeRuntime at /src/quickjs.c:2653
#8  main at /src/qjs.c:730

The bytecode occupies 135 bytes of a small allocator block with 136 usable bytes. The write is fc ff ff ff. The fc byte lands in the last unused byte. The next two ff bytes set free_next to 0xffff. The final ff byte sets block_size_idx to 0xff.

Each small allocator block starts with this header:

// quickjs.c
typedef struct JSMallocBlockHeader {
    union {
        uint16_t block_idx;
        uint16_t free_next;
    } u;                         // The first two overwritten header bytes.
    uint8_t block_size_idx;      // The third overwritten header byte.

    // The remaining header fields are not changed by this write.
    // ...
} JSMallocBlockHeader;

free_next links unused blocks. block_size_idx selects the block size. The overwrite changes them to 65535 and 255.

When js_arena_malloc() later reuses the corrupted block for victim1, it replaces free_next with the real block_idx, but leaves the corrupted block_size_idx unchanged:

// quickjs.c
static void *js_arena_malloc(JSRuntime *rt, size_t size)
{
    // ...

    // Select the next unused block.
    block_idx = ar->first_free_block;
    b = arena_get_block(ar, block_idx, block_size);
    ar->first_free_block = b->u.free_next;

    // Restore block_idx, but not block_size_idx.
    b->u.block_idx = block_idx;

    // ...
    return b->user_data;
}

When victim1 is later freed, js_arena_free() uses the corrupted value as an array index:

// quickjs.c
static void js_arena_free(JSRuntime *rt, void *ptr)
{
    JSMallocBlockHeader *b;

    // Find the header stored before the allocation.
    b = container_of(ptr, JSMallocBlockHeader, user_data);

    // ...

    // The corrupted value 255 is used as an array index.
    unsigned int block_idx = b->u.block_idx;
    unsigned int block_size_idx = b->block_size_idx;
    unsigned int block_size = arena_block_sizes[block_size_idx];

    // Calculate the arena address using the invalid block size.
    JSArena *ar = (JSArena *)((uint8_t *)b -
                              (size_t)block_size * block_idx -
                              sizeof(JSArena));

    // This condition was true in the captured run.
    if (unlikely(ar->n_used_blocks == ar->n_blocks))
        // The invalid index selects a list outside the 31 entries.
        list_add(&ar->free_link,
                 &rt->arena_state.free_arena_list[block_size_idx]);

    // ...
}

By the time of the crash, block_idx has been restored to 18, but block_size_idx remains 255. Only values from 0 to 30 are valid.

In the tested build, reading arena_block_sizes[255] returned 0, which produced the wrong arena address. The same invalid index selected free_arena_list[255], outside the list array. Its next pointer was NULL.

list_add() passes that NULL pointer to __list_add(), which crashes when it dereferences next:

// list.h
static inline void list_add(struct list_head *el, struct list_head *head)
{
    // head points outside free_arena_list, and head->next is NULL.
    __list_add(el, head, head->next);
}

static inline void __list_add(struct list_head *el,
                              struct list_head *prev,
                              struct list_head *next)
{
    // ...

    // next is NULL, so this causes SIGSEGV.
    next->prev = el;
}

Suggested Fix

Check dbuf_error(&s->byte_code) after re_emit_op_u32() and after compiling the following alternative. Return re_parse_out_of_memory(s) before patching the branch if either check fails.

Severity

High

CVE ID

No known CVE

Weaknesses

No CWEs

Credits