V8 GC

Garbage Collection

V8 Garbage collection works in a way that it traverse from the root objects (that are known to be alive; referenced from globals, stack, registers etc), and mark objects that are reachable from the root, which are marked as alive. For these unmarked objects, they're considered dead and thus collectable (freed).

Generational Hypothesis

It's a hypothesis that most objects die young; if it survives a cycle, it would probably survive more. In order to take advantage of these; V8 uses two heaps for objects that fall into different categorizes.

• They are initially allocated with in the young generation heap space (Nursery)
• If they survived multiple GC cycles, they got promoted into older generations

Finding Pointers

Finding pointers are also a important questions to help us traverse the tree of object through root. How do we know I given data in the objects is just a data, or point to another object that should be traversed and considered in the traversal?

Additionally, In order to promote a GC objects, we need to find the pointer to the object. This is also useful in marking roots, update objects when moved (e.g., due to consolidations in heap).

• In V8's heap, this is implemented by having objects describe it's own layout, type-based traversing that tells V8 where to find pointers within a given object)
• In V8's stack, due to that layouts of C++ stack frames aren't explicitly defined; it's not easy to know where the pointers are, we use on of the following technique:
  • Precise Root Tracking
  • Conservative Stack Scanning

    V8 is moving from Precise Root Tracking to Conservative Stack Scanning, currently.

Precise Root Tracking:

In C++, we use Handle<T> (handle) to mark a reference to the JS Heap (e.g., Handle<Array> array = Array:New(isolate, 3); )_ This tells the GC that array is alive and should be used as a root.

• If we use direct pointer (e.g., Array array =... )_ instead, GC wouldn't know about array and could possibly free it. (could possibly results in a dangling pointers).

An advantage of doing this in this way is that, we can easily get callbacks on lifespan of the object; have these callbacks when created and destroyed. Make it easy to track their state on the tree (live references on a objects).

However, since destroying and creating these handles happens frequently, this results in a lot of runtime costs.

Internally, this handle adds a level of indirection, these handles just points entry in the handle block; which points to the actual object in the JS heap.
(These handles are destroyed, so it naturally updates the trace of roots)
Good thing is when a object is moved, only the entry in the handle block would need to be moved, we don't need to change the handle: (It really helps to move stuff!, in which it points to a slot in the Handle block first, then points to the object)

Note that this HandleScope design are pretty error prone, since it's lifetimes are tied to scopes, developers need to deal with variables that outlived the scope

Handle<Array> NewPointerArray(int x, int y, int z) {

	// Quick context, each isolate is a independent thread
	// with it's own heap, GC, etc.
	// This gets current isolate instance via TLS,
	// to know which context are we putting the array at.
	Isolate* isolate = Isolate::GetCurrent();

	// Creating a handle scope
	HandleScope handle_scope(isolate);
	handle<Array> array = Array:New(isolate, 3);

	array->Set(0, Integer::New(isolate, x));
	array->Set(1, Integer::New(isolate, y));
	array->Set(2, Integer::New(isolate, z));

	return array;
}

Like in this case, return array; would be a problem since array belongs to handle_scope, which destructor will be called at the end of this function (scope); so the burden of tracking is put on the developers.

In situations where developers know that garbage collections would not happen, they can use a direct pointer Tagged<T> instead of a handle for better performance. But this is tricky:

• When using a direct pointer when GC can occur: this leads to UAFs / Dangling pointers
• When using a handle when GC can't occur: Bad performance

Google have a static analyzer, named gcmole for detecting this sort of misuse between Handles and Handle's Scope pointer and GC behavior. But it's not perfect.

Currently (Conservative Stack scanning)

Since as we seen that using Handles can have undesirable security properties (scopes), and performances. In order to address this, V8 is moving away from Handles to use direct pointers. GC is in two different environments, the JS and the C++.

For JS context we know exactly the stack frame layout, but for C++ we don't; In which each of pointer would be treated as an potential pointer. (assuming everything is a ptr)

As we iterates C++ frame, we check each of which is pointing to a range to determine if it's a pointer. e.g., a pointer that points into the heap would be considered one (reachable).

• But what if looks like a pointer? there can be false positive. However this isn't too bad, it might only cause over-approximated.

However, in case when we're moving an object in V8's GC, it's referencers would also be updated. In this case, the value of the value that looks like a pointer would be corrupted

• Thus, this can only be used if there're a "pining" mechanism in place.

Scavenger

V8 uses Scavenger for young generation GC. It basically:

1. Label the heap into from and to spaces
   1. New allocations came from from space
2. marked objects (alive) moves to to space. This allows all new alive objects to be compactly allocated at to space.
   1. Once they're all moved, then label swaps (to to from space)

However, this moving approach is not compatible with the conservative stack approach (since it requires moving objects__). V8 taken a new mark-sweep approach. (MinorMS)

MinorMS

It basically marks alive objects; sweeps heap unmark objects. It uses a bitmap to store the location of alive objects in the heap. (for each live objects, a bit in the bitmap is set to say that there's a live object in that region of heap). We iterate these alive objects via the bitmap, we collect dead objects in between into a freelist. In which these freed objects would become FreeSpace.

For promotions, MinorMS promotes objects with page granularity. So if some objects in a given space survives some number of collection (or if less some threshold of objects was allocated in the page), that entire space gets promoted, this is how they bypass the need of moving objects.

Why?

1. Moving from Handles to direct pointers C++
2. You need to find pointers using conservative stack scanning
3. With CSS, objects referenced from the stack cannot be moved (heap alike region values causing false-positives?)
   1. By design, scavenger always move all the live objects
4. So we need a new young generation GC -> MinorMS

MinorMS is current fully supported and marked non-experimental, however still not enabled by default. Chrome previously grey-scale released MinorMS (partially released on machines), however it cause memory regression since the fragmentations of heap memories, which blocked it's full deployment. Additionally, V8 team is working on a fully pinning methodology in Scavenger.

Exploitable Issue on MinorMS: Issue 40063472

This issue happens in Array.shift method in JS, this is literally just left shifting a array (0 1 2 3 4 become 1 2 3 4). The naive way (linear time complexity) it to move every object one slot to the left, but the better way is to just move the array header one slot to the right, and update the pointer to point one step forward. (overwriting the leftest element).

However, this leaves a hole on the leftmost side of the array, which would be take place by a "Filler Object". The need of this is because the sweeper jumps from one object to the next, and they assume that the end of a object is always immediately followed by the start of another object. Since left trimming leaves a hole, it would've break the traversal, thus we need filler objects for the traversal to work.

The sweeper works by:

• Traversing the heap from object to object (marked), and freeing the space in between marked objects, which become a FreeSpace
  • These FreeSpace are also a object with map, size, and next field to organize the spaces with linked list.

map marks the shape, types of the object

SPILLSLOT is a mechanism by JIT that "overflows" the value for a register into the stack space when the register space is full. (e.g., when they need to save and de-reference an intermediate value for later, but the register space is full.)

For Issue 40063472, the problem is that when the array gets left-trimmed, the original spot that the SPILLSLOT is pointing at would become the filler object instead of the original array. However, Google's original response on that is, it's not a problem as long as the array is no longer used after that. However, what happens is that the GC might end up visiting the SPILLSLOT on the stack (Conservative Root Scanning), and end up marking the filler object wrongly pointed by the SPILLSLOT****.

function f0(1, o){
	let v17 = [];

	for (let i19 = 0; i19 < 2000; ++i19){
		v17.push(1);
		v17.push({});
		v17.shift();
	}

	vat a0 = o[0], a1 = a0, a2 = a0 //... Spill registers
	o[0] = a0 ^ a1 ^ //...
	gc()
}
var o = new Uint32Array(2)
for(let i=0, i < OUTER_ITER, I++){
	f0(i, o)
}

For the PoC, we're basically first .shift, then spilling the register, and then calling GC. Running this in the vulnerability, we would hit a DCHECK that a FreeSpace is on the marking work list. The reason why this is dangerous, is because GC have a special mechanism that frees them even when they're marked. Because FillerObject only appear when a object is shrink (wasted for some reason, should be reclaim on GC)

How we exploit that is:

1. We create a element array, pointed by the pointer on the stack.
2. The element array .shift (get's left-trimmed for a few time); so the pointer points to a bunch of filler objects.
   1. The Filler Objects still get marked by the stack, but because of that special property we talked about, they still got freed.
3. We're able to reclaim the Freed Filler Object, (but still marked__).
4. We forge a fake object that overlaps the JSArray until it's len part.
5. Once the sweeper comes alone, as we explained it jumps from objects to objects. It would jump over the fake object (since it's marked).
   1. the sweeper would would consider the end of the fake object till the start of the next marked object is freed.
   2. It would overwrites, the JSArrary, as FreeSpace (to be freed).
      1. Specifically, the FreeSpace's Map Overwrites the len field of the JS array

The difficulty here would be to manipulate the fake object's size, in order to make it just ends before the len of the JSArray.

• To do so, we spray objects with decreasing sizes.

  • We use FIXED_DOUBLE_ARRAY since they only have a map and a len field.

  • This is very ingenious since regardless where-ever the stack pointer SPILLSLOT lands, the object would always be interpreted to have the right size and end on the right position

    

By far, what this bugs is:

1. Array.shift leaves a FillerObject on the right (since leaving a hole would stop the sweeper from working properly, which works by jumping from an marked object to another.)
2. This FillerObject might be pointed by a SPILLSLOT
3. That SPILLSLOT would be marked via GC as a pointer.
4. But since it's a FillerObject, it would be freed. (so a marked object, is freed)
5. We exploit that by:
   1. Reclaiming that freed spot. (while it's still marked)
   2. We fake a object with it's len pointing before the len of the JSArray
   3. sweeper would jump based on the the len of the forged, marked object, (In which we forged that so the part of the JSArray became a part of the forged object)
   4. sweeper free the space after the size that forged object claimed to have, until next marked object; while JSArray's len is overwritten by the map of that FreedSpace.

V8 Heap Sandbox

If objects in the v8 heap are corrupted, this should only facilitate on in the v8 heap.

The primitive we mentioned previously should be restricted under the v8 heap sandbox. The v8 sandbox is design such the use of external spaces for objects that could be prone for corruption. For example, DOMPoint holds objects in a external space, in this case the blink heap. When accessing a objects that within the internal space, we don't just hold a direct pointer to the object (since this would be easily manipulated). We use a broker table for the table reference.

Embedder Field is controllable in V8 heap

c++

CppObject* GetCppObject(JSApiWrapper* wrapper) { uint32_t index = wrapper->embedder_field;

This is design such:

1. The heap sandbox points to a broker CppHeapPointerTable
2. The CppHeapPointerTable points to the. external object (Cpp pointer) in the Blink heap The worst that attackers can do is to change the index to another pointer broker.

   In the past, this could be exploited by confusing two DOM objects such that getters / setters (since they blindly lookup and resolve in the Blink Heap) can control the body of the confused objects.
   This was solved by tagging in the PointerTable, to ensure the caller methods call must belongs to the original correct type. In which became robust against such substitution attacks.

Sandbox Escape

Here's how the pointer tagging is implemented under the hood. During the entry of the construction of the CppPointerTable; The raw pointer and the tag all together; and a mark bit being unconditionally set. This mark bit is refer as black allocation.

Black Tagging

V8 uses three-color tagging for incremental GC

1. White: Not visited, would be collected after GC
2. Grey: Visited, but child objects are not all scanned
3. Black: Visited, child objects are already scanned. For newly allocated objects during the incremental GC, they're directly marked as Black to avoid being collected

   If objects are being allocated at the same time, they must be marked to a work list, or the GC can't find them. However, in this case they're unconditionally marked. And this is a security critical issue.

The problem here is that, is if:

1. We create a JS object on the v8 heap
2. Delete all references to that.
   1. Both the JS wrapper & Blink Heap object would not be marked
   2. They would be GC'ed
3. But because that the CppHeapPointerTable would be unconditionally marked, it would be marked, so it would still points to the original index (through freed) in the Blink Heap.

As attacker, we want to do to is cause a situation where the V8 heap and the blink heap object have a different type (since it's a trusted relationship, through the relationship between embedded field and tagged pointer table is not trusted). In such we:

1. re-create the former mention scenario where the CppHeapPointerTable is marked but neither is the JS wrapper and the Blink Heap object is. In which let's say the JSwrapper is typed "a"
   1. In which the CppHeapPointerTable would still be referenced the original freed slot.
2. We allocates a "B" typed JS wrapper object, then a "A" typed JS wrapper object. in which the typed "B" would take the original freed slot (that's originally pointed by the type "A" marked PointerTable)

   Note that here the original graphing of the presentation is wrong

3. We use the previous write primitive to manipulate the "A" typed V8 heap object's Embedder Field to point to the "A" typed residual PointerTable
   1. This satisfies the V8 wrapper & PointerTable tagging check: since both are the same type (type A)
   2. We since the PointerTable actually points to the type B Blink Heap Object, we have type confused.

      https://www.youtube.com/watch?v=sM2d0ciaeiI