diff --git a/src/net.h b/src/net.h --- a/src/net.h +++ b/src/net.h @@ -33,6 +33,7 @@ #include #include #include +#include #ifndef WIN32 #include @@ -1221,4 +1222,21 @@ std::string getSubVersionEB(uint64_t MaxBlockSize); std::string userAgent(const Config &config); +struct NodeEvictionCandidate { + NodeId id; + int64_t nTimeConnected; + int64_t nMinPingUsecTime; + int64_t nLastBlockTime; + int64_t nLastTXTime; + bool fRelevantServices; + bool fRelayTxes; + bool fBloomFilter; + uint64_t nKeyedNetGroup; + bool prefer_evict; + bool m_is_local; +}; + +[[nodiscard]] std::optional +SelectNodeToEvict(std::vector &&vEvictionCandidates); + #endif // BITCOIN_NET_H diff --git a/src/net.cpp b/src/net.cpp --- a/src/net.cpp +++ b/src/net.cpp @@ -44,9 +44,9 @@ "miniUPnPc API version >= 10 assumed"); #endif -#include - #include +#include +#include // How often to dump addresses to peers.dat static constexpr std::chrono::minutes DUMP_PEERS_INTERVAL{15}; @@ -836,20 +836,6 @@ return nSentSize; } -struct NodeEvictionCandidate { - NodeId id; - int64_t nTimeConnected; - int64_t nMinPingUsecTime; - int64_t nLastBlockTime; - int64_t nLastTXTime; - bool fRelevantServices; - bool fRelayTxes; - bool fBloomFilter; - uint64_t nKeyedNetGroup; - bool prefer_evict; - bool m_is_local; -}; - static bool ReverseCompareNodeMinPingTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) { return a.nMinPingUsecTime > b.nMinPingUsecTime; @@ -936,53 +922,8 @@ elements.erase(elements.end() - eraseSize, elements.end()); } -/** - * Try to find a connection to evict when the node is full. - * Extreme care must be taken to avoid opening the node to attacker triggered - * network partitioning. - * The strategy used here is to protect a small number of peers for each of - * several distinct characteristics which are difficult to forge. In order to - * partition a node the attacker must be simultaneously better at all of them - * than honest peers. - */ -bool CConnman::AttemptToEvictConnection() { - std::vector vEvictionCandidates; - { - LOCK(cs_vNodes); - - for (const CNode *node : vNodes) { - if (node->HasPermission(PF_NOBAN)) { - continue; - } - if (!node->IsInboundConn()) { - continue; - } - if (node->fDisconnect) { - continue; - } - bool peer_relay_txes = false; - bool peer_filter_not_null = false; - if (node->m_tx_relay != nullptr) { - LOCK(node->m_tx_relay->cs_filter); - peer_relay_txes = node->m_tx_relay->fRelayTxes; - peer_filter_not_null = node->m_tx_relay->pfilter != nullptr; - } - NodeEvictionCandidate candidate = { - node->GetId(), - node->nTimeConnected, - node->nMinPingUsecTime, - node->nLastBlockTime, - node->nLastTXTime, - HasAllDesirableServiceFlags(node->nServices), - peer_relay_txes, - peer_filter_not_null, - node->nKeyedNetGroup, - node->m_prefer_evict, - node->addr.IsLocal()}; - vEvictionCandidates.push_back(candidate); - } - } - +[[nodiscard]] std::optional +SelectNodeToEvict(std::vector &&vEvictionCandidates) { // Protect connections with certain characteristics // Deterministically select 4 peers to protect by netgroup. @@ -1038,7 +979,7 @@ total_protect_size); if (vEvictionCandidates.empty()) { - return false; + return std::nullopt; } // If any remaining peers are preferred for eviction consider only them. @@ -1080,10 +1021,61 @@ vEvictionCandidates = std::move(mapNetGroupNodes[naMostConnections]); // Disconnect from the network group with the most connections - NodeId evicted = vEvictionCandidates.front().id; + return vEvictionCandidates.front().id; +} + +/** Try to find a connection to evict when the node is full. + * Extreme care must be taken to avoid opening the node to attacker + * triggered network partitioning. + * The strategy used here is to protect a small number of peers + * for each of several distinct characteristics which are difficult + * to forge. In order to partition a node the attacker must be + * simultaneously better at all of them than honest peers. + */ +bool CConnman::AttemptToEvictConnection() { + std::vector vEvictionCandidates; + { + LOCK(cs_vNodes); + for (const CNode *node : vNodes) { + if (node->HasPermission(PF_NOBAN)) { + continue; + } + if (!node->IsInboundConn()) { + continue; + } + if (node->fDisconnect) { + continue; + } + bool peer_relay_txes = false; + bool peer_filter_not_null = false; + if (node->m_tx_relay != nullptr) { + LOCK(node->m_tx_relay->cs_filter); + peer_relay_txes = node->m_tx_relay->fRelayTxes; + peer_filter_not_null = node->m_tx_relay->pfilter != nullptr; + } + NodeEvictionCandidate candidate = { + node->GetId(), + node->nTimeConnected, + node->nMinPingUsecTime, + node->nLastBlockTime, + node->nLastTXTime, + HasAllDesirableServiceFlags(node->nServices), + peer_relay_txes, + peer_filter_not_null, + node->nKeyedNetGroup, + node->m_prefer_evict, + node->addr.IsLocal()}; + vEvictionCandidates.push_back(candidate); + } + } + const std::optional node_id_to_evict = + SelectNodeToEvict(std::move(vEvictionCandidates)); + if (!node_id_to_evict) { + return false; + } LOCK(cs_vNodes); for (CNode *pnode : vNodes) { - if (pnode->GetId() == evicted) { + if (pnode->GetId() == *node_id_to_evict) { pnode->fDisconnect = true; return true; } diff --git a/src/test/net_tests.cpp b/src/test/net_tests.cpp --- a/src/test/net_tests.cpp +++ b/src/test/net_tests.cpp @@ -21,6 +21,7 @@ #include +#include #include #include #include @@ -757,4 +758,180 @@ g_mock_deterministic_tests = false; } +std::vector +GetRandomNodeEvictionCandidates(const int n_candidates, + FastRandomContext &random_context) { + std::vector candidates; + for (int id = 0; id < n_candidates; ++id) { + candidates.push_back({ + /* id */ id, + /* nTimeConnected */ + static_cast(random_context.randrange(100)), + /* nMinPingUsecTime */ + static_cast(random_context.randrange(100)), + /* nLastBlockTime */ + static_cast(random_context.randrange(100)), + /* nLastTXTime */ + static_cast(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 candidates, + const std::vector &node_ids, + FastRandomContext &random_context) { + Shuffle(candidates.begin(), candidates.end(), random_context); + const std::optional 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 candidate_setup_fn, + const std::vector &node_ids, + FastRandomContext &random_context) { + std::vector 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.nMinPingUsecTime = 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.nMinPingUsecTime = 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()