🔗 JavaScript Garbage Collectors

In this chapter, we will discuss garbage collection as it applies to JavaScript engines. The garbage collector is an essential component of JavaScript, as it allows the language to almost completely abstract away memory management from developers.

🔗 Motivation

JavaScript explicitly allocates objects, but does not free them. For example:

JavaScript
for (let i=0; i<10000; i++) {
    let a = new Array(1000);
}

What happens to all these objects after they are no longer referenced? How does the engine know when to delete them?

We could try to implement a form of reference counting, similar to how DOM memory management works. However, this is especially difficult because of the kinds of relationships that tend to form between objects.

  • Lots of reference cycles in JSObjects
    • Dealing with "weakrefs" becomes complicated quickly
    • Significant overhead

Instead, both JSC and V8 chose to implement garbage collection strategies.

🔗 Garbage Collection

The main idea behind garbage collection is to have the engine periodically search through memory for objects that are "ready" to be freed.

The simplest method for accomplishing this is known as "Mark and Sweep":

  1. Start at a known-alive object
  2. Follow all refs
  3. Mark every object found (mark)
  4. Delete any objects not marked (sweep)

🔗 Mark and Sweep

Consider the following JavaScript Code:

JavaScript
a = {};
a.b = {};
a.b.c = a.b;

a.b = null;

Here, we've created 3 objects, created references between them, made a reference cycle between b and c, then "cut" the bc cycle in the last line:

If we were to have the garbage collector run, it would start at the root node (window) and follow all the refs it can:

window and a are found and marked, while both b and c are no longer connected. Therefore, the engine can safely free both.

🔗 Intro Garbage Collector Exercise

[open exercise]

🔗 V8 Garbage Collector - Orinoco

V8's garbage collector is called Orinoco. It features:

  • Precise root finding
  • Moving GC
  • Generational GC (old space)
  • Stop-the-world, Iterative, and Concurrent marking

🔗 V8 Orinoco - Precise Root Finding

One of the most important tasks a GC has is to find every "root" or starting node in the (often cyclic) reference graphs of JavaScript objects. If we miss a root node, not only will that node be left unmarked, but many or all of its children will also be unmarked.

This will almost always lead to a potential Use-After-Free situation. V8's solution to this problem of determining the "root set" is the Handle template.

🔗 V8 Orinoco - Handles

In the simplest terms, Handle<T> obj tells the garbage collector that obj is "alive":

C++
template <bool deferred_string_key>
JsonStringifier::Result JsonStringifier::Serialize_(Handle<Object> object,
                                                    bool comma,
                                                    Handle<Object> key) {
  Handle<Object> initial_value = object;
  ...
  if (object->IsJSReceiver() || object->IsBigInt()) {
    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
        isolate_, object, ApplyToJsonFunction(object, key), EXCEPTION);
  }
  ...
}

A contrived example of how Handle might be used:

C++
some_v8_function(args) {
    Handle<JSObject> obj = some_operation();
    ...

    // do things with the object
    ...
}

In this example, the Handle will inform the Garbage Collector that this object is 100% guaranteed to still be alive. This is because obj is a local variable, stored on the stack, which only "goes away" once the function finishes.

If a garbage collection is triggered during this time, the GC will know to use obj as a root node for marking.

Handles come with some downsides however:

  • Must convert everything to Handle<> all the time!
  • More abstraction
  • Easy to miss and cause a UAF

🔗 V8: CVE-2020-6379

This bug was caused primarily by an implicit raw pointer used in a profiling function that can trigger a GC. Normally, this was only possible with the developer console open, but it was also exposed through an origin trial (a Chrome-specific system of opting-in one's site to experimental features).

Let's take a look at the relevant code:

C++
void ProfilerListener::CodeCreateEvent(CodeEventListener::LogEventsAndTags tag,
                                       AbstractCode abstract_code,
                                       SharedFunctionInfo shared,
                                       Name script_name, int line, int column) {
  ...
  // script is stored as a pointer on the stack
  Script script = Script::cast(shared.script());
  ...
  for (...) {
    // Raw stack pointer used after GC later in loop
    int line_number = script.GetLineNumber(position) + 1;
    ...
    // Inline Stack triggers NewFixedArray allocation, which may cause GC
    it.source_position().InliningStack(handle(code, isolate_));
  }
  ...
}

// `Script script` is an instance of HeapObject, which is really a pointer!
class HeapObject : public Object { ... }
class Object : public TaggedImpl<HeapObjectReferenceType::STRONG, Address> { ... }

This is a real world example of a GC "missing" an object because it was not aware of it. If we take a look at the patch fixing the issue:

diff
-  if (shared.script().IsScript()) {
-    Script script = Script::cast(shared.script());
+  if (shared_handle->script().IsScript()) {
+    Handle<Script> script =
+        handle(Script::cast(shared_handle->script()), isolate_);

We can see that correctly wrapping the script variable with Handle fixes the issue.

For full details see the Chromium Bug Tracker.

🔗 Moving GC

V8 uses a "Moving Garbage Collector", which means that objects may be moved around in memory after a GC runs, and their references updated to the new location. This feature also heavily relies on Handle, as neglecting to wrap an object with Handle can lead to a dangling pointer if the object is moved.

For this concept to work, V8 divides the heap into two sections:

  • From Space
  • To Space

New objects get placed in "From Space" when they are allocated:

The GC marks the elements within From Space:

At this point, instead of individually calling free() on all unmarked objects, the Garbage Collector moves these objects to To Space:

Once all marked objects have been moved, only "dead" objects will remain in From Space, which can be marked empty as one big chunk. This makes reclaiming memory significantly faster.

Note that once objects are moved, the roles of From Space and To Space are reversed. That is, To Space becomes the new From Space for servicing object allocations, and similarly the old From Space will be To Space the next time the GC runs.

🔗 Generational GC

V8's GC is also Generational, meaning it records how long objects are alive. This allows for heuristics that improve performance. The main idea behind Generational GCs is to skip objects if they have remained "alive" for some period of time, which reduces the cost of a "regular" GC. Then, under memory pressure, a full GC can be performed to collect any leaks that have accumulated.

V8 creates a separate heap, called Old Space, for long-lived objects:

  • Objects are moved here if they survive 2 GC cycles
  • Acts as 'storage' for long-lived objects
  • Mark and Sweep is performed less frequently

We can pick up where we left off with our example from the previous section. As we can see, the young generation is starting to become populated:

At some point, the GC will run and mark "living" objects in From Space:

Finally, those objects that have survived both "rounds" of garbage collection are promoted to Old Space instead of moved to To Space.

"Old" objects are more likely than not to continue "living" for a long time, so Old Space is GC'd less frequently.

🔗 Marking Strategies: Stop-The-World

So far, we have been describing an approach known as "Stop-The-World" when discussing the "mark" stage of garbage collection. It is straightforward and safe by default:

  • Program execution pauses
  • Garbage Collector runs, marks, and sweeps
  • Program execution resumes

Of course, the downside is that this approach is slow and can even cause noticeable "pauses" in execution.

🔗 Marking Strategies: Iterative

To improve on performance, we could try to perform the GC in small steps:

  • Stop program execution
  • Mark a few objects
  • Continue program execution
  • Later, stop the program again and pick up where marking left off

Overall, this causes less noticeable pauses in execution, but comes at the cost of potentially leading to exploitable issues:

New objects created between iterations may be missed and freed:

JavaScript
a = {};
a.b = {};
a.b.c = {};

Here we create some objects, and we'll start an iterative GC run:

Here, we've started an iterative run and marked some objects. Let's assume execution resumes and the following code runs:

JavaScript
a = {};
a.b = {};
a.b.c = {};
// --- First GC Iteration ---
a.d = {};

We've added d as a property of a. Our reference graph looks like this:

However, consider what happens when we resume our iterative garbage collection! It will resume at node b, and run down to the bottom of the graph, never finding the newly created property d:

This can cause the GC to free or move d incorrectly!

🔗 Marking Strategies: Iterative - Write Barriers

In general, Garbage Collectors use "Write Barriers" to solve this problem. A "Write Barrier" is a term used for code that runs when a particular location is written to. For example, let's take a look at PropertyArray::set:

C++
void PropertyArray::set(int index, Object value) {
  ...
  int offset = OffsetOfElementAt(index);
  RELAXED_WRITE_FIELD(*this, offset, value);
  WRITE_BARRIER(*this, offset, value);
}

And the associated WRITE_BARRIER definition:

C++
#define WRITE_BARRIER(object, offset, value)                        \
  do {                                                              \
    DCHECK_NOT_NULL(GetHeapFromWritableObject(object));             \
    MarkingBarrier(object, (object)->RawField(offset), value);      \
    GenerationalBarrier(object, (object)->RawField(offset), value); \
  } while (false)

This code would be triggered when a property is set. In our previous example, when property d was added to a, this code would have ran and informed the GC to mark d.

This helps eliminate most cases where references can be added but "skipped over" due to the iterative approach.

🔗 Marking Strategies: Concurrent

This strategy involves running the GC in a separate thread to eliminate the need for pauses in execution.

Concurrent GC has the same issues as the iterative approach, but the nature of running concurrently makes it even more critical to use Write Barriers whenever an object is created or changed. To prevent race conditions, marking and write-barriers must be atomic.

🔗 V8 Scavenging / Major GC

There are two conceptual "modes" that the V8 GC can run in.

First, there is "Scavenging", which focuses on being fast. This mode is used for the smaller "Garbage Collects" that happen solely on young objects in From Space.

On the other hand, a Major GC scans the entire heap (i.e. including Old Space). This is slower, as it includes the "full scope" of features available for scanning and moving memory:

🔗 JavaScriptCore Garbage Collection

JSC's garbage collector is known as Riptide, which was introduced to the project in 2017.

Riptide uses the following approaches in order to achieve its goals:

  • Conservative root finding
  • Generational GC (sticky marks)
  • Concurrent marking

As we can see, there is some overlap with V8 (Generational, Concurrent), and the "big picture goal" is identical as well.

🔗 Riptide (JSC) Concurrent Marking

Riptide runs concurrently to the rest of the engine while marking JavaScript objects (although it can stop execution or use locks for certain complex operations). This means that the caveats we discussed previously for an iterative approach apply. That is, the need for write barriers.

In Orinoco, a write barrier resulting from object.field = value tells the GC to mark and scan value. Riptide instead uses a "Retreating Wavefront" strategy, where a write barrier tells the GC to "retreat" and revisit object:

  • Write-Barrier indicates object needs to be revisited
  • GC eventually revisits object and ends up finding value to mark

To avoid racing with the marking threads, special care must be taken to ensure that indicating the revisit occurs after the field is written, using a memory fence of some sort.

🔗 JSC CVE-2018-4192

This is a real-world example of a race condition arising from Riptide's concurrent nature, leading to a Use-After-Free. It was discovered by us (RET2) for Pwn2Own 2018.

Specifically, the vulnerability was in Array.prototype.reverse.

Can you spot the bug?

C++
EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState* exec)
{
    ...
    case ALL_CONTIGUOUS_INDEXING_TYPES:
    case ALL_INT32_INDEXING_TYPES: {
        auto& butterfly = *thisObject->butterfly();
        if (length > butterfly.publicLength())
            break;
        auto data = butterfly.contiguous().data();
        std::reverse(data, data + length);
        return JSValue::encode(thisObject);
    }
    ...
}

The critical "bug" here occurs with the std::reverse call. Imagine we have an array of 100 objects, and a garbage collection runs:

  • The first 50 objects are marked as "alive" on a marking thread
  • On the main JS thread, .reverse() is called on the array
  • The last 50 objects (never marked) are now at the start of the array
    • The already-marked first 50 are now the last 50
  • The marking thread resumes at the 51st object, seeing and marking the first 50 objects again
  • The last 50 objects are incorrectly freed as they were never visited/marked

This is depicted by the diagram below:

This vulnerability was fixed by adding a write-barrier to the object being reversed. That way, when garbage collection "resumes", it will know to check the swapped objects:

diff
        auto data = butterfly.contiguous().data();
        std::reverse(data, data + length);
+       if (!hasInt32(thisObject->indexingType()))
+           vm.heap.writeBarrier(thisObject);
        return JSValue::encode(thisObject);

We also wrote extensive blogposts on discovering, analyzing, and exploiting this bug:

🔗 JSC Wasm Missing Write Barrier

This is another example of a missing write-barrier leading to exploitable UAF scenarios.

For this bug, a write barrier was missing when expanding and adding entries to a Wasm (Web Assembly) table. A Wasm Table is essentially an array of function or object references.

When a table is expanded, a specified default value (e.g. a JS object) is written into the new slots. Since the table object has been modified, a write barrier should be used to indicate a potential revisit.

C++
std::optional<uint32_t> Table::grow(uint32_t delta, JSValue defaultValue) 
    ...
    auto checkedGrow = [&] (auto& container, auto initializer) {
        ...
        for (uint32_t i = m_length; i < allocatedLength(newLength); ++i) {
            initializer(container.get()[i]);
        }
    };
    if (!checkedGrow(m_jsValues, [defaultValue] (WriteBarrier<Unknown>& slot) { 
        slot.setStartingValue(defaultValue); 
    }))
        return std::nullopt;
    ...
}

// slot.setStartingValue does not emit a write barrier!
// (compare to set, which does)
template <typename T, typename Traits> class WriteBarrierBase {
    void setStartingValue(JSValue value) { m_value = JSValue::encode(value); }
    void WriteBarrierBase<...>::set(VM& vm, const JSCell* owner, JSValue value)
    {
        m_value = JSValue::encode(value);
        vm.heap.writeBarrier(owner, value);
    }
}

Without the barrier, the object added into the table may be missed during marking and incorrectly freed. Just like the previous bug, this can lead to a UAF of an arbitrary JavaScript object.

Below is an annotated proof-of-concept to UAF a JSArray:

JavaScript
let wasm_data = await load_file('mod.wasm'); // Simple mod with table of refs
let mod = new WebAssembly.Module(wasm_data);
// Table of references to js objects
let table = new WebAssembly.Table({element:"externref", initial:0});
let inst = new WebAssembly.Instance(mod, {e:{table:table}});

// GC will set the table's sticky mark
// (so non-full gc won't revisit table)
gc();
for (let i=0; i<0x100; i++) {
    // Expand table with default js refs
    // However this fails to trigger a write barrier
    inst.exports.table.grow(1, new Array(4))

    // Since the table is now sticky marked, further collection will
    // ignore the table + new refs (no WB triggered) -> UAF of JSArray
    for (let j = 0; j < i+1; j++) {
        if (inst.exports.table.get(j).length !== 4) {
            print('length 0x' + inst.exports.table.get(j).length.toString(16))
            //length: 0xbadbeef0
            // We now have OOB length!
        }
    }
}

If we look at the patch, we can see that slot.set() is now used to place default values into the table, which triggers a write barrier:

diff
@@ -123,13 +123,14 @@ std::optional<uint32_t> Table::grow(uint32_t delta, JSValue defaultValue)

+    VM& vm = m_owner->vm();
-    if (!checkedGrow(m_jsValues, [defaultValue] (WriteBarrier<Unknown>& slot) {
-        slot.setStartingValue(defaultValue); 
+    if (!checkedGrow(m_jsValues, [&](WriteBarrier<Unknown>& slot) {
+        slot.set(vm, m_owner, defaultValue);
     }))
         return std::nullopt;

🔗 Conservative Garbage Collection

You may have noticed that JSC uses "Conservative" root-finding, which is distinct from V8's "precise root finding". Instead of using Handle to inform the GC of objects, JSC scans the stack for pointers:

  • Look for any valid pointers to JS objects
  • Use these objects as roots for the mark and sweep

Since Riptide is concurrent, it must stop execution while it scans the stack:

  • Would be dangerous to race stack changes while scanning
  • Too complex/pointless to do write barriers on the stack

There are several downsides to this approach. Raw pointers that are not stored on the stack will be missed, and there is also the potential for false positives: non-pointer values that happen to "look like" a valid address. There is also the possibility of using these 'false positives' as a side channel:

  • Attacker controls a qword --> can tell if it is a valid heap pointer

This article talks about potentially breaking ASLR using side channels.

Additionally, conservative scanning skips the C/C++ Heap, the DOM Heap, data section, etc. If a reference is kept in any of those, a UAF can occur.

🔗 JSC CVE-2017-2491

This vulnerability is an example of a pointer being stored "out of sight" of the JavaScript garbage collector and resulting in a Use-After-Free in JSC::CachedCall.

This bug was used by Samuel Groß and Niklas Baumstark of phoenhex, you can read their full write up here.

Let's take a quick look at some relevant code:

C++
namespace JSC {
    class CachedCall {
    private:
        bool m_valid;
        Interpreter* m_interpreter;
        VM& m_vm;
        VMEntryScope m_entryScope;
        ProtoCallFrame m_protoCallFrame;
        Vector<JSValue> m_arguments;
        CallFrameClosure m_closure;
    };
}

Specifically, Vector<JSValue> m_arguments is concerning. The Vector<JSValue> backing data is stored on the C++ heap, which the GC has no visibility into. Any objects stored in this vector have the potential to be missed by the GC and freed, causing a UAF.

The fix for this issue was to change Vector<JSValue> to MarkedArgumentBuffer. Functionally, these two are nearly identical, but MarkedArgumentBuffer informs the GC of its contents.

🔗 Sticky Marks

Earlier, it was mentioned that Riptide implements a generational GC, somewhat like V8 does.

Riptide accomplishes this with the concept of 'Sticky Marks.' The idea is to mark objects as "sticky", but not to clear this mark when done with a GC cycle. When there is low or no memory pressure, a fast "Eden" garbage collection runs. This ignores all objects with the "sticky" mark unless they explicitly triggered a write-barrier.

This shifts attention to "young" objects that are more likely to pop in and out of existence.

🔗 Triggering GC Exercise

[open exercise]

🔗 Freed Objects

A final note on Garbage Collection: both V8 and JSC do not clear object memory when objects are freed. All of the underlying data is still there, the memory is simply marked as available to use.

The only exception is that JSC does overwrite the structure ID field with a "nuked" bit, which distinguishes it as explicitly invalid.

🔗 Summary

JavaScript engines employ many different strategies to efficiently perform garbage collection

  • Generations, Root Finding, Iterative / Concurrent, Moving

There are many vulnerability patterns that stem from these GCs

  • Missing handles
  • Missed conservative roots
  • Missing write barriers
  • Race Conditions