文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.191091
中文引用格式： 荊琛，傅曉彤，董偉，等. 基于Q-學習算法的有狀態網絡協議模糊測試方法研究[J].電子技術應用，2020，46(4)：49-52，56.
英文引用格式： Jing Chen，Fu Xiaotong，Dong Wei，et al. Research on fuzzing method of stateful network protocol based on Q-learning algorithm[J]. Application of Electronic Technique，2020，46(4)：49-52，56.
0 引言
協議漏洞挖掘是保證網絡通信安全的重要手段，傳統漏洞挖掘技術主要包括逆向分析[1-2]和模糊測試[3]。其中，模糊測試具有準確率高、不要求源代碼、適用性高等優點，是目前最常用的協議漏洞挖掘方法。有狀態網絡協議模糊測試技術的主要發展歷程如下。
最初，使用傳統的模糊測試方法對包括有狀態網絡協議在內的所有網絡協議進行測試，通過變異或生成的方法產生大量測試用例，將其作為協議實體程序的輸入，期望這些不尋常的輸入能引發協議實體異常，從中找到協議的安全漏洞[4-5]。這種測試方法對于有狀態網絡協議來說，當測試用例與協議實體狀態不匹配時，測試用例可能會被協議實體直接丟棄，測試用例有效性低[6]。
于是，研究人員提出了根據協議狀態機構造測試序列的有狀態網絡協議模糊測試方法[7-9]，主要包括3個步驟：(1)通過正常的報文交互，將協議實體引導至某個待測狀態，這些正常交互報文所構成的序列稱為前置引導序列；(2)向協議實體輸入報文類型與被測狀態相對應的測試用例，檢測是否存在異常，如果檢測到協議實體在處理測試用例后出現系統崩潰或者停止響應等異常情況，則保存錯誤現場以待進一步分析；(3)若未檢測到異常，還需按照特定順序輸入正常報文將協議實體引導至終止狀態，準備下一輪測試，這些正常報文所構成的序列被稱為回歸序列。這種測試方法提高了測試用例有效性，但前置引導序列和回歸序列這些輔助報文在測試過程中的重復交互降低了測試效率，且因是根據協議實體所處的協議狀態輸入報文類型相對應的測試用例，導致無法發現由報文異常輸入順序所引出的協議缺陷。
因此，本文針對有狀態網絡協議提出了一種基于Q-學習算法的模糊測試方法，不需要引導狀態的輔助類型報文，且能在確保一定的測試用例有效性前提下，引入報文異常輸入順序測試。
1 關于有狀態網絡協議的模糊測試
1.1 有狀態網絡協議
根據輸入報文相互之間是否存在關聯，網絡通信協議可分為無狀態協議和有狀態協議兩類[10]。無狀態協議是指報文發送方輸出的各個報文之間沒有關聯性，而對于有狀態協議，協議實體會記錄所接收到的報文信息，在處理報文后可能會出現協議狀態的變化。有狀態網絡通信協議通常采用確定有限狀態機(Deterministic Finite Automation，DFA)[11]作為協議交互的形式化描述模型。
將DFA定義為一個六元組M=(S，I，O，δ，β，T)，其中：S={s0，s1，…，sn}是有限狀態集合，其中s0表示為M的初始狀態，且在任意時刻，M只能處于某一狀態si，有限狀態機由s0狀態開始接收輸入；I={i1，i2，…，im}是有限輸入符號集合；O={o1，o2，…，om}是有限輸出符號集合；δ：S×I→S是狀態遷移函數；β：S×I→O是狀態輸出函數；T是終結狀態集合。當DFA應用于網絡協議描述時，I表示協議實體可接受并正常處理的輸入報文類型集合，O表示協議實體輸出的報文類型集合，以M表示協議狀態機。
以FTP協議[12]狀態機為例，其輸入輸出報文類型的抽象符號如表1所示，M包括8個狀態，狀態集合S={s0，s1，s2，s3，s4，s5，s6，s7}。狀態機M如圖1所示，其中s0到s1的遷移表示為i1/o1，它表示協議實體處于s0狀態時，如果接收USER類型報文(用i1表示)，將輸出331類型報文(用o1表示)，同時協議實體狀態遷移至s1狀態。
1.2 關于有狀態網絡協議的模糊測試
在實施模糊測試時，協議實體對每個測試用例會給出相應的反饋信息[13]，例如當測試用例不能被正確地接收處理時，協議實體會通過響應報文的形式告知。當協議實體處于狀態si，輸入報文im，根據協議狀態機將協議在狀態si處理報文im后輸出的響應報文on稱為由狀態si與輸入im確定的期望響應報文，如果得到的輸出不是響應報文on，則稱之為由狀態si與輸入im確定的非期望響應報文；若根據協議狀態機，狀態si與報文im并無對應關系，則將得到的任何響應報文都稱為由狀態si與輸入im確定的非期望響應報文。另外，在測試時，若在設定時間閾值內未返回任何報文，也視為得到的是非期望響應報文。關于有狀態網絡協議的模糊測試，測試用例可以分為以下4類：
(1)第一類測試用例導致協議實體崩潰；
(2)第二類測試用例能夠被程序正確接收處理，可以引發協議實體狀態跳轉并輸出期望響應報文；
(3)第三類是導致協議實體輸出非期望響應報文的被協議實體直接丟棄的測試用例，沒有進行程序執行過程，不會引發協議實體程序異常和狀態的轉換；
(4)第四類是導致協議實體輸出非期望響應報文的引出協議實體缺陷的測試用例。
對網絡協議的模糊測試過程主要是為了發現能夠觸發協議實體異常的測試用例，對于確定的測試用例集，如何能讓這些測試用例在模糊測試過程中達到最佳效果？考慮降低第三類測試用例的出現率，提高第一、四類測試用例的出現率。關于一個測試用例，它是觸發協議實體異常的第一、四類測試用例，還是被程序正確處理的第二類測試用例，或是被丟棄的第三類測試用例？這與輸入該測試用例時協議實體所處的狀態密切相關。因此，考慮在測試時根據協議實體狀態選取測試用例。對協議實體的狀態推斷主要依據于協議實體的響應報文。對于在si狀態下輸入由im變異生成的測試用例，如果協議實體的響應報文是協議狀態si和輸入im所對應的期望響應報文，那么表明測試用例為第二類測試用例，被協議實體正常接收處理，協議實體狀態已經處于sj狀態，可以根據狀態sj選取測試用例進行下一步測試。如果協議實體的響應報文屬于協議狀態si和輸入im所對應的非期望響應報文，那么協議實體可能仍處于si狀態，也可能由于測試用例的作用，跳轉到狀態si之外的狀態。在這種情況下，需要輸入與狀態si相對應的正常輸入報文in，觀察協議實體的響應，如果響應報文是狀態si和輸入in所對應的期望響應報文，那么表明測試用例為第三類測試用例且此時協議實體已經被引導至sq狀態，繼續輸入根據狀態sq選取的測試用例進行測試；如果響應報文是狀態si和輸入in所對應的非期望響應報文，那么在輸入報文in之前，協議實體可能出現異常，表明測試用例為第四類測試用例，需要保存輸入數據以待進一步分析。
2 基于Q-學習算法的模糊測試方法
2.1 強化學習
強化學習是一種從環境狀態映射到動作的學習，目標是使智能體在與環境的互動過程中獲得最大累積獎賞[14]。強化學習把學習看作試探評價過程，如圖2所示，智能體根據環境狀態st選擇一個動作at作用于環境，環境在動作at的作用下轉移到狀態st+1，同時產生一個獎賞rt反饋給智能體，智能體再根據獎賞rt與狀態st+1選擇下一個動作，選擇原則是使獎賞最大化。
強化學習的目的是尋找一個策略π：S→A，使得每個狀態s的值函數Vπ(s)或狀態-動作值函數Qπ(s，a)達到最大?！爸岛瘮怠迸c“狀態-動作值函數”分別表示指定“狀態”上以及指定“狀態-動作”上的累積獎賞[15]。
Q-學習算法[16]是一種異策略時序差分強化學習算法，Q-學習算法中狀態-動作值函數采用實際Q值增量式更新，對于狀態-動作對(s，a)的值函數Q(s，a)，根據每次采樣得到的立即獎賞r進行一次更新：
2.2 基于Q-學習算法的有狀態網絡協議模糊測試方法
在1.2小節，已經提出根據協議實體狀態選取測試用例的思想。由于主要是想通過輸入報文類型與被測狀態不對應的測試用例引入報文異常輸入順序測試，提高漏洞挖掘能力，因此，考慮根據協議實體狀態選擇報文類型，然后根據報文類型選取測試用例進行測試。那么，應該以何種策略來根據協議實體狀態選擇報文類型，以使得在引入報文異常輸入順序測試后仍能確保一定的測試用例有效性呢？這一問題可以通過制定恰當的獎賞規則轉化為強化學習中尋找策略π的問題來加以解決，下面就通過Q-學習算法來解決該問題。
(1)狀態集合
S={s0，s1，…，sn}，即協議的狀態集合。
(2)動作集合
A={a1，a2，…，am}={i1，i2，…，im}，即協議的輸入報文類型集合。
(3)動作探索策略
Q-學習通過探索-利用過程發現最優獎賞，“利用”過程選擇最大Q值所對應的輸入報文類型，“探索”過程則是隨機選擇輸入報文類型以防止發現不了最優獎賞。本文采用“
-貪婪探索策略”，在協議狀態s下以小概率
隨機選擇輸入報文類型，以概率1-
選擇具有最大Q值的輸入報文類型。
(4)立即獎賞
在協議狀態s下選擇報文類型為a的測試用例進行測試后，根據測試用例的類別確定狀態-動作對(s，a)的立即獎賞r。
根據協議實體狀態s，依據“
-貪婪探索策略”選擇報文類型為a的測試用例對協議實體進行測試。輸入測試用例后，通過觀察協議實體是否崩潰判斷測試用例是否為第一類測試用例；通過響應報文分析協議實體狀態并區分第二、三、四類測試用例。根據測試用例的類別確定狀態-動作對(s，a)的立即獎賞r，通過獎賞r更新Q值與策略π，降低第三類測試用例的出現率，提高第一、四類測試用例的出現率。基于Q-學習算法的有狀態網絡協議模糊測試方法描述如下：
(1)建立狀態空間S和動作空間A；
(2)初始化Q值表和策略π；
(3)初始化協議實體狀態至s0；
(4)依據“
-貪婪探索策略”，根據協議實體當前狀態s選擇報文類型為a的測試用例輸入協議實體；
(5)在協議實體處理測試用例后，觀察協議實體反饋信息，分析協議實體當前狀態，判斷測試用例類別，確定狀態-動作對(s，a)的立即獎賞r；
(6)更新Q值表；
(7)更新策略π；
(8)若測試用例為第一、四類測試用例，記錄異常后跳轉至步驟(3)；若協議實體當前狀態為協議終結狀態，跳轉至步驟(3)；否則跳轉至步驟(4)。
3 實驗與分析
3.1 實驗建立
Sulley[17]是目前較為成熟的模糊測試框架，有對有狀態網絡協議進行模糊測試的完整測試方案。本文方法Q-Fuzzing 將與Sulley按照以下描述場景進行仿真實驗對比：以FTP協議實體作為測試對象，兩種方法均采用由Sulley變異策略生成的測試用例，測試用例的漏洞挖掘效力相當。
3.2 實驗結果分析
3.2.1 測試效率評估
測試效率是指單位時間輸入的測試用例數量，用向被測協議實體輸入的測試用例個數與發送報文的總數的比值
值來衡量測試效率，
值的數學表達式為：
=∑A/∑m，其中，∑A表示輸入的測試用例總數，∑m表示發送報文的總數?！艫一定時，
值越大，說明發送輔助類型的報文越少，單位時間輸入的測試用例數量越高，測試效率越高。在測試過程中，Q-Fuzzing與Sulley的
值與輸入的測試用例總數∑A的關系如圖3所示。
Sulley采用完善的引導機制，隨著測試路徑的深入，前置引導序列等輔助報文的比重越來越大，
值越來越低。Q-Fuzzing雖在分析協議實體狀態時存在一定的輔助報文交互，但是該方法不需要引導狀態的輔助報文，輔助報文的比重較低，
值相對較高。
3.2.2 測試用例有效性評估
假設輸入的某個測試用例沒有被協議實體直接拋棄，而是進行程序執行過程，那么稱該測試用例為有效完成測試的測試用例(簡稱為有效測試用例)。測試用例有效性是指一個測試用例為有效測試用例的概率，以有效測試用例個數與輸入的測試用例總數的比值φ表示測試用例有效性，φ的數學表達式為：φ=∑Ac/∑A，其中，∑Ac表示有效測試用例總數，∑A表示輸入的測試用例總數。在測試過程中，Q-Fuzzing與Sulley的測試用例有效性φ與輸入的測試用例總數∑A的關系如圖4所示。
Sulley采用完善的引導機制，使得測試用例可以在協議實體處于對應狀態時進行輸入，測試用例有效性較高。Q-Fuzzing在測試初期，輸入報文時盲目性較大，存在很多被拋棄的測試用例，測試用例有效性低，但隨著在測試過程中實踐學習，測試用例有效性逐步提高，最終趨于穩定。
3.2.3 漏洞挖掘能力
漏洞挖掘能力是指在模糊測試正常執行條件下挖掘漏洞的數目。兩種方法挖掘漏洞數目如表2所示。
在漏洞挖掘能力方面，Q-Fuzzing效果好于Sulley。對于FTP 協議實體中存在的3個漏洞：(1)當協議實體狀態轉換序列為s0->s1->s2->s3->s4時，輸入變異的i5報文后，協議實體崩潰；(2)當協議實體狀態轉換序列為s5->s4->s5時，輸入與s5狀態并不對應的i12的變異報文后，協議實體崩潰；(3)當協議實體狀態轉換序列為s0->s1->s2->s3->s4->s5時，輸入變異的i7報文，協議實體出現狀態異常遷移，協議實體既不處于s5狀態也不處于s6狀態。Q-Fuzzing挖掘出漏洞1、2、3，Sulley僅挖掘出漏洞1，未能挖掘出漏洞2、3。
根據測試效率與挖掘漏洞能力比較，相比于Sulley測試方法，本文測試方法Q-Fuzzing具有明顯的優勢，達到了預期的測試效果。
4 結論
本文提出了一種基于Q-學習算法的有狀態網絡協議模糊測試方法，通過反饋信息分析協議實體狀態，根據協議實體狀態和Q值選取測試用例進行測試。實驗結果表明，該方法不需要引導狀態的輔助類型報文，且能在確保一定的測試用例有效性下，進行報文異常輸入順序測試，顯著提高了測試效率和漏洞挖掘能力。在該方法中，協議狀態機的完整性以及學習算法中參數的設定對測試結果的影響很大, 因此，下一步有必要對協議狀態機以及參數的調節進行深入的研究。
參考文獻
[1] 程必成，劉仁輝，趙云飛，等.非標工業控制協議格式逆向方法研究[J].電子技術應用，2018，44(4)：126-129.
[2] 魏驍，劉仁輝，許鳳凱.基于靜態二進制分析的工控協議逆向分析[J].電子技術應用，2018，44(3)：126-130.
[3] 張雄，李舟軍.模糊測試技術研究綜述[J].計算機科學，2016，43(5)：1-8，26.
[4] SUTTON M，GREENE A，AMINI P.Fuzzing：brute force vulner-ability discovery[M].[S.l.]：Pearson Education，2007.
[5] 王穎，楊義先，鈕心忻，等.基于控制流序位比對的智能Fuzzing測試方法[J].通信學報，2013，34(4)：114-121.
[6] MUNEA T L，LIM H，SHON T.Network protocol fuzz testing for information systems and applications: a survey and taxonomy[J].Multimedia Tools & Applications，2016，75(22)：14745-14757.
[7] ZHAO J，CHEN S，LIANG S，et al.RFSM-fuzzing a smart fuzzing algorithm based on regression FSM[C].Eighth International Conference on P2P，Parallel，Grid，Cloud and Internet Computing.IEEE，2013：380-386.
[8] CUI B，LIANG S，CHEN S，et al.A novel fuzzing method for Zigbee based on finite state machine[J].International Journal of Distributed Sensor Networks，2014，2014(3)：1-12.
[9] 康紅凱，吳禮發，洪征，等.一種基于FSM的BGP-4協議模糊測試方法[J].計算機工程與應用，2017，53(6)：111-117.
[10] 張寶峰，張翀斌，許源.基于模糊測試的網絡協議漏洞挖掘[J].清華大學學報(自然科學版)，2009(s2)：2113-2118.
[11] NARAYAN J，SHUKLA S K，CLANCY T C.A survey of automatic protocol reverse engineering tools[J].ACM Computing Surveys，2015，48(3)：1-26.
[12] GASCON H，WRESSNEGGER C，YAMAGUCHI F，et al.Pulsar：stateful black-box fuzzing of proprietary network protocols[M].Security and Privacy in Communication Networks.Springer International Publishing，2015：330-347.
[13] 張洪澤，洪征，周勝利，等．基于協議狀態機遍歷的模糊測試優化方法[J]．計算機工程與應用，2020，56(4)：82-91.
[14] SUTTON R S，BARTO A G.Reinforcement learning：an introduction[M].Cambridge，USA：MIT Press，1998.
[15] 周志華.機器學習[M].北京：清華大學出版社，2016.
[16] WATKINS C J C H.Learning from delayed rewards[J].Robotics & Autonomous Systems，1989，15(4)：233-235.
[17] GitHub.Sulley[EB/OL].(2013-06-11)[2015-06-29]. https：//github.com/OpenRCE/sulley.
作者信息:
荊 琛1，2，傅曉彤1，董 偉2，趙云飛2
（1.西安電子科技大學 網絡與信息安全學院，陜西 西安710071；2.華北計算機系統工程研究所，北京102209）