net: Add unit testing of node eviction logic

practicalswift commented at 12:47 pm on November 24, 2020: contributor

Add unit testing of node eviction logic.

Closes #19966.

practicalswift force-pushed on Nov 24, 2020

fanquake added the label P2P on Nov 24, 2020

fanquake added the label Tests on Nov 24, 2020

practicalswift force-pushed on Nov 24, 2020

DrahtBot commented at 7:48 pm on November 24, 2020: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#20196 (net: fix GetListenPort() to derive the proper port by vasild)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

jonatack commented at 10:16 pm on November 24, 2020: member

Thanks for working on adding testing here. I’ll try to review this soon.

in src/net.cpp:973 in 2c62fb607c outdated

966@@ -1016,7 +967,51 @@ bool CConnman::AttemptToEvictConnection()
967     vEvictionCandidates = std::move(mapNetGroupNodes[naMostConnections]);
968 
969     // Disconnect from the network group with the most connections
970-    NodeId evicted = vEvictionCandidates.front().id;
971+    return vEvictionCandidates.front();
972+}
973+
974+/** Try to find a connection to evict when the node is full.

laanwj commented at 12:12 pm on December 3, 2020:

Please move this doc-comment to the header, it’s an exported function now.

practicalswift commented at 4:10 pm on December 4, 2020:

Good point. Done!

laanwj commented at 12:12 pm on December 3, 2020: member

Concept ACK. Thanks for adding tests.

I sometimes wonder if it would make sense to move “semi-internal” things that are only exposed externally for unit testing, like in this case “NodeEvictionCandidate” and “SelectNodeToEvict”, to a separate set of headers. But not here anyhow.

in src/test/net_tests.cpp:820 in 2c62fb607c outdated

815+namespace {
816+// The number of eviction candidates at (or above) which we are guaranteed that
817+// the current eviction logic will find a node to evict no matter what eviction
818+// candidates it is given. This constant may need to be adjusted if the eviction
819+// logic changes.
820+const int GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE = 29;

dhruv commented at 0:35 am on December 4, 2020:

Would it be valuable to break this out into the various reasons the peers are protected from eviction? For example:

In src/net.h

0const int PEERS_PROTECTED_BY_NET_GROUP = 4

In src/net.cpp

0EraseLastKElements(vEvictionCandidates, CompareNetGroupKeyed, PEERS_PROTECTED_BY_NET_GROUP);

In src/test/net_tests.cpp:

0GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE = PEERS_PROTECTED_BY_NET_GROUP + ... + 1

jnewbery commented at 2:24 pm on December 4, 2020:

0constexpr int GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE{29};

practicalswift commented at 4:13 pm on December 4, 2020:

That is nicer. Addressed!

practicalswift commented at 10:33 pm on December 4, 2020:

I think that is a good idea but I kind of like that this PR doesn’t touch the actual selection code (keeping the diff at a minimum). I’d like to keep it that way but I’d be glad to review a change like the one suggested in a trivial “introduce constants” PR:).

in src/test/net_tests.cpp:826 in 2c62fb607c outdated

821+
822+// The number of eviction candidates at (or below) which we are guaranteed that
823+// the current eviction logic won't find a node to evict no matter what eviction
824+// candidates it is given. This constant may need to be adjusted if the eviction
825+// logic changes.
826+const int GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW = 20;

dhruv commented at 0:42 am on December 4, 2020:

Is this the highest such number at which non-eviction is guaranteed? If so, could you help me understand how we get 20?

practicalswift commented at 10:29 pm on December 4, 2020:

Yes, but I’m afraid I cannot help you with that at the moment: so far it is a purely an empirical/experimental result :D

Counterexamples or proofs welcome! :)

in src/net.cpp:1006 in 75f056fe19 outdated

1003+            NodeEvictionCandidate candidate = {node->GetId(), node->nTimeConnected, node->nMinPingUsecTime,
1004+                                               node->nLastBlockTime, node->nLastTXTime,
1005+                                               HasAllDesirableServiceFlags(node->nServices),
1006+                                               peer_relay_txes, peer_filter_not_null, node->nKeyedNetGroup,
1007+                                               node->m_prefer_evict, node->addr.IsLocal()};
1008+            vEvictionCandidates.push_back(candidate);

dhruv commented at 4:49 am on December 4, 2020:

Would it make sense to use emplace_back here?

practicalswift commented at 11:03 pm on December 4, 2020:

I’m afraid that won’t be possible until C++20¹ :) See P0960: “Allow initializing aggregates from a parenthesized list of values” .

¹ Assuming you mean without adding a new ctor to NodeEvictionCandidate.

dhruv commented at 4:59 am on December 4, 2020: member

utACK 2c62fb6. Thank you, @practicalswift for making the code more testable. Also for exposure to idiomatic modern C++. I will checkout the branch and run soon.

in src/net.cpp:899 in 2c62fb607c outdated

903- *   for each of several distinct characteristics which are difficult
904- *   to forge.  In order to partition a node the attacker must be
905- *   simultaneously better at all of them than honest peers.
906- */
907-bool CConnman::AttemptToEvictConnection()
908+NODISCARD Optional<NodeEvictionCandidate> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&& vEvictionCandidates)

jnewbery commented at 2:07 pm on December 4, 2020:

This is a silent merge conflict with master. NODISCARD should be replaced with [[nodiscard]]

jnewbery commented at 2:19 pm on December 4, 2020:

Why return a NodeEvictionCandidate optional here, when only the NodeId is used? I think it’d be better to return an Optional<NodeId>

practicalswift commented at 4:09 pm on December 4, 2020:

Thanks! Fixed!

practicalswift commented at 4:09 pm on December 4, 2020:

Makes sense. Feedback addressed!

in src/net.cpp:1009 in 2c62fb607c outdated

1005+                                               HasAllDesirableServiceFlags(node->nServices),
1006+                                               peer_relay_txes, peer_filter_not_null, node->nKeyedNetGroup,
1007+                                               node->m_prefer_evict, node->addr.IsLocal()};
1008+            vEvictionCandidates.push_back(candidate);
1009+        }
1010+        node_to_evict = SelectNodeToEvict(std::move(vEvictionCandidates));

jnewbery commented at 2:16 pm on December 4, 2020:

Why is this called with cs_vNodes held? Previously, we’d release the lock before running through this logic.

jnewbery commented at 2:19 pm on December 4, 2020:

What’s the reason for the std::move here? Why not just pass this as an lvalue reference?

practicalswift commented at 3:01 pm on December 4, 2020:

Good point. It can be moved to the outer scope. Thanks!

Context: #19972 (review)

practicalswift commented at 4:10 pm on December 4, 2020:

rvalue ref was suggested by @sipa: see #19972 (review) for rationale.

jnewbery commented at 10:54 am on December 7, 2020:

I understand why you’d want to pass by ref, but there’s no benefit to passing by rvalue. This code suggests to me that SelectNodeToEvict() is going to keep ownership of vEvictionCandidates and you’re using move semantics to avoid a copy, but that’s not actually happening here.

There’s no harm in using && and move here, but it’s unnecessary and possibly confusing.

in src/test/net_tests.cpp:780 in 2c62fb607c outdated

772@@ -771,4 +773,129 @@ BOOST_AUTO_TEST_CASE(PoissonNextSend)
773     g_mock_deterministic_tests = false;
774 }
775 
776+std::vector<NodeEvictionCandidate> GetRandomNodeEvictionCandidates(const int n_candidates, FastRandomContext& random_context)
777+{
778+    std::vector<NodeEvictionCandidate> candidates;
779+    for (int i = 0; i < n_candidates; ++i) {
780+        candidates.push_back({/* id */ static_cast<NodeId>(random_context.randrange(100)),

jnewbery commented at 2:21 pm on December 4, 2020:

This can create duplicate node ids, which isn’t possible in the product code.

practicalswift commented at 4:12 pm on December 4, 2020:

Now setting id to i directly making it unique. Instead of relying on the caller doing this :)

in src/test/net_tests.cpp:803 in 2c62fb607c outdated

798+    Shuffle(shuffled_candidates.begin(), shuffled_candidates.end(), random_context);
799+    const Optional<NodeEvictionCandidate> evicted_node = SelectNodeToEvict(std::move(shuffled_candidates));
800+    if (!evicted_node) {
801+        return false;
802+    }
803+    return std::find(node_ids.begin(), node_ids.end(), evicted_node->id) != node_ids.end();

jnewbery commented at 2:23 pm on December 4, 2020:

Does this break if there are multiple eviction candidates with the same id?

practicalswift commented at 4:13 pm on December 4, 2020:

Yes, the code was relying on the caller making sure the candidate ids are unique. Now doing that in GetRandomNodeEvictionCandidates as suggested.

in src/test/net_tests.cpp:856 in 2c62fb607c outdated

851+
852+            // Four nodes with the highest keyed netgroup values should be
853+            // protected from eviction.
854+            BOOST_CHECK(!IsEvicted(
855+                number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate, const size_t idx) {
856+                    candidate.id = idx;

jnewbery commented at 2:28 pm on December 4, 2020:

I think if you just constructed the NodeEvictionCandidates with sequential node id numbers, you wouldn’t need to do this here.

practicalswift commented at 4:14 pm on December 4, 2020:

Good point. Done!

jnewbery added the label Review club on Dec 4, 2020

practicalswift force-pushed on Dec 4, 2020

MarcoFalke commented at 5:35 am on December 5, 2020: member

tsan failue can be ignored or fixed by a rebase

practicalswift commented at 10:05 am on December 5, 2020: contributor

@MarcoFalke Thanks! Rebased!

practicalswift force-pushed on Dec 5, 2020

in src/net.cpp:12 in 071b4cdd50 outdated

 8@@ -9,6 +9,7 @@
 9 
10 #include <net.h>
11 
12+#include <attributes.h>

jnewbery commented at 10:45 am on December 7, 2020:

No longer needed since you removed NODISCARD

practicalswift commented at 11:47 am on December 7, 2020:

Fixed!

in src/test/net_tests.cpp:796 in 071b4cdd50 outdated

790+                              /* m_is_local */ random_context.randbool()});
791+    }
792+    return candidates;
793+}
794+
795+bool IsEvicted(const std::vector<NodeEvictionCandidate>& candidates, const std::vector<NodeId> node_ids, FastRandomContext& random_context)

jnewbery commented at 11:11 am on December 7, 2020:

I think this function and the other IsEvicted() could use a very short comment to explain the interface (here: returns true if any of the node ids in node_ids are selected for eviction).

practicalswift commented at 11:47 am on December 7, 2020:

Fixed!

jnewbery commented at 11:13 am on December 7, 2020: member

Very strong concept ACK. This area of the code is definitely undertested. The structure of the unit tests (passing in a setup lambda function to set the relevant parameters in the eviction candidates) is really nice.

practicalswift force-pushed on Dec 7, 2020

MarcoFalke added the label Needs rebase on Dec 7, 2020

MarcoFalke commented at 11:51 am on December 7, 2020: member

needs rebase

practicalswift force-pushed on Dec 7, 2020

MarcoFalke renamed this:
~~test/net: Add unit testing of node eviction logic~~
net: Add unit testing of node eviction logic
on Dec 7, 2020

practicalswift commented at 12:27 pm on December 7, 2020: contributor

I understand why you’d want to pass by ref, but there’s no benefit to passing by rvalue. This code suggests to me that SelectNodeToEvict() is going to keep ownership of vEvictionCandidates and you’re using move semantics to avoid a copy, but that’s not actually happening here.

I’ve now reverted to the original version (alternative 1 below), since your suggestion and sipa’s suggestion are mutually exclusive :)

I’ll let others chime in regarding the choice between the three alternatives:

0Alternative 1. Optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>)
1Alternative 2. Optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&)
2Alternative 3. Optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&&)

Trying to summarize the pros/cons:

Alternative 1. Simple and no gotchas. Does an extraneous copy.
Alternative 2. No extraneous copy. Possibly surprising that a function named SelectNodeToEvict modifies its input.
Alternative 3. No extraneous copy. Risk of accidental use-after-moved-from in the future. Possibly confusing (see #20477 (review)).

Perhaps the members of the review club could chime in. Some questions for the review club: Do you agree with the pros/cons of each alternative? Which alternative do you find easier to review? Which alternative do you prefer? Is it possible to quantify the real-world impact of the extraneous copy in a theoretical worst-case scenario?

jnewbery commented at 12:37 pm on December 7, 2020: member

since your suggestion and sipa’s suggestion are mutually exclusive :)

I don’t think they are mutually exclusive. There are two questions here:

Should the argument be passed by value or by reference?
If passed by reference, should it be passed by lvalue reference or rvalue reference?

I don’t think there’s any disagreement about (1). We should pass by reference to avoid a copy.

For (2), I think it’s slightly odd to pass by rvalue reference when it’s not necessary to do so, but that’s more of a stylistic thing. I see now that you’re calling the function with a prvalue in the tests, which means you can’t pass by lvalue reference. My preference would therefore be to revert to what you had before.

in src/test/net_tests.cpp:800 in ccc8162b22 outdated

795+// Returns true if any of the node ids in node_ids are selected for eviction.
796+bool IsEvicted(const std::vector<NodeEvictionCandidate>& candidates, const std::vector<NodeId> node_ids, FastRandomContext& random_context)
797+{
798+    std::vector<NodeEvictionCandidate> shuffled_candidates = candidates;
799+    Shuffle(shuffled_candidates.begin(), shuffled_candidates.end(), random_context);
800+    const Optional<NodeId> evicted_node_id = SelectNodeToEvict(shuffled_candidates);

jnewbery commented at 12:45 pm on December 7, 2020:

Any reason not to shuffle in place?

0bool IsEvicted(std::vector<NodeEvictionCandidate>& candidates, const std::vector<NodeId> node_ids, FastRandomContext& random_context)
1{
2    Shuffle(candidates.begin(), candidates.end(), random_context);
3    const Optional<NodeId> evicted_node_id = SelectNodeToEvict(candidates);

practicalswift commented at 12:58 pm on December 7, 2020: contributor

@jnewbery

Updated accordingly.

Personally I prefer the std::vector<NodeEvictionCandidate>&& alternative in this case since it makes it clear from reading the code at the call site that vEvictionCandidates is not intended to be used after the SelectNodeToEvict call.

Hopefully any use-after-moved-from would be quite obvious.

Example of future patches where the signature makes a difference from a gotcha perspective:

Given signature Optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&)

0    Optional<NodeId> node_id_to_evict = SelectNodeToEvict(vEvictionCandidates);
1    if (!node_id_to_evict) {
2        return false;
3    }
4+   if (!vEvictionCandidates.empty()) { // Likely BAD, but not immediately obvious why
5+       … do something with the now perhaps surprisingly modified vEvictionCandidates …

Given signature Optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&&)

0    Optional<NodeId> node_id_to_evict = SelectNodeToEvict(std::move(vEvictionCandidates));
1    if (!node_id_to_evict) {
2        return false;
3    }
4+   if (!vEvictionCandidates.empty()) { // BAD and hopefully obviously so thanks to std::move above :)
5+       … do something with vEvictionCandidates which is now in some valid but otherwise indeterminate state …

practicalswift force-pushed on Dec 7, 2020

DrahtBot removed the label Needs rebase on Dec 7, 2020

jnewbery commented at 1:55 pm on December 7, 2020: member

Personally I prefer the std::vector&& alternative in this case since it makes it clear from reading the code at the call site that vEvictionCandidates is not intended to be used after the SelectNodeToEvict call.

Fine by me!

jnewbery commented at 1:56 pm on December 7, 2020: member

utACK cadd93f35d1bbf662e348a0dee172cdf4af6a903

in src/test/net_tests.cpp:823 in cadd93f35d outdated

818+namespace {
819+// The number of eviction candidates at (or above) which we are guaranteed that
820+// the current eviction logic will find a node to evict no matter what eviction
821+// candidates it is given. This constant may need to be adjusted if the eviction
822+// logic changes.
823+constexpr int GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE{29};

narula commented at 5:17 pm on December 9, 2020:

Please add some justification for these numbers, even if it’s a description of the simulation/test you ran to get them. I don’t understand how this 29 is guaranteed and the 20 is guaranteed below.

This reply makes it sound like it’s not guaranteed?

#20477 (review)

narula commented at 5:51 pm on December 9, 2020:

Good discussion in PR review club about it today and @jonatack pointed out justification for the 20 is in test/functional/p2p_eviction.py.

in src/test/net_tests.cpp:852 in cadd93f35d outdated

847+                BOOST_CHECK(!SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context)));
848+            }
849+            if (number_of_nodes >= GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE) {
850+                BOOST_CHECK(SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context)));
851+            } else {
852+                continue;

narula commented at 5:26 pm on December 9, 2020:

I think you’re not running the following checks if the number of nodes is between the min and the max because of this continue. Is that the intention?

~~Edit: ignore me! I’m looking at the wrong for loop.~~

Edit again: Nope, I think I was right the first time…

MarcoFalke commented at 6:02 pm on December 9, 2020:

I don’t get this either

troygiorshev commented at 7:13 pm on December 9, 2020:

I’ve proposed an alternative that might be easier to parse. https://github.com/bitcoin/bitcoin/pull/20477/files#r539574518

troygiorshev commented at 7:33 pm on December 9, 2020:

It’s “don’t run the checks if the number of nodes is less than the max”. But, I’m not sure why we would do this…

practicalswift commented at 10:42 pm on December 9, 2020:

@narula Oh, good catch! The continue should be dropped. I don’t remember what the apparently incorrect reasoning behind it was TBH :)

Thanks for catching it!

MarcoFalke commented at 6:02 pm on December 9, 2020: member

Concept ACK

in src/test/net_tests.cpp:853 in cadd93f35d outdated

848+            }
849+            if (number_of_nodes >= GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE) {
850+                BOOST_CHECK(SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context)));
851+            } else {
852+                continue;
853+            }

troygiorshev commented at 7:12 pm on December 9, 2020:

I’m a HUGE supporter of the early return pattern (AKA bouncer pattern) that you’re using here. However, maybe this alternative is a little easier to parse.

(Maybe not in this annoyingly narrow GitHub window though…)

 0            if (number_of_nodes < GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE) {
 1            	// Verify correctness of GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW
 2            	if (number_of_nodes <= GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW) {
 3            		// At this number of nodes, we're guaranteed to never evict any of them
 4                	BOOST_CHECK(!SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context)));
 5                }
 6            	// There is no need to run the sub-tests for fewer than the number of nodes guaranteed for eviction
 7            	// ^ FWIW I don't agree with this, see below
 8            	continue;
 9            }
10            // number_of_nodes >= GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE
11            // Verify correctness of GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE
12            BOOST_CHECK(SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context)));

Honestly though, I think it’s just the similarity between the names of GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE and GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW that is making this so difficult. Maybe (maybe…) EVICTION_THRESHOLD and NON_EVICTION_THRESHOLD and put the fact that it’s inclusive on both ends in the comments? Or follow the half-open convention of “lower bounds are inclusive, upper bounds are exclusive”. Popular in Python, not sure about C++.

All of this said, why have the early return at all? All of the tests below check for non-eviction. Can’t we run them regardless of the number of nodes?

(Feel free to reword my code comments)

practicalswift commented at 11:39 pm on December 9, 2020: contributor

Thanks for reviewing!

Pushed an updated version:

Now skipping the GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE and GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW checking which isn’t particularly important compared to the other tests.

Also fixed an incorrect comment.

Should hopefully be ready for final review :)

practicalswift force-pushed on Dec 9, 2020

in src/test/net_tests.cpp:853 in d32c53fe64 outdated

848+                number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) {
849+                    candidate.nLastTXTime = number_of_nodes - candidate.id;
850+                },
851+                {0, 1, 2, 3}, random_context));
852+
853+            // Four non-tx-relay peers that most recently sent us novel blocks

jnewbery commented at 10:29 am on December 10, 2020:

The comment here says ‘four’, but the code below is asserting that 8 non-tx-relay candidates are protected.

practicalswift commented at 10:53 pm on December 10, 2020:

Good catch. There are two nLastBlockTime based protections: that’s why more than four are protected in practice in this specific test case. Now testing the two different nLastBlockTime protections a.) independently and b.) jointly.

in src/test/net_tests.cpp:812 in d32c53fe64 outdated

807+// apply eviction logic and then return true if any of the node ids in node_ids
808+// are selected for eviction.
809+bool IsEvicted(const int number_of_nodes, std::function<void(NodeEvictionCandidate&)> candidate_setup_fn, const std::vector<NodeId> node_ids, FastRandomContext& random_context)
810+{
811+    std::vector<NodeEvictionCandidate> candidates = GetRandomNodeEvictionCandidates(number_of_nodes, random_context);
812+    for (size_t i = 0; i < candidates.size(); ++i) {

MarcoFalke commented at 1:01 pm on December 10, 2020:

nit: could use ranged for loop?

practicalswift commented at 10:01 pm on December 10, 2020:

Oh, of course. A prior version used the index. Thanks!

in src/test/net_tests.cpp:805 in d32c53fe64 outdated

798+    Shuffle(candidates.begin(), candidates.end(), random_context);
799+    const Optional<NodeId> evicted_node_id = SelectNodeToEvict(std::move(candidates));
800+    if (!evicted_node_id) {
801+        return false;
802+    }
803+    return std::find(node_ids.begin(), node_ids.end(), *evicted_node_id) != node_ids.end();

MarcoFalke commented at 1:05 pm on December 10, 2020:

how is this different from a less verbose

0    return node_ids.find(*evicted_node_id) != node_ids.end();

practicalswift commented at 10:00 pm on December 10, 2020:

std::vector doesn’t have a find function. Perhaps you were thinking of std::map or std::set? :)

in src/test/net_tests.cpp:790 in d32c53fe64 outdated

785+                              /* fRelevantServices */ random_context.randbool(),
786+                              /* fRelayTxes */ random_context.randbool(),
787+                              /* fBloomFilter */ random_context.randbool(),
788+                              /* nKeyedNetGroup */ random_context.randrange(100),
789+                              /* prefer_evict */ random_context.randbool(),
790+                              /* m_is_local */ random_context.randbool()});

MarcoFalke commented at 1:08 pm on December 10, 2020:

style-nit: Adding a trailing comma here would not only make future diffs smaller if they add a new member, but also eat the extraneous whitespace at the beginning of the line.

practicalswift commented at 10:01 pm on December 10, 2020:

Good point! Thanks!

MarcoFalke approved

MarcoFalke commented at 1:13 pm on December 10, 2020: member

ACK.

Nice test.

practicalswift force-pushed on Dec 10, 2020

practicalswift commented at 10:58 pm on December 10, 2020: contributor

Updated.

Addressed feedback from @MarcoFalke and @jnewbery.

Also added a combined test which tests the protections based on nKeyedNetGroup (4 peers protected), nMinPingUsecTime (8 peers protected), nLastTXTime (4 peers protected) and nLastBlockTime (8 peers protected) jointly.

Kindly re-review thoroughly :)

in src/test/net_tests.cpp:833 in 6767d63d02 outdated

828+
829+    for (int i = 0; i < NODE_EVICTION_TEST_ROUNDS; ++i) {
830+        for (int number_of_nodes = 0; number_of_nodes < NODE_EVICTION_TEST_UP_TO_N_NODES; ++number_of_nodes) {
831+            // Four nodes with the highest keyed netgroup values should be
832+            // protected from eviction.
833+            BOOST_CHECK(!IsEvicted(

dhruv commented at 11:36 pm on December 10, 2020:

In the previous version of the test, we tested:

No eviction happens with <= 20 peers
An eviction happens with >= 29 peers
If an eviction happens, the protected peers are not evicted

In the new version, we are checking that the protected peers are not evicted in any situation (3). The last test case covers for (1). However, the test will not alert if an eviction does not happen when it should (>= 29 peers). Am I missing something?

Personally, I found the GUARANTEED_EVICTION_THRESHOLD and GUARANTEED_NON_EVICTION_THRESHOLD valuable to test and also as documentation.

practicalswift commented at 6:50 am on December 11, 2020:

@dhruv I can re-add it if someone has time to figure out the actual logic behind the constant 29. I haven’t had time to back my empirical observation (via simulation) with proper analysis. Help welcome! :)

dhruv commented at 3:43 pm on December 11, 2020:

From PR Review club:

Q: Why is eviction guaranteed if we have at least 29 eviction candidates?

The code in net.cpp (https://github.com/bitcoin/bitcoin/blob/fabecce/src/net.cpp#L954-L968) protects at most 28 peers from eviction (4 by net group, 8 by lowest ping time, 4 by last time of novel tx, up to 8 non-tx-relay peers by last novel block time, and 4 more peers by last novel block time). So any additional peers are guaranteed to be candidates for eviction.

Q: Why is non-eviction guaranteed if we have no more than 20 eviction candidates? Is 20 the highest number of nodes that guarantees non-eviction?

The protection at net.cpp::961 for up to 8 non-tx-relay peers may, or may not apply to the randomly generated eviction candidates since !n.fRelayTxes && n.fRelevantServices will evaluate to randbool. So we cannot count them in the guaranteed non-eviction?

So, guaranteed non-eviction is only on 4(CompareNetGroupKeyed) + 8(ReverseCompareNodeMinPingTime) + 4(CompareNodeTXTime) + 4(CompareNodeBlockTime) = 20.

jonatack commented at 4:12 pm on December 11, 2020:

@practicalswift the review club meeting log about your PR is here, if useful: https://bitcoincore.reviews/20477

practicalswift commented at 3:24 pm on December 15, 2020:

Thanks! Now assert eviction at >= 29 candidates and non-eviction at <= 20 candidates. Please re-review :)

jnewbery commented at 4:52 pm on December 15, 2020:

I don’t think these <=20/>=29 tests are very useful, will need to be updated whenever any changes are made to the eviction logic, and aren’t very realistic (in general, nodes have many more than 29 inbound slots).

practicalswift commented at 5:03 pm on December 15, 2020:

I’ll happily adjust to the consensus opinion, but I’ll let others chime in before changing anything in order to avoid another round of change+revert :)

dhruv commented at 7:30 pm on December 15, 2020:

Even if we remove the <=20 assertion, we are already checking non-eviction <=20 (it’s implicit in the tests). So the tests will need need to updated when changes are made anyway. I am not sure I understand why that’s undesirable.

I think it is useful to test that eviction does indeed happen (not just that protections are provided) when it should. After all, SelectNodeToEvict should select a node to evict :) Without the >=29 assertion, does this test guarantee that?

All that said, @jnewbery is infinitely more qualified than I am. I’m happy with whatever you all decide and will learn from it.

jnewbery commented at 9:47 am on December 11, 2020: member

ACK 6767d63d02cc8a670f3d409db1c78a77fdcb5363

jonatack commented at 4:13 pm on December 11, 2020: member

Will review properly as soon as my laptop is done with the gitian builds for 3 RCs…until then, it’s basically unusable.

practicalswift commented at 3:25 pm on December 15, 2020: contributor

Updated to address @dhruv’s feedback. Should hopefully be ready for final review. Please re-review :)

practicalswift force-pushed on Dec 15, 2020

dhruv commented at 7:42 pm on December 15, 2020: member

ACK 1c9b235

MarcoFalke commented at 10:04 am on December 16, 2020: member

cr ACK 6767d63d02cc8a670f3d409db1c78a77fdcb5363 🤠

Signature:

 0-----BEGIN PGP SIGNED MESSAGE-----
 1Hash: SHA512
 2
 3cr ACK 6767d63d02cc8a670f3d409db1c78a77fdcb5363 🤠
 4-----BEGIN PGP SIGNATURE-----
 5
 6iQGzBAEBCgAdFiEE+rVPoUahrI9sLGYTzit1aX5ppUgFAlwqrYAACgkQzit1aX5p
 7pUgJLwwAljffgO2Xw1Iez563pRA0ztSBIkuzEBPGf9nYifcbQJsfPMCdLzuu3MPQ
 8ZgfWPQNmtEuSTNq0R4Hl+XaPmBcoS5LDOTfxJWsQtb+kE0uXVfN1nRu4+d91/Sor
 9+NT9Ach7YRVvJPOZZc0euxyka0pxLwX3+LdXa1k26gL2teT5knaROnCfSxenrFrO
10YIzbBfkn2lm/TMu4FhC2hW+OZon4zfHHCPzJYkQR2FByixLDqIIEOJiOY9ycLJQm
11ys9xGzn0lZz0/hw4ApEe2b+lLREn/6YMjPNefo0hWcADAYDbjsvEYBsFm0Z6m5Mw
12BXA4lhUPWes5QboZ1LCxrEdxGG10uj8LwIBwESp/KVpZ53w0f9yU+mBQ68bruAHh
135hFAJmriES6q8Ml/q2b3IUq8tXwOBM+2poGR8MtTYV6Obk/3eus2bA33EVsfNzm3
14ZXzo/F1yQvXlD1kSDU3Aez1yodeLK3GQNoTKaPIGeIwOM3sPhDhJ6REMYskLM4tt
15PxqHvOZz
16=Gf1H
17-----END PGP SIGNATURE-----

Timestamp of file with hash 23398d20d71a2405d911d0dc99e4fc62b592150f49fa6c17afd6d588c418522c -

MarcoFalke commented at 10:06 am on December 16, 2020: member

cr ACK 1c9b235c330fe7b9b71f687ef14cb10fe588172b 👲

Signature:

 0-----BEGIN PGP SIGNED MESSAGE-----
 1Hash: SHA512
 2
 3cr ACK 1c9b235c330fe7b9b71f687ef14cb10fe588172b 👲
 4-----BEGIN PGP SIGNATURE-----
 5
 6iQGzBAEBCgAdFiEE+rVPoUahrI9sLGYTzit1aX5ppUgFAlwqrYAACgkQzit1aX5p
 7pUjQWgv/TnEWYjD/Ws2y2WL23agZIEyXZwlxbLCJTWkydKzBnOrPdP1QOBl3DZ95
 81ICN5MfBErZtO825TG8NU2VfCesJRIJKV4996nw7GqpN+KfBlkYHNipYfoF9xdHB
 9J0MT/97/wsrsWGhYEdwx3ftk0CHMNNDMN++N4BSx3h314jGnuNzV4DiUoz2ea9X3
101IAsitmrqa37xIlLIvdLSwRVDcWQyJ7oQ+NUo2KsSztXJ6XEpZcUAqhfRwuS9Ku4
11R3DIJHLXKk8PUEXlnmDWVtfnhuhGW4g3V6ZJdUId7OfUr85H/rGSxSeejqSqxLt/
128hGiRsuftelXPfd7SOAjRW5h6x6NFCJBgcVVOYKzjvjyknyH3it3IrPi9WFwLLWS
1398fNiUtiE2SsXOUFXxbbyalCZlQols/pBklibFoPNPhfHCT7ZPvazINGBJwkwxVS
14GL1IIAKftgsUJhmiSDy/LHfHwXC2vOL2ipdPLJuR7CPLPj9iBZ2picP4h3zRpSo2
15lubdxdSX
16=z6dl
17-----END PGP SIGNATURE-----

Timestamp of file with hash 3a47dabfa2f12ebc4fbd136dcd7771912bfcd7ed7ce86ba72f473c364fba70a0 -

MarcoFalke commented at 10:07 am on December 16, 2020: member

I ACKed both versions. Let me know which one to merge.

jnewbery commented at 10:11 am on December 16, 2020: member

code review ACK 1c9b235c33

Either are fine to merge.

jonatack commented at 10:36 am on December 16, 2020: member

wait for meeee 😀

in src/net.cpp:899 in 1c9b235c33 outdated

902- *   for each of several distinct characteristics which are difficult
903- *   to forge.  In order to partition a node the attacker must be
904- *   simultaneously better at all of them than honest peers.
905- */
906-bool CConnman::AttemptToEvictConnection()
907+[[nodiscard]] Optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&& vEvictionCandidates)

jonatack commented at 10:48 am on December 16, 2020:

fbba7d8aada5b1d7a63ad4133 add #include <optional.h> header

perhaps call this SelectConnectionToEvict() for symmetry with AttemptToEvictConnection(), or SelectPeerToEvict() as a peer is a node that is not ours

practicalswift commented at 11:58 am on December 16, 2020:

Now including optional.h.

Regarding the naming: I see your point but given NodeEvictionCandidate inputs I think SelectNodeToEvict works.

in src/net.cpp:1008 in 1c9b235c33 outdated

1004+                                               peer_relay_txes, peer_filter_not_null, node->nKeyedNetGroup,
1005+                                               node->m_prefer_evict, node->addr.IsLocal()};
1006+            vEvictionCandidates.push_back(candidate);
1007+        }
1008+    }
1009+    Optional<NodeId> node_id_to_evict = SelectNodeToEvict(std::move(vEvictionCandidates));

jonatack commented at 10:50 am on December 16, 2020:

fbba7d8aada5b1d7a63ad4 could be const

practicalswift commented at 11:58 am on December 16, 2020:

Good catch! Fixed!

in src/test/net_tests.cpp:798 in 1c9b235c33 outdated

793+    }
794+    return candidates;
795+}
796+
797+// Returns true if any of the node ids in node_ids are selected for eviction.
798+bool IsEvicted(std::vector<NodeEvictionCandidate> candidates, const std::vector<NodeId> node_ids, FastRandomContext& random_context)

jonatack commented at 11:07 am on December 16, 2020:

6767d63d02cc8a670f3d409db1 ref to const?

0bool IsEvicted(std::vector<NodeEvictionCandidate> candidates, const std::vector<NodeId>& node_ids, FastRandomContext& random_context)

practicalswift commented at 11:58 am on December 16, 2020:

Good catch! Fixed!

in src/test/net_tests.cpp:811 in 1c9b235c33 outdated

806+}
807+
808+// Create number_of_nodes random nodes, apply setup function candidate_setup_fn,
809+// apply eviction logic and then return true if any of the node ids in node_ids
810+// are selected for eviction.
811+bool IsEvicted(const int number_of_nodes, std::function<void(NodeEvictionCandidate&)> candidate_setup_fn, const std::vector<NodeId> node_ids, FastRandomContext& random_context)

jonatack commented at 11:10 am on December 16, 2020:

6767d63d02cc8a670f3d409 ref to const here as well

0bool IsEvicted(const int number_of_nodes, std::function<void(NodeEvictionCandidate&)> candidate_setup_fn, const std::vector<NodeId>& node_ids, FastRandomContext& random_context)

practicalswift commented at 11:58 am on December 16, 2020:

Good catch! Fixed!

jonatack commented at 11:30 am on December 16, 2020: member

ACK 1c9b235c330fe7b9b71f modulo a few suggestions

net: Move eviction node selection logic to SelectNodeToEvict(...) ed73f8cee0

test: Add unit testing of node eviction logic 685c428de0

Assert eviction at >= 29 candidates. Assert non-eviction at <= 20 candidates. fee88237e0

practicalswift force-pushed on Dec 16, 2020

practicalswift commented at 12:01 pm on December 16, 2020: contributor

@jonatack Thanks for reviewing! Feedback addressed: please re-review :)

jonatack commented at 12:16 pm on December 16, 2020: member

ACK fee88237e03c21bf81f21098e6b89ecfa5327cee

Thanks for adding this nicely done coverage! Looking forward to more.

MarcoFalke commented at 12:30 pm on December 16, 2020: member

ACK fee88237e03c21bf81f21098e6b89ecfa5327cee 🐼

Signature:

 0-----BEGIN PGP SIGNED MESSAGE-----
 1Hash: SHA512
 2
 3ACK fee88237e03c21bf81f21098e6b89ecfa5327cee 🐼
 4-----BEGIN PGP SIGNATURE-----
 5
 6iQGzBAEBCgAdFiEE+rVPoUahrI9sLGYTzit1aX5ppUgFAlwqrYAACgkQzit1aX5p
 7pUiu/Av/RLQ2/lM0mJ7uTlvDebTgk57QGAdIs4rv+t9X7wUizqNhEjFHU2KC0HS0
 8hU6QjHZelMuy0IvIRrcT33LCZkczPQbEQ4ZMAV5VZhuRNvAisi1PHxueX5U+oT83
 9UKS899fiy7VN3RD7g7E/sMDNuGAo1hSV7MgYQMOlCG8dSJ3bbuF2d1jNEYqJQ7oa
10MkmdtB0SwvCOtZyvcsVDI8yC8UJ5r2ybgE+bYfMK9BzMUyWQriWmOnoVQBrnwb5j
11Zr7g/4pnq04078EuaBVP981P+Pc4pj6Eo63iIinabl74aLU3hsHa0bnUCkpihBSg
12stooipOqKXQsOS/jI1XyElhclE3EolEE6+0QIXFpx3H7AlkovPdF/LeeezH0dVDB
13hSl7VrdKrTxP7kjSBKBMOiPbzBdVSqo6ktaqhBI7YXlDepR7V54/PlDs7QEcM91r
143iEvD/wbMFJQZHzHEbmCINPXBwdOh9MleFgm0dgTMor7djOpaxgbYq/2Y5Bx4/4K
15s1ZuLUUS
16=f3JL
17-----END PGP SIGNATURE-----

Timestamp of file with hash fb125172e7abd1e8e484ae4f527e5e86e05737d1b1e006310dca8dbb38203afc -

MarcoFalke merged this on Dec 16, 2020

MarcoFalke closed this on Dec 16, 2020

sidhujag referenced this in commit 24939efb29 on Dec 17, 2020

laanwj referenced this in commit dede9eb924 on Mar 30, 2021

practicalswift deleted the branch on Apr 10, 2021

Fabcien referenced this in commit f9de217f49 on Jun 15, 2021

Fabcien referenced this in commit e284ab5f4c on Jun 15, 2021

DrahtBot locked this on Aug 16, 2022

net: Add unit testing of node eviction logic #20477

Conflicts