[發明專利]一種基于字典樹剪枝搜索的協議關鍵字識別方法

有效

• 申請號: 201611051833.6
• 申請日: 2016-11-23
• 公開（公告）號: CN106713273B
• 公開（公告）日: 2019-08-09
• 發明（設計）人: 衣龍騰;齊維孔;周鈉;李明;劉曉暉
• 申請（專利權）人: 中國空間技術研究院
• 主分類號: H04L29/06
• 分類號: H04L29/06;G06F16/22
• 代理公司: 中國航天科技專利中心 11009
• 代理人: 陳鵬

一種基于字典樹剪枝搜索的協議關鍵字識別方法，首先獲取需要識別的數據流，將數據流中數據存入循環隊列buffer，對buffer中字符串記進行掃描，生成字典樹中分支，在每次字典樹中分支生成過程中，當滿足剪枝條件時計算各個節點的剪枝閾值進行字典樹剪枝，最后獲取精煉比例PurifyRate，根據精煉比例PurifyRate得到關鍵字，完成關鍵字識別。本發明方法通過引入字典樹剪枝算法，解決了使用傳統字典樹算法進行協議關鍵字識別時使用的存儲空間過大的缺陷，具有提高了計算機的空間利用效率的優點，具有較好的使用價值。

技術領域

本發明涉及一種關鍵字識別技術，特別是一種基于字典樹剪枝搜索的協議關鍵字識別方法。

背景技術

協議逆向工程是指在不依賴于協議描述的情況下，通過對協議實體的網絡輸入輸出、系統行為和指令執行流程等信息進行監控和分析，提取協議語法、語義和工作流程。協議逆向分為格式逆向和狀態機逆向兩大類。在格式逆向中，對協議中關鍵字的識別和提取是一項基本而重要的工作。協議的關鍵字是指在協議傳輸單元，即報文中，由協議規范所規定的對通信的控制起關鍵作用的信息，一般會頻繁地出現在通信數據流中，現有的對協議關鍵字進行識別的方法主要有以下幾種：

(1)基于多序列比對的協議關鍵字識別

在協議格式逆向的工作中，Beddoe首先將生物信息學中的多序列比對(MultipleSequence Alignment，MSA)算法引入到工程中，并嘗試獲得報文的結構信息。在生物信息學中，通過對多個DNA序列進行比對，可以發現某序列片段的功能、結構和進化信息。具體地說，多序列比對針對給定的多個字符串，通過對每個字符串分別添加、刪除字母或加入空格，使它們具有最大的相似性。與此類似，通過比對相同格式的不同報文實例，可以識別報文中的不變字段與可變字段，從而初步獲得報文結構信息。Beddoe等人利用構造系統樹的啟發式方法引導多序列比對的執行，有效地降低了算法的時間復雜度，提高了執行的效率。該方法的主要缺點在于，該方法對于緊湊、簡單的報文識別效果較好，對于復雜、冗余字段較多的報文，其效率和準確度較低。

(2)基于報文內容變化分布特征的協議關鍵字識別

Trifilo等人提出了基于報文內容變化分布特征的報文格式挖掘方案。具體來說，首先以字節為單位獲得每次會話過程中，每個字節在多個報文中取值的頻率分布。然后以字節為單位獲得多次會話過程中，每個字節的頻率分布。根據頻率分布推斷出哪幾個字節屬于關鍵字或固定字段，哪幾個字節屬于參數字段。然而，這種方法存在兩點不足：第一，有的字段寬度是變化的，如果在某個位置出現“錯位”的情況，則后面的統計信息是沒有意義的；第二，判斷字段變化范圍的閾值是經驗值，缺乏客觀性。

(3)基于字典樹的協議特征字挖掘

字典樹又稱單詞查找樹、Trie樹，是一種樹形結構，也是一種哈希樹的變種。它常常被應用于統計，排序和保存大量的字符串，其查找效率優于哈希樹，所以經常被搜索引擎系統用于文本詞頻統計。字典樹的根節點不包含字符，除根節點外每一個節點都只包含一個字符，從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串，每個節點的所有子節點包含的字符都不相同。

對數據流進行協議特征字挖掘時，傳統的方法是設定一個固定大小的滑動窗口，將數據流開頭的單詞作為字典樹的第一個單詞，然后將窗口依次向后移動直到數據的結尾，將數據中出現的可能的單詞全部存儲在字典樹中。在字典樹建立好后，再次掃描整個數據，統計字典樹中的所有單詞出現的頻率，將出現頻率相對大的單詞，即協議特征字作為可能的關鍵字，在接下來的分析過程中將這些協議特征字作為分析目標，最終挖掘出真正的協議關鍵字。采用傳統的字典樹對協議關鍵字進行挖掘存在兩個重要的缺陷。

(1)存儲空間占用過大：對于常見的二進制通信數據流，若采用長度為n的滑動窗口進行協議特征字挖掘，可能的單詞組合最多有2的n次方種。隨著協議特征字長度的增加，用于存儲字典樹的空間呈指數增加。在滑動窗口的大小n較大時，計算機的存儲空間無法完整地存儲整棵字典樹。