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有沒有什麼對等的優化策略