Subject: Re: [lisp] Need comments on LISP Threats Analysis

From: [email-masked] (Noel Chiappa)
Date: Thu, 21 Mar 2013 14:01:29 -0400 (EDT)

> From: Darrel Lewis <[email-masked]>

    > Another useful piece of information would be

As I was idly thinking about this this morning, one additional tweak to the
'aged usage count' came to mind, which is to record the time the mapping was
loaded. This would help filter out 'newly loaded real mappings', which one
should probably leave for another pass, from 'DoS mappings loaded a while
ago', which one can definitely recycle.

The aging algorithm could become something like:

- if the aged count is small, _and_ the load-time is a while in the past,
    add this mapping to the 'potential free list'

and when a new mapping has to be loaded, loop over the 'potential free list'
(until one finds a re-usable entry), for each entry:

- check to see if the aged usage count has become large (this will catch
    those few entries which are real, but looked like they might be bogus
    when they were added to the 'potential free list'; if so, remove this
    entry from the PFL
- otherwise, recycle this entry; done

I'm not sure this is worth it (it costs one extra memory word per mapping
cache entry; the extra computational load is negligible), but it should
pretty much prevent the loss of any newly-loaded 'real' mappings.

    > _which EID instigated_ the map request. .. all the map-requests
    > generated by that host could be treated as a lower priority (and aged
    > out faster) than those cache entries instigated by other hosts.

Interesting. 

This again would make the mapping entries larger, but it is probably worth
doing, because it would allow one to actually cut out the control plane load
from such DoS attacks, a significant cost. (The control plane load is
probably actually the worst part of such attacks, actually.)

You'd have to build a database of requestors, and in each entry, have a count
of the number of mappings that were discarded after a while, without a
significant usage count (this count too should probably be aged). Once a host
had tripped a certain level, it would go in a 'request rate limited' penalty
box.

Although I guess if you have the requestor database, you could just use it to
count mapping requests directly (again, aged) which will avoid the overhead
of per-mapping-entry source information - too-active requestors could be
individually rate-limited (as above).

And if you did that, you could probably avoid the 'load time' thing above;
rate-limiting requestors directly would be the primary line of defence, and
the cache would only need a simple aged usage count to filter out the (fewer)
DoS'd entries.

    > There are, literally, dozens of techniques to optimize a cache that is
    > under pressure from DoS attacks.

Indeed - my brain is spinning out more as I type this.

(E.g. divide the mapping cache into three pools: 'newly arrived', 'potential
free list' and 'significant use' - new entries start in the first, and after
a time interval, move either to the second or third, depending on their usage
count at the expiration of the time interval.)

	Noel

---

From: Darrel Lewis <[email-masked]>
Date: Thu, 21 Mar 2013 12:13:59 -0700

Noel,

Good discussion, I don't mean to be exhaustive here, because first of all there is so much research (and practical implementations) of these algorithms that I don't feel its possible, and second, I think trying to appear exhaustive might preclude further innovation by implementers.

I encourage everyone actively thinking about this to investigate the information that Albert posted to the list, I find the work that his team of researchers have been working on very interesting.

One comment inline:
<snip>
> individually rate-limited (as above).

An ITR must have to have a request database (in order to match replies to request nonce's if nothing else) so extending that to include the things you talk about above seems straightforward.

> the cache would only need a simple aged usage count to filter out the (fewer)

You got it.  Again, products such as Arbor and (now, regrettably, gone) Riverhead have been using such algorithms to protect state machines for more than a decade.

-Darrel