EncodedS2ShapeIndex: OOB access via unchecked shape_id in cell decode #676

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:

int64_t shape_id = 0;
for (...) {
  if (shape_id >= std::numeric_limits<int>::max()) return false; // overflow only
  shape_id += <untrusted delta>;       // 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<EncodedS2ShapeIndex::AtomicShape>::operator[]:
    Assertion '__n < this->size()' failed.

Impact

OOB read (shapes_[id].load()) and OOB write (shapes_[id].compare_exchange_strong())
on a std::vector<std::atomic<S2Shape*>>. 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.