Ismaël Mejía created AVRO-4302:
----------------------------------
Summary: Bound decode recursion depth to prevent stack overflow
from deeply nested data
Key: AVRO-4302
URL: https://issues.apache.org/jira/browse/AVRO-4302
Project: Apache Avro
Issue Type: Improvement
Components: csharp, javascript, perl, c, php, ruby, c++, java, python
Reporter: Ismaël Mejía
Assignee: Ismaël Mejía
h2. Summary
Avro binary decoders across the language SDKs do not bound the *recursion depth*
of decoded data. A recursive schema lets a malicious or malformed input drive
arbitrarily deep nesting during decoding, exhausting the call stack and crashing
the process ({{StackOverflowError}} in Java/C#, segfault in C/C++, thread abort
in the others) with only a tiny payload. This is a denial-of-service gap
distinct from, but in the same family as, the collection/allocation limits added
under AVRO-4292 and the decompression limits under AVRO-4283.
h2. The threat
Consider a self-referencing ("recursive") schema, e.g. a linked list:
{code:json}
{"type":"record","name":"Node","fields":[
{"name":"next","type":["null","Node"]}
]}
{code}
Each level of nesting is encoded as a single union-branch byte (select the
{{Node}} branch) before recursing into the next {{Node}}. An attacker can
therefore encode ~1 nesting level per byte: roughly *1 MB of input yields ~1
million levels of recursion*. Because every SDK decodes nested records/arrays/
maps/unions with a recursive call chain
({{read -> readRecord -> read -> ...}}), the call stack grows in lockstep with
the data nesting and overflows long before any other limit is reached (typically
at tens of thousands of frames), taking down the decoding thread/process.
Tree-shaped recursive schemas (a record with an {{array}} of itself, a {{map}}
of itself, deeply nested unions, etc.) are equally exploitable.
h2. Why it is not currently guarded
* There is *no decoder-level structural event for records*. Arrays, maps and
unions have {{arrayStart}}/{{mapStart}}/{{readIndex}} hooks, but a record is
just a sequence of fields, so the decoder cannot observe record nesting --
only
the reader (which drives the recursive descent) can.
* *Bounding the parser/symbol-stack size is incorrect*: for the grammar-based
decoders the stack size conflates width and depth (a record with 100k fields
pushes 100k symbols with zero nesting), so a size cap would falsely reject
wide-but-shallow data. Genuine depth tracking (increment on structural
descent, decrement on ascent) is required.
* Most SDKs have *more than one reader path* that must be guarded. In Java, for
example: {{GenericDatumReader}} (and its Specific/Reflect subclasses) via
{{ResolvingDecoder}}, *and* the separate {{FastReaderBuilder}} path (which
reads from a plain decoder with pre-compiled field readers). Both recurse
independently.
h2. Proposed approach
* Introduce a configurable maximum decode recursion depth, enforced by every
binary decoder/reader, incremented when descending into a record/array/map/
union value and decremented on exit, throwing a clear, bounded Avro error
(not a {{StackOverflowError}}/segfault) once the limit is exceeded.
* Default the limit to a safe value that comfortably exceeds any realistic
schema nesting (e.g. ~1000) while preventing stack exhaustion; make it tunable
per SDK, and document it alongside {{AVRO_MAX_COLLECTION_ITEMS}} and the
decompression limit.
* Cover *all* reader implementations in each SDK (e.g. Java: both the resolving/
validating datum readers and the fast reader).
* Be careful with state: a per-instance depth counter can be corrupted by
concurrent reuse of a reader; prefer threading the depth through the recursive
call or another decode-scoped mechanism.
* Reject too-deep input with a distinct error type/message, separate from
"malformed" or "collection too large".
h3. Suggested per-SDK audit points
* *Java*: {{GenericDatumReader.read/readRecord}}, {{FastReaderBuilder}} field
readers, and the resolving/validating decoders.
* *C*: {{value-read.c}} ({{read_value}} / {{read_record_value}} etc.).
* *C++*: {{Generic.cc}} ({{GenericReader::read}}), the parsing decoders.
* *C#*: {{GenericReader.Read}} and the fast/preresolving readers.
* *Python*: {{io.py}} {{read_data}}/{{read_record}}.
* *Ruby*: {{io.rb}} {{read_data}}/{{read_record}}.
* *PHP*: {{AvroIODatumReader}} {{readData}}/{{readRecord}}.
* *Perl*: {{BinaryDecoder.pm}} {{decode}}/{{decode_record}}.
* *JavaScript*: {{schemas.js}} {{RecordType._read}} and friends.
* *Rust* (github.com/apache/avro-rs): {{decode.rs}} recursive {{decode}}.
h2. Testing
Each SDK should add a regression test that decodes a deeply nested payload for a
recursive schema (e.g. a ~1 MB linked list) and asserts a bounded, well-defined
error is raised rather than a crash / stack overflow, plus a test confirming a
legitimately (moderately) deep value within the limit still decodes.
h2. Relationship to other issues
* AVRO-4292 -- collection block-count / allocation limits (the "available bytes"
work). Related decoder-hardening umbrella; recursion depth is deliberately
scoped separately because it is more invasive (touches the core recursive read
dispatch, multiple reader paths per SDK) and warrants its own design review.
* AVRO-4283 -- maximum decompressed block size. Sibling DoS-hardening effort for
the container-file codecs.
Recommend implementing as an umbrella with one subtask per language SDK,
mirroring AVRO-4292/AVRO-4283, once a common approach and default limit are
agreed.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
