[發明專利]一種基于遺傳算法的包匹配方法

在審

• 申請號: 201710091852.X
• 申請日: 2017-02-21
• 公開（公告）號: CN106817376A
• 公開（公告）日: 2017-06-09
• 發明（設計）人: 程實;王則林;潘建生;王昱;程顯毅
• 申請（專利權）人: 南通大學;南通先進通信技術研究院有限公司
• 主分類號: H04L29/06
• 分類號: H04L29/06;G06N3/12
• 代理公司: 北京科億知識產權代理事務所(普通合伙)11350
• 代理人: 湯東鳳

本發明提供一種基于遺傳算法的包匹配方法，包括如下步驟：(1)采用遺傳算法來進行特征選擇，選出相關特征位，去除冗余特征位和無關特征位；(2)對包規則庫中的規則進行分析和處理，精簡規則庫中的覆蓋規則和交叉規則。本發明通過運用遺傳算法去對防火墻的包規則庫進行降維處理，在降維的同時對包規則庫的冗余規則進行分析和處理，數值實驗顯示本發明提出的思想，無論包規則庫在什么規模下，都能改善包匹配算法的各項性能指標。

技術領域

本發明涉及網絡安全技術領域，具體涉及一種基于遺傳算法的包匹配方法。

背景技術

防火墻包匹配算法對防火墻的包轉發效率有著關鍵性的影響，近些年很多學者從不同角度提出了不同的包匹配算法，這些算法有的適應特定的環境，在特定的環境下性能很好，有些算法綜合性能較優，但具體的某個性能表現一般，有的算法只能處理特定的數據，有的算法需要特定的硬件支持，總之，所有的算法都有其優秀的一面，肯定也有它的缺陷，沒有一個算法能在所有的環境下，性能都是最優。包匹配算法根據其特點大體可分為基于軟件、基于硬件以及混雜的。現在常把包匹配算法分為五類：窮舉搜索匹配算法、分解匹配算法、決策樹匹配算法、元祖空間匹配算法以及基于智能的算法。

這些算法都是從算法本身出發去尋找解決問題的切入點，其中分解匹配算法是把整個維度進行分割，分而治之。窮舉搜索匹配算法是以犧牲時間、效率來節省空間。決策樹匹配算法需要消耗大量的無效空間。基于智能的算法還處于探索階段，如何把高維的問題降維成低維的問題，如何從控制論的角度去分析問題，上述各種匹配算法，理論上都有待于完善。

包匹配問題面對的是128位的IP地址，16位的端口號，8位的上層協議，相異的規則數目理論上應該是2¹²⁸*2¹²⁸*2¹⁶*2¹⁶*2⁸，實際上網絡設備中的規則數遠遠小于這個數，這就意味著296個特征位有許多冗余特征位，而相關特征的數目卻是一個很小的數值。因此，從包匹配問題的本身考慮，可以發現問題本身存在大量的冗余，可以考慮采用降維的思想去降低問題的復雜程度，附帶減少規則庫的規則間存在的冗余。

目前，降維有兩類主流技術：特征選擇和特征變換。特征選擇就是去尋找能有效對問題進行分類的特征子集，通過這些特征子集識別個體的能力和運用問題的所有特征識別問題的能力要存在一定程度的近似性。這種近似性也是衡量特征選擇是否確當的依據。特征選擇就是特征壓縮，壓縮掉冗余的特征，針對具體的問題就是屬性選擇或者變量選擇。對于特征子集的選擇方法主要有隨機的方法、啟發式方法、窮舉法以及智能優化的方法。

啟發式方法運用啟發式思想去尋找特征子集，這種方法不能估算收斂時間，也不能保證尋找的特征子集是最優的，一般尋找到的只是問題的較優子集。窮舉法是一種思想最單純的降維策略，對于N維的特征集合，有2N種可能的搜索子集，窮舉法可以尋找到問題的最優子集，但是從性能上講，由于開銷太大，它是不實際的一種降維方法。隨機的方法依據一定的概率來尋找問題的特征子集，性能較差。而智能優化方法是模擬生物進化或者種群的生活規律來實現問題優化，智能優化方法一般能尋找到問題全局最優解，能找到問題的最優特征子集，但是也僅限于找的問題的近似解。

發明內容

本發明的發明目的是解決上述技術問題，提供一種基于遺傳算法的包匹配方法，無論包規則庫在什么規模下，都能改善包匹配算法的各項性能指標。

為解決上述技術問題，本發明的實施例提供一種基于遺傳算法的包匹配方法，包括如下步驟：

(1)采用遺傳算法來進行特征選擇，選出相關特征位，去除冗余特征位和無關特征位；

(2)對包規則庫中的規則進行分析和處理，精簡規則庫中的覆蓋規則和交叉規則。

其中，上述的包匹配方法還包括步驟(2)之后的步驟(3)算法設計，具體步驟如下：