閱讀筆記——《未知協議狀態機推斷技術研究綜述》

【參考文獻】盛嘉杰, 牛勝杰, 陳陽, 等. 未知協議狀態機推斷技術研究綜述[J]. 計算機與現代化, 2023 (05): 58.
【注】本文僅為作者個人學習筆記，如有冒犯，請聯系作者刪除。

摘要

協議逆向工程（PRE）描述了協議的行為邏輯，一般分為協議格式提取和狀態機構造2個步驟。
首先，本文介紹PRE的形式化定義和基本原則，并討論主要領域的具體要求。
其次，分析狀態機推理方法，并將其分為3種模式：聚類方法、狀態相關方法和輪詢狀態實體方法，然后從不同的角度比較算法的逆向能力和時間效率。
最后展望協議狀態機推理的發展趨勢。

摘要

1、引言

2、協議狀態機分析

2.1、定義

2.2、應用

3、協議狀態機推斷算法

3.1、聚類方法

3.2、狀態相關字段方法

3.3、輪詢狀態實體方法

4、狀態機算法分析

1、引言

協議是由2個或多個協議實體遵循以完成通信的一組規則，其包含3個基本要素：語法 (Syntax)、語義 (Semantics)、時序邏輯 (Temporal Logic)。
PRE是指在不依賴于協議描述的情況下，通過對協議實體的網絡輸入輸出、系統行為和指令執行流程進行監控和分析，提取協議語法、語義以及同步信息的過程。
PRE通常包含2個步驟：協議格式分析和狀態機推斷。格式分析包括：格式抽取和語義抽取。

2、協議狀態機分析

2.1、定義

協議狀態機是協議實體之間的交互行為。有限狀態機 (FSM)又稱為自動狀態機，它能自動確定該自動機的輸入輸出模型，假設存在唯一輸入輸出模型，那么就稱為確定有限狀態機 (DFA)。
一個DFA通常由六元組? $X=(Z,\Omega ,T,q_0,F,U)$ 組成，其中， $Z=\left \{ q_0,q_1,q_2,...\right \}$ 是有限狀態的集合， $\Omega$ 是字母表集合， $T$ 為狀態遷移函數， $q_0$ 為DFA的初始狀態， $F$ 為接收狀態集合， $U$ 為拒絕狀態集合。
一個協議狀態機可以描述為一種DFA的六元組，利用狀態轉移函數確定狀態機的轉移，利用初始狀態與接受狀態集合，作狀態機的化簡。
協議狀態機是協議逆向工程的最后一步，圖1為協議逆向工程的總體流程。
協議狀態機是協議狀態之間通過某些行為特征進行轉換的一種描述協議之間關系的模型，它往往呈現出圖或者樹的結構，節點代表狀態，相鄰節點間的邊則代表不同類型的報文片段，終止狀態通常用2個圈進行表示，如圖2所示。
- 在圖2中，狀態2通過不同的報文片段可以到達狀態3或者狀態 5，而狀態5通過特定的報文片段，則可以到達終止狀態6。

2.2、應用

模糊測試
- 模糊測試，是一種利用測試用例，發現軟件或者代碼漏洞的技術，在狀態機推斷完成后，可以在測試用例中應用。
協議重用
- 協議重用是在了解該協議的基礎上，利用一系列手段，達成應用的跨平臺和重用的過程。
無線網絡對抗
- 在無線網絡對抗中，獲取協議規范是很重要的，無線網絡在全世界有相當大的規模，不法分子常利用無線網絡進行攻擊。狀態機的分析能夠理解該行為是否符合正常行為，避免了一定的損失。

3、協議狀態機推斷算法

狀態相關字段指的是能夠標記協議邏輯的報文片段。而許多狀態機相關的論文都是基于狀態相關字段的處理，所以提取狀態相關字段方法的不同也就代表不同的狀態機推斷方法。
協議狀態機的構造主要基于通信數據幀中狀態相關字段的取值以及它們之間的順序關系，將獲取得到的狀態與相關算法結合，能自動生成協議狀態機。
對于狀態機的創新點，都聚集在提取狀態相關字段與狀態機優化方向，如圖3所示。
協議狀態機起始階段的發展，如圖4所示。

3.1、聚類方法

依據：報文格式的相似度。
聚類方法的具體任務：
- 按照聚類結果給每一條報文分配對應類型的標簽，最終能得到初始協議狀態機。
- 根據不同的協議狀態機化簡算法，對初始狀態機進行化簡，得到最終協議狀態機。
聚類方法存在的問題：
- 該方法會受到聚類算法本身復雜度的限制，并且在聚類過程中，生成幾個簇（報文類型的種類）也是該算法需要自行解決的問題。
- 聚類方法能將語法相同的報文聚合在一起，但是對于語義相同的報文，并不能實現聚集。
以下是各個聚類方法的具體介紹。
- PEXT是一種協議狀態機的推斷方法，并寫成了工具。該方法首先利用了LCSS方法把獲取到的報文進行聚類，其次用群集標識標記每個數據包，并將數據包的報文分開成為單獨的流。最后定義了相同順序的序列歸納于同一個狀態，最大公共非重疊字串大于2作為篩選條件這一規則，將報文組合為一個狀態，按照上述方法提取了狀態機。此方法還利用了 “pull-out”與“pull-in”將狀態機進行化簡，此方法的缺點在于閾值需要手動設置，并且劃分的單獨流會形成冗余。
- Antunes提出了ReverX方法，此方法分為3個步驟：第一個步驟對每個狀態的訪問次數進行標注，利用了摩爾化簡公式對狀態機進行化簡，最終得到了普適化狀態機；第二個步驟對報文包的頭部信息聚類，比如網絡地址信息，這里有個約束，對報文選取的時間間隔不大于1h；第三個步驟通過因果關系與等價關系對狀態機約減，最終得到真實情況的狀態機。此方法缺點在于僅對文本協議有效，二進制協議效果較差。圖5為ReverX方法生成的FTP狀態機。【ANTUNES J，NEVES N，VERISSIMO P. Reverse engineering of protocols from network traces［C］// The 18th Working Conference on Reverse Engineering. 2011:169-178.】
- Comparetti利用了動態污點分析與程序上下文比對信息實現了自動提取狀態機技術，主要分為會話分析與報文聚類2個階段。在第一個階段中，記錄了動態污點分析得到的執行蹤跡，并按照格式劃分報文，再推斷報文格式。在第二個階段中，利用了PAM聚類算法進行分類，并提出了3種相似性，使推斷更為合理。再構建了初始狀態機。最后采用Exbar算法對相似的狀態進行合并，確定了最小狀態機。但是該算法未考慮當會話數量較多，狀態機化簡會有大量比較操作，這會降低算法的性能。【COMPARETTI P M，WONDRACEK G，KRUEGEL C，et al. Prospex: Protocol specification extraction［C］// The 30th IEEE Symposium on Security and Privacy Berkeley. 2009: 110-125.】
- 王辰等人針對現有狀態機推斷算法忽略了協議系統的輸入與輸出關系，提出了一種基于狀態融合的協議狀態機推斷方法。此方法依據會話樣本集，構建EPTT形式的初始狀態機。EPTT實質是一種聚類，將相同前綴序列聚集在一起。然后進行狀態匹配與融合，融合過程以EPTT作為原始Blue-Fringe算法的輸入，并對相似度的計算規則做了些補充，最后按照相似度從高到低排列進行融合。此方法雖然考慮到了協議間的輸入與輸出關系，但是協議關鍵字提取設定的閾值需要手動確定，這會加大協議關鍵字的不確定性。【王辰，吳禮發，洪征，等 . 一種基于狀態融合的協議狀態機推斷方法［J］. 解放軍理工大學學報(自然科學版)， 2015，16(4):322-329.】
- Wang 等人在文獻中提出了概率狀態機這一概念并提出了PEXT方法，圖6是此方法的流程圖。【Wang Y, Zhang Z, Yao D, et al. Inferring protocol state machine from network traces: a probabilistic approach[C]//Applied Cryptography and Network Security: 9th International Conference, ACNS 2011, Nerja, Spain, June 7-10, 2011. Proceedings 9. Springer Berlin Heidelberg, 2011: 1-18.】
  - 圖6方法主要分為以下幾個步驟：首先獲取協議報文的格式。作者通過搜索頻繁出現的字符串，提取協議格式報文，并利用了雙樣本K-S測試求出最小字段長度，得到了協議格式報文。其次推斷協議狀態消息。利用PAM算法將報文頭聚類得到集群，目的是對協議格式的報文進行分組，作者把集群的中心看作協議的狀態。作者利用閾值消除無效的狀態類型對，計算轉移概率，構建成狀態機。但是也存在著一些局限性，需要自己確定閾值，也沒有考慮語義信息。
- 王軍針對APTA樹的化簡做了一些改進，提出了EDSM的狀態機逆向方法。該方法首先構建一顆APTA樹，該樹用來存儲報文信息，相同的報文字段匯集在一個節點上，不同的則作為左右節點分散。這里的APTA樹，實際上也是一種聚類的方式。然后對Prospex的啟發式算法做了改進，充分考慮到字段之間的依賴關系，利用元組的方式對狀態進行標注。最后利用了EDSM算法對狀態進行合并，此方法使用事件驅動的狀態合并方法按照搜索策略進行狀態的合并。通過遍歷一個紅-藍框架，并將紅藍節點進行改變的方式，將狀態進行合并，最終得到協議狀態機。此方法雖然解決了Prospex的字段依賴的問題，但是仍然存在一些缺陷，APTA樹過于龐大，這會大大影響狀態機推斷的時間復雜度。【王軍 . 基于 EDSM 的二進制協議狀態機逆向［D］. 哈爾濱：哈爾濱工業大學，2016.】

3.2、狀態相關字段方法

依據：協議報文中通常會有相關報文片段能標識該報文的協議邏輯，例如TCP協議的ACK、FIN等標志位可以作為該報文的狀態相關字段。
任務
- 按照協議本身性質，用規則或者統計學方法提取出協議狀態相關字段。
- 按照不同的方式，將狀態相關字段結合數據結構構建出初始協議狀態機。
- 是根據不同的協議狀態機化簡算法，例如啟發式算法，對初始狀態機進行化簡，得到最終協議狀態機。
解決的問題
- 解決聚類方法能識別語法相同的報文，但忽略了語義相同報文的問題。
- 根據統計學或者數據挖掘的理論，去尋找狀態相關字段的方法，不會有聚類方法中存在報文類型種類不確定性的問題，所以它能夠更加精確地表示報文的狀態。
存在的問題
- 對于規則的定義依賴較大，規則定義的恰不恰當，直接會影響到狀態相關字段方法的準確性。
以下是各個狀態相關字段方法的具體介紹。
- Trifilo等人針對 PEXT 方法狀態標注不足做出了改進并提出了一種 BFS 方法。該方法首先根據相關字段在不同會話中能表現出相似的行為這種特點，識別出協議報文中最相關的字段。其次運用了“狀態分裂算法”對狀態進行了定義與轉換，主要分為 3 個步驟：1）初始狀態機的構造。由于相關字段狀態的值相同，但是有可能狀態不同，進行了二進制數的標注。 2）分裂。使用時間窗去檢查相同值代表的不同狀態，與初始創建的狀態機進行比較，創建新的狀態機。3）修剪。將不存在的轉換都刪除。但是此方法也存在一些缺點，方法只能體現出包含字節的相似度，不能體現一定的邏輯關系。【TRIFILO A，BURSCHKA S，BIERSACK E. Traffic to pro? tocol reverse engineering［C］// IEEE Symposium on Com? putational Intelligence for Security and Defense Applica? tions，.2009:1-8.】
- 孟凡治等人為了解決 BFS方法所存在的處理協議幀時有未對齊報文字段的缺陷，提出了一種新的解決方案。該方案在提取協議狀態相關字段前，利用了改進的漸進多序列對比算法將報文字段對齊。在提取狀態相關字段步驟時，根據同一個協議的不同通信通常有相似的行為邏輯這一特點，將對齊的報文字段利用字段取值分布的方式去計算對齊好的多條報文字段的取值，將這個取值稱之為DV，DV為0時，為協議報文的固定字段，所以舍棄，最后選擇 DV 中最小的值當作狀態相關字段。最后該方法根據時序關系，將狀態機進行重構，最終將不同的協議狀態圖合并，得到完整的協議狀態機轉移圖。該方法雖然解決了BFS未對齊報文字段的問題，但是仍然有一些缺陷，沒有考慮一些報文字段的順序性，忽視了字段與字段間的聯系。【孟凡治，劉淵，張春瑞，等 . 基于狀態相關字段識別的未知二進制協議狀態機逆向方法［J］. 電訊技術，2015，55 (4):372-378.】
- 閆小勇等人對目前構建前綴樹龐大和提取相關字段沒有順序性問題，提出了 BSMISRF 算法。該算法舍棄了 VDV 算法，采用了最長公共子序列尋找狀態相關字節，體現序列元素的順序相似性。再利用鄰接表構建初始狀態機，減少了APTA樹的大量比較操作。最后是狀態機的化簡，分為 2 個步驟，第一個步驟為確定轉移概率，將異常會話刪除。第二個步驟利用出入度將狀態機進行化簡，把并列的狀態合成為一個狀態。但是也存在一些局限性，當存在大量會話時，異常會話刪除會耗時耗力，而且此方法對字段切分的準確度要求較高。此方法實例如圖7所示。【閆小勇，李青，莫有權. 基于狀態相關字段的二進制協議狀態機推斷［J］. 計算機工程，2019，45(7):126-133.】
- 方敏之為了解決 VDV 方法與 BSMISRF 方法沒有考慮到狀態字段的時間順序性與不同會話之間的行為邏輯相似性這個問題，提出了LSISF方法。該方法在狀態相關字段提取方面分為了2個步驟，第一個步驟利用 LSISF 方法計算出每個字段的不同取值之間的平均編輯距離，然后設置閾值，選取比閾值小的字段作為候選狀態字段；第二個步驟計算出每個字段的權重與各個會話不同包中同一字段方差的均值 (Average of the Distribution of Variances，VDA)，然后通過計算V值也就是VDA與字段權重的比值來篩選出狀態相關字段。其次在獲取狀態相關字段基礎上，根據狀態轉移矩陣生成概率狀態機。此方法最后通過協議狀態存在順序與并列的關系，對協議狀態機進行化簡。方法雖然解決了 APTA 樹過于龐大與 BSMISRF 方法的問題，但是對與一些較少、不固定的報文字段而言，計算 VDA 的方式得到的狀態相關字段會比較不準確。【方敏之. 基于流量行為二進制協議逆向分析方法研究與實現［D］. 南京:東南大學，2021.】
- 黃笑言等人在文獻中利用統計學理論與時序關系構建出狀態轉換圖，首先在語義關鍵字提取方法中設置了3個步驟，第一個步驟通過分隔符劃為一個個文本塊 token，第二個步驟考察關鍵字在會話集的分布特征識別語義關鍵字，第三個步驟發現關鍵字在報文的偏移特征，可以驗證提取的語義關鍵字是否正確。其次利用鄰接矩陣表示各個報文類型序列之間的關系，若報文類型序列的順序是一致的，合并成一個狀態轉換，再通過強順序約束關系的狀態標注、會話必經路徑的狀態標注、對可選出現的報文類型集進行狀態標注方法進行狀態機構建。但是此方法也存在一些局限性，只通過報文類型序列相同進行狀態轉換不太全面，會話數較多時，構建鄰接矩陣比較復雜。【黃笑言，陳性元，祝寧，等 . 基于狀態標注的協議狀態機逆向方法［J］. 計算機應用，2013，33(12):3486-3489.】
- Lin 等人針對現有的協議狀態推斷方法模型都沒有注意到可以實時捕獲報文的特點，基于 EFSM 提出了一種 ReFSM 方法，該方法由 3 個步驟構成：1）消息類型識別。消息類型識別模塊使用 Apriori關鍵字分析來提取協議關鍵字，并在通過K-means算法將消息分組之前確定聚類數，每個組被視為不同的消息類型。2）FSM 構造和語義推導。通過構建 PTA 樹接受所有協議會話，并使用 K-尾合并算法化簡協議狀態機。3）提取包含觀察到的消息中消息字段值的子數據集，以便進一步分析以搜索報文中字段的相關性，由此推導的結果用于在EFSM中的每個轉換。最后通過比較生成的a樹與b樹是否有相同的結構完成狀態機的合并操作。雖然此方法在狀態相關字段提取方面，將狀態相關字段方法與聚類方法相結合，對提取出的協議狀態相關字段的精確度有了很大的提高，但是仍然有狀態爆炸的問題。【LIN Y R，LAI Y K，BUI Q T，et al. ReFSM: Reverse engi? neering from protocol packet traces to test generation by ex? tended finite state machines［J］. Journal of Network and Computer Applications，2020，171:102819.】
- Sun 等人提出了一種新的狀態機建模方法隨機協議有限狀態傳感器(Stochastic Protocol finitestate Transducer，SPT)，SPT 的主要職責是描述消息交互關系并分析記錄會話中的行為概率分布。該模型配備了統計信息，也能夠預測后續行為。其設計了一種名為Sptia PL的SPT學習方法，第一步處理初始報文，并提取狀態相關字段，提取狀態相關字段的方法時基于 3 種假設，第一，認為狀態相關字段在協議的頭部；第二，狀態相關字段為單個字段；第三，相同報文字段具有較強的統計相關性。然后通過 MIS 計算每個報文字段的值，MIS 較高則為狀態相關字段，再按照時間順序組成報文序列；第二步通過一系列分析從報文序列重建 SPT 模型，包括模型構建、狀態合并和在漸進學習過程中計算概率。最后，可以獲得描述未知協議行為邏輯的SPT模型，并用于分析其消息交互特征或預測其未來的消息或行為。在狀態機化簡時，運用了測試狀態兼容性的方法，將狀態進行合并。雖然此方法的時間復雜度（O（n））與空間復雜度（O（n））是最優的，解決了狀態爆炸的問題，但是此方法在復雜的網絡狀況下，比如存在異常報文或者攻擊報文的狀態位并沒有攜帶在報文的頭部，那么此方法會失效。【SUN F H，WANG S，ZHANG H L. A progressive learning method on unknown protocol behaviors［J］. Journal of Net? work and Computer Applications，2022，197(2):103249.】

3.3、輪詢狀態實體方法

依據：推斷過程中需要和協議實體交互來指導推斷。
方法：利用請求詢問和應答2個機制，結合正例樣本集與負例樣本集生成初始協議狀態機。正例樣本集表示與協議狀態交互后，能夠接受的報文；反例樣本集表示與協議狀態交互后，不能夠接受的報文。
輪詢狀態實體方法能夠實時與協議實體進行交互，生成的協議狀態機是不斷地向協議實體進行交流而得到最終的協議狀態機。
優點：能夠更加精確地生成協議狀態機。
存在問題：需要生成大量的詢問，增加了時間復雜度；獲取反例樣本集困難。
以下是各個輪詢狀態實體方法的具體介紹。
- Angluin提出了一種新的解決方案，對狀態實體進行輪詢的方法。L*算法假設存在一個Oracle，并在此基礎上可以回答等價詢問（equivalence query）與成員詢問（membership query）。L*算法通過修改一張觀察表，記錄請求詢問的結果，當結果為 1 則確定該狀態，否則淘汰。membership query 構建一個連續的觀察表，再生成一個候選狀態機，最后通過等價詢問，也是該文中所提的猜想，若一致，則終止判斷，否則提供反例。【ANGLUIN D. Learning regular sets from queries and coun? terexamples［J］. Information and Computation，1987，75(2): 87-106.】此外等價詢問使用 Valiant提出的近似識別標準，利用隨機抽樣，消除了T*最小充分性假設的限制。但是，此方法也存在一些缺點，此方法會產生大量的詢問，效率過低，把報文當作相互獨立的符號，忽略了報文之間的相關性。【VALIANT L G. A theory of the learnable［J］. Communica? tions of the ACM，1984，27(11):1134-1142.】
- 潘雁等人為了解決子類型無法對多個報文組合進行變異的問題，提出了一種漸進式的協議狀態機主動推斷方法。此方法考慮到字母表太大而導致算法性能降低的情況，首先將報文進行預處理，循環的將報文轉換成類型序列放入字母表中，并結合映射器推斷初始狀態機；然后針對已有的數據中大多數為正常報文數據，異常報文數據缺失的情況，將報文通過整數疊加、字節翻轉等方式，變異正常的報文；最后利用了基于前綴匹配的預響應機制，減少與協議實體互動的次數。但是此方法也存在一些問題，雖然用變異的手段擴充了樣本的多樣性，但是樣本空間的擴大對協議狀態機生成的時間效率而言，是大大的提高了。【潘雁，林偉，祝躍飛. 漸進式的協議狀態機主動推斷方法［J/OL］. 網絡與信息安全學報，2022（2022-05-09）［2022-05-30］. https://kns.cnki.net/kcms2/article/abstract? v=3uoqIhG8C45S0n9fL2suRadTyEVl2pW9UrhTDCdPD66 Sr0yZ-At6r3ZZ0-X5GzOOL6Lq-Z3hGgLSWHH-XlVloJx 0BboRkqHq&uniplatform=NZKPT.】