开放科学(资源服务)标志码(OSID)：

0 概述

随着网络通信规模迅速扩大和大量新的移动应用出现，小众通信协议和未公开专有协议的数量逐年递增^[1]，无线网络^[2]在网络通信中的使用比重逐年增大^[3-4]。对于提高网络服务、检测流量异常和通信对抗而言，识别协议是最基本的要求。有研究指出，准确的协议特征提取是协议识别的关键^[5]，只有在原始数据中准确地挖掘出未知协议的特征，才能以此为依据对后续未知协议数据进行有效的对比识别。由于比特流形式的协议包含的数据特征形式较为单一，因此提取关键的比特流序列作为协议特征是一种有效的方式^[6]。通过挖掘特征序列所在帧内位置、特征序列帧内位置关系等辅助信息，并将关键序列、序列位置和序列位置关系作为复合特征，可提高协议识别的准确率。

目前，对比特流形式的未知通信协议进行特征提取已有较多研究。文献[7]针对零知识环境下协议特征提取准确率不高的问题，提出比特流未知协议的复合特征提取方法，把协议中频繁项和偏移位置2个属性作为协议特征，提高了特征提取的准确率，但该方法获得的只是单一的字段，提取的特征较为单一。文献[8]针对AC(Aho-Corasick)算法特征候选集中元素数量随时间和频繁项长度增加呈指数级增加的问题，提出CFI(Combined Frequency Items)算法。该算法是AC算法和Apriori结合并优化的方法，其采用AC算法生成频繁字节项，并由Apriori算法进行频繁项匹配得到协议特征。文献[9]通过改进基于互信息的特征选择算法和帧特征选择算法对比特流未知协议帧进行特征提取。该方法有效但是特征包含信息较单一，影响了协议识别准确率。文献[10-11]先对原始数据进行聚类，再对不同的簇进行分析，从中挖掘到地址字段作为协议特征，但同样存在特征单一影响协议识别效率的问题。文献[12]提出了多模式匹配和关联规则相结合的比特流协议特征提取方法，通过改进AC算法提取频繁项，减少了频繁候选元素和对数据的扫描次数。但该方法需要建立一个深度为切分长度的字典树，若频繁项长度过长，则构建字典树就会越复杂。文献[13]提出基于特征分析矩阵的特征码提取方法。该方法无需建立字典树，而是根据协议特征序列前n个比特对应的十进制为索引建立特征分析矩阵，数据扫描时定位更准确且效率更高，同时也达到了改进AC算法的效果，但仍未解决特征每增加一个比特就要扫描一次数据的操作问题。

为提高未知协议特征提取的准确率，本文提出一种基于序列统计的特征提取方法FEMSA。统计定长序列出现的位置和频次，以序列是否固定和交互作为筛选条件来提取频繁项，从而提高频繁项提取的效率。同时通过关联规则连接频繁序列，去除冗余的序列信息来优化频繁项集，最终得到协议特征集合。

1 比特流形式协议

本文主要对比特流形式的未知无线协议帧集合进行特征提取研究。根据已知无线协议(如IEEE 802.11、IEEE 802.3等)格式分析可知，完整的帧格式由帧头、控制段、数据段、验证信息等组成，这些部分又可以分为固定域和变化域^[14]。固定域包括固定序列和交互序列。固定序列为在同一位置内只出现一种序列或者固定出现几种序列，若2种序列交替出现，则称为交互序列。此外，变化域可称为数据域，指各种变化的数据序列。协议数据帧示例如图 1所示。

为在后文中方便描述，做以下定义：

定义 1  $ {F}_{i} $为提取出的频繁项，$ {C}_{i} $为提取出的协议特征，两者都由三元组$ [{S}_{i}, {L}_{i}, {P}_{i}] $表示。其中：$ {S}_{i} $为统计序列；$ {L}_{i} $为序列$ {S}_{i} $在帧内出现的位置；$ {P}_{i} $为序列$ {S}_{i} $在位置$ {L}_{i} $出现频率，频率阈值$ \mathrm{m}\mathrm{i}\mathrm{n}\_\mathrm{s}\mathrm{u}\mathrm{p} $可以通过Jaccard系数^[15]来获得。

定义 2  二元组$ [{L}_{ij}, {T}_{ij}] $表示某一序列的位置和在当前位置出现的频次。其中：$ {L}_{ij} $为序列出现的位置；$ {T}_{ij} $为序列在位置$ {L}_{ij} $处出现的频次。

定义 3  二元组$ [{S}_{ij}, {P}_{ij}] $表示在帧内某一位置上出现的序列和序列在当前位置出现频率。其中：$ {S}_{ij} $为在某一位置处出现的序列；$ {P}_{ij} $为$ {S}_{ij} $序列在当前位置出现的频率。

2 基于序列统计的特征提取方法

常用的协议特征提取方法是遍历统计，即统计可能出现的比特组合各种状态出现的频次，选取出现频次多的比特组合供后续研究使用。若未知协议特征长度不固定，则需要在扫面数据帧集时逐次增加比特数，由此带来因反复扫描数据帧集而造成分析工作量大的问题。对此，文献[13]提出了基于特征分析矩阵的协议特征获取方法FAMM。该方法无需反复扫描数据帧集，但是需要创建特征分析矩阵存储每一个备选特征序列的后续一定长度字符串，且备选特征序列长度增加需扫描特征分析矩阵。当源数据量很大时，需要增大空间创建分析矩阵，而当特征长度逐次增加比特时，则需要反复扫描特征分析矩阵。因此，文献[13]方法并未从本质上改变因长度变化导致的多次扫描数据时间消耗的问题。

本文结合闭包性思想^[16]提出一种定长统计序列频繁度的方法，通过遍历一次数据，建立一个序列长度为l bit的特征分析矩阵A，记录统计序列、序列的位置和频次，同时统计频次大于$ \mathrm{m}\mathrm{i}\mathrm{n}\_\mathrm{s}\mathrm{u}\mathrm{p} $的序列，得到初始频繁项集。

对频繁序列仅通过出现的频次进行筛选，造成出现错误序列的可能性较大，对此，本文增加筛选条件以降低误识率。如图 1所示，由于协议中存在固定和交互序列，因此为提高特征提取准确率和协议识别效率，挖掘更多的协议特征信息，本文根据概率统计^[17]和相似性度量^[18]思想，在满足频繁条件的序列中提取固定和交互序列，得到频繁项集。由于前序提取结果中存在序列重叠的问题，因此得到的频繁项集中存在大量的冗余信息。此外，真实的协议特征长度是不固定的，采用定长序列统计的方法无法完整表达协议特征。本文引入关联规则^[19]的思想连接相关频繁序列，以得到更长的频繁序列，并以更长频繁序列替换原有的频繁序列更新频繁项集，将协议特征集提取分为频繁项集提取和关联规则连接频繁序列两部分。特征提取过程如图 2所示。

2.1 频繁项集提取

初始频繁序列提取过程。设初始序列长度l，将2^l种l bit组合作为初始序列进行统计。扫描数据，统计所有2^l种长度为l的比特组合出现的位置和频次以及存储位置和频次，构成特征分析矩阵A。该矩阵含有2^l行，为列可增矩阵，每行元素数量不定，每个元素表示为$ [{L}_{ij}, {T}_{ij}] $。特征分析矩阵A存储多种序列出现的位置和频次，矩阵的一行表示同一序列出现的位置和频次，表示如下：

${\boldsymbol{A}} = \left[ {\begin{array}{*{20}{c}} {{a_{11}}}&{{a_{12}}}& \cdots &{{a_{1n}}}\\ {{a_{21}}}&{{a_{22}}}& \cdots &{{a_{2n}}}\\ \vdots & \vdots &{}& \vdots \\ {{a_{m1}}}&{{a_{m2}}}& \cdots &{{a_{mn}}} \end{array}} \right], {a_{ij}} = \left[ {{L_{ij}}, {T_{ij}}} \right]$

构造特征分析矩阵(Construct the Feature Analysis Matrix，CFAM)算法描述如下：

算法  CFAM算法

输入  $ n $帧比特流形式的数据

输出  特征分析矩阵$ \mathit{A} $

步骤1  初始化矩阵行数2^l，每行均含0个元素，初始化匹配位置$ {L}_{i} $。

步骤2  取数据帧中$ {L}_{i}~{L}_{i}+l $处的比特组合，设为$ {S}_{i} $，对应的十进制为d，位置是$ {L}_{i} $。在特征分析矩阵中第d行遍历元素，查看是否存在位置$ {L}_{i} $元素。若不存在，将频次$ {T}_{dj} $设为1，并在这行的尾部添加；若存在，将频次$ {T}_{dj} $加1。

步骤3  若一帧数据结束，则初始化位置$ {L}_{i}^{} $，进行下一帧数据遍历，重复步骤2，直至遍历完$ n $帧数据，特征分析矩阵建立完成。

遍历特征分析矩阵，统计每个序列$ {S}_{i} $频率值$ P\left({S}_{i}\right) $：

$ P\left({S}_{i}\right)=\frac{T\left({S}_{i}\right)}{n} $

(1)

其中：$ T\left({S}_{i}\right) $为序列$ {S}_{i} $出现的频次；$ n $为数据帧数。当$ P\left({S}_{i}\right) > min\_sup $时，将序列$ {S}_{i} $、$ {S}_{i} $位置$ {L}_{i} $和频率$ {P}_{i}=P\left({S}_{i}\right) $表示为$ [{S}_{i}, {L}_{i}, {P}_{i}] $，加入到初始频繁项集。

根据概率统计和相似度思想提取固定序列和交互序列对初始频繁项集进行筛选。由于协议固定序列和交互序列出现的情况与位置和包含内容有关，因此根据初始频繁项集构建一个索引为位置$ {L}_{i} $的查询矩阵B，存储特征序列和频率。查询矩阵B是一个列可增矩阵，由二元组$ {b}_{ij} $组成，存储在不同位置上出现的序列和序列在当前位置上出现的频率，矩阵的一行表示在相同位置上出现的所有序列和序列频率。表示如下：

${\boldsymbol{B}} = \left[ {\begin{array}{*{20}{c}} {{b_{11}}}&{{b_{12}}}& \cdots &{{b_{1n}}}\\ {{b_{21}}}&{{b_{22}}}& \cdots &{{b_{2n}}}\\ \vdots & \vdots &{}& \vdots \\ {{b_{m1}}}&{{b_{m2}}}& \cdots &{{b_{mn}}} \end{array}} \right], {b_{ij}} = \left[ {{S_{ij}}, {P_{ij}}} \right]$

通过对大量协议帧集统计得出固定序列和交互序列在协议中存在的规律，通过查询矩阵B对满足规律的固定序列和交互序列提取到频繁项集。

固定序列和交互序列提取(Fixed and Interactive Sequence Extraction，FISE)算法描述如下：

算法  FISE算法

输入  查询矩阵B

输出  频繁项集$ \mathrm{F} $

步骤1  按行遍历查询矩阵，若在位置$ {L}_{i} $上出现唯一序列$ {S}_{i} $且出现的概率$ P\left({S}_{i}\right)=1 $时，将序列$ {S}_{i} $视为固定序列，加上位置$ {L}_{i} $和概率$ P\left({S}_{i}\right) $构成三元组，提取到频繁项集，否则当概率不为1，跳转步骤4；序列不为1，否则跳转执行步骤2。

步骤2  若在位置$ {L}_{i} $有2个元素，计算2个元素中序列$ {S}_{1} $、$ {S}_{2} $的相似度：

$ \mathrm{s}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{r}({S}_{1}, {S}_{2})=\frac{|{S}_{1}\bigcap {S}_{2}|}{|{S}_{1}\bigcup {S}_{2}|} $

(2)

当$ \mathrm{s}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{r}({S}_{1}, {S}_{2})\ge \mathrm{r}\mathrm{e}\mathrm{p}\mathrm{e}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{e} $时，将2个序列加上位置和频率构成三元组作为交互序列提取到频繁项集；否则跳转执行步骤3

步骤3  若在位置$ {L}_{i} $上出现多个初始频繁序列$ {S}_{1}, {S}_{2}\cdots {S}_{n}, $且$ \mathop \sum \limits_{i=1}^{n}P\left({S}_{i}\right)=1 $时，则将序列$ {S}_{i} $视为固定序列，加上位置$ {L}_{i} $和频率$ P\left({S}_{i}\right) $构成三元组，提取到频繁项集；否则跳转步骤4

步骤4  若在位置$ {L}_{i} $上存在多个(> 2)元素，且元素中各序列$ {S}_{i} $的频率和不为1时，则$ \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{t}\left({L}_{i}\right) $为位置$ {L}_{i} $上所有序列组成的集合，计算$ \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{t}\left({L}_{i}\right) $与其他所有任意一个集合$ \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{t}\left({L}_{j}\right) $的相似度：

$ \mathrm{s}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{r}\left(\mathrm{U}\mathrm{n}\mathrm{i}\mathrm{t}\right({L}_{i}), \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{t}({L}_{j}\left)\right)=\frac{\left|\mathrm{ }\mathrm{U}\mathrm{n}\mathrm{i}\mathrm{t}\right({L}_{i})\bigcap \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{t}({L}_{j}\left)\mathrm{ }\right|}{\left|\mathrm{ }\mathrm{U}\mathrm{n}\mathrm{i}\mathrm{t}\right({L}_{i})\bigcup \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{t}({L}_{j}\left)\mathrm{ }\right|} $

(3)

当$ \mathrm{s}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{r}\left(\mathrm{U}\mathrm{n}\mathrm{i}\mathrm{t}\right({L}_{i}), \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{t}({L}_{j}\left)\right)\ge \mathrm{r}\mathrm{e}\mathrm{p}\mathrm{e}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{e} $时，将2个位置上所有序列加上位置和频率构成三元组作为交互序列提取到频繁项集，否则读取下一行。

步骤5  判断查询矩阵是否遍历完成，若完成，则输出频繁项集，否则跳转执行步骤1。

在位置$ {L}_{i} $上的序列出现频率为1，对单协议而言这样的序列一定是此协议的固定序列，在位置$ {L}_{i} $上出现的序列频率和为1，说明在当前位置反复出现几个序列，这几个序列亦是此协议在当前位置上的固定序列。当$ \mathrm{s}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{r}\left(\right) $值超过$ \mathrm{r}\mathrm{e}\mathrm{p}\mathrm{e}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{e} $阈值时，即在$ {L}_{i} $位置超过$ \mathrm{r}\mathrm{e}\mathrm{p}\mathrm{e}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{e} $的数据在$ {L}_{j} $位置的集合中也出现了，将位置$ {L}_{i} $和$ {L}_{j} $出现的初始频繁序列作为交互序列提取出来；若在位置$ {L}_{i} $上，2个初始频繁序列具有$ \mathrm{r}\mathrm{e}\mathrm{p}\mathrm{e}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{e} $的相似度，则作为交互序列提取出来。

上述方法能够识别提取固定序列和在2个位置出现或相同位置出现的相似度很高的交互序列。在分析中出现固定序列和交互序列提取冲突时，以交互序列提取为准。但是交互序列的提取存在一定的局限性：提取的数据必须是短时间内有交互的数据，即对于在某些设备只发送信息而不接收信息或在另外的设备只接收信息而不发送信息的环境下抓取的数据帧，用此方法提取交互序列存在一定困难性。

2.2 关联规则连接频繁序列

本文引入关联规则的思想，通过频繁序列连接(Frequently Sequence Connected，FSC)算法连接频繁项集中的序列得到更长频繁序列，更新频繁项集。此操作能够去除冗余信息，得到更为精简的频繁序列，最终得到协议特征集。

频繁项集$ F=\{{F}_{i}, {F}_{j}, \cdots , {F}_{n}\}, {F}_{i}=[{S}_{i}, {L}_{i}, {P}_{i}] $，判断$ {F}_{i} $和$ {F}_{j} $中的序列是否在位置上存在$ {L}_{i}\le {L}_{j}+\left|{S}_{j}\right| $或者$ {L}_{j}\le {L}_{i}+\left|{S}_{i}\right| $的关系，若2个序列存在上述位置关系，记为$ {S}_{i}{S}_{j} $或者$ {S}_{j}{S}_{i} $，以前者为例计算连接后在帧集中出现的频率$ P\left({S}_{i}{S}_{j}\right) $和两的置信度。

连接后出现$ {S}_{i}{S}_{j} $的频率如式(4)所示：

$ P\left({S}_{i}{S}_{j}\right)=\frac{T\left({S}_{i}{S}_{j}\right)}{n} $

(4)

其中：$ T\left({S}_{i}{S}_{j}\right) $为$ {S}_{i}{S}_{j} $出现的频次；$ n $为数据帧数。置信度如式(5)所示，表示在$ {S}_{i} $出现的帧数据上$ {S}_{j} $也出现的概率：

$ \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{f}({S}_{i}\to {S}_{j})=\frac{P\left({S}_{i}{S}_{j}\right)}{P\left({S}_{i}\right)} $

(5)

通过FSC算法对频繁项集中的频繁序列根据关联的思想进行连接，去除频繁项集中冗余信息，优化频繁项集得到协议特征集。算法描述如下：

算法  FSC算法

输入  频繁项集$ F $

输出  协议特征集$ C $

步骤1

while(集合$ F $未遍历完成){

将集合$ \mathrm{F} $中所有项添加到$ \mathrm{F}\text{'} $中；

任取集合$ \mathrm{F} $中两项$ {\mathrm{F}}_{\mathrm{i}} $和$ {\mathrm{F}}_{\mathrm{j}} $，序列为$ {\mathrm{S}}_{\mathrm{i}} $和$ {\mathrm{S}}_{\mathrm{j}} $；

If($ {\mathrm{L}}_{\mathrm{i}}\le {\mathrm{L}}_{\mathrm{j}}+\left|{\mathrm{S}}_{\mathrm{j}}\right| $或者$ {\mathrm{L}}_{\mathrm{j}}\le {\mathrm{L}}_{\mathrm{i}}+\left|{\mathrm{S}}_{\mathrm{i}}\right| $){

连接两者，得到长频繁序列$ {\mathrm{S}}_{\mathrm{i}}{\mathrm{S}}_{\mathrm{j}} $($ {\mathrm{S}}_{\mathrm{j}}{\mathrm{S}}_{\mathrm{i}} $)，记为$ {\mathrm{S}}_{\mathrm{z}} $；

If(概率$ \mathrm{P}\left({\mathrm{S}}_{\mathrm{z}}\right) $和置信度$ \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{f}\left(\right) $是否满足连接的阈值){

加上位置为$ {\mathrm{L}}_{\mathrm{i}} $($ {\mathrm{L}}_{\mathrm{j}} $)和频率为$ \mathrm{P}\left({\mathrm{S}}_{\mathrm{z}}\right) $表示为三元组替代$ {\mathrm{F}}_{\mathrm{i}} $和$ {\mathrm{F}}_{\mathrm{j}} $两项；更新频繁项集$ \mathrm{F}\text{'} $；}Else{

继续遍历集合}}Else

继续遍历集合}

步骤2

while($ \mathrm{F} $！= $ \mathrm{F}\text{'} $) {

跳转执行步骤1，参数集合$ \mathrm{F}=\mathrm{F}\text{'} $；}

将$ \mathrm{F} $集合中所有的项添加到$ \mathrm{C} $集合中

步骤3  输出集合$ \mathrm{C} $

3 仿真验证与分析 3.1 仿真设置

对本文算法进行实验验证，利用Wireshark软件对一小局域网中通信使用的协议，并将得到的协议数据转换为连续的比特流形式的数据帧，从而生成实验所用数据集。利用已知协议数据而不引进先验知识模拟未知无线协议数据，验证本文方法的可行性。仿真数据集信息如表 1所示。

3.2 仿真结果分析 3.2.1 频繁序列统计方法仿真验证

采用数据集J1验证频繁序列统计时间随序列长度变化而变化。由图 3可以看出，频繁序列的统计时间随序列长度增加而增加。时间增加的原因包括：改进的AC方法需要构建"字典树"，且长度越长，构建的"字典树"越大，消耗的时间越多；特征分析矩阵方法虽然不需要构建"字典树"，但是目标序列长度越长，建立的矩阵越大，目标序列增加长度遍历矩阵的时间会越长。本文方法消耗时间较少，这是因为算法不需要存储统计序列的后续一段序列，且只需要遍历一次分析矩阵，时间只花在创建特征分析矩阵和频繁项提取上。

3.2.2 协议特征提取仿真验证

本文将F-measure评价方法^[20]运用到特征提取方法的验证中，分析通过协议特征集识别协议消息的结果，以反映协议特征提取的效果。本文使用的评价指标为准确率和召回率。在F-measure评价方法中，以T_P表示实际上属于该类型协议且被识别为该类型的协议帧数，以F_P表示实际上不属于该类型的协议但被识别为该类型的协议帧数。

1) 特征提取准确率$ R $定义为通过协议特征序列识别协议消息类型的正确率，如式(6)所示：

$ R=\frac{{T}_{\mathrm{P}}}{{T}_{\mathrm{P}}+{F}_{\mathrm{P}}}\times 100\mathrm{\%} $

(6)

其中：T_P是识别正确的协议帧数；F_P是误识别的协议帧数。

2) 特征提取的召回率$ r $定义为通过协议特征序列识别协议类型正确的帧数与该类型协议数据帧总数量的比率，衡量的是通过协议特征序列识别协议类型的查全率，如式(7)所示：

$ r=\frac{{T}_{\mathrm{P}}}{N}\times 100\mathrm{\%} $

(7)

其中：$ N $是此类消息数据帧的数量。

本文方法和FAMM方法的特征提取准确率和召回率对比如图 4和图 5所示。由图 4可以看出，本文方法可以对多种未知协议进行有效的特征提取，且准确率高于90%。但是由于比特流形式的未知协议数据特征单一，假特征出现的可能性较大。从图 5特征提取召回率来看，基本上所有正确特征都被提取出来，存在极小部分个性特征未被提取出。综上，本文提出的协议特征提取方法能够在比特流形式的未知协议数据中成功提取协议特征集，并且在速度与准确率方面优于FAMM方法。

4 结束语

本文根据比特流形式协议通信数据的特点，提出一种基于序列统计的未知无线协议特征提取方法。通过统计定长序列出现的频率和位置并结合特征分析矩阵提取频繁序列，以降低频繁序列统计的时间。根据固定序列出现概率和交互序列相似性筛选频繁序列得到初始频繁项集，提高频繁序列提取的准确率，同时引入关联规则的思想连接频繁序列，去除冗余序列信息得到协议特征集。仿真结果表明，本文方法在准确率和效率方面较FAMM方法取得了较大的性能提升。下一步将在获取协议特征的基础上对大量数据帧和协议特征进行分析，准确提取出协议所表达的语义，达到识别未知协议的目的。