Merge #18565: tests: Add fuzzing harnesses for classes/functions in policy/fees.h, checkqueue.h and cuckoocache.h. Add fuzzing coverage.

283bd72156959f420f13acc7a34e513ca3446025 tests: Add coverage of {,Incremental}DynamicUsage(const std::set<X, Y>& s) to existing fuzzer (practicalswift)
bf76000493082da05bf7258a5038e16fa76cd143 tests: Add fuzzing harness for classes/functions in cuckoocache.h (practicalswift)
57890b2555ca347373109052f6789c23f46bc594 tests: Add fuzzing harness for classes/functions in checkqueue.h (practicalswift)
2df5701e902effa93834d9520690cbaca7e504f3 tests: Add coverage of GetVirtualTransactionSize(...) to existing fuzzer (practicalswift)
7b9a2dc86426926038b2f49d3d4ce4cb64dcd14b tests: Add fuzzing harness for AdditionOverflow(...) (practicalswift)
44fb2a596b4a1aa70253c4145c35be6de68da22a tests: Add fuzzing harness for FeeFilterRounder (practicalswift)

Pull request description:

  Includes:

  ```
  tests: Add fuzzing harness for FeeFilterRounder
  tests: Add fuzzing harness for classes/functions in checkqueue.h
  tests: Add fuzzing harness for classes/functions in cuckoocache.h
  tests: Add coverage of {,Incremental}DynamicUsage(const std::set<X, Y>& s) to existing fuzzer
  tests: Add coverage of GetVirtualTransactionSize(...) to existing fuzzer
  tests: Add fuzzing harness for AdditionOverflow(...)
  ```

  See [`doc/fuzzing.md`](https://github.com/bitcoin/bitcoin/blob/master/doc/fuzzing.md) for information on how to fuzz Bitcoin Core.

ACKs for top commit:
  MarcoFalke:
    ACK 283bd72156959f420f13acc7a34e513ca3446025

Tree-SHA512: 2361edfb5c47741b22d9fb996836c5250c5a26bc5e956039ea6a0c55ba2d36c78f241d66f85bc02f5b85b9b83d5fde56a5c4702b9d1b7ac4a9a3ae391ca79eaa

8 files changed, 249 insertions, 2 deletions

diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 3443ee089d..e775ae43a1 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -3,6 +3,7 @@
 # file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 FUZZ_TARGETS = \
+  test/fuzz/addition_overflow \
   test/fuzz/addr_info_deserialize \
   test/fuzz/addrdb \
   test/fuzz/address_deserialize \
@@ -27,13 +28,16 @@ FUZZ_TARGETS = \
   test/fuzz/bloom_filter \
   test/fuzz/bloomfilter_deserialize \
   test/fuzz/chain \
+  test/fuzz/checkqueue \
   test/fuzz/coins_deserialize \
+  test/fuzz/cuckoocache \
   test/fuzz/decode_tx \
   test/fuzz/descriptor_parse \
   test/fuzz/diskblockindex_deserialize \
   test/fuzz/eval_script \
   test/fuzz/fee_rate \
   test/fuzz/fee_rate_deserialize \
+  test/fuzz/fees \
   test/fuzz/flat_file_pos_deserialize \
   test/fuzz/flatfile \
   test/fuzz/float \
@@ -280,6 +284,12 @@ endif
 
 if ENABLE_FUZZ
 
+test_fuzz_addition_overflow_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
+test_fuzz_addition_overflow_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
+test_fuzz_addition_overflow_LDADD = $(FUZZ_SUITE_LD_COMMON)
+test_fuzz_addition_overflow_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
+test_fuzz_addition_overflow_SOURCES = test/fuzz/addition_overflow.cpp
+
 test_fuzz_addr_info_deserialize_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) -DADDR_INFO_DESERIALIZE=1
 test_fuzz_addr_info_deserialize_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
 test_fuzz_addr_info_deserialize_LDADD = $(FUZZ_SUITE_LD_COMMON)
@@ -424,12 +434,24 @@ test_fuzz_chain_LDADD = $(FUZZ_SUITE_LD_COMMON)
 test_fuzz_chain_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
 test_fuzz_chain_SOURCES = test/fuzz/chain.cpp
 
+test_fuzz_checkqueue_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
+test_fuzz_checkqueue_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
+test_fuzz_checkqueue_LDADD = $(FUZZ_SUITE_LD_COMMON)
+test_fuzz_checkqueue_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
+test_fuzz_checkqueue_SOURCES = test/fuzz/checkqueue.cpp
+
 test_fuzz_coins_deserialize_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) -DCOINS_DESERIALIZE=1
 test_fuzz_coins_deserialize_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
 test_fuzz_coins_deserialize_LDADD = $(FUZZ_SUITE_LD_COMMON)
 test_fuzz_coins_deserialize_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
 test_fuzz_coins_deserialize_SOURCES = test/fuzz/deserialize.cpp
 
+test_fuzz_cuckoocache_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
+test_fuzz_cuckoocache_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
+test_fuzz_cuckoocache_LDADD = $(FUZZ_SUITE_LD_COMMON)
+test_fuzz_cuckoocache_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
+test_fuzz_cuckoocache_SOURCES = test/fuzz/cuckoocache.cpp
+
 test_fuzz_decode_tx_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
 test_fuzz_decode_tx_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
 test_fuzz_decode_tx_LDADD = $(FUZZ_SUITE_LD_COMMON)
@@ -466,6 +488,12 @@ test_fuzz_fee_rate_deserialize_LDADD = $(FUZZ_SUITE_LD_COMMON)
 test_fuzz_fee_rate_deserialize_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
 test_fuzz_fee_rate_deserialize_SOURCES = test/fuzz/deserialize.cpp
 
+test_fuzz_fees_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
+test_fuzz_fees_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
+test_fuzz_fees_LDADD = $(FUZZ_SUITE_LD_COMMON)
+test_fuzz_fees_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
+test_fuzz_fees_SOURCES = test/fuzz/fees.cpp
+
 test_fuzz_flat_file_pos_deserialize_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) -DFLAT_FILE_POS_DESERIALIZE=1
 test_fuzz_flat_file_pos_deserialize_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
 test_fuzz_flat_file_pos_deserialize_LDADD = $(FUZZ_SUITE_LD_COMMON)
diff --git a/src/cuckoocache.h b/src/cuckoocache.h
index 4ad5818cdc..2daf676c4a 100644
--- a/src/cuckoocache.h
+++ b/src/cuckoocache.h
@@ -5,6 +5,7 @@
 #ifndef BITCOIN_CUCKOOCACHE_H
 #define BITCOIN_CUCKOOCACHE_H
 
+#include <algorithm> // std::find
 #include <array>
 #include <atomic>
 #include <cmath>
diff --git a/src/test/fuzz/addition_overflow.cpp b/src/test/fuzz/addition_overflow.cpp
new file mode 100644
index 0000000000..a455992b13
--- /dev/null
+++ b/src/test/fuzz/addition_overflow.cpp
@@ -0,0 +1,55 @@
+// Copyright (c) 2020 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+
+#include <cstdint>
+#include <string>
+#include <vector>
+
+#if defined(__has_builtin)
+#if __has_builtin(__builtin_add_overflow)
+#define HAVE_BUILTIN_ADD_OVERFLOW
+#endif
+#elif defined(__GNUC__) && (__GNUC__ >= 5)
+#define HAVE_BUILTIN_ADD_OVERFLOW
+#endif
+
+namespace {
+template <typename T>
+void TestAdditionOverflow(FuzzedDataProvider& fuzzed_data_provider)
+{
+    const T i = fuzzed_data_provider.ConsumeIntegral<T>();
+    const T j = fuzzed_data_provider.ConsumeIntegral<T>();
+    const bool is_addition_overflow_custom = AdditionOverflow(i, j);
+#if defined(HAVE_BUILTIN_ADD_OVERFLOW)
+    T result_builtin;
+    const bool is_addition_overflow_builtin = __builtin_add_overflow(i, j, &result_builtin);
+    assert(is_addition_overflow_custom == is_addition_overflow_builtin);
+    if (!is_addition_overflow_custom) {
+        assert(i + j == result_builtin);
+    }
+#else
+    if (!is_addition_overflow_custom) {
+        (void)(i + j);
+    }
+#endif
+}
+} // namespace
+
+void test_one_input(const std::vector<uint8_t>& buffer)
+{
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    TestAdditionOverflow<int64_t>(fuzzed_data_provider);
+    TestAdditionOverflow<uint64_t>(fuzzed_data_provider);
+    TestAdditionOverflow<int32_t>(fuzzed_data_provider);
+    TestAdditionOverflow<uint32_t>(fuzzed_data_provider);
+    TestAdditionOverflow<int16_t>(fuzzed_data_provider);
+    TestAdditionOverflow<uint16_t>(fuzzed_data_provider);
+    TestAdditionOverflow<char>(fuzzed_data_provider);
+    TestAdditionOverflow<unsigned char>(fuzzed_data_provider);
+    TestAdditionOverflow<signed char>(fuzzed_data_provider);
+}
diff --git a/src/test/fuzz/checkqueue.cpp b/src/test/fuzz/checkqueue.cpp
new file mode 100644
index 0000000000..2ed097b827
--- /dev/null
+++ b/src/test/fuzz/checkqueue.cpp
@@ -0,0 +1,65 @@
+// Copyright (c) 2020 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <checkqueue.h>
+#include <optional.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+
+#include <cstdint>
+#include <string>
+#include <vector>
+
+namespace {
+struct DumbCheck {
+    const bool result = false;
+
+    DumbCheck() = default;
+
+    explicit DumbCheck(const bool _result) : result(_result)
+    {
+    }
+
+    bool operator()() const
+    {
+        return result;
+    }
+
+    void swap(DumbCheck& x)
+    {
+    }
+};
+} // namespace
+
+void test_one_input(const std::vector<uint8_t>& buffer)
+{
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+
+    const unsigned int batch_size = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(0, 1024);
+    CCheckQueue<DumbCheck> check_queue_1{batch_size};
+    CCheckQueue<DumbCheck> check_queue_2{batch_size};
+    std::vector<DumbCheck> checks_1;
+    std::vector<DumbCheck> checks_2;
+    const int size = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 1024);
+    for (int i = 0; i < size; ++i) {
+        const bool result = fuzzed_data_provider.ConsumeBool();
+        checks_1.emplace_back(result);
+        checks_2.emplace_back(result);
+    }
+    if (fuzzed_data_provider.ConsumeBool()) {
+        check_queue_1.Add(checks_1);
+    }
+    if (fuzzed_data_provider.ConsumeBool()) {
+        (void)check_queue_1.Wait();
+    }
+
+    CCheckQueueControl<DumbCheck> check_queue_control{&check_queue_2};
+    if (fuzzed_data_provider.ConsumeBool()) {
+        check_queue_control.Add(checks_2);
+    }
+    if (fuzzed_data_provider.ConsumeBool()) {
+        (void)check_queue_control.Wait();
+    }
+}
diff --git a/src/test/fuzz/cuckoocache.cpp b/src/test/fuzz/cuckoocache.cpp
new file mode 100644
index 0000000000..f674efe1b1
--- /dev/null
+++ b/src/test/fuzz/cuckoocache.cpp
@@ -0,0 +1,49 @@
+// Copyright (c) 2020 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <cuckoocache.h>
+#include <optional.h>
+#include <script/sigcache.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+#include <test/util/setup_common.h>
+
+#include <cstdint>
+#include <string>
+#include <vector>
+
+namespace {
+FuzzedDataProvider* fuzzed_data_provider_ptr = nullptr;
+
+struct RandomHasher {
+    template <uint8_t>
+    uint32_t operator()(const bool& /* unused */) const
+    {
+        assert(fuzzed_data_provider_ptr != nullptr);
+        return fuzzed_data_provider_ptr->ConsumeIntegral<uint32_t>();
+    }
+};
+} // namespace
+
+void test_one_input(const std::vector<uint8_t>& buffer)
+{
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    fuzzed_data_provider_ptr = &fuzzed_data_provider;
+    CuckooCache::cache<bool, RandomHasher> cuckoo_cache{};
+    if (fuzzed_data_provider.ConsumeBool()) {
+        const size_t megabytes = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, 16);
+        cuckoo_cache.setup_bytes(megabytes << 20);
+    } else {
+        cuckoo_cache.setup(fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, 4096));
+    }
+    while (fuzzed_data_provider.ConsumeBool()) {
+        if (fuzzed_data_provider.ConsumeBool()) {
+            cuckoo_cache.insert(fuzzed_data_provider.ConsumeBool());
+        } else {
+            cuckoo_cache.contains(fuzzed_data_provider.ConsumeBool(), fuzzed_data_provider.ConsumeBool());
+        }
+    }
+    fuzzed_data_provider_ptr = nullptr;
+}
diff --git a/src/test/fuzz/fees.cpp b/src/test/fuzz/fees.cpp
new file mode 100644
index 0000000000..090994263e
--- /dev/null
+++ b/src/test/fuzz/fees.cpp
@@ -0,0 +1,26 @@
+// Copyright (c) 2020 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <amount.h>
+#include <optional.h>
+#include <policy/fees.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+
+#include <cstdint>
+#include <string>
+#include <vector>
+
+void test_one_input(const std::vector<uint8_t>& buffer)
+{
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    const CFeeRate minimal_incremental_fee{ConsumeMoney(fuzzed_data_provider)};
+    FeeFilterRounder fee_filter_rounder{minimal_incremental_fee};
+    while (fuzzed_data_provider.ConsumeBool()) {
+        const CAmount current_minimum_fee = ConsumeMoney(fuzzed_data_provider);
+        const CAmount rounded_fee = fee_filter_rounder.round(current_minimum_fee);
+        assert(MoneyRange(rounded_fee));
+    }
+}
diff --git a/src/test/fuzz/integer.cpp b/src/test/fuzz/integer.cpp
index fff2fabd17..7c2537aaf5 100644
--- a/src/test/fuzz/integer.cpp
+++ b/src/test/fuzz/integer.cpp
@@ -23,6 +23,7 @@
 #include <streams.h>
 #include <test/fuzz/FuzzedDataProvider.h>
 #include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
 #include <time.h>
 #include <uint256.h>
 #include <util/moneystr.h>
@@ -35,6 +36,7 @@
 #include <cassert>
 #include <chrono>
 #include <limits>
+#include <set>
 #include <vector>
 
 void initialize()
@@ -90,8 +92,12 @@ void test_one_input(const std::vector<uint8_t>& buffer)
     }
     (void)GetSizeOfCompactSize(u64);
     (void)GetSpecialScriptSize(u32);
-    // (void)GetVirtualTransactionSize(i64, i64); // function defined only for a subset of int64_t inputs
-    // (void)GetVirtualTransactionSize(i64, i64, u32); // function defined only for a subset of int64_t/uint32_t inputs
+    if (!MultiplicationOverflow(i64, static_cast<int64_t>(::nBytesPerSigOp)) && !AdditionOverflow(i64 * ::nBytesPerSigOp, static_cast<int64_t>(4))) {
+        (void)GetVirtualTransactionSize(i64, i64);
+    }
+    if (!MultiplicationOverflow(i64, static_cast<int64_t>(u32)) && !AdditionOverflow(i64, static_cast<int64_t>(4)) && !AdditionOverflow(i64 * u32, static_cast<int64_t>(4))) {
+        (void)GetVirtualTransactionSize(i64, i64, u32);
+    }
     (void)HexDigit(ch);
     (void)MoneyRange(i64);
     (void)ToString(i64);
@@ -109,6 +115,12 @@ void test_one_input(const std::vector<uint8_t>& buffer)
     (void)memusage::DynamicUsage(u8);
     const unsigned char uch = static_cast<unsigned char>(u8);
     (void)memusage::DynamicUsage(uch);
+    {
+        const std::set<int64_t> i64s{i64, static_cast<int64_t>(u64)};
+        const size_t dynamic_usage = memusage::DynamicUsage(i64s);
+        const size_t incremental_dynamic_usage = memusage::IncrementalDynamicUsage(i64s);
+        assert(dynamic_usage == incremental_dynamic_usage * i64s.size());
+    }
     (void)MillisToTimeval(i64);
     const double d = ser_uint64_to_double(u64);
     assert(ser_double_to_uint64(d) == u64);
diff --git a/src/test/fuzz/util.h b/src/test/fuzz/util.h
index b70ea6d90e..ba4b012f95 100644
--- a/src/test/fuzz/util.h
+++ b/src/test/fuzz/util.h
@@ -120,4 +120,15 @@ NODISCARD bool MultiplicationOverflow(const T i, const T j) noexcept
     }
 }
 
+template <class T>
+NODISCARD bool AdditionOverflow(const T i, const T j) noexcept
+{
+    static_assert(std::is_integral<T>::value, "Integral required.");
+    if (std::numeric_limits<T>::is_signed) {
+        return (i > 0 && j > std::numeric_limits<T>::max() - i) ||
+               (i < 0 && j < std::numeric_limits<T>::min() - i);
+    }
+    return std::numeric_limits<T>::max() - i < j;
+}
+
 #endif // BITCOIN_TEST_FUZZ_UTIL_H