google / google/s2geometry

EncodedS2LaxPolygonShape: heap-buffer-overflow in edge() via CELL_IDS point vector

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

Description

## Heap-buffer-overflow in `EncodedS2LaxPolygonShape::edge()` on malformed input

A malformed encoded index triggers an ASan **heap-buffer-overflow** (`READ of size 24`)
in `EncodedS2LaxPolygonShape::edge()`.

### Stack

```
ERROR: AddressSanitizer: heap-buffer-overflow on address ... (READ of size 24)
#0 __asan_memcpy
#1 EncodedS2LaxPolygonShape::edge(int) const
#2 main /tmp/s2_repro_full.cc:24 (shape->edge(edge_id))
```

### Root cause

`EncodedS2LaxPolygonShape::Init()` decodes `loop_starts_` (an
`EncodedUintVector`) but never validates its contents. `edge()` →
`chain_edge(i, j)` then computes

```cpp
int start = loop_starts_[i];
return Edge(vertices_[start + j], vertices_[start + k]);
```

so a `loop_starts_[i]` value beyond the real vertex count makes
`EncodedS2PointVector::operator[]` (CELL_IDS format) index past the decoded block
data, and `DecodeCellIdsFormat()` performs the unchecked `memcpy` of the 24-byte
`S2Point`.

(Note: this is a refinement of my initial analysis. I first suspected the CELL_IDS
block-count arithmetic in `InitCellIdsFormat()`, but that path is already guarded by
the `int32_t`-max check. The reproducible trigger is the unvalidated `loop_starts_`,
which is what the fix addresses.)

The non-encoded `S2LaxPolygonShape::Init()` has the same missing validation; PR #675
fixes both variants.

### Reproduction

323-byte input (base64, decode to a file and pass to the traversal reproducer):

```
EDmHBQEDAJUAEAABDI5CxsXB7z+Jcwt+Gjq2PwKBl7YwB2iR7z/GPwkRY+OvOt8/KDOol30I7D//8r7xc9qTID+QPcF9W5DQPyjgCBAIBQt+GjrGPwkRY+OvIiIpIiIiIiJzk8F9kNA/KOAIEHFycXCPbGwAAAAyM3wyMjIybGxsbGxsbG1sbHhtAHh4eHh4eHh4eHh4eHh4eHh4eDh4eHgCbGxswrjWRbY/l7YwB2iR7z/GPwkRY+OvOt8/KDOol30I7D//8jq2PwKBwrjsP//yvvFz2pMgP5A9wX1bkNA/KOAIEAgFC34aOsY/CRFj468iIiIiIiIiInOTwX2Q0D8o4AgQeHh4eHh4eHh4eHh4eHg4eHh4bGxsbAcAAAAAAAAAco+Pj2xsAAAAMjJ8MjIyMmxsbGxsbGxsbGxsbGxsAAE=
```

`Init()` returns `true`; the documented traversal then triggers the overflow in `edge()`.

### Impact

Out-of-bounds read (memory corruption / information disclosure) via `__asan_memcpy`
of an `S2Point` (24 bytes).

Related to #674/#676/#677 (all in the encoded-index decode path), but a distinct
class: an actual heap-buffer-overflow rather than a null-deref or OOM.

Fixed by PR #675.

Contributor guide

Open the contributing guide

Research direction

Start with EncodedS2LaxPolygonShape::Init() and edge(), following the chain through chain_edge() and the CELL_IDS decoding path; compare the corresponding S2LaxPolygonShape::Init() behavior. Reproduce the malformed input with the documented traversal under ASan and verify that the overflow no longer occurs for either encoded or non-encoded shapes.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.