tisonkun opened a new issue, #187: URL: https://github.com/apache/datasketches-rust/issues/187
## Problem A non-empty Bloom image contains both its bit array and a cached `num_bits_set` value. `BloomFilter::deserialize` recomputes the count only when the serialized value is the dirty sentinel (`u64::MAX`). Every other in-range value is trusted without checking it against the bit array. For example, serializing a filter containing an item and changing only the cached count to zero produces an image that is accepted with: - a non-empty bit array, - `is_empty() == true`, and - `contains(inserted_item) == false` because membership queries short-circuit on `is_empty()`. This turns inconsistent serialized metadata into a false negative, contradicting the Bloom filter contract and the deserializer documentation that corrupted input is rejected. Reviewed revision: `4266ad9cad21e0660c2ae9506174e01665bd100d`. ## Expected behavior For a non-empty image, deserialization must verify that a non-dirty cached count equals the population count of the decoded bit array. A mismatch should return `ErrorKind::InvalidData`. The dirty sentinel remains valid and should trigger a recount. ## Relationship to other implementations The current Java heap and direct readers also trust a non-dirty cached count and recount only `-1`: https://github.com/apache/datasketches-java/blob/4067ffefabbcd03944dc3617ff2948ab760f3b75/src/main/java/org/apache/datasketches/filters/bloomfilter/HeapBitArray.java#L57-L83 https://github.com/apache/datasketches-java/blob/4067ffefabbcd03944dc3617ff2948ab760f3b75/src/main/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayR.java#L43-L54 The current C++ and Go readers use the same dirty-sentinel behavior: https://github.com/apache/datasketches-cpp/blob/c22888581964fc490feee835766cc8c3adb722e0/filters/include/bloom_filter_impl.hpp#L286-L314 https://github.com/apache/datasketches-go/blob/c558cc2d64f9a307c196a7adb0067eadd1b776f7/filters/bloom_filter_builder.go#L245-L269 The proposed Rust validation is intentionally stricter than the current reference readers. It does not change the wire format or reject any internally consistent image, including dirty images; it only rejects corrupt metadata that can violate the no-false-negative guarantee. ## Proposed fix Always compute the population count after reading a non-empty bit array. Use the computed count for the dirty sentinel, and reject any other serialized count that differs from it. ## Acceptance criteria - Add regression coverage for a zero cached count over a non-empty bit array. - Cover at least one non-zero undercount or overcount. - Verify that the dirty sentinel is still accepted and recomputed. - Verify valid Java, C++, and Go snapshots continue to deserialize. - Return `ErrorKind::InvalidData` for inconsistent counts. - Run the repository check, test, and lint workflows. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
