Root Cause

     

Chrome Oilpan - Meta Data, Freelists and more

April 7th, 2017
Chris Rohlf

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);
}

In this overloaded new operator we call a function allocateObject, this function calls a static function ThreadHeap::allocateOnArenaIndex and passes in a pointer to the Nodes ThreadState and the size of the allocation requested. As many objects inherit from Node, the size will vary between calls. That size is passed to allocationSizeFromSize which is used to calculate the actual size needed for the allocation. Here's the entire function:

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;
}

The first checks ensures the requested size isn't too big. The max size that can be requested here is 134217728 bytes. The allocation size is increased by adding the size of the HeapObjectHeader object (more on this in a few minutes) and then finally ensuring it is properly aligned.

The NormalPageArena pointer is dereferenced to call the allocateObject function to allocate the memory for the Node object. Note that Address is defined as using Address = uint8_t*;.

// 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;
}

The allocateObject function below determines whether we will take the fast path or the slow path. The fast path first checks if the requested size, allocationSize, is less than or equal to the remaining amount of free space in the arena. If this conditional is passed then the address of the current allocation point, m_currentAllocationPoint is assigned to a typedef'd uint8_t* headerAddress. The NormalPageArena member variables are updated to reflect the new objects size, and a HeapObjectHeader class instance is constructed at that address via the new operator. The resulting pointer is calculated by adding the address plus the size of the HeapObjectHeader and is returned to the caller.

// 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);
}

Before I explain the slow path via outOfLineAllocate I want to step back and talk about the HeapObjectHeader class as its very important for the context of this post. The HeapObjectHeader class is a single dword, m_encoded, of inline meta-data. Its a bit-field that encodes information about the allocation, and its completely unprotected from linear overwrites.

// 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.

This dword, m_encoded, sits at the beginning of every allocation. Because there is no secret canary guarding this meta data it is a prime target for an exploit developer. Overwriting this value with a linear overwrite and triggering a call to the NormalPageArena::coalesce function will use the untrusted size to adjust the startOfGap pointer. The resulting address will be passed to FreeList::addToFreeList. In addition to this unprotected m_encoded value the FreeListEntry class, which inherits from HeapObjectHeader contains an inline m_next pointer which forms a singly linked list of free'd chunks. The FreeListEntry::unlink function is easily abused if the m_next pointer can be controlled via linear overwrite. More on this later. Lets briefly return to the NormalPageArena slow path.

The slow path, shown below starting in NormalPageArena::outOfLineAllocate, is heavily commented and mostly self explanitory. The allocator either returns a 'large object' if the size is big enough, or attempt to allocate from an existing free list. If the latter fails then Blink will attempt to iterate through all pages for a suitable freelist. If this fails then Blink will call the coalesce function which iterates through each page looking for chunks marked free'd so they can be combined. A call to allocateFromFreeList is made immediately after. If these efforts fail then a GC cycle is triggered, a new page is allocated, and a final attempt at calling allocateFromFreeList is made.

// 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;
}

The most interesting of these paths is perhaps allocateFromFreeList. A brief look at this function shows a for loop that attempts to allocate from the first FreeListEntry in each bucket that holds allocations bigger than allocationSize. If one is found the unlink function is called followed by a call to setAllocationPoint which sets the address previously unlinked, and then a call to allocateObject is made ensuring the chunk is returned.

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;
}

If we take a quick look at the FreeListEntry class we see it inherits from HeapObjectHeader and is basically a singly linked list with an unprotected next pointer that lives inline with user data.

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;
};

The addToFreeList function confirms this is functionality. When the size of the free'd chunk is smaller than a FreeListEntry itself a HeapObjectHeader with the freelist bit set is constructed at the address. Otherwise a FreeListEntry structure is constructed at the address. This puts the m_next pointer at risk of a linear overwrite as well as the contents of the HeapObjectHeader bitfield.

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);

I've only briefly covered the slow path implemented by NormalPageArena::outOfLineAllocate but a few issues with its design are obvious. These inline meta-data values should be protected by a secret canary value that is checked before any operations are performed on both allocated and free'd chunks in this arena. I reported these issues to Google in August of 2016. Chris Palmer has done some great work getting fixes into Chrome. These types of changes can have non-trivial performance implications, so they must be designed and implemented carefully. Besides the exposed inline meta-data, one of the simpler issues to fix is the lack of randomization in allocations from the freelist. I attempted to mitigate this particular issue in PartitionAlloc in the past. Without this randomization the potential for linear overwrites targetting inline meta data is more predictable and thus more reliable.

While OilPan is missing a few mitigations such as meta data canaries, there are some protections such as guard page allocations on either side of the pages managed byNormalPageArena. And by its very nature of being a garbage collected heap, it is more difficult to perform heap feng shui techniques to create holes in the allocation patterns, and then allocate objects of our choosing at those addresses. This makes exploiting use-after-free vulnerabilities, a common vulnerability pattern in browsers, harder to exploit.