[ratelimits] Remarks regarding the Knot DNS 1.2.0 RRL implementation

[Marek Vavruša]

On 5 March 2013 20:27, Vernon Schryver <vjs at rhyolite.com> wrote:
>> From: =?UTF-8?Q?Marek_Vavru=C5=A1a?= <marek.vavrusa at nic.cz>
>
>
>> > For estimating collision rates, the seed, class, and qtype have a
>> > total of less than 3 bits of entropy, and so must be ignored along
>> > with the constants in the hash function.  At authoritative servers,
>> > the qname also limited entropy.  At a server authoritative for 1000
>> > domains, the entropy of the qname is only 10 bits.
>>
>> That is a good point - how much does it affect the resulting hash?
>> I'm not familiar with the "3 bit" threshold for ignoring it, but it is
>> a good point - I'm worried
>> about class information content mostly. I'll do some measurements later on.
>
> "Entropy" is a way of talking about the size of the range or number
> of outputs of a hash function.  To a good approximation, at any given
> time, there are fewer than 8 different combinations of seed, class,
> and QTYPE.  My point is that almost all of the entropy is in the IP
> address.

I am aware of it and it bothers me to be honest.
But back to the original scenario, I have made a quick test to measure
number of collisions using the exact same query (QNAME=test.rrl.) from
N=100 000 random IPs (uniform dist.) and checked the number of
collisions. N is chosen as an expected response rate, since collision
in a >=1sec. inactive bin isn't really a collision just bucket reuse.
There were ~3400 collisions in 100 000 different IPs (SD~52.2, 1000
test runs). That is about p=0.034 which is reasonable for me
(distribution attached).
Yes, there can be other cases, but if they are unpredictable and seed
changes over time, I would be okay with that. But it's not just about
me, so IF the operators want the same behavior, we would be willing to
implement the internal chaining you proposed, similar to open
addressing. It is a reasonable compromise, yes.

>
>
>> No, maybe I explained it wrong. Let's say the bucket is assigned to 192.168.0.1,
>> it has a remaining rate X for this time window. Now a 10.2.3.4 hits
>> the same bucket,
>> collision is detected, bucket is reassigned and marked and an extra
>> portion of the rate is given to a bucket.
>
> How do you detect the collision?  Do you do what the NSD code does?
> I understand that to be:
>    - save the IP address in bucket
>    - during lookup, compare the IP address of the request with the
>       IP address in the bucket.
>      + If they differ, reset the counters and timers and save the
>           IP address in the bucket.

This is where the implementation differs, I already described it in
the previous email.
We don't allow multiple resets in a time window (1 second), just once
and we give some extra rate to the bucket.

>      + If they are the same, update the counters and timers and
>          possibly drop the response.
>
> The problem with that mechanism is not false positives or dropping
> good responses.  False positives do not happen between separate IP
> addresses although they can for a single IP address at about 1000
> qnames/second (birthday paradox).
> Instead, the problem is false negatives or failing to block attacks
> during collisions between legitimate requests and attack requests.

I agree and I already described it in previous emails.

> Perhaps someone else will compute the probability of failing to
> block some of at least 1 attack stream among A attack streams while
> handling N legitimate responses/second when both A and N are uniformly
> distributed among B buckets.  When I tried that estimate last year,
> the result was not fatal but I thought not good.
>
>
> Vernon Schryver    vjs at rhyolite.com
> _______________________________________________
> ratelimits mailing list
> ratelimits at lists.redbarn.org
> http://lists.redbarn.org/mailman/listinfo/ratelimits
-------------- next part --------------
A non-text attachment was scrubbed...
Name: colls.png
Type: image/png
Size: 4670 bytes
Desc: not available
URL: <http://lists.redbarn.org/pipermail/ratelimits/attachments/20130306/1156445f/attachment.png>