基于最佳路徑搜索的二進(jìn)制協(xié)議格式關(guān)鍵詞邊界確定方法

閆小勇，李 青

(信息工程大學(xué)，鄭州450001)

(*通信作者電子郵箱yanxiaoyong2016@163.com)

0 引言

二進(jìn)制協(xié)議結(jié)構(gòu)緊湊、控制開銷小、傳輸效率高，因而得到廣泛應(yīng)用。尤其在物聯(lián)網(wǎng)中，二進(jìn)制協(xié)議應(yīng)用主導(dǎo)地位更為突出。二進(jìn)制協(xié)議字段不受字節(jié)長(zhǎng)度限制，不使用公開字符編碼，使得二進(jìn)制協(xié)議分析具有很高的難度。二進(jìn)制協(xié)議逆向成為協(xié)議逆向工程的難題。在沒有協(xié)議先驗(yàn)知識(shí)的條件下，二進(jìn)制協(xié)議的字段切分十分困難，往往只能得到字段的組合;確切的字段邊界分析很難做到，往往只能得到概率意義下的邊界。為此本文提出從關(guān)鍵詞的角度進(jìn)行二進(jìn)制協(xié)議逆向分析。

目前僅有少量研究是基于網(wǎng)絡(luò)流量對(duì)二進(jìn)制協(xié)議進(jìn)行報(bào)文格式逆向分析。Tao等［1］改進(jìn)多序列比對(duì)算法，使其適用于二進(jìn)制協(xié)議，利用貝葉斯決策和最大似然準(zhǔn)則實(shí)現(xiàn)二進(jìn)制協(xié)議字段定界。多序列比對(duì)算法能夠解決可變字段和不可變字段之間的定界問(wèn)題，但對(duì)于可變字段和可變字段以及不可變字段和不可變字段之間的定界，因?yàn)槿鄙僬Z(yǔ)義信息，很難實(shí)現(xiàn)。雖然Tao等［1］最終利用貝葉斯決策和最大似然準(zhǔn)則很大程度上提升了字段定界的準(zhǔn)確性，但推斷結(jié)果中仍存在字段組合問(wèn)題，即多個(gè)字段被誤判為一個(gè)字段。Tong等［2］設(shè)計(jì)了一種抗誤碼的未知二進(jìn)制協(xié)議解析方法，提出模糊加權(quán)的多序列比對(duì)算法，在推斷結(jié)果中同樣會(huì)出現(xiàn)多個(gè)字段被誤判為一個(gè)字段的情況。孟凡治等［3］提出基于概率比對(duì)的通信協(xié)議格式逆向分析方法，通過(guò)概率比對(duì)算法使字段準(zhǔn)確對(duì)齊，再通過(guò)特征統(tǒng)計(jì)量的差異性進(jìn)行字段分割，該方法同樣會(huì)出現(xiàn)字段組合問(wèn)題。上述方法均以獲取二進(jìn)制協(xié)議報(bào)文格式為最終目標(biāo)，但因先驗(yàn)信息缺失，往往只能得到字段組合，同時(shí)字段邊界也只是概率意義下的字段邊界。

關(guān)鍵詞與報(bào)文格式之間存在聯(lián)系。對(duì)于文本類協(xié)議，關(guān)鍵詞序列可以作為報(bào)文格式。Wang等［4］利用n-gram算法對(duì)同種應(yīng)用協(xié)議數(shù)據(jù)作分解，提取協(xié)議關(guān)鍵詞，用關(guān)鍵詞序列代替協(xié)議報(bào)文作報(bào)文聚類，最后用多序列比對(duì)算法推斷報(bào)文格式。Luo等［5］提出基于位置的協(xié)議逆向方法AutoReEngine，利用Apriori算法提取頻繁字符串，并對(duì)頻繁字符串作基于位置的方差統(tǒng)計(jì)，方差小的作為協(xié)議關(guān)鍵詞，最終協(xié)議報(bào)文格式為提取的關(guān)鍵詞序列。黎敏等［6］建立隱半馬爾可夫模型，描述協(xié)議報(bào)文字段之間的關(guān)系，通過(guò)最大似然概率分段方法實(shí)現(xiàn)報(bào)文字段的最佳劃分，文中將報(bào)文格式簡(jiǎn)化為“關(guān)鍵詞+變量字段”的分段形式，本質(zhì)上是以關(guān)鍵詞序列作為協(xié)議報(bào)文格式。以上研究均針對(duì)文本類協(xié)議，通過(guò)提取協(xié)議關(guān)鍵詞序列近似協(xié)議報(bào)文格式。

對(duì)于二進(jìn)制協(xié)議，字段組合靈活，很少出現(xiàn)關(guān)鍵詞和變量字段交替出現(xiàn)的情形，因而關(guān)鍵詞序列不等價(jià)于協(xié)議報(bào)文格式。如何從關(guān)鍵詞角度進(jìn)行二進(jìn)制協(xié)議報(bào)文格式逆向分析成為亟待解決的問(wèn)題。

面向二進(jìn)制私有協(xié)議數(shù)據(jù)逆向分析，本文提出了一種基于最佳路徑搜索的二進(jìn)制協(xié)議格式關(guān)鍵詞邊界確定方法(method for determining the boundaries of Binary Protocol Format Keywords based on Optimal path search，OBPFK)，實(shí)現(xiàn)了以關(guān)鍵詞為核心的協(xié)議逆向分析。本文主要工作有:1)對(duì)協(xié)議關(guān)鍵詞作進(jìn)一步劃分，提出協(xié)議分類關(guān)鍵詞和協(xié)議格式關(guān)鍵詞定義;2)提出迭代n-gram-position算法，有效解決了n-gram算法中n值不易確定和固定偏移位置格式關(guān)鍵詞的邊界提取問(wèn)題;3)利用最佳路徑搜索算法實(shí)現(xiàn)了對(duì)格式關(guān)鍵詞的聯(lián)合最優(yōu)定界。

1 問(wèn)題描述

1.1 格式關(guān)鍵詞

協(xié)議報(bào)文格式可以看作是字段序列，協(xié)議字段是具有特定語(yǔ)義的最小不可分割子序列［7］。同種類型協(xié)議報(bào)文的字段集合記為 FD={fd1，fd2，…，fdi，…，fdg}，其中 fdi(1 ≤i≤g)為字段。一個(gè)協(xié)議報(bào)文可以唯一地劃分為g個(gè)不相交字段。

絕大部分網(wǎng)絡(luò)協(xié)議報(bào)文中存在協(xié)議鍵詞，協(xié)議關(guān)鍵詞是指滿足一定條件(位置和頻度)的字符串 /比特串［8］。同種類型協(xié)議報(bào)文的關(guān)鍵詞集合記為 KW={kw1，kw2，…，kwi，…，kwt}，其中kwi(1≤i≤t)為關(guān)鍵詞。

協(xié)議關(guān)鍵詞不同于協(xié)議字段，如圖1所示。借用圓與圓之間的位置關(guān)系來(lái)描述:同一FD中，相鄰字段位置僅存在相切關(guān)系;同一KW中，相鄰關(guān)鍵詞位置存在相交、相切和相離三種關(guān)系。

圖1 協(xié)議字段和協(xié)議關(guān)鍵詞Fig.1 Protocol fields and protocol keywords

協(xié)議關(guān)鍵詞在協(xié)議數(shù)據(jù)分析中具有重要的作用，既可以用于區(qū)分不同協(xié)議報(bào)文，也可以作為協(xié)議字段，成為協(xié)議報(bào)文格式的一部分。根據(jù)其作用不同，本文將協(xié)議關(guān)鍵詞分為分類關(guān)鍵詞、格式關(guān)鍵詞和其他關(guān)鍵詞。分類關(guān)鍵詞和格式關(guān)鍵詞的定義如下。

定義1 給定報(bào)文集合中不同類型協(xié)議報(bào)文的關(guān)鍵詞集合為 PKW={KW1，KW2，…，KWi，…，KWu}，KWi={kwi1，kwi2，…，kwij，…，kwit}表示同種類型協(xié)議報(bào)文的關(guān)鍵詞集合。kwij∈ KWi，若 kwijKWw(w ∈ (1，u)，w ≠ i)，則 kwij為KWi對(duì)應(yīng)協(xié)議的一個(gè)分類關(guān)鍵詞。

定義2 同種類型協(xié)議報(bào)文的字段集合為FD={fd1，fd2，…，fdi，…，fdg}，相應(yīng)的關(guān)鍵詞集合為 KW={kw1，kw2，…，kwj，…，kwt}。若 kwj=fdi，則kwj為該協(xié)議的一個(gè)格式關(guān)鍵詞。

分類關(guān)鍵詞與數(shù)據(jù)集中包含的協(xié)議有關(guān)，假設(shè)數(shù)據(jù)集中有兩種不同類型協(xié)議報(bào)文，關(guān)鍵詞kw只存在于一種類型的協(xié)議報(bào)文中，那么kw就是該種類型協(xié)議報(bào)文的一個(gè)分類關(guān)鍵詞。格式關(guān)鍵詞是協(xié)議字段，或者協(xié)議字段的組合。分類關(guān)鍵詞集合和格式關(guān)鍵詞集合可能存在交集，即協(xié)議關(guān)鍵詞是分類關(guān)鍵詞的同時(shí)，也可能是格式關(guān)鍵詞。其他關(guān)鍵詞既不是分類關(guān)鍵詞，也不是格式關(guān)鍵詞。格式關(guān)鍵詞提取要求數(shù)據(jù)集純度高，數(shù)據(jù)多樣性好，覆蓋時(shí)空分布。分類關(guān)鍵詞提取對(duì)數(shù)據(jù)集樣本沒有特殊的要求。

協(xié)議報(bào)文格式可以看作協(xié)議字段序列，協(xié)議格式關(guān)鍵詞序列不等價(jià)于協(xié)議報(bào)文格式，屬于報(bào)文格式的一個(gè)子集。報(bào)文格式的形式會(huì)影響格式關(guān)鍵詞邊界的確定。以文本類協(xié)議和二進(jìn)制協(xié)議為例:文本類協(xié)議的字段通常為特定的詞，這些詞由ASCII字符組成，易于理解，字段邊界為預(yù)定義的分割符(例如空格或者回車換行)，因此格式關(guān)鍵詞的邊界易于確定;二進(jìn)制協(xié)議結(jié)構(gòu)緊湊，字段之間沒有分割符，面向私有協(xié)議時(shí)，因缺乏先驗(yàn)信息，格式關(guān)鍵詞邊界確定較為困難。

1.2 問(wèn)題模型

二進(jìn)制協(xié)議數(shù)據(jù)幀的最小單元為比特，值域D={

右玉县| 颍上县| 吉木萨尔县| 石门县| 红桥区| 墨脱县| 旺苍县| 墨竹工卡县| 武隆县| 峨山| 海安县| 夏邑县| 加查县| 新邵县| 都昌县| 襄汾县| 曲靖市| 布尔津县| 沈丘县| 永济市| 崇义县| 龙州县| 灵丘县| 修武县| 水城县| 定日县| 周口市| 南充市| 喀喇沁旗| 淮滨县| 信阳市| 高雄县| 吴忠市| 东丰县| 云梦县| 施秉县| 临沧市| 甘孜县| 钟祥市| 八宿县| 鹰潭市|