吳 軍，鄧寶龍，邵定宏

（南京工業(yè)大學(xué) 電子與信息工程學(xué)院，江蘇 南京211816）

0 引 言

防火墻規(guī)則間異常的檢測方法一般將規(guī)則序列轉(zhuǎn)化對等體或?qū)σ汛嬖诘膶Φ润w［1－4］進(jìn)行改進(jìn)，達(dá)到提高規(guī)則間異常檢測效率的目的。Al－Shaer和H.Hamed 首次對分布式防火墻規(guī)則間存在的異常進(jìn)行定義［5］，并提出了基于策略樹PT （policy tree）的分布式防火墻規(guī)則異常檢測算法。該算法時間復(fù)雜度為O（dN ），其中d是規(guī)則維數(shù)，N 表示規(guī)則數(shù)量。文獻(xiàn) ［5］提出了一種BDD （binary decision diagrams）變體二叉樹BT （binary tree）模型，實現(xiàn)了分布式防火墻規(guī)則異常的檢測。該算法的時間復(fù)雜度為O（lg N ＋N／w），其中N 為規(guī)則數(shù)量，w 為機(jī)器字長。BT 算法相對于PT 算法規(guī)則異常檢測效率有一定的提高，但是在構(gòu)建對等體時將規(guī)則序列號丟棄，導(dǎo)致無法精確分析具體規(guī)則間產(chǎn)生的異常，并且隨著規(guī)則數(shù)量的增加檢測效率降低。陳文慧提出一種防火墻決策樹FDT （firewall decision tree）的變形 MFDT （marked firewall decision tree）模型［6］。MFDT 模型除滿足FDT 的特性外，MFDT 中保留規(guī)則原始位置信息。MFDT 可以實現(xiàn)規(guī)則的插入、刪除、更新操作，但是此模型僅局限于獨立防火墻規(guī)則間的分析。Alex X.Liu等人提出了將防火墻規(guī)則轉(zhuǎn)化為策略圖FDD［7］，不僅可以保證與原始規(guī)則保持一致性、完整性、緊湊性基礎(chǔ)上，消除獨立防火墻規(guī)則間的異常。由于FDD 構(gòu)建過程中將規(guī)則的序列號丟棄，以及構(gòu)建過程中會增加決策路徑數(shù)量［7］，這些都增加了基于FDD 模型分析分布式防火墻規(guī)則異常的困難。另外，文獻(xiàn) ［8］提出一種方法可以將獨立防火墻中的異常規(guī)則自動修正，但對于自動修正分布式防火墻中的異常規(guī)則，實現(xiàn)優(yōu)化異常規(guī)則的研究較少。

研究發(fā)現(xiàn)，存在的分布式防火墻異常規(guī)則檢測算法通常將上游［9］（下游）防火墻轉(zhuǎn)化為對等體，將下游［9］（上游）防火墻中規(guī)則逐一和對等體進(jìn)行比較，判斷規(guī)則間異常。由于在構(gòu)建對等體時將規(guī)則序列號丟棄，導(dǎo)致無法精確具體分析規(guī)則間產(chǎn)生的異常，并且隨著規(guī)則數(shù)量的增加檢測效率降低，同時缺少分布式防火墻異常規(guī)則自動修正優(yōu)化方法。針對上述問題，我們提出了一種基于FDD 的進(jìn)化模型半同構(gòu)標(biāo)記防火墻決策圖SMFDD，實現(xiàn)分布式防火墻具體規(guī)則間異常檢測，提高異常規(guī)則檢測效率，同時通過SMFDD 間邏輯操作達(dá)到優(yōu)化分布式防火墻中異常規(guī)則的目的。實驗結(jié)果表明，在布式防火墻規(guī)則轉(zhuǎn)化為SMFDD后，對SMFDD 之間的比較操作可以快速檢測規(guī)則間異常。尤其當(dāng)防火墻規(guī)則數(shù)量較大時，效果更加顯著。SMFDD 間的邏輯操作，實現(xiàn)了對存在異常的規(guī)則自動修正，達(dá)到優(yōu)化異常規(guī)則的目的。

1 SMFDD模型分析

本節(jié)首先分析分布式防火墻規(guī)則間的異常，然后對FDD 進(jìn)化過程進(jìn)行分析。整個進(jìn)化過程包括兩部分：防火墻規(guī)則轉(zhuǎn)化為對等體標(biāo)記防火墻決策圖MFDD （marked firewall decision diagram）、MFDD 半同構(gòu)化處理形成SMFDD。最后通過SMFDD 比較操作檢測規(guī)則異常，以及SMFDD 間邏輯操作，自動修正異常規(guī)則。

1.1 規(guī)則異常定義

防火墻規(guī)則由訪問控制列表中的列表項組成，決定數(shù)據(jù)包執(zhí)行的動作。每個規(guī)則由規(guī)則號、過濾域、動作域3部分組成。其中規(guī)則號決定數(shù)據(jù)包匹配的順序。過濾域通常由源IP地址、目的IP、源port、目的port、協(xié)議類型五元組組成。動作域只考慮接受與拒絕數(shù)據(jù)包。防火墻中的規(guī)則表示為：＜o(jì)rder＞＜protocol＞＜src＿ip＞＜src＿port＞＜dst＿ip＞＜dst＿port＞＜action＞。規(guī)則異常是指規(guī)則之間1個域或多個域重疊或交叉，導(dǎo)致產(chǎn)生一種模糊分類問題［9］。 若規(guī)則 rx和 ry存在異常， 則 i：rx［Fi］ry［Fi］，且rx和ry的動作域 （action）不同。其中，∈｛，，＝｝，F(xiàn)i ∈｛protocol，src＿ip，src＿port，dst＿ip，dst＿port｝。

分布式防火墻結(jié)構(gòu)，如圖1所示，對于靠近源地址的防火墻fu稱為上游防火墻，靠近目的地址的防火墻fd稱為下游防火墻。下面給出分布式防火墻規(guī)則異常的定義［9］：

定義1 上游防火墻fu允許的數(shù)據(jù)包被下游的防火墻fd丟棄，則出現(xiàn)非法流入異常。

定義2 上游防火墻fu拒絕的數(shù)據(jù)包被下游的防火墻fd接受，則出現(xiàn)屏蔽異常。

圖1 分布式防火墻結(jié)構(gòu)

1.2 SMFDD的構(gòu)建及運算

在SMFDD的構(gòu)建過程中，首先將防火墻規(guī)則轉(zhuǎn)化為FDD的變體MFDD，要確保MFDD 的有序性。MFDD 在保持原始規(guī)則完整性、一致性、緊湊性的基礎(chǔ)上，消除獨立防火墻規(guī)則間異常，同時保持原始規(guī)則序列信息。其次，將MFDDs半同構(gòu)化處理構(gòu)造成除葉子節(jié)點之外，其他節(jié)點完全相同的SMFDDs。下面是關(guān)與MFDD模型相關(guān)定義。

定義3 防火墻規(guī)則的過濾域包括F1F2，…Fd，表示順序關(guān)系，使得F1F2…Fd，當(dāng)所有決策路徑（v1e1…vkekvk＋1）都滿足F（v1）F（v2）… F（vk），則稱MFDD 滿足有序性。

定義4 當(dāng)MFDDs f 和f′中對應(yīng)非葉子節(jié)點v 和v′，v和v′節(jié)點的邊一一對應(yīng)，且具有相同的標(biāo)識，稱v 和v′是半同構(gòu)節(jié)點。

定義5 當(dāng)MFDDs f 和f′中所有對應(yīng)非葉子節(jié)點具有相同的出度值和入度值，且對應(yīng)邊的具有相同的標(biāo)識，稱f 和f′是半同構(gòu)化體。

1.2.1 SMFDD 的構(gòu)建過程

SMFDD 的構(gòu)建過程如下：①防火墻規(guī)則轉(zhuǎn)化為對等體MFDD。②MFDDs半同構(gòu)化處理形成SMFDDs。

步驟1 MFDD 構(gòu)建

將規(guī)則序列＜r1，...，rn＞轉(zhuǎn)化為對等體MFDDf，f和規(guī)則序列的過濾決策是一致的。其中規(guī)則形式化表述為rk［F1］∧rk［F2］∧...∧rk［F3］→action。從第1條規(guī)則r1轉(zhuǎn)化決策路徑開始，依次將r2，...，rn添加到f 中，最終形成規(guī)則序列對等體MFDDf。假設(shè)已將規(guī)則集中r1，...，rk添加到f 中，f根節(jié)點v 有k 條邊e1，...，ek，如果需要將規(guī)則rk＋1添加到f，則需要完成以下2個步驟。

首先，判斷是否需要添加邊到v，令rk＋1的F1值為S1，邊的標(biāo)示為I（e1），M（e）為規(guī)則序列號標(biāo)記。如果S1－（I（e1）∪...∪I（ek）≠，則需要添加一條ek＋1，令I(lǐng)（ek＋1）＝S1－（I（e1）∪...∪I（ek）），M（ej）＝｛k＋1｝，同時ek＋1指向rk＋1［F2］∧rk＋1［F3］∧...∧rk＋1［Fd］→action 產(chǎn)生的子樹。反之，則不需添加新的邊。其次，比S1和I（ej），其中1≤j≤k，比較結(jié)果包括以下3種情況：①S1∩I（ej）＝。滿足第1 步的條件，創(chuàng)建新邊。②S1∩I（ej）＝I（ej）。規(guī)則域存在重疊部分，同一個數(shù)據(jù)包可能匹配rk＋1和M（ej）中規(guī)則，令M（ej）＝M（ej）∪｛k＋1｝，邊ej指向rk＋1［F2］∧rk＋1［F3］∧...∧rk＋1［Fd］→action 產(chǎn)生的子樹。③S1∩I（ej）≠∧S1∩I（ej）≠I（ej）。

將邊ej拆分成邊e′和e″，其中I（e′）＝I（ej）－S1，I（e″）＝I（ej）∩S1，M（e″）＝M（e′）＝M（ej），將e′和e″指向ej邊所指向的子樹，并刪除邊ej指向的子樹。將表1和表2中的上游防火墻fu和下游防火墻fd中規(guī)則應(yīng)用到上述構(gòu)造過程對應(yīng)生成圖2和圖3。為簡單起見，本文設(shè)定協(xié)議類型值為只包括0 （TCP）或1 （UDP）。對于表3 是表示規(guī)則過濾域的簡寫與域值范圍，表4是圖例中IP地址及動作域的簡寫標(biāo)識。

表1 防火墻fu 的規(guī)則集

表2 防火墻fd 的規(guī)則集

圖2 fu 對等體

表3 規(guī)則過濾域的簡寫與域值范圍

圖3 fd 對等體

表4 簡寫標(biāo)識

步驟2 MFDDs半同構(gòu)化處理構(gòu)建SMFDDs

MFDDs的半同構(gòu)化等價于全部非葉子節(jié)點的半同構(gòu)化。對于節(jié)點va有m 條邊 ｛e1，e2…，em｝，vb有n條邊｛e′1，e′2…，e′n｝，va和vb出邊的I（e）為單一連續(xù)區(qū)間。假設(shè)邊e1的I（e1）＝ ［a，b1］，邊e′1的I（e′1）＝ ［a，b′1］。I（e1）和I（e′1）比較結(jié)果分以下兩種情況：①當(dāng)b1＝b′1，I（e1）＝I（e′1）。下一步比較邊e2和e′2的I（e2）和I（e′2）值。②當(dāng)b1≠b′1，假設(shè)b1＜b′1，將邊e′1拆分成兩條邊e和e′，e和e′分別指向e′1的子樹，I（e）＝ ［a，b1］，I（e′）＝［b1＋1，b′1］，邊標(biāo)記M（e）＝M（e′）＝M（e′1）。下一步比較I（e2）和I（e′）。這里邊的標(biāo)識左區(qū)間是相同的，將這個比較過程繼續(xù)下去，直到節(jié)點最右側(cè)的邊。當(dāng)最右側(cè)邊的值也相同時，完成節(jié)點的半同構(gòu)化。重復(fù)上述過程，除葉子節(jié)點外，實現(xiàn)所有節(jié)點半同構(gòu)化。將圖2與圖3經(jīng)過半結(jié)構(gòu)化處理后，結(jié)果如圖4和圖5所示。

1.2.2 SMFDD 間比較操作檢測異常規(guī)則

通過比較半同構(gòu)體f 和f′中對應(yīng)決策路徑中的葉子節(jié)點的值，判斷規(guī)則間是否存在異常。設(shè)（1≤r≤m，1≤i≤n）表示葉子節(jié)點的值，其中m 和n分別表示葉子節(jié)點數(shù)和防火墻中規(guī)則的個數(shù)。通過比較f 和f′對應(yīng)決策路中的值，判斷規(guī)則間是否存在異常。比較的結(jié)果包括：①-r，r′，1≤r，r′≤m，。防火墻規(guī)則r和r′過濾決策相同，r和r′之間不存在異常關(guān)系。②-r，r′，1≤r，r′≤m，。防火墻規(guī)則r和r′過濾決策相同，r和r′之間存在異常關(guān)系。例如，通過比較圖4和圖5半同構(gòu)體f 和f′中對應(yīng)決策路徑中的葉子節(jié)點的值，可以發(fā)現(xiàn)fu中規(guī)則r1和fd中規(guī)則r′3存在屏蔽異常。

圖4 fu 生成的SMFDDf

圖5 fd 生成的SMFDDf′

1.2.3 SMFDD 間邏輯操作優(yōu)化異常規(guī)則

2 算法提出

本節(jié)采用類C 描述，給出了SMFDD 構(gòu)造算法、規(guī)則異常檢測算法及規(guī)則優(yōu)化算法的偽代碼。

2.1 SMFDD構(gòu)造算法

上述算法，首先將上下防火墻規(guī)則轉(zhuǎn)化為MFDDf′和f″后，在此基礎(chǔ)上，將f′和f″中非葉子節(jié)點半同構(gòu)化處理，完成f′和f″半同構(gòu)體的構(gòu)建。

2.2 規(guī)則異常檢測算法

上述算法，在將上下游防火墻規(guī)則轉(zhuǎn)化成SMFDD f′和SMFDDf″基礎(chǔ)上，比較f′和f″對應(yīng)的決策路徑中葉子節(jié)點值。根據(jù)異常的定義，判斷規(guī)則間的異常關(guān)系。

2.3 規(guī)則優(yōu)化算法

上述算法，通過將f′和f″對應(yīng)的決策路徑中葉子節(jié)點值之間邏輯與操作，自動修正異常規(guī)則。

3 性能分析與評價

本文使用仿真實驗來分析與評價算法的性能，首先搭建仿真實驗環(huán)境，然后分析實驗結(jié)果并評價算法的性能。

3.1 實驗設(shè)計

在NS2中構(gòu)建一個虛擬的分布式防火墻應(yīng)用場景，選取其中兩個防火墻，將不同數(shù)量規(guī)則寫入防火墻中。文獻(xiàn)［10］資料反映實際投入使用的防火墻規(guī)則數(shù)量最多約為3000條，在實驗過程中，設(shè)定防火墻規(guī)則最多為3000條，符合實際應(yīng)用條件。本文實驗包括3部分：第1部分是對FDD 進(jìn)化過程的性能分析；第2部分分析了在不同規(guī)則的情況下，MFDD 進(jìn)化模型實現(xiàn)規(guī)則異常檢測的效率，并將其與BT 算法和PT 算法進(jìn)行比較；第3部分通過SMFDD間邏輯操作，分析了規(guī)則間異常優(yōu)化算法的性能。

3.2 結(jié)果分析

實驗的第1部分是對FDD 進(jìn)化過程的性能分析。圖7給出了FDD 進(jìn)化過程的仿真結(jié)果，從中可以看出，隨著防火墻中規(guī)則數(shù)量的增加，F(xiàn)DD 進(jìn)化過程各部分所需時間都在增加。當(dāng)規(guī)則集數(shù)量相同時，規(guī)則集轉(zhuǎn)化為對等體MFDD 的時間占FDD 進(jìn)化過程比例最大，半同構(gòu)化過程其次，半同構(gòu)體間比較時間相對最少。

圖7 FDD 進(jìn)化過程

實驗的第2部分分析了基于SMFDD 的規(guī)則異常檢測算法的執(zhí)行效率，并將其與BT 算法和PT 算法進(jìn)行比較。從仿真結(jié)果圖8可以看出，當(dāng)防火墻中規(guī)則數(shù)量較少時，BT算法速度最快，PT算法略低于BT算法，基于SMFDD 的規(guī)則異常檢測算法執(zhí)行速度低于兩者。從圖9中可以看出，當(dāng)防火墻中規(guī)則數(shù)量較多時，基于SMFDD 的規(guī)則異常檢測算法最優(yōu)，PT算法和BT算法相近，但是執(zhí)行速度遠(yuǎn)低于基于SMFDD的規(guī)則異常檢測算法。出現(xiàn)這種結(jié)果的原因包括：①當(dāng)防火墻中含有少量規(guī)則時，由規(guī)則集轉(zhuǎn)化為對等體BT、PT或MFDD時，MFDD的構(gòu)建過程需要較多的時間。即在規(guī)則異常檢測過程中，MFDD的構(gòu)建時間占有比例較大。②由于FDD進(jìn)化模型產(chǎn)生的決策路徑數(shù)量高于BT和PT模型，增加了規(guī)則異常檢測時間。③當(dāng)防火墻中規(guī)則數(shù)量增加后，由于基于SMFDD的規(guī)則異常檢測算法只需要將半同構(gòu)體間對應(yīng)的決策路徑進(jìn)行一次比較，既可以判斷規(guī)則間的異常。BT或PT算法根據(jù)規(guī)則間異常關(guān)系，規(guī)則多次與決策路徑比較。綜上所述，當(dāng)防火墻中規(guī)則數(shù)量較多時，基于SMFDD的規(guī)則異常檢測算法優(yōu)于BT與PT算法。

圖8 PT、BT 及SMFDD 算法分析

圖9 PT、BT 及SMFDD 算法分析

實驗第3部分分析了優(yōu)化規(guī)則異常算法的性能。仿真結(jié)果如圖10所示，從中可以看出，隨著防火墻中規(guī)則數(shù)目的增加，該算法的執(zhí)行時間也在增加。對于兩個擁有3000條規(guī)則的防火墻，完成異常規(guī)則的修正需要大約16s，說明該算法具有較高執(zhí)行的效率。

圖10 SMFDD 邏輯與運算

4 結(jié)束語

本文提出的SMFDD 模型，在保持原始規(guī)則完整性、一致性、緊湊性，消除了獨立防火墻規(guī)則間異常。將規(guī)則序列號添加到SMFDD 中，通過SMFDD 間的比較操作，可以快速確定異常規(guī)則。另外，通過SMFDD 之間邏輯操作，定位到引起規(guī)則異常重疊或交叉域，修正分布式防火墻規(guī)則間異常，優(yōu)化防火墻規(guī)則。仿真結(jié)果表明，當(dāng)防火墻含有一定量規(guī)則時，基于SMFDD 的異常規(guī)則檢測算法可以顯著提高分布式防火墻規(guī)則間異常檢測效率，異常優(yōu)化算法實現(xiàn)快速優(yōu)化異常規(guī)則。

［1］Hu Hongxin，Gail－Joon Ahn，Kulkami K.Dectecting and resolving firewall policy anomalies ［J］.IEEE Transactions on Depend Computing，2012，9 （3）：318－331.

［2］Jeffrey A，Samak T.Model checking firewall policy configurations［C］／／Proceedings of the IEEE International Symposium on Polices for Distributed Systems and Network，2009：60－67.

［3］Acharya HB，Gouda MG.Firewall verification and redundancy checking are equivalent processing ［C］／／IEEE INFOCOM，2011：2123－2128.

［4］Liu AX，Gouda MG.Firewall policy queries ［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20（6）：766－777.

［5］ZHANG Li，CHEN Qinghua.The research on distributed firewall policy anomaly detection algorithm ［D］.Nanjing：Nanjing University of Science and Technology，2007 （in Chinese）.［張麗，陳清華.分布式防火墻策略異常檢測算法的研究［D］.南京：南京理工大學(xué)，2007.］.

［6］CHEN Weihui，CHEN Huaping，WANG Weiping.The research on firewall system of policy configuration ［D］.Hefei：University of Science and Technology of China，2007 （in Chinese）.［陳文慧，陳華平，王衛(wèi)平.防火墻系統(tǒng)策略配置研究［D］.合肥：中國科學(xué)技術(shù)大學(xué)，2007］.

［7］Gouda MG，Liu AX.Structured firewall design ［J］.Computer Networks，2007，51 （4）：1106－1120.

［8］Liu AX，Gouda MG.Complete redundancy removal for packet classifiers in TCAMs ［J］.IEEE Transactions on Parallel and Distributed Systems，2010，21 （4）：424－437.

［9］WANG Weiping，CHEN Wenhui，ZHU Weiwei，et al.Analysis of distributed firewall policy configuration mistakes and their detection ［J］.Journal of the Graduate School of the Chinese Academy of Sciences，2007，24 （2）：257－265 （in Chinese）.［王衛(wèi)平，陳文惠，朱衛(wèi)未，等.分布式防火墻策略配里錯誤的分析與檢測 ［J］.中國科學(xué)院研究生院學(xué)報，2007，24 （2）：257－265.］

［10］Chen F，Liu AX，Hwang J，et al.First step towards automatic correction of firewall policy faults ［J］.ACM Transactions on Autonomous and Adaptive Systems，2012，7 （2）：1－24.