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]
