一種基於改良自動狀態機的網絡通信五元組快速匹配算法
2023-06-08 03:35:46 3
一種基於改良自動狀態機的網絡通信五元組快速匹配算法
【專利摘要】本發明公開了一種基於改良自動狀態機的網絡通信五元組(源IP、目的IP、源埠、目的埠、協議號)快速匹配算法，所述算法包括：五元組單元分割模塊，用於構建失配碰撞域；混合自動狀態機模塊，用於實現點與段數據的統一匹配；通配符映射模塊，用於解決匹配中的通配符匹配問題；通配規則計算模塊，用於減小通配符映射造成的冗餘操作。本算法的特色在於：儘可能提取五元組中靜態參數構建普通自動狀態機，構建更大的碰撞域，對於段式參數，在自動狀態機後添加鍊表，形成混合自動狀態機結構，實現對段式參數匹配的支持；利用通配符映射，解決通配符匹配問題，並精確通配替換規則，減少冗餘計算。本發明算法可廣泛應用於入侵檢測系統、網絡黑白名單庫、網絡數據分析等產品中。
【專利說明】—種基於改良自動狀態機的網絡通信五元組快速匹配算法
【技術領域】
[0001]本發明屬於網絡通信領域，特別涉及一種基於改良自動狀態機的網絡通信五元組快速匹配算法。
【背景技術】
[0002]隨著計算機科學技術的發展，尤其是網際網路技術的發展，網絡通信技術變得愈發重要。網絡通信技術中，一般通過比對網絡通信信息(網絡通信五元組，即源IP、源埠、目的IP、目的埠、協議號)的一致性，來監控通信實體間的通信源信息和目的信息，進而判斷其是否異常。尤其在入侵檢測防禦領域，系統需要配置一些網絡通信黑名單庫(規則庫)或者白名單庫，以對經過某個網絡通信節點的網絡信息進行監控，判斷其是否在黑名單和白名單庫中，從而採取相應的措施。
[0003]目前主流的通信信息系統中都用到了多模式匹配算法來完成上述任務。AC、ACBM、WM等都是成熟的多模式匹配算法。這些算法的特點是匹配時間效率不與模式(規則)庫的數據量有關係，而只與待匹配數據量有關，提高了在模式庫信息量非常大情況下的匹配效率，但同時也存在算法的存儲空間消耗隨匹配單元值取值範圍增大而激增的缺點。
[0004]典型的網絡通信系統中，一般規則為單點信息(五元組參數均為定值)組成。同時，規則庫信息(IP、埠)還存在通配和數據段的情況。如在一個通信系統中，不需要關注源IP而只需要關注除源IP以外的其他信息，通常做法是將源IP設置為通配，表示任意IP都可以匹配，其他信息依照實際情況填寫。又如，在一個通信系統中，只關注源IP的某一個段區間，源IP的其他段不需要關注，則通常做法是將網絡通信五元組中源IP填寫為段數據，具體格式如[192.168.0.1,192.168.0.128]。通常情況下，在IP中分段關注的情況比較多，而埠和協議號的分段情況較為少見。根據IP的特點，IP段存在於IP的尾部，IP段的長度越長，則IP段範圍越大，相反，則IP段所表示的範圍越小。通常情況下，通信系統中所關注的IP段範圍一般在IP的後16位，而IP段長度超出16位的情況較為少見。
[0005]多模式匹配算法不能很好的應用於含有IP段和通配符的五元組信息庫中，故目前主流的通信系統中，一般將規則庫分為只包含單點信息的規則庫、包含IP段信息的規則庫以及包含通配信息的規則庫，然後運用多模式匹配算法處理單點信息規則庫。對包含IP段信息或包含通配信息的規則庫，只能用遍歷規則庫或為規則庫做hash的方式對待匹配通信信息進行匹配，效率較低並且時間、空間效率不能兼顧。若想讓兩種規則庫的匹配都能運用多模式匹配算法，只能將包含IP段和包含通配的五元組信息拆分為單點五元組信息，再運用多模式匹配算法。這樣，雖然可以顯著的提高匹配的時間效率，但會更加凸顯多模式匹配算法消耗內存過大的缺陷。
[0006]故需要尋求一種可以處理含有IP段信息和含有通配信息的快速匹配算法，以更好的提高網絡通信信息匹配過程中的時間效率和空間效率。
【發明內容】
[0007]為解決網絡通信中通信五元組與規則庫匹配響應時間長，規則庫存儲空間大等缺點，本發明提出了一種基於改良自動狀態機的網絡通信五元組快速匹配算法，所述方案包括:
[0008]一種根據輸入五元組的結構，對待匹配數據進行分割與轉換的方法，其特徵在於，所述方法包括:
[0009]對不同類型的五元組數據分別進行分割轉換，為後期的匹配提供支持。
[0010]具體為:
[0011]設原始輸入五元組為ΠΜ單點源IP)、Port^源埠)、IP2(單點目的IP)、Port2 (目的埠)、Protocol (協議號)或[IP11, IP12](段源 IP)、Port1 (源埠)、[IP21,IP22](段目的 IP)、Port2 (目的埠)、Protocol (協議號)。
[0012]其中，如果五元組中的某個IP為段IP，則將五元組中的其他IP同樣視為段IP，即如果五元組中其他IP為單點IP，則將其變換為[原單點IP，原單點IP]。
[0013]步驟I，針對含有通配符的輸入五元組，將通配符用數字O替換，如:某一條五元組中源IP為通配，具體為*、Portp IP2> Port2、Protocol O為通配符)，則替換後的五元組為O、Port」 IP2、Port2、Protocol。
[0014]步驟2，統一規則及待匹配五元組的格式。分割五元組中的IP以及埠號，各埠號分割為兩段，每段長度為8位，即將Port1分割為P!、p2，將Port2分割為p3、p4，ppp2、p3、P4長度均為8位，分割IP時存在如下兩種情況:
[0015]針對不含段式參數的五元組，將IP分割為四段，每段長度為8位，即將IP1分害為ipsec」 ipsec2、ipsec3、ipsec4,將 IP2 分割為 ipsec5、ipsec6、ipsec7、ipsec8 ；
[0016]針對含段式參數的五元組，先將IP分為兩段，每段長度為16位，一般情況下IP前16位為常量，將前16位再次分割為兩段，每段長度為8位，而後16位不再拆分，記為一個數值區間段。具體為，將段[IP11, IP12]分割為ipseCp ipsec2、[ipsec起始，ipsec結束](ipsec起始至ipsec IP後十六位)。當IP前16位不為常量時，將IP前16位分割擴展為多個前16位為定值的IP常量值。
[0017]步驟3，調整輸入五元組各元素的順序，將能夠在匹配時使待匹配輸入儘快失配的元素前置，使匹配過程中待匹配五元組在自動狀態機的失配率最高。調整方法為:將分割轉換後的五元組數據根據數據分布集中度由低到高排列，將協議號置於最後。一般情況下將源、目的IP的後16位數據後置，使得單點五元組和段五元組的前部數據均為不變的單點數據，五元組匹配過程中能夠儘快跳出自動狀態機失配而不會進入鍊表查找。
[0018]具體為:
[0019]對單點五元組數據(規則或待匹配數據)，
[0020]ipsec」 ipsec2、ipsec3、ipsec4、p」 p2、ipsec5、ipsec6、ipsec7、ipsec8、p3、p4、Protocol,
[0021]變換為，
[0022]P1' p2、p3、p4、ipsec」 ipsec2、ipsec5、ipsec6、ipsec3、ipsec4、ipsec7、ipsec8、Protocol ；
[0023]針對段五元組數據，
[0024]ipsec」 ipsec2、[ipsec源起始，ipsec源結束]、p」 p2、ipsec5、ipsec6、[ipsec 目的起始，ipsec 目的結束]、p3、P4> Protocol,
[0025]變換為，
[0026]P1' p2、p3、p4、ipseC1、ipsec2、ipsec5、ipsec6> [ipsec 源起始，ipsec 源結束]、p!、[ipsec目的起始，ipsec目的結束]、Protocol。
[0027]一種基於對五元組的分割與變換，構建混合自動狀態機的方法。其特徵在於，所述方法包括:
[0028]針對無段式參數的五元組,構建普通自動狀態機；
[0029]針對含段式參數的五元組,在已構建的自動狀態機中常量參數末尾點連接鍊表，鍊表中存儲數據為兩部分，一部分為以IP後16位段的上下限為參數的數據段參數，另一部分為協議號。形成一個混合自動狀態機，用於實現使用同一數據結構一次完成對五元組的匹配。
[0030]具體為:在構建自動狀態機時，如果出現數據段參數，則在常量參數構成的自動狀態機末尾連接一個鍊表，鍊表中以段的上下限為參數存儲所有數據段參數，並將協議號存儲入鍊表。形成一個混合自動狀態機。如規則中源IP為[192.168.0.1，192.168.0.253]，目的IP為192.169.0.254，協議號為TCP,則將兩個IP各自的前16位(192 168 192 169)輸入自動狀態機後，在169這個節點後添加鍊表，以[0.1,0.253]、[0.254，0.254]、TCP為參數存儲數據。
[0031]一種基於完整規則庫，構建通配擴展矩陣，並根據通配擴展矩陣，擴展待匹配五元組數據的方法，其特徵在於，所述方法包括:
[0032]根據完整五元組規則庫，構建通配符替換規則矩陣，以下簡稱擴展矩陣；
[0033]其中，分析通配符在五元組信息的分布情況，除協議號(其通配情況在匹配時特殊處理)之外的其他四個參數都可能出現通配符，則通配符在五元組中可能出現的情況總數為24 = 16種。每一種情況構成一個由4個元素組成的行向量，向量元素依次表示五元組中相應的IP、埠位置是否出現通配符。由代表16種通配分布情況的行向量組成一個完整的通配符分布情況矩陣。根據完整五元組規則庫中通配符分布情況，計算得出相應的通配分布行向量(完整通配符分布行向量的子集)組成擴展矩陣，再對此擴展矩陣進行進行簡化，去除不含I的行數，得到精簡的擴展矩陣。
[0034]具體為:
[0035]如通配替換後的規則為0.Χ.Χ.Χ，Χ.0.0.Χ，Χ.Χ.0.0，生成一個擴展矩陣如下，矩陣中M代表相應位置沒有通配符，I代表相應位置有通配符，則生成替換規則矩陣
■I MMM'
N= MllM ο.MM I 1.
[0036]根據生成的擴展矩陣，對待匹配五元組進行通配擴展；
[0037]擴展方法為，將待匹配五元組數據擴展為與擴展矩陣行數相同的含通配符的五元組數據組，並將原五元組自身加入擴展五元組數據組。通過五元組數據與擴展行向量的對照，將某些五元組數據中參數變為O。方法為，讀取每個擴展矩陣行向量，得到行向量中元素為O的位置信息,將每條五元組數據中相應位置變為O。
[0038]具體為:
I M M M ■
[0039]設替換規則為N= MllM ，待匹配五元組為A、B、C、D，E(E為協議號，
-MM11.不考慮通配問題，故N矩陣與P矩陣的前四列對應)，則通配擴展後的待匹配五元組為
OBCDE'
P= AOODE ο.ΑΒ00Ε.
[0040]一種基於通配擴展後的五元組數據和混合自動狀態機的快速匹配方法，其特徵在於，所述方法包括:
[0041]將待匹配五元組輸入混合自動狀態機進行匹配，匹配情況有兩種，一種是在鍊表層之前，一種是在鍊表層之後。
[0042]在鍊表層之前匹配時，按普通自動狀態機匹配，匹配成功則在進入鍊表層之後繼續匹配；匹配失敗，則跳出自動狀態機，說明待匹配五元組整體匹配失敗。
[0043]在鍊表層及鍊表層之後匹配，首先按普通自動狀態機匹配，直到成功匹配到最後一個節點；匹配失敗，則跳入鍊表層進行匹配。特殊的，當匹配到最後一個節點時，如果最後一個節點數據為0，則匹配成功，不為O則按普通自動狀態機匹配。
[0044]進入鍊表進行匹配，首先判斷待匹配五元組兩個IP的後16位是否均存在於鍊表參數區間內，其次判斷協議號是否匹配，特殊的，當鍊表中協議號為O時，則認為匹配成功，若失配則進入下一個鍊表節點繼續匹配，直到匹配成功或失配跳出。
[0045]本發明所提供的技術方案的有益效果是:
[0046]能夠使用同一數據結構一次完成對五元組的匹配。通過分割提取五元組中靜態參數構建普通自動狀態機，從而構建更多的碰撞域，保證儘快失配；針對五元組中段式參數，在自動狀態機後添加鍊表，實現對帶有段式參數五元組匹配的支持；通過通配符替換算法，可以實現五元組對通配符匹配的支持，並通過規定通配替換的計算規則，防止漏解並減少冗餘計算。
【專利附圖】
【附圖說明】
[0047]圖1是本算法基於改良自動狀態機的網絡通信五元組快速匹配的整體流程示意圖。
[0048]圖2是本算法基於對五元組的分割與變換，構建混合自動狀態機的示意圖。
[0049]圖3為本算法基於根據調整順序後的規則五元組，構建自動狀態機的流程示意圖。
[0050]圖4為本算法基於改良自動狀態機的網絡通信五元組快速匹配的整體流程示意圖。
【具體實施方式】
[0051]為使本發明之目的、技術方案和優點闡述更加清晰，下面將結合附圖與實際用例，對本發明做進一步的詳細描述。
[0052]圖1為本算法對於基於改良自動狀態機的網絡通信五元組快速匹配算法整體流程示意圖，共有四個關鍵模塊，每個模塊的具體功能與實現如下:
[0053]101本發明所述的根據輸入規則五元組的結構，對規則五元組進行分割轉換的方法具體如下:
[0054]針對不同類型的五元組數據分別進行分割轉換，首先判斷五元組中是否含有通配符，對含有通配符的五元組進行通配處理，通配處理後再判斷五元組中是否含有段式參數，對含有段式參數的五元組進行特殊分割處理，不含段式參數的五元組進行普通分割。
[0055]具體為:
[0056]步驟1，針對含有通配符的實際規則五元組，將通配符用數字O替換，如:某一條規則五元組為*、A、B、C、D (*為通配符)，則替換後的五元組為O、A、B、C、D。
[0057]步驟2，統一實際規則五元組的格式。分割五元組中的IP以及埠號，各埠號分割為兩段，每段為8位，分割IP時存在如下兩種情況:
[0058]針對不含段式參數的五元組，將IP分割為四段，每段長度為8位，如一條五元組的一個IP為192.168.0.254，分割後的IP成為192、168、0、254四個數據段；
[0059]針對含段式參數的五元組，將IP分割為兩段，每段長度為16位，一般情況下IP前16位為常量，將前16位再次分割為兩段，每段長度為8位，如一條實際規則五元組的一個IP 為 192.168.0.1 至 192.168.0.254，分割後的該五元組 IP 成為 192,168,0.1 至 0.254 三個數據參數，當IP前16位不為常量，將IP前16位分割擴展為多個前16位為定值的數據參數，再將前16位分割為每段長度為8位的數據段，如一條實際規則五元組的一個IP為192.168.0.1 至 192.169.0.254，則分割後的該五元組 IP 為 192,168,0.1 至 0.254，192、169,0.1 至 0.254。
[0060]步驟3，調整輸入五元組各元素的順序，構建更大的碰撞域。調整方法為:
[0061]針對單點五元組數據(規則或待匹配數據)ipseq、ipsec2、ipsec3、ipsec4>p1>p2>ipsec5、ipsec6、ipsec7、ipsec8、p3、p4、Protocol,變換為 ipsec」 ipsec2、ipsec5、ipsec6>P1^P2> p3、p4、ipsec3、ipsec4、ipsec7、ipsec8、Protocol。如一條分割後的規則五元組為 192、168、0、254、04、B0、121、14、88、76、07、DO、TCP，調整順序後的五元組為 04、B0,07, D0、192、168、121、14、0、254、88、76、TCP。
[0062]針對段五元組數據ipsec」 ipsec2、ipsec 源起始至 ipsec 源結束、ΡρΡ2、ipsec5、ipsec6、ipsec 目的起始至 ipsec 目的結束、p3、P4> Protocol,變換為 P1^ p2、p3、p4、ipsec^ ipsec2、ipsec5、ipsec6、ipsec源起始至ipsec源結束、p」 ipsec目的起始至ipsec目的結束、Protocol。如一條分割後的規則五元組為 192,168,0.1 至 0.254、04、B0、121、14、88.75 至 88.76、07、D0、TCP，調整順序後的五元組為 04、B0、07、D0、192、168、121、14、0.1 至 0.254,88.75 至 88.76、TCP。
[0063]102本發明所述的基於對規則五元組的分割與變換，構建混合自動狀態機的算法具體如下:
[0064]構建自動狀態機時，會出現兩種類型的五元組，一種為含段式參數的五元組，一種為普通五元組，本發明將兩種類型的五元組統一在一個混合自動狀態機中，具體操作如下:
[0065]針對無段式參數的五元組，構建普通自動狀態機；
[0066]針對含段式參數的五元組,在常量參數構成的自動狀態機末尾連接鍊表,鍊表中存儲數據為兩部分，一部分為以段的上下限為參數的數據段參數，另一部分為協議號。形成一個混合自動狀態機，用於實現使用同一數據結構一次完成對五元組的匹配。
[0067]在構建自動狀態機時，如果出現數據段參數，則在常量參數構成的自動狀態機末尾連接一個鍊表，鍊表中以段的上下限為參數存儲所有數據段參數，並將協議號存儲入鍊表。形成一個混合自動狀態機。如規則中源IP為192.168.0.1至192.168.0.253，目的IP為192.168.0.254，協議號為TCP，則將兩個IP各自的前16位輸入自動狀態機後，在168這個節點後添加鍊表，以0.1至0.253,0.254至0.254,TCP為參數存儲數據[0.1至0.2530.254至 0.254TCP]。
[0068]圖2為本算法基於對規則五元組的分割與變換，構建混合自動狀態機的示意圖。
[0069]103本發明所述的對待匹配五元組進行初始化的方法具體如下:
[0070]I)根據通配替換後的規則五元組，確定替換規則。
[0071]如通配替換後的規則為O、X、X、X、X，X、0、0、X、X，X、X、0、0、0，根據該規則生成簡單的替換規則矩陣，本發明採用的方法為，將規則中的數字O轉換為數字1，表示該位置還有通配符，其餘位置轉換為數字M，表示該位置不含有通配符，則生成替換規則矩陣
IMMM'
N= MllM ο -MM11.
[0072]2)根據生成的替換規則，對待匹配五元組進行通配擴展。擴展方法為，將待匹配五元組根據替換規則中的每一行進行擴展，需要轉換的位置只有替換規則中數字I的位置轉換為數字0，而數字O的位置，令待匹配五元組中的元素不變。
IMMM'
[0073]設替換規則為N= MllM ，待匹配五元組為A、B、C、D、E，則通配擴展後的待
OBCDE'
匹配五元組為p= AOODE。.A B O O 0.
[0074]最後將原待匹配五元組本身加入擴展匹配五元組，形成待匹配擴展五元組集合。
[0075]3)如101中的步驟2、步驟3操作。
[0076]104本發明所述的基於通配擴展後的五元組數據和混合自動狀態機的快速匹配方法，具體如下:
[0077]根據擴展後的多個子五元組組成的五元組集合，將其輸入混合自動狀態機進行匹配，匹配過程為:
[0078]將待匹配五元組輸入混合自動狀態機進行匹配，匹配情況有兩種，一種是在鍊表層之前，一種是在鍊表層之後。
[0079]在鍊表層之前匹配時，按普通自動狀態機匹配，匹配成功則在進入鍊表層之後繼續匹配；匹配失敗，則跳出自動狀態機，說明待匹配五元組整體匹配失敗。
[0080]在鍊表層及鍊表層之後匹配，首先按普通自動狀態機匹配，直到成功匹配到最後一個節點；匹配失敗，則跳入鍊表層進行匹配。特殊的，當匹配到最後一個節點時，如果最後一個節點數據為O (協議號的通配情況)，則匹配成功，不為O則按普通自動狀態機匹配。
[0081]進入鍊表進行匹配，首先判斷待匹配五元組兩個IP的後16位是否均存在於鍊表參數區間內，其次判斷協議號是否匹配，特殊的，當鍊表中協議號為O時，則認為匹配成功，若失配則進入下一個鍊表節點繼續匹配，直到匹配成功或失配跳出。
[0082]以下以上述過程確定參數為標準，對應用實例進行說明。
[0083]實施例1
[0084]設一個實際規則五元組為:
[0085]192.16.0.18,2000,192.168.0.1 至 192.168.0.254、2000、TCP, 192.167.0.18 至192.168.0.254、*、*、2000、UDP，192.16.0.18,2000,192.168.1.1、1200、TCP
[0086]待匹配五元組為:
[0087]192.168.0.18、1500、192.168.0.254、2000、UDP。
[0088]步驟1:首先判斷出規則五元組中含有通配符，將所有通配符進行通配處理，處理後的規則五元組為:
[0089]192.16.0.18,2000,192.168.0.1 至 192.168.0.254、1200、TCP, 192.167.0.18 至192.168.0.254、0、0、2000、UDP，192.16.0.18,2000,192.168.0.1 至 192.168.0.254、1200、
TCP。
[0090]步驟2:將通配處理後的規則五元組的埠分割為兩段，每段長度為8位，判斷五元組中存在段的情況，將五元組進行分割，對於192.168.0.1至192.168.0.254，將前16位與後16位分割，得到192.168,0.1至0.254兩段，再將前16位分割，成為192、168、0.1至0.254 ;針對 192.167.0.18 至 192.168.0.254 將其分割為 192.167.0.18 至 192.167.0.254和 192.168.0.18 至 192.168.0.254，再將前 16 位與後 16 位分割，得到 192.167,0.18 至0.254 和 192.168,0.18 至 0.254，一共四段，再將前 16 位分割，得至Ij 192,168,0.18 至 0.254和192、168、0.18至0.254，一共六段。不存在段情況的五元組則將IP分割為四段，每段長度為8位，最終得到分割後的實際規則五元組為192、16、0、18、07、7D、192、168、0.1至0.254、
04、BO、TCP, 192,167,0.18 至 0.254、0、0、0、0、0、0、07、7D、UDP，192,168,0.18 至 0.254、0、
0、0、0、0、0、07、7D、UDP，192、16、0、18、07、7D、192、168、1、1、04、BO、TCP。
[0091]步驟3:將轉換後的規則五元組進行順序的調整，規則五元組調整為:
[0092]07、7D、04、B0、192、16、192、168、0、18、0.I 至 0.254、TCP，0、0、07、7D、192、167、0、
0、0.18至0.254、0、0、UDP，0、0、07、7D、192、168、0、0、0.18至0.254、0、0、UDP，07、7D、04、B0、192、16、192、168、0、18、1、1、TCP。
[0093]步驟4:針對無段式參數的規則五元組,構建普通自動狀態機；針對含段式參數的規則五元組，在常量參數構成的自動狀態機末尾連接鍊表，鍊表中存儲數據為兩部分，一部分為以段的上下限為參數的數據段參數，另一部分為協議號。形成一個混合自動狀態機，具體參見圖3。
[0094]步驟5:對待匹配五元組進行初始化，具體操作過程為:
[0095]首先根據通配替換後的矩陣得到替換規則矩陣為N= [M I I M]，再根據通配替換規則，對待匹配五元組進行通配擴展，擴展後的待匹配五元組為P = [192.168.0.18 O O2000 UDP]，最後進行待匹配五元組的統一格式和調整順序的操作，得到初始化後的待匹配五元組 05、DC、07、7D、192、168、192、168、0、18、0、254、UDP。
[0096]步驟6:將待匹配五元組輸入混合自動狀態機進行匹配。發現待匹配五元組與替換後規則五元組中的0、0、07、7D、192、168、0、0、0.18至0.254、0、0、UDP匹配，即與實際規則五元組中的 192.167.0.18 至 192.168.0.254、*、*、2000、UDP 匹配，匹配成功。
[0097]圖4為上述快速匹配過程的整體流程示意圖。
[0098]本發明實施例所提供的技術方案，可廣泛應用於含有段式參數以及通配符規則的快速匹配，並可根據通配矩陣用於入侵檢測系統、網絡黑白名單庫、網絡數據分析等產品中。
[0099]本發明實施例中的具體步驟，可以通過軟體變成實現，相應的軟體程序可存儲於可讀取的存儲介質中，如光碟、硬碟、移動存儲介質等。
[0100]以上為本發明的具體實施例，但並不用以限制本發明，對於本【技術領域】的普通技術人員來說，凡在不脫離本發明原理的前提下，所做的任何修改、等同替換、改進等，均應包含在本發明的保護髮明範圍之內。
【權利要求】
1.一種根據輸入五元組的結構，對五元組數據進行分割與轉換的方法，其特徵在於，所述方法包括: 針對含有通配符的輸入五元組，將通配符用數字O替換； 分割五元組中的IP以及埠號，統一規則及待匹配五元組的格式； 調整輸入五元組各元素的順序，得到經過變換後的五元組規則數據，供後續使用。
2.如權利要求1所述的對五元組數據進行分割與轉換的方法，其特徵在於，針對含有通配符的輸入五元組，將通配符用數字O替換，具體為:某一條五元組中源IP為通配，如規則為 5KPort1'IP2、Port2、Protocol (* 為通配符),則替換後的五元組為(KPort1'IP2、Port2、Protocol ο
3.如權利要求1所述的對五元組數據進行分割與轉換的方法，其特徵在於，分割五元組中的IP以及埠號，統一規則及待匹配五元組的格式。具體為: 分割五元組中的IP以及埠號，埠號分割為兩段，每段長度為8位，分割IP時存在如下兩種情況: 針對不含段式參數的五元組，將IP分割為四段，每段長度為8位； 針對含段式參數的五元組，將IP前16位分割為兩段，每段長度為8位，而後16位不再拆分，記為一個數值區間段。具體為，將段區間[IP11, IP12]分割為ipseCpipseCy [ipsec起始，ipsec結束](ipsec起始至ipsec結束為IP後十六位)。
4.如權利要求3所述的含段IP的分割方法，當IP段信息越過IP第16位出現在IP前16位時，將IP前16位分割擴展為多個前16位為定值的IP常量值。
5.如權利要求1所述的對五元組數據進行分割與轉換的方法，其特徵在於，調整輸入五元組各元素的順序，得到經過變換後的五元組規則數據。具體為: 將能夠在匹配時使待匹配輸入儘快失配的元素前置，使匹配過程中待匹配五元組在自動狀態機的失配率最高。具體調整方法為:將分割轉換後的五元組數據根據數據分布集中度由低到高排列，將協議號置於最後。一般情況下將源、目的IP的後16位數據後置，使得單點五元組和段五元組的前部數據均為不變的單點數據，五元組匹配過程中能夠儘快跳出自動狀態機失配而不會進入鍊表查找。
6.一種基於對五元組的分割與變換，構建混合自動狀態機的方法。其特徵在於，所述方法包括: 將無段式五元組規則和含段式五元組規則統一構建混合自動狀態機。 針對無段式參數的五元組，構建普通自動狀態機； 針對含段式參數的五元組，在當前規則常量參數構成的自動狀態機末尾連接鍊表。
7.如權利要求6所述的構建混合自動狀態機的方法，其特徵在於，針對含段式參數的五元組,在當前規則常量參數構成的自動狀態機末尾連接鍊表。具體為: 鍊表中存儲數據為兩部分，一部分為以段的上下限為參數的數據段參數，另一部分為協議號，形成一個混合自動狀態機。在構建自動狀態機時，如果出現數據段參數，則在當前規則常量參數構成的自動狀態機末尾連接一個鍊表，鍊表中以段的上下限為參數存儲所有數據段參數，並將協議號存儲入鍊表，形成混合自動狀態機。如規則中源IP為192.168.0.1 ?192.168.0.253，目的 IP 為 192.169.0.254，協議號為 TCP,則將兩個 IP 各自的前16位(192168192169)輸入自動狀態機後，在169這個節點後添加鍊表，以0.1?0.253,0.254 ?0.254、TCP 為例，存儲形式為[0.1 ?0.253，0.254 ?0.254，TCP]。
8.—種構建通配擴展規則矩陣，並根據通配擴展矩陣，擴展待匹配五元組數據的方法，其特徵在於，所述方法包括: 根據完整五元組規則庫，構建通配符替換規則矩陣； 根據生成的替換規則矩陣，對待匹配五元組進行通配擴展。
9.如權利要求8所述的執行匹配的方法，其特徵在於，根據完整五元組規則庫，構建通配符替換規則矩陣。具體為: 針對每一條五元組規則,計算得出一個由4個元素組成的行向量，向量元素依次表示五元組中相應的IP、埠的通配符出現情況，如對應位置元素為通配符，則對應值為1，否則為某一統一非I定值M，將所有行向量組成替換規則矩陣。再對得到的矩陣進行簡化，去除不含I的行向量，得到精簡的由通配分布行向量組成擴展矩陣，此矩陣內行向量即為所有的通配替換規則，而此矩陣行數即為一條待匹配規則要擴展的通配擴展五元組個數。
10.如權利要求8所述的執行匹配的方法，其特徵在於，根據生成的替換規則矩陣，對待匹配五元組進行通配擴展。具體為: 將待匹配五元組數據擴展為含O的五元組數據組，數組個數與擴展矩陣行數相同。通過待匹配五元組數據與擴展矩陣每個行向量的對照，將待匹配五元組數據中相應參數變換。具體為:讀取擴展矩陣的每個行向量，得到行向量中元素為I的位置信息，將待匹配五元組數據中相應位置變為0，生成一條待匹配五元組擴展副本，依次進行，直至生成全部待匹配五元組擴展副本。
I MMM' 設替換規則為N= MllM ，待匹配五元組為A、B、C、D，E，則通配擴展後的待匹配.M M I 1.0BCDE'五元組為P= AOODE。.ΑΒ00Ε.
11.一種基於通配擴展後的五元組數據和混合自動狀態機的快速匹配方法，其特徵在於，所述方法包括: 將待匹配五元組(包括原五元組及其擴展形式)輸入混合自動狀態機進行匹配，匹配情況有兩種，一種是在鍊表層之前的匹配，一種是在鍊表層之後的匹配。 在鍊表層之前匹配，按普通自動狀態機匹配，匹配成功則在進入鍊表層之後繼續匹配；匹配失敗，則跳出自動狀態機，說明待匹配五元組整體匹配失敗。 在鍊表層之後匹配，首先按普通自動狀態機匹配，直至成功匹配到最後一個節點；匹配失敗，則跳入鍊表層進行匹配。特殊的，當匹配到最後一個節點時，如果最後一個節點數據為0，則匹配成功，不為O則按普通自動狀態機匹配。 進入鍊表進行匹配，首先判斷待匹配五元組兩個IP的後16位是否均存在於相應鍊表參數區間內，段參數匹配成功後判斷協議號是否匹配。特殊的，當鍊表中協議號為O時，則認為匹配成功，若失配則進入下一個鍊表節點繼續匹配，直到匹配成功或失配跳出。
【文檔編號】H04L12/26GK104283736SQ201410393270
【公開日】2015年1月14日 申請日期:2014年8月3日 優先權日:2014年8月3日
【發明者】朱永強, 朱正富, 楊光明, 鄭童瀚, 黃曉強, 秦疏婷 申請人:成都網安科技發展有限公司