This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new 934df69 fix(frequencies): reject out-of-range map-size fields on
deserialize (#224)
934df69 is described below
commit 934df697dc0a975af8cb6986984b657aac058774
Author: Jaideep Pyne <[email protected]>
AuthorDate: Tue Aug 25 21:48:59 2026 +0530
fix(frequencies): reject out-of-range map-size fields on deserialize (#224)
Co-authored-by: tison <[email protected]>
---
CHANGELOG.md | 1 +
datasketches/src/frequencies/sketch.rs | 67 +++++++++++--
datasketches/tests/frequencies_test/update.rs | 6 ++
datasketches/tests/serde_tests/frequencies.rs | 133 ++++++++++++++++++++++++++
4 files changed, 200 insertions(+), 7 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 91629ca..91ae5f6 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -18,6 +18,7 @@ All significant changes to this project will be documented in
this file.
### Bug fixes
+* Frequent-items map sizes are now limited consistently to the cross-language
maximum of `2^30`: `FrequentItemsSketch::new` rejects larger configurations,
and `deserialize` returns `InvalidData` for out-of-range or inconsistent header
fields instead of panicking on corrupt input. Empty images restore the minimum
backing map instead of allocating from `lg_cur_map_size`, and non-empty images
validate `active_items` against the declared map capacity and remaining payload
before preallocatin [...]
* T-Digest compression now handles `k = u16::MAX` without overflowing the
scale normalization input.
* T-Digest deserialization now validates declared payload lengths before
allocating. Updating a deserialized digest whose unmerged buffer already
exceeds the compression threshold now compresses it instead of allowing the
buffer to grow without bound.
diff --git a/datasketches/src/frequencies/sketch.rs
b/datasketches/src/frequencies/sketch.rs
index 41b1ac7..bea0ca7 100644
--- a/datasketches/src/frequencies/sketch.rs
+++ b/datasketches/src/frequencies/sketch.rs
@@ -39,11 +39,38 @@ type SerializeItem<T> = fn(&mut SketchBytes, &T);
type DeserializeItems<T> = fn(SketchSlice<'_>, usize) -> Result<Vec<T>, Error>;
const LG_MIN_MAP_SIZE: u8 = 3;
+// Java represents map sizes as positive `int` powers of two, while the C++
+// implementation uses 32-bit table indices. Keep Rust configurations within
+// the same cross-language range.
+const LG_MAX_MAP_SIZE: u8 = 30;
+const MAX_MAP_SIZE: usize = 1usize << LG_MAX_MAP_SIZE;
const SAMPLE_SIZE: usize = 1024;
const EPSILON_FACTOR: f64 = 3.5;
const LOAD_FACTOR_NUMERATOR: usize = 3;
const LOAD_FACTOR_DENOMINATOR: usize = 4;
+fn map_capacity_for_lg(lg_map_size: u8) -> usize {
+ debug_assert!(lg_map_size <= LG_MAX_MAP_SIZE);
+ (1usize << lg_map_size) * LOAD_FACTOR_NUMERATOR / LOAD_FACTOR_DENOMINATOR
+}
+
+fn validate_lg_map_sizes(lg_max: u8, lg_cur: u8) -> Result<(), Error> {
+ if lg_cur < LG_MIN_MAP_SIZE {
+ return Err(Error::deserial(format!(
+ "lg_cur_map_size must be at least {LG_MIN_MAP_SIZE}, got {lg_cur}"
+ )));
+ }
+ if lg_max > LG_MAX_MAP_SIZE {
+ return Err(Error::deserial(format!(
+ "lg_max_map_size must be at most {LG_MAX_MAP_SIZE}, got {lg_max}"
+ )));
+ }
+ if lg_cur > lg_max {
+ return Err(Error::deserial("lg_cur_map_size exceeds lg_max_map_size"));
+ }
+ Ok(())
+}
+
/// Error guarantees for frequent item queries.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ErrorType {
@@ -110,7 +137,8 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
///
/// # Panics
///
- /// Panics if `max_map_size` is not a power of two.
+ /// Panics if `max_map_size` is not a power of two or exceeds `2^30`, the
+ /// maximum supported by the cross-language format implementations.
///
/// # Examples
///
@@ -127,6 +155,10 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
max_map_size.is_power_of_two(),
"max_map_size must be power of 2"
);
+ assert!(
+ max_map_size <= MAX_MAP_SIZE,
+ "max_map_size must not exceed {MAX_MAP_SIZE}"
+ );
let lg_max_map_size = max_map_size.trailing_zeros() as u8;
Self::with_lg_map_sizes(lg_max_map_size, LG_MIN_MAP_SIZE)
}
@@ -230,7 +262,7 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
///
/// This is `0.75 * max_map_size`.
pub fn maximum_map_capacity(&self) -> usize {
- (1usize << self.lg_max_map_size) * LOAD_FACTOR_NUMERATOR /
LOAD_FACTOR_DENOMINATOR
+ map_capacity_for_lg(self.lg_max_map_size)
}
/// Returns the current map capacity.
@@ -473,13 +505,17 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
fn with_lg_map_sizes(lg_max_map_size: u8, lg_cur_map_size: u8) -> Self {
let lg_max = lg_max_map_size.max(LG_MIN_MAP_SIZE);
let lg_cur = lg_cur_map_size.max(LG_MIN_MAP_SIZE);
+ assert!(
+ lg_max <= LG_MAX_MAP_SIZE,
+ "lg_max_map_size must not exceed {LG_MAX_MAP_SIZE}"
+ );
assert!(
lg_cur <= lg_max,
"lg_cur_map_size must not exceed lg_max_map_size"
);
let map = ReversePurgeItemHashMap::new(1usize << lg_cur);
let cur_map_cap = map.capacity();
- let max_map_cap = (1usize << lg_max) * LOAD_FACTOR_NUMERATOR /
LOAD_FACTOR_DENOMINATOR;
+ let max_map_cap = map_capacity_for_lg(lg_max);
let sample_size = SAMPLE_SIZE.min(max_map_cap);
Self {
lg_max_map_size: lg_max,
@@ -567,14 +603,14 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
Family::FREQUENCY.validate_id(family)?;
ensure_serial_version_is(SERIAL_VERSION, serial_version)?;
- if lg_cur > lg_max {
- return Err(Error::deserial("lg_cur_map_size exceeds
lg_max_map_size"));
- }
+ validate_lg_map_sizes(lg_max, lg_cur)?;
let is_empty = (flags & EMPTY_FLAG_MASK) != 0;
if is_empty {
ensure_preamble_longs_in(&[PREAMBLE_LONGS_EMPTY], pre_longs)?;
- return Ok(Self::with_lg_map_sizes(lg_max, lg_cur));
+ // Java also restores empty images at the minimum size. `lg_cur`
does
+ // not carry item state here and must not control an eager
allocation.
+ return Ok(Self::with_lg_map_sizes(lg_max, LG_MIN_MAP_SIZE));
}
ensure_preamble_longs_in(&[PREAMBLE_LONGS_NONEMPTY], pre_longs)?;
@@ -582,6 +618,13 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
.read_u32_le()
.map_err(insufficient_data("active_items"))?;
let active_items = active_items as usize;
+ let cur_map_cap = map_capacity_for_lg(lg_cur);
+ if active_items > cur_map_cap {
+ return Err(Error::deserial(format!(
+ "active_items ({active_items}) exceeds the capacity implied by
\
+ lg_cur_map_size ({lg_cur}): at most {cur_map_cap}"
+ )));
+ }
cursor
.read_u32_le()
.map_err(insufficient_data("<unused>"))?;
@@ -590,6 +633,16 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
.map_err(insufficient_data("stream_weight"))?;
let offset_val =
cursor.read_u64_le().map_err(insufficient_data("offset"))?;
+ // Each active item has an eight-byte weight before its encoded key.
Check
+ // that lower bound before trusting the count for `Vec` preallocation.
+ let weight_bytes = active_items.checked_mul(size_of::<u64>());
+ if !weight_bytes.is_some_and(|needed| needed <=
cursor.remaining().len()) {
+ return Err(Error::insufficient_data(format!(
+ "active_items ({active_items}) exceeds the remaining {} bytes",
+ cursor.remaining().len()
+ )));
+ }
+
let mut values = Vec::with_capacity(active_items);
for i in 0..active_items {
values.push(cursor.read_u64_le().map_err(|_| {
diff --git a/datasketches/tests/frequencies_test/update.rs
b/datasketches/tests/frequencies_test/update.rs
index 13d115c..7419dba 100644
--- a/datasketches/tests/frequencies_test/update.rs
+++ b/datasketches/tests/frequencies_test/update.rs
@@ -561,6 +561,12 @@ fn test_items_invalid_map_size_panics() {
FrequentItemsSketch::<String>::new(6);
}
+#[test]
+#[should_panic(expected = "max_map_size must not exceed")]
+fn test_map_size_above_cross_language_limit_panics() {
+ FrequentItemsSketch::<i64>::new(1usize << 31);
+}
+
#[test]
fn test_estimated_size() {
let mut sketch: FrequentItemsSketch<i64> = FrequentItemsSketch::new(64);
diff --git a/datasketches/tests/serde_tests/frequencies.rs
b/datasketches/tests/serde_tests/frequencies.rs
index 0e4fbdc..75f69b6 100644
--- a/datasketches/tests/serde_tests/frequencies.rs
+++ b/datasketches/tests/serde_tests/frequencies.rs
@@ -24,7 +24,9 @@ use datasketches::error::ErrorKind;
use datasketches::frequencies::FrequentItemValue;
use datasketches::frequencies::FrequentItemsSketch;
use googletest::assert_that;
+use googletest::prelude::anything;
use googletest::prelude::contains_substring;
+use googletest::prelude::err;
use googletest::prelude::gt;
use crate::serialization_test_data;
@@ -395,3 +397,134 @@ fn test_go_frequent_strings_utf8() {
assert_eq!(sketch.estimate(&"шщъыь".to_string()), 6);
assert_eq!(sketch.estimate(&"эюя".to_string()), 7);
}
+
+// Header field constants for the DataSketches frequent-items format.
+const FREQ_SERIAL_VERSION: u8 = 1;
+const FREQ_FAMILY_ID: u8 = 10;
+const FREQ_PREAMBLE_LONGS_EMPTY: u8 = 1;
+const FREQ_PREAMBLE_LONGS_NONEMPTY: u8 = 4;
+const FREQ_EMPTY_FLAG_MASK: u8 = 5;
+
+fn empty_header(lg_max: u8, lg_cur: u8) -> Vec<u8> {
+ let mut bytes = SketchBytes::with_capacity(8);
+ bytes.write_u8(FREQ_PREAMBLE_LONGS_EMPTY);
+ bytes.write_u8(FREQ_SERIAL_VERSION);
+ bytes.write_u8(FREQ_FAMILY_ID);
+ bytes.write_u8(lg_max);
+ bytes.write_u8(lg_cur);
+ bytes.write_u8(FREQ_EMPTY_FLAG_MASK);
+ bytes.write_u16_le(0);
+ bytes.into_bytes()
+}
+
+// Regression: a corrupt header must never panic (or trigger an oversized
+// allocation) inside `with_lg_map_sizes`; deserialize must reject it cleanly.
+// Before the fix, `lg_max_map_size = 222` drove `1usize << lg_max` past the
+// width of `usize`, panicking with "attempt to shift left with overflow" in
+// debug builds.
+#[test]
+fn test_deserialize_rejects_out_of_range_lg_max_map_size() {
+ let bytes = empty_header(222, 5);
+ let result = FrequentItemsSketch::<i64>::deserialize(&bytes);
+ assert_that!(result, err(anything()));
+ assert_eq!(result.unwrap_err().kind(), ErrorKind::InvalidData);
+}
+
+#[test]
+fn test_deserialize_rejects_out_of_range_lg_max_map_size_nonempty() {
+ let mut bytes = SketchBytes::with_capacity(16);
+ bytes.write_u8(FREQ_PREAMBLE_LONGS_NONEMPTY);
+ bytes.write_u8(FREQ_SERIAL_VERSION);
+ bytes.write_u8(FREQ_FAMILY_ID);
+ bytes.write_u8(200); // lg_max_map_size, out of range
+ bytes.write_u8(3); // lg_cur_map_size
+ bytes.write_u8(0); // flags (not empty)
+ bytes.write_u16_le(0);
+ bytes.write_u32_le(0); // active_items
+ bytes.write_u32_le(0);
+ bytes.write_u64_le(0); // stream_weight
+ bytes.write_u64_le(0); // offset
+ let result = FrequentItemsSketch::<i64>::deserialize(&bytes.into_bytes());
+ assert_that!(result, err(anything()));
+}
+
+// `lg_cur_map_size` below the documented minimum is also corruption; the C++
+// reference `check_size` rejects it, so the Rust port must too.
+#[test]
+fn test_deserialize_rejects_undersized_lg_cur_map_size() {
+ let bytes = empty_header(10, 1);
+ let result = FrequentItemsSketch::<i64>::deserialize(&bytes);
+ assert_that!(result, err(anything()));
+}
+
+// The largest supported configuration must remain cheap while the sketch is
+// empty and round-trip through the public constructor and serializer.
+#[test]
+fn test_maximum_map_size_empty_round_trip() {
+ let sketch = FrequentItemsSketch::<i64>::new(1usize << 30);
+ let bytes = sketch.serialize();
+ let restored = FrequentItemsSketch::<i64>::deserialize(&bytes).unwrap();
+ assert!(restored.is_empty());
+ assert_eq!(restored.lg_max_map_size(), 30);
+ assert_eq!(restored.lg_cur_map_size(), 3);
+}
+
+// Builds a minimal non-empty (four-preamble-long) header. The caller supplies
+// `lg_max`, `lg_cur`, and `active_items`; no item payload is appended, so this
+// is only useful for exercising the header-consistency guards that run before
+// the payload is read.
+fn nonempty_header(lg_max: u8, lg_cur: u8, active_items: u32) -> Vec<u8> {
+ let mut bytes = SketchBytes::with_capacity(32);
+ bytes.write_u8(FREQ_PREAMBLE_LONGS_NONEMPTY);
+ bytes.write_u8(FREQ_SERIAL_VERSION);
+ bytes.write_u8(FREQ_FAMILY_ID);
+ bytes.write_u8(lg_max);
+ bytes.write_u8(lg_cur);
+ bytes.write_u8(0); // flags (not empty)
+ bytes.write_u16_le(0);
+ bytes.write_u32_le(active_items);
+ bytes.write_u32_le(0); // unused
+ bytes.write_u64_le(0); // stream_weight
+ bytes.write_u64_le(0); // offset
+ bytes.into_bytes()
+}
+
+// Regression for tisonkun's report on #224: the accepted boundary
+// `(lg_max, lg_cur) = (30, 30)` on an *empty* header still drove
+// `ReversePurgeItemHashMap::new(1 << 30)` (~1e9 slots, multi-GB) before any
+// payload was read. An empty sketch holds nothing, so it must now build its
map
+// at the minimum size and deserialize cheaply instead of attempting the
+// allocation. If the fix regressed, this test would OOM/hang rather than fail.
+#[test]
+fn test_deserialize_empty_header_does_not_over_allocate() {
+ let bytes = empty_header(30, 30);
+ let restored = FrequentItemsSketch::<i64>::deserialize(&bytes).unwrap();
+ assert!(restored.is_empty());
+ assert_eq!(restored.num_active_items(), 0);
+ assert_eq!(restored.lg_max_map_size(), 30);
+ assert_eq!(restored.lg_cur_map_size(), 3);
+}
+
+// A non-empty header whose `lg_cur_map_size` is too small to hold the claimed
+// `active_items` under the load factor is corrupt: a map of `1 << 3` slots has
+// capacity 6, so it can never hold 100 active items. Reject it instead of
+// trusting the header.
+#[test]
+fn test_deserialize_rejects_lg_cur_inconsistent_with_num_active() {
+ let bytes = nonempty_header(10, 3, 100);
+ let result = FrequentItemsSketch::<i64>::deserialize(&bytes);
+ assert_that!(result, err(anything()));
+ assert_eq!(result.unwrap_err().kind(), ErrorKind::InvalidData);
+}
+
+// A non-empty header claiming a huge `active_items` that the remaining bytes
+// cannot possibly contain must be rejected before any capacity is reserved
from
+// that count, so a corrupt header cannot drive a multi-GB `Vec` allocation.
+#[test]
+fn test_deserialize_rejects_num_active_exceeding_payload() {
+ // 700_000_000 <= capacity implied by lg_cur = 30, so it clears the
capacity
+ // guard, but there are no item bytes for it, so the length guard rejects
it.
+ let bytes = nonempty_header(30, 30, 700_000_000);
+ let result = FrequentItemsSketch::<i64>::deserialize(&bytes);
+ assert_that!(result, err(anything()));
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
