[C++] Hash-collision CPU amplification building the Schema/StructType field-name index

[K-ANOY]

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).

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++

[guptapiyush16]

I would like to work on this issue
Kindly assign it to me

[pitrou]

@guptapiyush16 Since you are a first-time contributor, I would suggest focussing on issues labelled "good first issue".