google / google/s2geometry

EncodedS2ShapeIndex: OOM (16 GiB alloc) from unchecked num_edges/num_clipped

Open
#677 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
2.7k
Forks
357
Avg merge
11h 4m
Merged PRs (30d)
1

Description

## OOM (16 GiB allocation) from unchecked size fields in `S2ShapeIndexCell::Decode`

A 117-byte malformed input causes `S2ShapeIndexCell::Decode()` to attempt a single
`operator new(17179869180)` (~16 GiB), crashing with OOM.

### Root cause

Three values decoded from the untrusted header are used for allocation without bounds
checks:

1. **Single-shape path** — `int num_edges = header >> 3;` where `header` is `uint64_t`.
A large header makes `header >> 3` overflow `int` (→ negative), which sign-extends to
`0xFFFFFFFF` when passed to `S2ClippedShape::Init`, which does
`edges_ = new int32_t[0xFFFFFFFF]` = 17179869180 bytes.
2. **Multi-shape path** — `num_clipped = header >> 3` is unbounded, so `add_shapes()` allocates
memory proportional to an attacker-controlled count.
3. **Multi-shape path** — `num_edges = (header >> 3) + 1` is unbounded.

### Reproduction

117-byte input (base64):

```
CAAIFAAIAWxsbGxsbGxsbGxsbGxsbGxsbGxsbGxsbGxsbGxsbGxsbGxsbGxsbGxsi4uLi4uLi4uLbGxsdQAAACePCAAIABoAGgAgAAATJP////////8HjwAAAAAAAAAAAAAAAABAAAAAADoAEwAAEwgFOs8A
```

libFuzzer:

```
ERROR: libFuzzer: out-of-memory (malloc(17179869180))
#9 S2ShapeIndexCell::Decode(int, Decoder*) <- operator new(16 GiB)
#10 EncodedS2ShapeIndex::GetCell(int) const
```

### Impact

Denial of service: a 117-byte input forces a ~16 GiB allocation (CWE-400 uncontrolled
resource consumption), crashing the process.

### Fix

Bound each size field: `num_edges` against `int32` max / remaining input bytes, and
`num_clipped` against `num_shape_ids`. See PR #675.

Related to (distinct from) #674 (null deref) and #676 (OOB shape_id).

Contributor guide

Open the contributing guide

Research direction

Start with S2ShapeIndexCell::Decode and reproduce the issue with the provided 117-byte input or libFuzzer. Inspect S2ClippedShape::Init and add_shapes, then compare with PR #675; done means malformed size fields no longer trigger an oversized allocation and are bounded as described.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
security
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.