OOM (2.4 GiB alloc) via unchecked num_edges in single-shape S2ShapeIndexCell::Decode
- 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
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