K-ANOY opened a new issue, #51389:
URL: https://github.com/apache/arrow/issues/51389
### Describe the bug, including details regarding any error messages,
version, and platform.
Arrow builds a field-name → index lookup
(`std::unordered_multimap<std::string_view, int>`) from field names when
constructing a `Schema`/`SchemaBuilder` or a `StructType`. The map uses the
default `std::hash<std::string_view>` and its construction has no cap on field
count. When the field names are attacker-controlled — for example the schema
read from an untrusted Parquet/IPC/Feather file — many distinct names chosen to
land in the same bucket make construction (and later name lookups) approach
quadratic time.
## Affected code
File: `cpp/src/arrow/type.cc`
- `CreateNameToIndexMap(fields)` at `1333-1342` builds
`std::unordered_multimap<std::string_view, int>` keyed by `fields[i]->name()`.
- Holders: `StructType::Impl::name_to_index_` (`1369`),
`Schema::Impl::name_to_index_` (`2286`), and
`SchemaBuilder::Impl::name_to_index_` (`2589`, inserted at `2575` via
`emplace_hint(find(name), …)`). Lookups go through `LookupNameIndex` /
`equal_range` (`1399-1416`, `2376-2408`).
```cpp
std::unordered_multimap<std::string_view, int> CreateNameToIndexMap(const
FieldVector& fields) {
std::unordered_multimap<std::string_view, int> name_to_index;
name_to_index.reserve(fields.size());
for (size_t i = 0; i < fields.size(); ++i) {
const std::string_view name = fields[i]->name();
// The find() hint avoids libc++'s quadratic scan of equal keys on plain
emplace.
name_to_index.emplace_hint(name_to_index.find(name), name,
static_cast<int>(i));
}
return name_to_index;
}
```
The existing `find()` hint addresses the *duplicate-key* quadratic (many
fields with the *same* name). It does **not** address hash **collisions**: when
many *distinct* names hash to one bucket, each `find()` scans the growing
bucket, so building the map is O(n²) in the number of colliding names. A single
lookup (`GetFieldIndex` / `equal_range`) is worst-case O(bucket size); the
quadratic cost is in building the map (or in a batch of such lookups), not in
one lookup.
## Trigger and impact
- A `Schema` / `StructType` is constructed from field names on the normal
path. When those names come from an untrusted source — the schema of a
Parquet/Arrow-IPC/Feather file, or any API that builds types from externally
supplied names — the names are attacker-controlled.
- The type construction itself has no field-count cap. The file-reader entry
points do have some protection that bounds how many fields can be decoded —
e.g. Parquet's default Thrift container-size limit of `1,000,000`
(`cpp/src/parquet/properties.h:69`, `kDefaultThriftContainerSizeLimit`). This
does not prevent hash collisions (up to ~10^6 colliding field names still
yields catastrophic O(n²) construction), but it is the relevant upper bound and
should not be omitted.
- Impact is CPU amplification while building the type and on subsequent name
lookups. This report demonstrates map-level degradation, not a specific
end-to-end pipeline outage.
## Suggested fix
- Use a hash-flooding-resistant (per-process-seeded) hasher for the
field-name index, or bound the number of fields accepted when the schema
originates from untrusted input.
### Component(s)
C++
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
