This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datafusion.git
The following commit(s) were added to refs/heads/main by this push:
new a407990b44 fix: out-of-bounds read in ArrowBytesMap on a short/long
hash collision (#25218)
a407990b44 is described below
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]
