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]
