Ban socket addresses not sending a valid connection ID

[josecelano]

From: torrust/torrust-demo#14
Relates to: #1033

We are having problems with the tracker demo. The logs contain many errors validating the connection ID. It looks like the client doesn't implement the protocol correctly because it's not sending the connection ID received from the connect request. Since the client is making many requests, this produces a lot of new ERROR records in the logs, ultimately depressing tracker performance.

Solution Overview:

1. Hierarchical Counting Bloom Filters:

   • Individual IP Layer: Use one CBF to track individual IP addresses. This will allow for fine-grained detection of misbehaving IPs.

   • Subnet Layer: Implement another level of CBFs where each filter covers a subnet range. This allows for detecting patterns of misbehavior across a subnet without penalizing neighboring IPs inappropriately.

Implementation Details:

• Individual IP CBF:

  • Each IP address is hashed into this filter.
  • When an error occurs, increment the count associated with that IP's hash in the CBF.
  • If the count exceeds a threshold, you can take action against that specific IP (e.g., rate limiting or temporary banning).

• Subnet CBF:

  • Instead of hashing individual IPs, hash the subnet address (e.g., the network part of an IP address).
  • When multiple IPs within a subnet misbehave, their errors are aggregated into this subnet's count.
  • If the count for a subnet exceeds a different, higher threshold, you can apply measures at the subnet level, like rate limiting traffic from that subnet.

Advantages:

• Granularity: This approach gives you both detailed control over individual IPs and the ability to detect broader patterns of misbehavior within subnets.

• Performance: CBFs are efficient in terms of memory usage and speed, allowing for quick lookups and updates even with large datasets.

• Flexibility: You can adjust the thresholds for individual IPs and subnets separately, allowing for different levels of tolerance based on your policy or observed behavior patterns.

• False Positives: While CBFs have a small chance of false positives, by using multiple levels (individual and subnet), you can mitigate the impact. For example, if an IP is flagged at both levels, it's more likely to be a true positive.

Challenges:

• Configuration: You need to decide on the size of the CBFs, the number of hash functions, and the error thresholds for both individual IPs and subnets. This requires some experimentation or simulation to find the right balance between false positives, memory usage, and effectiveness.

• Complexity: Managing two layers of CBFs introduces additional complexity in terms of implementation and maintenance.

• False Positives at Subnet Level: If a subnet contains both misbehaving and well-behaving IPs, the well-behaving ones might suffer from the actions taken against the subnet.

Implementation Steps:

1. Decide on the Subnet Size: Determine what constitutes a subnet for your purposes (e.g., /24, /16, etc.).

2. Initialize CBFs:

   • Create one CBF for individual IPs.
   • Create another CBF for subnets, where each bucket represents a subnet.

3. Error Handling Logic:

   • When an error occurs:
     • Hash the IP to update the individual IP CBF.
     • Extract the subnet from the IP and hash it to update the subnet CBF.

4. Action Protocol:

   • If an individual IP's count exceeds a threshold, apply rate limiting or other measures to that IP.
   • If a subnet's count exceeds a higher threshold, consider similar measures but at the subnet level.

5. Decay Mechanism: Implement a decay or aging process for counts to ensure that past behavior doesn't indefinitely affect current interactions unless the behavior persists.

By employing this hierarchical approach with Counting Bloom Filters, you can effectively manage IP-based errors at different levels of granularity, protecting your network's performance while minimizing the impact on innocent IPs.

Originally posted by @da2ce7 in torrust/torrust-demo#14 (comment)

[josecelano]

Hi @da2ce7 I guess you proposed a Counting Bloom Filters mainly because:

• We can have too many misbehaving clients.
• Time needed either to add items or to check whether an item is in the set is a fixed constant, O(k).
• They consume less memory than other alternatives.

Notes

• There are many implementations in Rust: https://www.reddit.com/r/rust/comments/10y9t9v/there_are_87_bloom_filter_crates_strategies_for/
• Xor Filters can't be used because they don't allow adding new entries without rebuilding.
• Cuckoo Filters don't support counting natively.

Preliminary research

Crates containing Counting Bloom Filters:

• https://github.com/yankun1992/fastbloom
• https://github.com/nicklan/bloom-rs
• https://github.com/nervosnetwork/bloom-filters

Crates apparently not containing Counting Bloom Filters:

• https://github.com/tomtomwombat/fastbloom/
• https://github.com/sile/scalable_cuckoo_filter
• https://github.com/domodwyer/bloom2
• https://github.com/jedisct1/rust-bloom-filter
• https://github.com/dpbriggs/growable-bloom-filters
• https://github.com/arthurprs/qfilter

Some explanations:

• Build your own Counting Bloom Filter in Rust
• Learning Rust - Implementing a bloom filter
• What are Counting Bloom Filters? — Python Implementation
• Modern Bloom Filters: 22x Faster!

Papers:

• countBF: A General-purpose High Accuracy and
  Space Efficient Counting Bloom Filter
• Ultra-Fast Bloom Filters using SIMD Techniques
• False Negative Problem of Counting Bloom Filter

[josecelano]

Here's a comparison of three Rust crates that implement Counting Bloom Filters:

Crate Name	GitHub Stars	Number of Contributors	Initial Release Date	Latest Commit Date	Crates.io Downloads	Used by	Notable Users
fastbloom	86	2	2 years ago	December 2023 (crate updated 1 year ago)	66,454	N/A	N/A
bloom	26	1	10 years ago	Sep 2016 (crate updated 8 years ago)	540,063	N/A	N/A
bloom-filters	7	4	6 years ago	Jun 2021 (crate updated over 3 years ago)	203,647	292	Nervos Network

Notes:

• fastbloom: A fast Bloom filter implemented in Rust, with Python bindings available. It supports both standard and counting Bloom filters.

• bloom-rs: Provides standard and counting Bloom filters. Last updated in 2016, indicating potential lack of recent maintenance.

• bloom-filters: A fast Bloom filter implementation in Rust, primarily maintained by the Nervos Network team.

Data is based on available information as of December 2024.

[josecelano]

Hi @da2ce7 I think I'm going to implement it in two phases, first the IPs and then the subnets. I will probably use the bloom-filters crate.

NOTES/QUESTIONS:

• I think it will be hard to find a good size for the subnet in the subnet filter. I guess you wanted to introduce this level to avoid DoS attacks and not only bad client implementations. Maybe you are assuming all those bad implementations are actually attacks. Is there a reason why an attacker could use many IPs in the same subnet? I'm trying to understand why this would be effective without banning many false positives.
• Should we use socket addresses instead of IPs? I don't think so.

[josecelano]

Hi @da2ce7, I've implemented the minimal solution here.

When should we unban an IP?

I think we can unban all IPs every 24 hours (cbf.clear();). We can wrap the filter with a type that resets the inner CBF (deletes it and creates a new one) every 24 hours. What do you think?

I have more questions in my previous comment ☝🏼.

[josecelano]

Today, we discussed this issue in our weekly meeting.

@da2ce7 said the false negatives rate is too high. @da2ce7 I forgot to mention that you can set the rate:

The frequency of false positives can be preciecly bounded by setting the size of the filter, and is called the False Positive Rate.

See https://docs.rs/bloom/latest/bloom/index.html#bloom-filters.

@da2ce7 also commented there is an open issue for a long time about the high False-positive rate:

• False-positive rate much higher due to broken HashIter implementation nicklan/bloom-rs#2

We were also considering using another crate that I discarded because It does not have an implementation for a Counting Bloom Filter. The crate:

https://github.com/tomtomwombat/fastbloom

NOTE: It has the same name as the other one I was analyzing, but they are actually two different packages:

• https://github.com/yankun1992/fastbloom (https://crates.io/crates/fastbloom-rs)
• https://github.com/tomtomwombat/fastbloom (https://crates.io/crates/fastbloom)

I've opened a new issue to ask them for their plans to add a Counting Bloom Filter feature.

We also discussed alternative implementations to remove false positives. I will describe the solution in a new comment.

[josecelano]

1. Alternative Implementation: Two-Tiered Approach

The basic idea is to use the CBF just as a fast filter to detect potencial bad actors. If the counter for an IP goes over a threshold, we don't ban the IP directly. Instead, we add the IP to a reliable secondary list with a HashMap.

Counting Bloom Filter as a Fast Filter:

• Use the CBF to estimate potential misbehaving IPs quickly.
• Increment the counter in the CBF for each bad request from an IP.
• When the counter for an IP exceeds 10 in the CBF, move that IP to a more reliable structure for precise counting.

Reliable Backend Structure:

• Use a HashMap (or another reliable key-value store) for precise counting of IPs that are flagged as misbehaving by the CBF.
• In the HashMap, count up to 10 precise errors and only ban the IP when the count reaches 10.
• Once an IP is banned, you no longer need to query it in the HashMap (or the CBF), which helps reduce the overhead.

False Positive Handling:

• False positives in the CBF will only lead to lookups in the HashMap but will not result in incorrect bans.
• This ensures no false negatives because the actual banning decision is always based on the precise counts in the HashMap.

Unban Handling:

• We can remove IPs from the HashMap periodically or after a period for that concrete IP. We can include a timestamp for when the ban started.

Pros

• No false positives. No client is banned accidentally.

Cons

• For potentially misbehaving IPS, we have to double check it, by accessing two data structures. I wonder if that wouldn't be more costly than just replying with the error message. In the end, we don't even need to get data from the main torrent repository, which is, I think, one of the main bottlenecks.
• If there are many bad actors, that can lead to another type of attack: memory consumption. But that's a problem we have anyway for normal requests.

Questions

• When should we clean the CBF? I think @da2ce7 proposed not to clean it because the bucket might contain more than one IP.
• @da2ce7 I think this was not exactly your idea because you mentioned something about the IP hash. Could you correct this description of the implementation?

[josecelano]

In the new implementation add a new metric to tracker stats for the number of banned IPs.