EncodedS2LaxPolygonShape: heap-buffer-overflow in edge() via CELL_IDS point vector
- 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
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