This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-25218-9a1ad7c792967adf315bf64b157ab584156802fc in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit a407990b4443d76428c8a2103ddbfc5e81c68c6b Author: Jay Zhan <[email protected]> AuthorDate: Sat Sep 12 23:33:27 2026 +0000 fix: out-of-bounds read in ArrowBytesMap on a short/long hash collision (#25218) ## Which issue does this PR close? - No existing issue. Found while running the extended CI `force_hash_collisions` job against unrelated work; happy to file one first if you prefer. ## Rationale for this change `ArrowBytesMap` keeps a value's bytes inline in an entry's `offset_or_inline` field when the value is at most `SHORT_VALUE_LEN` (8) bytes, and keeps an offset into the value buffer there otherwise. The lookup for a **long** value checked only that the hashes matched, then built `header.range()` from that field and read the buffer with `get_unchecked`: ```rust let entry = self.map.find_mut(hash, |header| { if header.hash != hash { return false; } // SAFETY: buffer is only appended to, and we correctly inserted values and offsets let existing_value = unsafe { self.buffer.get_unchecked(header.range()) }; value == existing_value }); ``` When that hash matches a **short** entry, `offset_or_inline` holds inlined bytes rather than an offset, so the range is nonsense and the read goes outside the buffer. The lookup for a short value does not have this problem, because it already compares `header.len` first, which is precisely what keeps it sound. This is reachable whenever a value of at most 8 bytes and a value longer than 8 bytes collide on the full 64-bit hash inside one map. Two things make that worth fixing rather than dismissing: - DataFusion hashes with `foldhash::fast::FixedState::default()`, a fixed compile-time seed, so a colliding pair is reproducible across runs and machines and can be found offline once. - The expected number of such pairs grows with the product of the short and long distinct counts, so the exposure rises with cardinality rather than staying constant. The map backs grouped aggregation on a single string or binary column (`GroupValuesBytes`) and `count(DISTINCT …)` over those types (`ArrowBytesSet`), so this is on the path of ordinary `GROUP BY` and `COUNT(DISTINCT)` queries. What happens on a collision depends on the inlined bytes read as an offset. If they happen to land inside the buffer, the comparison sees unrelated bytes, reports inequality, and the query is correct by luck. Otherwise the read is out of bounds, which is undefined behaviour: with UB checks enabled it aborts, and in a release build it reads unmapped or unrelated memory. The extended CI job builds the workspace with `force_hash_collisions`, where every value hashes to `0` so every short/long pair collides. Today `dataframe::test_grouping_with_alias` aborts there: ``` unsafe precondition(s) violated: slice::get_unchecked requires that the range is within the slice thread caused non-unwinding panic. aborting. ``` The check is asymmetric for a reason worth stating: the short-value lookup already compares `header.len`, so a long entry can never be mistaken for a short one. Only the long-value lookup was missing it. That single comparison guards two different failure modes, an out-of-bounds read in one direction and a false equality that merges two distinct values in the other, which is why the regression test exercises both orders. ## What changes are included in this PR? - Compare `header.len` on the long-value path, exactly as the short-value path already does. That rules out short entries, so `offset_or_inline` is only ever treated as an offset when it is one, and it doubles as a cheap early-out. It cannot reject a real match, since two equal long values have equal lengths. - Rewrite the `SAFETY` comment to state the invariant that actually holds. - Give `datafusion-physical-expr-common` the `force_hash_collisions` passthrough feature that `datafusion-common`, `datafusion-core`, `datafusion-physical-plan` and the two aggregate crates already have, so the path can be reached deterministically from a unit test. ## What is the testing strategy for this PR? `short_and_long_values_with_colliding_hashes` in `binary_map.rs`, gated on `force_hash_collisions`, inserts a short and a long value in both orders and asserts each distinct value is offered to the payload function exactly once. The values are chosen so that removing either length check actually fails: `"ab"` inlines to 0x6162, far past the end of the buffer, and a single NUL byte inlines to 0, which is the offset of a long value stored first. Mutation-checked both ways: removing the long path's check aborts on the precondition violation, removing the short path's check trips the assertion. With the fix, the whole `core_integration` suite passes under `--features force_hash_collisions` (1144 tests) where it previously aborted. Without the feature, `datafusion-physical-expr-common`, `datafusion-functions-aggregate` and the `dataframe` integration tests all pass, and clippy is clean in both feature configurations. ## Are there any user-facing changes? --- datafusion/physical-expr-common/Cargo.toml | 3 + datafusion/physical-expr-common/src/binary_map.rs | 69 +++++++++++++++++++++-- 2 files changed, 68 insertions(+), 4 deletions(-) diff --git a/datafusion/physical-expr-common/Cargo.toml b/datafusion/physical-expr-common/Cargo.toml index 903f5a6a90..4276814fd0 100644 --- a/datafusion/physical-expr-common/Cargo.toml +++ b/datafusion/physical-expr-common/Cargo.toml @@ -45,6 +45,9 @@ default = [] # Enables the `PhysicalExpr::to_proto` hook used by `datafusion-proto`. # Off by default so crates that never serialize plans pay nothing. proto = ["dep:datafusion-proto-models"] +# Test-only: makes every value hash to the same bucket, so that code paths +# which only run on a hash collision are reachable in tests. +force_hash_collisions = ["datafusion-common/force_hash_collisions"] [dependencies] arrow = { workspace = true } diff --git a/datafusion/physical-expr-common/src/binary_map.rs b/datafusion/physical-expr-common/src/binary_map.rs index c82e473f99..c9f8c5d119 100644 --- a/datafusion/physical-expr-common/src/binary_map.rs +++ b/datafusion/physical-expr-common/src/binary_map.rs @@ -511,12 +511,15 @@ where else { // Check if the value is already present in the set let entry = self.map.find_mut(hash, |header| { - // compare value if hashes match - if header.hash != hash { + // Without the length test, a short entry colliding on + // `hash` builds `range()` from its inlined bytes and + // reads past the buffer: memory safety, not just a + // wasted comparison. + if header.hash != hash || header.len != value_len { return false; } - // Need to compare the bytes in the buffer - // SAFETY: buffer is only appended to, and we correctly inserted values and offsets + // SAFETY: a long entry, so `offset_or_inline` indexes the + // append-only `buffer`, written before the insert. let existing_value = unsafe { self.buffer.get_unchecked(header.range()) }; value == existing_value @@ -1103,6 +1106,64 @@ mod tests { ); } + /// A short value and a long value whose hashes collide must not be confused, + /// whichever of them is inserted first. + /// + /// A short value keeps its bytes inlined in the entry's `offset_or_inline` + /// field, while a long one keeps an offset into the value buffer there. An + /// entry is only examined when its hash matches, so the length has to be + /// compared before that field is interpreted at all. Each direction fails + /// differently without that check, and each case below is chosen to make it + /// actually fail rather than get away with it: + /// + /// * long value looked up against a short entry: `header.range()` is built + /// out of the inlined bytes, so `"ab"` (0x6162) sends the read tens of + /// kilobytes past the end of the buffer; + /// * short value looked up against a long entry: the inlined bytes are + /// compared against that entry's offset, so a single NUL byte (inlined as + /// 0) matches the long value stored at offset 0 and the two distinct + /// values collapse into one. + /// + /// `force_hash_collisions` makes every value collide, which is the only way + /// to reach either path deterministically. + #[cfg(feature = "force_hash_collisions")] + #[test] + fn short_and_long_values_with_colliding_hashes() { + let long = "a value too long to be inlined"; + assert!(long.len() > SHORT_VALUE_LEN); + + for [first, second] in [[long, "\0"], ["ab", long]] { + assert!(first.len() <= SHORT_VALUE_LEN || second.len() <= SHORT_VALUE_LEN); + // The second value is the one looked up against an entry of the + // other kind; the repeats must match their own entry. + let values: ArrayRef = Arc::new(StringArray::from(vec![ + Some(first), + Some(second), + Some(first), + Some(second), + ])); + + let mut map = ArrowBytesMap::<i32, usize>::new(OutputType::Utf8); + let mut inserted = vec![]; + let mut payloads = 0; + map.insert_if_new( + &values, + |value| { + inserted.push(value.expect("no nulls in this test").to_vec()); + payloads += 1; + payloads + }, + |_| {}, + ); + + assert_eq!( + inserted, + vec![first.as_bytes().to_vec(), second.as_bytes().to_vec()], + "inserting {first:?} then {second:?}" + ); + } + } + // asserts that the set contains the expected strings, in the same order fn assert_set<O: OffsetSizeTrait>(set: ArrowBytesSet<O>, expected: &[Option<&str>]) { let strings = set.into_state(); --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
