google / google/leveldb

Block entry bounds check wraps around: 2 GiB out-of-bounds read in Block::Iter::ParseNextKey

Open Beginner friendly
#1,348 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
39.4k
Forks
8.2k
PR merge metrics
No merged PRs in 30d

Description

`DecodeEntry` (table/block.cc:71 at HEAD 7ee830d) validates a block entry with:

```cpp
if (static_cast(limit - p) < (*non_shared + *value_length)) {
return nullptr;
}
```

The sum `*non_shared + *value_length` is computed in `uint32_t` and wraps around. A crafted entry with `non_shared = 0x80000000` and `value_length = 0x80000001` sums to 1, passes the check, and `Block::Iter::ParseNextKey` then executes `key_.append(p, 0x80000000)` (table/block.cc:269) — reading 2 GiB starting from inside the (small) block buffer.

**Reproduction** (105-byte crafted SSTable, no fuzzing required):

- data block contents: entry `[shared=0][non_shared=varint(0x80000000)][value_length=varint(0x80000001)]` + 1 filler byte + restart array (restart point 0, num_restarts 1); trailer type `kNoCompression`
- index block with a single entry pointing at that data block; standard footer with magic
- `Table::Open` succeeds; `NewIterator()` + `SeekToFirst()` triggers the read

**Observed**:

- Release build (leveldb built by its own CMake): the process dies with SIGBUS/SIGSEGV inside the 2 GiB read (exit 135).
- ASan build with NDEBUG: `AddressSanitizer: READ of size 2147483648` in `leveldb::Block::Iter::ParseNextKey()` via `SeekToFirst`.

This is reachable from any iteration/seek over a crafted on-disk table (block checksums protect against accidental corruption, not against a deliberately constructed file), e.g. when opening a restored/synced/imported database. I reported this through Google's vulnerability process first; it was reviewed as a valid finding and I was directed to open it here.

**Suggested fix** — widen the sum before comparing:

```cpp
if (static_cast(limit - p) <
static_cast(*non_shared) + *value_length) {
return nullptr;
}
```

or bound-check each operand against `limit - p` individually.

A self-contained reproduction program (crafts the table and drives `Table::Open`/`SeekToFirst`) is available; happy to attach it or send it as a PR adding a regression test.

Contributor guide

Open the contributing guide

Research direction

Start in table/block.cc at DecodeEntry around line 71 and follow the bounds check into Block::Iter::ParseNextKey around line 269. Use the supplied crafted SSTable reproduction to exercise Table::Open, NewIterator(), and SeekToFirst(). Done means the crafted entry is rejected without the oversized read, with a regression test covering the failure.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
databases, security
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
82/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.