diff --git a/src/test/fuzz/CMakeLists.txt b/src/test/fuzz/CMakeLists.txt
--- a/src/test/fuzz/CMakeLists.txt
+++ b/src/test/fuzz/CMakeLists.txt
@@ -75,6 +75,7 @@
 endfunction()
 
 add_regular_fuzz_targets(
+	addition_overflow
 	addrdb
 	asmap
 	base_encode_decode
@@ -84,9 +85,12 @@
 	bloom_filter
 	cashaddr
 	chain
+	checkqueue
+	cuckoocache
 	descriptor_parse
 	eval_script
 	fee_rate
+	fees
 	flatfile
 	float
 	hex
diff --git a/src/test/fuzz/addition_overflow.cpp b/src/test/fuzz/addition_overflow.cpp
new file mode 100644
--- /dev/null
+++ b/src/test/fuzz/addition_overflow.cpp
@@ -0,0 +1,54 @@
+// 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<uint8_t>(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
--- /dev/null
+++ b/src/test/fuzz/checkqueue.cpp
@@ -0,0 +1,58 @@
+// 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 <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
--- /dev/null
+++ b/src/test/fuzz/cuckoocache.cpp
@@ -0,0 +1,60 @@
+// 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 <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>();
+    }
+};
+
+struct FuzzCuckooCacheKey {
+    bool b;
+
+public:
+    FuzzCuckooCacheKey(bool _b = false) : b(_b){};
+    operator bool() const { return b; }
+};
+} // 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<CuckooCache::KeyOnly<FuzzCuckooCacheKey>, 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(
+                FuzzCuckooCacheKey(fuzzed_data_provider.ConsumeBool()));
+        } else {
+            cuckoo_cache.contains(
+                FuzzCuckooCacheKey(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
--- /dev/null
+++ b/src/test/fuzz/fees.cpp
@@ -0,0 +1,27 @@
+// 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 <feerate.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 Amount current_minimum_fee = ConsumeMoney(fuzzed_data_provider);
+        const Amount 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
--- a/src/test/fuzz/integer.cpp
+++ b/src/test/fuzz/integer.cpp
@@ -34,10 +34,12 @@
 
 #include <test/fuzz/FuzzedDataProvider.h>
 #include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
 
 #include <cassert>
 #include <chrono>
 #include <limits>
+#include <set>
 #include <vector>
 
 void initialize() {
@@ -101,10 +103,15 @@
     }
     (void)GetSizeOfCompactSize(u64);
     (void)GetSpecialScriptSize(u32);
-    // function defined only for a subset of int64_t inputs
-    // ()GetVirtualTransactionSize(i64, i64);
-    // function defined only for a subset of int64_t/uint32_t inputs
-    // ()GetVirtualTransactionSize(i64, i64, u32);
+    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 * SATOSHI);
     (void)ToString(i64);
@@ -122,6 +129,13 @@
     (void)memusage::DynamicUsage(u8);
     const uint8_t uch = static_cast<uint8_t>(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
--- a/src/test/fuzz/util.h
+++ b/src/test/fuzz/util.h
@@ -136,4 +136,14 @@
     }
 }
 
+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