aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorMarcoFalke <falke.marco@gmail.com>2020-12-16 13:30:48 +0100
committerMarcoFalke <falke.marco@gmail.com>2020-12-16 13:30:55 +0100
commitb440c33179e777bfebb8c12840e06ea691a4868f (patch)
treeb8f283fac0425b08c7ebecb1ffcb8aeacbf2fcd7 /src
parentdff0f6f753eafd932d7d65fbfa33585f620e8e54 (diff)
parentfee88237e03c21bf81f21098e6b89ecfa5327cee (diff)
Merge #20477: net: Add unit testing of node eviction logic
fee88237e03c21bf81f21098e6b89ecfa5327cee Assert eviction at >= 29 candidates. Assert non-eviction at <= 20 candidates. (practicalswift) 685c428de0fb63ca6ec1419bb112f07d27bcdf14 test: Add unit testing of node eviction logic (practicalswift) ed73f8cee0d7b7facbd2e8dde24a237f20c48c0c net: Move eviction node selection logic to SelectNodeToEvict(...) (practicalswift) Pull request description: Add unit testing of node eviction logic. Closes #19966. ACKs for top commit: jonatack: ACK fee88237e03c21bf81f21098e6b89ecfa5327cee MarcoFalke: ACK fee88237e03c21bf81f21098e6b89ecfa5327cee 🐼 Tree-SHA512: 0827c35609122ca42bfabb17feaaee35c191ab4dc2e428282af425a6c176eaeaff2789b74a4f7eb4ca6b8cb10603068e90ca800e6ef3bc3904d50e76616f7a2b
Diffstat (limited to 'src')
-rw-r--r--src/net.cpp101
-rw-r--r--src/net.h18
-rw-r--r--src/test/net_tests.cpp145
3 files changed, 210 insertions, 54 deletions
diff --git a/src/net.cpp b/src/net.cpp
index 66bf9b0315..db4b541ca7 100644
--- a/src/net.cpp
+++ b/src/net.cpp
@@ -16,6 +16,7 @@
#include <net_permissions.h>
#include <netbase.h>
#include <node/ui_interface.h>
+#include <optional.h>
#include <protocol.h>
#include <random.h>
#include <scheduler.h>
@@ -844,21 +845,6 @@ size_t CConnman::SocketSendData(CNode *pnode) const EXCLUSIVE_LOCKS_REQUIRED(pno
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;
@@ -914,43 +900,8 @@ static void EraseLastKElements(std::vector<T> &elements, Comparator comparator,
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()
+[[nodiscard]] Optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&& vEvictionCandidates)
{
- std::vector<NodeEvictionCandidate> 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);
- }
- }
-
// Protect connections with certain characteristics
// Deterministically select 4 peers to protect by netgroup.
@@ -988,7 +939,7 @@ bool CConnman::AttemptToEvictConnection()
total_protect_size -= initial_size - vEvictionCandidates.size();
EraseLastKElements(vEvictionCandidates, ReverseCompareNodeTimeConnected, total_protect_size);
- if (vEvictionCandidates.empty()) return false;
+ if (vEvictionCandidates.empty()) return nullopt;
// If any remaining peers are preferred for eviction consider only them.
// This happens after the other preferences since if a peer is really the best by other criteria (esp relaying blocks)
@@ -1020,10 +971,52 @@ bool CConnman::AttemptToEvictConnection()
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<NodeEvictionCandidate> 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 Optional<NodeId> 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/net.h b/src/net.h
index 20e356562b..278e539f8d 100644
--- a/src/net.h
+++ b/src/net.h
@@ -33,6 +33,7 @@
#include <map>
#include <memory>
#include <thread>
+#include <vector>
class CScheduler;
class CNode;
@@ -1239,4 +1240,21 @@ inline std::chrono::microseconds PoissonNextSend(std::chrono::microseconds now,
return std::chrono::microseconds{PoissonNextSend(now.count(), average_interval.count())};
}
+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]] Optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&& vEvictionCandidates);
+
#endif // BITCOIN_NET_H
diff --git a/src/test/net_tests.cpp b/src/test/net_tests.cpp
index c86974ba5b..beac65942e 100644
--- a/src/test/net_tests.cpp
+++ b/src/test/net_tests.cpp
@@ -9,6 +9,7 @@
#include <cstdint>
#include <net.h>
#include <netbase.h>
+#include <optional.h>
#include <serialize.h>
#include <span.h>
#include <streams.h>
@@ -21,6 +22,7 @@
#include <boost/test/unit_test.hpp>
+#include <algorithm>
#include <ios>
#include <memory>
#include <string>
@@ -781,4 +783,147 @@ BOOST_AUTO_TEST_CASE(PoissonNextSend)
g_mock_deterministic_tests = 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)),
+ /* nMinPingUsecTime */ static_cast<int64_t>(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 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.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()