Patch-gapping is the practice of exploiting vulnerabilities in open-source software that are already fixed (or are in the process of being fixed) by the developers before the actual patch is shipped to users. This window, in which the issue is semi-public while the user-base remains vulnerable, can range from from days to months. It is increasingly seen as a serious concern, with possible in-the-wild uses detected by Google. In a previous post, we demonstrated the feasibility of developing a 1day exploit for Chrome well before a patch is rolled out to users. In a similar vein, this post details the discovery, analysis and exploitation of another recent 1day vulnerability affecting Chrome.

Background

Besides analyzing published vulnerabilities, our nDay team also identifies possible security issues while the fixes are in development. An interesting change list on chromium-review piqued our interest in mid-August. It was for an issue affecting sealed and frozen objects, including a regression test that triggered a segmentation fault. It has been abandoned (and deleted) since then in favor of a different patch approach, with work continuing under CL 1760976, which is a much more involved change.

Since the fix turned out to be so complex, the temporary solution for the 7.7 v8 branch was to disable the affected functionality. This will only be rolled into a stable release on the 10th of September, though. A similar change was made in the 7.6 branch but it came two days after a stable channel update to 76.0.3809.132, so it wasn’t included in that release. As such, the latest stable Chrome release remains affected. These circumstances made the vulnerability an ideal candidate to develop a 1day exploit for.

The commit message is descriptive, the issue is the result of the effects of Object.preventExtensions and Object.seal/freeze on the maps and element storage of objects and how incorrect map transitions are followed by v8 under some conditions. Since map handling in v8 is a complex topic, only the absolutely necessary details will be discussed that are required to understand the vulnerability. More information on the relevant topics can be found under the following links:

• Fast frozen & sealed elements in V8
• Fast properties in V8
• The story of a V8 performance cliff in React

Object Layout In v8

JS engines implement several optimizations on the property storage of objects. A common technique is to use separate backing stores for the integer keys (often called elements) and string/Symbol keys (usually referred to as slots or named properties). This allows the engines to potentially use continuous arrays for properties with integer keys, where the index maps directly to the underlying storage, speeding up access. String keyed values are also stored in an array but to get the index corresponding to the key, another level of indirection is needed. This information, among other things, is provided by the map (or HiddenClass) of the object.

The storage of object shapes in a HiddenClass is another attempt at saving storage space. HiddenClasses are similar in concept to classes in object-oriented languages. However, since it is not possible to know the property configuration of objects in a prototype-based language like JavaScript in advance, they are created on demand. JS engines only create a single HiddenClass for a given shape, which is shared by every object that has the same structure. Adding a named property to an object results in the creation of a new HiddenClass, which contains the storage details for all the previous properties and the new one, then the map of the object is updated, as shown below (figures from the v8 dev blog).

These transitions are saved in a HiddenClass chain, which is consulted when new objects are created with the same named properties, or the properties are added in the same order. If there is a matching transition, it is reused, otherwise a new HiddenClass is created and added to the transition tree.

The properties themselves can be stored in three places. The fastest is in-object storage, which only needs a lookup for the key in the HiddenClass to find the index into the in-object storage space. This is limited to a certain number of properties, others are stored in the so-called fast storage, which is a separate array pointed by the properties member of the object, as shown below.

If an object has many properties added and deleted, it can get expensive to maintain the HiddenClasses. V8 uses heuristics to detect such cases and migrate the object to a slow, dictionary based property storage, as shown on the following diagram.

Another frequent optimization is to store the integer keyed elements in a dense or packed format, if they can all fit in a specific representation, e.g. small integer or float. This bypasses the usual value boxing in the engines, which stores numbers as pointers to Number objects, thus saving space and speeding up operations on the array. V8 handles several such element kinds, for example PACKED_SMI_ELEMENTS, which denotes an elements array with small integers stored contiguously. This storage format is tracked in the map of the object and needs to be kept updated all the time to avoid type confusion issues. Element kinds are organized into a lattice, transitions are only ever allowed to more general types. This means that adding a float value to an object with PACKED_SMI_ELEMENTS elements kind will convert every value to double, set the newly added value and change the element kind to PACKED_DOUBLE_ELEMENTS.

preventExtensions, seal and freeze

JavaScript provides several ways to fix the set of properties on an object.

• Object.preventExtensions: prevents new properties from being added to the object.
• Object.seal: prevents the addition of new properties, as well as the reconfiguration of existing ones (changing their writable, enumerable or configurable attributes).
• Object.freeze: the same as Object.seal but also prevent the changing of property values, thus effectively prohibiting any change to an object.

PoC analysis

The vulnerability arises because v8 follows map transitions in certain cases without updating the element backing store accordingly, which can have wide-ranging consequences. A modified trigger with comments is shown below.

// Based on test/mjsunit/regress/regress-crbug-992914.js

function mainSeal() {
  const a = {foo: 1.1};   // a has map M1
  Object.seal(a);         // a transitions from M1 to M2 Map(HOLEY_SEALED_ELEMENTS)

  const b = {foo: 2.2};   // b has map M1
  Object.preventExtensions(b);  // b transitions from M1 to M3 Map(DICTIONARY_ELEMENTS)
  Object.seal(b);         // b transitions from M3 to M4
  const c = {foo: Object} // c has map M5, which has a tagged `foo` property, causing the maps of `a` and `b` to be deprecated
  b.__proto__ = 0;        // property assignment forces migration of b from deprecated M4 to M6

  a[5] = 1;               // forces migration of a from the deprecated M2 map, v8 incorrectly uses M6 as new map without converting the backing store. M6 has DICTIONARY_ELEMENTS while the backing store remained unconverted.
}

mainSeal();

In the proof-of-concept code, two objects, a and b are created with the same initial layout, then a is sealed and Object.preventExtensions and Object.seal is called on b. This causes a to switch a map with HOLEY_SEALED_ELEMENTS elements kind and b is migrated to slow property storage via a map with DICTIONARY_ELEMENTS elements kind.

The vulnerability is triggered in lines 10-13. Line 10 creates object c with an incompatibly typed foo property. This causes a new map with a tagged foo property to be created for c and the maps of a and b are marked deprecated. This means that they will be migrated to a new map on the next property set operation. Line 11 triggers the transition for b, Line 13 triggers it for a. The issue is that v8 mistakenly assumes that a can be migrated to the same map as b but fails to also convert the backing store. This causes a type confusion to happen between a FixedArray (the Properties array shown in the Object Layout In v8 section) and a NumberDictionary (the Properties Dict).

A type confusion the other way around is also possible, as demonstrated by another regression test in the patch. There are probably also other ways this invalid map transition could be turned into an exploitable primitive, for example by breaking assumptions made by the optimizing JIT compiler.

Exploitation

The vulnerability can be turned into an arbitrary read/write primitive by using the type confusion shown above to corrupt the length of an Array, then using that Array for further corruption of TypedArrays. These can then be leveraged to achieve arbitrary code execution in the renderer process.

FixedArray and NumberDictionary Memory Layout

FixedArray is the C++ class used for the backing store of several different JavaScript objects. It has a simple layout, shown below, with only a map pointer, a length field stored as a v8 small integer (essentially a 31-bit integer left-shifted by 32), then the elements themselves.

pwndbg> job 0x065cbb40bdf1
 0x65cbb40bdf1: [FixedDoubleArray]
 map: 0x1d3f95f414a9 
 length: 16
 0: 0.1
 1: 1
 2: 2
 3: 3
 4: 4
 …
 pwndbg> tel 0x065cbb40bdf0 25
 00:0000   0x65cbb40bdf0 -> 0x1d3f95f414a9 <- 0x1d3f95f401
 01:0008   0x65cbb40bdf8 <- 0x1000000000
 02:0010   0x65cbb40be00 <- 0x3fb999999999999a
 03:0018   0x65cbb40be08 <- 0x3ff0000000000000
 04:0020   0x65cbb40be10 <- 0x4000000000000000
 … 

The NumberDictionary class implements an integer keyed hash table on top of FixedArray. Its layout is shown below. It has four additional members besides map and length:

• elements: the number of elements stored in the dictionary.
• deleted: number of deleted elements.
• capacity: number of elements that can be stored in the dictionary. The length of the FixedArray backing a number dictionary will be three times its capacity plus the extra header members of the dictionary (four).
• max number key index: the greatest key stored in the dictionary.

The vulnerability makes it possible to set these four fields to arbitrary values in a plain FixedArray, then trigger the type confusion and treat them as header fields of a NumberDictionary.

pwndbg> job 0x2d7782c4bec9
0x2d7782c4bec9: [NumberDictionary]
- map: 0x0c48e8bc16d9 <Map>
- length: 28
- elements: 4
- deleted: 0
- capacity: 8
- elements: {
0: 0x0c48e8bc04d1 <undefined> -> 0x0c48e8bc04d1 <undefined>
1: 0 -> 16705
2: 0x0c48e8bc04d1 <undefined> -> 0x0c48e8bc04d1 <undefined>
3: 1 -> 16706
4: 0x0c48e8bc04d1 <undefined> -> 0x0c48e8bc04d1 <undefined>
5: 0x0c48e8bc04d1 <undefined> -> 0x0c48e8bc04d1 <undefined>
6: 2 -> 16707
7: 3 -> 16708
}

pwndbg> tel 0x2d7782c4bec9-1 25
00:0000   0x2d7782c4bec8 -> 0xc48e8bc16d9 <- 0xc48e8bc01
01:0008   0x2d7782c4bed0 <- 0x1c00000000
02:0010   0x2d7782c4bed8 <- 0x400000000
03:0018   0x2d7782c4bee0 <- 0x0
04:0020   0x2d7782c4bee8 <- 0x800000000
05:0028   0x2d7782c4bef0 <- 0x100000000
06:0030   0x2d7782c4bef8 -> 0xc48e8bc04d1 <- 0xc48e8bc05
...
09:0048   0x2d7782c4bf10 <- 0x0
0a:0050   0x2d7782c4bf18 <- 0x414100000000
0b:0058   0x2d7782c4bf20 <- 0xc000000000
0c:0060   0x2d7782c4bf28 -> 0xc48e8bc04d1 <- 0xc48e8bc05
...
0f:0078   0x2d7782c4bf40 <- 0x100000000
10:0080   0x2d7782c4bf48 <- 0x414200000000
11:0088   0x2d7782c4bf50 <- 0xc000000000

Elements in a NumberDictionary are stored as three slots in the underlying FixedArray. E.g. the element with the key 0 starts at 0x2d7782c4bf10 above. First comes the key, then the value, in this case a small integer holding 0x4141, then the PropertyDescriptor denoting the configurable, writable, enumerable attributes of the property. The 0xc000000000 PropertyDescriptor corresponds to all three attributes set.

The vulnerability makes all header fields of a NumberDictionary, except length, controllable by setting them to arbitrary values in a plain FixedArray, then treating them as header fields of a NumberDictionary by triggering the issue. While the type confusion can also be triggered in the other direction, it did not yield any immediately promising primitives. Further type confusions can also be caused by setting up a fake PropertyDescriptor to confuse a data property with an accessor property but these also proved too limited and were abandoned.

The capacity field is the most interesting from an exploitation perspective, since it is used in most bounds calculations. When attempting to set, get or delete an element, the HashTable::FindEntry function is used to get the location of the element corresponding to the key. Its code is shown below.

// Find entry for key otherwise return kNotFound.
template <typename Derived, typename Shape>
int HashTable<Derived, Shape>::FindEntry(ReadOnlyRoots roots, Key key,
			int32_t hash) {
	uint32_t capacity = Capacity();
	uint32_t entry = FirstProbe(hash, capacity);
	uint32_t count = 1;
	// EnsureCapacity will guarantee the hash table is never full.
	Object undefined = roots.undefined_value();
	Object the_hole = roots.the_hole_value();
	USE(the_hole);
	while (true) {
		Object element = KeyAt(entry);
		// Empty entry. Uses raw unchecked accessors because it is called by the
		// string table during bootstrapping.
		if (element == undefined) break;
		if (!(Shape::kNeedsHoleCheck && the_hole == element)) {
			if (Shape::IsMatch(key, element)) return entry;
		}
		entry = NextProbe(entry, count++, capacity);
	}
	return kNotFound;
}

The hash tables in v8 use quadratic probing with a randomized hash seed. This means that the hash argument in the code, and the exact layout of dictionaries in memory will change from run to run. The FirstProbe and NextProbe functions, shown below, are used to look for the location where the value is stored. Their size argument is the capacity of the dictionary and thus, attacker-controlled.

inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) {
	return hash & (size - 1);
}

inline static uint32_t NextProbe(uint32_t last, uint32_t number, uint32_t size) {
	return (last + number) & (size - 1);
}

Capacity is a power-of-two number under normal conditions and masking the probes with capacity-1 results in limiting the range of accesses to in-bounds values. However, setting the capacity to a larger value via the type-confusion will result in out-of-bounds accesses. The issue with this approach is the random hash seed, which will cause probes and thus out-of-bounds accesses to random offsets. This can easily results in crashes, as v8 will try to interpret any odd value as a tagged pointer.

A possible solution is to set capacity to an out-of-bounds number k that is a power-of-two plus one. This causes the FindEntry algorithm to only visit two possible locations, one at offset zero, and one at offset k (times three). With careful padding, a target Array can be placed following the dictionary, which has its length property at just that offset. Invoking a delete operation on the dictionary with a key that is the same as the length of the target Array will cause the algorithm to replace the length with the hole value. The hole is a valid pointer to a static object, in effect a large value, allowing the target Array to be used for more convenient, array-based out-of-bounds read and write operations.

While this method can work, it is nondeterministic due to the randomization and the degraded nature of the corrupted NumberDictionary. However, failure does not crash Chrome and is easily detectable; reloading the page reinitializes the hash seed so the exploit can be attempted an arbitrary number of times.

Arbitrary Code Execution

The following object layout is used to gain arbitrary read/write access to the process memory space:

• o: the object that will be used to trigger the vulnerability.
• padding: an Array that is used as padding to get the target float array at exactly the right offset from o.
• float_array: the Array that is the target of the initial length corruption via the out-of-bounds element deletion on o.
• tarr: a TypedArray used to corrupt the next typed array.
• aarw_tarr: typed array used for arbitrary memory access.
• obj_addrof: object used to implement the addrof primitive which leaks the address of an arbitrary JavaScript object.

The exploit achieves code execution by the following the usual steps after the initial corruption:

• Create the layout described above.
• Trigger the vulnerability, corrupt the length of float_array through the deletion of a property on o. Restart the exploit by reloading the page in case this step fails.
• Corrupt the length of tarr to increase reliability, since continued usage of the corrupted float array can introduce problems.
• Corrupt the backing store of aarw_tarr and use it to gain arbitrary read write access to the address space.
• Load a WebAssembly module. This maps a read-write-executable memory region of 4KiB into the address space.
• Traverse the JSFunction object hierarchy of an exported function from the WebAssembly module using the arbitrary read/write primitive to find the address of the read-write-executable region.
• Replace the code of the WebAssembly function with shellcode and execute it by invoking the function.

The complete exploit code can be found on our GitHub page and seen in action below. Note that a separate vulnerability would be needed to escape the sandbox employed by Chrome.

Detection

The exploit doesn’t rely on any uncommon features or cause unusual behavior in the renderer process, which makes distinguishing between malicious and benign code difficult without false positive results.

Mitigation

Disabling JavaScript execution via the Settings / Advanced settings / Privacy and security / Content settings menu provides effective mitigation against the vulnerability.

Conclusion

Subscribers of our nDay feed had access to the analysis and functional exploit 5 working days after the initial patch attempt appeared on chromium-review. A fix in the stable channel of Chrome will only appear in version 77, scheduled to be released tomorrow.

Malicious actors probably have capabilities based on patch-gapping. Timely analysis of such vulnerabilities allows our customers to test how their defensive measures hold up against unpatched security issues. It also enables offensive teams to test the detection and response functions within their organization.