[Bug] Manifest bad internal key causes DB Open process crash

# Manifest bad internal key causes DB Open process crash

## 1. Basic Information

- **Repository**: https://github.com/google/leveldb
- **Affected commit**: `7ee830d02b623e8ffe0b95d59a74db1e58da04c5`
- **Affected version**: leveldb 1.23.0 / HEAD@`7ee830d02b62`
- **Component**: MANIFEST and VersionSet recovery path
- **Primary sink**: `db/version_edit.cc` and `db/version_set.cc`
- **Related path**: `VersionEdit::DecodeFrom()` -> `VersionSet::Builder::Apply()` -> `VersionSet::Recover()` -> `DB::Open()`
- **Vulnerability type**: CWE 191 Integer Underflow leading to process crash

## 2. Vulnerability Summary

`VersionEdit::DecodeFrom()` accepts malformed MANIFEST `smallest` and `largest` values as long as they are non empty. A 1 byte string is therefore accepted as an InternalKey even though a valid InternalKey must contain at least 8 trailing bytes for sequence and type.

Later, when recovery inserts these forged keys into the `VersionSet::Builder` set, `InternalKeyComparator::Compare()` calls `ExtractUserKey()` and performs `internal_key.size() - 8`. For a 1 byte key this underflows, turns into a huge size, and eventually reaches `memcmp`, where AddressSanitizer reports `negative-size-param` and aborts the process.

The result is a crash during `DB::Open()` when a target opens a crafted LevelDB directory.

## 3. Affected Code

```c++
static bool GetInternalKey(Slice* input, InternalKey* dst) {
Slice str;
if (GetLengthPrefixedSlice(input, &str)) {
return dst->DecodeFrom(str);
} else {
return false;
}
}
```

```c++
bool DecodeFrom(const Slice& s) {
rep_.assign(s.data(), s.size());
return !rep_.empty();
}

inline Slice ExtractUserKey(const Slice& internal_key) {
assert(internal_key.size() >= 8);
return Slice(internal_key.data(), internal_key.size() - 8);
}
```

## 4. Technical Details

The malformed MANIFEST record reaches `VersionSet::Recover()` through normal recovery logic. Because `GetInternalKey()` and `InternalKey::DecodeFrom()` only reject empty values, a 1 byte key is accepted and stored in file metadata. Once recovery compares two such file metadata entries, the comparator reaches `ExtractUserKey()` and underflows on `size() - 8`, which turns a malformed key into a memory unsafe comparison size and crashes the process.

## 5. Files

Files in this folder:

- `Manifest_Bad_InternalKey_DoS.md`: report
- `poc/generate_payloads.cc`: payload generator source
- `poc/open_db.cc`: minimal `DB::Open()` trigger source
- `poc/reproduce.sh`: reproduction script

## 6. Reproduction Steps

### Prerequisites

#### Required tools

Please ensure the environment has:

- `git`
- `cmake`
- a working C and C++ compiler

#### Working directory

Enter this folder first:

```bash
cd /path/to/Manifest_Bad_InternalKey_DoS/submit
```

### One click reproduction

Run:

```bash
bash ./poc/reproduce.sh
```

The script will:

- clone `leveldb` and check out the affected commit;
- build a sanitized `libleveldb.a`;
- build the payload generator and the `DB::Open()` trigger;
- generate a crafted LevelDB directory containing a malformed `MANIFEST-000001`;
- run the trigger and verify that the crash log contains `negative-size-param`, `VersionSet::Builder::Apply`, `VersionSet::Recover`, and `DB::Open`.

If the script prints `[*] reproduction succeeded`, the issue was reproduced.

### Manual reproduction

#### Step 1. Obtain the affected source tree

```bash
WORKDIR="$(mktemp -d)"
git clone https://github.com/google/leveldb.git "$WORKDIR/leveldb"
cd "$WORKDIR/leveldb"
git checkout 7ee830d02b623e8ffe0b95d59a74db1e58da04c5
```

#### Step 2. Build sanitized leveldb

If `clang` and `clang++` are available, run:

```bash
export CC=clang
export CXX=clang++
```

Then build:

```bash
cmake -S . -B build \
-DCMAKE_BUILD_TYPE=RelWithDebInfo \
-DLEVELDB_BUILD_TESTS=OFF \
-DLEVELDB_BUILD_BENCHMARKS=OFF \
-DCMAKE_C_FLAGS='-fsanitize=address,undefined -fno-omit-frame-pointer' \
-DCMAKE_CXX_FLAGS='-fsanitize=address,undefined -fno-omit-frame-pointer -fno-sanitize=vptr' \
-DCMAKE_EXE_LINKER_FLAGS='-fsanitize=address,undefined'
cmake --build build -j2
```

#### Step 3. Build the helper binaries

From the `submit/` directory:

```bash
cd /path/to/Manifest_Bad_InternalKey_DoS/submit

"$CXX" -std=c++17 \
-fsanitize=address,undefined \
-fno-sanitize=vptr \
-fno-omit-frame-pointer \
-fno-exceptions \
-fno-rtti \
-I"$WORKDIR/leveldb/include" \
-I"$WORKDIR/leveldb" \
-I"$WORKDIR/leveldb/build/include" \
./poc/generate_payloads.cc "$WORKDIR/leveldb/build/libleveldb.a" -lpthread -o ./poc/gen_payloads

"$CXX" -std=c++17 \
-fsanitize=address,undefined \
-fno-sanitize=vptr \
-fno-omit-frame-pointer \
-fno-exceptions \
-fno-rtti \
-I"$WORKDIR/leveldb/include" \
-I"$WORKDIR/leveldb" \
-I"$WORKDIR/leveldb/build/include" \
./poc/open_db.cc "$WORKDIR/leveldb/build/libleveldb.a" -lpthread -o ./poc/open_db
```

#### Step 4. Generate the malicious database directory

```bash
./poc/gen_payloads ./workdir
```

#### Step 5. Trigger the vulnerability

```bash
ASAN_OPTIONS=abort_on_error=1:detect_leaks=0 \
UBSAN_OPTIONS=halt_on_error=1:print_stacktrace=1 \
./poc/open_db ./workdir/manifest_bad_internal_key_db
```

The output should contain:

- `ERROR: AddressSanitizer: negative-size-param`
- `VersionSet::Builder::Apply`
- `VersionSet::Recover`
- `DB::Open`

A local verification run produced the following key output:

```text
[*] trigger exit code: 134
[*] non zero exit is expected here because ASAN aborts after the bug is triggered
==93267==ERROR: AddressSanitizer: negative-size-param: (size=-7)
#9 ... in leveldb::VersionSet::Builder::Apply(...)
#10 ... in leveldb::VersionSet::Recover(bool*)
#12 ... in leveldb::DB::Open(...)
SUMMARY: AddressSanitizer: negative-size-param ...
[*] reproduction succeeded
```

### Expected vs Actual Behavior

- **Expected behavior**: opening a malformed database directory should return `Corruption` or another regular parse error.
- **Actual behavior**: a malformed MANIFEST reaches the recovery comparator and crashes the process during `DB::Open()`.

## 7. Root Cause

The issue is not just missing validation. Recovery accepts malformed InternalKeys that are shorter than 8 bytes, and later comparator logic assumes that every InternalKey already satisfies that invariant. The assumption breaks in release builds, so the subtraction in `ExtractUserKey()` underflows and feeds an invalid size into the comparator.

## 8. Suggested Fix

Reject malformed InternalKeys during MANIFEST decoding and add an explicit guard before subtracting 8 bytes:

```c++
static bool GetInternalKey(Slice* input, InternalKey* dst) {
Slice str;
ParsedInternalKey parsed;
if (!GetLengthPrefixedSlice(input, &str)) return false;
if (!ParseInternalKey(str, &parsed)) return false;
dst->SetFrom(parsed);
return true;
}

inline Slice ExtractUserKey(const Slice& internal_key) {
if (internal_key.size() < 8) return Slice();
return Slice(internal_key.data(), internal_key.size() - 8);
}
```

[poc.zip](https://github.com/user-attachments/files/26167054/poc.zip)

Start with db/version_edit.cc and db/version_set.cc, following VersionEdit::DecodeFrom() through VersionSet::Builder::Apply(), VersionSet::Recover(), and DB::Open(). Run poc/reproduce.sh and inspect the listed payload files; done means malformed MANIFEST keys produce a regular parse error instead of crashing, with the reproduction no longer reporting negative-size-param.

Written by the indexing model from the issue text.