未知二進(jìn)制協(xié)議的報(bào)文分割方法

徐 魁,海 洋,李曉輝,朱承才,陶 軍,3

(1.寶雞市公安局通信處,陜西 寶雞 721014;2.東南大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院,江蘇 南京 211189;3.計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室(東南大學(xué)),江蘇 南京 211189)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展,保障通信網(wǎng)絡(luò)的安全愈發(fā)重要。二進(jìn)制協(xié)議因其非侵入性的特點(diǎn)以及在網(wǎng)絡(luò)中的廣泛應(yīng)用成為了當(dāng)前研究的熱點(diǎn)。

協(xié)議逆向工程的關(guān)鍵在于對(duì)協(xié)議報(bào)文如何分段。對(duì)未知規(guī)范的通信需要通過(guò)監(jiān)控網(wǎng)絡(luò)流量等方法對(duì)其進(jìn)行逆向工程[1]。靜態(tài)流量逆向工程的應(yīng)用包括僵尸網(wǎng)絡(luò)分析[2]、蜜罐設(shè)置[2-3]、模糊漏洞測(cè)試[4]和網(wǎng)絡(luò)自動(dòng)建模[5]。2004年,Beddoe[6]和Rauch提出了首個(gè)解決方案:序列比對(duì)。此后ProDecoder[7]和PRISMA[2]發(fā)現(xiàn)自然語(yǔ)言處理在使用ASCII編碼關(guān)鍵字來(lái)構(gòu)造消息的協(xié)議上運(yùn)行良好。推斷消息格式往往需要大量消息,然而多序列比對(duì)會(huì)導(dǎo)致指數(shù)復(fù)雜性[8],當(dāng)數(shù)據(jù)量巨大時(shí)性能變差。另一方面,長(zhǎng)可變消息可能出現(xiàn)對(duì)齊偏差,從而導(dǎo)致字段邊界誤判。因此,為了聚類(lèi)消息類(lèi)型或?qū)R字段序列,就需要進(jìn)行消息字段劃分。ScriptGen[3]、Discoverer[9]和Netzob使用序列對(duì)齊來(lái)推斷消息格式。FieldHunter[10-11]使用字段類(lèi)型的特征化等方法進(jìn)行格式推斷。張蔚瑤等人使用協(xié)議特征庫(kù)對(duì)未知協(xié)議進(jìn)行逆向分析[12]。此外,研究人員提出了三類(lèi)創(chuàng)新性的協(xié)議報(bào)文分段方法:基于信息論投票的報(bào)文分段、基于決策模型的報(bào)文分段[13]與基于報(bào)文內(nèi)部結(jié)構(gòu)的報(bào)文分段。Zhang等人[14]提出協(xié)議關(guān)鍵詞提取方法ProWord,首次將無(wú)監(jiān)督專(zhuān)家投票算法應(yīng)用于流量分析。Sun等人[15]引入統(tǒng)計(jì)信息,從信息論的角度提出協(xié)議報(bào)文分段算法ProSeg。IPART[16]在專(zhuān)家投票算法基礎(chǔ)上又加入語(yǔ)義識(shí)別,對(duì)報(bào)文分段點(diǎn)進(jìn)行二次確認(rèn)。Jiang等人[17]提出基于相鄰字節(jié)距離的報(bào)文分段算法ABInfer,采用最近鄰聚類(lèi)算法迭代將相鄰字節(jié)進(jìn)行合并,然后對(duì)字段進(jìn)行劃分。

協(xié)議字段劃分的過(guò)程可以抽象為報(bào)文字節(jié)序列中字段邊界的決策問(wèn)題。黎敏等人[18]將字段劃分過(guò)程看成馬爾可夫過(guò)程,在此基礎(chǔ)上使用隱半馬爾可夫模型(Hidden Semi-Markov Models,HSMM)[19]進(jìn)行字段劃分。Cai等人[20]同樣使用隱半馬爾可夫模型進(jìn)行求解,對(duì)黎敏的工作進(jìn)行了優(yōu)化。Tao等人[21]使用貝葉斯決策模型進(jìn)行協(xié)議逆向分析,提出了對(duì)二進(jìn)制協(xié)議進(jìn)行字段劃分的方法PRE-Bin。

協(xié)議報(bào)文的部分研究以比特為粒度,挖掘比特間的表征關(guān)系。Kleber等人[22]研究協(xié)議報(bào)文的內(nèi)部結(jié)構(gòu),提出了一種新穎的報(bào)文分段方法NEMESYS。Marchetti等人[23]通過(guò)幅度序列和位翻轉(zhuǎn)頻率尋找報(bào)文分段點(diǎn),提出汽車(chē)通信數(shù)據(jù)幀分段方法READ。

基于上述情況,該文提出了一種用于未知二進(jìn)制協(xié)議逆向工程的協(xié)議字段劃分方案HV。主要工作如下所述:

首先,提出字節(jié)翻轉(zhuǎn)率的概念并將其應(yīng)用到消息分析。從垂直分析的角度,通過(guò)對(duì)比相鄰消息的結(jié)構(gòu),找到該二進(jìn)制協(xié)議在消息結(jié)構(gòu)上的共性。其次,從水平分析的角度探究單條消息的內(nèi)部結(jié)構(gòu)?；诘谝粩?shù)字定律等方法初步找到消息邊界;使用路徑搜索等算法找到更多候選邊界點(diǎn),從而優(yōu)化消息字段劃分的結(jié)果。接著,創(chuàng)新性地聯(lián)合水平以及垂直分析進(jìn)行消息字段的劃分,設(shè)計(jì)用于未知二進(jìn)制協(xié)議字段劃分方案HV。對(duì)從上述得到的消息分段點(diǎn)進(jìn)行評(píng)估、投票等決策,得到最終結(jié)果。最后,引入格式匹配分?jǐn)?shù)(Format Match Score,FMS)用于量化特定消息的格式推斷質(zhì)量。

1 算法思路

1.1 基于垂直分析的報(bào)文分段

此階段探究的是消息之間所呈現(xiàn)出的結(jié)構(gòu)信息。對(duì)相鄰的消息進(jìn)行比較,得出相關(guān)的統(tǒng)計(jì)信息。

1.1.1 字節(jié)翻轉(zhuǎn)率與位翻轉(zhuǎn)率

一般工業(yè)協(xié)議粒度為字節(jié),將消息載荷以字節(jié)形式展開(kāi),使用字節(jié)翻轉(zhuǎn)率進(jìn)行評(píng)估。字節(jié)翻轉(zhuǎn)率定義如下:

(1)

其中,BFi表示第i個(gè)字節(jié)的翻轉(zhuǎn)率,M是所有消息集合,mj是M集合中第j條消息,mj(i)是第j條消息的第i個(gè)字節(jié)。⊕是異或操作。|M|是消息集合中的消息數(shù)量。這一步得到一個(gè)含有n個(gè)元素的數(shù)組,每個(gè)元素代表某一字節(jié)處的翻轉(zhuǎn)率,n是消息載荷字節(jié)的長(zhǎng)度。字節(jié)翻轉(zhuǎn)率獨(dú)立于同一消息中鄰近的字節(jié),只與鄰近的消息有關(guān)。過(guò)程如算法1所描述。

同理,可以將消息載荷以比特形式展開(kāi),得到位翻轉(zhuǎn)率。定義如下:

(2)

位翻轉(zhuǎn)率處理的粒度是比特位。

1.1.2 字段劃分

對(duì)消息進(jìn)行翻轉(zhuǎn)率的計(jì)算后可以得到字節(jié)翻轉(zhuǎn)率數(shù)組BF以及位翻轉(zhuǎn)率數(shù)組bF。接著進(jìn)行字段劃分。首先遍歷字節(jié)翻轉(zhuǎn)率數(shù)組,查找符合如下條件之一的字節(jié)位置:

(1)該位置字節(jié)的翻轉(zhuǎn)率為局部極值點(diǎn),即滿足:BFi≥BFi-1and BFi≥BFi+1。

(2)該位置字節(jié)與相鄰的位置字節(jié)都具有一個(gè)較高的翻轉(zhuǎn)率,即滿足:

BFi≥Φ and (BFi-1≥Φ or BFi+1≥Φ)。

(3)該位置字節(jié)的翻轉(zhuǎn)率為0,即BFi=0。

將符合條件的字節(jié)位置標(biāo)記為字段邊界可疑點(diǎn)。經(jīng)過(guò)上述處理得到一個(gè)邊界列表b。將字節(jié)翻轉(zhuǎn)率為0的字節(jié)位標(biāo)記為邊界。根據(jù)翻轉(zhuǎn)率的定義,經(jīng)常變化的字段翻轉(zhuǎn)率會(huì)偏大,反之則偏小。

位翻轉(zhuǎn)率數(shù)組是一個(gè)輔助數(shù)組。對(duì)于計(jì)數(shù)字段,翻轉(zhuǎn)率會(huì)較大。計(jì)數(shù)字段低位的字節(jié)翻轉(zhuǎn)率為1,相應(yīng)的最低比特位翻轉(zhuǎn)率也為1。并且計(jì)數(shù)字段從最低位到最高位翻轉(zhuǎn)率應(yīng)是遞減的,每一位的翻轉(zhuǎn)率是下一位的兩倍。當(dāng)字節(jié)翻轉(zhuǎn)率為1后可利用位翻轉(zhuǎn)率數(shù)組進(jìn)行確認(rèn)。當(dāng)認(rèn)定某一字節(jié)為計(jì)數(shù)字段時(shí),需要查看該字節(jié)的后一字節(jié)以及前一字節(jié)。這一過(guò)程如算法2所描述。

算法2:字段劃分階段二1:function divide2(BF, bF, b) :2: BLen len(BF);3: bLen len(bF);4: For i In range(0, BLen) :5: IF BFi = 1 :6: IF detectLeftMatch(bF, i) :7: b.append((i-2, BFi-2));8: b.erase(i-1);9: ELIF detectRightMatch(bF, i) :10: b.append((i+1, BFi+1));11: b.erase(i);12: return b;

通過(guò)算法2可以得到垂直分析的邊界列表b。該階段是在尋找同一種協(xié)議的所有消息中共有部分的統(tǒng)計(jì)特性。在進(jìn)行消息分段時(shí)需要取一個(gè)固定的長(zhǎng)度進(jìn)行消息間比對(duì)。具體如何取值下文有所說(shuō)明。

1.2 基于水平分析的報(bào)文分段

協(xié)議字段劃分的過(guò)程可以抽象為報(bào)文字節(jié)序列中字段邊界的決策問(wèn)題。因此可以使用路徑搜索算法從水平分析的角度對(duì)消息的內(nèi)部結(jié)構(gòu)進(jìn)行分段。在此之前需要進(jìn)行分支度量以及約束條件的定義。

1.2.1 分支度量的定義及第一數(shù)字定律擴(kuò)展

第一數(shù)字定律,指所有自然隨機(jī)變量只要樣本空間足夠大,每一樣本首位數(shù)字為1至9,各數(shù)字的概率在一定范圍內(nèi)具有穩(wěn)定性。以1為首位數(shù)字的數(shù)的出現(xiàn)概率約為總數(shù)的三成。總結(jié)而言,越大的數(shù)以它為首幾位的數(shù)出現(xiàn)的概率就越低。

在十進(jìn)制中,以n開(kāi)頭的數(shù)出現(xiàn)的幾率為:

(3)

然而二進(jìn)制協(xié)議中對(duì)以“0”開(kāi)頭的字節(jié)也會(huì)保留,因此可以擴(kuò)展為:

(4)

分支度量在定義時(shí)主要基于第一數(shù)字定律,邊界評(píng)估指標(biāo)如式(5)所示:

(5)

1.2.2 約束條件

約束條件控制節(jié)點(diǎn)之間是否可達(dá)。構(gòu)造約束條件時(shí):首先字段長(zhǎng)度是有限的,一般不超過(guò)4個(gè)字節(jié),個(gè)別字段會(huì)達(dá)到8字節(jié),多數(shù)情況下為偶數(shù)或“1”。其次,字段是單向的,即字段是從左往右,不存在從右往左的。評(píng)估指標(biāo)如式(6)(7)所示:

(6)

(7)

式(6)中,di,j表示第i個(gè)候選邊界和第j個(gè)候選邊界之間的距離。根據(jù)最短路徑搜索的思想,為使最佳路徑的路徑權(quán)值和最小,該式使用score的倒數(shù)作為分支度量。式(7)中,wk是一個(gè)距離權(quán)重,其中k是整數(shù),表示兩個(gè)候選邊界之間相隔的字節(jié)數(shù)。當(dāng)k=1,2,4時(shí),表示j>i并且字段長(zhǎng)度合理,使用平方增量;當(dāng)k≤0(從右往左)或者k=3(3個(gè)字節(jié)長(zhǎng)度的字段一般不常見(jiàn))或者k>4(字段長(zhǎng)度太長(zhǎng))時(shí),權(quán)重為負(fù)無(wú)窮,即不可達(dá)。

1.2.3 最佳路徑搜索算法

根據(jù)分支度量和約束條件生成候選邊界有向圖,利用最佳路徑搜索算法從有向圖中找到與真實(shí)格式關(guān)鍵詞邊界最接近的一條路徑作為最終格式關(guān)鍵詞的邊界推斷結(jié)果。目標(biāo)函數(shù)如式(8)所示:

(8)

其中,Trace是所有可能的路徑集合,tracek是集合的第k條路徑。

最佳路徑搜索算法應(yīng)用于關(guān)鍵詞邊界選擇,最終目標(biāo)是尋找一條從第一個(gè)候選邊界點(diǎn)到最后一個(gè)候選邊界點(diǎn)權(quán)值之和最小或最大的路徑。

1.3 聯(lián)合垂直分析和水平分析的消息分段

1.3.1 劃分方案

消息的水平分析通過(guò)消息內(nèi)部所蘊(yùn)含的信息對(duì)字段進(jìn)行了劃分。消息的垂直分析通過(guò)消息序列之間所蘊(yùn)含的信息對(duì)字段進(jìn)行了劃分。這兩種方案各自的特點(diǎn)如表1所示。

表1 水平與垂直分析優(yōu)缺點(diǎn)

該文將這兩種方式進(jìn)行結(jié)合,設(shè)計(jì)了一種創(chuàng)新性的消息字段劃分方案HV。

對(duì)于水平分析,分析的是單條消息;結(jié)合垂直分析時(shí)要將分析對(duì)象由單條消息轉(zhuǎn)為消息集合。

圖1 投票機(jī)制執(zhí)行過(guò)程

接下來(lái),結(jié)合垂直分析與水平分析的結(jié)果。設(shè)水平分析的字段邊界劃分結(jié)果為Ih={ih,1,ih,2,…},垂直分析的字段邊界劃分結(jié)果為Iv={iv,1,iv,2,…},最終的結(jié)果取兩者的并集,即I=Ih∪Iv。

1.3.2 方案優(yōu)化

為避免在data字段進(jìn)行消息字段劃分對(duì)結(jié)果產(chǎn)生干擾,需要對(duì)消息進(jìn)行截尾處理。這里使用平均類(lèi)內(nèi)距離作為評(píng)估指標(biāo),如式(9)所示:

(9)

接著對(duì)消息作截尾處理,取不同長(zhǎng)度的消息計(jì)算平均類(lèi)內(nèi)距離,取平均類(lèi)內(nèi)距離驟增時(shí)的消息長(zhǎng)度lenavg作為截尾點(diǎn)候選點(diǎn)。同時(shí)考慮所有消息中最短的消息長(zhǎng)度lenmin。將lenavg的初始值設(shè)為所有消息的長(zhǎng)度最小值,再設(shè)一個(gè)下限lenlow,在該文中設(shè)為10。最終的截尾長(zhǎng)度lenfinal取值如下:

lenfinal=min{lenmin,max{lenavg,lenlow}}

(10)

1.4 格式匹配分?jǐn)?shù)FMS

引入格式匹配分?jǐn)?shù)FMS作為字段劃分質(zhì)量的度量。該測(cè)度主要考慮三個(gè)方面:(1)正確識(shí)別字段的比率;(2)區(qū)分移位字段邊界和完全錯(cuò)誤字段;(3)量化不同字段邊界推斷的遞減效用。

FMS為消息的每一個(gè)真實(shí)邊界rk定義了范圍,一個(gè)邊界的范圍起始點(diǎn)為前一個(gè)邊界rk-1和前一邊界rk的中間點(diǎn),范圍結(jié)束點(diǎn)為當(dāng)前邊界rk和后一邊界rk+1的中間點(diǎn)。消息開(kāi)始處r0和消息結(jié)束處r|R|不分配邊界范圍。因此,當(dāng)推斷邊界il滿足式(11)時(shí),就表明il屬于rk的范圍。

(11)

式中,il表示第l個(gè)推斷的字段邊界的下標(biāo)索引,0

δr=argmin{|i-r|}-r

(12)

將空集上的min運(yùn)算符定義為minφ=-∞?？芍膔有四種情況:①δr=-∞:對(duì)于真實(shí)邊界r,沒(méi)有與之匹配的推斷結(jié)果。②δr=0:推斷邊界與真實(shí)邊界完全吻合。③-∞<δr<0:推斷邊界在真實(shí)邊界的左邊,偏移量為δr字節(jié)。④δr>0:推斷邊界在真實(shí)邊界的右邊,偏移量為δr字節(jié)。

模式匹配分?jǐn)?shù)的定義如式(13)所示。

(13)

最后,對(duì)整個(gè)式子進(jìn)行標(biāo)準(zhǔn)化,使得FMS的值在0到1之間。推斷質(zhì)量越高,FMS越大。

2 實(shí) 驗(yàn)

2.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)樣本為668條S7COMM協(xié)議數(shù)據(jù)、115條DNP3.0協(xié)議數(shù)據(jù)、3 948條Modbus協(xié)議數(shù)據(jù)和674條EGD協(xié)議數(shù)據(jù)。S7COMM協(xié)議使用TPKT和COPT封裝PDU,DNP3.0協(xié)議較復(fù)雜,Modbus協(xié)議較簡(jiǎn)單,EGD協(xié)議含有時(shí)間戳等字段。

由于實(shí)驗(yàn)無(wú)需對(duì)不同協(xié)議的字段劃分結(jié)果進(jìn)行橫向比較,因此并未保持協(xié)議數(shù)據(jù)的數(shù)據(jù)量一致。實(shí)驗(yàn)中投票時(shí)的Θ設(shè)置為0.8,FMS的γ設(shè)置為2,使用tshark對(duì)消息解析出的信息作為基準(zhǔn)。

2.2 實(shí)驗(yàn)結(jié)果及性能分析

圖2展示了四種協(xié)議截尾后的投票結(jié)果?？梢?jiàn)劃分結(jié)果的有效字段較多,側(cè)面印證截尾的必要性。

該階段對(duì)字段邊界的推導(dǎo)初具成效,尤其是EGD協(xié)議。這是因?yàn)镋GD協(xié)議主要由IP地址和時(shí)間戳字段等常見(jiàn)字段組成。這些字段在投票前已經(jīng)被事先定義的字段識(shí)別方法識(shí)別了。

圖2 投票結(jié)果

在垂直分析時(shí)需要計(jì)算位翻轉(zhuǎn)率,圖3展示了這四種協(xié)議的位翻轉(zhuǎn)率?？梢?jiàn)字段邊界左邊的比特位的翻轉(zhuǎn)率普遍偏高,所以翻轉(zhuǎn)率高的位置附近或者翻轉(zhuǎn)率驟降點(diǎn)可以判定為字段邊界。

圖3 位翻轉(zhuǎn)率

實(shí)驗(yàn)使用Netzob以及NEMESYS作為對(duì)比方法,如圖4所示。(a)描述的是S7COMM協(xié)議的字段劃分的質(zhì)量,可見(jiàn)隨著數(shù)據(jù)量的增加三者的質(zhì)量變化都較小。(b)描述的是Modbus字段劃分的質(zhì)量,其中Netzob推測(cè)的質(zhì)量最高。(c)描述的是DNP3.0字段劃分的質(zhì)量。可見(jiàn)Netzob的質(zhì)量較差。因?yàn)閷?shí)驗(yàn)中DNP3.0協(xié)議的數(shù)據(jù)量太少,Netzob可挖掘的統(tǒng)計(jì)信息太少。且NEMESYS和HV都有較大起伏,這是因?yàn)镹EMESYS只考慮單條消息,依賴于每條消息的取值,所以不受樣本數(shù)增加的影響;但是HV在考慮單條消息的同時(shí)也會(huì)考慮多條消息之間的比較,因此隨著相似樣本的增加會(huì)提高推測(cè)質(zhì)量。(d)描述的是EGD字段的劃分質(zhì)量,清晰地觀察到HV的推導(dǎo)質(zhì)量極高且穩(wěn)定,達(dá)到了0.725,這是因?yàn)镋GD協(xié)議中有幾個(gè)字段的語(yǔ)義被HV事先定義了。

圖4 FMS測(cè)度下的字段劃分質(zhì)量

圖5展示了HV與Netzob和NEMESYS在所有消息上的推導(dǎo)質(zhì)量的分布情況。從圖中可以看出HV除了在Modbus協(xié)議上的推測(cè)質(zhì)量不如Netzob,其余情況下的推測(cè)質(zhì)量均高于Netzob和NEMESYS,而且較為穩(wěn)定。HV整體上是優(yōu)于Netzob以及NEMESYS的。

圖5 FMS分布情況

表2列出了三種方法的運(yùn)行時(shí)間。其中+∞表示在30分鐘內(nèi)無(wú)法求解。可以看出,三種方法中Netzob的運(yùn)行時(shí)間最長(zhǎng),甚至當(dāng)數(shù)據(jù)集到達(dá)一定數(shù)量時(shí),可能無(wú)法求解。這是由于Netzob和大多數(shù)協(xié)議逆向算法相同,使用了全局序列比對(duì)算法,導(dǎo)致具有指數(shù)級(jí)別的時(shí)間復(fù)雜度。當(dāng)對(duì)最大長(zhǎng)度為l的k條消息進(jìn)行比對(duì)時(shí),復(fù)雜度為O(lk)。從中還可以看出,NEMESYS運(yùn)行時(shí)間最短,這是因?yàn)镹EMESYS不需要將數(shù)據(jù)集中的消息進(jìn)行任何比較,它只與消息的長(zhǎng)度以及數(shù)量相關(guān),導(dǎo)致它具有極低的線性復(fù)雜度。同樣,HV運(yùn)行時(shí)間也較短,并且運(yùn)行時(shí)間也幾乎是線性的。以Modbus為例,在分析1 974條消息時(shí),NEMESYS與HV都是在幾秒內(nèi)完成,而Netzob使用的時(shí)間是HV的500倍。

表2 執(zhí)行時(shí)間 s

圖5說(shuō)明邊界推斷的質(zhì)量只有在Modbus協(xié)議上是Netzob>HV>NEMESYS;而S7COMM,DNP3.0和EGD協(xié)議上均為HV>NEMESYS>Netzob。從表2可知,Netzob的執(zhí)行時(shí)間遠(yuǎn)遠(yuǎn)大于HV以及NEMESYS。而后兩者的執(zhí)行時(shí)間相差無(wú)幾。因此,綜合字段劃分質(zhì)量和劃分時(shí)間,HV總體上是優(yōu)于Netzob以及NEMESYS的,它有著較穩(wěn)定的推斷質(zhì)量。HV的執(zhí)行時(shí)間幾乎是線性的,當(dāng)數(shù)據(jù)量較大時(shí)也能快速處理,而Netzob中的序列比對(duì)的復(fù)雜度是指數(shù)級(jí)別,當(dāng)數(shù)據(jù)到達(dá)一定量就無(wú)法求解。

3 結(jié)束語(yǔ)

推斷二進(jìn)制協(xié)議的格式結(jié)構(gòu)對(duì)于二進(jìn)制協(xié)議分析十分重要。目前的協(xié)議逆向分析對(duì)于文本協(xié)議的研究較深,針對(duì)二進(jìn)制協(xié)議進(jìn)行逆向分析仍存在難點(diǎn)。字段劃分是協(xié)議逆向過(guò)程中的前置步驟,協(xié)議逆向的準(zhǔn)確度很大程度依賴于字段劃分的質(zhì)量。為解決上述問(wèn)題,該文提出了一種新穎的較簡(jiǎn)單的未知二進(jìn)制協(xié)議字段劃分方法HV。HV首先單獨(dú)分析每一條消息的內(nèi)部結(jié)構(gòu);接著通過(guò)計(jì)算相鄰消息之間的字節(jié)以及位翻轉(zhuǎn)率進(jìn)行字段劃分;最后結(jié)合兩次分段得到最終的字段劃分結(jié)果。其他需要成對(duì)比較消息的方法復(fù)雜度在指數(shù)級(jí)別,HV幾乎只需要線性復(fù)雜度。并且與其它方案相比,此方案在推斷字段邊界的質(zhì)量上也有著不錯(cuò)的表現(xiàn)。該文還定義了格式匹配分?jǐn)?shù)來(lái)衡量字段劃分的質(zhì)量,相比傳統(tǒng)的衡量指標(biāo),格式匹配分?jǐn)?shù)更加適用于字段劃分。