google / google/s2geometry

EncodedS2ShapeIndex: OOB access via unchecked shape_id in cell decode

Open Beginner friendly
#676 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

## Out-of-bounds access in `EncodedS2ShapeIndex::shape()` via unchecked `shape_id`

Related to (but distinct from) #674. A malformed `EncodedS2ShapeIndex` can encode a
clipped shape whose `shape_id >= num_shape_ids()`, causing an OOB access on the
`shapes_` vector during lazy shape decode.

### Root cause

`S2ShapeIndexCell::Decode()` derives `shape_id` from the untrusted header
(`shape_id_count >> 4`, `header >> 4`, `shape_delta`) and only guards against `int`
overflow, never against `num_shape_ids`:

```cpp
int64_t shape_id = 0;
for (...) {
if (shape_id >= std::numeric_limits::max()) return false; // overflow only
shape_id += ; // can exceed num_shape_ids
clipped->Init(shape_id, num_edges);
}
```

`shape(shape_id)` then does `shapes_[shape_id]` with the precondition
`0 <= id < num_shape_ids()`, but `shape_id` is out of range.

### Reproduction

24-byte input (base64):

```
BAgACAAICQkAAAAAAAAAAAAAAAAAAABA
```

`Init()` returns `true`; `index.shape(clipped.shape_id())` triggers:

```
stl_vector.h:1253: std::vector::operator[]:
Assertion '__n < this->size()' failed.
```

### Impact

OOB read (`shapes_[id].load()`) and OOB write (`shapes_[id].compare_exchange_strong()`)
on a `std::vector>`. Under ASan this is a heap-buffer-overflow;
without the bounds assertion it is a silent OOB access.

### Fix

In `S2ShapeIndexCell::Decode()`, reject any clipped shape with `shape_id >= num_shape_ids`
(return `false`). `num_shape_ids` is already a parameter, so the check is local.

Contributor guide

Open the contributing guide

Research direction

Start at S2ShapeIndexCell::Decode(), focusing on how shape_id is derived from the untrusted header and shape_delta. Reproduce the issue with the provided 24-byte base64 input, then verify malformed clipped shapes with shape_id >= num_shape_ids are rejected and cannot reach index.shape().

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
84/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.