EncodedS2ShapeIndex: OOB access via unchecked shape_id in cell decode
- 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
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