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

Tue Sep 9 00:32:31 EDT 2008

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/

-- 
- Xenion - http://www.xenion.com.au/ - VPS Hosting - Commercial Squid Support -
- $25/pm entry-level VPSes w/ capped bandwidth charges available in WA -