This is an automated email from the ASF dual-hosted git repository.

leerho pushed a commit to branch 5.3.x
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git

commit 9839ffd2ccc038d453e38b545750a5ed2d589dea
Author: Lee Rhodes <[email protected]>
AuthorDate: Fri Oct 30 13:51:04 2026 -0700

    REQ: check k and the compactor headers when deserializing
    
    deserialize() used the compactor header fields without checking them.
    A section size or number of sections of zero gave a nominal capacity of
    zero, so the buffer did not grow on the next update. The bytes overload
    checked 8 of the 20 header bytes. Large lg_weight and number of
    sections values made shifts undefined, and a non-empty sketch with no
    items read past the end of its only compactor.
    
    Both overloads now check:
    - k is even and in [MIN_K, MAX_K]
    - a non-empty sketch has at least one level, and exactly one with raw
      items, and a single level holds at least one item
    - compactor i has lg_weight i
    - the section size rounds to an even value in [MIN_K, k]
    - the number of sections is in [1, 64], and the raw section size,
      rounded to an integer, times the number of sections is at most k * k,
      as in datasketches-java
    The bytes overload checks the input holds the full compactor header.
    
    Co-Authored-By: Claude Opus 5.5 <[email protected]>
---
 req/include/req_compactor.hpp      |   5 +-
 req/include/req_compactor_impl.hpp |  34 ++++++++-
 req/include/req_sketch.hpp         |   2 +
 req/include/req_sketch_impl.hpp    |  29 +++++++-
 req/test/req_sketch_test.cpp       | 143 +++++++++++++++++++++++++++++++++++++
 5 files changed, 206 insertions(+), 7 deletions(-)

diff --git a/req/include/req_compactor.hpp b/req/include/req_compactor.hpp
index f013e49d..87ddf1b3 100755
--- a/req/include/req_compactor.hpp
+++ b/req/include/req_compactor.hpp
@@ -87,11 +87,11 @@ public:
 
   template<typename S>
   static req_compactor deserialize(std::istream& is, const S& serde, const 
Comparator& comparator,
-      const Allocator& allocator, bool sorted, bool hra);
+      const Allocator& allocator, bool sorted, bool hra, uint16_t k, uint8_t 
level);
 
   template<typename S>
   static std::pair<req_compactor, size_t> deserialize(const void* bytes, 
size_t size, const S& serde,
-      const Comparator& comparator, const Allocator& allocator, bool sorted, 
bool hra);
+      const Comparator& comparator, const Allocator& allocator, bool sorted, 
bool hra, uint16_t k, uint8_t level);
 
   template<typename S>
   static req_compactor deserialize(std::istream& is, const S& serde, const 
Comparator& comparator,
@@ -122,6 +122,7 @@ private:
   void ensure_space(uint32_t num);
 
   static uint32_t nearest_even(float value);
+  static void check_header(uint16_t k, uint8_t level, uint8_t lg_weight, float 
section_size_raw, uint8_t num_sections);
 
   template<typename InIter, typename OutIter>
   static void promote_evens_or_odds(InIter from, InIter to, bool flag, OutIter 
dst);
diff --git a/req/include/req_compactor_impl.hpp 
b/req/include/req_compactor_impl.hpp
index 72aafc94..bcc276c6 100755
--- a/req/include/req_compactor_impl.hpp
+++ b/req/include/req_compactor_impl.hpp
@@ -326,6 +326,30 @@ uint32_t req_compactor<T, C, A>::nearest_even(float value) 
{
   return static_cast<uint32_t>(round(value / 2)) << 1;
 }
 
+template<typename T, typename C, typename A>
+void req_compactor<T, C, A>::check_header(uint16_t k, uint8_t level, uint8_t 
lg_weight, float section_size_raw,
+    uint8_t num_sections) {
+  // the sketch creates the compactor at level h with lg_weight h
+  if (lg_weight != level) {
+    throw std::invalid_argument("Possible corruption: compactor " + 
std::to_string(level) + " has lg_weight "
+        + std::to_string(lg_weight));
+  }
+  // the section size starts at k and shrinks to no less than MIN_K
+  // (the first check is false for NaN and keeps nearest_even() in range)
+  const uint32_t section_size = (section_size_raw > 0 && section_size_raw <= k 
+ 1) ? nearest_even(section_size_raw) : 0;
+  if (section_size < req_constants::MIN_K || section_size > k) {
+    throw std::invalid_argument("Possible corruption: section size " + 
std::to_string(section_size_raw)
+        + " is out of range for k " + std::to_string(k));
+  }
+  // the number of sections starts at 3 and doubles, and must keep 1 << 
(num_sections - 1) defined
+  // the limit uses the raw section size: when that has shrunk to 3, the even 
section size is 4 and can exceed it
+  const uint32_t rounded_section_size = 
static_cast<uint32_t>(round(section_size_raw));
+  if (num_sections < 1 || num_sections > 64 || rounded_section_size * 
num_sections > static_cast<uint32_t>(k) * k) {
+    throw std::invalid_argument("Possible corruption: number of sections " + 
std::to_string(num_sections)
+        + " is out of range for section size " + 
std::to_string(section_size_raw) + " and k " + std::to_string(k));
+  }
+}
+
 template<typename T, typename C, typename A>
 template<typename InIter, typename OutIter>
 void req_compactor<T, C, A>::promote_evens_or_odds(InIter from, InIter to, 
bool odds, OutIter dst) {
@@ -394,13 +418,15 @@ size_t req_compactor<T, C, A>::serialize(void* dst, 
size_t capacity, const S& se
 template<typename T, typename C, typename A>
 template<typename S>
 req_compactor<T, C, A> req_compactor<T, C, A>::deserialize(std::istream& is, 
const S& serde,
-    const C& comparator, const A& allocator, bool sorted, bool hra) {
+    const C& comparator, const A& allocator, bool sorted, bool hra, uint16_t 
k, uint8_t level) {
   auto state = read<decltype(state_)>(is);
   auto section_size_raw = read<decltype(section_size_raw_)>(is);
   auto lg_weight = read<decltype(lg_weight_)>(is);
   auto num_sections = read<decltype(num_sections_)>(is);
   read<uint16_t>(is); // padding
   auto num_items = read<uint32_t>(is);
+  if (!is.good()) throw std::runtime_error("error reading from std::istream");
+  check_header(k, level, lg_weight, section_size_raw, num_sections);
   auto items = deserialize_items(is, serde, allocator, num_items);
   return req_compactor(hra, lg_weight, sorted, section_size_raw, num_sections, 
state, std::move(items), num_items,
       comparator, allocator);
@@ -431,8 +457,9 @@ auto req_compactor<T, C, 
A>::deserialize_items(std::istream& is, const S& serde,
 template<typename T, typename C, typename A>
 template<typename S>
 std::pair<req_compactor<T, C, A>, size_t> req_compactor<T, C, 
A>::deserialize(const void* bytes, size_t size,
-    const S& serde, const C& comparator, const A& allocator, bool sorted, bool 
hra) {
-  ensure_minimum_memory(size, 8);
+    const S& serde, const C& comparator, const A& allocator, bool sorted, bool 
hra, uint16_t k, uint8_t level) {
+  ensure_minimum_memory(size, sizeof(state_) + sizeof(section_size_raw_) + 
sizeof(lg_weight_) + sizeof(num_sections_)
+      + sizeof(uint16_t) + sizeof(num_items_));
   const char* ptr = static_cast<const char*>(bytes);
   const char* end_ptr = static_cast<const char*>(bytes) + size;
 
@@ -447,6 +474,7 @@ std::pair<req_compactor<T, C, A>, size_t> req_compactor<T, 
C, A>::deserialize(co
   ptr += 2; // padding
   uint32_t num_items;
   ptr += copy_from_mem(ptr, num_items);
+  check_header(k, level, lg_weight, section_size_raw, num_sections);
   auto pair = deserialize_items(ptr, end_ptr - ptr, serde, allocator, 
num_items);
   ptr += pair.second;
   return std::pair<req_compactor, size_t>(
diff --git a/req/include/req_sketch.hpp b/req/include/req_sketch.hpp
index 2e2bc309..ed6d11f7 100755
--- a/req/include/req_sketch.hpp
+++ b/req/include/req_sketch.hpp
@@ -465,7 +465,9 @@ private:
       optional<T>&& min_item, optional<T>&& max_item,
       std::vector<Compactor, AllocCompactor>&& compactors, const Comparator& 
comparator);
 
+  static void check_k(uint16_t k);
   static void check_preamble_ints(uint8_t preamble_ints, uint8_t num_levels);
+  static void check_num_levels(uint8_t num_levels, bool raw_items);
   static void check_serial_version(uint8_t serial_version);
   static void check_family_id(uint8_t family_id);
 
diff --git a/req/include/req_sketch_impl.hpp b/req/include/req_sketch_impl.hpp
index 8acea8bc..3c1cb408 100755
--- a/req/include/req_sketch_impl.hpp
+++ b/req/include/req_sketch_impl.hpp
@@ -456,6 +456,7 @@ req_sketch<T, C, A> req_sketch<T, C, 
A>::deserialize(std::istream& is, const Ser
   const auto num_levels = read<uint8_t>(is);
   const auto num_raw_items = read<uint8_t>(is);
 
+  check_k(k);
   check_preamble_ints(preamble_ints, num_levels);
   check_serial_version(serial_version);
   check_family_id(family_id);
@@ -469,6 +470,7 @@ req_sketch<T, C, A> req_sketch<T, C, 
A>::deserialize(std::istream& is, const Ser
   optional<T> max_item;
 
   const bool raw_items = flags_byte & (1 << flags::RAW_ITEMS);
+  check_num_levels(num_levels, raw_items);
   const bool is_level_0_sorted = flags_byte & (1 << 
flags::IS_LEVEL_ZERO_SORTED);
   std::vector<Compactor, AllocCompactor> compactors(allocator);
 
@@ -494,10 +496,12 @@ req_sketch<T, C, A> req_sketch<T, C, 
A>::deserialize(std::istream& is, const Ser
     compactors.push_back(Compactor::deserialize(is, sd, comparator, allocator, 
is_level_0_sorted, k, num_raw_items, hra));
   } else {
     for (size_t i = 0; i < num_levels; ++i) {
-      compactors.push_back(Compactor::deserialize(is, sd, comparator, 
allocator, i == 0 ? is_level_0_sorted : true, hra));
+      compactors.push_back(Compactor::deserialize(is, sd, comparator, 
allocator, i == 0 ? is_level_0_sorted : true, hra,
+          k, static_cast<uint8_t>(i)));
     }
   }
   if (num_levels == 1) {
+    if (compactors[0].get_num_items() == 0) throw 
std::invalid_argument("Possible corruption: non-empty sketch with no items");
     const auto begin = compactors[0].begin();
     const auto end = compactors[0].end();
     n = compactors[0].get_num_items();
@@ -537,6 +541,7 @@ req_sketch<T, C, A> req_sketch<T, C, A>::deserialize(const 
void* bytes, size_t s
   uint8_t num_raw_items;
   ptr += copy_from_mem(ptr, num_raw_items);
 
+  check_k(k);
   check_preamble_ints(preamble_ints, num_levels);
   check_serial_version(serial_version);
   check_family_id(family_id);
@@ -549,6 +554,7 @@ req_sketch<T, C, A> req_sketch<T, C, A>::deserialize(const 
void* bytes, size_t s
   optional<T> max_item;
 
   const bool raw_items = flags_byte & (1 << flags::RAW_ITEMS);
+  check_num_levels(num_levels, raw_items);
   const bool is_level_0_sorted = flags_byte & (1 << 
flags::IS_LEVEL_ZERO_SORTED);
   std::vector<Compactor, AllocCompactor> compactors(allocator);
 
@@ -577,12 +583,14 @@ req_sketch<T, C, A> req_sketch<T, C, 
A>::deserialize(const void* bytes, size_t s
     ptr += pair.second;
   } else {
     for (size_t i = 0; i < num_levels; ++i) {
-      auto pair = Compactor::deserialize(ptr, end_ptr - ptr, sd, comparator, 
allocator, i == 0 ? is_level_0_sorted : true, hra);
+      auto pair = Compactor::deserialize(ptr, end_ptr - ptr, sd, comparator, 
allocator, i == 0 ? is_level_0_sorted : true, hra,
+          k, static_cast<uint8_t>(i));
       compactors.push_back(std::move(pair.first));
       ptr += pair.second;
     }
   }
   if (num_levels == 1) {
+    if (compactors[0].get_num_items() == 0) throw 
std::invalid_argument("Possible corruption: non-empty sketch with no items");
     const auto begin = compactors[0].begin();
     const auto end = compactors[0].end();
     n = compactors[0].get_num_items();
@@ -706,6 +714,23 @@ sorted_view_(nullptr)
   update_num_retained();
 }
 
+template<typename T, typename C, typename A>
+void req_sketch<T, C, A>::check_k(uint16_t k) {
+  if (k < req_constants::MIN_K || k > req_constants::MAX_K || (k & 1) != 0) {
+    throw std::invalid_argument("Possible corruption: k must be even and in 
the range ["
+        + std::to_string(req_constants::MIN_K) + ", " + 
std::to_string(req_constants::MAX_K) + "]: " + std::to_string(k));
+  }
+}
+
+template<typename T, typename C, typename A>
+void req_sketch<T, C, A>::check_num_levels(uint8_t num_levels, bool raw_items) 
{
+  // a non-empty sketch has at least one compactor, and raw items fit in one
+  if (num_levels == 0 || (raw_items && num_levels != 1)) {
+    throw std::invalid_argument("Possible corruption: number of levels " + 
std::to_string(num_levels)
+        + (raw_items ? " with raw items" : ""));
+  }
+}
+
 template<typename T, typename C, typename A>
 void req_sketch<T, C, A>::check_preamble_ints(uint8_t preamble_ints, uint8_t 
num_levels) {
   const uint8_t expected_preamble_ints = num_levels > 1 ? 4 : 2;
diff --git a/req/test/req_sketch_test.cpp b/req/test/req_sketch_test.cpp
index c8cf5cbe..6cff32b9 100755
--- a/req/test/req_sketch_test.cpp
+++ b/req/test/req_sketch_test.cpp
@@ -23,6 +23,7 @@
 
 #include <fstream>
 #include <sstream>
+#include <cstring>
 #include <limits>
 #include <stdexcept>
 
@@ -592,4 +593,146 @@ TEST_CASE("get_rank equivalence") {
 //  sketch.serialize(os);
 //}
 
+
+template<typename Bytes, typename V>
+static void put_value(Bytes& bytes, size_t offset, V value) {
+  std::memcpy(bytes.data() + offset, &value, sizeof(value));
+}
+
+TEST_CASE("req sketch: deserialize rejects inconsistent compactors", 
"[req_sketch]") {
+  using vector_bytes = req_sketch<float>::vector_bytes;
+  // preamble: k at 4, number of levels at 6, number of raw items at 7
+  // compactor: state(8), section size(4), lg_weight(1), number of 
sections(1), padding(2), number of items(4), items
+  const size_t k_offset = 4;
+  const size_t num_levels_offset = 6;
+  const size_t num_raw_items_offset = 7;
+  const size_t estimation_compactor = 24; // after the preamble, n, min and max
+  const size_t exact_compactor = 8; // after the preamble
+  const size_t section_size = 8;
+  const size_t lg_weight = 12;
+  const size_t num_sections = 13;
+  const size_t num_items = 16;
+  const size_t items = 20;
+  auto check_rejected = [](const vector_bytes& bytes) {
+    REQUIRE_THROWS_AS(req_sketch<float>::deserialize(bytes.data(), 
bytes.size()), std::invalid_argument);
+    std::stringstream s(std::ios::in | std::ios::out | std::ios::binary);
+    s.write(reinterpret_cast<const char*>(bytes.data()), bytes.size());
+    REQUIRE_THROWS_AS(req_sketch<float>::deserialize(s), 
std::invalid_argument);
+  };
+
+  req_sketch<float> raw(12);
+  for (int i = 0; i < 3; ++i) raw.update(static_cast<float>(i));
+  req_sketch<float> exact(12);
+  for (int i = 0; i < 50; ++i) exact.update(static_cast<float>(i));
+  req_sketch<float> estimation(12);
+  for (int i = 0; i < 1000; ++i) estimation.update(static_cast<float>(i));
+  REQUIRE(estimation.serialize()[num_levels_offset] > 2);
+
+  SECTION("valid images") {
+    // sketches deep enough for the sections to have grown, in both rank 
accuracy modes
+    for (bool hra: {true, false}) {
+      req_sketch<float> sketch(12, hra);
+      for (int i = 0; i < 1000000; ++i) sketch.update(static_cast<float>(i));
+      auto bytes = sketch.serialize();
+      REQUIRE(req_sketch<float>::deserialize(bytes.data(), 
bytes.size()).get_n() == sketch.get_n());
+      std::stringstream s(std::ios::in | std::ios::out | std::ios::binary);
+      sketch.serialize(s);
+      REQUIRE(req_sketch<float>::deserialize(s).get_n() == sketch.get_n());
+    }
+  }
+
+  SECTION("valid images with the smallest section size") {
+    // the raw section size has shrunk to 3, which the section size rounds up 
to 4
+    req_sketch<float> sketch(6);
+    for (int i = 0; i < 100000; ++i) sketch.update(static_cast<float>(i));
+    auto bytes = sketch.serialize();
+    float raw_section_size;
+    std::memcpy(&raw_section_size, bytes.data() + estimation_compactor + 
section_size, sizeof(raw_section_size));
+    REQUIRE(raw_section_size == Approx(3).margin(0.001));
+    REQUIRE(bytes[estimation_compactor + num_sections] == 12);
+    REQUIRE(req_sketch<float>::deserialize(bytes.data(), bytes.size()).get_n() 
== sketch.get_n());
+    std::stringstream s(std::ios::in | std::ios::out | std::ios::binary);
+    sketch.serialize(s);
+    REQUIRE(req_sketch<float>::deserialize(s).get_n() == sketch.get_n());
+
+    // k = 12 needs about 2 billion items to get here, so set the header it 
would have
+    bytes = estimation.serialize();
+    put_value(bytes, estimation_compactor + section_size, 3.0f);
+    put_value(bytes, estimation_compactor + num_sections, 
static_cast<uint8_t>(48));
+    REQUIRE(req_sketch<float>::deserialize(bytes.data(), bytes.size()).get_n() 
== estimation.get_n());
+  }
+
+  SECTION("invalid k") {
+    for (uint16_t k: {2, 13, 2000}) {
+      auto bytes = estimation.serialize();
+      put_value(bytes, k_offset, k);
+      check_rejected(bytes);
+    }
+  }
+
+  SECTION("section size out of range") {
+    for (float size: {0.0f, 2.0f, 14.0f, 1e12f, 
std::numeric_limits<float>::quiet_NaN()}) {
+      auto bytes = estimation.serialize();
+      put_value(bytes, estimation_compactor + section_size, size);
+      check_rejected(bytes);
+    }
+  }
+
+  SECTION("number of sections out of range") {
+    for (uint8_t sections: {0, 65}) {
+      auto bytes = estimation.serialize();
+      put_value(bytes, estimation_compactor + num_sections, sections);
+      check_rejected(bytes);
+    }
+    // in range, but too many for this section size and k
+    auto bytes = estimation.serialize();
+    put_value(bytes, estimation_compactor + section_size, 3.0f);
+    put_value(bytes, estimation_compactor + num_sections, 
static_cast<uint8_t>(64));
+    check_rejected(bytes);
+  }
+
+  SECTION("wrong lg_weight") {
+    for (uint8_t weight: {1, 70}) {
+      auto bytes = estimation.serialize();
+      put_value(bytes, estimation_compactor + lg_weight, weight);
+      check_rejected(bytes);
+    }
+    auto bytes = exact.serialize();
+    put_value(bytes, exact_compactor + lg_weight, static_cast<uint8_t>(1));
+    check_rejected(bytes);
+    // the second compactor repeats the first one's lg_weight
+    bytes = estimation.serialize();
+    uint32_t count;
+    std::memcpy(&count, bytes.data() + estimation_compactor + num_items, 
sizeof(count));
+    const size_t second_compactor = estimation_compactor + items + count * 
sizeof(float);
+    REQUIRE(bytes[second_compactor + lg_weight] == 1);
+    put_value(bytes, second_compactor + lg_weight, static_cast<uint8_t>(0));
+    check_rejected(bytes);
+  }
+
+  SECTION("no levels") {
+    auto bytes = exact.serialize();
+    bytes[num_levels_offset] = 0;
+    check_rejected(bytes);
+    bytes = raw.serialize();
+    bytes[num_levels_offset] = 0;
+    check_rejected(bytes);
+  }
+
+  SECTION("no items") {
+    auto bytes = exact.serialize();
+    put_value(bytes, exact_compactor + num_items, static_cast<uint32_t>(0));
+    check_rejected(bytes);
+    bytes = raw.serialize();
+    bytes[num_raw_items_offset] = 0;
+    check_rejected(bytes);
+  }
+
+  SECTION("compactor header beyond the input") {
+    auto bytes = estimation.serialize();
+    bytes.resize(estimation_compactor + 10);
+    REQUIRE_THROWS_AS(req_sketch<float>::deserialize(bytes.data(), 
bytes.size()), std::out_of_range);
+  }
+}
+
 } /* namespace datasketches */


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to