Merge #9037: net: Add test-before-evict discipline to addrman

e68172ed9 Add test-before-evict discipline to addrman (Ethan Heilman)

Pull request description:

  This change implement countermeasures 3 (test-before-evict) suggested in our paper: ["Eclipse Attacks on Bitcoin’s Peer-to-Peer Network"](http://cs-people.bu.edu/heilman/eclipse/).
  # Design:

  A collision occurs when an address, addr1, is being moved to the tried table from the new table, but maps to a position in the tried table which already contains an address (addr2). The current behavior is that addr1 would evict addr2 from the tried table.

  This change ensures that during a collision, addr1 is not inserted into tried but instead inserted into a buffer (setTriedCollisions). The to-be-evicted address, addr2, is then tested by [a feeler connection](https://github.com/bitcoin/bitcoin/pull/8282). If addr2 is found to be online, we remove addr1 from the buffer and addr2 is not evicted, on the other hand if addr2 is found be offline it is replaced by addr1.

  An additional small advantage of this change is that, as no more than ten addresses can be in the test buffer at once, and addresses are only cleared one at a time from the test buffer (at 2 minute intervals), thus an attacker is forced to wait at least two minutes to insert a new address into tried after filling up the test buffer. This rate limits an attacker attempting to launch an eclipse attack.
  # Risk mitigation:
  - To prevent this functionality from being used as a DoS vector, we limit the number of addresses which are to be tested to ten. If we have more than ten addresses to test, we drop new addresses being added to tried if they would evict an address. Since the feeler thread only creates one new connection every 2 minutes the additional network overhead is limited.
  - An address in tried gains immunity from tests for 4 hours after it has been tested or successfully connected to.
  # Tests:

  This change includes additional addrman unittests which test this behavior.

  I ran an instance of this change with a much smaller tried table (2 buckets of 64 addresses) so that collisions were much more likely and observed evictions.

  ```
  2016-10-27 07:20:26 Swapping 208.12.64.252:8333 for 68.62.95.247:8333 in tried table
  2016-10-27 07:20:26 Moving 208.12.64.252:8333 to tried
  ```

  I documented tests we ran against similar earlier versions of this change in #6355.
  # Security Benefit

  This is was originally posted in PR #8282 see [this comment for full details](https://github.com/bitcoin/bitcoin/pull/8282#issuecomment-237255215).

  To determine the security benefit of these larger numbers of IPs in the tried table I modeled the attack presented in [Eclipse Attacks on Bitcoin’s Peer-to-Peer Network](https://eprint.iacr.org/2015/263).

  ![attackergraph40000-10-1000short-line](https://cloud.githubusercontent.com/assets/274814/17366828/372af458-595b-11e6-81e5-2c9f97282305.png)

  **Default node:** 595 attacker IPs for ~50% attack success.
  **Default node + test-before-evict:** 620 attacker IPs for ~50% attack success.
  **Feeler node:** 5540 attacker IPs for ~50% attack success.
  **Feeler node + test-before-evict:** 8600 attacker IPs for ~50% attack success.

  The node running feeler connections has 10 times as many online IP addresses in its tried table making an attack 10 times harder (i.e. requiring the an attacker require 10 times as many IP addresses in different /16s). Adding test-before-evict increases resistance of the node by an additional 3000 attacker IP addresses.

  Below I graph the attack over even greater attacker resources (i.e. more attacker controled IP addresses). Note that test-before-evict maintains some security far longer even against an attacker with 50,000 IPs. If this node had a larger tried table test-before-evict could greatly boost a nodes resistance to eclipse attacks.

  ![attacker graph long view](https://cloud.githubusercontent.com/assets/274814/17367108/96f46d64-595c-11e6-91cd-edba160598e7.png)

Tree-SHA512: fdad4d26aadeaad9bcdc71929b3eb4e1f855b3ee3541fbfbe25dca8d7d0a1667815402db0cb4319db6bd3fcd32d67b5bbc0e12045c4252d62d6239b7d77c4395

1 files changed, 176 insertions, 11 deletions

diff --git a/src/test/addrman_tests.cpp b/src/test/addrman_tests.cpp
index b338d6d366..0d8bd90119 100644
--- a/src/test/addrman_tests.cpp
+++ b/src/test/addrman_tests.cpp
@@ -52,6 +52,17 @@ public:
     {
         CAddrMan::Delete(nId);
     }
+
+    // Simulates connection failure so that we can test eviction of offline nodes
+    void SimConnFail(CService& addr)
+    {
+         int64_t nLastSuccess = 1;
+         Good_(addr, true, nLastSuccess); // Set last good connection in the deep past.
+
+         bool count_failure = false;
+         int64_t nLastTry = GetAdjustedTime()-61;
+         Attempt(addr, count_failure, nLastTry);
+     }
 };
 
 static CNetAddr ResolveIP(const char* ip)
@@ -226,7 +237,7 @@ BOOST_AUTO_TEST_CASE(addrman_new_collisions)
     BOOST_CHECK_EQUAL(addrman.size(), 0);
 
     for (unsigned int i = 1; i < 18; i++) {
-        CService addr = ResolveService("250.1.1." + boost::to_string(i));
+        CService addr = ResolveService("250.1.1." + std::to_string(i));
         addrman.Add(CAddress(addr, NODE_NONE), source);
 
         //Test: No collision in new table yet.
@@ -252,7 +263,7 @@ BOOST_AUTO_TEST_CASE(addrman_tried_collisions)
     BOOST_CHECK_EQUAL(addrman.size(), 0);
 
     for (unsigned int i = 1; i < 80; i++) {
-        CService addr = ResolveService("250.1.1." + boost::to_string(i));
+        CService addr = ResolveService("250.1.1." + std::to_string(i));
         addrman.Add(CAddress(addr, NODE_NONE), source);
         addrman.Good(CAddress(addr, NODE_NONE));
 
@@ -385,7 +396,7 @@ BOOST_AUTO_TEST_CASE(addrman_getaddr)
     for (unsigned int i = 1; i < (8 * 256); i++) {
         int octet1 = i % 256;
         int octet2 = i >> 8 % 256;
-        std::string strAddr = boost::to_string(octet1) + "." + boost::to_string(octet2) + ".1.23";
+        std::string strAddr = std::to_string(octet1) + "." + std::to_string(octet2) + ".1.23";
         CAddress addr = CAddress(ResolveService(strAddr), NODE_NONE);
 
         // Ensure that for all addrs in addrman, isTerrible == false.
@@ -436,8 +447,8 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_tried_bucket)
     std::set<int> buckets;
     for (int i = 0; i < 255; i++) {
         CAddrInfo infoi = CAddrInfo(
-            CAddress(ResolveService("250.1.1." + boost::to_string(i)), NODE_NONE),
-            ResolveIP("250.1.1." + boost::to_string(i)));
+            CAddress(ResolveService("250.1.1." + std::to_string(i)), NODE_NONE),
+            ResolveIP("250.1.1." + std::to_string(i)));
         int bucket = infoi.GetTriedBucket(nKey1);
         buckets.insert(bucket);
     }
@@ -448,8 +459,8 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_tried_bucket)
     buckets.clear();
     for (int j = 0; j < 255; j++) {
         CAddrInfo infoj = CAddrInfo(
-            CAddress(ResolveService("250." + boost::to_string(j) + ".1.1"), NODE_NONE),
-            ResolveIP("250." + boost::to_string(j) + ".1.1"));
+            CAddress(ResolveService("250." + std::to_string(j) + ".1.1"), NODE_NONE),
+            ResolveIP("250." + std::to_string(j) + ".1.1"));
         int bucket = infoj.GetTriedBucket(nKey1);
         buckets.insert(bucket);
     }
@@ -488,8 +499,8 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_new_bucket)
     std::set<int> buckets;
     for (int i = 0; i < 255; i++) {
         CAddrInfo infoi = CAddrInfo(
-            CAddress(ResolveService("250.1.1." + boost::to_string(i)), NODE_NONE),
-            ResolveIP("250.1.1." + boost::to_string(i)));
+            CAddress(ResolveService("250.1.1." + std::to_string(i)), NODE_NONE),
+            ResolveIP("250.1.1." + std::to_string(i)));
         int bucket = infoi.GetNewBucket(nKey1);
         buckets.insert(bucket);
     }
@@ -501,7 +512,7 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_new_bucket)
     for (int j = 0; j < 4 * 255; j++) {
         CAddrInfo infoj = CAddrInfo(CAddress(
                                         ResolveService(
-                                            boost::to_string(250 + (j / 255)) + "." + boost::to_string(j % 256) + ".1.1"), NODE_NONE),
+                                            std::to_string(250 + (j / 255)) + "." + std::to_string(j % 256) + ".1.1"), NODE_NONE),
             ResolveIP("251.4.1.1"));
         int bucket = infoj.GetNewBucket(nKey1);
         buckets.insert(bucket);
@@ -514,7 +525,7 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_new_bucket)
     for (int p = 0; p < 255; p++) {
         CAddrInfo infoj = CAddrInfo(
             CAddress(ResolveService("250.1.1.1"), NODE_NONE),
-            ResolveIP("250." + boost::to_string(p) + ".1.1"));
+            ResolveIP("250." + std::to_string(p) + ".1.1"));
         int bucket = infoj.GetNewBucket(nKey1);
         buckets.insert(bucket);
     }
@@ -522,4 +533,158 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_new_bucket)
     //  than 64 buckets.
     BOOST_CHECK(buckets.size() > 64);
 }
+
+
+BOOST_AUTO_TEST_CASE(addrman_selecttriedcollision)
+{
+    CAddrManTest addrman;
+
+    // Set addrman addr placement to be deterministic.
+    addrman.MakeDeterministic();
+
+    BOOST_CHECK(addrman.size() == 0);
+
+    // Empty addrman should return blank addrman info.
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+
+    // Add twenty two addresses.
+    CNetAddr source = ResolveIP("252.2.2.2");
+    for (unsigned int i = 1; i < 23; i++) {
+        CService addr = ResolveService("250.1.1."+std::to_string(i));
+        addrman.Add(CAddress(addr, NODE_NONE), source);
+        addrman.Good(addr);
+
+        // No collisions yet.
+        BOOST_CHECK(addrman.size() == i);
+        BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+    }
+
+    // Ensure Good handles duplicates well.
+    for (unsigned int i = 1; i < 23; i++) {
+        CService addr = ResolveService("250.1.1."+std::to_string(i));
+        addrman.Good(addr);
+
+        BOOST_CHECK(addrman.size() == 22);
+        BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+    }
+
+}
+
+BOOST_AUTO_TEST_CASE(addrman_noevict)
+{
+    CAddrManTest addrman;
+
+    // Set addrman addr placement to be deterministic.
+    addrman.MakeDeterministic();
+
+    // Add twenty two addresses.
+    CNetAddr source = ResolveIP("252.2.2.2");
+    for (unsigned int i = 1; i < 23; i++) {
+        CService addr = ResolveService("250.1.1."+std::to_string(i));
+        addrman.Add(CAddress(addr, NODE_NONE), source);
+        addrman.Good(addr);
+
+        // No collision yet.
+        BOOST_CHECK(addrman.size() == i);
+        BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+    }
+
+    // Collision between 23 and 19.
+    CService addr23 = ResolveService("250.1.1.23");
+    addrman.Add(CAddress(addr23, NODE_NONE), source);
+    addrman.Good(addr23);
+
+    BOOST_CHECK(addrman.size() == 23);
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "250.1.1.19:0");
+
+    // 23 should be discarded and 19 not evicted.
+    addrman.ResolveCollisions();
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+
+    // Lets create two collisions.
+    for (unsigned int i = 24; i < 33; i++) {
+        CService addr = ResolveService("250.1.1."+std::to_string(i));
+        addrman.Add(CAddress(addr, NODE_NONE), source);
+        addrman.Good(addr);
+
+        BOOST_CHECK(addrman.size() == i);
+        BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+    }
+
+    // Cause a collision.
+    CService addr33 = ResolveService("250.1.1.33");
+    addrman.Add(CAddress(addr33, NODE_NONE), source);
+    addrman.Good(addr33);
+    BOOST_CHECK(addrman.size() == 33);
+
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "250.1.1.27:0");
+
+    // Cause a second collision.
+    addrman.Add(CAddress(addr23, NODE_NONE), source);
+    addrman.Good(addr23);
+    BOOST_CHECK(addrman.size() == 33);
+
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() != "[::]:0");
+    addrman.ResolveCollisions();
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+}
+
+BOOST_AUTO_TEST_CASE(addrman_evictionworks)
+{
+    CAddrManTest addrman;
+
+    // Set addrman addr placement to be deterministic.
+    addrman.MakeDeterministic();
+
+    BOOST_CHECK(addrman.size() == 0);
+
+    // Empty addrman should return blank addrman info.
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+
+    // Add twenty two addresses.
+    CNetAddr source = ResolveIP("252.2.2.2");
+    for (unsigned int i = 1; i < 23; i++) {
+        CService addr = ResolveService("250.1.1."+std::to_string(i));
+        addrman.Add(CAddress(addr, NODE_NONE), source);
+        addrman.Good(addr);
+
+        // No collision yet.
+        BOOST_CHECK(addrman.size() == i);
+        BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+    }
+
+    // Collision between 23 and 19.
+    CService addr = ResolveService("250.1.1.23");
+    addrman.Add(CAddress(addr, NODE_NONE), source);
+    addrman.Good(addr);
+
+    BOOST_CHECK(addrman.size() == 23);
+    CAddrInfo info = addrman.SelectTriedCollision();
+    BOOST_CHECK(info.ToString() == "250.1.1.19:0");
+
+    // Ensure test of address fails, so that it is evicted.
+    addrman.SimConnFail(info);
+
+    // Should swap 23 for 19.
+    addrman.ResolveCollisions();
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+
+    // If 23 was swapped for 19, then this should cause no collisions.
+    addrman.Add(CAddress(addr, NODE_NONE), source);
+    addrman.Good(addr);
+
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+
+    // If we insert 19 is should collide with 23.
+    CService addr19 = ResolveService("250.1.1.19");
+    addrman.Add(CAddress(addr19, NODE_NONE), source);
+    addrman.Good(addr19);
+
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "250.1.1.23:0");
+
+    addrman.ResolveCollisions();
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+}
+
+
 BOOST_AUTO_TEST_SUITE_END()