You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@datasketches.apache.org by "jaideeppyne (via GitHub)" <gi...@apache.org> on 2026/08/26 00:53:32 UTC
[PR] fix(cpc): reject malformed input on deserialize instead of panicking (datasketches-rust)
jaideeppyne opened a new pull request, #226:
URL: https://github.com/apache/datasketches-rust/pull/226
## Description
`CpcSketch::deserialize` returns a `Result`, but malformed or corrupt bytes could reach the FM85 decompressor and panic rather than returning an error. A fuzzer over single-byte mutations of valid sketches found reachable panics in release builds, including:
- index-out-of-bounds in `maybe_fill_bitbuf` when the compressed stream is truncated;
- out-of-range window / pair-table indexing when a decoded pair row exceeds `k`;
- failed asserts on the sliding-window offset and column permutation;
- divide-by-zero / arithmetic overflow from inconsistent header fields.
This is the same "reject invalid states on deserialize" theme as #218/#221 (REQ) and #224 (frequencies); CPC was uncovered.
## Fix
The decompression read path (`uncompress` and its callees, used only during deserialization) is now fallible. `deserialize` validates the header up front — coupon-space bound on `num_coupons`, flavor-vs-flags consistency, and `table_num_entries` bounds (which also caps the decode allocation) — and the decompressor bounds-checks every compressed-word read and rejects any decoded pair whose row falls outside `[0, 2^lg_k)` before it is used. The happy-path decode logic is unchanged.
## Compatibility
Valid sketches are unaffected: the Java, C++, and Go serialization round-trips still pass byte-for-byte, and a new round-trip test asserts identical estimates and re-serialized bytes across all flavors.
## Tests
Adds `tests/cpc_test/deserialize.rs`: a corruption fuzzer that must never panic, targeted corruptions that must return `Err`, and a valid-sketch round-trip check. Before this change the fuzzer/targeted tests panic; after, they pass. `cargo fmt` and `cargo clippy -D warnings` are clean.
Note: a separate, pre-existing 32-bit overflow in `determine_pseudo_phase` for `lg_k >= 21` (reachable from serialize as well) is out of scope here and left for a follow-up.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix(cpc): reject malformed input on deserialize instead of panicking (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun closed pull request #226: fix(cpc): reject malformed input on deserialize instead of panicking
URL: https://github.com/apache/datasketches-rust/pull/226
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix(cpc): reject malformed input on deserialize instead of panicking (datasketches-rust)
Posted by "jaideeppyne (via GitHub)" <gi...@apache.org>.
jaideeppyne commented on code in PR #226:
URL: https://github.com/apache/datasketches-rust/pull/226#discussion_r3921791280
##########
datasketches/src/cpc/compression.rs:
##########
@@ -403,116 +404,154 @@ impl CompressedState {
let mut next_true_pair = 0;
for i in 0..self.table_num_entries {
let row_col = pairs[i as usize];
- assert_ne!(row_col, u32::MAX);
+ if row_col == u32::MAX {
+ return Err(Error::deserial("CPC hybrid table contains an invalid pair"));
+ }
let col = row_col & 63;
Review Comment:
The successor #227 removes this hybrid-loop sentinel branch and validates the sentinel in the low-level pair decoder, with a dedicated regression test. Since #227 merged and superseded this PR, this specific finding is addressed there.
##########
datasketches/src/cpc/sketch.rs:
##########
@@ -639,7 +639,54 @@ impl CpcSketch {
)));
}
- let uncompressed = compressed.uncompress(lg_k, num_coupons);
+ // The coupon space of a sketch has `k * 64` cells (`k` rows of 64 columns each), so a
+ // valid sketch can never report more coupons than that. Rejecting larger values keeps the
+ // flavor arithmetic below from overflowing on corrupt input.
+ if (num_coupons as u64) > 64 * (1u64 << lg_k) {
+ return Err(Error::deserial(format!(
+ "num_coupons ({}) exceeds coupon space for lg_k = {}",
+ num_coupons, lg_k
+ )));
+ }
+
+ // A valid sketch stores a sliding window exactly for the pinned and sliding flavors, and
+ // stores its coupons in the surprising-value table for the sparse and hybrid flavors. The
+ // flavor is fully determined by `lg_k` and `num_coupons`, so the flags must agree with it.
+ let flavor = determine_flavor(lg_k, num_coupons);
+ let window_expected = matches!(flavor, Flavor::Pinned | Flavor::Sliding);
Review Comment:
The HIP part needs a distinction: `serialize()` sets `has_hip = !merge_flag` even for an empty sketch, so rejecting that flag solely because `num_coupons == 0` would reject valid output. The window/flavor check rejects an empty sketch with a window. The zero-coupon/table-flag case is still permissive in the successor code I inspected; I am not claiming that part is fixed. This PR was superseded by #227, so I am leaving that residual finding visible rather than reopening the old patch.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix(cpc): reject malformed input on deserialize instead of panicking (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on PR #226:
URL: https://github.com/apache/datasketches-rust/pull/226#issuecomment-5422755830
Superseded by #227, which incorporates the fallible CPC decompression work, retains Jaideep Pyne as a co-author on the CPC commit, and extends the audit across the other sketch deserializers.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix(cpc): reject malformed input on deserialize instead of panicking (datasketches-rust)
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #226:
URL: https://github.com/apache/datasketches-rust/pull/226#discussion_r3858827197
##########
datasketches/src/cpc/sketch.rs:
##########
@@ -639,7 +639,54 @@ impl CpcSketch {
)));
}
- let uncompressed = compressed.uncompress(lg_k, num_coupons);
+ // The coupon space of a sketch has `k * 64` cells (`k` rows of 64 columns each), so a
+ // valid sketch can never report more coupons than that. Rejecting larger values keeps the
+ // flavor arithmetic below from overflowing on corrupt input.
+ if (num_coupons as u64) > 64 * (1u64 << lg_k) {
+ return Err(Error::deserial(format!(
+ "num_coupons ({}) exceeds coupon space for lg_k = {}",
+ num_coupons, lg_k
+ )));
+ }
+
+ // A valid sketch stores a sliding window exactly for the pinned and sliding flavors, and
+ // stores its coupons in the surprising-value table for the sparse and hybrid flavors. The
+ // flavor is fully determined by `lg_k` and `num_coupons`, so the flags must agree with it.
+ let flavor = determine_flavor(lg_k, num_coupons);
+ let window_expected = matches!(flavor, Flavor::Pinned | Flavor::Sliding);
Review Comment:
`num_coupons == 0` implies `Flavor::Empty`, but the deserializer currently allows `has_hip` / `has_table` / `has_window` flags to be set in that case (because the flavor/flag consistency checks only constrain window for pinned/sliding and table for sparse/hybrid). This accepts serialized states that `serialize()` cannot produce and undermines the goal of rejecting malformed inputs early.
##########
datasketches/src/cpc/compression.rs:
##########
@@ -403,116 +404,154 @@ impl CompressedState {
let mut next_true_pair = 0;
for i in 0..self.table_num_entries {
let row_col = pairs[i as usize];
- assert_ne!(row_col, u32::MAX);
+ if row_col == u32::MAX {
+ return Err(Error::deserial("CPC hybrid table contains an invalid pair"));
+ }
let col = row_col & 63;
Review Comment:
In hybrid uncompression, `validate_pair_rows(&pairs, lg_k)?` runs before this loop, which already rejects `u32::MAX` (row index is far out of range). That makes the `row_col == u32::MAX` branch unreachable, and the more specific error message here will never be returned. Either remove this check or move it before row validation (and/or incorporate the check into `validate_pair_rows`).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix(cpc): reject malformed input on deserialize instead of panicking (datasketches-rust)
Posted by "jaideeppyne (via GitHub)" <gi...@apache.org>.
jaideeppyne commented on PR #226:
URL: https://github.com/apache/datasketches-rust/pull/226#issuecomment-5423436441
Thanks — and thanks for keeping the co-authorship. Extending the audit across the other sketch deserializers is the right call; happy to see it land that way.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org