Merge bitcoin/bitcoin#35818: bloom: avoid undefined sizing calculations
What changed, and why it matters
This commit fixes a bug in Bitcoin Core's Bloom filter constructor that could perform undefined math when given unusual inputs, such as zero elements or a zero/invalid false-positive rate. The fix adds input checks and special-case handling so the constructor no longer divides by zero, takes the logarithm of zero, or converts an out-of-range floating-point size to an integer. The affected constructor is used only in tests and fuzzing, not in normal peer-to-peer network code, so the practical risk to live Bitcoin nodes is low.
No immediate action is required for production nodes. Developers should ensure the patched constructor is used in all new tests and fuzz targets, and consider whether any other code paths construct CBloomFilter with user-controlled nElements/nFPRate values that could reach the fixed helper.
Security signals we found
Undefined behavior in size calculation: conversion of out-of-range double to unsigned int
Divide-by-zero in hash-function count when nElements is zero
log(0) / FE_DIVBYZERO when false-positive rate is zero
Missing validation of false-positive rate range and finiteness
Constructor used by fuzz target and unit tests, not by network deserialization path
Evidence from the diff
The four-argument CBloomFilter constructor previously computed vData.size() as std::min((unsigned int)(-1/LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM_FILTER_SIZE8)/8 and nHashFuncs as std::min((unsigned int)(vData.size()8/nElementsLN2), MAX_HASH_FUNCS). This produced undefined behavior for nElements==0 (divide by zero in nHashFuncs), nFPRate==0 (log(0) and possible FE_DIVBYZERO), non-finite or out-of-range nFPRate (NaN/negative/>1), and valid inputs whose computed size exceeded unsigned int range before the clamp. The patch introduces a BloomFilterSize helper that asserts nFPRate is finite and in [0,1], returns 0 for zero elements, returns the maximum permitted size for zero false-positive rate with positive elements, and clamps the floating-point size to MAX_BLOOM_FILTER_SIZE8.0 before converting to unsigned int. It also guards nHashFuncs against division by zero. Tests and fuzz coverage are added for these boundary cases.
Changed components
src/common/bloom.cppsrc/common/bloom.hsrc/test/bloom_tests.cppsrc/test/fuzz/bloom_filter.cppInspect captured patch +75 / −4
### src/common/bloom.cpp
@@ -11,6 +11,7 @@
#include <script/solver.h>
#include <span.h>
#include <streams.h>
+#include <util/check.h>
#include <util/fastrange.h>
#include <util/overflow.h>
@@ -22,19 +23,27 @@
static constexpr double LN2SQUARED = 0.4804530139182014246671025263266649717305529515945455;
static constexpr double LN2 = 0.6931471805599453094172321214581765680755001343602552;
+static unsigned int BloomFilterSize(const unsigned int elements, const double false_positive_rate)
+{
+ Assert(std::isfinite(false_positive_rate) && false_positive_rate >= 0 && false_positive_rate <= 1);
+ if (elements == 0) return 0; // Must precede the zero-rate case to preserve empty-filter semantics.
+ if (false_positive_rate == 0) return MAX_BLOOM_FILTER_SIZE; // Avoid log(0) raising FE_DIVBYZERO.
+ return std::min(-1 / LN2SQUARED * elements * log(false_positive_rate), MAX_BLOOM_FILTER_SIZE * 8.0) / 8;
+}
+
CBloomFilter::CBloomFilter(const unsigned int nElements, const double nFPRate, const unsigned int nTweakIn, unsigned char nFlagsIn) :
/**
* The ideal size for a bloom filter with a given number of elements and false positive rate is:
* - nElements * log(fp rate) / ln(2)^2
* We ignore filter parameters which will create a bloom filter larger than the protocol limits
*/
- vData(std::min((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM_FILTER_SIZE * 8) / 8),
+ vData(BloomFilterSize(nElements, nFPRate)),
/**
* The ideal number of hash functions is filter size * ln(2) / number of elements
* Again, we ignore filter parameters which will create a bloom filter with more hash functions than the protocol limits
* See https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these formulas
*/
- nHashFuncs(std::min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)),
+ nHashFuncs(nElements == 0 ? 0 : std::min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)),
nTweak(nTweakIn),
nFlags(nFlagsIn)
{
### src/common/bloom.h
@@ -55,6 +55,8 @@ class CBloomFilter
public:
/**
* Creates a new bloom filter which will provide the given fp rate when filled with the given number of elements
+ * nFPRate must be in [0, 1].
+ * An nElements of 0 creates an empty filter which ignores inserts and matches everything.
* Note that if the given parameters will result in a filter outside the bounds of the protocol limits,
* the filter created will be as close to the given parameters as possible within the protocol limits.
* This will apply if nFPRate is very low or nElements is unreasonably high.
### src/test/bloom_tests.cpp
@@ -17,8 +17,12 @@
#include <test/util/random.h>
#include <test/util/setup_common.h>
#include <uint256.h>
+#include <util/check.h>
#include <util/strencodings.h>
+#include <cfenv>
+#include <cmath>
+#include <limits>
#include <vector>
#include <boost/test/unit_test.hpp>
@@ -58,6 +62,53 @@ BOOST_AUTO_TEST_CASE(bloom_create_insert_serialize)
BOOST_CHECK_MESSAGE( filter.contains("99108ad8ed9bb6274d3980bab5a85c048f0950c8"_hex_u8), "Bloom filter doesn't contain just-inserted object!");
}
+BOOST_AUTO_TEST_CASE(bloom_create_filter_size)
+{
+ auto filter_size{[](unsigned int elements, double false_positive_rate) {
+ DataStream stream{};
+ stream << CBloomFilter{elements, false_positive_rate, /*nTweak=*/0, BLOOM_UPDATE_ALL};
+ return ReadCompactSize(stream);
+ }};
+
+ BOOST_CHECK_EQUAL(filter_size(/*elements=*/10, /*false_positive_rate=*/0.01), 11);
+ BOOST_CHECK_EQUAL(filter_size(/*elements=*/10'000'000, /*false_positive_rate=*/0.01), MAX_BLOOM_FILTER_SIZE);
+ BOOST_CHECK_EQUAL(filter_size(/*elements=*/1, /*false_positive_rate=*/1), 0);
+
+ std::feclearexcept(FE_ALL_EXCEPT);
+ BOOST_CHECK_EQUAL(filter_size(/*elements=*/0, /*false_positive_rate=*/0), 0);
+ // Negative zero compares equal to zero, so it is a valid zero rate.
+ BOOST_CHECK_EQUAL(filter_size(/*elements=*/1, /*false_positive_rate=*/-0.0), MAX_BLOOM_FILTER_SIZE);
+ BOOST_CHECK_EQUAL(filter_size(/*elements=*/1, /*false_positive_rate=*/0), MAX_BLOOM_FILTER_SIZE);
+ BOOST_CHECK_EQUAL(filter_size(std::numeric_limits<unsigned int>::max(), /*false_positive_rate=*/0.01), MAX_BLOOM_FILTER_SIZE);
+ for (double rate : {std::numeric_limits<double>::denorm_min(), std::numeric_limits<double>::min(), std::numeric_limits<double>::epsilon()}) {
+ const auto size{filter_size(/*elements=*/1, rate)};
+ BOOST_CHECK_GT(size, 0);
+ BOOST_CHECK_LE(size, MAX_BLOOM_FILTER_SIZE);
+ }
+ BOOST_REQUIRE_EQUAL(std::fetestexcept(FE_DIVBYZERO | FE_INVALID), 0);
+}
+
+BOOST_AUTO_TEST_CASE(bloom_create_insert_empty)
+{
+ CBloomFilter filter{/*nElements=*/1, /*nFPRate=*/1, /*nTweak=*/0, BLOOM_UPDATE_ALL};
+ BOOST_CHECK(filter.IsWithinSizeConstraints());
+ filter.insert("beef"_hex_u8);
+ BOOST_CHECK(filter.contains("beef"_hex_u8));
+ BOOST_CHECK(filter.contains("deadbeef"_hex_u8)); // An empty filter holds no bits, so it matches everything
+}
+
+BOOST_AUTO_TEST_CASE(bloom_create_invalid_false_positive_rate)
+{
+ test_only_CheckFailuresAreExceptionsNotAborts mock_checks{};
+
+ BOOST_CHECK_EXCEPTION((CBloomFilter{1, std::numeric_limits<double>::signaling_NaN(), /*nTweak=*/0, BLOOM_UPDATE_ALL}), NonFatalCheckError, HasReason{"Internal bug detected"}); // Classifying a signaling NaN may raise FE_INVALID
+ std::feclearexcept(FE_ALL_EXCEPT);
+ for (double rate : {-std::numeric_limits<double>::infinity(), -std::numeric_limits<double>::denorm_min(), std::nextafter(1.0, 2.0), std::numeric_limits<double>::infinity(), std::numeric_limits<double>::quiet_NaN()}) {
+ BOOST_CHECK_EXCEPTION((CBloomFilter{1, rate, /*nTweak=*/0, BLOOM_UPDATE_ALL}), NonFatalCheckError, HasReason{"Internal bug detected"});
+ }
+ BOOST_REQUIRE_EQUAL(std::fetestexcept(FE_DIVBYZERO | FE_INVALID), 0);
+}
+
BOOST_AUTO_TEST_CASE(bloom_create_insert_serialize_with_tweak)
{
// Same test as bloom_create_insert_serialize, but we add a nTweak of 100
### src/test/fuzz/bloom_filter.cpp
@@ -19,9 +19,18 @@ FUZZ_TARGET(bloom_filter)
FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
bool good_data{true};
+ const auto false_positive_rate{fuzzed_data_provider.ConsumeBool() ?
+ fuzzed_data_provider.ConsumeProbability<double>() :
+ fuzzed_data_provider.PickValueInArray({
+ 0.0,
+ std::numeric_limits<double>::denorm_min(),
+ std::numeric_limits<double>::min(),
+ std::numeric_limits<double>::epsilon(),
+ 1.0,
+ })};
CBloomFilter bloom_filter{
- fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(1, 10000000),
- 1.0 / fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(1, std::numeric_limits<unsigned int>::max()),
+ fuzzed_data_provider.ConsumeIntegral<unsigned int>(),
+ false_positive_rate,
fuzzed_data_provider.ConsumeIntegral<unsigned int>(),
static_cast<unsigned char>(fuzzed_data_provider.PickValueInArray({BLOOM_UPDATE_NONE, BLOOM_UPDATE_ALL, BLOOM_UPDATE_P2PUBKEY_ONLY, BLOOM_UPDATE_MASK}))};
LIMITED_WHILE (good_data && fuzzed_data_provider.remaining_bytes() > 0, 10'000) {Why this scored 35/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.