Linux的Netfilter框架深度思考-对比Cisco的ACL
在前面
0.1.本文不涉及具体实现，也不涉及源代码，不剖析代码
0.2.本文不争辩Linux或者Cisco IOS不同版本之间的实现细节
0.3.本文不正确处请指出
Cisco无疑是网络领域的领跑者，而Linux则是最具活力的操作系统内核，Linux几乎可以实现网络方面的所有特性，然而肯定还有一定的优化空间，本文首先向Cisco看齐，然后从不同的角度分析Netfilter的对应特性，最终提出一个ip_conntrack的优化方案。
0.4.累坏了，但还是撑着整理了这篇文档
1.设计的异同
Netfilter是一个设计良好的框架，之所以说它是一个框架是因为它提供了最基本的底层支撑，而对于实现的关注度却没有那么高，这种底层支撑实际上就是其5个HOOK点：
PREROUTING：数据包进入网络层马上路由前
FORWARD：数据包路由之后确定要转发之后
INPUT：数据包路由之后确定要本地接收之后
OUTPUT：本地数据包发送(详情见附录4)
POSTROUTING：数据包马上发出去之前
1).HOOK点的设计：
Netfilter的hook点其实就是固定的“检查点”，这些检查点是内嵌于网络协议栈的，它将检查点无条件的安插在协议栈中，这些检查点的检查是无条件执行的 ；对比Cisco，我们知道其ACL也是经过精心设计的，但是其思想却和Netfilter截然相反，ACL并不是内嵌在协议栈的，而是一种“外部的列表”，策略包含在这些列表中，这些列表必须绑定在具体的接口上方能生效，除了绑定在接口上之外，检查的数据包的方向也要在绑定时指定，这说明ACL只是一个外接的策略，可以动态分派到任何需要数据包准入检查的地方。
2.数据流的异同-仅考虑转发情况
1).对于Cisco，数据包的通过路径如下：
2).对于Linux的Netfilter，数据包的通过路径如下：
3.效率和灵活性
3.1.过滤的位置
从数据流的图示中可以看出Netfilter的数据包过滤发生在网络层，这实际上是一个很晚的时期，从安全性上考虑，很多攻击-特别是针对路由器/服务器本身的Dos攻击-此时已经形成了，一个有效的预防方式就是在更早的时候丢弃数据包，这也正是Cisco的策略：“在尽可能早的时候丢弃数据包”。而Cisco也正是这么做的，这个从上面的图示中可以看出。Cisco的过滤发生在路由之前。
3.2.过滤表的条目
由于Netfilter是内嵌在协议栈中的全局的过滤框架，加之其位置较高，很难对“哪些包应该匹配哪些策略”进行区分，而Cisco的ACL配置在网卡接口，并且指定了匹配数据包的方向，因此通过区分网卡接口和方向，最终一个数据包只需要经过“一部分而不是全部”的策略的匹配。比如从Ether0进入的数据包只会匹配配置在Ether0上入站方向的ACL。
3.3.NAT的位置
Netfilter的NAT发生在filter之前和之后，而Cisco的nat也发生在filter之中，这对二者filter策略的配置有很大的影响，对于使用Netfilter的系统，需要配置DNAT之后或者SNAT之前的地址，而对于Cisco，则需要配置DNAT之前或者SNAT之后的地址。
3.4.配置灵活性
3.4.1.Cisco的acl配置很灵活，甚至“配置到接口”，“指明方向”这一类信息都是外部的，十分符合UNIX哲学的KISS原则，但是在具体的配置上对工程师的要求更高一些，他们不仅仅要考虑匹配项等信息，而且还要考虑接口的规划。
3.4.2.Netfilter的设计更加集成化，它将接口和方向都统一地集成在了“匹配项”中，工程师只需要知道ip信息或者传输层信息就可以配置了，如果他们不关心接口，甚至不需要指明接口信息，实际上在iptables中，不使用-i和-o选项的有很多。
4.Netfilter优化
4.1.防火墙策略查找优化
4.1.1.综述
传统意义上，Netfilter将所有的规则按照配置的顺序线性排列在一起，每一个数据包都要经过所有的这些规则，这大大降低了效率，随着规则的增加，效率会近似线性的下降，如果能让一个数据包仅仅通过一部分的规则的匹配就比较好了。这就是说，我们要对规则进行分类，然后先将过往的数据包用高效的算法匹配到一个特定的分类，然后该数据包只需要再继续匹配该分类中规则就可以了。
分类实际山很简单，它基于一个再简单不过的解析几何事实：在一条线段上，一个点将整个线段分为3部分： 
因此，任何一个匹配项都可以归结为一个所谓的“键值”，在该键值空间中，一定有某种顺序可供排序，那么一个键值，就能将这个键值空间分为三个部分：大于，等于，小于。一维空间如此，N维空间亦如此，只是更精确，这里N是我们挑选出来的匹配域。为了更好的理解下面的论述，先给出两幅图。传统意义的防火墙规则匹配操作如下图所示，它是平坦的：
而优化后的防火墙规则匹配操作如下图所示，它是分维度的： 
最终，只有虚线所围的区域有规则要匹配，只有数据包“掉进了”这些区域，才需要匹配规则，否则全部按照“策略”行事。当然，一个数据包不可能掉进两个区域。这里只考虑了源IP地址和目的IP地址这种二维的情形，如果加上第四层协议，端口等信息维度，匹配就更加精确了，并且，只要使用的“类”匹配算法足够精巧，操作是不会随着规则的增加而增加的，而这一部分内容正是我们马上就要讨论的内容
4.1.2.Cisco的优化策略
很多用过Cisco的人都知道，Cisco有一个叫做Turbo ACL的概念，这个Turbo ACL的要旨就是“不再用规则匹配数据包，而成为了使用数据包的信息查找需要匹配它的规则”。这就意味着在ACL插入系统的时候就要对其进行排序，然后数据包进入的时候，通过数据包的信息去查找排过续的规则集。
想了解Cisco的技术细节，直接浏览其官方网站的Support是很有必要的，这里有最直接的讲述，Cisco的技术Support有一个很好的地方，那就是它有情景分析。我下面就用那上面的例子来进行分析，基本上基于一篇文档：《TURBO ACL》。
Turbo ACL定义了一系列的匹配域，如下图所示：
其中绿色的表示三层信息，红色的表示四层信息，粉色的表示第三层+第四层的信息。针对于每一个匹配域，都存在一个表，我们称为“值表”：
其中索引是为了查找和管理方便，而值则被填入规则中对应该表的匹配域的值，ACL位图指示该表的该记录匹配哪些ACL。因此，对于所有的匹配域，由于一共有8个匹配域，那么就有8个这样的表。为了更加容易理解，给出一个例子，首先看4条acl规则：
#access-list 101 deny tcp 192.168.1.0 0.0.0.255 192.168.2.0 0.0.0.255 eq telnet
#access-list 101 permit tcp 192.168.1.0 0.0.0.255 192.168.2.0 0.0.0.255 eq http
#access-list 101 deny tcp 192.168.1.0 0.0.0.255 192.168.3.0 0.0.0.255 eq http
#access-list 101 deny icmp 192.168.1.0 0.0.0.255 200.200.200.0 0.0.0.255
这些规则填入匹配域表格后，匹配域表格如下：
然后仅给出一个“源地址1”的值表：
到此为止，我们已经给出了所有的静态的数据结构，接下来就是具体的动态操作了，归为一种算法。Cisco的规则匹配算法是分层次的，并且是可并行运算的，因此它的效率极其高效，整个算法分为两大部分：
1).数据包基于所有匹配域的位图查找
这个步骤是可以并行的，比如可以同时在两个处理器上查找“源地址1”的值表和“源地址2”的值表，从而最大化CPU利用率，以最快的速度得到两个位图，算法对于采用何种查找算法没有规定，取决于添加ACL时如何将匹配域的值插入对应值表。另外，哪种查找快用哪种，这是不争的事实，我们一般很少有动态插入的，一般都是静态插入的，因此对数据插入的性能要求并不高，关键要素是查找。这个查找算法的查找效率非常重要，好的算法如果是O(1)的，那就意味着匹配规则的过程消耗的时间不会随着规则的增加而增加，事实上即使是O(n)的查找算法， 也将N次的匹配操作转化为了按照一个比例小得多的a*N次的查找操作，往往a是一个很小的且小于1的数字...
2).多个位图多次的AND操作
取多个结果的交集，最终得到一条或者几条ACE。这种位图的算法是Cisco惯用的用空间换时间的策略，传说中的256叉树使用的也是这样的策略。
下面给出操作的流程图：
作为一个情景分析，我们考虑一个数据包到来，它的匹配域的值如下：
源地址1 : 192.168
源地址2 : 1.1
目的地址1 : 200.200
目的地址2 : 200.1
四层协议 : 0001 (ICMP)
针对此包的操作流程图如下，假设仅有上述举例的acl可用：
最终得到了0001，也就是仅有最后一条规则是匹配的。
这样我们就结束了Turbo ACL的讨论，接下来就要看看Linux的Netfilter有没有什么对等的优化策略