Characterize Memory Usage for Keyed Variants

[SergioBenitez]

Hello!

Thank you for implementing this!

A common rate limiting scenario in the HTTP world involves keyed limiting based on IP addresses. The keyed variants in this crate look like a great tool to implement this, wherein the key would be the IP address. However, I'm worried that this route would make it somewhat trivial to DoS a server by exhausting its memory usage.

The specific scenario I'm worried about is an attacker controlling many IP address and issuing requests which go through the rate limiting code. The code path would mean that the key is looked up/stored by the rate limiter. If keys are stored and never cleared, then each IP address increases memory usage by at least 4 bytes, or for a savvy attacker, at least 16. After only 2B requests, the attacker will have forced usage of at least 32GiB of memory (or just 62M to consume 1GiB). A /64 IPv6 range contains way more than 2B IPs, so this attack is trivially mountable.

What recourse exists in this crate to prevent this from happening? Does calling retain_recent() and shrink_to_fit() periodically alleviate the concern? Or is there something else than can be done externally?

Thanks!

[antifuchs]

Hi, that's a great question! So if you're the victim of a DDoS attack with many, rapidly-changing IP addresses, I think you will find your worst fears confirmed: An attacker will be able to consume as much memory in a keyed rate limiter as they like. (Especially if they can use IPv6 addresses!)

You can and should absolutely call retain_recent and shrink_to_fit to get some memory back after the attack is over, but it won't help you while it's going on.

If this kind of DDoS attack is a concern, one thing that might help right now is to hash the IP addresses into a fixed number of buckets (however many you're willing to sacrifice in terms of memory) and then put that as a keyed rate-limiter (with a high-enough quota to support however many customers you expect) in front of the keyed-by-IP rate limiter.

One extension to governor that might be cool is a method that checks whether a key already exists in the rate limiter state; then you could check if an IP address is known already, and if not rate-limit its creation; if too many new IPs show up (as in a DDoS attack, or a particularly successful product release), you could automatically reject them.

[antifuchs]

I made #172 for this purpose, do you think this would help? A keyed check with a DDoS guard would be like:

let keyed_limiter = RateLimiter::dashmap(Quota::per_second(nonzero!(20))); // your existing limiter
let key_limiter = RateLimiter::direct(Quota::per_minute(nonzero!(1000_u32))); // a new one, controlling memory usage.

loop {
    let request = accept_request();
    if !keyed_limiter.contains_key(request.origin_ip) {
        if let Err(_) = key_limiter.check() {
            request.deny();
            continue;
        }
    }
    // at this point, we're ok to check the key:
    if let Ok(_) = keyed_limiter.check_key(request.origin_ip) {
        // handle the request!
    } else {
        request.deny():
        continue;
    }
}

[SergioBenitez]

Note that this doesn't need to be a DDoS attack in the sense that you need multiple machines: a single machine with an IPv6 address range is sufficient to carry out the attack. What's more, no actual attack is required to illustrate the issue: a service with moderate memory limits that runs for a sufficiently long time with a sufficiently large variance in request IP sources will eventually crash. This is effectively a remote-controlled memory leak.

The proposed idea in #172 prolongs the uptime of an affected server, but it doesn't resolve the issue. Memory still grows without bound, albeit more slowly. For a fix to be considered correct, it needs to bound memory usage.

A solution I'm experimenting with is to periodically atomically swap out the rate limiter for a fresh one, deallocating the old one in the process. This bounds memory to MAX_REQ_RATE * SWAP_PERIOD * SPACE_PER_KEY. Knowing the value of MAX_REQ_RATE is difficult, but conservative estimates are simple and viable, and one can always use a third (unkeyed) rate limiter to guarantee the rate.

A straight-forward implementation of this idea has the downside that it implicitly enables bursty limiting even when undesired. Specifically, referring to the "leaky bucket" analogy, when a swap occurs, all buckets are emptied, so any new checks will pass when they would have failed had a swap not occurred. This can be resolved by migrating state as necessary to the new limiter, but that complicates the implementation, and at least for use-cases I can consider, is unnecessary.

It would be fantastic to be able to control memory usage for keyed variants in the library directly, either via the idea I propose here, or via having greater control of the hash-map and evicting stale/old key/value pairs as needed.

[SergioBenitez]

You can and should absolutely call retain_recent and shrink_to_fit to get some memory back after the attack is over, but it won't help you while it's going on.

It should help while an attack is proceeding as well, assuming the time frame of the attack is >>> than the period these methods are called and the rate limiting periods. Empirically speaking, however, I have observed little to no memory savings by calling these methods both periodically as well as after bombardment has concluded.

[SergioBenitez]

After a bit more testing, it looks like calling retain_recent() and shrink_to_fit(), in that order, periodically, does indeed suffice! It performs slightly worse that the atomic swap idea above, presumably because the map is locked which these calls are happening whereas the technique above can clear memory in parallel, but memory is indeed bounded. Closing this issue.

[antifuchs]

Ah! Great to know that it works for you. Your point about memory growth still being a problem if there's a user-chosen key attack is very valid: You'll definitely want to call retain_recent and shrink_to_fit regularly, even if the key number growth is bounded.

Do you think the contains_key change is useful regardless? If not, I might just leave it out for now.