google / google/s2geometry

OOM (2.4 GiB alloc) via unchecked num_edges in single-shape S2ShapeIndexCell::Decode

Open Beginner friendly
#679 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 (2.4 GiB alloc) from unchecked `num_edges` in the single-shape `S2ShapeIndexCell::Decode` path

A 28-byte malformed encoded index triggers a ~2.4 GiB allocation in
`S2ShapeIndexCell::Decode()` (single-shape "other combination of edges" branch).

### Stack

```
ERROR: libFuzzer: out-of-memory (malloc(2415919100))
#0 __sanitizer_print_stack_trace
#9 S2ShapeIndexCell::Decode(int, Decoder*)
#10 MutableS2ShapeIndex::Init(Decoder*, S2ShapeIndex::ShapeFactory const&)
#11 LLVMFuzzerTestOneInput
```

### Root cause

In the single-shape branch (`src/s2/s2shape_index.cc`), after the int-overflow
guard added in #677, `num_edges = header >> 3` is bounded only against
`int32_t::max()` — **not against the remaining input bytes**. A header value that
yields a large-but-positive `num_edges` (e.g. 603,979,775) passes the check and
`S2ClippedShape::Init(0, num_edges)` allocates `num_edges * 4` ≈ 2.4 GiB *before*
`DecodeEdges()` reads the (absent) edge data.

This is the single-shape counterpart of the multi-shape gap fixed in #677: the
multi-shape path was bounded with `if (num_edges > decoder->avail()) return false;`,
but the single-shape path was not.

### Reproduction

28-byte input (base64):

```
CAgEAP7/6ggLCAgICHgICP////8R/7L3AP//6g==
```

Decode to a file and pass to a harness that calls `MutableS2ShapeIndex::Init`
(or `EncodedS2ShapeIndex::Init`) with a `LazyDecodeShapeFactory`; the
`Init()` succeeds and the allocation is observed under ASan/libFuzzer
(`-rss_limit_mb` default).

### Impact

Denial of service via unbounded allocation from a tiny untrusted input (memory
exhaustion), same class as #677.

Related to #677 (the int-overflow OOM); this is the large-but-positive case the
#677 fix did not cover.

Contributor guide

Open the contributing guide

Research direction

Start in src/s2/s2shape_index.cc at S2ShapeIndexCell::Decode(), focusing on the single-shape "other combination of edges" branch and its call from MutableS2ShapeIndex::Init(). Reproduce the issue with the provided 28-byte base64 input through a harness using LazyDecodeShapeFactory; done means the malformed input no longer causes the reported multi-GiB allocation and initialization rejects it.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.