基于局部序列比對的漏洞挖掘技術研究

單路超，王建章，許德森，李東垣，趙 鵬，王國相，褚騰飛

(1.北京郵電大學, 北京 100876; 2.中華通信系統有限責任公司，北京 100070)

基于局部序列比對的漏洞挖掘技術研究

單路超1，王建章2，許德森2，李東垣2，趙 鵬2，王國相1，褚騰飛1

(1.北京郵電大學, 北京 100876; 2.中華通信系統有限責任公司，北京 100070)

針對網絡協議漏洞挖掘系統在網絡協議格式分析過程中使用全局序列比對技術效率不高的問題，結合網絡漏洞挖掘背景，對序列比對技術進行深入分析，提出了一種更為有效的基于局部序列比對算法的Fuzzing漏洞挖掘新方法。在獲取網絡協議格式分析的過程中，提高漏洞挖掘效率。仿真結果表明，該方法較全局序列比對方法在執行效率上具有較為明顯的優勢。

漏洞挖掘；Fuzzing；局部序列比對；算法

0 引言

隨著網絡協議的發展，在網絡應用中，網絡漏洞會出現在系統的軟件、硬件或協議中。這種漏洞的出現會給用戶帶來巨大的損失，因此漏洞挖掘被廣泛應用在網絡系統中。漏洞挖掘技術主要包括手動測試、Fuzzing算法分析[1]、靜態分析、比較分析和運行時分析技術。其中，Fuzzing算法由于其優良的性能而被廣泛應用在分布式網絡中。在對數據進行檢查時，運用的主要技術便是序列比對技術。序列比對，即按照實際需求，對某兩個序列的相似性進行考察，具有非常大的現實意義[2]。根據比對范圍，可以將序列比對劃分為全局比對和局部比對。現在的漏洞挖掘系統中大量運用全局序列比對技術來進行數據檢查。

Smith和Waterman利用動態規劃思想，將Needleman—Wunsch算法進行改進，提出了Smith—Wateman算法[3]，兩條序列中，整體的相似性往往都不是很大，可能只在某些局部區域有相似性，因此局部序列比對要比全局序列比對效率更高。

本文在Fuzzing網絡漏洞挖掘技術的常用框架基礎上，基于已有技術和整體框架，將部分序列比對算法應用于漏洞挖掘中的報文協議格式分析過程，最后針對本文提出的新型網絡漏洞挖掘系統，完成實驗環境的搭建和系統的配置，對改進后的網絡漏洞挖掘系統性能進行對比測試。

圖1 Fuzzing工作流程圖

1 網絡漏洞與Fuzzing技術

本文主要研究的漏洞挖掘中的模糊測試技術(Fuzzing)屬于灰盒測試技術，通過向測試目標程序發送大量的半有效數據并觀測輸出結果，來發現目標系統中存在的漏洞[4]。

在利用Fuzzing技術進行漏洞挖掘[5]時，首先確定測試對象，產生非預期數據構造測試用例，啟動模糊測試。然后對程序中出現的異常和錯誤進行檢測和分析。最后對于檢測出來的錯誤或異常，確定漏洞利用的可能性。Fuzzing的工作流程如圖1所示。

2 網絡協議部分分式漏洞挖掘技術的原理

通過構造網絡協議漏洞挖掘測試器，經過搭建系統、配置環境、構造測試用例、生成請求等過程，完成會話控制腳本。首先對網絡進行協議分析，構造測試用例保存在requests中，編寫會話控制腳本，最后開始Fuzzing測試。

在實際網絡協議漏洞挖掘[6]過程中，對網絡協議格式進行解析是非常重要的一個環節。基于這種思想，本文對傳統的模糊測試漏洞挖掘器進行改進，改進后的模糊測試漏洞挖掘器結構如圖2所示。

圖2 改進后的漏洞挖掘器結構圖

目前應用的網絡協議格式分析方法主要有兩種：基于軌跡的分析方法和基于數據流的分析方法。基于軌跡的分析方法主要是通過動態污點分析技術對報文的解析過程進行跟蹤。

本文主要對基于數據流的分析方法進行研究和改進。基于數據流的網絡協議分析方法主要通過對測試對象發送和接收數據包的屬性進行測試，得到網絡協議信息并構造測試用例。本文中的網絡協議格式分析過程包括4個子過程：采集數據流、初步處理、數據報文分類、協議格式分析。

在進行網絡協議格式解析之前，先獲取大量數據流，對數據流進行初步處理，獲得初始報文序列。然后利用匹配規則將得到的序列按照相似性進行分組，用于格式分析。最后，通過改進后的局部序列比對技術，對報文格式進行分析。其中對網絡數據流進行初步處理是網絡協議分析的重要前提。數據報文分類過程是整個網絡協議分析過程的第二個關鍵步驟，它分為3個子過程：報文分析、報文聚類、分類報文小組。網絡協議格式分析的最后一個環節是網絡協議格式獲取，前面的幾個步驟已經將輸入的網絡數據流分成不同的報文小組，通過對接收到的報文進行準確分類以及對比分析，最終可以得到報文的協議格式。在網絡協議獲取過程中，利用序列比對算法將數據報文對齊，對報文中含有的關鍵信息進行識別和分析，傳遞給Sulley框架，從而構造出測試用例，完成報文協議格式解析。

在網絡協議漏洞挖掘系統中，局部序列比對算法可以十分精確地找到序列間的最大匹配子序列，這是全局比對算法無法做到的。因此，本文在已有的網絡協議分析基礎上，提出一種使用局部序列比對算法的網絡協議格式獲取過程，提高序列比對效率，從而加快網絡協議格式的獲取速度。

全局序列比對著眼于兩個序列全長的最優比對，而局部序列比對則對序列之間的某個局部片段進行檢測和比對。本文提出的改進型網絡協議漏洞挖掘技術將Smith-Waterman動態規劃算法[7]引入到網絡協議格式分析過程中，并對改進后的漏洞挖掘系統性能進行研究和分析。

Smith-Waterman算法的主要思想為：對于給定的兩個序列M=m1m2m3…mn和N=n1n2n3…nm，設序列M和序列N的相似度用之前設計好的計分函數σ(m,n)來表示，對插入、刪除等操作賦予不同的分值[8]。對打分矩陣進行初始化，使矩陣首行和首列元素為0，即：

G(i,0)=G(0,j)=0

對于任意一個輸入序列，都可以表示成k×1矩陣的形式。在進行插入或刪除空格時，不能出現全為空格的一列。如果將對比之后的序列中的空格刪去，則能恢復成原序列。

對于兩個序列中的字母x、y，設字母取值于集合Z，在漏洞挖掘系統中，Z可以設置為A～Z字母集合。設計一個計分函數σ(x,y)，用來表示兩個序列對比過程的得分。

根據設計好的計分函數，通過遞歸方法得到每次對比的分數，存于得分矩陣G的相應位置上，初始化和計算得分矩陣的過程可以用如下等式表示：

在上述計算得分矩陣G的等式中，(1)表示初始化過程；(2)表示元素替換所帶入的計分函數數值，此時指針移動方向為指向右下方；(3)表示插入空格所對應的計分結果，此時指針移動方向為向下；(4)表示刪除空格所對應的計分結果，此時指針方向為向右。在進行序列比對時，將要比對的序列M和N寫在矩陣的兩側，根據設計好的計分函數，將序列M和N中的元素依次相互比較，將得分結果寫在打分矩陣G對應的位置上，某個位置的得分取元素替換、插入、刪除3種操作中的分值最大者，即按照左、上、左上3個來源方向結合計分函數σ(x,y)對同一個位置進行打分,分數最大值即為這個位置的得分。假設長度為i的序列，其插入損失為Wi，對變量1≤x≤|M|、1≤y≤|N|，打分矩陣的計分過程可以用如下公式表示：

Gi,j=max{Gi-1,j-1+σ(mi,nj)，max{Gi-x,j-Wx}，max{Gi,j-y-Wy}，0}

因為局部序列比對只是對兩個完整序列的局部區域進行比較，因此在打分過程中，將負數記為0不會影響最后比對結果。

打分過程完成后，開始進行回溯過程，尋找相似子序列。同樣因為局部序列沒有對兩個序列中的全部內容進行對比，因此回溯過程不需要從打分矩陣的最右下角處開始，只需要從得分最高的單元格開始即可。

回溯過程規則如下：

(1)從打分矩陣中的最高分單元格開始回溯，此處即為兩個比對序列中的相似片段末端。

(2)回溯方向有3個：上、左上、左。回溯到這3個方向對應的下一個單元格中最大分數的位置。如果出現分數一樣的情況，左上的優先級最高。

(3)重復執行(2)，直至無法找到下一個不為0的向上路徑。此時，按照回溯路徑寫出的序列即為M、N的最大相似子序列。

圖3 Smith-Waterman算法流程圖

圖3為Smith-Waterman算法的流程圖[9]。

Smith-Waterman算法在填充打分矩陣時，先將第一行和第一列元素置為0，并且用0代替負分。在進行回溯時，從右下角最大正分值處開始，尋找打分矩陣中每個正分值處的返回指針，直至無法找到下一個不為0的向上路徑為止，如圖4所示。回溯完成后，根據回溯路徑即可得到最優解。比如輸入的兩個序列為：ABCDEDC、EBDAEDB時，按照上述算法得到的比對結果為:BCD_ED;B_DAED。

圖4 回溯示意圖

3 算法的仿真和分析

為了驗證在網絡協議漏洞挖掘系統中采用局部序列對比技術比全局序列對比技術性能更好，本文在兩臺PC上搭建實驗環境，一臺提供服務器端和客戶端，另一臺與之進行通信交互。兩臺實驗PC連接如圖5所示。PC1又分為主機和虛擬機兩部分，分別負責構造測試用例和系統服務器部分功能。PC2主要負責產生網絡協議解析模塊需要的網絡數據流。實驗環境搭建好后，將PC1與PC2進行正常交互，捕捉網絡數據包，然后進行網絡協議格式解析，構造測試用例并完成會話腳本。接著啟動PC1中的虛擬機部分，進行相應的配置，開始模糊測試。本文設計的整個實驗系統應用在網絡協議FTP測試中，選用WarFTP服務器為測試對象，通過測量協議格式分析中進行序列對比的測試樣本長度及系統運行時間，可以得到改進后的網絡協議漏洞挖掘系統與傳統漏洞挖掘系統性能對比結果。

圖5 PC連接圖

本文以輸入序列程序運行時間作為判斷網絡協議漏洞挖掘系統性能的標準，對于輸入的固定長度報文序列，分別使用本文對比方法和傳統對比方法分析報文信息并構造測試用例，完成模糊測試。對于固定長度的相同報文序列，經過不同序列比對方式會導致整個漏洞挖掘系統的程序運行時間不同，對比結果如圖6所示。

圖6 對比結果圖

由圖6可以看出，本文提出的改進型網絡協議漏洞挖掘系統運行效率比傳統漏洞挖掘系統快，有效性和實用性更高。

4 結束語

本文介紹了現有網絡協議漏洞挖掘技術的工作流程及模塊結構，并對模糊測試的工作模式進行闡述。在此基礎上，對網絡協議漏洞挖掘過程中的網絡協議格式解析進行優化，結合局部序列對比技術，提高了整個網絡協議漏洞挖掘系統的工作效率，最后對改進的漏洞挖掘系統設計測試實驗，驗證了本文所提新型漏洞挖掘方法在執行效率上與傳統漏洞挖掘方法相比有一定的提高。

[1] 史記, 曾昭龍, 楊從保,等. Fuzzing測試技術綜述[J].信息網絡安全, 2014(3):87-91.

[2] 王櫻,李錫輝.多序列比對算法綜述[J].中國新通信, 2014(5):92-93.

[3] LEE S T, LIN C Y, CHE L H. GPU-based cloud service for Smith-Waterman algorithm using frequency distance filtration scheme[J]. BioMed Research International, 2013, 2013(1):721738.

[4] 劉大光.基于模糊測試的網絡協議自動化漏洞挖掘工具設計與實現[D]. 北京：北京大學, 2014.

[5] 裘志慶, 宦飛. 基于網絡爬蟲和Fuzzing的漏洞挖掘檢測工具[J]. 微型電腦應用, 2016, 32(3):73-76.

[6] 潘道欣, 王軼駿, 薛質.基于網絡協議逆向分析的遠程控制木馬漏洞挖掘[J]. 計算機工程, 2016, 42(2):146-150.

[7] LIU Y, HUANG W, JOHNSON J, et al. GPU accelerated Smith-Waterman[J]. Lecture Notes in Computer Science, 2006, 3994:188-195.

[8] GAO Y, HENDERSON M . Speeding up pairwise sequence alignments: a scoring scheme reweighting based approach[C]. Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering. Washington DC: IEEE Computer Society, 2007:1194-1198.

[9] IBRAHIM A, ELSIMARY H, ALJUMAH A. Novel reconfigurable hardware accelerator for protein sequence alignment using Smith-Waterman algorithm[J]. Ieice Transactions on Fundamentals of Electronics Communications & Computer Sciences, 2016, 99(3):683-690.

[10] Zhang Saidan, Zhang Luyong. Vulnerability mining for network protocols based on fuzzing[C]. Systems and Informatics (ICSAI), 2014 2nd IEEE International Conference,2014:644-648.

The research of vulnerability mining technology based on local sequence alignment

Shan Luchao1, Wang Jianzhang2, Xu Desen2, Li Dongyuan2, Zhao Peng2, Wang Guoxiang1, Chu Tengfei1

(1. Beijing University of Posts and Telecommunications, Beijing 100876, China; 2. China Communication System Co.,Ltd., Beijing 100070, China)

This paper studied the efficiency of Global sequence alignment technology in the network protocol vulnerabilities mining system, which is not very high when applied in the analytical process of network protocol format. Under the background of network vulnerability mining, this paper analyzed the sequences comparing technology and proposed a more effective method of vulnerability mining.Based on Fuzzing mining technology and the local sequence alignment,this new method improved the efficiency of vulnerability mining when analyzing the network protocol format.The simulation results showed that this new method has many obvious advantages in the execution efficiency compared with the traditional global sequence alignment method.Key words: vulnerability mining; Fuzzing; local sequence alignment; algorithm

TP309.2

A

10.19358/j.issn.1674- 7720.2017.03.001

單路超，王建章，許德森，等.基于局部序列比對的漏洞挖掘技術研究[J].微型機與應用，2017,36(3)：1-3，7.

2016-10-01)

單路超(1993-)，男，碩士研究生，主要研究方向：多協議網絡。

王建章(1964-)，男，高級工程師，主要研究方向：多協議網絡，云計算及大數據。

許德森(1957-)，男，研究員，主要研究方向：無線多協議網絡，天線技術等。