diff options
| -rw-r--r-- | src/Makefile.test.include | 1 | ||||
| -rw-r--r-- | src/net.cpp | 82 | ||||
| -rw-r--r-- | src/net.h | 32 | ||||
| -rw-r--r-- | src/test/fuzz/node_eviction.cpp | 1 | ||||
| -rw-r--r-- | src/test/net_peer_eviction_tests.cpp | 348 | ||||
| -rw-r--r-- | src/test/net_tests.cpp | 143 |
6 files changed, 439 insertions, 168 deletions
diff --git a/src/Makefile.test.include b/src/Makefile.test.include index e00f17a83f..c5b1c065ce 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -101,6 +101,7 @@ BITCOIN_TESTS =\ test/merkleblock_tests.cpp \ test/miner_tests.cpp \ test/multisig_tests.cpp \ + test/net_peer_eviction_tests.cpp \ test/net_tests.cpp \ test/netbase_tests.cpp \ test/pmt_tests.cpp \ diff --git a/src/net.cpp b/src/net.cpp index f9ae67b75c..e629d6a0a5 100644 --- a/src/net.cpp +++ b/src/net.cpp @@ -840,6 +840,12 @@ static bool CompareLocalHostTimeConnected(const NodeEvictionCandidate &a, const return a.nTimeConnected > b.nTimeConnected; } +static bool CompareOnionTimeConnected(const NodeEvictionCandidate& a, const NodeEvictionCandidate& b) +{ + if (a.m_is_onion != b.m_is_onion) return b.m_is_onion; + return a.nTimeConnected > b.nTimeConnected; +} + static bool CompareNetGroupKeyed(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) { return a.nKeyedNetGroup < b.nKeyedNetGroup; } @@ -870,13 +876,51 @@ static bool CompareNodeBlockRelayOnlyTime(const NodeEvictionCandidate &a, const return a.nTimeConnected > b.nTimeConnected; } -//! Sort an array by the specified comparator, then erase the last K elements. -template<typename T, typename Comparator> -static void EraseLastKElements(std::vector<T> &elements, Comparator comparator, size_t k) +//! Sort an array by the specified comparator, then erase the last K elements where predicate is true. +template <typename T, typename Comparator> +static void EraseLastKElements( + std::vector<T>& elements, Comparator comparator, size_t k, + std::function<bool(const NodeEvictionCandidate&)> predicate = [](const NodeEvictionCandidate& n) { return true; }) { std::sort(elements.begin(), elements.end(), comparator); size_t eraseSize = std::min(k, elements.size()); - elements.erase(elements.end() - eraseSize, elements.end()); + elements.erase(std::remove_if(elements.end() - eraseSize, elements.end(), predicate), elements.end()); +} + +void ProtectEvictionCandidatesByRatio(std::vector<NodeEvictionCandidate>& vEvictionCandidates) +{ + // Protect the half of the remaining nodes which have been connected the longest. + // This replicates the non-eviction implicit behavior, and precludes attacks that start later. + // To favorise the diversity of our peer connections, reserve up to (half + 2) of + // these protected spots for onion and localhost peers, if any, even if they're not + // longest uptime overall. This helps protect tor peers, which tend to be otherwise + // disadvantaged under our eviction criteria. + const size_t initial_size = vEvictionCandidates.size(); + size_t total_protect_size = initial_size / 2; + const size_t onion_protect_size = total_protect_size / 2; + + if (onion_protect_size) { + // Pick out up to 1/4 peers connected via our onion service, sorted by longest uptime. + EraseLastKElements(vEvictionCandidates, CompareOnionTimeConnected, onion_protect_size, + [](const NodeEvictionCandidate& n) { return n.m_is_onion; }); + } + + const size_t localhost_min_protect_size{2}; + if (onion_protect_size >= localhost_min_protect_size) { + // Allocate any remaining slots of the 1/4, or minimum 2 additional slots, + // to localhost peers, sorted by longest uptime, as manually configured + // hidden services not using `-bind=addr[:port]=onion` will not be detected + // as inbound onion connections. + const size_t remaining_tor_slots{onion_protect_size - (initial_size - vEvictionCandidates.size())}; + const size_t localhost_protect_size{std::max(remaining_tor_slots, localhost_min_protect_size)}; + EraseLastKElements(vEvictionCandidates, CompareLocalHostTimeConnected, localhost_protect_size, + [](const NodeEvictionCandidate& n) { return n.m_is_local; }); + } + + // Calculate how many we removed, and update our total number of peers that + // we want to protect based on uptime accordingly. + total_protect_size -= initial_size - vEvictionCandidates.size(); + EraseLastKElements(vEvictionCandidates, ReverseCompareNodeTimeConnected, total_protect_size); } [[nodiscard]] std::optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&& vEvictionCandidates) @@ -893,30 +937,17 @@ static void EraseLastKElements(std::vector<T> &elements, Comparator comparator, // An attacker cannot manipulate this metric without performing useful work. EraseLastKElements(vEvictionCandidates, CompareNodeTXTime, 4); // Protect up to 8 non-tx-relay peers that have sent us novel blocks. - std::sort(vEvictionCandidates.begin(), vEvictionCandidates.end(), CompareNodeBlockRelayOnlyTime); - size_t erase_size = std::min(size_t(8), vEvictionCandidates.size()); - vEvictionCandidates.erase(std::remove_if(vEvictionCandidates.end() - erase_size, vEvictionCandidates.end(), [](NodeEvictionCandidate const &n) { return !n.fRelayTxes && n.fRelevantServices; }), vEvictionCandidates.end()); + const size_t erase_size = std::min(size_t(8), vEvictionCandidates.size()); + EraseLastKElements(vEvictionCandidates, CompareNodeBlockRelayOnlyTime, erase_size, + [](const NodeEvictionCandidate& n) { return !n.fRelayTxes && n.fRelevantServices; }); // Protect 4 nodes that most recently sent us novel blocks. // An attacker cannot manipulate this metric without performing useful work. EraseLastKElements(vEvictionCandidates, CompareNodeBlockTime, 4); - // Protect the half of the remaining nodes which have been connected the longest. - // This replicates the non-eviction implicit behavior, and precludes attacks that start later. - // Reserve half of these protected spots for localhost peers, even if - // they're not longest-uptime overall. This helps protect tor peers, which - // tend to be otherwise disadvantaged under our eviction criteria. - size_t initial_size = vEvictionCandidates.size(); - size_t total_protect_size = initial_size / 2; - - // Pick out up to 1/4 peers that are localhost, sorted by longest uptime. - std::sort(vEvictionCandidates.begin(), vEvictionCandidates.end(), CompareLocalHostTimeConnected); - size_t local_erase_size = total_protect_size / 2; - vEvictionCandidates.erase(std::remove_if(vEvictionCandidates.end() - local_erase_size, vEvictionCandidates.end(), [](NodeEvictionCandidate const &n) { return n.m_is_local; }), vEvictionCandidates.end()); - // Calculate how many we removed, and update our total number of peers that - // we want to protect based on uptime accordingly. - total_protect_size -= initial_size - vEvictionCandidates.size(); - EraseLastKElements(vEvictionCandidates, ReverseCompareNodeTimeConnected, total_protect_size); + // Protect some of the remaining eviction candidates by ratios of desirable + // or disadvantaged characteristics. + ProtectEvictionCandidatesByRatio(vEvictionCandidates); if (vEvictionCandidates.empty()) return std::nullopt; @@ -937,7 +968,7 @@ static void EraseLastKElements(std::vector<T> &elements, Comparator comparator, for (const NodeEvictionCandidate &node : vEvictionCandidates) { std::vector<NodeEvictionCandidate> &group = mapNetGroupNodes[node.nKeyedNetGroup]; group.push_back(node); - int64_t grouptime = group[0].nTimeConnected; + const int64_t grouptime = group[0].nTimeConnected; if (group.size() > nMostConnections || (group.size() == nMostConnections && grouptime > nMostConnectionsTime)) { nMostConnections = group.size(); @@ -985,7 +1016,8 @@ bool CConnman::AttemptToEvictConnection() node->nLastBlockTime, node->nLastTXTime, HasAllDesirableServiceFlags(node->nServices), peer_relay_txes, peer_filter_not_null, node->nKeyedNetGroup, - node->m_prefer_evict, node->addr.IsLocal()}; + node->m_prefer_evict, node->addr.IsLocal(), + node->m_inbound_onion}; vEvictionCandidates.push_back(candidate); } } @@ -425,6 +425,7 @@ public: std::atomic<int64_t> nLastSend{0}; std::atomic<int64_t> nLastRecv{0}; + //! Unix epoch time at peer connection, in seconds. const int64_t nTimeConnected; std::atomic<int64_t> nTimeOffset{0}; // Address of this peer @@ -1278,8 +1279,39 @@ struct NodeEvictionCandidate uint64_t nKeyedNetGroup; bool prefer_evict; bool m_is_local; + bool m_is_onion; }; +/** + * Select an inbound peer to evict after filtering out (protecting) peers having + * distinct, difficult-to-forge characteristics. The protection logic picks out + * fixed numbers of desirable peers per various criteria, followed by (mostly) + * ratios of desirable or disadvantaged peers. If any eviction candidates + * remain, the selection logic chooses a peer to evict. + */ [[nodiscard]] std::optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&& vEvictionCandidates); +/** Protect desirable or disadvantaged inbound peers from eviction by ratio. + * + * This function protects half of the peers which have been connected the + * longest, to replicate the non-eviction implicit behavior and preclude attacks + * that start later. + * + * Half of these protected spots (1/4 of the total) are reserved for onion peers + * connected via our tor control service, if any, sorted by longest uptime, even + * if they're not longest uptime overall. Any remaining slots of the 1/4 are + * then allocated to protect localhost peers, if any (or up to 2 localhost peers + * if no slots remain and 2 or more onion peers were protected), sorted by + * longest uptime, as manually configured hidden services not using + * `-bind=addr[:port]=onion` will not be detected as inbound onion connections. + * + * This helps protect onion peers, which tend to be otherwise disadvantaged + * under our eviction criteria for their higher min ping times relative to IPv4 + * and IPv6 peers, and favorise the diversity of peer connections. + * + * This function was extracted from SelectNodeToEvict() to be able to test the + * ratio-based protection logic deterministically. + */ +void ProtectEvictionCandidatesByRatio(std::vector<NodeEvictionCandidate>& vEvictionCandidates); + #endif // BITCOIN_NET_H diff --git a/src/test/fuzz/node_eviction.cpp b/src/test/fuzz/node_eviction.cpp index 603d520cf5..70ffc6bf37 100644 --- a/src/test/fuzz/node_eviction.cpp +++ b/src/test/fuzz/node_eviction.cpp @@ -31,6 +31,7 @@ FUZZ_TARGET(node_eviction) /* nKeyedNetGroup */ fuzzed_data_provider.ConsumeIntegral<uint64_t>(), /* prefer_evict */ fuzzed_data_provider.ConsumeBool(), /* m_is_local */ fuzzed_data_provider.ConsumeBool(), + /* m_is_onion */ fuzzed_data_provider.ConsumeBool(), }); } // Make a copy since eviction_candidates may be in some valid but otherwise diff --git a/src/test/net_peer_eviction_tests.cpp b/src/test/net_peer_eviction_tests.cpp new file mode 100644 index 0000000000..31d391bf7d --- /dev/null +++ b/src/test/net_peer_eviction_tests.cpp @@ -0,0 +1,348 @@ +// Copyright (c) 2021 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 <net.h> +#include <test/util/setup_common.h> + +#include <boost/test/unit_test.hpp> + +#include <algorithm> +#include <functional> +#include <optional> +#include <unordered_set> +#include <vector> + +BOOST_FIXTURE_TEST_SUITE(net_peer_eviction_tests, BasicTestingSetup) + +namespace { +constexpr int NODE_EVICTION_TEST_ROUNDS{10}; +constexpr int NODE_EVICTION_TEST_UP_TO_N_NODES{200}; +} // namespace + +std::vector<NodeEvictionCandidate> GetRandomNodeEvictionCandidates(const int n_candidates, FastRandomContext& random_context) +{ + std::vector<NodeEvictionCandidate> candidates; + for (int id = 0; id < n_candidates; ++id) { + candidates.push_back({ + /* id */ id, + /* nTimeConnected */ static_cast<int64_t>(random_context.randrange(100)), + /* m_min_ping_time */ std::chrono::microseconds{random_context.randrange(100)}, + /* nLastBlockTime */ static_cast<int64_t>(random_context.randrange(100)), + /* nLastTXTime */ static_cast<int64_t>(random_context.randrange(100)), + /* fRelevantServices */ random_context.randbool(), + /* fRelayTxes */ random_context.randbool(), + /* fBloomFilter */ random_context.randbool(), + /* nKeyedNetGroup */ random_context.randrange(100), + /* prefer_evict */ random_context.randbool(), + /* m_is_local */ random_context.randbool(), + /* m_is_onion */ random_context.randbool(), + }); + } + return candidates; +} + +// Create `num_peers` random nodes, apply setup function `candidate_setup_fn`, +// call ProtectEvictionCandidatesByRatio() to apply protection logic, and then +// return true if all of `protected_peer_ids` and none of `unprotected_peer_ids` +// are protected from eviction, i.e. removed from the eviction candidates. +bool IsProtected(int num_peers, + std::function<void(NodeEvictionCandidate&)> candidate_setup_fn, + const std::unordered_set<NodeId>& protected_peer_ids, + const std::unordered_set<NodeId>& unprotected_peer_ids, + FastRandomContext& random_context) +{ + std::vector<NodeEvictionCandidate> candidates{GetRandomNodeEvictionCandidates(num_peers, random_context)}; + for (NodeEvictionCandidate& candidate : candidates) { + candidate_setup_fn(candidate); + } + Shuffle(candidates.begin(), candidates.end(), random_context); + + const size_t size{candidates.size()}; + const size_t expected{size - size / 2}; // Expect half the candidates will be protected. + ProtectEvictionCandidatesByRatio(candidates); + BOOST_CHECK_EQUAL(candidates.size(), expected); + + size_t unprotected_count{0}; + for (const NodeEvictionCandidate& candidate : candidates) { + if (protected_peer_ids.count(candidate.id)) { + // this peer should have been removed from the eviction candidates + BOOST_TEST_MESSAGE(strprintf("expected candidate to be protected: %d", candidate.id)); + return false; + } + if (unprotected_peer_ids.count(candidate.id)) { + // this peer remains in the eviction candidates, as expected + ++unprotected_count; + } + } + + const bool is_protected{unprotected_count == unprotected_peer_ids.size()}; + if (!is_protected) { + BOOST_TEST_MESSAGE(strprintf("unprotected: expected %d, actual %d", + unprotected_peer_ids.size(), unprotected_count)); + } + return is_protected; +} + +BOOST_AUTO_TEST_CASE(peer_protection_test) +{ + FastRandomContext random_context{true}; + int num_peers{12}; + + // Expect half of the peers with greatest uptime (the lowest nTimeConnected) + // to be protected from eviction. + BOOST_CHECK(IsProtected( + num_peers, [](NodeEvictionCandidate& c) { + c.nTimeConnected = c.id; + c.m_is_onion = c.m_is_local = false; + }, + /* protected_peer_ids */ {0, 1, 2, 3, 4, 5}, + /* unprotected_peer_ids */ {6, 7, 8, 9, 10, 11}, + random_context)); + + // Verify in the opposite direction. + BOOST_CHECK(IsProtected( + num_peers, [num_peers](NodeEvictionCandidate& c) { + c.nTimeConnected = num_peers - c.id; + c.m_is_onion = c.m_is_local = false; + }, + /* protected_peer_ids */ {6, 7, 8, 9, 10, 11}, + /* unprotected_peer_ids */ {0, 1, 2, 3, 4, 5}, + random_context)); + + // Test protection of onion and localhost peers... + + // Expect 1/4 onion peers to be protected from eviction, + // independently of other characteristics. + BOOST_CHECK(IsProtected( + num_peers, [](NodeEvictionCandidate& c) { + c.m_is_onion = (c.id == 3 || c.id == 8 || c.id == 9); + }, + /* protected_peer_ids */ {3, 8, 9}, + /* unprotected_peer_ids */ {}, + random_context)); + + // Expect 1/4 onion peers and 1/4 of the others to be protected + // from eviction, sorted by longest uptime (lowest nTimeConnected). + BOOST_CHECK(IsProtected( + num_peers, [](NodeEvictionCandidate& c) { + c.nTimeConnected = c.id; + c.m_is_local = false; + c.m_is_onion = (c.id == 3 || c.id > 7); + }, + /* protected_peer_ids */ {0, 1, 2, 3, 8, 9}, + /* unprotected_peer_ids */ {4, 5, 6, 7, 10, 11}, + random_context)); + + // Expect 1/4 localhost peers to be protected from eviction, + // if no onion peers. + BOOST_CHECK(IsProtected( + num_peers, [](NodeEvictionCandidate& c) { + c.m_is_onion = false; + c.m_is_local = (c.id == 1 || c.id == 9 || c.id == 11); + }, + /* protected_peer_ids */ {1, 9, 11}, + /* unprotected_peer_ids */ {}, + random_context)); + + // Expect 1/4 localhost peers and 1/4 of the other peers to be protected, + // sorted by longest uptime (lowest nTimeConnected), if no onion peers. + BOOST_CHECK(IsProtected( + num_peers, [](NodeEvictionCandidate& c) { + c.nTimeConnected = c.id; + c.m_is_onion = false; + c.m_is_local = (c.id > 6); + }, + /* protected_peer_ids */ {0, 1, 2, 7, 8, 9}, + /* unprotected_peer_ids */ {3, 4, 5, 6, 10, 11}, + random_context)); + + // Combined test: expect 1/4 onion and 2 localhost peers to be protected + // from eviction, sorted by longest uptime. + BOOST_CHECK(IsProtected( + num_peers, [](NodeEvictionCandidate& c) { + c.nTimeConnected = c.id; + c.m_is_onion = (c.id == 0 || c.id == 5 || c.id == 10); + c.m_is_local = (c.id == 1 || c.id == 9 || c.id == 11); + }, + /* protected_peer_ids */ {0, 1, 2, 5, 9, 10}, + /* unprotected_peer_ids */ {3, 4, 6, 7, 8, 11}, + random_context)); + + // Combined test: expect having only 1 onion to allow allocating the + // remaining 2 of the 1/4 to localhost peers, sorted by longest uptime. + BOOST_CHECK(IsProtected( + num_peers + 4, [](NodeEvictionCandidate& c) { + c.nTimeConnected = c.id; + c.m_is_onion = (c.id == 15); + c.m_is_local = (c.id > 6 && c.id < 11); + }, + /* protected_peer_ids */ {0, 1, 2, 3, 7, 8, 9, 15}, + /* unprotected_peer_ids */ {4, 5, 6, 10, 11, 12, 13, 14}, + random_context)); + + // Combined test: expect 2 onions (< 1/4) to allow allocating the minimum 2 + // localhost peers, sorted by longest uptime. + BOOST_CHECK(IsProtected( + num_peers, [](NodeEvictionCandidate& c) { + c.nTimeConnected = c.id; + c.m_is_onion = (c.id == 7 || c.id == 9); + c.m_is_local = (c.id == 6 || c.id == 11); + }, + /* protected_peer_ids */ {0, 1, 6, 7, 9, 11}, + /* unprotected_peer_ids */ {2, 3, 4, 5, 8, 10}, + random_context)); + + // Combined test: when > 1/4, expect max 1/4 onion and 2 localhost peers + // to be protected from eviction, sorted by longest uptime. + BOOST_CHECK(IsProtected( + num_peers, [](NodeEvictionCandidate& c) { + c.nTimeConnected = c.id; + c.m_is_onion = (c.id > 3 && c.id < 8); + c.m_is_local = (c.id > 7); + }, + /* protected_peer_ids */ {0, 4, 5, 6, 8, 9}, + /* unprotected_peer_ids */ {1, 2, 3, 7, 10, 11}, + random_context)); + + // Combined test: idem > 1/4 with only 8 peers: expect 2 onion and 2 + // localhost peers (1/4 + 2) to be protected, sorted by longest uptime. + BOOST_CHECK(IsProtected( + 8, [](NodeEvictionCandidate& c) { + c.nTimeConnected = c.id; + c.m_is_onion = (c.id > 1 && c.id < 5); + c.m_is_local = (c.id > 4); + }, + /* protected_peer_ids */ {2, 3, 5, 6}, + /* unprotected_peer_ids */ {0, 1, 4, 7}, + random_context)); + + // Combined test: idem > 1/4 with only 6 peers: expect 1 onion peer and no + // localhost peers (1/4 + 0) to be protected, sorted by longest uptime. + BOOST_CHECK(IsProtected( + 6, [](NodeEvictionCandidate& c) { + c.nTimeConnected = c.id; + c.m_is_onion = (c.id == 4 || c.id == 5); + c.m_is_local = (c.id == 3); + }, + /* protected_peer_ids */ {0, 1, 4}, + /* unprotected_peer_ids */ {2, 3, 5}, + random_context)); +} + +// Returns true if any of the node ids in node_ids are selected for eviction. +bool IsEvicted(std::vector<NodeEvictionCandidate> candidates, const std::unordered_set<NodeId>& node_ids, FastRandomContext& random_context) +{ + Shuffle(candidates.begin(), candidates.end(), random_context); + const std::optional<NodeId> evicted_node_id = SelectNodeToEvict(std::move(candidates)); + if (!evicted_node_id) { + return false; + } + return node_ids.count(*evicted_node_id); +} + +// Create number_of_nodes random nodes, apply setup function candidate_setup_fn, +// apply eviction logic and then return true if any of the node ids in node_ids +// are selected for eviction. +bool IsEvicted(const int number_of_nodes, std::function<void(NodeEvictionCandidate&)> candidate_setup_fn, const std::unordered_set<NodeId>& node_ids, FastRandomContext& random_context) +{ + std::vector<NodeEvictionCandidate> candidates = GetRandomNodeEvictionCandidates(number_of_nodes, random_context); + for (NodeEvictionCandidate& candidate : candidates) { + candidate_setup_fn(candidate); + } + return IsEvicted(candidates, node_ids, random_context); +} + +BOOST_AUTO_TEST_CASE(peer_eviction_test) +{ + FastRandomContext random_context{true}; + + for (int i = 0; i < NODE_EVICTION_TEST_ROUNDS; ++i) { + for (int number_of_nodes = 0; number_of_nodes < NODE_EVICTION_TEST_UP_TO_N_NODES; ++number_of_nodes) { + // Four nodes with the highest keyed netgroup values should be + // protected from eviction. + BOOST_CHECK(!IsEvicted( + number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { + candidate.nKeyedNetGroup = number_of_nodes - candidate.id; + }, + {0, 1, 2, 3}, random_context)); + + // Eight nodes with the lowest minimum ping time should be protected + // from eviction. + BOOST_CHECK(!IsEvicted( + number_of_nodes, [](NodeEvictionCandidate& candidate) { + candidate.m_min_ping_time = std::chrono::microseconds{candidate.id}; + }, + {0, 1, 2, 3, 4, 5, 6, 7}, random_context)); + + // Four nodes that most recently sent us novel transactions accepted + // into our mempool should be protected from eviction. + BOOST_CHECK(!IsEvicted( + number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { + candidate.nLastTXTime = number_of_nodes - candidate.id; + }, + {0, 1, 2, 3}, random_context)); + + // Up to eight non-tx-relay peers that most recently sent us novel + // blocks should be protected from eviction. + BOOST_CHECK(!IsEvicted( + number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { + candidate.nLastBlockTime = number_of_nodes - candidate.id; + if (candidate.id <= 7) { + candidate.fRelayTxes = false; + candidate.fRelevantServices = true; + } + }, + {0, 1, 2, 3, 4, 5, 6, 7}, random_context)); + + // Four peers that most recently sent us novel blocks should be + // protected from eviction. + BOOST_CHECK(!IsEvicted( + number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { + candidate.nLastBlockTime = number_of_nodes - candidate.id; + }, + {0, 1, 2, 3}, random_context)); + + // Combination of the previous two tests. + BOOST_CHECK(!IsEvicted( + number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { + candidate.nLastBlockTime = number_of_nodes - candidate.id; + if (candidate.id <= 7) { + candidate.fRelayTxes = false; + candidate.fRelevantServices = true; + } + }, + {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, random_context)); + + // Combination of all tests above. + BOOST_CHECK(!IsEvicted( + number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { + candidate.nKeyedNetGroup = number_of_nodes - candidate.id; // 4 protected + candidate.m_min_ping_time = std::chrono::microseconds{candidate.id}; // 8 protected + candidate.nLastTXTime = number_of_nodes - candidate.id; // 4 protected + candidate.nLastBlockTime = number_of_nodes - candidate.id; // 4 protected + }, + {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}, random_context)); + + // An eviction is expected given >= 29 random eviction candidates. The eviction logic protects at most + // four peers by net group, eight by lowest ping time, four by last time of novel tx, up to eight non-tx-relay + // peers by last novel block time, and four more peers by last novel block time. + if (number_of_nodes >= 29) { + BOOST_CHECK(SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context))); + } + + // No eviction is expected given <= 20 random eviction candidates. The eviction logic protects at least + // four peers by net group, eight by lowest ping time, four by last time of novel tx and four peers by last + // novel block time. + if (number_of_nodes <= 20) { + BOOST_CHECK(!SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context))); + } + + // Cases left to test: + // * "If any remaining peers are preferred for eviction consider only them. [...]" + // * "Identify the network group with the most connections and youngest member. [...]" + } + } +} + +BOOST_AUTO_TEST_SUITE_END() diff --git a/src/test/net_tests.cpp b/src/test/net_tests.cpp index 858b90b8b2..8eab26f3d5 100644 --- a/src/test/net_tests.cpp +++ b/src/test/net_tests.cpp @@ -857,147 +857,4 @@ BOOST_AUTO_TEST_CASE(LocalAddress_BasicLifecycle) BOOST_CHECK_EQUAL(IsLocal(addr), false); } -std::vector<NodeEvictionCandidate> GetRandomNodeEvictionCandidates(const int n_candidates, FastRandomContext& random_context) -{ - std::vector<NodeEvictionCandidate> candidates; - for (int id = 0; id < n_candidates; ++id) { - candidates.push_back({ - /* id */ id, - /* nTimeConnected */ static_cast<int64_t>(random_context.randrange(100)), - /* m_min_ping_time */ std::chrono::microseconds{random_context.randrange(100)}, - /* nLastBlockTime */ static_cast<int64_t>(random_context.randrange(100)), - /* nLastTXTime */ static_cast<int64_t>(random_context.randrange(100)), - /* fRelevantServices */ random_context.randbool(), - /* fRelayTxes */ random_context.randbool(), - /* fBloomFilter */ random_context.randbool(), - /* nKeyedNetGroup */ random_context.randrange(100), - /* prefer_evict */ random_context.randbool(), - /* m_is_local */ random_context.randbool(), - }); - } - return candidates; -} - -// Returns true if any of the node ids in node_ids are selected for eviction. -bool IsEvicted(std::vector<NodeEvictionCandidate> candidates, const std::vector<NodeId>& node_ids, FastRandomContext& random_context) -{ - Shuffle(candidates.begin(), candidates.end(), random_context); - const std::optional<NodeId> evicted_node_id = SelectNodeToEvict(std::move(candidates)); - if (!evicted_node_id) { - return false; - } - return std::find(node_ids.begin(), node_ids.end(), *evicted_node_id) != node_ids.end(); -} - -// Create number_of_nodes random nodes, apply setup function candidate_setup_fn, -// apply eviction logic and then return true if any of the node ids in node_ids -// are selected for eviction. -bool IsEvicted(const int number_of_nodes, std::function<void(NodeEvictionCandidate&)> candidate_setup_fn, const std::vector<NodeId>& node_ids, FastRandomContext& random_context) -{ - std::vector<NodeEvictionCandidate> candidates = GetRandomNodeEvictionCandidates(number_of_nodes, random_context); - for (NodeEvictionCandidate& candidate : candidates) { - candidate_setup_fn(candidate); - } - return IsEvicted(candidates, node_ids, random_context); -} - -namespace { -constexpr int NODE_EVICTION_TEST_ROUNDS{10}; -constexpr int NODE_EVICTION_TEST_UP_TO_N_NODES{200}; -} // namespace - -BOOST_AUTO_TEST_CASE(node_eviction_test) -{ - FastRandomContext random_context{true}; - - for (int i = 0; i < NODE_EVICTION_TEST_ROUNDS; ++i) { - for (int number_of_nodes = 0; number_of_nodes < NODE_EVICTION_TEST_UP_TO_N_NODES; ++number_of_nodes) { - // Four nodes with the highest keyed netgroup values should be - // protected from eviction. - BOOST_CHECK(!IsEvicted( - number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { - candidate.nKeyedNetGroup = number_of_nodes - candidate.id; - }, - {0, 1, 2, 3}, random_context)); - - // Eight nodes with the lowest minimum ping time should be protected - // from eviction. - BOOST_CHECK(!IsEvicted( - number_of_nodes, [](NodeEvictionCandidate& candidate) { - candidate.m_min_ping_time = std::chrono::microseconds{candidate.id}; - }, - {0, 1, 2, 3, 4, 5, 6, 7}, random_context)); - - // Four nodes that most recently sent us novel transactions accepted - // into our mempool should be protected from eviction. - BOOST_CHECK(!IsEvicted( - number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { - candidate.nLastTXTime = number_of_nodes - candidate.id; - }, - {0, 1, 2, 3}, random_context)); - - // Up to eight non-tx-relay peers that most recently sent us novel - // blocks should be protected from eviction. - BOOST_CHECK(!IsEvicted( - number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { - candidate.nLastBlockTime = number_of_nodes - candidate.id; - if (candidate.id <= 7) { - candidate.fRelayTxes = false; - candidate.fRelevantServices = true; - } - }, - {0, 1, 2, 3, 4, 5, 6, 7}, random_context)); - - // Four peers that most recently sent us novel blocks should be - // protected from eviction. - BOOST_CHECK(!IsEvicted( - number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { - candidate.nLastBlockTime = number_of_nodes - candidate.id; - }, - {0, 1, 2, 3}, random_context)); - - // Combination of the previous two tests. - BOOST_CHECK(!IsEvicted( - number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { - candidate.nLastBlockTime = number_of_nodes - candidate.id; - if (candidate.id <= 7) { - candidate.fRelayTxes = false; - candidate.fRelevantServices = true; - } - }, - {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, random_context)); - - // Combination of all tests above. - BOOST_CHECK(!IsEvicted( - number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) { - candidate.nKeyedNetGroup = number_of_nodes - candidate.id; // 4 protected - candidate.m_min_ping_time = std::chrono::microseconds{candidate.id}; // 8 protected - candidate.nLastTXTime = number_of_nodes - candidate.id; // 4 protected - candidate.nLastBlockTime = number_of_nodes - candidate.id; // 4 protected - }, - {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}, random_context)); - - // An eviction is expected given >= 29 random eviction candidates. The eviction logic protects at most - // four peers by net group, eight by lowest ping time, four by last time of novel tx, up to eight non-tx-relay - // peers by last novel block time, and four more peers by last novel block time. - if (number_of_nodes >= 29) { - BOOST_CHECK(SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context))); - } - - // No eviction is expected given <= 20 random eviction candidates. The eviction logic protects at least - // four peers by net group, eight by lowest ping time, four by last time of novel tx and four peers by last - // novel block time. - if (number_of_nodes <= 20) { - BOOST_CHECK(!SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context))); - } - - // Cases left to test: - // * "Protect the half of the remaining nodes which have been connected the longest. [...]" - // * "Pick out up to 1/4 peers that are localhost, sorted by longest uptime. [...]" - // * "If any remaining peers are preferred for eviction consider only them. [...]" - // * "Identify the network group with the most connections and youngest member. [...]" - } - } -} - BOOST_AUTO_TEST_SUITE_END() |