基于TextRank算法的未知网络协议帧定位方法

刘治国,宋广跃,蔡文珠,刘庆利

(大连大学 a.通信与网络重点实验室; b.信息工程学院,辽宁 大连 116622)

0 概述

随着计算机网络技术的不断发展,越来越多的网络私有协议被应用于数据传输过程中,但此类私有协议通常不公开且具有固定格式[1-3]。如何从截获的通信数据中识别出网络私有协议是当前的一个重要研究课题,而在比特流数据中确定帧头和帧尾以获得完整的数据帧是该研究中亟需解决的问题。

国内外针对原始比特流形式的未知网络协议通信数据识别已开展了很多研究,但由于比特流数据具有随机性和无界性的特点[4-5],因此现有研究仍存在一定的局限性。文献[6]分析链路层协议通用帧格式以及通信数据中各帧之间的相互关联关系,通过对比特流数据中的序列进行统计和分析识别出同步序列,并以此为依据对比特流数据进行切分从而得到一个个完整的数据帧,但在序列统计过程中存在效率低下的问题。文献[7]对通信数据进行挖掘,通过挖掘到的频繁序列间的位置差分析其中的关联关系,推断出帧头位置及帧长并实现帧切分,但该方法仅在帧长不定的情况下性能较好。文献[8]通过改进传统模式匹配算法实现比特流中的序列统计,并结合比特流特点提出剪枝算法以提高序列统计效率,同时减少空间占用,利用该方法可提取出通信数据中的频繁序列,但其不适用于长频繁序列的统计。文献[9-10]采用数据挖掘中的关联分析方法提取多重关联规则序列并实现比特流切分,但该方法存在频繁度门限区间难以确定的问题。为实现比特流形式数据帧的有效定界,本文提出一种基于TextRank的未知网络协议帧定位方法(UPFLM),其能够在比特流形式的未知网络协议中准确定位数据帧的起始位置。

1 协议格式分析

无线网络通信数据的获取方式决定了预处理数据具有以下特点[11-12]:1)各帧首尾相接形成比特流;2)数据中只有“0”和“1”两种元素。同时,针对IEEE 802.11、IEEE 802.3、异步传输模式(Asynchronous Transfer Mode,ATM)等已知网络协议进行分析可知,完整的数据帧格式由帧头、控制段、数据段和检验信息等组成,所有组成部分又可分为固定域与可变域[13],因此比特流形式的未知协议数据格式如图1所示。

图1 比特流形式的未知协议数据格式

针对比特流形式的未知网络协议数据,为便于描述进行以下定义:

定义1比特流B的长度m为其所包含的比特个数。

定义2将比特流中长度为目标序列长度、位于不同位置的序列定义为一个节点,每个节点具有两个邻居节点。

定义3在长度为m的比特流B中,长度为n的序列的期望出现频率为Paverage。比特流B中长度为n的序列共有m-n+1个,而长度为n的序列存在2n种可能,因此:

(1)

2 基于TextRank的未知协议帧定位方法

由上文分析可知,在比特流形式的未知协议数据中可以通过挖掘帧头位置信息实现对帧的定位与切分。未知协议帧定位方法主要包括序列统计、关键序列提取以及帧头序列挖掘3个主要步骤。

2.1 基于FLSS算法的序列统计

序列统计过程可以参考传统模式匹配算法,其中,单模式匹配算法(如KMP、BM算法)每次遍历比特流仅能统计一个目标字符串,多模式匹配算法(如AC、Wu-Manber算法)扫描一次比特流便可统计出所有目标序列的出现次数[14-15]。

针对比特流协议的数据特点,为统计出比特流中出现的所有序列,本文通过对传统AC算法进行改进,提出定长序列统计(Fixed Length Sequence Statistics,FLSS)算法。在FLSS算法中包含目标序列的所有可能情况,采用枚举所有长度为n序列的方式产生目标序列,并将其通过数组的形式进行存储以构成字典,从而取代Trie树减少空间占用[16]。每个目标序列可以定义为一个状态,通过二元组形式表示为O(station,value),其中,station为状态描述,在字典数组中表现为数组的下标,value为状态的值,即序列的出现次数,在字典数组中表现为数组的值。同时,在统计过程中不存在匹配失败的情况,失败指针在这一过程中不起作用。为实现不同状态之间的跳转,综合考虑状态信息与读入数据之间的关系,设计状态跳转函数:

new_station=(station %2n-1)×2+new_bit

(2)

其中,n表示目标序列长度,new_bit表示最新读入比特位的值,station表示当前状态,new_station表示将要跳转的下一状态。根据状态跳转函数可将最新读入的比特值在状态间进行转换,从而统计出每个字符串的出现频次,最终得到每个状态station所对应的value值,即字典的数组值。

FLSS算法具体描述如下:

输入目标序列长度n,比特流B

输出二元组O(station,value)形式的状态信息

步骤1根据给定的目标序列长度n,枚举出所有目标序列,构造字典数组。

步骤2识别比特流B中初始长度为n的序列,更新其对应状态的station、value信息。

步骤3读入下一比特new_bit,根据状态跳转函数跳转到下一状态new_station并更新其value值。

步骤4若比特流B读取完毕,则跳转到步骤5;否则重复步骤3直至比特流B全部读取完毕。

步骤5按照二元组中的value值对各状态进行排序并输出其状态信息。

2.2 基于BitstreamRank的关键序列提取

在实际通信过程中,网络协议的特征字段通常很长,当利用FLSS算法进行序列统计时,需要建立长度为2n的数组,直接对长序列进行统计意味着大量的空间会被占用,并且由于序列具有向下闭包性[17-18],即某一频繁序列的子序列也是频繁序列,因此对短序列进行统计并进一步处理得到关键序列。

为通过序列统计得到比特流中的关键序列,本文引入自然语言处理中的关键词抽取算法TextRank[19],在此基础上提出BitstreamRank算法,基于投票原理得到每个节点的权重以实现关键词抽取。由于数据为比特流形式,因此算法主要包括状态初始权重计算、节点权重计算和关键序列提取3个步骤。状态初始权重计算的目的是设置状态的投票权重,计算公式为:

VW(stationi)=P(stationi)-Paverage=

(3)

其中,stationi表示比特流B中起始为第i位、长度为n的序列对应的状态,VW(stationi)表示stationi的投票权重,P(stationi)表示状态i在比特流B中的实际出现频率,Paverage为长度为n的序列期望出现频率。通过式(3)可以设置各状态的投票权重,当状态的实际出现频率P(stationi)小于期望出现频率Paverage时,其投票权重为负;当P(stationi)大于期望出现频率Paverage时,其投票权重为正。

为便于描述,将比特流中的每个序列定义为节点,状态权重计算过程即利用某一节点的邻居节点进行投票,从而获得该节点在比特流B中的权重WS,计算公式为:

(4)

其中,nodei表示比特流中起始为第i位、长度为n的节点,WS为节点权重,stationt表示节点nodei对应的状态,VM为状态的初始权重,d表示阻尼系数,其意义为某一节点指向其他任意节点的概率,通常取经验值0.85。

经过计算比特流中状态的权重可知,如果某一序列为比特流中的关键序列,则其表现为连续权重较高的状态。

长关键序列提取算法具体描述如下:

输入比特流B,各节点权重WS

输出长关键序列

步骤1查找各节点权重WS中的最大值max_WS。

步骤2按顺序遍历比特流B中的各节点。

步骤3如果节点权重大于0.75×max_WS,则判定此节点对应的序列为关键序列,执行步骤4;否则跳转到步骤2。

步骤4如果下一个节点的权重也大于0.75×max_WS,则将两序列按照位置关系合并为一个序列并重复步骤4;否则跳转到步骤5。

步骤5将得到的关键序列进行存储并记录起始位置,若遍历结束,则跳转到步骤6;否则跳转到步骤2。

步骤6输出长关键序列信息。

2.3 基于欧氏距离的帧头序列挖掘

帧定界问题中的关键是确定帧头和帧尾位置。为解决这一问题,本文在提取比特流中的关键序列后,根据关键序列对比特流进行切分并计算切分后各序列之间的相似度,从而确定帧头位置。

采用欧氏距离衡量序列间的相似度,两序列间的相似度计算公式为:

(5)

其中,str1、str2表示两序列,str1,m、str2,m表示两序列的第m位的比特值,dist表示两序列之间的欧氏距离,N为序列需要对比的长度,通常取两序列中较短序列的长度或根据需要人为设置。

由于比特流切分后会得到多个序列,因此在两序列相似度的基础上,以多序列间平均相似度为依据,按照平均相似度由高到低的顺序对关键序列进行排序。多序列间的平均相似度计算公式为:

(6)

其中,distaverage表示根据关键序列切分后得到的多个序列之间的平均相似度,k表示切分后得到的序列个数,ComTime表示需要比较的次数。经过排序后,平均相似度最高的关键序列位于帧头,根据此序列即可完成帧定位与切分。

3 仿真验证与结果分析

3.1 实验设置

为对本文算法进行验证,利用Wireshark软件对同一主机不同时间的通信数据进行采集,并将采集到的数据包转换为连续的比特流形式,从而生成实验所用数据集。数据集详细信息如表1所示。

表1 数据集信息

3.2 序列统计方法验证

为验证FLSS算法的有效性,采用上文构建的数据集进行实验验证。首先在J1数据集中对不同长度的序列进行统计,并与文献[5]中的改进AC算法和传统AC算法进行对比实验,序列统计时间对比结果如图2所示。可以看出,在数据集大小不变的情况下,3种算法的统计时间随目标序列长度的增加而增加。统计时间增加的主要原因为在序列统计过程中需要根据目标序列长度构建字典数组,目标序列越长,字典数组越大,构建时间也会增加。当数据集及目标序列长度相同时,FLSS算法优于改进AC算法和传统AC算法,其原因为改进AC算法及传统AC算法需要构建Trie树,且需统计长度为0～n的所有序列,而FLSS算法只需构建字典数组并统计指定长度的序列,因此FLSS算法的时间消耗低于其他两种算法。

图2 序列统计时间对比

为观察数据集大小对序列统计过程的影响,分别将J1数据集～J4数据集在不同目标序列长度下进行实验,实验结果如图3所示。可以看出,当目标序列长度不变时,序列统计时间随数据集大小的增长而增加。序列统计时间主要包含字典数组构建时间与比特流遍历时间,当数据集变大时,比特流长度增加,因此序列统计时间也随之增加。当数据集大小不变时,目标序列长度越长,统计时间越长,符合之前实验结论。综上所述,FLSS算法能够在不同大小的数据集中对不同长度的序列进行挖掘,且挖掘效果优于AC算法。

图3 4个数据集在不同目标序列长度下的统计时间对比

3.3 BitstreamRank算法有效性验证

为进一步验证BitstreamRank算法的有效性,对J1数据集进行序列统计后获取的数据进行处理,得到J1数据集的部分节点权重如图4所示。可以看出,BitstreamRank算法能够通过计算节点在数据中的权重有效识别出关键序列。

图4 J1数据集部分节点权重

利用BitstreamRank算法对上述关键序列进行提取,并将序列提取结果与Wireshark捕获到的原始数据进行对比分析,如表2所示。可以看出,BitstreamRank算法能够对连续比特流中的关键序列进行有效提取。

表2 J1数据集关键序列提取

3.4 帧定位与切分效果分析

根据上文所得的关键序列提取结果对比特流进行初步切分,并对不同序列切分后得到的结果进行相似度分析,按照相似度从高到低进行排序。实验首先对比本文UPFLM方法与文献[5]中的比特流切分方法(Bitstream Segmentation Method,BSM)的时间消耗,然后对两种方法的识别效果进行分析,采用准确率与误识别率衡量帧定位方法的准确度。

1)帧定位准确率R的计算公式为:

(7)

其中,Frecog表示定位结果中定位正确的帧数量,Ftotal表示数据集中包含的帧数量。

2)误识别率Regerr的计算公式为:

(8)

其中,Ferr表示帧定位过程中被错误判定为帧头的数量。

本文UPFLM方法与BSM方法在J1数据集～J4数据集上的帧定位时间对比结果如图5所示。可以看出,在整体帧定位过程中,UPFLM方法的帧定位时间少于BSM方法。其主要原因为BSM方法需对提取到的短序列进行序列拼接,并且要考察所有序列之间的位置关系来判定帧头位置,而UPFLM方法只需对位于不同位置的同一关键序列的后续序列进行分析,因此减少了帧定位时间。

图5 UPFLM与BSM方法的帧定位时间对比

UPFLM与BSM方法在J1数据集～J4数据集上的帧定位准确率对比结果如图6所示。可以看出,UPFLM方法能够有效对未知协议数据进行帧定位,准确率高于90%。但由于通信数据的数据段中可能包含相同的关键序列,这些冗余序列对切分结果会造成一定影响,因此通信数据的每一帧所包含的数据段越长,冗余序列出现的可能性越大,则帧定位效果越差。J4数据集的准确率低于其他两个数据集的主要原因为J4数据集中包含两种协议,当数据集只含有单一协议时,帧头序列保持不变,则定位准确率较高,当数据集有多种协议共存时,帧头序列具有多种可能,因此定位准确率会降低。

图6 UPFLM与BSM方法的帧定位准确率对比

对帧定位得到的结果进行统计,可以得到UPFLM与BSM方法的误识别率对比结果,如图7所示。可以看出,UPFLM方法的误识别率低于BSM方法。其主要原因为UPFLM方法只需判定后续序列相似度最高的关键序列位置为帧头位置,而BSM方法中多个特征序列之间的关系会对定位准确率产生影响。

图7 UPFLM与BSM方法的误识别率对比

综上所述,本文UPFLM方法能够在比特流形式的未知协议数据中成功定位出位于帧头的序列,依此判定帧头位置,并且在定位速度与准确率方面均优于BSM方法。

4 结束语

本文根据比特流形式的通信数据特点,利用FLSS算法统计出通信数据中目标序列的出现频率,并基于通信协议格式,在关键序列提取过程中引入BitstreamRank算法对关键序列进行挖掘,根据关键序列对比特流进行切分并计算切分后各序列之间的相似度,从而定位帧头位置。仿真结果表明,该方法能有效地对比特流形式的未知协议数据进行分析,从而完成帧定位与帧切分,并且在定位速度与准确率方面均优于BSM方法。后续将对通过本文UPFLM方法获得的帧数据做进一步分析,并在大量同类型未知网络协议的数据帧及关键序列基础上,准确提取出其格式特征,实现未知网络协议的有效识别。