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 anythis 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 anymove to the top.! pings and traceroute permit icmp any anyeither 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 34xxxrarely 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 US2rarely 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 XXXmove 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 anyand 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 [email protected] 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 [email protected] 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 [email protected] https://puck.nether.net/mailman/listinfo/cisco-nsp archive at http://puck.nether.net/pipermail/cisco-nsp/
