[c-nsp] NPE G1, CEF and ACLs and high CPU

Tue Sep 9 01:07:57 EDT 2008

Are you serious?

Well, I unhappily and disappointedly stand corrected, then.  Indeed, 
Cisco documentation appears to confirm what you and Bill are saying.

There are a variety of known algorithms for traversing hashed structures 
while taking order of precedence into account.  I am, quite frankly, 
astonished that they are not used, or that it takes some sort of ASIC or 
TCAM enhancement to make that happen.

Adrian Chadd wrote:

> Bill is practically right. The semantics for Cisco ACLs aren't "here's a set
> of IP ranges, apply this behaviour", they're a linear walk of rules from
> top to bottom applying behaviour at each step. Collapsing that into the
> smallest set of possible operations is -not- taught at first/second year
> computer science. Eg:
> 
> * permit ssh 1.2.3.0/24
> * deny ssh 1.2.4.8/30
> * permit ssh 1.2.0.0/16
> * deny ssh 1.0.0.0/8
> 
> Please yank the first year computer science curriculum bit which provides
> the student with the clue required to algorithmically determine the smallest
> set of permit/deny's keeping the above semantics correct. Then do some basic
> analysis to find out what the resource bounds are on determining that.
> Oh, then prove that you can evaluate it in "more or less O(1) time". Go on,
> I dare you :) (Note: I -think- the TCAM ACL rule programming in later IOSes
> can do that? Perhaps Rodney or someone else from Cisco can comment.. :)
> 
> There's some rule folding (and compiling?) stuff that I've heard about in
> later software-forwarding IOSes which attempt to mitigate this somewhat but
> I've never really sat down and (ab)used it.
> 
> Now, I suggest you go back and read how iptables / ipfw / pf rules
> are actually -parsed- and -handled- in the various *NIXes you speak of.
> I've done this exercise and I'll give you a hint - rules are evaluated
> much the same as they are on the Cisco, except in some cases the evaluation
> doesn't stop at first hit and there are other gotchas (like "match X goto rule
> Y"). Go figure out why.
> 
> I'll give you an even bigger hint - the best way to get a speedup under
> *NIX packet filters is to build "sets" of IP addresses to apply your policies
> rather than individual rules for each network you want to allow SSH for.
> The difference between one rule w/ a 200,000 network IP set versus 200,000
> entries is pretty staggering - and the latter depends on the rule ordering.
> Just like Bill said. :)
> 
> 
> 
> 
> Adrian
> 
> On Tue, Sep 09, 2008, Alex Balashov wrote:
>> Are you _sure_ that order is important in these ACLs?  I ask because I 
>> honestly don't know, so don't get me wrong.
>>
>> It just seems rather unlikely.  Organising data like that into 
>> structures where matching and access can happen at more or less an O(1) 
>> formal computational complexity is a basic skill that is taught at the 
>> beginning of any undergraduate curriculum in computer science.  Students 
>> are taught to understand that large amounts of random (non-sorted) data 
>> cannot be stored in a linear structure, and that even linear structures 
>> with comparatively few elements (such as an access list) can be very 
>> slow if the lookup is repeated with very great frequency.
>>
>> That's why such data gets stored in multidimensional and relational data 
>> structures:  things like binary trees (and their innumerable 
>> permutations), undirected string vector graphs for heavy lexical token 
>> matching, hash tables, and various relational mechanisms for forming 
>> bindings or indices from a quick and superficial glimpse at the data.
>>
>> It's how every firewall/packet filtering engine (such as Linux 
>> netfilter, or the FreeBSD packet filter) is implemented, so packets are 
>> matched using a hashing strategy rather than linear, iterative comparisons.
>>
>> What you appear to be suggesting in your dwelling upon the significance 
>> of rules being at the bottom or top of an access list definition would 
>> also imply that these basic algorithmic innovations and elements of the 
>> software engineering canon have somehow managed, with great finesse, to 
>> escape the notice of the people who wrote IOS.  I refuse to believe that.
>>
>> bill fumerola wrote:
>>
>>> [ reading through quickly, just some ACL pointers.. ]
>>>
>>> On Mon, Sep 08, 2008 at 09:15:31PM +0100, Mateusz B?aszczyk wrote:
>>>> ! deny rogue IPs (it is interesting how many catches are here)
>>>> deny ip 10.0.0.0 .... any
>>>> deny ip 192... any
>>>> deny ip host 0.0.0.0 any
>>> this breaks PMTUD. icmp messages from poorly addressed routers still
>>> need to get back to your hosts.
>>>
>>>> etc....
>>>> ! deny spoofing us...
>>>> deny ip OURBLOCK1 any
>>>> deny ip OURBLOCK2 any
>>> move to the top.
>>>
>>>> ! pings and traceroute
>>>> permit icmp any any
>>> either permit the specific ICMPs required for end to end communication
>>> to work and permit the rest after your anti-spoof, or just move this
>>> towards the top.
>>>
>>>> permit udp any any range 32xxx 34xxx
>>> rarely used, moved towards the bottom.
>>>
>>>> ! transit providers
>>>> permit tcp host THEM1 host US1 eg bgp
>>>> permit tcp host THEM1 eq bgp host US1
>>>> ! Internet eXchanges - bgp/msdp
>>>> permit tcp THEM2 WCARD2 host US2  eg bgp
>>>> permit tcp THEM2 WCARD2 eq bgp host US2
>>>> deny ip any US1
>>>> deny ip any US2
>>> rarely used, move towards bottom. consider removing the port-specific
>>> portions and see if you can get your ISP to use the TTL hack.
>>>
>>>> ! some legacy stuff
>>>> permit ip any host XXX
>>> move towards the top.
>>>
>>>> ! deny access to infrastructure
>>>> deny ip any NETWORK_1
>>>> ...
>>>> deny ip any NETWORK_N
>>> <hack>
>>> sometimes, you can null route these blocks and use policy route-maps
>>> that set next-hop for your local device and/or management networks
>>> that allow the forwarding plane take care of discarding these
>>> </hack>
>>>
>>>> permit ip any any
>>> and here's where the majority of your traffic matches - at the bottom.
>>> this will kill performance. consider the trade-off of adding a:
>>>
>>> permit tcp any any established
>>>
>>> towards the top of your config. that rule will catch the majority of
>>> most networks' traffic. your deny rules below will still prevent SYN
>>> packets from getting through to your infrastructure space. yes, your
>>> 'infrastructure' will be open to ACK floods and other such things, but
>>> you can deploy other measures to assist with that. for example: ACLs on
>>> the interfaces facing your management network instead.
>>>
>>> also, if you run a service that represents the bulk of your traffic on
>>> that device, add a short-circuit rule for that service higher at the
>>> top, even if a rule with wider reach allows the same later.
>>>
>>>> any significant advantage over entry-level 6500/7600?
>>> 6500/7600 will be way less order dependent and you'll be able to have
>>> much longer ACLs. in my experience, on software platforms 99% of your
>>> traffic should either be permitted or denied in the first 5 or so rules
>>> or you're going to see serious performance problems.
>>>
>>> consider using 'access-list compiled' if your platform/IOS support it.
>>>
>>> distribute your ACLs as much as possible. take a multi layered approach.
>>> know your device's strengths and weaknesses when it comes to filtering
>>> and exploit those.
>>>
>>> -- bill
>>> _______________________________________________
>>> cisco-nsp mailing list  cisco-nsp at puck.nether.net
>>> https://puck.nether.net/mailman/listinfo/cisco-nsp
>>> archive at http://puck.nether.net/pipermail/cisco-nsp/
>>
>> -- 
>> Alex Balashov
>> Evariste Systems
>> Web    : http://www.evaristesys.com/
>> Tel    : (+1) (678) 954-0670
>> Direct : (+1) (678) 954-0671
>> Mobile : (+1) (706) 338-8599
>> _______________________________________________
>> cisco-nsp mailing list  cisco-nsp at puck.nether.net
>> https://puck.nether.net/mailman/listinfo/cisco-nsp
>> archive at http://puck.nether.net/pipermail/cisco-nsp/
> 

-- 
Alex Balashov
Evariste Systems
Web    : http://www.evaristesys.com/
Tel    : (+1) (678) 954-0670
Direct : (+1) (678) 954-0671
Mobile : (+1) (706) 338-8599