[addrman, net] Ensure tried collisions resolve, and allow feeler connections to existing outbound netgroups #15486

sdaftuar · 2019-02-26T20:29:47Z

The restriction on outbound peers sharing the same network group is not intended to apply to feeler connections, so fix this.

This fixes an issue where a tried table collision with an entry to a netgroup we already have an outbound connection to could cause feelers to stop working, because the tried collision buffer (m_tried_collisions) would never be drained.

Also, ensure that all entries don't linger in m_tried_collisions by evicting an old entry if its collisions is unresolved after 40 minutes.

sdaftuar · 2019-02-26T20:31:48Z

I think this should resolve #15484, but it's not clear to me if this is entirely sufficient to protect against the class of error, or if we should add additional logic to ResolveCollisions() to ensure that collisions get eventually resolved.

DrahtBot · 2019-02-26T21:37:11Z

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

Conflicts

No conflicts as of last run.

sdaftuar · 2019-02-26T21:39:01Z

Updated with a commit that tries to fix the underlying problem in addrman, by doing eviction anyway after 20 minutes (to prevent m_tried_collisions from never being drained).

If it looks good, I'll update the OP of this PR before merge.

gmaxwell · 2019-02-26T22:43:29Z

This bugfix should probably get tagged for 0.18.

Fixes a bug where feelers could be stuck trying to resolve a collision in the tried table that is to an address in the same netgroup as an existing outbound peer. Thanks to Muoi Tran for the original bug report and detailed debug logs to track this down.

src/addrman.h

After 40 minutes, time out a test-before-evict entry and just evict without testing. Otherwise, if we were unable to test an entry for some reason, we might break using feelers altogether.

sipa · 2019-02-28T00:53:35Z

utACK f71fdda

src/addrman.cpp

Sjors · 2019-03-01T16:18:47Z

Useful background info for context:

Eclipse Attacks on Bitcoin’s Peer-to-Peer Network" https://eprint.iacr.org/2015/263.pdf (by @EthanHeilman e.a.
net: Feeler connections to increase online addrs in the tried table. #8282
net: Add test-before-evict discipline to addrman #9037

Sjors

utACK f71fdda, but would be nice to have a test that demonstrates the original bug.

As @sipa suggested a few years ago, let's put a link to that paper in a comment somewhere.

src/addrman.cpp

src/net.cpp

sdaftuar · 2019-03-01T21:18:00Z

Addressed nits.

gmaxwell · 2019-03-01T23:23:00Z

utACK

Sjors · 2019-03-02T10:48:05Z

To clarify what I brought up inline:

bitcoin/src/addrman.cpp

Lines 240 to 253 in 20e6ea2

    
           // Will moving this address into tried evict another entry? 
        
           if (test_before_evict && (vvTried[tried_bucket][tried_bucket_pos] != -1)) { 
        
               // Output the entry we'd be colliding with, for debugging purposes 
        
               auto colliding_entry = mapInfo.find(vvTried[tried_bucket][tried_bucket_pos]); 
        
               LogPrint(BCLog::ADDRMAN, "Collision inserting element into tried table (%s), moving %s to m_tried_collisions=%d\n", colliding_entry != mapInfo.end() ? colliding_entry->second.ToString() : "", 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); 
        
           }

The log statement says we're moving it to m_tried_collisions, but that's not true if that's full. Hence my suggestion to move the log statement inside the if statement (line 245).

For the case m_tried_collisions is full @sdaftuar wrote:

I don't think it's quite as simple as "when in doubt, don't evict". I think in the case of a collision we bias ourselves towards not evicting, unless the peer we might evict can't be connected to via feeler connection.

My thought is that if m_tried_collisions is ever full, it seems like that is a scenario where we may be under attack; so not replacing things in our tried table (which we assume to have some good peers in it) is safe, even if not optimal. Maybe @EthanHeilman or @gmaxwell has a better intuition for how this works though.

And @EthanHeilman replied:

I agree with your intuition.

We bias toward not evicting. The assumption is that if the tried table is contains many evil IPs we have already lost and won't hear about good IPs. Thus, we assume the tried has many good IPs and that they should not be evicted unless a particular IP in tried is offline and thus no longer provides security.

But a few lines down it seems we're doing the opposite, namely bias ourselves towards evicting:

bitcoin/src/addrman.cpp

Lines 572 to 579 in 20e6ea2

    
           } else if (GetAdjustedTime() - info_new.nLastSuccess > ADDRMAN_TEST_WINDOW) { 
        
               // If the collision hasn't resolved in some reasonable amount of time, 
        
               // just evict the old entry -- we must not be able to 
        
               // connect to it for some reason. 
        
               LogPrint(BCLog::ADDRMAN, "Unable to test; replacing %s with %s in tried table anyway\n", info_old.ToString(), info_new.ToString()); 
        
               Good_(info_new, false, GetAdjustedTime()); 
        
               erase_collision = true; 
        
           }

We don't know anything about this new entry, because we couldn't connect, so it seems to me it would be more consistent to keep the old entry.

It's still much better than getting stuck of course, so utACK 20e6ea2.

gmaxwell · 2019-03-02T14:14:29Z

We don't know anything about this new entry,

When we insert the new entry in tried in the first place, it's because we've actually tried it. When inserting it we may find that it causes us to want to evict an old tried entry (which has also been tried, but not as recently). What the code is supposed to do (post try before evict) is to test the old tried entry before evicting it, in order to give it a second chance to stay around iff its still connectible.

Sjors · 2019-03-02T14:55:54Z

Ah, I think I get it now... since we don't specifically track when things were added to m_tried_collisions, the check info_new.nLastSuccess > ADDRMAN_TEST_WINDOW is just the way we determine when the entry was added to the new table, which coincides with the time we last heard from it, i.e. when it last sent us a version message. And that's also when it's added to m_tried_collisions.

If we receive a version message:

bitcoin/src/net_processing.cpp

Line 1765 in 20e6ea2

if (strCommand == NetMsgType::VERSION) {

From an outbound node:

bitcoin/src/net_processing.cpp

Line 1885 in 20e6ea2

if (!pfrom->fInbound)

That's when we call MarkAddressGood in net.cpp which in turn calls CAddrMan::Good_, which adds it to m_tried_collisions.

sdaftuar · 2019-03-02T16:39:30Z

Ah, I think I get it now... since we don't specifically track when things were added to m_tried_collisions, the check info_new.nLastSuccess > ADDRMAN_TEST_WINDOW is just the way we determine when the entry was added to the new table

That's not necessarily when the entry was added to the new table -- we can do that when learning about an address, for instance when relayed to us via an addr message from another peer. But otherwise I think your description is correct (in particular, that should be the time that we attempted to put it in the tried table but discovered the collision).

naumenkogs · 2019-03-04T20:25:21Z

utACK

sdaftuar · 2019-03-06T21:45:50Z

I think this is ready to go -- anything left that I missed?

laanwj · 2019-03-09T06:12:13Z

utACK 20e6ea2

…ow feeler connections to existing outbound netgroups 20e6ea2 [addrman] Improve collision logging and address nits (Suhas Daftuar) f71fdda [addrman] Ensure collisions eventually get resolved (Suhas Daftuar) 4991e3c [net] feeler connections can be made to outbound peers in same netgroup (Suhas Daftuar) 4d83401 [addrman] Improve tried table collision logging (Suhas Daftuar) Pull request description: The restriction on outbound peers sharing the same network group is not intended to apply to feeler connections, so fix this. This fixes an issue where a tried table collision with an entry to a netgroup we already have an outbound connection to could cause feelers to stop working, because the tried collision buffer (`m_tried_collisions`) would never be drained. Also, ensure that all entries don't linger in `m_tried_collisions` by evicting an old entry if its collisions is unresolved after 40 minutes. Tree-SHA512: 553fe2b01b82cd7f0f62f90c6781e373455a45b254e3bec085b5e6b16690aa9f3938e8c50e7136f19dafa250ed4578a26227d944b76daf9ce4ef0c75802389b6

Github-Pull: bitcoin#15486 Rebased-From: 4d83401

Fixes a bug where feelers could be stuck trying to resolve a collision in the tried table that is to an address in the same netgroup as an existing outbound peer. Thanks to Muoi Tran for the original bug report and detailed debug logs to track this down. Github-Pull: bitcoin#15486 Rebased-From: 4991e3c

After 40 minutes, time out a test-before-evict entry and just evict without testing. Otherwise, if we were unable to test an entry for some reason, we might break using feelers altogether. Github-Pull: bitcoin#15486 Rebased-From: f71fdda

Github-Pull: bitcoin#15486 Rebased-From: 20e6ea2

fanquake · 2019-03-09T07:07:45Z

~~Backported in #15563.~~

Done by @laanwj in f810f14...b80dedb.

Github-Pull: #15486 Rebased-From: 4d83401 Tree-SHA512: c7843191c470d8b3298d4375632ddbcfd26358d21100bcbffa8d40498782f9dfef08cfb7b3c040525ef912b27ddd593322b60f8f21e16e2ae9bae66433ce807e

Fixes a bug where feelers could be stuck trying to resolve a collision in the tried table that is to an address in the same netgroup as an existing outbound peer. Thanks to Muoi Tran for the original bug report and detailed debug logs to track this down. Github-Pull: #15486 Rebased-From: 4991e3c Tree-SHA512: 2752c9909d55ff63b9143168033d0d3952effba7f911181919eb62291edf822ec54fffbb20e35b5c5f8cb1092d75c496665da00139dbebe5ce402cbea3ad87c5

After 40 minutes, time out a test-before-evict entry and just evict without testing. Otherwise, if we were unable to test an entry for some reason, we might break using feelers altogether. Github-Pull: #15486 Rebased-From: f71fdda Tree-SHA512: 66c61a9f030b1666e98e4fe66dd6cfc5f1d03b2a1ec01567b195903db6e4412ac778f4464ee9ef35ae6faa1ab7e4b18ef7ecb9a7ced29e6494046990aebf7b76

Github-Pull: #15486 Rebased-From: 20e6ea2 Tree-SHA512: 73b37a98cf4d9ede1d39c30d178d63a5a6865dba6cb7a9f33bd1e03445acb708b3007c7cde991b5de96a407262adda23279fe7a1d2ed31b0b5a33b2e97aaba9b

Github-Pull: bitcoin#15486 Rebased-From: 4d83401 Tree-SHA512: c7843191c470d8b3298d4375632ddbcfd26358d21100bcbffa8d40498782f9dfef08cfb7b3c040525ef912b27ddd593322b60f8f21e16e2ae9bae66433ce807e

Fixes a bug where feelers could be stuck trying to resolve a collision in the tried table that is to an address in the same netgroup as an existing outbound peer. Thanks to Muoi Tran for the original bug report and detailed debug logs to track this down. Github-Pull: bitcoin#15486 Rebased-From: 4991e3c Tree-SHA512: 2752c9909d55ff63b9143168033d0d3952effba7f911181919eb62291edf822ec54fffbb20e35b5c5f8cb1092d75c496665da00139dbebe5ce402cbea3ad87c5

After 40 minutes, time out a test-before-evict entry and just evict without testing. Otherwise, if we were unable to test an entry for some reason, we might break using feelers altogether. Github-Pull: bitcoin#15486 Rebased-From: f71fdda Tree-SHA512: 66c61a9f030b1666e98e4fe66dd6cfc5f1d03b2a1ec01567b195903db6e4412ac778f4464ee9ef35ae6faa1ab7e4b18ef7ecb9a7ced29e6494046990aebf7b76

Github-Pull: bitcoin#15486 Rebased-From: 20e6ea2 Tree-SHA512: 73b37a98cf4d9ede1d39c30d178d63a5a6865dba6cb7a9f33bd1e03445acb708b3007c7cde991b5de96a407262adda23279fe7a1d2ed31b0b5a33b2e97aaba9b

…ow feeler connections to existing outbound netgroups Summary: 20e6ea259b222b10f066f22695a5f56c52071f63 [addrman] Improve collision logging and address nits (Suhas Daftuar) f71fdda3bc2e7acd2a8b74e882364866b8b0f55b [addrman] Ensure collisions eventually get resolved (Suhas Daftuar) 4991e3c813c9848d3b3957ea3ad433f02fca9e81 [net] feeler connections can be made to outbound peers in same netgroup (Suhas Daftuar) 4d834018e368c3481a5421891395f64aa9002185 [addrman] Improve tried table collision logging (Suhas Daftuar) Pull request description: The restriction on outbound peers sharing the same network group is not intended to apply to feeler connections, so fix this. This fixes an issue where a tried table collision with an entry to a netgroup we already have an outbound connection to could cause feelers to stop working, because the tried collision buffer (`m_tried_collisions`) would never be drained. Also, ensure that all entries don't linger in `m_tried_collisions` by evicting an old entry if its collisions is unresolved after 40 minutes. Tree-SHA512: 553fe2b01b82cd7f0f62f90c6781e373455a45b254e3bec085b5e6b16690aa9f3938e8c50e7136f19dafa250ed4578a26227d944b76daf9ce4ef0c75802389b6 Backport of Core [[bitcoin/bitcoin#15486 | PR15486]] This PR was in response to bitcoin/bitcoin#15484, but I did not find the issue mentioned [[ bitcoin/bitcoin#15484 (comment) | here ]] in my debug log while running master. Test Plan: ninja ninja check-all Reviewers: O1 Bitcoin ABC, #bitcoin_abc, jasonbcox, deadalnix Reviewed By: O1 Bitcoin ABC, #bitcoin_abc, jasonbcox, deadalnix Subscribers: jasonbcox Differential Revision: https://reviews.bitcoinabc.org/D6489

…eler connections to existing outbound netgroups ccb6a4a [addrman] Improve collision logging and address nits (Suhas Daftuar) aa3c805 [addrman] Ensure collisions eventually get resolved (Suhas Daftuar) efd1d6a [net] feeler connections can be made to outbound peers in same netgroup (Suhas Daftuar) afcffc4 [addrman] Improve tried table collision logging (Suhas Daftuar) Pull request description: Two pretty direct back ports for the address manager. Coming from bitcoin#13115 and bitcoin#15486. ACKs for top commit: random-zebra: rebase utACK ccb6a4a, and merging... Tree-SHA512: 89d42b3164f92fcee69bc981c7e0887cab09820088732297dbcadbf4ccfc3257e9564ef2b394205f3153c8a03e4c0a0e8145b1c291e8cd980dc06b0ffa65a28c

…and allow feeler connections to existing outbound netgroups 20e6ea2 [addrman] Improve collision logging and address nits (Suhas Daftuar) f71fdda [addrman] Ensure collisions eventually get resolved (Suhas Daftuar) 4991e3c [net] feeler connections can be made to outbound peers in same netgroup (Suhas Daftuar) 4d83401 [addrman] Improve tried table collision logging (Suhas Daftuar) Pull request description: The restriction on outbound peers sharing the same network group is not intended to apply to feeler connections, so fix this. This fixes an issue where a tried table collision with an entry to a netgroup we already have an outbound connection to could cause feelers to stop working, because the tried collision buffer (`m_tried_collisions`) would never be drained. Also, ensure that all entries don't linger in `m_tried_collisions` by evicting an old entry if its collisions is unresolved after 40 minutes. Tree-SHA512: 553fe2b01b82cd7f0f62f90c6781e373455a45b254e3bec085b5e6b16690aa9f3938e8c50e7136f19dafa250ed4578a26227d944b76daf9ce4ef0c75802389b6

[addrman] Improve tried table collision logging

4d83401

fanquake added the P2P label Feb 26, 2019

fanquake added this to the 0.18.0 milestone Feb 26, 2019

sdaftuar force-pushed the 2019-02-addrman-collisions branch from 2410d33 to 1b0621b Compare February 27, 2019 14:34

EthanHeilman reviewed Feb 27, 2019

View reviewed changes

src/addrman.h Outdated Show resolved Hide resolved

[addrman] Ensure collisions eventually get resolved

f71fdda

After 40 minutes, time out a test-before-evict entry and just evict without testing. Otherwise, if we were unable to test an entry for some reason, we might break using feelers altogether.

sdaftuar force-pushed the 2019-02-addrman-collisions branch from 1b0621b to f71fdda Compare February 27, 2019 21:54

naumenkogs reviewed Feb 28, 2019

View reviewed changes

src/addrman.cpp Outdated Show resolved Hide resolved

Sjors approved these changes Mar 1, 2019

View reviewed changes

src/addrman.cpp Show resolved Hide resolved

src/addrman.cpp Outdated Show resolved Hide resolved

src/net.cpp Outdated Show resolved Hide resolved

src/net.cpp Show resolved Hide resolved

[addrman] Improve collision logging and address nits

20e6ea2

sdaftuar mentioned this pull request Mar 1, 2019

Test coverage of our networking code #14210

Open

sdaftuar changed the title ~~[net] Allow feeler connections to go to the same netgroup as existing outbound peers~~ [addrman, net] Ensure tried collisions resolve, and allow feeler connections to existing outbound netgroups Mar 1, 2019

laanwj added the Needs backport label Mar 4, 2019

laanwj merged commit 20e6ea2 into bitcoin:master Mar 9, 2019

fanquake pushed a commit to fanquake/bitcoin that referenced this pull request Mar 9, 2019

[addrman] Improve tried table collision logging

ceb5ab3

Github-Pull: bitcoin#15486 Rebased-From: 4d83401

fanquake pushed a commit to fanquake/bitcoin that referenced this pull request Mar 9, 2019

[addrman] Improve collision logging and address nits

d6602c2

Github-Pull: bitcoin#15486 Rebased-From: 20e6ea2

fanquake mentioned this pull request Mar 9, 2019

backport: Ensure tried collisions resolve, and allow feeler connections to existing outbound netgroups #15563

Closed

fanquake removed the Needs backport label Mar 9, 2019

Sjors mentioned this pull request Mar 15, 2019

Don't query all DNS seeds at once #15558

Merged

adamjonas mentioned this pull request May 6, 2020

No feeler connection is made when our tip is stale #15484

Closed

furszy mentioned this pull request Mar 22, 2021

[Backport] Ensure tried collisions resolve, and allow feeler connections to existing outbound netgroups PIVX-Project/PIVX#2257

Merged

bitcoin locked as resolved and limited conversation to collaborators Dec 16, 2021

[addrman, net] Ensure tried collisions resolve, and allow feeler connections to existing outbound netgroups #15486

[addrman, net] Ensure tried collisions resolve, and allow feeler connections to existing outbound netgroups #15486

Uh oh!

Conversation

sdaftuar commented Feb 26, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sdaftuar commented Feb 26, 2019

Uh oh!

DrahtBot commented Feb 26, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

sdaftuar commented Feb 26, 2019

Uh oh!

gmaxwell commented Feb 26, 2019

Uh oh!

Uh oh!

sipa commented Feb 28, 2019

Uh oh!

Uh oh!

Sjors commented Mar 1, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Sjors left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

sdaftuar commented Mar 1, 2019

Uh oh!

gmaxwell commented Mar 1, 2019

Uh oh!

Sjors commented Mar 2, 2019

Uh oh!

gmaxwell commented Mar 2, 2019

Uh oh!

Sjors commented Mar 2, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sdaftuar commented Mar 2, 2019

Uh oh!

naumenkogs commented Mar 4, 2019

Uh oh!

sdaftuar commented Mar 6, 2019

Uh oh!

laanwj commented Mar 9, 2019

Uh oh!

fanquake commented Mar 9, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

9 participants

sdaftuar commented Feb 26, 2019 •

edited

Loading

DrahtBot commented Feb 26, 2019 •

edited

Loading

Sjors commented Mar 1, 2019 •

edited

Loading

Sjors left a comment •

edited

Loading

Sjors commented Mar 2, 2019 •

edited

Loading

fanquake commented Mar 9, 2019 •

edited

Loading