一种二进制私有协议字段格式划分方法

秦中元,陆 凯,张群芳,黄星期

1(东南大学 网络空间安全学院,南京 210096)2(炮兵防空兵学院南京校区,南京 211132)

1 引 言

1967年,来自英格兰国家物理实验室的R.A.Scantleburry和K.A.Bartlett在一份备忘录[1]中最早把“protocol”这个英文单词用于描述数据通信的过程,现如今,各种标准化组织、网络通信技术方案提供者、网络运营商等纷纷制定了相应的公开协议.顾名思义,此类协议规格公开,使用的数据格式也属于已知范畴,如手机APP与后台交互时最常使用的HTTP协议,在家用路由器中配置地址时使用的DHCP协议等.与此同时,出于保护商业利益、信息保密等目的,或对于卫星、雷达、无人机等特殊设备而言,有时候设备间进行通信的协议规格不方便公开,于是产生了适用于此环境的私有协议.

在当前的网络环境中存在着一定程度的私有协议,且所占比重并不小.现如今可穿戴设备越发流行,可穿戴设备在认证等步骤中使用的蓝牙协议一般也是各厂商自定义的私有协议[2],目前各个厂商推出的智能家居系列产品大多也使用自定义的私有协议进行通信.此外,有资料显示巴西的RNP组织[3]通过分析国家研究与教育网络的流量组成,统计发现存在着接近30%的未识别网络协议.

对私有协议的逆向分析包含字段格式划分、语义分析和状态机推断几大方向,而协议字段划分有基于网络流量分析和基于执行轨迹分析两种主要方法.本文主要采用基于流量的分析方法来对私有协议进行格式划分.

对于基于特征选择与提取的协议格式划分,目前已有许多专家学者进行了相关研究.2007年,Cui[4]等人发表了Discoverer方案,面向应用层协议提取字段格式,引入了特殊标识(FD)鉴定方法,从报文首部到尾部依次寻找特殊标识,借此剥离不同格式的报文.2011年,Wang[5]等人提出了用于二进制协议特征挖掘的Biprominer方案,在不引入先验知识的情况下,基于统计特征进行关键词提取.2013年,Luo[6]等人发表了AutoReEngine方案,以单个字节为单位,所有单字节可能的取值为初始备选集,使用Apriori[7]算法获取关键词集合.2014年,张楠[8]提出了一种基于前导码对数据帧进行识别和划分的方案,并采用FP-growth算法来寻找其中的关联规则以完成协议特征信息提取.2015年,岳旸[9]等人发表了面向二进制数据帧的聚类系统,使用了改进的AC算法挖掘得到二进制数据帧中的频繁序列,然后使用Apriori算法挖掘特征之间的关联关系,在此基础上结合二进制数据帧特点对结果进行了剪枝操作.2016年,S Tao[10]等人提出了一种新颖的PRE-Bin方法,能基于细粒度位自动提取出二进制协议的二进制类型字段.2017年,李阳[11]等人发表了基于离散序列报文的协议格式特征自动提取算法,通过改进DBSCAN聚类和PrefixScan模式挖掘方法,通过对关键词进行筛选得到特征集合.邢长征[12]等人提出了一种基于三角矩阵和差集的垂直数据格式挖掘频繁项集的挖掘算法,大大减少了挖掘频繁项集时间和空间内存的开销.Z Xu[13]等人提出了一种名为MIDI的基于互信息差的协议格式快速提取方法,其基本思想来自于相邻字段之间的统计特性差异,并且MIDI只需要字段的局部对齐,而不是整个协议格式的对齐.H Xu[14]等人发表了基于无人平台监控状态数据的测量与控制协议的逆向分析,主要采用改进的BF算法和AP算法进行模式串匹配和关联规则提取,获得协议消息的初步格式.2018年,肖文[15]等人提出了两种新的量化度量数据集稀疏度的方法,这两种度量方法均考虑了频繁项挖掘任务背景下最小支持度对数据集稀疏度的影响,反映了事务频繁项集之间的差异度.

通过分析现有的基于频繁项挖掘的协议格式划分方案,我们发现其中主要存在着以下三个方面的问题:

1)频繁项长度问题.将频繁项挖掘算法应用到协议序列挖掘时,需要考虑协议设计特点.对文本类协议而言,在设计时通常以字节为最小单位确定字段长度,因此在构造频繁项时,采用以字节为单位的迭代或拼接方案是合理的.然而二进制协议在协议设计上比较灵活,并没有规定字段长度必须以字节为单位.

2)频繁项筛选问题.在频繁项筛选过程中,要求既保留最能反映序列特征的关键词,又尽可能减少关键词的遗漏,所以如何选择和设定指标就显得尤为重要.文本类协议常常使用特定字符作为分界,各个字段的值域分布相对比较固定,频繁项特征容易在序列数据集中反复出现,对于某字符串是否频繁这个问题是比较容易界定的.传统的应用Apriori算法进行频繁项挖掘的方案采用支持度和置信度进行特征筛选,对于文本类协议而言是可行的.然而二进制协议字段的值域分布比较丰富,不存在空格等明显的定界符号,在筛选时需要考虑频繁项出现的位置等其他信息进行辅助判断.

3)根据频繁项集合如何有效地进行格式划分的问题.常见的基于频繁项的格式划分方法追求尽可能全面和精确地构造频繁项集.对于格式划分问题通常采用直接在序列中寻找出相应频繁项的位置,将该频繁项的起始和结束位置推断为边界位置的方法进行划分.这种划分方法对频繁项集的可靠程度依赖性较高,出现少划分的可能性较大.

基于以上分析,本文提出了一种改进的基于频繁项挖掘的协议字段格式划分方法,其主要工作在于:

1)采用N-gram切分的方式,以半字节为最小单位获取候选频繁项集合,在构造候选项集的同时记录频繁项出现的序列编号及在序列中的位置,通过计算常见度和边界熵对频繁项进行筛选;

2)将筛选后的频繁项集作为语料库,采用自然语言处理中的正向最大匹配算法对协议序列进行分词并在分词位置进行计分,通过分数统计得到候选边界集,再在计算候选边界集中每个位置的信息熵后再次进行筛选,得到最终结果集;

3)对提出的算法进行了实验验证,仿真实验结果表明本文方法的有效性.

2 方法设计

2.1 总体流程

本文方法的总体流程如图1所示.考虑二进制协议中字段的长度可能小于一个字节且不一定是整数字节,选择基于N-gram模型以半字节为最小单位构造候选最大项集,然后使用常见度指标和位置熵指标进行筛选,最后使用自然语言处理中的正向最大匹配算法进行边界特征构造投票,并在获取到候选边界集合后,根据各个候选边界位置的信息熵大小再进行筛选.

图1 总体流程Fig.1 Overall process

其中,候选最大项集的定义为通过对字符序列按一定长度进行截取,得到的候选的关键词集合,由于在构建该项集之后,需要对该项集进行频繁项筛选,因此在构建时,此候选项集合在其生命周期中为容量最大的时段,因此命名为候选最大项集.

2.2 候选最大项集构造

考虑到研究对象为二进制协议,关键词长度并非总是以字节为单位出现,本文提出了一种基于N-gram模型的切分算法.

在构造最大项集时,首先确定切分长度范围,也即目标频繁项长度范围,考虑到二进制协议的特性,本文将最小迭代字节长度设定为半个字节,也就是使用0.5字节(4位比特位)、1字节(8位比特位)、1.5字节(12位比特位)和2字节(16位比特位)四种逐渐增加的长度进行频繁项挖掘.在确定频繁项长度范围之后,考虑使用N-gram模型从前向后对序列进行切分,并记录切分得到的子字符串内容、记录其出现的次数以及出现的位置.切分流程如图2所示.

最大项集构造算法如下:对于输入的协议数据集,遍历其中每一条协议数据,设定关键词长度为1到4,即关键词的最大长度为半个字节;而后根据关键词长度截取序列,判断是否已经存在该序列,若不存在,则保存,若存在,则更新其位置和出现次数等信息;最后输出所有保存的关键词序列.具体的算法流程如算法1所示.

算法1.最大项集构造算法

Input:dataSet:协议数据集

Output:map:哈希表

procedureCENSUSING(dataSet)

foralldataindataSetdo

length=data.length()

// 设定关键词长度为1到4,即最大为半个字节

forsize=1;size<5;size++do

forpointer=5;pointer

// 根据关键词长度截取序列,判断是否在map中

ifmapcontainsdata(pointer,pointer+i)then

gram=map.get(data)

// 修改map中存储的响应的gram,gram包含location等属性

insertlocationandidintogram

else

// 在map中新增gram

create a newgram

insertname,locationandidintogram

endif

endfor

endfor

endfor

returnmap

endprocedure

图2 候选最大项集构造Fig.2 Construction of the maximum set of items

在算法1中,根据事先设定好的size的初始值和递增步长,对协议序列集逐条进行了处理.由于本文设定频繁项的长度最小为半个字节,最大为两字节,而本文在数据手机时获得的协议序列是以字符串的形式体现,字符串中的一个字符表示半个字节长度.因此在算法中,相应的size初始值设定为1,最大递增到4.算法进行过程中,我们将每一个项定义为一个gram,保存在哈希表中.gram中除了记录了该项的名称,还记录着该项出现的次数和位置.在进行序列切分时,若切分得到的项在哈希表中找不到,那么就需要新建gram并加入到哈希表中,如果该gram在哈希表中存在,那么就可以通过哈希表寻找到对应项的内容并更新其中的出现次数和位置信息.

2.3 频繁项筛选

在最大项集构造完成后,需要对其进行筛选以得到频繁项集.本小节提出并使用使用常见度S和位置熵H进行频繁项筛选.

判断某个项是否频繁,首先需要判断其出现的频率是否达到某种阈值.因此频繁项出现的频率特征肯定需要作为频繁项筛选的依据之一.参考Apriori算法[7]中对支持度的定义,我们定义常见度S来表示频繁项在整个序列集合中出现的频繁程度.

定义1.常见度S为包含频繁项的序列数量与集合G中所有序列数量的比值,计算公式为:

(1)

通过计算常见度S对候选最大项集进行初步筛选后,可以筛去原集合中出现次数较少的项.但仅依靠常见度进行筛选是不够的.受AutoReEngine方案[6]使用方差分布推断频繁序列所在区域是否属于协议字段的启发,本文提出了一种新的反映项出现位置变化特征的指标,命名为位置熵H.

定义2.位置熵H.对候选频繁项而言,位置熵H用来表示该项在协议数据中出现位置的变化程度.位置熵H的计算基于香农提出的经典信息熵计算公式,定义为:

(2)

其中locations集合表示该项所有出现过的位置,实际上记录在该项对应的gram中.P(xi)为某个位置坐标xi在locations集合中出现的概率.

通过设定相应的常见度阈值可以筛选过滤掉出现次数较少的项,而通过计算位置熵可以筛选得到出位置熵为0的固定项集合以及位置熵波动较小的候选关键词集合用于后续进行字段格式推断.我们将位置熵为0的固定项集合记为fixSet,将位置熵波动较小的候选关键词集合记为wordSet.

图3 频繁项筛选Fig.3 Screening of frequent items

频繁项筛选流程如图3所示,对于3.1节中得到的最大项集,我们逐一进行计算其常见度和位置熵并与阈值进行比较,筛选掉常见度较小的项和位置熵较大的项.

2.4 边界投票

Proword[16]方案首次将自然语言处理中的投票专家算法和信息熵概念引入到了协议逆向中来.受此启发,如果在协议格式划分的过程中,将协议语言也看作是一种自然语言,在已经具备固定频繁项集合fixSet和候选关键词集合wordSet的条件下,将这两个集合看作中文分词中的固定搭配语料库和常见词语库,那么对于协议序列的格式划分操作就可以看作一种关键词匹配的分词行为.在自然语言处理中,匹配分词有正向匹配、反向匹配、最大匹配、最小匹配等多种方式可以结合使用.由于协议是通信双方约定的一种交流规范,通常认为协议的解析方在接收到发送方发来的协议信息时,是从协议信息的前部向后部进行协议解析的,使用最小匹配进行分词会使得频繁项集合中较短的频繁项被优先使用,导致整个协议序列产生过多划分,很容易造成协议字段的破碎.因此使用修改后的正向最大匹配算法,将频繁项挖掘过程中得到的固定项集合和关键词集合作为语料库进行分词,一定程度上就可以从分词得到的结果中推断出协议格式.

自然语言处理分词中的正向最大匹配算法从左到右将待分词文本中的连续字符与词表进行匹配,如果匹配成功就进行一次切分.这里的匹配成功包含两个条件,其一是当前连续字符组成的词语在词表中出现,其二是必须保证连接下一个字符后产生的词语不是词表中的词或词的前缀.在应用到本文中时,由于本文中设定的语料库为频繁项挖掘后得到的结果,与自然语言处理中真正的语料库在数量和长度范围上存在较大差异,故在将正向最大匹配的思想引入到协议格式划分时需要做出一定修改.具体的算法流程为:首先,设定关键词最大长度与最小长度,遍历序列数据集中的每条数据,从最大长度开始,逐渐减小其长度,先使用固定词集对该待匹配词语进行匹配,若匹配成功,则对该匹配词语投票加1,即匹配成功次数加1;然后再使用关键词集对该待匹配词语进行匹配,若匹配成功,则投票加1;在匹配过程中,应当通过循环,从前向后遍历整个序列.当遍历完序列数据集时,便可得到基于正向最大匹配的投票结果.具体的算法流程如算法2所示.

算法2.基于正向最大匹配的投票算法

Input:wordSet:关键词集;fixSet:固定词集;dataSet:序列数据集;maxL:关键词最大长度;minL:关键词最小长度

Output:υ(x):投票分数

procedureMATHING(wordSet,fixSet,dataSet)

foralldataindataSetdo

length=data.length()

point=0

whilepoint

// 从最大长度开始匹配

forj=maxL;j>0;j=j-1do

isFixed=data(point,point+1)

// 使用固定词集对待匹配词语进行匹配

ifisFixed∈fixSetthen

// 匹配成功则进行投票

υ(point+j-1)=υ(point+j-1)+1

point=point+j

endif

endfor

fork=maxL;k>minL- 1;k=k-1do

isWord=data(point,point+k)

// 使用关键词集对待匹配词语进行匹配

ifisWord∈wordSetthen

υ(point+k-1)=υ(point+k-1)+1

point=point+k

endif

endfor

// 通过循环从前向后匹配

point=point+1

endwhile

endfor

returnυ(x)

endprodedure

在对序列进行正向最大匹配和对对应匹配位置进行投票时,首先需要确定词语的最大长度maxL和最小长度minL,并初始化一个函数φ(x)用于记录投票分数.本文设定maxL为语料库中候选词语的最大长度2字节,相应的minL为0.5字节,并将函数φ(x)初始化为函数y=0.在匹配过程中,设置序列的头部为起始位置point,优先选择在固定词集fixSet中寻找长度为maxL的词语进行匹配,在无法完成匹配的情况下,通过逐步减少候选词语长度再进行匹配,直到词语长度小于minL.在上述过程中一旦出现成功匹配,设成功匹配的词语长度为sucL,则将起始位置point后移sucL位,并向结果函数中的(point+sucL- 1)位置进行投票,即φ(point+sucL-1)=φ(point+sucL-1)+1.如果始终无法完成匹配,则使用关键词集wordSet替换上述流程中的fixSet,重复相应操作.若仍然无法完成匹配,则将起始位置point移动到序列的下一个字符处.

2.5 边界筛选

在边界投票过程结束后,需要进行进一步的边界筛选.将投票结果映射为字段边界格式时,首先需要排除掉投票得分不为0但分数过低的位置项.投票的分数是否过低的标准是可以根据协议数据集的大小和投票的结果进行调整的.过低的分数实际上意味着协议序列在此位置进行划分的情况存在但罕见,因此对于该位置是否能被划分为字段边界的问题不具备足够说服力.

此外,由于在频繁项挖掘中为了控制算法的复杂度,我们对频繁项的长度做了限制,而实际上协议字段的长度在设计时并没有长短限制.本文规定的最长关键词长度为2字节,那么对于包含超过2字节字段的协议来说,在最大匹配的投票过程中显然就会出现所预测的边界比实际边界情况多的情况,所以对候选边界集非常有必要再进行边界的筛选操作.

筛选操作具体实现时同样利用了字段边界信息熵特点,对于初步划分得到的边界集合,计算集合中每一项对应位置的熵值,如果熵值为0,即对于数据集中的每一条协议序列,在该位置的字符都从未发生变化,那么就可以认定该位置是协议字段边界的可能性极小,极有可能为设定关键词长度过小导致的多划分,因而可以从边界集合中去除该项.如果熵值较大,则在协议格式推断的结果集中予以保留.

3 实验结果

本文在使用macOS10.12.5操作系统,装载了i5双核CPU的个人电脑上进行实验.共选取了446条ICMP协议数据、91条Zigbee协议数据和1559条Memcached协议数据作为实验对象,由于篇幅限制,本文只介绍Memcached协议数据的实验结果.

3.1 评估指标

在对实验结果进行评估时,经常使用的是召回率和准确率等较为常见的指标,但本文所研究的对象以及提出的方案并不适用于用这两种指标来进行评估.在保证实验过程中不引入协议规格,不知晓协议字节宽度的基础上,对于实验结果的评估我们提出两个指标,分别为格式划分的准确度和格式贴合的精确度.在介绍两个指标的计算方式之前,需要定义三个集合:

1)实验给出的划分结果集合:

Hexp={h1,h2,h3,…,hn}

(3)

2)真实、正确的协议格式边界集合:

Htrue={t1,t2,t3,…,tm}

(4)

3)考虑样本多样性的正确边界集合.考虑样本多样性的人工推测边界集合.由于我们掌握的实验数据在样本多样性上存在局限性,对于始终没有发生过变化的连续字段,我们是没有办法进行划分的,因此我们额外定义了一种考虑样本多样性的正确边界集合用于评估实验结果:

Hman={t1,t2,t3,…,tp}

(5)

定义3.准确度Z.格式划分的准确度主要着眼于准确性,对于结果推断中出现的误划分和多余划分容忍度较低,而对于少划分的情况容忍度较高,准确度Z的计算公式定义如下:

(6)

定义4.精确度J.格式贴合的精确度主要描述格式边界的推断点与真实字段比特位之间的偏差程度,对于格式边界的小幅度滑动容忍度较高,精确度J的计算公式定义如下:

(7)

考虑到实验数据样本的多样性对方案实验效果的影响,另设立实验准确度Zexp和实验精确度Jexp两项指标,使用人工推测边界集合Hman取代以上两式中使用的真实边界集合Htrue进行计算,即可得到实验准确度和实验精确度的大小,实验准确度和实验精确度越高,表示本文提出的方法代替人工进行格式划分的效果越好.

3.2 字段划分结果

通过对协议数据分别进行频繁项挖掘、最大匹配分词和投票,可以得到相应的投票分数,在此基础上通过基于信息熵的边界筛选,就可以得到最终预测的协议边界结果,并和真实格式边界和人工推测格式边界进行比较以验证实验的准确度和精确度.以Memcached协议为例,设定支持度阈值λS为0.3,位置熵阈值λH为2,并设定当某位置的投票值低于协议集合中数据个数的十分之一时,认为该位置不具备作为候选边界的资格,不将其加入到边界候选集中.实验中通过频繁项挖掘和最大匹配投票可以得到如图4所示的投票分数.

从图4中可以清晰地看到各个位置的投票情况,重点关注图像中分值非0的点,通过初次筛选,筛去分值较低的位置5后,可以得到协议边界候选集合为:

HMemcached={2,3,4,7,8,9,10,13,16,23,24,46,48}

接下来计算候选集合中每个位置的位置熵,筛去位置熵为0的位置3,7,9,13,23后,得到最终推测边界集合:

Hexp={2,4,8,10,16,24,46,48}

对于Memcached协议,通过资料可以查询到其真实的格式为:

Htrue={2,4,8,10,12,16,24,32,48}

而在考虑样本多样性的情况下,通过人工对所捕获到的协议数据进行分析,可以推测得到边界集合为:

Hman={2,4,8,10,24,48}

图4 Memcached协议投票结果Fig.4 Voting result of Memcached protocol

设人工推测得到的边界划分为划分情况1,协议真实字段边界为划分情况2,本方案推测得到的字段边界为划分情况3,以点图方式绘图可以得到图5.

图5 协议格式划分结果Fig.5 Comparison of the protocol format extraction

由于本文所提出的研究方案具有先验知识匮乏,纯依靠网络流量进行分析的特性,不可避免的会产生划分失当的情况.

与协议真实格式相比,本方案的实验结果中主要出现了少划分和误划分的情况,少划分的主要原因在于收集到的协议数据样本多样性不足,当两个连续字段始终没有产生过值域变化时,本方案中基于信息熵的筛选算法会将这两个字段中的边界筛除,从结果上看即为产生了少划分.误划分的原因主要在于协议的部分关键词之间可能存在有规律连续出现的问题,这样在最大匹配时会产生边界的轻微滑动,出现误划分.

与人工推测得到的协议格式相比,本方案实验结果出现了两处多划分的情况,主要是因为人工推测时主要考虑字段划分的准确性,对于变化域分界不明显的区域,考虑合并为一整个长字段,因而整体字段划分数量较少.相比而言,本方案则会给出一些较为精细的推断意见,从结果上看就以多划分的形式呈现出来.

通过计算可以得到划分的准确度为77.8%,精确度为75%,实验准确度为77.8%,实验精确度为91.7%,说明尽管存在划分不当的地方导致准确度还不够高,但精确度较高,表明格式位置滑动范围较小,方案整体效果较好.

3.3 方案比较

除了Memcached协议数据,另外使用预处理后的ICMP-1协议数据集合和Zigbee-1协议数据集合进行实验,并采用同样的指标将本文提出的方法与复现的AutoReEngine方案进行对比,比对结果如图6所示.可以看到除了在准确度方面,由于本文方案使用Zigbee-1协议数据进行实验时出现了一处由于边界滑动导致的误划分,使得准确度下降以外,在精确度和实验精确度方面,本文方案较AutoReEngine方案效果都更好.原AutoReEngine方案以字节为最小单位进行划分,采用了比较传统的Apriori方案进行频繁项挖掘,没有考虑到二进制协议的特点,因此其实验结果相对保守,实验中产生的误划分和多余划分的情况并不多,但相对的对字段切分位置的贴合程度上就会有所欠缺,因此在更加重视字段划分精准程度的精确度和实验精确度指标上,显然现有的方案效果更佳.综上,使用本文方案得到的划分结果与协议规格的贴合度更高,也进一步证明了本文方案的可行性.

图6 方案效果对比Fig.6 Comparison of different schemes

4 结束语

本文提出了一种基于频繁项挖掘和最大分词匹配的协议格式划分方案,首先充分考虑到了二进制协议与文本类协议在格式划分时的差异,采用基于N-gram的切分方式以半字节为最小单位获取候选频繁项集合,其次在构造候选项集的同时记录频繁项出现的序列编号及在序列中的位置,由此可以方便地计算得到常见度和边界熵从而对频繁项进行筛选.将筛选后的频繁项集作为语料库,采用正向最大匹配算法进行分词投票,通过分数统计得到候选边界集,最后经过计算位置信息熵进行筛选得到协议格式划分的结果.实验结果证明,本文提出的方法能够实现协议格式划分的目标.