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 bb86d439db494e3d362e54cc4f83481893974335
Author: Lee Rhodes <[email protected]>
AuthorDate: Fri Oct 30 13:51:04 2026 -0700

    KLL: check k, the number of levels and the levels array when deserializing
    
    deserialize() used the serialized levels array without checking it. A
    level beyond the capacity, or a level that starts before the previous
    one, put level boundaries outside the items buffer, and the bytes
    overload read the levels array without checking the input size.
    
    Both overloads now check that k >= MIN_K, that there is at least one
    level, that the input holds the levels array, and that each level starts
    at or after the previous one and no later than the capacity.
    
    Co-Authored-By: Claude Opus 5.5 <[email protected]>
---
 kll/include/kll_sketch.hpp      |  3 ++
 kll/include/kll_sketch_impl.hpp | 35 +++++++++++++++++++++
 kll/test/kll_sketch_test.cpp    | 70 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 108 insertions(+)

diff --git a/kll/include/kll_sketch.hpp b/kll/include/kll_sketch.hpp
index d672c419..39cac445 100644
--- a/kll/include/kll_sketch.hpp
+++ b/kll/include/kll_sketch.hpp
@@ -591,10 +591,13 @@ class kll_sketch {
     uint32_t safe_level_size(uint8_t level) const;
     uint32_t get_num_retained_above_level_zero() const;
 
+    static void check_k(uint16_t k);
     static void check_m(uint8_t m);
     static void check_preamble_ints(uint8_t preamble_ints, uint8_t flags_byte);
     static void check_serial_version(uint8_t serial_version);
     static void check_family_id(uint8_t family_id);
+    static void check_num_levels(uint8_t num_levels);
+    static void check_levels(const vector_u32& levels);
 
     void check_sorting() const;
 
diff --git a/kll/include/kll_sketch_impl.hpp b/kll/include/kll_sketch_impl.hpp
index b12a39c8..a1d0c4da 100644
--- a/kll/include/kll_sketch_impl.hpp
+++ b/kll/include/kll_sketch_impl.hpp
@@ -450,6 +450,7 @@ kll_sketch<T, C, A> kll_sketch<T, C, 
A>::deserialize(std::istream& is, const Ser
   const auto m = read<uint8_t>(is);
   read<uint8_t>(is); // skip unused byte
 
+  check_k(k);
   check_m(m);
   check_preamble_ints(preamble_ints, flags_byte);
   check_serial_version(serial_version);
@@ -472,6 +473,7 @@ kll_sketch<T, C, A> kll_sketch<T, C, 
A>::deserialize(std::istream& is, const Ser
     min_k = read<uint16_t>(is);
     num_levels = read<uint8_t>(is);
     read<uint8_t>(is); // skip unused byte
+    check_num_levels(num_levels);
   }
   vector_u32 levels(num_levels + 1, 0, allocator);
   const uint32_t capacity(kll_helper::compute_total_capacity(k, m, 
num_levels));
@@ -480,8 +482,10 @@ kll_sketch<T, C, A> kll_sketch<T, C, 
A>::deserialize(std::istream& is, const Ser
   } else {
     // the last integer in levels_ is not serialized because it can be derived
     read(is, levels.data(), sizeof(levels[0]) * num_levels);
+    if (!is.good()) throw std::runtime_error("error reading from 
std::istream");
   }
   levels[num_levels] = capacity;
+  check_levels(levels);
   optional<T> min_item;
   optional<T> max_item;
   if (!is_single_item) {
@@ -537,6 +541,7 @@ kll_sketch<T, C, A> kll_sketch<T, C, A>::deserialize(const 
void* bytes, size_t s
   ptr += copy_from_mem(ptr, m);
   ptr += sizeof(uint8_t); // skip unused byte
 
+  check_k(k);
   check_m(m);
   check_preamble_ints(preamble_ints, flags_byte);
   check_serial_version(serial_version);
@@ -560,6 +565,7 @@ kll_sketch<T, C, A> kll_sketch<T, C, A>::deserialize(const 
void* bytes, size_t s
     ptr += copy_from_mem(ptr, min_k);
     ptr += copy_from_mem(ptr, num_levels);
     ptr += sizeof(uint8_t); // skip unused byte
+    check_num_levels(num_levels);
   }
   vector_u32 levels(num_levels + 1, 0, allocator);
   const uint32_t capacity(kll_helper::compute_total_capacity(k, m, 
num_levels));
@@ -567,9 +573,11 @@ kll_sketch<T, C, A> kll_sketch<T, C, A>::deserialize(const 
void* bytes, size_t s
     levels[0] = capacity - 1;
   } else {
     // the last integer in levels_ is not serialized because it can be derived
+    ensure_minimum_memory(size, (ptr - static_cast<const char*>(bytes)) + 
sizeof(levels[0]) * num_levels);
     ptr += copy_from_mem(ptr, levels.data(), sizeof(levels[0]) * num_levels);
   }
   levels[num_levels] = capacity;
+  check_levels(levels);
   optional<T> min_item;
   optional<T> max_item;
   if (!is_single_item) {
@@ -867,6 +875,14 @@ uint32_t kll_sketch<T, C, 
A>::get_num_retained_above_level_zero() const {
   return levels_[num_levels_] - levels_[1];
 }
 
+template<typename T, typename C, typename A>
+void kll_sketch<T, C, A>::check_k(uint16_t k) {
+  if (k < kll_constants::MIN_K) {
+    throw std::invalid_argument("Possible corruption: K must be >= " + 
std::to_string(kll_constants::MIN_K)
+        + ": " + std::to_string(k));
+  }
+}
+
 template<typename T, typename C, typename A>
 void kll_sketch<T, C, A>::check_m(uint8_t m) {
   if (m != kll_constants::DEFAULT_M) {
@@ -909,6 +925,25 @@ void kll_sketch<T, C, A>::check_family_id(uint8_t 
family_id) {
   }
 }
 
+template<typename T, typename C, typename A>
+void kll_sketch<T, C, A>::check_num_levels(uint8_t num_levels) {
+  if (num_levels == 0) {
+    throw std::invalid_argument("Possible corruption: number of levels must be 
> 0");
+  }
+}
+
+// The last entry is the capacity. Each level must start at or after the 
previous one,
+// so every level lies within the items buffer.
+template<typename T, typename C, typename A>
+void kll_sketch<T, C, A>::check_levels(const vector_u32& levels) {
+  for (size_t i = 1; i < levels.size(); ++i) {
+    if (levels[i - 1] > levels[i]) {
+      throw std::invalid_argument("Possible corruption: levels[" + 
std::to_string(i - 1) + "] = "
+          + std::to_string(levels[i - 1]) + " > levels[" + std::to_string(i) + 
"] = " + std::to_string(levels[i]));
+    }
+  }
+}
+
 template <typename T, typename C, typename A>
 string<A> kll_sketch<T, C, A>::to_string(bool print_levels, bool print_items) 
const {
   // Using a temporary stream for implementation here does not comply with 
AllocatorAwareContainer requirements.
diff --git a/kll/test/kll_sketch_test.cpp b/kll/test/kll_sketch_test.cpp
index b8d0b031..cb09473e 100644
--- a/kll/test/kll_sketch_test.cpp
+++ b/kll/test/kll_sketch_test.cpp
@@ -835,4 +835,74 @@ TEST_CASE("kll sketch", "[kll_sketch]") {
   REQUIRE(test_allocator_total_bytes == 0);
 }
 
+
+TEST_CASE("kll sketch: deserialize rejects inconsistent levels", 
"[kll_sketch]") {
+  using vector_bytes = kll_sketch<int>::vector_bytes;
+  const size_t k_offset = 4;
+  const size_t num_levels_offset = 18;
+  const size_t levels_offset = 20;
+  auto put_u32 = [](vector_bytes& bytes, size_t offset, uint32_t value) {
+    std::memcpy(bytes.data() + offset, &value, sizeof(value));
+  };
+  auto get_u32 = [](const vector_bytes& bytes, size_t offset) {
+    uint32_t value;
+    std::memcpy(&value, bytes.data() + offset, sizeof(value));
+    return value;
+  };
+  auto check_rejected = [](const vector_bytes& bytes) {
+    REQUIRE_THROWS_AS(kll_sketch<int>::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(kll_sketch<int>::deserialize(s), std::invalid_argument);
+  };
+
+  kll_sketch<int> one_level(8);
+  for (int i = 0; i < 3; ++i) one_level.update(i);
+  kll_sketch<int> three_levels(8);
+  for (int i = 0; i < 40; ++i) three_levels.update(i);
+  REQUIRE(three_levels.serialize()[num_levels_offset] == 3);
+
+  SECTION("first level beyond capacity") {
+    auto bytes = one_level.serialize();
+    put_u32(bytes, levels_offset, 1009);
+    check_rejected(bytes);
+  }
+
+  SECTION("level beyond capacity") {
+    auto bytes = three_levels.serialize();
+    put_u32(bytes, levels_offset + sizeof(uint32_t), 100000);
+    check_rejected(bytes);
+  }
+
+  SECTION("decreasing levels") {
+    auto bytes = three_levels.serialize();
+    REQUIRE(get_u32(bytes, levels_offset) > 0);
+    put_u32(bytes, levels_offset + sizeof(uint32_t), 0);
+    check_rejected(bytes);
+  }
+
+  SECTION("zero levels") {
+    auto bytes = three_levels.serialize();
+    bytes[num_levels_offset] = 0;
+    check_rejected(bytes);
+  }
+
+  SECTION("k below minimum") {
+    auto bytes = three_levels.serialize();
+    const uint16_t k = 4;
+    std::memcpy(bytes.data() + k_offset, &k, sizeof(k));
+    check_rejected(bytes);
+  }
+
+  SECTION("levels beyond the input") {
+    auto bytes = three_levels.serialize();
+    bytes[num_levels_offset] = 40;
+    bytes.resize(levels_offset);
+    REQUIRE_THROWS_AS(kll_sketch<int>::deserialize(bytes.data(), 
bytes.size()), std::out_of_range);
+    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(kll_sketch<int>::deserialize(s), std::runtime_error);
+  }
+}
+
 } /* namespace datasketches */


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

Reply via email to