Harden encoded shape-index and polygon-shape decode against malformed input (fixes #674, #676, #677, #678, #679) - #675
Open
sushant-me wants to merge 7 commits into
Conversation
GetCell() returns nullptr when S2ShapeIndexCell::Decode() fails on a corrupt or malformed encoded index. Iterator::cell() then dereferences that nullptr, crashing with SIGSEGV even though Init() reported success. Return a static empty cell instead of nullptr so the read API (which assumes lazy decode is infallible) never observes a null cell. Fixes google#674
A malformed encoded cell can encode a clipped shape whose shape_id exceeds num_shape_ids. Decode() only guarded against int overflow, not the actual number of shapes, so a later shape(shape_id) performed an out-of-bounds access on the shapes_ vector. Reject any clipped shape with shape_id >= num_shape_ids. Fixes google#676
Three unbounded values decoded from the input header could trigger huge allocations: 1. Single-shape path: int num_edges = header >> 3 overflowed int when header was a large uint64, becoming negative and then 0xFFFFFFFF when passed to S2ClippedShape::Init, which did new int32_t[0xFFFFFFFF] (~16 GiB). 2. Multi-shape path: num_clipped = header >> 3 was unbounded, so add_shapes() allocated memory proportional to an attacker-controlled count. 3. Multi-shape path: num_edges = (header >> 3) + 1 was unbounded. Bound each against num_shape_ids / int32 max / the remaining input bytes. Fixes google#677
chain_edge() indexes vertices_[loop_starts_[i] + j], so a malformed loop_starts would read out of bounds. Validate monotonicity, first==0, and last==num_vertices.
EncodedS2LaxPolygonShape::Init() decoded loop_starts_ but never validated its count or values. chain_edge() then indexed vertices_[loop_starts_[i] + j], so a malformed loop_starts produced a heap-buffer-overflow on decoding an untrusted encoded index. Validate that loop_starts_ has num_loops_+1 entries, starts at 0, is non-decreasing, and ends at the vertex count. Fixes google#678
The single-shape 'other combination' branch of S2ShapeIndexCell::Decode bounded num_edges only against int32 max, not against the remaining encoded bytes. A large-but-positive num_edges passed the check and S2ClippedShape::Init allocated num_edges * 4 bytes (~2.4 GiB) before DecodeEdges read the (absent) edge data. Bound it against decoder->avail(), matching the multi-shape path. Fixes google#679
…oogle#676/google#677/google#678/google#679) Adds EncodedS2ShapeIndex.MalformedInputRegression, which feeds three fuzzer-produced malformed indexes (null cell, unvalidated loop_starts, unbounded single-shape num_edges) through Init + traversal. Each previously crashed or allocated unboundedly; after the fixes they must be rejected or traversed safely. Verified standalone under ASan/UBSan: all three inputs are handled cleanly.
Author
|
Adding local verification for this PR, since CI on this branch is still awaiting approval. Built and ran it against this branch (HEAD That test covers the malformed inputs from #674, #676, #677, #678 and #679. Two things worth knowing so a local run isn't misread:
|
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Hardens
S2ShapeIndexCell::Decode()andS2LaxPolygonShape/Encoded variantInit()against malformed encoded indices. Fixes five distinct crash/OOM/overflow bugs, all triggered by unchecked values decoded from the input:GetCell()returnednullptrwhen a cell failed to decode, andIterator::cell()dereferenced it (null-deref SIGSEGV). Now returns a static empty cell.shape_idwas only guarded againstintoverflow, not againstnum_shape_ids, soshape(shape_id)did an OOB access onshapes_. Now rejectsshape_id >= num_shape_ids.num_edges/num_clippedwere unbounded, allowing a ~16 GiB allocation(OOM) from a 117-byte input via int-truncation of
header >> 3. Now bounded againstint32max,num_shape_ids, and the remaining input bytes.EncodedS2LaxPolygonShape::Init()decodedloop_starts_withoutvalidating its count or values, so
chain_edge()indexedvertices_[loop_starts_[i] + j]out of bounds (heap-buffer-overflow inedge()). Now validatesloop_starts_hasnum_loops_+1entries, starts at 0,is non-decreasing, and ends at the vertex count. The same validation is added to the
non-encoded
S2LaxPolygonShape::Init()as defense-in-depth.num_edgesonlyagainst
int32max, not the remaining input bytes, so a large-but-positivenum_edgescaused a ~2.4 GiB allocation from a 28-byte input. Now bounded againstdecoder->avail(), matching the multi-shape path.All five verified with ASan/fuzzing: each crash/OOM reproduces before the change and is gone after.
Authored by Sushant Poudel (sushant-me).
Fixes #674, fixes #676, fixes #677, fixes #678, fixes #679.