Let me introduce the root cause of CVE-2020-6418 in Chrome’s V8 JavaScript engine.
Settings
# install depot_tools
cd ~
git clone https://chromium.googlesource.com/chromium/tools/depot_tools.git
export PATH=$HOME/depot_tools:$PATH
echo 'export PATH=$HOME/depot_tools:$PATH' >> ~/.zshrc
# get V8
cd ~
mkdir v8
cd v8
fetch v8
cd v8
git checkout bdaa7d66a37adcc1f1d81c9b0f834327a74ffe07
# build V8
gclient sync -D
sudo apt install -y python ninja-build
build/install-build-deps.sh
./tools/dev/gm.py x64.release
Backgrounds
To explain the root cause, I will first introduce the essential concepts needed for better understanding.
Map Inference
Map inference in V8 is the process of inferring the map, or type, of an object during the optimization phase.
The reason for this process is that V8 handles JavaScript, a dynamic language, where the map of an object can change at runtime.
At this point, continuously updating the map information is essential to perform or maintain optimization.
Let’s take a look at an example.
(To use debug commands in V8, you must enable the –allow-natives-syntax option.
Examples of debug commands include: %DebugPrint(), %SystemBreak(), and others.)
Currently, it can be confirmed that the array is of the SMI type.
At this point, if the value at the 0th index of the array is changed to 1.1, you can observe that the map, which was previously of the SMI type, is updated to DOUBLE.
(In V8, this is part of a broader concept known as type transition.)
The results inferred by Map Inference can fall into one of the following two categories:
/* src/compiler/map-inference.h */
// The MapInference class provides access to the "inferred" maps of an
// {object}. This information can be either "reliable", meaning that the object
// is guaranteed to have one of these maps at runtime, or "unreliable", meaning
// that the object is guaranteed to have HAD one of these maps.
//
// The MapInference class does not expose whether or not the information is
// reliable. A client is expected to eventually make the information reliable by
// calling one of several methods that will either insert map checks, or record
// stability dependencies (or do nothing if the information was already
// reliable).
- Reliable: If there is no possibility of the map changing at runtime, it is returned as reliable.
- Unreliable: If there is a possibility of the map changing at runtime, it is returned as unreliable.
In V8, there is a node called MapChecks, and its role is to verify the map of an object that contains this node at runtime.
In the case of reliable, as mentioned earlier, there is no possibility of the map changing. Therefore, if the routine were to recheck the map, it would result in performance degradation.
To address this, objects marked as reliable do not have a MapChecks node inserted, thereby optimizing performance.
For unreliable objects, map verification is necessary for optimization because the map might change at runtime.
To handle this, MapChecks nodes are inserted for unreliable objects, ensuring that the map is checked at runtime.
This allows the system to maintain optimization despite the potential for map changes.
Receiver
In JavaScript, the receiver refers to the object that is the target of a function call. For example, when calling arr.pop() on an array arr, the receiver of the pop() function is arr.
Receiver
ex) arr.pop() -> pop()
Sea of nodes
Sea of Nodes is a technique used by V8’s TurboFan for optimization. It represents all operations and data in a program as nodes in a graph-based Intermediate Representation (IR).
For example, if the JavaScript code is as follows:
let a = 10;
let b = 20;
let c = a + b;
console.log(c);
When represented using the Sea of Nodes, it would look like this:
a = 10 -> node 1
b = 20 -> node 2
c = a + b -> node 3 (Node 1 and Node 2 dependencies)
console.log(c) -> node 4(dependent on Node 3)
This is a way of representing the results as dependencies between nodes.
The basic operational sequence of the Sea of Nodes is as follows.
1.Front-End: Converts JavaScript source code into bytecode, and then transforms it into an Intermediate Representation (IR) that TurboFan can understand.
2.Sea of Nodes Graph Creation: Represents all operations and values as nodes, forming a graph. This graph is unordered and solely depicts the dependency relationships between nodes.
3.Optimization: Performs various optimizations, such as constant folding, common subexpression elimination, dead code elimination, and loop optimization.
4.Back-End: Generates machine code based on the optimized node graph.
Effect chain
In the Effect Chain of the Sea of Nodes, the portion that connects the transformation process of a function is referred to as the function’s Effect Chain.
The transformations mentioned here encompass all operations during runtime that can alter the map of an object or array due to structural or state changes.
Examples of Transformation Processes:
Adding or removing elements in an array
Resizing an array
Changing the type of elements in an array
Adding or removing properties of an object
Changing the type of an object’s property
Modifying the prototype of an object
Declaring variables and optimizing their usage
※Many more such transformations exist.
patch1
The patch for this vulnerability consists solely of the addition of the red line shown in the diagram. (The specific location is in the InferReceiverMapsUnsafe() function, where the JSCreate node is processed.)
For now, we will simply note this and move on; the explanation will be revisited after discussing the root cause in detail.
Root cause
// static
NodeProperties::InferReceiverMapsResult NodeProperties::InferReceiverMapsUnsafe(
JSHeapBroker* broker, Node* receiver, Node* effect,
ZoneHandleSet<Map>* maps_return) {
HeapObjectMatcher m(receiver);
if (m.HasValue()) {
HeapObjectRef receiver = m.Ref(broker);
// We don't use ICs for the Array.prototype and the Object.prototype
// because the runtime has to be able to intercept them properly, so
// we better make sure that TurboFan doesn't outsmart the system here
// by storing to elements of either prototype directly.
//
// TODO(bmeurer): This can be removed once the Array.prototype and
// Object.prototype have NO_ELEMENTS elements kind.
if (!receiver.IsJSObject() ||
!broker->IsArrayOrObjectPrototype(receiver.AsJSObject())) {
if (receiver.map().is_stable()) {
// The {receiver_map} is only reliable when we install a stability
// code dependency.
*maps_return = ZoneHandleSet<Map>(receiver.map().object());
return kUnreliableReceiverMaps;
}
}
}
InferReceiverMapsResult result = kReliableReceiverMaps;
while (true) {
switch (effect->opcode()) {
case IrOpcode::kMapGuard: {
Node* const object = GetValueInput(effect, 0);
if (IsSame(receiver, object)) {
*maps_return = MapGuardMapsOf(effect->op());
return result;
}
break;
}
case IrOpcode::kCheckMaps: {
Node* const object = GetValueInput(effect, 0);
if (IsSame(receiver, object)) {
*maps_return = CheckMapsParametersOf(effect->op()).maps();
return result;
}
break;
}
case IrOpcode::kJSCreate: {
if (IsSame(receiver, effect)) {
base::Optional<MapRef> initial_map = GetJSCreateMap(broker, receiver);
if (initial_map.has_value()) {
*maps_return = ZoneHandleSet<Map>(initial_map->object());
return result;
}
// We reached the allocation of the {receiver}.
return kNoReceiverMaps;
}
break;
}
This section pertains to the content of the InferReceiverMapsUnsafe() function, where the patch was applied.
Within the function, the switch (effect->opcode()) statement categorizes the type of effect and proceeds with the code accordingly.
However, since the patch specifically targets the part handling JSCreate, we will focus solely on that portion for further examination.
NodeProperties::InferReceiverMapsResult NodeProperties::InferReceiverMapsUnsafe(
JSHeapBroker* broker, Node* receiver, Node* effect,
ZoneHandleSet<Map>* maps_return) {
...
InferReceiverMapsResult result = kReliableReceiverMaps;
while (true) {
switch (effect->opcode()) {
...
}
// Stop walking the effect chain once we hit the definition of
// the {receiver} along the {effect}s.
if (IsSame(receiver, effect)) return kNoReceiverMaps;
// Continue with the next {effect}.
DCHECK_EQ(1, effect->op()->EffectInputCount());
effect = NodeProperties::GetEffectInput(effect);
}
}
To explain the function’s details, the InferReceiverMapsUnsafe() function’s role is to trace back the effect chain to infer the map of the receiver.
By examining the parameters of the InferReceiverMapsUnsafe() function, we can identify the receiver and effect concepts studied earlier.
The receiver passed as a parameter refers to the node for which the map is to be inferred, and the effect refers to the node from which the exploration begins.
The function returns a total of three possible outcomes, as follows.
/* src/compiler/node-properties.h */
// Walks up the {effect} chain to find a witness that provides map
// information about the {receiver}. Can look through potentially
// side effecting nodes.
enum InferReceiverMapsResult {
kNoReceiverMaps, // No receiver maps inferred.
kReliableReceiverMaps, // Receiver maps can be trusted.
kUnreliableReceiverMaps // Receiver maps might have changed (side-effect).
};
kNoReceiverMaps is returned when the receiver’s map cannot be inferred.
kReliableReceiverMaps is returned when the receiver’s map is stable and can be trusted not to change.
kUnreliableReceiverMaps is returned when the receiver’s map has changed or is likely to change.
Below is the part of the code that processes JSCreate, where the vulnerability exists.
NodeProperties::InferReceiverMapsResult NodeProperties::InferReceiverMapsUnsafe(
JSHeapBroker* broker, Node* receiver, Node* effect,
ZoneHandleSet<Map>* maps_return) {
...
InferReceiverMapsResult result = kReliableReceiverMaps;
while (true) {
switch (effect->opcode()) {// Check what the effect is
...
case IrOpcode::kJSCreate: { // If it's a JSCreate node, execute the following code
if (IsSame(receiver, effect)) { // If receiver equals effect, attempt to fetch the receiver's initial map
base::Optional<MapRef> initial_map = GetJSCreateMap(broker, receiver);
if (initial_map.has_value()) {
*maps_return = ZoneHandleSet<Map>(initial_map->object());
return result; // Return the result
}
// We reached the allocation of the {receiver}.
return kNoReceiverMaps; // If the initial map could not be fetched, return kNoReceiverMaps
}
break;
}
...
}
...
}
}
In the part (IsSame(receiver, effect)), if receiver equals effect, the routine to fetch the initial map of the receiver is executed.
If they are not the same, the code below is executed.
// Continue search for receiver map outside the loop. Since operations
// inside the loop may change the map, the result is unreliable.
effect = GetEffectInput(effect, 0);
result = kUnreliableReceiverMaps;
continue;
This code is part of the Effect Chain Loop, located at /src/compiler/node-properties.cc, starting from line 443.
The code executes when the receiver and effect are not the same and continues running until they match.
When the receiver and effect are not equal, it indicates that the effect chain has not yet been fully traversed, meaning there is still more to trace back.
This implies that there might be other effects in the chain where the map could have been changed, so all effects must be checked.
As a result, if the receiver and effect are not equal, this loop is executed to continue traversing the chain until all potential changes to the map are verified.
The InferReceiverMapsUnsafe() function is called from the constructor of the MapInference class, as shown in the following code:
MapInference::MapInference(JSHeapBroker* broker, Node* object, Node* effect)
: broker_(broker), object_(object) {
ZoneHandleSet<Map> maps;
auto result =
NodeProperties::InferReceiverMapsUnsafe(broker_, object_, effect, &maps); // Retrieve the result of the InferReceiverMapsUnsafe() function.
maps_.insert(maps_.end(), maps.begin(), maps.end()); // // Store the returned maps.
maps_state_ = (result == NodeProperties::kUnreliableReceiverMaps) // Check the state of the returned maps and handle it as kUnreliableDontNeedGuard or kReliableOrGuarded.
? kUnreliableDontNeedGuard
: kReliableOrGuarded;
DCHECK_EQ(maps_.empty(), result == NodeProperties::kNoReceiverMaps);
}
The map_state section processes values based on the return result of the InferReceiverMapsUnsafe() function.
When the result is kUnreliableReceiverMaps, it is categorized as either kUnreliableDontNeedGuard or kReliableOrGuarded. Below is an explanation of these states and their reasoning:
kUnreliableDontNeedGuard
This state indicates that while the Map may change, a runtime check (Guard) is not necessary for safe execution.
Meaning:
The Map might change, but the change does not impact the computation results.
This allows the program to safely proceed without adding additional runtime checks.
Reason:
The purpose of this approach is to maximize performance by avoiding unnecessary Guards.
Even though the Map could change, the impact on the optimized code is considered negligible, and the risk is deemed acceptable.
kReliableOrGuarded
This state indicates that the Map is either stable or can be made stable by adding a runtime check (Guard) to ensure safety.
Meaning:
The Map is trusted to remain unchanged or,
A Guard is added to monitor and ensure the Map’s stability during runtime.
Reason:
When there is potential for the Map to change in a way that could affect the computation results, adding a Guard ensures correctness.
This state strikes a balance between performance and reliability by providing safeguards when necessary.
kUnreliableDontNeedGuard refers to a state where the map might change, but it is considered safe not to add runtime checks (Guard).
Let’s make it easier to understand with an example.
Cases Where Map Changes Are Harmless
1.
let arr = [1, 2, 3];
Object.defineProperty(arr, 'custom', { value: 42 }); // Map changes
arr.pop(); // Removes the last element of the array (works correctly regardless of the map change)
Whether the second line exists or not, the last element of the arr array is still removed.
This means that even if the map changes, the result remains the same. Therefore, the map change is deemed harmless.
2.
let obj = { a: 1, b: 2 };
Object.defineProperty(obj, 'c', { value: 3, writable: false }); // Map changes
console.log(obj.a + obj.b); // 1 + 2 = 3 (works correctly regardless of the map change)
When adding and printing a and b, it doesn’t matter whether c is added or not.
Thus, the map change is considered harmless.
※ There are other examples, but since this is not the main focus, they are omitted.
In the case as described above
maps_state_ = (result == NodeProperties::kUnreliableReceiverMaps)
? kUnreliableDontNeedGuard
: kReliableOrGuarded;
The map_state can be set to kUnreliableDontNeedGuard.
Map inference is mainly performed during the optimization process in the Inlining phase, and JSCallReducer is responsible for optimizing function calls.
For example, the code that performs map inference in the ReduceArrayPrototypePop() function, which optimizes Array.prototype.pop(), is as follows.
Reduction JSCallReducer::ReduceArrayPrototypePop(Node* node) {
...
Node* receiver = NodeProperties::GetValueInput(node, 1);
Node* effect = NodeProperties::GetEffectInput(node);
Node* control = NodeProperties::GetControlInput(node);
MapInference inference(broker(), receiver, effect); //create inference
if (!inference.HaveMaps()) return NoChange();
MapHandles const& receiver_maps = inference.GetMaps();
std::vector<ElementsKind> kinds;
if (!CanInlineArrayResizingBuiltin(broker(), receiver_maps, &kinds)) {
return inference.NoChange();
}
if (!dependencies()->DependOnNoElementsProtector()) UNREACHABLE();
inference.RelyOnMapsPreferStability(dependencies(), jsgraph(), &effect, //call the function RelyOnMapsPreferStability()
control, p.feedback());
...
}
This shows a call to the inference function called RelyOnMapsPreferStability()
The content of the function is as follows.
bool MapInference::RelyOnMapsPreferStability(
CompilationDependencies* dependencies, JSGraph* jsgraph, Node** effect,
Node* control, const FeedbackSource& feedback) {
CHECK(HaveMaps());
if (Safe()) return false; // The insertion of the check node depends on the result of the safe() function.
if (RelyOnMapsViaStability(dependencies)) return true;
CHECK(RelyOnMapsHelper(nullptr, jsgraph, effect, control, feedback)); //The part where the check node is inserted
return false;
}
The insertion of the Mapchecks node in the following RelyOnMapsHelper() function is determined based on the result returned by the safe() function.
The content of the safe() function is as follows:
bool MapInference::Safe() const { return maps_state_ != kUnreliableNeedGuard; }
If we break down the process up to the RelyOnMapsPreferStability() function, when maps_state = kUnreliableNeedGuard, safe() returns false due to the if (Safe()) return false; part,
and then the following Mapchecks section is executed, causing the map to be checked at runtime.
On the other hand, if maps_state != kUnreliableNeedGuard, safe() returns true, and the if (Safe()) return false; statement returns false, meaning the Mapchecks section is not executed.
In other words, the Mapchecks node is not inserted.
The important point here is that map_state is classified into two categories.
maps_state_ = (result == NodeProperties::kUnreliableReceiverMaps)
? kUnreliableDontNeedGuard
: kReliableOrGuarded;
That is, in the case of kReliableOrGuarded, the Mapchecks node is not inserted.
The fact that the Mapchecks node is not inserted means that at runtime, even if the Map of the object changes, we won’t be able to know about it.
To explain this further:
V8 handles object reads differently based on the type of the map.
Below is the layout of the V8 Map.
// Map layout:
// +---------------+------------------------------------------------+
// | _ Type _ | _ Description _ |
// +---------------+------------------------------------------------+
// | TaggedPointer | map - Always a pointer to the MetaMap root |
// +---------------+------------------------------------------------+
// | Int | The first int field |
// `---+----------+------------------------------------------------+
// | Byte | [instance_size] |
// +----------+------------------------------------------------+
// | Byte | If Map for a primitive type: |
// | | native context index for constructor fn |
// | | If Map for an Object type: |
// | | inobject properties start offset in words |
// +----------+------------------------------------------------+
// | Byte | [used_or_unused_instance_size_in_words] |
// | | For JSObject in fast mode this byte encodes |
// | | the size of the object that includes only |
// | | the used property fields or the slack size |
// | | in properties backing store. |
// +----------+------------------------------------------------+
// | Byte | [visitor_id] |
// +----+----------+------------------------------------------------+
// | Int | The second int field |
// `---+----------+------------------------------------------------+
// | Short | [instance_type] |
// +----------+------------------------------------------------+
// | Byte | [bit_field] |
// | | - has_non_instance_prototype (bit 0) |
// | | - is_callable (bit 1) |
// | | - has_named_interceptor (bit 2) |
// | | - has_indexed_interceptor (bit 3) |
// | | - is_undetectable (bit 4) |
// | | - is_access_check_needed (bit 5) |
// | | - is_constructor (bit 6) |
// | | - has_prototype_slot (bit 7) |
// +----------+------------------------------------------------+
// | Byte | [bit_field2] |
// | | - new_target_is_base (bit 0) |
// | | - is_immutable_proto (bit 1) |
// | | - unused bit (bit 2) |
// | | - elements_kind (bits 3..7) |
// +----+----------+------------------------------------------------+
// | Int | [bit_field3] |
// | | - enum_length (bit 0..9) |
// | | - number_of_own_descriptors (bit 10..19) |
// | | - is_prototype_map (bit 20) |
// | | - is_dictionary_map (bit 21) |
// | | - owns_descriptors (bit 22) |
// | | - is_in_retained_map_list (bit 23) |
// | | - is_deprecated (bit 24) |
// | | - is_unstable (bit 25) |
// | | - is_migration_target (bit 26) |
// | | - is_extensible (bit 28) |
// | | - may_have_interesting_symbols (bit 28) |
// | | - construction_counter (bit 29..31) |
// | | |
// +****************************************************************+
// | Int | On systems with 64bit pointer types, there |
// | | is an unused 32bits after bit_field3 |
// +****************************************************************+
// | TaggedPointer | [prototype] |
// +---------------+------------------------------------------------+
// | TaggedPointer | [constructor_or_backpointer_or_native_context] |
// +---------------+------------------------------------------------+
// | TaggedPointer | [instance_descriptors] |
// +****************************************************************+
// ! TaggedPointer ! [layout_descriptors] !
// ! ! Field is only present if compile-time flag !
// ! ! FLAG_unbox_double_fields is enabled !
// ! ! (basically on 64 bit architectures) !
// +****************************************************************+
// | TaggedPointer | [dependent_code] |
// +---------------+------------------------------------------------+
// | TaggedPointer | [prototype_validity_cell] |
// +---------------+------------------------------------------------+
// | TaggedPointer | If Map is a prototype map: |
// | | [prototype_info] |
// | | Else: |
// | | [raw_transitions] |
// +---------------+------------------------------------------------+
Therefore, the way fields are read differs depending on whether the type is SMI or Double.
This means that if an object initially had an SMI Map but its Map changes to Double via Jscreate at runtime, TurboFan won’t be aware of the change due to the absence of the Mapchecks node.
As a result, the value, which is set as Double, may be accessed as if it were an SMI, leading to Type Confusion.
patch2
In the patch section, the line result = kUnreliableReceiverMaps; was added to allow checking the Map once again.
Reference
https://cwresearchlab.co.kr/entry/CVE-2020-6418-Incorrect-side-effect-modelling-for-JSCreate
Comments