Add test-before-evict discipline to addrman

Changes addrman to use the test-before-evict discipline in which an
address is to be evicted from the tried table is first tested and if
it is still online it is not evicted.

Adds tests to provide test coverage for this change.

This change was suggested as Countermeasure 3 in
Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman,
Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report
2015/263. March 2015.

4 files changed, 319 insertions, 19 deletions

diff --git a/src/addrman.cpp b/src/addrman.cpp
index 9eefffb45b..9a7fad4900 100644
--- a/src/addrman.cpp
+++ b/src/addrman.cpp
@@ -187,7 +187,7 @@ void CAddrMan::MakeTried(CAddrInfo& info, int nId)
     info.fInTried = true;
 }
 
-void CAddrMan::Good_(const CService& addr, int64_t nTime)
+void CAddrMan::Good_(const CService& addr, bool test_before_evict, int64_t nTime)
 {
     int nId;
 
@@ -233,10 +233,22 @@ void CAddrMan::Good_(const CService& addr, int64_t nTime)
     if (nUBucket == -1)
         return;
 
-    LogPrint(BCLog::ADDRMAN, "Moving %s to tried\n", addr.ToString());
+    // which tried bucket to move the entry to
+    int tried_bucket = info.GetTriedBucket(nKey);
+    int tried_bucket_pos = info.GetBucketPosition(nKey, false, tried_bucket);
+
+    // Will moving this address into tried evict another entry?
+    if (test_before_evict && (vvTried[tried_bucket][tried_bucket_pos] != -1)) {
+        LogPrint(BCLog::ADDRMAN, "addrman", "Collision inserting element into tried table, moving %s to m_tried_collisions=%d\n", addr.ToString(), m_tried_collisions.size());
+        if (m_tried_collisions.size() < ADDRMAN_SET_TRIED_COLLISION_SIZE) {
+            m_tried_collisions.insert(nId);
+        }
+    } else {
+        LogPrint(BCLog::ADDRMAN, "Moving %s to tried\n", addr.ToString());
 
-    // move nId to the tried tables
-    MakeTried(info, nId);
+        // move nId to the tried tables
+        MakeTried(info, nId);
+    }
 }
 
 bool CAddrMan::Add_(const CAddress& addr, const CNetAddr& source, int64_t nTimePenalty)
@@ -521,3 +533,82 @@ void CAddrMan::SetServices_(const CService& addr, ServiceFlags nServices)
 int CAddrMan::RandomInt(int nMax){
     return GetRandInt(nMax);
 }
+
+void CAddrMan::ResolveCollisions_()
+{
+    for (std::set<int>::iterator it = m_tried_collisions.begin(); it != m_tried_collisions.end();) {
+        int id_new = *it;
+
+        bool erase_collision = false;
+
+        // If id_new not found in mapInfo remove it from m_tried_collisions
+        if (mapInfo.count(id_new) != 1) {
+            erase_collision = true;
+        } else {
+            CAddrInfo& info_new = mapInfo[id_new];
+
+            // Which tried bucket to move the entry to.
+            int tried_bucket = info_new.GetTriedBucket(nKey);
+            int tried_bucket_pos = info_new.GetBucketPosition(nKey, false, tried_bucket);
+            if (!info_new.IsValid()) { // id_new may no longer map to a valid address
+                erase_collision = true;
+            } else if (vvTried[tried_bucket][tried_bucket_pos] != -1) { // The position in the tried bucket is not empty
+
+                // Get the to-be-evicted address that is being tested
+                int id_old = vvTried[tried_bucket][tried_bucket_pos];
+                CAddrInfo& info_old = mapInfo[id_old];
+
+                // Has successfully connected in last X hours
+                if (GetAdjustedTime() - info_old.nLastSuccess < ADDRMAN_REPLACEMENT_HOURS*(60*60)) {
+                    erase_collision = true;
+                } else if (GetAdjustedTime() - info_old.nLastTry < ADDRMAN_REPLACEMENT_HOURS*(60*60)) { // attempted to connect and failed in last X hours
+
+                    // Give address at least 60 seconds to successfully connect
+                    if (GetAdjustedTime() - info_old.nLastTry > 60) {
+                        LogPrint(BCLog::ADDRMAN, "addrman", "Swapping %s for %s in tried table\n", info_new.ToString(), info_old.ToString());
+
+                        // Replaces an existing address already in the tried table with the new address
+                        Good_(info_new, false, GetAdjustedTime());
+                        erase_collision = true;
+                    }
+                }
+            } else { // Collision is not actually a collision anymore
+                Good_(info_new, false, GetAdjustedTime());
+                erase_collision = true;
+            }
+        }
+
+        if (erase_collision) {
+            m_tried_collisions.erase(it++);
+        } else {
+            it++;
+        }
+    }
+}
+
+CAddrInfo CAddrMan::SelectTriedCollision_()
+{
+    if (m_tried_collisions.size() == 0) return CAddrInfo();
+
+    std::set<int>::iterator it = m_tried_collisions.begin();
+
+    // Selects a random element from m_tried_collisions
+    std::advance(it, GetRandInt(m_tried_collisions.size()));
+    int id_new = *it;
+
+    // If id_new not found in mapInfo remove it from m_tried_collisions
+    if (mapInfo.count(id_new) != 1) {
+        m_tried_collisions.erase(it);
+        return CAddrInfo();
+    }
+
+    CAddrInfo& newInfo = mapInfo[id_new];
+
+    // which tried bucket to move the entry to
+    int tried_bucket = newInfo.GetTriedBucket(nKey);
+    int tried_bucket_pos = newInfo.GetBucketPosition(nKey, false, tried_bucket);
+
+    int id_old = vvTried[tried_bucket][tried_bucket_pos];
+
+    return mapInfo[id_old];
+}
diff --git a/src/addrman.h b/src/addrman.h
index 38da754afb..67423c6c55 100644
--- a/src/addrman.h
+++ b/src/addrman.h
@@ -165,6 +165,9 @@ public:
 //! ... in at least this many days
 #define ADDRMAN_MIN_FAIL_DAYS 7
 
+//! how recent a successful connection should be before we allow an address to be evicted from tried
+#define ADDRMAN_REPLACEMENT_HOURS 4
+
 //! the maximum percentage of nodes to return in a getaddr call
 #define ADDRMAN_GETADDR_MAX_PCT 23
 
@@ -176,6 +179,9 @@ public:
 #define ADDRMAN_NEW_BUCKET_COUNT (1 << ADDRMAN_NEW_BUCKET_COUNT_LOG2)
 #define ADDRMAN_BUCKET_SIZE (1 << ADDRMAN_BUCKET_SIZE_LOG2)
 
+//! the maximum number of tried addr collisions to store
+#define ADDRMAN_SET_TRIED_COLLISION_SIZE 10
+
 /** 
  * Stochastical (IP) address manager 
  */
@@ -212,6 +218,9 @@ private:
     //! last time Good was called (memory only)
     int64_t nLastGood;
 
+    //! Holds addrs inserted into tried table that collide with existing entries. Test-before-evict discpline used to resolve these collisions.
+    std::set<int> m_tried_collisions;
+
 protected:
     //! secret key to randomize bucket select with
     uint256 nKey;
@@ -239,7 +248,7 @@ protected:
     void ClearNew(int nUBucket, int nUBucketPos);
 
     //! Mark an entry "good", possibly moving it from "new" to "tried".
-    void Good_(const CService &addr, int64_t nTime);
+    void Good_(const CService &addr, bool test_before_evict, int64_t time);
 
     //! Add an entry to the "new" table.
     bool Add_(const CAddress &addr, const CNetAddr& source, int64_t nTimePenalty);
@@ -250,6 +259,12 @@ protected:
     //! Select an address to connect to, if newOnly is set to true, only the new table is selected from.
     CAddrInfo Select_(bool newOnly);
 
+    //! See if any to-be-evicted tried table entries have been tested and if so resolve the collisions.
+    void ResolveCollisions_();
+
+    //! Return a random to-be-evicted tried table address.
+    CAddrInfo SelectTriedCollision_();
+
     //! Wraps GetRandInt to allow tests to override RandomInt and make it determinismistic.
     virtual int RandomInt(int nMax);
 
@@ -537,11 +552,11 @@ public:
     }
 
     //! Mark an entry as accessible.
-    void Good(const CService &addr, int64_t nTime = GetAdjustedTime())
+    void Good(const CService &addr, bool test_before_evict = true, int64_t nTime = GetAdjustedTime())
     {
         LOCK(cs);
         Check();
-        Good_(addr, nTime);
+        Good_(addr, test_before_evict, nTime);
         Check();
     }
 
@@ -554,6 +569,28 @@ public:
         Check();
     }
 
+    //! See if any to-be-evicted tried table entries have been tested and if so resolve the collisions.
+    void ResolveCollisions()
+    {
+        LOCK(cs);
+        Check();
+        ResolveCollisions_();
+        Check();
+    }
+
+    //! Randomly select an address in tried that another address is attempting to evict.
+    CAddrInfo SelectTriedCollision()
+    {
+        CAddrInfo ret;
+        {
+            LOCK(cs);
+            Check();
+            ret = SelectTriedCollision_();
+            Check();
+        }
+        return ret;
+    }
+
     /**
      * Choose an address to connect to.
      */
diff --git a/src/net.cpp b/src/net.cpp
index 201914685c..e08ce0fd33 100644
--- a/src/net.cpp
+++ b/src/net.cpp
@@ -1824,11 +1824,18 @@ void CConnman::ThreadOpenConnections(const std::vector<std::string> connect)
             }
         }
 
+        addrman.ResolveCollisions();
+
         int64_t nANow = GetAdjustedTime();
         int nTries = 0;
         while (!interruptNet)
         {
-            CAddrInfo addr = addrman.Select(fFeeler);
+            CAddrInfo addr = addrman.SelectTriedCollision();
+
+            // SelectTriedCollision returns an invalid address if it is empty.
+            if (!fFeeler || !addr.IsValid()) {
+                addr = addrman.Select(fFeeler);
+            }
 
             // if we selected an invalid address, restart
             if (!addr.IsValid() || setConnected.count(addr.GetGroup()) || IsLocal(addr))
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()