Root Cause

Chrome Oilpan - Meta Data, Freelists and more

Chrome originally used WebKit as its HTML, DOM, and web layout engine. In those days the browser used TCMalloc for most of its heap allocations. This made exploiting linear heap overflows and use-after-free vulnerabilities relatively straight forward. But in 2013 the WebKit code was forked into the Blink project. Around this time Chrome switched to PartitionAlloc for heap allocations for everything from Blink DOM nodes to standard containers that were often the target of memory disclosure exploits.

PartitionAlloc provided some pretty strong security guarantees: guard pages to protect against linear overflows from user data into page level meta-data, separation of allocations by size and type (if the API was used correctly), double free detection, masking of the freelist pointer, and no inline meta data between user chunks. I previously made an attempt at hardening PartitionAlloc even further by adding randomization of the freelist and introducing delayed free. PatitionAlloc is no longer used to allocate memory for DOM related C++ objects in Chrome. Instead a new garbage collected memory allocator, Oilpan, is used. Oilpan is a different design with its own tradeoffs that optimize for performance. But those tradeoffs can introduce opportunity for an exploit developer. This post is about some of those design decisions that resulted in a lack of exploit mitigations traditonally found in more mature memory allocators.

In 2015 Blink switched to Oilpan for allocation of DOM objects that inherit from Node. The Node class inherits from EventTarget which in turn inherits from GarbageCollectedFinalized. This remains the case for recent versions of Chrome (version 59 is the latest as of this writing). The Node object overloads the new operator and calls a special Oilpan allocation function.

Oilpan is a garbage collector, which means for these objects there is no reference count via the familiar WebKit RefPtr template. Oilpan supplies its own heap allocator which maintains little of the security properties that PartitionAlloc provided. I won't spend too much time explaining how the Oilpan GC works. For that I suggest reading some of the markdown documents linked above, they're really quite good. But we will spend some time looking at the basic allocation routines.

Before we can dive into the issue we need to understand how Oilpan allocates memory for Blink objects. In this context we are specifically talking about Blink objects that inherit from the Node class. As an example this means, among other things, any HTML element exposed to the browser DOM. The implementation of these elements is where you typically find use-after-free vulnerabilities. Our journey into the Oilpan allocator starts in the Node class definition in the overloaded new operator shown below.

// Node.h
void* operator new(size_t size)
{
    return allocateObject(size, false);
}
static void* allocateObject(size_t size, bool isEager)
{
    ThreadState* state = ThreadStateFor::Affinity>::state();
    const char typeName[] = "blink::Node";
    return ThreadHeap::allocateOnArenaIndex(state, size, isEager ? BlinkGC::EagerSweepArenaIndex : BlinkGC::NodeArenaIndex, GCInfoTrait::index(), typeName);
}

static inline size_t allocationSizeFromSize(size_t size)
{
    // Check the size before computing the actual allocation size.  The
    // allocation size calculation can overflow for large sizes and the check
    // therefore has to happen before any calculation on the size.
    RELEASE_ASSERT(size < maxHeapObjectSize);

    // Add space for header.
    size_t allocationSize = size + sizeof(HeapObjectHeader);
    // Align size with allocation granularity.
    allocationSize = (allocationSize + allocationMask) & ~allocationMask;
    return allocationSize;
}

// Heap.h
inline Address ThreadHeap::allocateOnArenaIndex(ThreadState* state, size_t size, int arenaIndex, size_t gcInfoIndex, const char* typeName)
{
    ASSERT(state->isAllocationAllowed());
    ASSERT(arenaIndex != BlinkGC::LargeObjectArenaIndex);
    NormalPageArena* arena = static_cast(state->arena(arenaIndex));
    Address address = arena->allocateObject(allocationSizeFromSize(size), gcInfoIndex);
    HeapAllocHooks::allocationHookIfEnabled(address, size, typeName);
    return address;
}

// HeapPage.h
inline Address NormalPageArena::allocateObject(size_t allocationSize, size_t gcInfoIndex)
{
    if (LIKELY(allocationSize <= m_remainingAllocationSize)) {
        Address headerAddress = m_currentAllocationPoint;
        m_currentAllocationPoint += allocationSize;
        m_remainingAllocationSize -= allocationSize;
        ASSERT(gcInfoIndex > 0);
        new (NotNull, headerAddress) HeapObjectHeader(allocationSize, gcInfoIndex);
        Address result = headerAddress + sizeof(HeapObjectHeader);
        ASSERT(!(reinterpret_cast(result) & allocationMask));

        SET_MEMORY_ACCESSIBLE(result, allocationSize - sizeof(HeapObjectHeader));
        ASSERT(findPageFromAddress(headerAddress + allocationSize - 1));
        return result;
    }
    return outOfLineAllocate(allocationSize, gcInfoIndex);
}

// HeapPage.h
// HeapObjectHeader is 4 byte (32 bit) that has the following layout:
//
// | gcInfoIndex (14 bit) | DOM mark bit (1 bit) | size (14 bit) | dead bit (1 bit) | freed bit (1 bit) | mark bit (1 bit) |
// - For non-large objects, 14 bit is enough for |size| because the blink
//   page size is 2^17 byte and each object is guaranteed to be aligned with
//   2^3 byte.
// - For large objects, |size| is 0. The actual size of a large object is
//   stored in LargeObjectPage::m_payloadSize.
// - 1 bit used to mark DOM trees for V8.
// - 14 bit is enough for gcInfoIndex because there are less than 2^14 types
//   in Blink.

// HeapPage.cpp
Address NormalPageArena::outOfLineAllocate(size_t allocationSize, size_t gcInfoIndex)
{
    ASSERT(allocationSize > remainingAllocationSize());
    ASSERT(allocationSize >= allocationGranularity);

    // 1. If this allocation is big enough, allocate a large object.
    if (allocationSize >= largeObjectSizeThreshold)
        return allocateLargeObject(allocationSize, gcInfoIndex);

    // 2. Try to allocate from a free list.
    updateRemainingAllocationSize();
    Address result = allocateFromFreeList(allocationSize, gcInfoIndex);
    if (result)
        return result;

    // 3. Reset the allocation point.
    setAllocationPoint(nullptr, 0);

    // 4. Lazily sweep pages of this heap until we find a freed area for
    // this allocation or we finish sweeping all pages of this heap.
    result = lazySweep(allocationSize, gcInfoIndex);
    if (result)
        return result;

    // 5. Coalesce promptly freed areas and then try to allocate from a free
    // list.
    if (coalesce()) {
        result = allocateFromFreeList(allocationSize, gcInfoIndex);
        if (result)
            return result;
    }

    // 6. Complete sweeping.
    getThreadState()->completeSweep();

    // 7. Check if we should trigger a GC.
    getThreadState()->scheduleGCIfNeeded();

    // 8. Add a new page to this heap.
    allocatePage();

    // 9. Try to allocate from a free list. This allocation must succeed.
    result = allocateFromFreeList(allocationSize, gcInfoIndex);
    RELEASE_ASSERT(result);
    return result;
}

Address NormalPageArena::allocateFromFreeList(size_t allocationSize, size_t gcInfoIndex)
{
    // Try reusing a block from the largest bin. The underlying reasoning
    // being that we want to amortize this slow allocation call by carving
    // off as a large a free block as possible in one go; a block that will
    // service this block and let following allocations be serviced quickly
    // by bump allocation.
    size_t bucketSize = static_cast(1) << m_freeList.m_biggestFreeListIndex;
    int index = m_freeList.m_biggestFreeListIndex;
    for (; index > 0; --index, bucketSize >>= 1) {
        FreeListEntry* entry = m_freeList.m_freeLists[index];
        if (allocationSize > bucketSize) {
            // Final bucket candidate; check initial entry if it is able
            // to service this allocation. Do not perform a linear scan,
            // as it is considered too costly.
            if (!entry || entry->size() < allocationSize)
                break;
        }
        if (entry) {
            entry->unlink(&m_freeList.m_freeLists[index]);
            setAllocationPoint(entry->getAddress(), entry->size());
            ASSERT(hasCurrentAllocationArea());
            ASSERT(remainingAllocationSize() >= allocationSize);
            m_freeList.m_biggestFreeListIndex = index;
            return allocateObject(allocationSize, gcInfoIndex);
        }
    }
    m_freeList.m_biggestFreeListIndex = index;
    return nullptr;
}

class FreeListEntry final : public HeapObjectHeader {
public:
    NO_SANITIZE_ADDRESS
    explicit FreeListEntry(size_t size)
        : HeapObjectHeader(size, gcInfoIndexForFreeListHeader)
        , m_next(nullptr)
    {
#if ENABLE(ASSERT)
        ASSERT(size >= sizeof(HeapObjectHeader));
        zapMagic();
#endif
    }

    Address getAddress() { return reinterpret_cast< Address>(this); }

    NO_SANITIZE_ADDRESS
    void unlink(FreeListEntry** prevNext)
    {
        *prevNext = m_next;
        m_next = nullptr;
    }

    NO_SANITIZE_ADDRESS
    void link(FreeListEntry** prevNext)
    {
        m_next = *prevNext;
        *prevNext = this;
    }

    NO_SANITIZE_ADDRESS
    FreeListEntry* next() const { return m_next; }

    NO_SANITIZE_ADDRESS
    void append(FreeListEntry* next)
    {
        ASSERT(!m_next);
        m_next = next;
    }

private:
    FreeListEntry* m_next;
};

void FreeList::addToFreeList(Address address, size_t size)
{
    ASSERT(size < blinkPagePayloadSize());
    // The free list entries are only pointer aligned (but when we allocate
    // from them we are 8 byte aligned due to the header size).
    ASSERT(!((reinterpret_cast(address) + sizeof(HeapObjectHeader)) & allocationMask));
    ASSERT(!(size & allocationMask));
    ASAN_UNPOISON_MEMORY_REGION(address, size);
    FreeListEntry* entry;
    if (size < sizeof(*entry)) {
        // Create a dummy header with only a size and freelist bit set.
        ASSERT(size >= sizeof(HeapObjectHeader));
        // Free list encode the size to mark the lost memory as freelist memory.
        new (NotNull, address) HeapObjectHeader(size, gcInfoIndexForFreeListHeader);

        ASAN_POISON_MEMORY_REGION(address, size);
        // This memory gets lost. Sweeping can reclaim it.
        return;
    }
    entry = new (NotNull, address) FreeListEntry(size);