Subject: [GROW] Bug in draft-zhang-fibaggregation-02.txt?

From: "John G. Scudder" <[email-masked]>
Date: Sat, 21 Nov 2009 03:23:36 +0900

Folks,

It looks to me as though your level 4A FIB aggregation algorithm has a  
bug... at least if you agree that "may create forwarding loops" is a  
bug.  Two routers aggregating across holes can end up in a forwarding  
loop.  Here's an example.  Consider this network, with X and A in one  
AS and B and Y in another:

    X --- A --- B --- Y

Router A receives the following routes:
- From X, 10.32/11 and 10.192/11
- From B, 10.0/11 and 10.224/11
Using algorithm 4A, it creates the aggregate 10/8 with nexthop B  
(randomly chosen)

Router B receives the following routes:
- From A, 10.32/11 and 10.192/11
- From Y, 10.0/11 and 10.224/11
- Using algorithm 4A, it creates the aggregate 10/8 with nexthop A  
(randomly chosen)

Packets to 10/8 other than the listed prefixes will loop (e.g. to  
10.64.1.1).  Of course, they have to reach A or B first but it's not  
difficult to imagine a scenario in which they could.

This problem arises from the case where you randomly pick a next hop.   
If two adjacent routers do this, they may end up picking each other.   
I haven't worked this through for the 4B algorithm, but considering  
that it has a similar random selection step, I would guess the same  
problem could arise.

This leads me to reflect that my biggest concern with the draft as it  
stands is that the correctness condition as stated ("after longest  
match lookup, if a destination address has a non-NULL next-hop in the  
un-aggregated FIB, it should have the same next-hop in the aggregated  
FIB") is a tad questionable.  IMO the base correctness condition is  
"has black-box identical behavior to a router not using FIB  
compression", which is stronger than what's stated.  You'd need to  
drop the "has a non-NULL next-hop" caveat.  This seems to be what your  
Level 1 and 2 algorithms provide (or anyway, are intended to  
provide).  I think you need to state clearly what the correctness  
conditions are for the other levels.  (And given a clear statement of  
the correctness conditions, proof of correctness would be very  
desirable!)

Regards,

--John

---

From: William Herrin <[email-masked]>
Date: Fri, 20 Nov 2009 14:29:14 -0500

On Fri, Nov 20, 2009 at 1:23 PM, John G. Scudder <[email-masked]> wrote:
> bug... at least if you agree that "may create forwarding loops" is a bug.
> [...]

Hi John,

As I understand it, that's a feature, not a bug. It's present in both
level 3 and level 4. Routing to process:unreachable is partially
abandoned in order to get additional FIB aggregation. Packets to those
addresses continue until they hit a router that happens to route them
to process:unreachable or until the TTL expires routing them to
process:timeexceeded.

Caveats about smurf-like attack vectors understood.

Regards,
Bill Herrin

>
> This problem arises from the case where you randomly pick a next hop.  If
> two adjacent routers do this, they may end up picking each other.  I haven't
> worked this through for the 4B algorithm, but considering that it has a
> similar random selection step, I would guess the same problem could arise.
>
> This leads me to reflect that my biggest concern with the draft as it stands
> is that the correctness condition as stated ("after longest match lookup, if
> a destination address has a non-NULL next-hop in the un-aggregated FIB, it
> should have the same next-hop in the aggregated FIB") is a tad questionable.
>  IMO the base correctness condition is "has black-box identical behavior to
> a router not using FIB compression", which is stronger than what's stated.
>  You'd need to drop the "has a non-NULL next-hop" caveat.  This seems to be
> what your Level 1 and 2 algorithms provide (or anyway, are intended to
> provide).  I think you need to state clearly what the correctness conditions
> are for the other levels.  (And given a clear statement of the correctness
> conditions, proof of correctness would be very desirable!)
>
> Regards,
>
> --John
> _______________________________________________
> GROW mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/grow
>

-- 
William D. Herrin ................ [email-masked]  [email-masked]
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

---

From: "John G. Scudder" <[email-masked]>
Date: Fri, 20 Nov 2009 14:40:02 -0500

On Nov 21, 2009, at 4:29 AM, William Herrin wrote:
> As I understand it, that's a feature, not a bug.

Any "feature" that can result in a long-lived forwarding loop seems  
like a non-starter to me.  It would be interesting to hear from  
network operators who *don't* think long-lived forwarding loops are a  
problem.  What's more, the bug I found should be easy to fix with  
little or no reduction in aggregation efficiency, so I don't see much  
justification for viewing it as a "feature".

> It's present in both level 3 and level 4.

I don't think the bug I pointed out is in level 3 since it depends on  
aggregating across different next hops.  Level 3 doesn't do this.  If  
you see a potential for forwarding loops in level 3, an example would  
be helpful.

--John

---

From: Beichuan Zhang <[email-masked]>
Date: Fri, 20 Nov 2009 15:08:13 -0700

On Nov 20, 2009, at 11:23 AM, John G. Scudder wrote:

> Folks,
>
> It looks to me as though your level 4A FIB aggregation algorithm has  
> a bug... at least if you agree that "may create forwarding loops" is  
> a bug.  Two routers aggregating across holes can end up in a  
> forwarding loop.  Here's an example.  Consider this network, with X  
> and A in one AS and B and Y in another:
>
>   X --- A --- B --- Y
>
> This problem arises from the case where you randomly pick a next  
> hop.  If two adjacent routers do this, they may end up picking each  
> other.  I haven't worked this through for the 4B algorithm, but  
> considering that it has a similar random selection step, I would  
> guess the same problem could arise.

John,

Thanks for the comments. Xiaohu Xu also expressed similar concerns  
regarding possible loops.

The forwarding loop is only possible to level-4 aggregation and only  
to prefixes that are not in the original routing table, i.e., extra  
routable space. We were aware of the possibility but didn't elaborate  
it in the draft. Our initial thoughts were that (1) Since it only  
happens to prefixes not in the RIB, in normal operational conditions,  
the volume of traffic should be negligible; (2) For an attacker to  
exploit this, he has to be able to direct traffic of unreachable  
prefixes to a router that happens to have a loop for that prefix.  
Since different routers aggregate differently, it is  probably very  
difficult for a remote attacker to achieve this. Likely the attack  
traffic will be dropped before reaching the target router or use the  
wrong target prefix.

Now we're also looking into ways to mitigate this problem. For  
example, add null next-hop to some extra routable space to reduce the  
size of the extra space without sacrificing too much on aggregation  
ratio; or don't run level-4 aggregation on a router when a neighbor  
router has a default route to it (since default route can bring in  
traffic of unreachable prefixes).

Such a loop may happen even when the next hop is not randomly picked.  
In your example topology, suppose X announces 3 prefixes and Y  
announces 2 prefixes, then traffic of unreachable prefixes will flow  
in the direction of ->B->A->X and no loop. However, if at router X,  
its 3 prefixes actually each takes a different next-hop to the left,  
then the unreachable prefixes will be aggregated with the 2 prefixes  
announced by Y and loop back to A.

>
> This leads me to reflect that my biggest concern with the draft as  
> it stands is that the correctness condition as stated ("after  
> longest match lookup, if a destination address has a non-NULL next- 
> hop in the un-aggregated FIB, it should have the same next-hop in  
> the aggregated FIB") is a tad questionable.  IMO the base  
> correctness condition is "has black-box identical behavior to a  
> router not using FIB compression", which is stronger than what's  
> stated.  You'd need to drop the "has a non-NULL next-hop" caveat.   
> This seems to be what your Level 1 and 2 algorithms provide (or  
> anyway, are intended to provide).  I think you need to state clearly  
> what the correctness conditions are for the other levels.  (And  
> given a clear statement of the correctness conditions, proof of  
> correctness would be very desirable!)

You're right. Basically level 3 and 4 relax the black-box forwarding  
correctness requirement for unreachable prefixes. The difference  
between 3 and 4 is that level 3 doesn't have potential loops for the  
unreachable prefixes. We'll address this in the revision of the draft.

A major reason we classify aggregation into different levels is for  
operators to be aware of the tradeoff involved in each level and pick  
the level of aggregation that they're comfortable with for their  
networks.

---
beichuan

---

From: Danny McPherson <[email-masked]>
Date: Sat, 28 Nov 2009 21:32:21 -0700

On Nov 20, 2009, at 3:08 PM, Beichuan Zhang wrote:
> John,
> 
> Thanks for the comments. Xiaohu Xu also expressed similar concerns regarding possible loops.
> 
> The forwarding loop is only possible to level-4 aggregation and only to prefixes that are not in the original routing table, i.e., extra routable space. We were aware of the possibility but didn't elaborate it in the draft. Our initial thoughts were that (1) Since it only happens to prefixes not in the RIB, in normal operational conditions, the volume of traffic should be negligible; (2) For an attacker to exploit this, he has to be able to direct traffic of unreachable prefixes to a router that happens to have a loop for that prefix. Since different routers aggregate differently, it is  probably very difficult for a remote attacker to achieve this. Likely the attack traffic will be dropped before reaching the target router or use the wrong target prefix.

Unless *the router* is the target - and I'd reckon that it's 
not actually that difficult to identify such candidate prefixes
from afar..  I share John's concerns here and would like to see 
them addressed and/or expressly elaborated as such in the draft.

-danny