EncodedS2ShapeIndex: OOM (16 GiB alloc) from unchecked num_edges/num_clipped
- 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
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