0 概述

协议状态机推断需要获取协议会话中的报文状态类型, 该状态类型标识了报文在会话中的逻辑顺序与功能^[1-3]。例如, TCP协议报文中的6位控制代码:URG, ACK, PSH, RST, SYN, FIN, 其不同的取值组合代表了不同的状态类型。能够表征协议状态类型的字段称为状态相关字段^[4]。

根据获取报文状态类型方法的不同, 现有关于协议状态机推断的相关研究可以分为基于聚类和基于状态相关字段2种类型。文献[5]通过层次聚类为每条报文分配类别标签, 将协议会话报文序列转化为类别标签序列, 构建初始状态机并对其进行化简, 得到最小确定状态机。但是, 其将报文之间的格式相似性作为相似性度量标准, 对于格式相似但状态类型不同的报文, 该方法将无法进行区分。文献[6]采用Dunn指数^[7]与Jaccard指数^[8]分别确定聚类类别数与报文相似性, 最终利用PAM算法^[9]实现报文聚类。但是, 其同样以聚类后的类别标签代替协议报文, 与文献[5]方法面临相同的问题。上述方法虽然易于实现, 但报文的格式类型与状态类型间不存在一一映射关系, 一些格式相似但状态类型不同的报文可能被聚为一类, 最终导致状态机推断错误。

文献[4]认为同种协议的会话具有相似的逻辑, 协议的状态信息由状态相关字段唯一确定。该文将二进制协议会话报文序列转化为状态相关字段序列, 并构建初始状态机。文献[10]利用统计方法提取状态相关字段, 通过邻接矩阵表示协议报文间的时序关系。文献[11-12]基于指令序列划分协议字段, 从中选取状态相关字段用于协议状态机推断, 但文中并未详细说明状态相关字段的具体选取方法。上述研究利用状态相关字段的不同取值来表示协议报文的状态类型, 较符合实际情况, 得到的状态机准确性较高。但面向私有协议时, 因为缺少先验信息, 导致难以准确获取状态相关字段。

在协议字段划分的基础上^[13], 筛选状态相关字段是推断二进制协议状态机的关键步骤。本文提出一种基于状态相关字段的二进制私有协议状态机推断方法BSMISRF。根据最长公共子序列距离(the Longest Common Subsequence Distance, LCSD)进行协议状态相关字段识别, 构建初始状态机并去除异常会话, 然后基于出度、入度进行相似状态合并, 在此基础上, 化简初始状态机以构建概率协议状态机。

1 问题描述

不同于文本类协议, 二进制协议的字段不受字节长度的限制, 字段之间不存在明显的定界符, 导致其字段划分比文本类协议困难^[13]。协议状态机只与协议的状态相关字段有关。状态相关字段的取值可变, 同种类型的协议字段中往往存在多个可变字段。在无先验知识的条件下, 状态相关字段极易与其他可变字段混淆, 从而给协议状态相关字段识别造成困难。

文献[14-16]根据所得的状态相关字段, 构建状态相关字段序列, 由该序列生成APTA树, 然后化简状态机。在会话数量较多时, 构造的状态前缀树往往过于庞大, 状态机化简需要大量的比较操作。

由训练集协议会话构建的状态机是一个特化的状态机, 只能接受训练集中的协议会话。异常报文序列的存在导致协议状态机中可能出现错误的状态转移。此外, 当协议状态类型较多时, 所构建的状态机过于复杂, 不易于理解。为构造正确、具有较小规模的协议状态机, 需要对初始状态机进行化简。因此, 进行二进制私有协议状态机推断需要解决协议字段划分、状态相关字段选取、初始状态机构建以及状态机化简等关键问题, 其流程如图 1所示。

假设输入的同种类型的协议报文集合为X={x₁, x₂, …, x_i, …, x_n}, x_i=b_i1b_i2…b_ij…b_im表示第i条二进制协议报文, b_ij∈{\0b0, \0b1}。经过协议字段划分后, 第i条二进制协议报文表示为x′_i=f_i1‖f_i2‖…‖f_ik‖…‖f_ip, f_ik=b_ij1b_i(j1+1)…b_ij2表示第i条协议报文的第k个字段, “‖”表示链接。由协议报文集合X重构的协议会话集为S=(s₁, s₂, …, s_i, …, s_N), s_i=(x_i1, x_i2, …, x_ij, …, x_iM)表示第i个协议会话, x_ij表示第i个协议会话的第j条协议报文。结合协议字段划分结果, 第i个协议会话为s′_i=(x′_i1, x′_i2, …, x′_ij, …, x′_iM), 第i个协议会话的第j个字段序列为s′_ij=(f_i1j, f_i2j, …, f_ijj, …, f_iMj), f_ijj表示第i个协议会话第j条协议报文的第j个字段。假定选取的状态相关字段为协议报文的第k个字段, 则与协议会话s_i相对应的状态相关字段序列为s_if=(f_i1k, f_i2k, …, f_ijk, …, f_iMk)。以s_if作为输入, 构建初始状态机, 通过协议状态的删除、合并操作实现状态机化简。

2 BSMISRF算法 2.1 基于LCSD的状态相关字段识别

在构建初始状态机时无法直接使用协议会话s_i=(x_i1, x_i2, …, x_ij, …, x_iM), 需要将协议会话用状态相关字段进行表示, 构建与协议会话对应的状态相关字段序列s_if=(f_i1k, f_i2k, …, f_ijk, …, f_iMk), 并作为初始状态机的输入, 如图 2所示。在面向私有协议时, 先验信息未知, 无法直接获取协议的状态相关字段, 需要先进行字段划分, 将s_i转换为s′_i=(x′_i1, x′_i2, …, x′_ij, …, x′_iM), 再根据划分结果识别状态相关字段, 最终构建状态相关字段序列s_if。

文献[4]总结出协议会话的特性:

1) 同种协议的会话具有相似的行为逻辑。

2) 协议行为逻辑由状态相关字段表示。

因此, 同种协议会话的状态相关字段序列具有相似的行为逻辑。文献[4]首先计算同种协议中不同会话的各字节方差, 如式(1)所示。然后计算不同会话的同一字节方差分布的方差(Variance of the Distribution of Variances, VDV), 如式(2)所示。最终, 将VDV最小的字节作为状态相关字节。

$ \sigma_{i k}^{2}=\frac{\left(f_{i1 k}-\overline{f}_{i k}\right)^{2}+\left(f_{i2 k}-\overline{f}_{i k}\right)^{2}+\cdots+\left(f_{i M k}-\overline{f}_{i k}\right)^{2}}{M} $

(1)

其中, σ_ik²表示第i个会话第k个字节的方差, f_i1k表示第i个会话第1个报文的第k个字节, f_i1k=b_i1j1b_i1(j1+1)…b_i1j2, j₁=8×k－7, j₂=8×k, M表示会话中的报文数。

$ \sigma_{k}^{2}=\frac{\left(\sigma_{1 k}^{2}-\overline{\sigma}_{k}^{2}\right)^{2}+\left(\sigma_{2 k}^{2}-\overline{\sigma}_{k}^{2}\right)^{2}+\cdots+\left(\sigma_{N k}^{2}-\overline{\sigma}_{k}^{2}\right)^{2}}{N} $

(2)

其中, σ_k²表示第k个字节的VDV, N表示会话数。

文献[4]算法(简称为VDV算法)对于协议状态机推断有一定效果, 但方差仅能反映样本的离散程度, 很难体现样本间的顺序约束关系与行为逻辑。例如, 在某会话集中, 只有同种类型协议的2个会话:会话1与会话2, 会话的第2个字段序列如图 3所示。采用VDV算法, 会话1和会话2的第2个字段序列相似, 因为会话1第2个字段序列的元素全部包含在会话2第2个字段序列中。根据式(1)、式(2)可知, σ₂²取值较小时, 第2个字段可能被识别为状态相关字段。但事实上, 会话1和会话2的第2个字段序列所包含的元素虽然相似, 但不同元素间的顺序差别较大, 即会话1和会话2的行为逻辑存在较大差异。由此可见, VDV算法仅能刻画序列所包含元素的相似性, 而无法体现序列元素的顺序相似性。

为解决上述问题, 本文提出一种基于LCSD的协议状态相关字段识别算法。LCSD是基于最长公共子序列的一种距离, 对于一个序列s, 如果其分别是2个或多个已知序列的子序列, 且在所有符合此条件的序列中长度最长, 则称s为已知序列的最长公共子序列。最长公共子序列可以通过动态规划进行求解, 式(3)是LCSD的计算公式。

$ d\left(s_{i_{1} j}^{\prime}, s_{i_{2} j}^{\prime}\right)=1-\frac{\left|L C S\left(s_{i_{1} j}^{\prime}, s_{i_{2} j}^{\prime}\right)\right|}{\min \left(\left|s_{i_{1} j}^{\prime}\right|, \left|s_{i_{2} j}^{\prime}\right|\right)} $

(3)

其中, d（s′_i1j, s′_i2j)表示字段序列s′_i1j和s′_i2j之间的距离, LCS(s′_i1j, s′_i2j)表示s′_i1j和s′_i2j的最长公共子序列, |LCS(s′_i1j, s′_i2j)|表示最长公共子序列的长度, |s′_i1j|和|s′_i2j|分别表示s′_i1j和s′_i2j的长度。

例如, 有状态相关字段序列s′₁₂=(1, 2, 3, 4, 5, 6)和s′₂₂=(1, 2, 3, 4, 6, 5), LCS(s′₁₂, s′₂₂)=(1, 2, 3, 4, 5), d(s′₁₂, s′₂₂)=1－5/6=0.17, 因此, 序列s′₁₂和s′₂₂最长公共子序列距离为0.17。有序列s′₁₂=(1, 2, 3, 4, 5, 6)和序列s′₃₂=(6, 5, 4, 3, 2, 1), LCS(s′₁₂, s′₃₂)=∅, d(s′₁₂, s′₃₂)=1－0/6=1, 因此, 序列s′₁₂和s′₃₂最长公共子序列距离为1。由此可见, LCSD不仅能够刻画序列所包含元素的相似性, 同时能反映序列元素的顺序相似性, 即行为逻辑相似性。序列所包含的元素相似, 元素逻辑顺序也相似, 则LCSD较小。在会话集中, LCSD之和最小的字段序列为状态相关字段序列, LCSD之和的计算如式(4)所示。

$ D_{j}=\sum\limits_{i_{1}, i_{2} \in(1, | S |), i_{2}>i_{1}} d\left(s_{i_{1} j}^{\prime}, s_{i_{2} j}^{\prime}\right) $

(4)

其中, |S|表示会话集中的会话数量, D_j表示会话集中所有会话的第j个字段序列的LCSD之和。最小D_j对应的字段为状态相关字段, 用f_s来表示。

基于LCSD进行状态相关字段识别的具体步骤如下:

步骤1  获取同种协议的会话, 构造协议会话集S={s₁, s₂, …, s_N}。

步骤2  设置指针指向协议报文的第0个字段。

步骤3  判断指针是否指向最后一个字段, 若是, 转到步骤5;否则, 指针指向下一个字段, 转到步骤4。

步骤4  提取会话集中不同会话的第j个字段序列{s_1j, s_2j, …, s_|S|j}, 计算D_j, 转到步骤3。

步骤5  根据规则选取最小D_j对应的字段, 将其作为状态相关字段。

识别出状态相关字段后, 将会话集中的所有会话用状态相关字段序列进行表示, 并作为初始状态机的输入, 如图 2所示。

2.2 基于邻接表的初始状态机构建

构建初始状态机的主流方法是构建APTA树, 然后接受所有状态相关字段序列并进行合并化简。该过程会导致初始构建的APTA树过于庞大, 需要大量的比较操作^[10]。本文利用邻接表构建初始状态机, 省去APTA树的相关过程。假设协议会话用状态相关字段序列表示为:

0001→0010→0011→0100→0101→0010

初始协议状态邻接表如表 1所示。状态0为起始状态, 没有对应的状态相关字段, 表示不存在一个状态在接受一个报文后能够转移到初始状态。输入状态相关字段序列的第1个值“0001”, 状态相关字段所在的列不存在“0001”, 因此, 添加“0001”到列表中, 同时添加状态1, 表示在接受到状态相关字段“0001”代表的报文后, 协议由之前的状态转移到状态1。在状态0对应的出度列中添加状态1, 表示状态0可以转移到状态1, 更新后的邻接表如表 2所示。将整个状态相关字段序列输入到状态邻接表中, 结果如表 3所示。最后一个值为“0010”, 已经在状态相关字段列中存在, 因此, 只需更新状态5的出度, 将状态2添加到状态5的出度列表中即可。

协议状态机的终止状态往往不止一个, 为构建便于理解的协议状态机, 本文标识终止状态, 同时记录每个转移出现的次数, 最终构造概率协议状态机, 如表 4所示。其中, 2(T)表示状态2可以作为终止状态, 1:1表示由状态0到状态1的转移出现了1次, 其余标识同上。将会话集中所有会话对应的状态相关字段序列添加到协议状态邻接表中, 当输入的状态相关字段已存在于状态邻接表中时, 只需更新出度列表; 否则, 先添加新的状态再更新出度列表。

由表 4状态邻接表还原出的概率协议状态机如图 4所示, 其中, 状态2可以作为终止状态, 用2个同心圆表示, “50%”表示状态2有50%的概率成为终止状态, 转移弧线下方的百分比表示各出度的比例。例如, 状态1只有一个出度状态2, 该出度的概率如式(5)所示。

$ p_{1}(1, 2)=\frac{n(1, 2)}{n(1, :)}=\frac{n(1, 2)}{n(1, 2)}=100 \% $

(5)

其中, p₁(1, 2)表示状态1的出度状态2出现的概率, n(1, 2)表示状态1到状态2的转移出现的次数, n(1, :)表示状态1的所有出度的总次数。

2.3 协议状态机化简 2.3.1 基于概率统计的异常会话去除

在真实环境中, 用户操作失误或者传输环境变化通常会导致不完整或错误会话的出现, 本文将其统称为异常会话。包含小概率转移的会话为异常会话, 异常会话在整个数据集中比例较小。利用含有异常会话的数据集推断的协议状态机会存在错误。本文统计各个转移出现的概率, 发现概率小的转移后定位转移所在的会话, 将该会话剔除, 然后在不包含异常会话的协议数据集上重新构建状态邻接表。

表 5所示为当前构建的状态邻接表, 输入状态相关字段序列0001→0011→0100→0101后, 状态邻接表如表 6所示。其中, 状态1有2个出度, 分别为状态2和状态3, 状态1到状态3的概率如式(6)所示, 状态1到状态2的概率如式(7)所示。状态1到状态3的概率仅为1%, 为小概率事件, 设置阈值θ_th, 当转移概率小于θ_th时, 对应转移为异常转移, 对应会话为异常会话。如果直接删除异常转移, 不做其他处理, 则异常会话的剩余部分仍然存在于状态邻接表中。为彻底消除异常会话的影响, 本文在确定异常转移与异常会话后, 将所有的异常会话从原始数据集中进行消除, 再对剩余的会话重新构建新的状态邻接表。

$ p_{1}(1, 3)=\frac{n(1, 3)}{n(1, :)}=\frac{n(1, 3)}{n(1, 3)+n(1, 2)}=1 \% $

(6)

$ p_{2}(1, 2)=\frac{n(1, 2)}{n(1, :)}=\frac{n(1, 2)}{n(1, 3)+n(1, 2)}=99 \% $

(7)

2.3.2 基于出度、入度的相似状态合并

经过前文的处理, 协议状态邻接表中不存在相同的协议状态相关字段。虽然没有相同的状态, 但可能存在相似的状态。为最大限度地化简状态机, 需要将相似状态进行合并。协议状态之间存在2种关系:顺序和并列, 如图 5所示。顺序关系指状态之间存在先后顺序, 例如状态1在状态0后, 两者是顺序关系。并列关系指状态之间没有先后顺序, 例如在状态2之后状态3~状态5都有可能出现, 状态3~状态5之间没有先后顺序, 属于并列关系。具有并列关系的状态属于相似状态, 可以合并, 图 6所示为合并图 5中相似状态后的状态机。

相似状态在状态邻接表中表现为入度和出度均相同。表 7所示为一个协议状态邻接表, 各状态相应的出度、入度如表 8所示。状态3~状态5的入度均为状态2, 出度均为状态6, 因此, 状态3~状态5为相似状态, 可以合并。合并后的状态邻接表如表 9所示, 状态3~状态5合并为状态3, 状态相关字段合并到状态3的相关字段, 包含状态4和状态5的出度列表统一更新为状态3, 并对相同出度对应的次数进行合并。

基于概率统计的异常会话去除和基于出度、入度的相似状态合并, 可以分别看作从原数据集和初始状态机2个方面对协议状态机进行化简。

3 实验结果与分析

为验证BSMISRF算法对二进制协议状态机推断的有效性, 选取TCP协议和SMB协议进行协议状态机推断。实验环境为一台PC(CPU i7-4720HQ, 内存8 GB), 操作系统为Windows 7, 利用Python编程语言进行程序编写测试。通过Wireshark软件在校园骨干网上采集数据包, 再通过五元组实现TCP协议会话分割, 获取TCP协议会话集。在PC上设置共享文件夹, 在手持客户端上安装文件共享软件, 通过文件共享软件对共享文件夹进行操作, 如文件创建、删除等, 利用Wireshark软件采集操作过程中产生的SMB协议数据包, 再通过五元组实现SMB协议会话分割, 获取SMB协议会话集。实验中使用的训练数据集和测试数据集信息如表 10、表 11所示。

在实验过程中, 仅涉及一个参数θ_th, 本文设定θ_th为0.01。评价指标采用协议逆向工程中常用的准确率和召回率, 如式(8)、式(9)所示。

$ precision_{p}=\frac{n_{p}^{t}}{n_{p}} $

(8)

$ recall_{p}=\frac{n_{p}^{t}}{n^{p}} $

(9)

其中, precision_p和recall_p分别表示协议p的准确率和召回率, n_p表示测试集数据被识别为协议p的会话数, n^p表示测试集数据中真正属于协议p的会话数, n_p^t表示被识别为协议p且真正属于协议p的会话数。

3.1 协议状态机推断结果

由BSMISRF算法推断的TCP和SMB协议状态机分别如图 7、图 8所示。在TCP协议状态机中, 路径0→1→2→3表示协议中3次握手建立连接的过程, 4→5→3→5→3和3→5→3→5→3均为TCP协议4次挥手关闭连接的过程。SMB协议状态相关字段对应的命令码如表 12所示, 路径0→1→2→3表示SMB协议的会话建立过程。

3.2 VDV算法与LCSD算法性能比较

VDV算法和LCSD算法均是状态相关字段选取算法, 前者只能刻画序列元素的相似性, 后者既能体现序列元素的相似性, 又能反映序列元素行为逻辑的相似性。图 9、图 10所示分别为TCP协议和SMB协议的状态相关字节/段选取结果。其中, 纵坐标中的“log”表示对纵坐标值取以e为底的对数。VDV算法以VDV最小取值对应字节为协议状态相关字节(VDV取值为0的是不可变字节)。LCSD算法以D最小取值对应字段为协议状态相关字段(D取值为0的是不可变字段)。对于TCP协议, 能够表示协议状态的是6位控制代码:URG, ACK, PSH, RST, SYN, FIN, 在TCP协议报文的第14个字节第7个字段。VDV和LCSD均能找到TCP协议的状态相关字节/段, 如图 9(a)和9(b)。对于SMB协议, 能够表示协议状态的是Command字段, 在SMB协议报文的第5个字节第2个字段。VDV算法无法找到SMB协议的状态字节, 如图 10(a), LCSD算法能够找到SMB协议的状态相关字段, 如图 10(b)。

3.3 化简前后的协议状态机规模比较

本文基于概率统计进行异常会话去除, 基于出度、入度实现相似状态合并, 以对初始状态机进行化简。化简前后的状态机规模如表 13、表 14所示。其中, NS_TCP和NS_SMB分别表示TCP和SMB协议的初始状态机, S_TCP和S_SMB分别表示TCP和SMB协议的最终状态机。TCP协议数据集中不包含相似状态, 但存在异常会话, 因此, 状态数和终止状态数没有变化, 只有状态转移数得到了约简。SMB协议数据集中存在相似状态, 也存在异常会话, 因此, 状态数、状态转移数以及终止状态数均得到了约简。2种协议的约简比例如图 11所示。

3.4 协议状态机性能评估

将TCP协议和SMB协议的混合会话集作为测试数据集, 如表 11所示, 利用推断的TCP协议状态机和SMB协议状态机分别对测试数据集中的会话进行识别, 准确率和召回率结果分别如表 15、表 16所示。由表 15、表 16可以看出, 本文协议状态机对测试数据集有较好的识别效果, 与真实协议状态机接近。

4 结束语

本文提出一种基于状态相关字段的二进制私有协议状态机推断方法BSMISRF。在TCP协议和SMB协议数据集上进行测试, 结果验证了该方法良好的识别性能。在实际应用中, BSMISRF方法对字段划分的准确度要求较高, 因此, 对二进制协议字段格式提取进行分析并获取高准确度的字段划分结果, 将是下一步的研究方向。