單路超,王建章,許德森,李東垣,趙 鵬,王國(guó)相,褚騰飛
(1.北京郵電大學(xué), 北京 100876; 2.中華通信系統(tǒng)有限責(zé)任公司,北京 100070)
基于局部序列比對(duì)的漏洞挖掘技術(shù)研究
單路超1,王建章2,許德森2,李東垣2,趙 鵬2,王國(guó)相1,褚騰飛1
(1.北京郵電大學(xué), 北京 100876; 2.中華通信系統(tǒng)有限責(zé)任公司,北京 100070)
針對(duì)網(wǎng)絡(luò)協(xié)議漏洞挖掘系統(tǒng)在網(wǎng)絡(luò)協(xié)議格式分析過程中使用全局序列比對(duì)技術(shù)效率不高的問題,結(jié)合網(wǎng)絡(luò)漏洞挖掘背景,對(duì)序列比對(duì)技術(shù)進(jìn)行深入分析,提出了一種更為有效的基于局部序列比對(duì)算法的Fuzzing漏洞挖掘新方法。在獲取網(wǎng)絡(luò)協(xié)議格式分析的過程中,提高漏洞挖掘效率。仿真結(jié)果表明,該方法較全局序列比對(duì)方法在執(zhí)行效率上具有較為明顯的優(yōu)勢(shì)。
漏洞挖掘;Fuzzing;局部序列比對(duì);算法
隨著網(wǎng)絡(luò)協(xié)議的發(fā)展,在網(wǎng)絡(luò)應(yīng)用中,網(wǎng)絡(luò)漏洞會(huì)出現(xiàn)在系統(tǒng)的軟件、硬件或協(xié)議中。這種漏洞的出現(xiàn)會(huì)給用戶帶來巨大的損失,因此漏洞挖掘被廣泛應(yīng)用在網(wǎng)絡(luò)系統(tǒng)中。漏洞挖掘技術(shù)主要包括手動(dòng)測(cè)試、Fuzzing算法分析[1]、靜態(tài)分析、比較分析和運(yùn)行時(shí)分析技術(shù)。其中,F(xiàn)uzzing算法由于其優(yōu)良的性能而被廣泛應(yīng)用在分布式網(wǎng)絡(luò)中。在對(duì)數(shù)據(jù)進(jìn)行檢查時(shí),運(yùn)用的主要技術(shù)便是序列比對(duì)技術(shù)。序列比對(duì),即按照實(shí)際需求,對(duì)某兩個(gè)序列的相似性進(jìn)行考察,具有非常大的現(xiàn)實(shí)意義[2]。根據(jù)比對(duì)范圍,可以將序列比對(duì)劃分為全局比對(duì)和局部比對(duì)?,F(xiàn)在的漏洞挖掘系統(tǒng)中大量運(yùn)用全局序列比對(duì)技術(shù)來進(jìn)行數(shù)據(jù)檢查。
Smith和Waterman利用動(dòng)態(tài)規(guī)劃思想,將Needleman—Wunsch算法進(jìn)行改進(jìn),提出了Smith—Wateman算法[3],兩條序列中,整體的相似性往往都不是很大,可能只在某些局部區(qū)域有相似性,因此局部序列比對(duì)要比全局序列比對(duì)效率更高。
本文在Fuzzing網(wǎng)絡(luò)漏洞挖掘技術(shù)的常用框架基礎(chǔ)上,基于已有技術(shù)和整體框架,將部分序列比對(duì)算法應(yīng)用于漏洞挖掘中的報(bào)文協(xié)議格式分析過程,最后針對(duì)本文提出的新型網(wǎng)絡(luò)漏洞挖掘系統(tǒng),完成實(shí)驗(yàn)環(huán)境的搭建和系統(tǒng)的配置,對(duì)改進(jìn)后的網(wǎng)絡(luò)漏洞挖掘系統(tǒng)性能進(jìn)行對(duì)比測(cè)試。
圖1 Fuzzing工作流程圖
本文主要研究的漏洞挖掘中的模糊測(cè)試技術(shù)(Fuzzing)屬于灰盒測(cè)試技術(shù),通過向測(cè)試目標(biāo)程序發(fā)送大量的半有效數(shù)據(jù)并觀測(cè)輸出結(jié)果,來發(fā)現(xiàn)目標(biāo)系統(tǒng)中存在的漏洞[4]。
在利用Fuzzing技術(shù)進(jìn)行漏洞挖掘[5]時(shí),首先確定測(cè)試對(duì)象,產(chǎn)生非預(yù)期數(shù)據(jù)構(gòu)造測(cè)試用例,啟動(dòng)模糊測(cè)試。然后對(duì)程序中出現(xiàn)的異常和錯(cuò)誤進(jìn)行檢測(cè)和分析。最后對(duì)于檢測(cè)出來的錯(cuò)誤或異常,確定漏洞利用的可能性。Fuzzing的工作流程如圖1所示。
通過構(gòu)造網(wǎng)絡(luò)協(xié)議漏洞挖掘測(cè)試器,經(jīng)過搭建系統(tǒng)、配置環(huán)境、構(gòu)造測(cè)試用例、生成請(qǐng)求等過程,完成會(huì)話控制腳本。首先對(duì)網(wǎng)絡(luò)進(jìn)行協(xié)議分析,構(gòu)造測(cè)試用例保存在requests中,編寫會(huì)話控制腳本,最后開始Fuzzing測(cè)試。
在實(shí)際網(wǎng)絡(luò)協(xié)議漏洞挖掘[6]過程中,對(duì)網(wǎng)絡(luò)協(xié)議格式進(jìn)行解析是非常重要的一個(gè)環(huán)節(jié)。基于這種思想,本文對(duì)傳統(tǒng)的模糊測(cè)試漏洞挖掘器進(jìn)行改進(jìn),改進(jìn)后的模糊測(cè)試漏洞挖掘器結(jié)構(gòu)如圖2所示。
圖2 改進(jìn)后的漏洞挖掘器結(jié)構(gòu)圖
目前應(yīng)用的網(wǎng)絡(luò)協(xié)議格式分析方法主要有兩種:基于軌跡的分析方法和基于數(shù)據(jù)流的分析方法。基于軌跡的分析方法主要是通過動(dòng)態(tài)污點(diǎn)分析技術(shù)對(duì)報(bào)文的解析過程進(jìn)行跟蹤。
本文主要對(duì)基于數(shù)據(jù)流的分析方法進(jìn)行研究和改進(jìn)?;跀?shù)據(jù)流的網(wǎng)絡(luò)協(xié)議分析方法主要通過對(duì)測(cè)試對(duì)象發(fā)送和接收數(shù)據(jù)包的屬性進(jìn)行測(cè)試,得到網(wǎng)絡(luò)協(xié)議信息并構(gòu)造測(cè)試用例。本文中的網(wǎng)絡(luò)協(xié)議格式分析過程包括4個(gè)子過程:采集數(shù)據(jù)流、初步處理、數(shù)據(jù)報(bào)文分類、協(xié)議格式分析。
在進(jìn)行網(wǎng)絡(luò)協(xié)議格式解析之前,先獲取大量數(shù)據(jù)流,對(duì)數(shù)據(jù)流進(jìn)行初步處理,獲得初始報(bào)文序列。然后利用匹配規(guī)則將得到的序列按照相似性進(jìn)行分組,用于格式分析。最后,通過改進(jìn)后的局部序列比對(duì)技術(shù),對(duì)報(bào)文格式進(jìn)行分析。其中對(duì)網(wǎng)絡(luò)數(shù)據(jù)流進(jìn)行初步處理是網(wǎng)絡(luò)協(xié)議分析的重要前提。數(shù)據(jù)報(bào)文分類過程是整個(gè)網(wǎng)絡(luò)協(xié)議分析過程的第二個(gè)關(guān)鍵步驟,它分為3個(gè)子過程:報(bào)文分析、報(bào)文聚類、分類報(bào)文小組。網(wǎng)絡(luò)協(xié)議格式分析的最后一個(gè)環(huán)節(jié)是網(wǎng)絡(luò)協(xié)議格式獲取,前面的幾個(gè)步驟已經(jīng)將輸入的網(wǎng)絡(luò)數(shù)據(jù)流分成不同的報(bào)文小組,通過對(duì)接收到的報(bào)文進(jìn)行準(zhǔn)確分類以及對(duì)比分析,最終可以得到報(bào)文的協(xié)議格式。在網(wǎng)絡(luò)協(xié)議獲取過程中,利用序列比對(duì)算法將數(shù)據(jù)報(bào)文對(duì)齊,對(duì)報(bào)文中含有的關(guān)鍵信息進(jìn)行識(shí)別和分析,傳遞給Sulley框架,從而構(gòu)造出測(cè)試用例,完成報(bào)文協(xié)議格式解析。
在網(wǎng)絡(luò)協(xié)議漏洞挖掘系統(tǒng)中,局部序列比對(duì)算法可以十分精確地找到序列間的最大匹配子序列,這是全局比對(duì)算法無法做到的。因此,本文在已有的網(wǎng)絡(luò)協(xié)議分析基礎(chǔ)上,提出一種使用局部序列比對(duì)算法的網(wǎng)絡(luò)協(xié)議格式獲取過程,提高序列比對(duì)效率,從而加快網(wǎng)絡(luò)協(xié)議格式的獲取速度。
全局序列比對(duì)著眼于兩個(gè)序列全長(zhǎng)的最優(yōu)比對(duì),而局部序列比對(duì)則對(duì)序列之間的某個(gè)局部片段進(jìn)行檢測(cè)和比對(duì)。本文提出的改進(jìn)型網(wǎng)絡(luò)協(xié)議漏洞挖掘技術(shù)將Smith-Waterman動(dòng)態(tài)規(guī)劃算法[7]引入到網(wǎng)絡(luò)協(xié)議格式分析過程中,并對(duì)改進(jìn)后的漏洞挖掘系統(tǒng)性能進(jìn)行研究和分析。
Smith-Waterman算法的主要思想為:對(duì)于給定的兩個(gè)序列M=m1m2m3…mn和N=n1n2n3…nm,設(shè)序列M和序列N的相似度用之前設(shè)計(jì)好的計(jì)分函數(shù)σ(m,n)來表示,對(duì)插入、刪除等操作賦予不同的分值[8]。對(duì)打分矩陣進(jìn)行初始化,使矩陣首行和首列元素為0,即:
G(i,0)=G(0,j)=0
對(duì)于任意一個(gè)輸入序列,都可以表示成k×1矩陣的形式。在進(jìn)行插入或刪除空格時(shí),不能出現(xiàn)全為空格的一列。如果將對(duì)比之后的序列中的空格刪去,則能恢復(fù)成原序列。
對(duì)于兩個(gè)序列中的字母x、y,設(shè)字母取值于集合Z,在漏洞挖掘系統(tǒng)中,Z可以設(shè)置為A~Z字母集合。設(shè)計(jì)一個(gè)計(jì)分函數(shù)σ(x,y),用來表示兩個(gè)序列對(duì)比過程的得分。
根據(jù)設(shè)計(jì)好的計(jì)分函數(shù),通過遞歸方法得到每次對(duì)比的分?jǐn)?shù),存于得分矩陣G的相應(yīng)位置上,初始化和計(jì)算得分矩陣的過程可以用如下等式表示:
在上述計(jì)算得分矩陣G的等式中,(1)表示初始化過程;(2)表示元素替換所帶入的計(jì)分函數(shù)數(shù)值,此時(shí)指針移動(dòng)方向?yàn)橹赶蛴蚁路剑?3)表示插入空格所對(duì)應(yīng)的計(jì)分結(jié)果,此時(shí)指針移動(dòng)方向?yàn)橄蛳拢?4)表示刪除空格所對(duì)應(yīng)的計(jì)分結(jié)果,此時(shí)指針方向?yàn)橄蛴?。在進(jìn)行序列比對(duì)時(shí),將要比對(duì)的序列M和N寫在矩陣的兩側(cè),根據(jù)設(shè)計(jì)好的計(jì)分函數(shù),將序列M和N中的元素依次相互比較,將得分結(jié)果寫在打分矩陣G對(duì)應(yīng)的位置上,某個(gè)位置的得分取元素替換、插入、刪除3種操作中的分值最大者,即按照左、上、左上3個(gè)來源方向結(jié)合計(jì)分函數(shù)σ(x,y)對(duì)同一個(gè)位置進(jìn)行打分,分?jǐn)?shù)最大值即為這個(gè)位置的得分。假設(shè)長(zhǎng)度為i的序列,其插入損失為Wi,對(duì)變量1≤x≤|M|、1≤y≤|N|,打分矩陣的計(jì)分過程可以用如下公式表示:
Gi,j=max{Gi-1,j-1+σ(mi,nj),max{Gi-x,j-Wx},max{Gi,j-y-Wy},0}
因?yàn)榫植啃蛄斜葘?duì)只是對(duì)兩個(gè)完整序列的局部區(qū)域進(jìn)行比較,因此在打分過程中,將負(fù)數(shù)記為0不會(huì)影響最后比對(duì)結(jié)果。
打分過程完成后,開始進(jìn)行回溯過程,尋找相似子序列。同樣因?yàn)榫植啃蛄袥]有對(duì)兩個(gè)序列中的全部?jī)?nèi)容進(jìn)行對(duì)比,因此回溯過程不需要從打分矩陣的最右下角處開始,只需要從得分最高的單元格開始即可。
回溯過程規(guī)則如下:
(1)從打分矩陣中的最高分單元格開始回溯,此處即為兩個(gè)比對(duì)序列中的相似片段末端。
(2)回溯方向有3個(gè):上、左上、左。回溯到這3個(gè)方向?qū)?yīng)的下一個(gè)單元格中最大分?jǐn)?shù)的位置。如果出現(xiàn)分?jǐn)?shù)一樣的情況,左上的優(yōu)先級(jí)最高。
(3)重復(fù)執(zhí)行(2),直至無法找到下一個(gè)不為0的向上路徑。此時(shí),按照回溯路徑寫出的序列即為M、N的最大相似子序列。
圖3 Smith-Waterman算法流程圖
圖3為Smith-Waterman算法的流程圖[9]。
Smith-Waterman算法在填充打分矩陣時(shí),先將第一行和第一列元素置為0,并且用0代替負(fù)分。在進(jìn)行回溯時(shí),從右下角最大正分值處開始,尋找打分矩陣中每個(gè)正分值處的返回指針,直至無法找到下一個(gè)不為0的向上路徑為止,如圖4所示?;厮萃瓿珊螅鶕?jù)回溯路徑即可得到最優(yōu)解。比如輸入的兩個(gè)序列為:ABCDEDC、EBDAEDB時(shí),按照上述算法得到的比對(duì)結(jié)果為:BCD_ED;B_DAED。
圖4 回溯示意圖
為了驗(yàn)證在網(wǎng)絡(luò)協(xié)議漏洞挖掘系統(tǒng)中采用局部序列對(duì)比技術(shù)比全局序列對(duì)比技術(shù)性能更好,本文在兩臺(tái)PC上搭建實(shí)驗(yàn)環(huán)境,一臺(tái)提供服務(wù)器端和客戶端,另一臺(tái)與之進(jìn)行通信交互。兩臺(tái)實(shí)驗(yàn)PC連接如圖5所示。PC1又分為主機(jī)和虛擬機(jī)兩部分,分別負(fù)責(zé)構(gòu)造測(cè)試用例和系統(tǒng)服務(wù)器部分功能。PC2主要負(fù)責(zé)產(chǎn)生網(wǎng)絡(luò)協(xié)議解析模塊需要的網(wǎng)絡(luò)數(shù)據(jù)流。實(shí)驗(yàn)環(huán)境搭建好后,將PC1與PC2進(jìn)行正常交互,捕捉網(wǎng)絡(luò)數(shù)據(jù)包,然后進(jìn)行網(wǎng)絡(luò)協(xié)議格式解析,構(gòu)造測(cè)試用例并完成會(huì)話腳本。接著啟動(dòng)PC1中的虛擬機(jī)部分,進(jìn)行相應(yīng)的配置,開始模糊測(cè)試。本文設(shè)計(jì)的整個(gè)實(shí)驗(yàn)系統(tǒng)應(yīng)用在網(wǎng)絡(luò)協(xié)議FTP測(cè)試中,選用WarFTP服務(wù)器為測(cè)試對(duì)象,通過測(cè)量協(xié)議格式分析中進(jìn)行序列對(duì)比的測(cè)試樣本長(zhǎng)度及系統(tǒng)運(yùn)行時(shí)間,可以得到改進(jìn)后的網(wǎng)絡(luò)協(xié)議漏洞挖掘系統(tǒng)與傳統(tǒng)漏洞挖掘系統(tǒng)性能對(duì)比結(jié)果。
圖5 PC連接圖
本文以輸入序列程序運(yùn)行時(shí)間作為判斷網(wǎng)絡(luò)協(xié)議漏洞挖掘系統(tǒng)性能的標(biāo)準(zhǔn),對(duì)于輸入的固定長(zhǎng)度報(bào)文序列,分別使用本文對(duì)比方法和傳統(tǒng)對(duì)比方法分析報(bào)文信息并構(gòu)造測(cè)試用例,完成模糊測(cè)試。對(duì)于固定長(zhǎng)度的相同報(bào)文序列,經(jīng)過不同序列比對(duì)方式會(huì)導(dǎo)致整個(gè)漏洞挖掘系統(tǒng)的程序運(yùn)行時(shí)間不同,對(duì)比結(jié)果如圖6所示。
圖6 對(duì)比結(jié)果圖
由圖6可以看出,本文提出的改進(jìn)型網(wǎng)絡(luò)協(xié)議漏洞挖掘系統(tǒng)運(yùn)行效率比傳統(tǒng)漏洞挖掘系統(tǒng)快,有效性和實(shí)用性更高。
本文介紹了現(xiàn)有網(wǎng)絡(luò)協(xié)議漏洞挖掘技術(shù)的工作流程及模塊結(jié)構(gòu),并對(duì)模糊測(cè)試的工作模式進(jìn)行闡述。在此基礎(chǔ)上,對(duì)網(wǎng)絡(luò)協(xié)議漏洞挖掘過程中的網(wǎng)絡(luò)協(xié)議格式解析進(jìn)行優(yōu)化,結(jié)合局部序列對(duì)比技術(shù),提高了整個(gè)網(wǎng)絡(luò)協(xié)議漏洞挖掘系統(tǒng)的工作效率,最后對(duì)改進(jìn)的漏洞挖掘系統(tǒng)設(shè)計(jì)測(cè)試實(shí)驗(yàn),驗(yàn)證了本文所提新型漏洞挖掘方法在執(zhí)行效率上與傳統(tǒng)漏洞挖掘方法相比有一定的提高。
[1] 史記, 曾昭龍, 楊從保,等. Fuzzing測(cè)試技術(shù)綜述[J].信息網(wǎng)絡(luò)安全, 2014(3):87-91.
[2] 王櫻,李錫輝.多序列比對(duì)算法綜述[J].中國(guó)新通信, 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] 劉大光.基于模糊測(cè)試的網(wǎng)絡(luò)協(xié)議自動(dòng)化漏洞挖掘工具設(shè)計(jì)與實(shí)現(xiàn)[D]. 北京:北京大學(xué), 2014.
[5] 裘志慶, 宦飛. 基于網(wǎng)絡(luò)爬蟲和Fuzzing的漏洞挖掘檢測(cè)工具[J]. 微型電腦應(yīng)用, 2016, 32(3):73-76.
[6] 潘道欣, 王軼駿, 薛質(zhì).基于網(wǎng)絡(luò)協(xié)議逆向分析的遠(yuǎn)程控制木馬漏洞挖掘[J]. 計(jì)算機(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
單路超,王建章,許德森,等.基于局部序列比對(duì)的漏洞挖掘技術(shù)研究[J].微型機(jī)與應(yīng)用,2017,36(3):1-3,7.
2016-10-01)
單路超(1993-),男,碩士研究生,主要研究方向:多協(xié)議網(wǎng)絡(luò)。
王建章(1964-),男,高級(jí)工程師,主要研究方向:多協(xié)議網(wǎng)絡(luò),云計(jì)算及大數(shù)據(jù)。
許德森(1957-),男,研究員,主要研究方向:無線多協(xié)議網(wǎng)絡(luò),天線技術(shù)等。