基于最佳路径搜索的二进制协议格式关键词边界确定方法

闫小勇，李 青

(信息工程大学，郑州450001)

(*通信作者电子邮箱yanxiaoyong2016@163.com)

0 引言

二进制协议结构紧凑、控制开销小、传输效率高，因而得到广泛应用。尤其在物联网中，二进制协议应用主导地位更为突出。二进制协议字段不受字节长度限制，不使用公开字符编码，使得二进制协议分析具有很高的难度。二进制协议逆向成为协议逆向工程的难题。在没有协议先验知识的条件下，二进制协议的字段切分十分困难，往往只能得到字段的组合;确切的字段边界分析很难做到，往往只能得到概率意义下的边界。为此本文提出从关键词的角度进行二进制协议逆向分析。

目前仅有少量研究是基于网络流量对二进制协议进行报文格式逆向分析。Tao等［1］改进多序列比对算法，使其适用于二进制协议，利用贝叶斯决策和最大似然准则实现二进制协议字段定界。多序列比对算法能够解决可变字段和不可变字段之间的定界问题，但对于可变字段和可变字段以及不可变字段和不可变字段之间的定界，因为缺少语义信息，很难实现。虽然Tao等［1］最终利用贝叶斯决策和最大似然准则很大程度上提升了字段定界的准确性，但推断结果中仍存在字段组合问题，即多个字段被误判为一个字段。Tong等［2］设计了一种抗误码的未知二进制协议解析方法，提出模糊加权的多序列比对算法，在推断结果中同样会出现多个字段被误判为一个字段的情况。孟凡治等［3］提出基于概率比对的通信协议格式逆向分析方法，通过概率比对算法使字段准确对齐，再通过特征统计量的差异性进行字段分割，该方法同样会出现字段组合问题。上述方法均以获取二进制协议报文格式为最终目标，但因先验信息缺失，往往只能得到字段组合，同时字段边界也只是概率意义下的字段边界。

关键词与报文格式之间存在联系。对于文本类协议，关键词序列可以作为报文格式。Wang等［4］利用n-gram算法对同种应用协议数据作分解，提取协议关键词，用关键词序列代替协议报文作报文聚类，最后用多序列比对算法推断报文格式。Luo等［5］提出基于位置的协议逆向方法AutoReEngine，利用Apriori算法提取频繁字符串，并对频繁字符串作基于位置的方差统计，方差小的作为协议关键词，最终协议报文格式为提取的关键词序列。黎敏等［6］建立隐半马尔可夫模型，描述协议报文字段之间的关系，通过最大似然概率分段方法实现报文字段的最佳划分，文中将报文格式简化为“关键词+变量字段”的分段形式，本质上是以关键词序列作为协议报文格式。以上研究均针对文本类协议，通过提取协议关键词序列近似协议报文格式。

对于二进制协议，字段组合灵活，很少出现关键词和变量字段交替出现的情形，因而关键词序列不等价于协议报文格式。如何从关键词角度进行二进制协议报文格式逆向分析成为亟待解决的问题。

面向二进制私有协议数据逆向分析，本文提出了一种基于最佳路径搜索的二进制协议格式关键词边界确定方法(method for determining the boundaries of Binary Protocol Format Keywords based on Optimal path search，OBPFK)，实现了以关键词为核心的协议逆向分析。本文主要工作有:1)对协议关键词作进一步划分，提出协议分类关键词和协议格式关键词定义;2)提出迭代n-gram-position算法，有效解决了n-gram算法中n值不易确定和固定偏移位置格式关键词的边界提取问题;3)利用最佳路径搜索算法实现了对格式关键词的联合最优定界。

1 问题描述

1.1 格式关键词

协议报文格式可以看作是字段序列，协议字段是具有特定语义的最小不可分割子序列［7］。同种类型协议报文的字段集合记为 FD={fd1，fd2，…，fdi，…，fdg}，其中 fdi(1 ≤i≤g)为字段。一个协议报文可以唯一地划分为g个不相交字段。

绝大部分网络协议报文中存在协议键词，协议关键词是指满足一定条件(位置和频度)的字符串 /比特串［8］。同种类型协议报文的关键词集合记为 KW={kw1，kw2，…，kwi，…，kwt}，其中kwi(1≤i≤t)为关键词。

协议关键词不同于协议字段，如图1所示。借用圆与圆之间的位置关系来描述:同一FD中，相邻字段位置仅存在相切关系;同一KW中，相邻关键词位置存在相交、相切和相离三种关系。

图1 协议字段和协议关键词Fig.1 Protocol fields and protocol keywords

协议关键词在协议数据分析中具有重要的作用，既可以用于区分不同协议报文，也可以作为协议字段，成为协议报文格式的一部分。根据其作用不同，本文将协议关键词分为分类关键词、格式关键词和其他关键词。分类关键词和格式关键词的定义如下。

定义1 给定报文集合中不同类型协议报文的关键词集合为 PKW={KW1，KW2，…，KWi，…，KWu}，KWi={kwi1，kwi2，…，kwij，…，kwit}表示同种类型协议报文的关键词集合。kwij∈ KWi，若 kwijKWw(w ∈ (1，u)，w ≠ i)，则 kwij为KWi对应协议的一个分类关键词。

定义2 同种类型协议报文的字段集合为FD={fd1，fd2，…，fdi，…，fdg}，相应的关键词集合为 KW={kw1，kw2，…，kwj，…，kwt}。若 kwj=fdi，则kwj为该协议的一个格式关键词。

分类关键词与数据集中包含的协议有关，假设数据集中有两种不同类型协议报文，关键词kw只存在于一种类型的协议报文中，那么kw就是该种类型协议报文的一个分类关键词。格式关键词是协议字段，或者协议字段的组合。分类关键词集合和格式关键词集合可能存在交集，即协议关键词是分类关键词的同时，也可能是格式关键词。其他关键词既不是分类关键词，也不是格式关键词。格式关键词提取要求数据集纯度高，数据多样性好，覆盖时空分布。分类关键词提取对数据集样本没有特殊的要求。

协议报文格式可以看作协议字段序列，协议格式关键词序列不等价于协议报文格式，属于报文格式的一个子集。报文格式的形式会影响格式关键词边界的确定。以文本类协议和二进制协议为例:文本类协议的字段通常为特定的词，这些词由ASCII字符组成，易于理解，字段边界为预定义的分割符(例如空格或者回车换行)，因此格式关键词的边界易于确定;二进制协议结构紧凑，字段之间没有分割符，面向私有协议时，因缺乏先验信息，格式关键词边界确定较为困难。

1.2 问题模型

二进制协议数据帧的最小单元为比特，值域D={b0，b1}。第k个格式关键词kfk表示为kfk=bkfskbkfsk+1…bl…bkfek，bl∈D，其中:l表示比特在协议数据帧中的偏移位置;kfsk和kfek分别为kfk的起始边界点和终止边界点。二进制协议数据帧由格式关键词可以表示为 frk=kf1‖kf2‖…‖kfk‖…‖kfm，“‖”是串行的意思。二进制协议数据帧集合可以表示为Fr={fr1，fr2，…，fri，…，frn}。二进制协议格式关键词边界确定的最终目标是要解决一个后验概率问题p(i=kfskor i=kfek|bi)，即在已知第i比特位观测值bi的条件下，该比特位是格式关键词起始边界点或者终止边界点的概率。

格式关键词边界确定涉及两个关键问题:格式关键词边界提取和格式关键词边界选择。格式关键词边界提取结果为候选格式关键词边界，往往存在误警和虚警问题。关键词边界选择能够解决误警和虚警问题，筛选出与真实格式关键词边界最吻合的子集作为格式关键词边界确定的最终结果。

本文输入数据为同种类型二进制协议数据帧，第k个格式关键词边界在协议数据帧中的偏移位置为kfsk和kfek。二进制协议格式关键词边界确定问题可以描述为:在格式关键词数量m未知的条件下，对格式关键词边界{kfs1，kfe1，kfs2，kfe2，…，kfsm，kfem}的最佳估计。OBPFK的系统框图如图2所示，具体步骤如下:

步骤1 由迭代n-gram-position算法提取频繁项的边界{fitem1，fitem2，…，fitemp}作为候选格式关键词边界。

步骤2 以{fitem1，fitem2，…，fitemp}中各比特位的频繁项边界命中率和左右分支信息熵之差为基础构造分支度量，以协议关键词和非协议关键词的n-gram-position取值变化率存在差异为基础构造约束条件，通过最佳路径搜索算法从候选格式关键词边界中筛选出与真实格式关键词边界最接近的序列。

图2 OBPFK系统框图Fig.2 System diagram of OBPFK

2 OBPFK

协议格式关键词边界确定受数据集样本多样性影响。因为时间和空间限制，获取的数据集样本可能存在多样性不足的问题，一些原本不是格式关键词的比特串被当作格式关键词提取出来，给结果带来误差。例如，AIS协议［9］中经度和维度的高位在短时间内不会发生变化，如果仅用短时间内的数据样本作测试，提取的格式关键词中将包含经纬度高位，而经纬度高位不是真实的协议格式关键词。本文假设用于测试的数据集样本具有足够的多样性。

2.1 基于迭代n-gram-positon的格式关键词边界提取算法

由于二进制协议字段通常具有固定的长度和偏移［10］，使得二进制协议格式关键词一般也具有固定长度和偏移。本文在n-gram算法［11］基础上引入位置因素提出n-gram-positon算法，用于提取二进制协议数据帧的频繁项。同时，为了克服n-gram-position算法中n值不易确定的问题，采用不同n值的n-gram-position算法迭代提取频繁项，并将所有频繁项边界点作为候选格式关键词边界点。

n-gram算法输入为协议报文fr=b1b2…bi…bs(bi∈D)，输出 n-gram 为:b1b2…bn，b2b3…bn+1，…，bs－n+1bs－n+2…bs。例如序列“10001010”的所有3-gram为:“100”“000”“001”“010”“101”。本文在原有算法基础上引入位置因素，提出n-gram-position。考虑位置因素后序列“10001010”的所有3-gram-position 为: “100-1” “000-2” “001-3” “010-4”“101-5”“010-6”。n-gram-position 的输入为协议报文 fr=b1b2…bi…bs(bi∈ D)，输出 n-gram-position 为:b1b2…bn-1，b2b3…bn+1-2，…，bs－n+1bs－n+2…bs-(s－ n+1)。同一协议报文的n-gram-position不存在重复项。

n-gram-position算法中最关键的是n值如何确定。文献［4］提出协议数据的n-gram近似服从齐普夫分布，并且4-gram最接近齐普夫分布，因此设置n为4。本文为了防止不同协议数据下，单一n值的统计结果会出现偏差，进行了不同n值的频繁项提取，并将所有频繁项的边界点作为候选格式关键词边界点。

本文设定最小支持度 minsupport，用于判定n-gram-position是否为频繁项，支持度的定义如下。

定义3 给定报文集合Fr，fr∈Fr是其中的一个报文，如果fr包含n-gram，并且偏移位置为position±θ(θ为允许的误差 范 围)，则 fr(n-gram-position) = 1，否 则 为 0。n-gram-position在Fr上的支持度为:sup(n-gram-position)=/|Fr|，其中|Fr|为Fr中的报文总数。

构建候选格式关键词边界点的伪代码如下:

Begin

fitem={} //初始化

for n=N1to N2do //N1、N2为n取值的上下限

for i=1 to s－n+1 do

if sup(n-gram－i)＞minsupport do

fitem=fitem ∪ {i，i+n －1}

end

end

end

End

2.2 基于最佳路径搜索的格式关键词边界选择算法

基于迭代n-gram-position提取的候选格式关键词边界点中往往存在误警和虚警问题，需要通过格式关键词边界选择算法筛选出与真实边界最为接近的节点序列。利用候选格式关键词边界点可以构造有向图，如图2中最佳路径搜索部分，横轴表示候选格式关键词边界点，纵轴表示格式关键词数量，最终格式关键词边界可以表示为有向图中的一条路径(如有向图中实线所示)。通过最佳路径搜索算法可以找到这样一条路径。

2.2.1 分支度量与约束条件

1)分支度量。

分支度量用于衡量有向图节点之间的转移权值。最佳路径搜索算法应用于格式关键词边界选择，最终目标是寻找一条从第一个候选边界点到最后一个候选边界点权值之和最小的路径。分支度量决定搜索路径的走向，是利用最佳路径搜索算法完成格式关键词边界选择的关键。本文在定义分支度量时考虑了两方面因素:频繁项边界命中率、左右分支信息熵。

频繁项边界命中率是指在迭代n-gram-position提取频繁项的结果中各比特位作为频繁项边界点出现的次数与迭代总次数的比值。用=1表示协议数据帧第i比特位在n-gram-position提取频繁项过程中被确定为频繁项边界点，=0表示第i比特位没有被确定为频繁项边界点。式(1)表示第i比特位在迭代范围为(N1，N2)时被确定为频繁项边界点的总次数。第i比特位被确定为频繁项边界点的命中率如式(2)所示。

HR越大，其所对应的比特位越有可能成为格式关键词边界点。

左右分支信息熵反映了比特位左右两侧比特串的取值分布情况。基于协议关键词和非协议关键词的熵值存在差异，可以利用比特位左右分支信息熵的差值作为判定该比特位是否为格式关键词边界点的依据。左右分支信息熵包括左分支信息熵和右分支信息熵，计算式如式(3)、式(4):

比特位的左右分支信息熵之差越大，则该比特位成为格式关键词边界点的可能性就越大，即HDi越大，第i比特位越有可能成为格式关键词边界点。

结合频繁项边界命中率以及左右分支信息熵构造最佳路径搜索算法的分支度量，如式(8)。因为最佳路径搜索算法利用了最短路径搜索的思想，为了使最佳路径的权值之和最小，选择HRi和HDi加权之和的倒数作为分支度量。Bmi表示由其他节点到第i个节点的转移权值。Bmi越小，转移到第i个节点的可能性就越大。

其中:wHR和wHD分别为HRi和HDi对应的权值，wHR+wHD=1。

2)约束条件。

约束条件控制节点之间是否可达，限制搜索路径的走向，同时约束条件能够压缩搜索空间，避免运算过程中遍历路径太多，导致运算量过大［12］。本文构造约束条件基于协议关键词和非协议关键词的n-gram-position具有不同的统计特性。以n-gram-position的取值变化率作为统计特性的衡量指标，如式(9)所示:

如图3，协议数据中所有报文在比特串b3b4b5b6的第1个3-gram-position处的不同取值个数|| 为 2;3-gram-position所有取值情况的个数 G为8;取值变化率为 0.25。

图3 取值变化率Fig.3 Value change rate

若两比特位之间比特串的n-gram-position取值变化率的方差大于设定阈值限varth，则认为n-gram-position取值变化率差异较大，进而判定该比特串既包含协议关键词部分，也包含非协议关键词部分，两节点之间不可达。取值变化率方差如式(10):

其中 珔γ(i，j，n)表示取值变化率均值。2.2.2 最佳路径搜索算法

根据分支度量和约束条件，结合由候选格式关键词边界点生成的有向图，利用最佳路径搜索算法从有向图中找到与真实格式关键词边界最接近的一条路径作为最终格式关键词边界推断结果。最佳路径搜索算法的步骤如下:

1)设置指针指向起始节点fitem1。

2)判断搜索指针是否指向结束位置，若成立，转到步骤5);否则指针移到下一个候选边界点。

3) 根据约束条件 var(i，j，n)＜ varth推测节点 fitemi的可能上游节点fitemj。由已经得到的最短路径fitems=(fitem1，fitem2，…，fitemi)扩展为到节点fitemj的可行路径，并计算各可行路径的分支度量总和Bmi，直到完成对 fitemj所有可行路径的遍历。

4)根据最佳路径搜索原则，选择分支度量总和最小的一条路径作为到节点fitemj的最佳路径，转到步骤2)。

5)根据搜索结果得到最佳路径，最终实现对协议格式关键词边界的确定。

3 仿真与实验分析

3.1 实验设置

为了验证OBPFK在二进制协议格式关键词边界确定中的有效性，在 AIS1、AIS18、ICMP00、ICMP03和 NetBIOS五种类型协议报文的真实数据集上进行测试，测试数据集如表1所示。几种协议报文的格式规范可以参考文献［9，13－14］。由格式关键词定义，五种类型协议报文的格式关键词如表2所示。例如AIS1协议报文格式关键词列表中，1-6表示该类协议数据帧的1到6比特为一个格式关键词。

实验涉及的主要参数设置为:minsupport=0.95、N1=3、N2=6、r=4 和 varth=0.05。minsupport为最小支持度，用于判定n-gram-position是否为频繁项，本文针对同种类型协议报文做格式关键词边界确定，考虑到可能存在少量噪声数据，因此设置 minsupport=0.95。N1和N2为 n-gram-position 算法中n取值范围的上下限，具体见3.1.1节。r为统计左右分支信息熵时左右两侧比特串长度，经实验论证设置为4。varth为n-gram-position取值变化率方差阈值，一般取较小值，经实验论证设置为0.05。

表1 测试数据集Tab.1 Test dataset

表2 格式关键词Tab.2 Format keywords

本文采用协议逆向工程中常用的准确率、召回率和F值作为衡量指标。设OBPFK确定的格式关键词边界为W={w1，w2，…，wq}，真实的格式关键词边界为 Y={y1，y2，…，ym}，准确率、召回率和F值的计算式如式(11)～(13)所示:

3.2 算法参数及性能分析

3.2.1 算法参数分析

n-gram算法中参数n影响频繁项提取。n取值太小，提取的频繁项数量会偏多;n取值太大，提取的频繁项数量会偏少。本文统计了不同n值时五种协议对应的F值，如图4所示。

当n值逐渐增大时，F值先增大后减小;协议不同，最佳n值可能不同。为了减小误差，本文n值为一个范围，而不是一个确定的值。由图4可以看出，3≤n≤6时，几种协议的F值相对较大，n＞6以后，部分协议F值下降较快。为了使n取值尽可满足不同协议，同时考虑到计算成本，本文设置n的取值范围为:3≤n≤6。

3.2.2 算法鲁棒性分析

为了测试OBPFK算法鲁棒性，本节在同种类型协议报文集合中加入噪声数据，噪声数据为其他协议数据。统计不同比例噪声数据下的F值，如图5所示，随着噪声比例增加，算法性能逐渐下降，最终保持平稳。在有噪声的协议数据集中，算法性能与最小支持度阈值minsupport和噪声数据类型有关。当噪声数据所占比例大于1－minsupport时，通过minsupport定义提取的频繁项数量将大幅下降，从而导致算法性能下降。若噪声数据的报文格式与目标协议数据的报文格式相似，则噪声数据对算法性能的影响很难消除。若噪声数据的报文格式与目标协议数据的报文格式差异较大，则适当调整minsupport取值，即可消除噪声对算法的影响。

图4 不同n下的F值统计Fig.4 F value statistics under different n

图5 不同比例噪声下的F值统计Fig.5 F value statistics under different proportional noise

3.2.3 算法整体性能分析

本节对OBPFK的整体性能进行了测试。针对数据集中的五种不同类型协议报文，分别计算了准确率、召回率和F值，实验结果如图6所示，五种类型协议报文的F值均在83%以上。

图6 OBPFK整体性能Fig.6 Overall performance of OBPFK

3.3 与经典算法的性能对比

本节对OBPFK与经典算法进行了性能对比。选取VDV(Variance of the Distribution of Variances)［15］和AutoReEngine［5］作为对比算 法。VDV 和 AutoReEngine 与OBPFK相似，均是基于关键词作协议报文格式逆向，但两者均以字节为单位，忽略了二进制协议字段不受字节长度限制的特性。OBPFK以比特为单位作统计，与 VDV和AutoReEngine相比，具有更高的准确度。在不同协议数据集上，对三种算法的F值进行统计，结果如图7所示，可以看出OBPFK在三种算法中性能最好。与VDV和AutoReEngine相比，OBPFK的F值平均提升约8个百分点。

图7 不同算法性能对比Fig.7 Performance comparison of different algorithms

3.4 算法复杂度分析

假设数据集中协议数据帧个数为 n，数据帧长度为l。VDV算法计算构成协议数据帧各个字节的方差，计算复杂度近似为O(l);AutoReEngine算法基于Apriori算法，计算复杂度近似为O(nl2);OBPFK的复杂度主要由格式关键词边界提取和格式关键词边界选择两部分构成，为O(nl+k2)，k为候选格式关键词边界点个数。

4 结语

本文提出基于最佳路径搜索的二进制协议格式关键词边界确定方法(OBPFK)，通过迭代n-gram-position算法提取候选格式关键词边界点，利用最佳路径搜索算法从候选边界点中筛选出与真实格式关键词边界点最接近的子集，作为协议格式关键词边界确定的结果。在 AIS1、AIS18、ICMP00、ICMP03和NetBios五种不同类型协议报文数据集上测试结果表明所提方法具有不错的性能。但OBPFK只能提取协议格式关键词，而协议格式关键词序列只是协议报文格式的一个子集，如何完整地确定二进制协议的字段边界，获取协议报文格式，是未来需要进一步研究的课题。