Skip to content

Commit 81176c5

Browse files
authored
[branch-55] fix: prevent unsafe integer interval propagation (#25234) (#26869)
- Part of #26868 This PR: - Backports #25234 to the `branch-55` line
1 parent 741d221 commit 81176c5

4 files changed

Lines changed: 407 additions & 6 deletions

File tree

‎datafusion/core/tests/fifo/mod.rs‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -239,9 +239,10 @@ mod unix_test {
239239
// Create a mutex for tracking if the right input source is waiting for data.
240240
let waiting = Arc::new(AtomicBool::new(true));
241241

242-
// Create schema
242+
// Use floating-point ordering so interval pruning does not depend on
243+
// proving that integer arithmetic in the join filter cannot overflow.
243244
let schema = Arc::new(Schema::new(vec![
244-
Field::new("a1", DataType::UInt32, false),
245+
Field::new("a1", DataType::Float64, false),
245246
Field::new("a2", DataType::UInt32, false),
246247
]));
247248

‎datafusion/physical-expr/src/expressions/binary.rs‎

Lines changed: 295 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -120,6 +120,23 @@ impl BinaryExpr {
120120
&self.op
121121
}
122122

123+
/// Mathematical intervals do not cover values produced by wrapping arithmetic.
124+
fn integer_arithmetic_may_wrap(
125+
&self,
126+
left: &Interval,
127+
right: &Interval,
128+
result: &Interval,
129+
) -> bool {
130+
!self.fail_on_overflow
131+
&& result.data_type().is_integer()
132+
&& matches!(
133+
self.op,
134+
Operator::Plus | Operator::Minus | Operator::Multiply
135+
)
136+
&& (result.is_unbounded()
137+
|| unsigned_subtraction_may_underflow(self.op, left, right, result))
138+
}
139+
123140
/// Wrapping on overflow breaks monotonicity (e.g. the sum of two
124141
/// ascending `UInt8` columns can wrap back to small values), so the
125142
/// derived ordering is kept only when overflow is impossible. `time ±
@@ -692,7 +709,12 @@ impl PhysicalExpr for BinaryExpr {
692709
let left_interval = children[0];
693710
let right_interval = children[1];
694711
// Calculate current node's interval:
695-
apply_operator(&self.op, left_interval, right_interval)
712+
let result = apply_operator(&self.op, left_interval, right_interval)?;
713+
if self.integer_arithmetic_may_wrap(left_interval, right_interval, &result) {
714+
Interval::make_unbounded(&result.data_type())
715+
} else {
716+
Ok(result)
717+
}
696718
}
697719

698720
fn propagate_constraints(
@@ -704,6 +726,36 @@ impl PhysicalExpr for BinaryExpr {
704726
let left_interval = children[0];
705727
let right_interval = children[1];
706728

729+
if left_interval.data_type().is_integer()
730+
&& right_interval.data_type().is_integer()
731+
&& matches!(
732+
self.op,
733+
Operator::Plus | Operator::Minus | Operator::Multiply | Operator::Divide
734+
)
735+
{
736+
// Integer division truncates: a / 2 = 1 permits both 2 and 3.
737+
// Wrapping arithmetic is likewise not invertible over mathematical
738+
// intervals. Keep the input domains rather than exclude valid rows.
739+
let contains_zero = |range: &Interval| -> Result<bool> {
740+
range.contains_value(ScalarValue::new_zero(&range.data_type())?)
741+
};
742+
// If an operand can be zero, a zero product does not constrain
743+
// the other operand. Dividing the parent interval loses that case.
744+
let zero_product = self.op == Operator::Multiply
745+
&& contains_zero(interval)?
746+
&& (contains_zero(left_interval)? || contains_zero(right_interval)?);
747+
if self.op == Operator::Divide
748+
|| zero_product
749+
|| self.integer_arithmetic_may_wrap(
750+
left_interval,
751+
right_interval,
752+
&apply_operator(&self.op, left_interval, right_interval)?,
753+
)
754+
{
755+
return Ok(Some(vec![]));
756+
}
757+
}
758+
707759
if self.op.eq(&Operator::And) {
708760
if interval.eq(&Interval::TRUE) {
709761
// A certainly true logical conjunction can only derive from possibly
@@ -824,7 +876,7 @@ impl PhysicalExpr for BinaryExpr {
824876
let (r_order, r_range) = (children[1].sort_properties, &children[1].range);
825877
match self.op() {
826878
Operator::Plus => {
827-
let range = l_range.add(r_range)?;
879+
let range = self.evaluate_bounds(&[l_range, r_range])?;
828880
Ok(ExprProperties {
829881
sort_properties: self.arithmetic_sort_properties(
830882
l_order.add(&r_order),
@@ -838,7 +890,7 @@ impl PhysicalExpr for BinaryExpr {
838890
})
839891
}
840892
Operator::Minus => {
841-
let range = l_range.sub(r_range)?;
893+
let range = self.evaluate_bounds(&[l_range, r_range])?;
842894
Ok(ExprProperties {
843895
sort_properties: self.arithmetic_sort_properties(
844896
l_order.sub(&r_order),
@@ -6115,6 +6167,246 @@ mod tests {
61156167
}
61166168
}
61176169

6170+
#[test]
6171+
fn test_integer_interval_propagation_covers_runtime_values() {
6172+
// Enumerate small domains and both ends of Int8, including zero divisors,
6173+
// truncation, signed overflow and checked arithmetic. Every successful
6174+
// runtime evaluation must remain possible after interval propagation.
6175+
let batch = RecordBatch::new_empty(Arc::new(Schema::empty()));
6176+
let domains = [
6177+
(-3i8, 3i8),
6178+
(0, 1),
6179+
(1, 3),
6180+
(-3, -1),
6181+
(-128, -127),
6182+
(126, 127),
6183+
];
6184+
for checked in [false, true] {
6185+
for op in [
6186+
Operator::Plus,
6187+
Operator::Minus,
6188+
Operator::Multiply,
6189+
Operator::Divide,
6190+
] {
6191+
let expr = BinaryExpr::new(lit(0i8), op, lit(0i8))
6192+
.with_fail_on_overflow(checked);
6193+
for (lo, hi) in domains {
6194+
for (rlo, rhi) in
6195+
domains.into_iter().chain([(-1, -1), (0, 0), (2, 2)])
6196+
{
6197+
let left = Interval::make(Some(lo), Some(hi)).unwrap();
6198+
let right = Interval::make(Some(rlo), Some(rhi)).unwrap();
6199+
let bounds = expr.evaluate_bounds(&[&left, &right]).unwrap();
6200+
if matches!(op, Operator::Plus | Operator::Minus) {
6201+
let children = [left.clone(), right.clone()].map(|range| {
6202+
ExprProperties {
6203+
range,
6204+
..ExprProperties::new_unknown()
6205+
}
6206+
});
6207+
assert_eq!(
6208+
expr.get_properties(&children).unwrap().range,
6209+
bounds
6210+
);
6211+
}
6212+
for a in lo..=hi {
6213+
for b in rlo..=rhi {
6214+
// Use the execution kernel as the oracle rather than
6215+
// duplicating its checked and wrapping arithmetic.
6216+
let runtime = BinaryExpr::new(lit(a), op, lit(b))
6217+
.with_fail_on_overflow(checked);
6218+
let result = match runtime.evaluate(&batch) {
6219+
Ok(value) => value.into_array(1).unwrap(),
6220+
Err(error) => {
6221+
assert!(
6222+
checked || op == Operator::Divide,
6223+
"wrapping {a} {op} {b} failed: {error}"
6224+
);
6225+
continue;
6226+
}
6227+
};
6228+
let result = result.as_primitive::<Int8Type>().value(0);
6229+
let result =
6230+
Interval::make(Some(result), Some(result)).unwrap();
6231+
assert_eq!(
6232+
bounds.contains(&result).unwrap(),
6233+
Interval::TRUE,
6234+
"forward {a} {op} {b}, checked={checked}, bounds={bounds:?}"
6235+
);
6236+
let propagated = expr
6237+
.propagate_constraints(&result, &[&left, &right])
6238+
.unwrap();
6239+
let propagated = propagated
6240+
.expect("successful runtime result must be feasible");
6241+
if !propagated.is_empty() {
6242+
assert_eq!(
6243+
propagated[0]
6244+
.contains(
6245+
Interval::make(Some(a), Some(a)).unwrap()
6246+
)
6247+
.unwrap(),
6248+
Interval::TRUE,
6249+
"left input excluded for {a} {op} {b}, checked={checked}: {propagated:?}"
6250+
);
6251+
assert_eq!(
6252+
propagated[1]
6253+
.contains(
6254+
Interval::make(Some(b), Some(b)).unwrap()
6255+
)
6256+
.unwrap(),
6257+
Interval::TRUE,
6258+
"right input excluded for {a} {op} {b}, checked={checked}: {propagated:?}"
6259+
);
6260+
}
6261+
}
6262+
}
6263+
}
6264+
}
6265+
}
6266+
}
6267+
}
6268+
6269+
#[test]
6270+
fn test_integer_interval_error_propagation() {
6271+
// Compare error messages without backtraces, which differ by call path.
6272+
let integer = Interval::make(Some(1i32), Some(2i32)).unwrap();
6273+
let boolean = Interval::TRUE;
6274+
for op in [Operator::Plus, Operator::Minus] {
6275+
let expr = BinaryExpr::new(lit(1i32), op, lit(true));
6276+
let expected = apply_operator(&op, &integer, &boolean)
6277+
.unwrap_err()
6278+
.strip_backtrace();
6279+
assert_eq!(
6280+
expr.evaluate_bounds(&[&integer, &boolean])
6281+
.unwrap_err()
6282+
.strip_backtrace(),
6283+
expected
6284+
);
6285+
let children =
6286+
[integer.clone(), boolean.clone()].map(|range| ExprProperties {
6287+
range,
6288+
..ExprProperties::new_unknown()
6289+
});
6290+
assert_eq!(
6291+
expr.get_properties(&children)
6292+
.unwrap_err()
6293+
.strip_backtrace(),
6294+
expected
6295+
);
6296+
}
6297+
6298+
// A nonnumeric parent cannot describe an integer product. Preserve
6299+
// the error from constructing zero for its unsupported type.
6300+
let parent = Interval::make_unbounded(&DataType::Utf8).unwrap();
6301+
let expr = BinaryExpr::new(lit(1i32), Operator::Multiply, lit(2i32));
6302+
assert_eq!(
6303+
expr.propagate_constraints(&parent, &[&integer, &integer])
6304+
.unwrap_err()
6305+
.strip_backtrace(),
6306+
ScalarValue::new_zero(&DataType::Utf8)
6307+
.unwrap_err()
6308+
.strip_backtrace()
6309+
);
6310+
}
6311+
6312+
#[test]
6313+
fn test_unsigned_subtraction_interval_underflow() {
6314+
let expr = BinaryExpr::new(lit(0u8), Operator::Minus, lit(1u8));
6315+
let left = Interval::make(Some(0u8), Some(2u8)).unwrap();
6316+
let right = Interval::make(Some(1u8), Some(1u8)).unwrap();
6317+
let wrapped = Interval::make(Some(255u8), Some(255u8)).unwrap();
6318+
assert_eq!(
6319+
expr.evaluate_bounds(&[&left, &right])
6320+
.unwrap()
6321+
.contains(&wrapped)
6322+
.unwrap(),
6323+
Interval::TRUE
6324+
);
6325+
assert_eq!(
6326+
expr.propagate_constraints(&wrapped, &[&left, &right])
6327+
.unwrap(),
6328+
Some(vec![])
6329+
);
6330+
}
6331+
6332+
#[test]
6333+
fn test_nested_wrapping_arithmetic_properties() {
6334+
let difference = Arc::new(BinaryExpr::new(lit(0u8), Operator::Minus, lit(1u8)));
6335+
let singleton = |value: u8| ExprProperties {
6336+
sort_properties: SortProperties::Singleton,
6337+
range: Interval::make(Some(value), Some(value)).unwrap(),
6338+
..ExprProperties::new_unknown()
6339+
};
6340+
let difference_props = difference
6341+
.get_properties(&[singleton(0), singleton(1)])
6342+
.unwrap();
6343+
assert_eq!(difference_props.sort_properties, SortProperties::Singleton);
6344+
assert!(
6345+
difference_props
6346+
.range
6347+
.contains_value(ScalarValue::UInt8(Some(255)))
6348+
.unwrap()
6349+
);
6350+
6351+
// The inner constant wraps to 255. An incorrect range of [0, 0]
6352+
// would let the outer addition claim to preserve ascending order.
6353+
let expr =
6354+
BinaryExpr::new(Arc::new(Column::new("a", 0)), Operator::Plus, difference);
6355+
let properties = expr
6356+
.get_properties(&[
6357+
ExprProperties {
6358+
sort_properties: SortProperties::Ordered(SortOptions::default()),
6359+
range: Interval::make(Some(0u8), Some(1u8)).unwrap(),
6360+
..ExprProperties::new_unknown()
6361+
},
6362+
difference_props,
6363+
])
6364+
.unwrap();
6365+
let batch = RecordBatch::try_new(
6366+
Arc::new(Schema::new(vec![Field::new("a", DataType::UInt8, false)])),
6367+
vec![Arc::new(UInt8Array::from(vec![0, 1]))],
6368+
)
6369+
.unwrap();
6370+
let actual = expr.evaluate(&batch).unwrap().into_array(2).unwrap();
6371+
assert_eq!(actual.as_ref(), &UInt8Array::from(vec![255, 0]));
6372+
assert_eq!(properties.sort_properties, SortProperties::Unordered);
6373+
for value in [0u8, 255] {
6374+
assert!(
6375+
properties
6376+
.range
6377+
.contains_value(ScalarValue::UInt8(Some(value)))
6378+
.unwrap()
6379+
);
6380+
}
6381+
}
6382+
6383+
#[test]
6384+
fn test_integer_comparison_still_propagates() {
6385+
// Integer comparisons must bypass the arithmetic overflow guard and
6386+
// still narrow their inputs: a = 5 restricts a in [0, 10] to [5, 5].
6387+
let expr = BinaryExpr::new(lit(0i32), Operator::Eq, lit(5i32));
6388+
let left = Interval::make(Some(0i32), Some(10i32)).unwrap();
6389+
let right = Interval::make(Some(5i32), Some(5i32)).unwrap();
6390+
assert_eq!(
6391+
expr.propagate_constraints(&Interval::TRUE, &[&left, &right])
6392+
.unwrap(),
6393+
Some(vec![right.clone(), right])
6394+
);
6395+
}
6396+
6397+
#[test]
6398+
fn test_safe_integer_multiplication_still_propagates() {
6399+
let expr = BinaryExpr::new(lit(0i32), Operator::Multiply, lit(2i32));
6400+
let left = Interval::make(Some(0i32), Some(10i32)).unwrap();
6401+
let right = Interval::make(Some(2i32), Some(2i32)).unwrap();
6402+
let parent = Interval::make(Some(4i32), Some(4i32)).unwrap();
6403+
assert_eq!(
6404+
expr.propagate_constraints(&parent, &[&left, &right])
6405+
.unwrap(),
6406+
Some(vec![Interval::make(Some(2i32), Some(2i32)).unwrap(), right])
6407+
);
6408+
}
6409+
61186410
#[test]
61196411
fn test_evaluate_bounds_int32() {
61206412
let schema = Schema::new(vec![

‎datafusion/physical-plan/src/filter.rs‎

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2073,6 +2073,18 @@ mod tests {
20732073
)),
20742074
)),
20752075
));
2076+
// i32::MIN also satisfies this predicate because subtracting 5 wraps.
2077+
// A mathematical lower bound of 5 would exclude a valid input value.
2078+
let batch = RecordBatch::try_new(
2079+
input.schema(),
2080+
vec![Arc::new(arrow::array::Int32Array::from(vec![i32::MIN]))],
2081+
)
2082+
.unwrap();
2083+
let result = predicate.evaluate(&batch).unwrap().into_array(1).unwrap();
2084+
assert_eq!(
2085+
result.as_ref(),
2086+
&arrow::array::BooleanArray::from(vec![true])
2087+
);
20762088
let filter: Arc<dyn ExecutionPlan> =
20772089
Arc::new(FilterExec::try_new(predicate, input)?);
20782090
let filter_statistics =
@@ -2085,7 +2097,7 @@ mod tests {
20852097
// `a <= 10` rejects nulls, so `a` has no surviving nulls even
20862098
// though the input statistics are entirely unknown.
20872099
null_count: Precision::Exact(0),
2088-
min_value: Precision::Inexact(ScalarValue::Int32(Some(5))),
2100+
min_value: Precision::Absent,
20892101
max_value: Precision::Inexact(ScalarValue::Int32(Some(10))),
20902102
sum_value: Precision::Absent,
20912103
distinct_count: Precision::Absent,

0 commit comments

Comments
 (0)