基于状态相关字段识别的未知二进制协议状态机逆向方法*

孟凡治，刘 渊，张春瑞，李 桐

(中国工程物理研究院计算机应用研究所，四川绵阳621900)

1 引言

随着互联网的发展，网络的安全形势变得越来越严峻。通信协议是网络的一个重要组成部分，协议规范是安全人员理解协议的根本。而在信息对抗领域，从截获的电磁信号中识别出通信协议规范是获取信息层信息的基础。针对未公开的通信协议，从通信数据中挖掘协议规范已成为协议逆向分析的一个研究热点。

协议规范挖掘分为语义和行为挖掘两部分，语义挖掘主要指协议格式挖掘，行为挖掘则是状态转移关系挖掘[1]。现有研究多数只关注协议格式的逆向[2－4]，而没有关注协议状态机的逆构。仅少量研究分析了协议状态机逆构问题[5－7]。

文献[8]提出了针对文本协议通过统计方法提取消息关键字，并根据消息关键字构建协议状态转移关系。文献[9]提出了概率状态机模型的概念，通过统计状态对在报文序列中出现的次数来计算状态间的转移概率。对于同一协议的不同会话数据，该方法构造出的状态转移关系将不同。

上面的研究成果仅针对文本协议。文献[10]提出了基于状态相关字段的二进制协议状态转移关系重构方法，但该方法存在处理协议帧中存有未对齐字段的协议数据时将失效的缺陷。文献[11]根据协议帧中最长公共子串对协议帧进行聚类与状态标记，由于协议状态的转换是由数据帧中关键字段引起，而不是由最长公共子串引起，因此该方法不太有效。

在二进制协议状态逆构过程中，协议状态的有效提取是整个过程的难点。本文提出了基于对应字段对齐和状态相关字段识别的未知二进制协议状态机重构方法，该方法从通信数据中识别出协议帧中的状态相关字段，并根据状态相关字段的变化情况构建二进制协议状态转移关系。最终基于该方法设计了一个根据通信数据逆构协议状态转移关系的状态机转移图重构系统。在整个系统中，基于改进的渐进多序列比对算法的相应字段对齐方法和基于字段统计量分析的状态相关字段提取方法是从协议帧中准确提取协议状态的基础。使用网络上真实运行协议的通信数据作为测试对象对系统进行测试，结果表明该系统能够有效地重构出二进制协议的状态转移关系。

2 系统结构

该状态转移图重构系统主要包括通信数据捕获、相应字段对齐、状态相关字段识别和协议状态机重构四部分，各模块的关系如图1所示。

图1 系统总体结构图Fig.1 The system architecture

2.1 通信数据捕获

使用网络抓包工具Wireshark捕获原始的网络通信数据，并使用恰当的过滤器来获取需要进行状态重构的协议的通信数据。

2.2 相应字段对齐

为了呈现并凸显协议帧中字段的特征以便进行统计分析，需要对协议帧字段进行对齐处理。协议帧中有些字段的取值在通信过程中几乎是不变的，以这些字段作为对齐基准可将协议帧中的相应字段对齐。本文采用改进的渐进多序列比对算法来对齐协议帧中相应字段。

2.3 状态相关字段识别

协议帧中仅有少量的字段与协议状态转换相关，本文称这些字段为状态相关字段，如TCP协议帧中的Flags字段就是状态相关字段。通过分析多个通信流中字段取值的分布的分布(Distribution of the Distribution of the Variances，DDV)来识别协议帧中的状态相关字段。

2.4 协议状态机重构

协议状态机重构模块负责根据状态相关字段构建协议状态机，结果将以状态转移图的形式输出，以便分析人员理解协议的行为逻辑。

3 基于状态相关字段的协议状态重构

3.1 理论基础

协议规范是协议实体进行通信时构造数据帧以及传输数据帧必须遵守的约定。数据帧的构造和传输严格受限于协议规范，因此协议规范的一些特征将在大量的通信数据中凸显出来，这也是能从通信数据中逆向出部分或全部协议规范的理论基础。

下面列出了一些适用于多数通信协议的准则，这些准则给予我们设计协议状态重构系统的灵感。

(1)协议帧的格式具有一定的结构，而不是随机的;

(2)在不同时间、不同地点重复通信过程，特定版本协议的帧结构是不变;

(3)同一个协议的多个通信过程具有相似的行为。

3.2 相应字段对齐

采用改进的渐进多序列比对算法来实现相应字段的对齐。渐进多序列比对算法主要涉及到局部序列比对算法、全局序列比对算法、协议进化树构建和替换矩阵构建四部分。局部序列比对算法用于计算两个序列间的相似程度，全局序列比对算法用于两个序列相应字段对齐。局部序列比对和全局序列比对都是二序列比对算法，要进行渐进多序列比对，需采用局部序列比对算法构建协议进化树，然后以协议进化树为指导，迭代采用全局序列比对算法进行渐进多序列比对。在局部序列比对、全局部序列比对和渐进多序列比对过程中，得罚分参数则是由替换矩阵提供，替换矩阵的构建方法将严重影响三种比对算法的比对结果，因此本文重点对替换矩阵的构建方法进行改进，使其适用于数据帧序列的比对。

3.2.1 局部序列比对算法

局部序列比对算法能够识别出两个序列的最相似子序列。虽然局部序列比对算法不能识别出协议帧中的字段，但它能够将相似的序列聚类在一起，以便后续使用全局比对算法将协议帧中的相应字段对齐。本文采用典型算法Smith Waterman作为局部序列比对算法，协议帧序列P和Q比对的得分矩阵的计算方法由式(1)、(2)、(3)给出:

式中，S(i，j)表示得分矩阵中第i行第j列的元素的得分情况;P[i]和Q[j]分别表示序列P的第i个元素和序列 Q 的第 j个元素;μ(P[i]，Q[j])表示序列P的第i个元素和序列Q的第j个元素比对时的得罚分函数，在经典的比对算法Needleman Wunsch中，采用了匹配得2分，不匹配得0分的条件函数。

得分矩阵计算完成后，基于得分矩阵采用动态规划算法就能提取协议帧序列P和Q的最长相似子序列。

3.2.2 全局序列比对算法

在通信过程中，协议帧中的许多字段几乎是不变的。与局部序列比对算法相反，全局序列比对算法能提取通信过程中协议帧中的字段。本文采用典型算法Needleman Wunsch作为全局序列比对算法。全局序列比对算法得分矩阵的构建同局部序列比对算法得分矩阵的构建方法基本相同，唯一不同之处在于它们采用不同的替换矩阵以及路径回溯方法。获取全局序列比对结果的路径回溯过程(算法1)如下:

3.2.3 协议进化树构建

为了更好地理解协议帧序列的结构，需要将多个协议帧进行比较。渐进多序列比对算法是一种快速有效的多序列比对算法。为了进行协议帧渐进多序列比对，首先需要构建协议进化树用于指导协议帧序列的比对过程。协议进化树的构造过程(算法2)如下:

算法2中dij的计算方法由式(4)给出:

式中，dij表示聚类Ci和Cj的距离，Dpq表示由局部序列比对算法Smith Waterman计算出的协议帧序列间的距离。

3.2.4 改进的替换矩阵

序列的比对结果受替换矩阵严重影响。构造合适的替换矩阵是生成合理的协议帧序列比对结果的基础。全局序列比对算法Needleman Wunsch采用匹配得2分，不匹配得0分的简单替换矩阵。但是该替换矩阵不适合于协议帧序列的比对。通过设计合适的替换矩阵，使得空位被插入到协议帧中最合适的位置，从而使协议帧中相应字段精确对齐。改进的替换矩阵的构造过程(算法3)如下:

根据协议帧序列的比对结果对替换矩阵进行调整，能够使得特殊数据帧中的字段也正确对齐到相应位置，从而提升了比对精度，更利于后续的字段统计特征分析工作。

3.3 状态相关字段识别

协议帧中不同字段具有不同功能，协议规范对协议帧中各字段的约束限制也不相同，因此各字段数据具有不同的统计特征。通过对各字段的统计特征进行分析，进而从中发现符合状态相关字段统计特征的状态相关字段。本文通过计算多个通信流中字段取值的分布的分布来识别协议帧中的状态相关字段。由于下面3条准则的存在，所以该方法是有效的:

(1)同一协议的不同通信流通常具有相似的行为逻辑，这样协议才能稳定地完成通信过程;

(2)协议的通信逻辑由协议帧中的状态相关字段表现;

(3)不同通信流中，状态相关字段总是表现出相同的行为。

使用字段取值的分布(Distribution of the Variances，DV)作为字段的统计特征量，不同的字段将具有不用的DV。由于通信协议设计时需要考虑简单、高效、稳定等特性，所以通信协议通常仅有少量的状态，即状态相关字段的DV将是相对较小的值。例如，状态相关字段的DV将明显比校验字段、序号字段和随机字段的DV小很多，但状态相关字段的DV也不会为0，因为DV值为0时表示该字段是一个不变字段，该字段是协议级特征字段而不是状态相关字段。通信流x中字段i的计算公式为，计算方法如图2所示。

图2 不同字段的DVFig.2 The DV value of different fields

对字段DV的统计分析缩小了状态相关字段的选取范围。为了最终确定状态相关字段，进一步使用多个通信流中字段取值的分布的分布作为字段的第二个统计特征量。由于同一协议的不同通信流通常具有相似的行为逻辑，所以状态相关字段的DDV将是除0以外的最小值(协议级特征字段的DDV将为0)。字段的DDV的计算公式为，计算方法如图 3 所示。

图3 不同字段的DDVFig.3 The DDV value of different fields

3.4 协议状态机重构

协议状态机的重构主要基于通信数据帧中状态相关字段的取值以及它们之间的顺序关系。数据帧中不同的状态相关字段反映了协议实体所在的不同状态，数据帧间的顺序关系反映了状态之间的转换关系。由于通信数据来自通信实体双方，构建协议状态机时将以其中一方作为主体(以另一方为主体则可构建出对应的协议状态机)，发送数据帧中的状态相关字段将反映出协议的状态变化，而接收数据帧中的状态相关字段将作为协议状态变化的辅助参考。在某些协议中，相同的状态相关字段在不同时期可能导致协议进入不同的状态，如TCP协议，发送SYN后发送ACK表示协议连接建立，而发送FIN后发送ACK表示协议连接关闭。虽然协议发送了同样的ACK，但却进入了不同状态。为解决这种情况，引入前因判断机制，即将发送数据帧与前期接收的数据帧一同考虑。该机制充分利用了通信协议的请求－响应设计，这样就能避免上述情况的发生。协议状态转移图的构建过程如下:

(1)针对一个通信过程，以start状态作为协议的开始状态;

(2)从通信数据中，顺序提取发送数据帧的状态相关字段，如果该字段首次出现，则创建一个新状态，记录下状态相关字段与状态的对应关系(包括接收的前驱状态相关字段)，并从当前状态转移到新状态;如果该字段已出现且前驱状态相关字段也相同，则从当前状态转移到与该状态相关字段对应的状态，否则创建一个新状态，记录下状态相关字段与状态的对应关系(包括接收的前驱状态相关字段)，并从当前状态转移到新状态;

(3)重复步骤2直到通信过程结束，协议最后进入end状态，该通信过程的协议状态转移图就构建完成;

(4)将不同通信过程的协议状态图进行合并、化简，生成完整的协议状态转移图。

4 实验与分析

为了验证协议状态重构系统的有效性，本文选举二进制协议地址解析协议(ARP)和传输控制协议(TCP)作为测试对象。

4.1 相应字段对齐

协议帧中某些字段的取值是经常变化的，这就可能造成在两个协议帧中不同字段取值相等的情况。采用简单替换矩阵的多序列比对算法为了迎合这种特殊情况，会在其他协议帧中插入大量的空隙，如图4所示，从而使得附近字段无法对齐。图5是采用改进替换矩阵的多序列比对结果，从图中能够看出，改进替换矩阵的多序列比对算法能够消除某些特殊协议帧序列对所有比对结果的影响，从而使协议帧中相应字段正确对齐。

图4 使用简单替换矩阵的多序列比对结果Fig.4 The alignment result of multiple sequences with simple substitution matrix

图5 使用改进替换矩阵的多序列比对结果Fig.5 The alignment result of multiple sequences with modified substitution matrix

4.2 状态相关字段识别

图6 显示了TCP协议帧字段DDV的对数分布情况。由于字段18和19的DDV值为0，为了能够计算出它们的对数值，实验中将字段18和19的DDV值设置成了0.1。从图6中可以看出字段14具有除0以外的最小DDV值。查阅TCP协议规范可知字段14是Flags字段，而与TCP协议状态转换相关的SYN、ACK和FIN等标志位都位于Flags字段中，所以识别Flags字段为TCP协议状态相关字段是合理的。

图6 TCP协议帧字段DDV分布图Fig.6 The distribution of DDV of different fields for TCP

图7 显示了ARP协议帧字段DDV的对数分布情况。为了能够计算出字段DDV值为0的对数值，实验中将字段DDV值为0的DDV值设置成了0.000 1。从图7中可以看出字段8具有除0以外的最小DDV值。查阅ARP协议规范可知字段8是操作码字段，操作码字段指示一个数据包是请求包还是应答包，而ARP协议帧中的其他字段都只是属性参数，因此操作码字段能够表现ARP协议的行为逻辑，选取操作码字段作为ARP协议状态相关字段是合理的。

图7 ARP协议帧字段DDV分布图Fig.7 The distribution of DDV of different fields for ARP

4.3 状态转移图重构

图8 给出了系统重构出的TCP协议状态转移图。状态图中转移条件r表示接收、s表示发送、后面的数字表示Flags字段取值的16进制表示。图中A部分是主动建立连接端的状态转移情况，参考TCP协议规范可知，该部分描述了主动建立连接端发送SYN、接收SYN－ACK、发送ACK从而建立起连接的过程。B部分是被动建立连接端的状态转移情况，它与A部分是相对应的。状态S3是数据传输状态。C部分是主动释放连接端的状态转移过程，该部分描述了主动释放连接端发送FIN－ACK、接收FIN－ACK、发送ACK从而释放连接的过程。D部分是与C部分相对应的被动释放连接端的状态转移过程。图中S3到end的转移表示协议发送了RST－ACK消息(Flags字段的16进制表示为14)。

图8 TCP协议状态转移图Fig.8 The state transition diagram of TCP

5 结束语

协议状态机是协议规范的一个重要部分，通过它能理解协议的行为逻辑。未知协议状态机逆构是协议逆向分析的重要技术之一。现有的研究成果仅针文本协议适用，无法解决二进制协议的状态机逆构问题。本文设计了一个根据通信数据逆构未知二进制协议状态转移图的系统。该状态转移图逆构系统采用了对应字段对齐技术、状态相关字段识别技术以及基于状态相关字段的协议状态机重构技术，适用于协议状态转移关系由状态相关字段取值变化驱动的通信协议。该方法具有一定的通用性和实用价值。为了验证该系统的有效性，选取了二进制协议TCP和ARP作为测试对象，测试结果表明该系统能够有效逆构出二进制通信协议的状态转移模型。通信数据中包含的协议信息毕竟有限，仅基于通信数据进行协议逆向分析能获取的协议信息也相对有限，而协议程序包含了完整的协议规范信息，未来将研究结合通信数据和协议程序的协议逆向分析技术，以便逆向出更多、更精确的协议信息。

[1]张钊，温巧燕，唐文.协议规范挖掘研究综述[J].计算机工程与应用，2013，49(9):1 －9.ZHANG Zhao，WEN Qiaoyan，TANG Wen.Survey of mining protocol specifications[J].Computer Engineering and Applications，2013，49(9):1 －9.(in Chinese)

[2]Cui W D，Kannan J，Wang H J.Discoverer:automatic protocol reverse engineering from network traces[C]//Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium.Berkeley，CA，USA:IEEE，2007:1－14.

[3]Caballero J，Yin H，Liang Z K，et al.Polyglot:automatic extraction of protocol message format using dynamic binary analysis[C]//Proceedings of the 14th ACM conference on Computer and communications security.Alexandria，VA:IEEE，2007:1 －5.

[4]罗琦.一种最大分类间隔SVDD的多文本分类算法[J].电讯技术，2014，54(4):496 －499.LUO Qi.A Mutli－class Text Categorization Algorithm Based on Maximal Classification Margin SVDD[J].Telecommunication Engineering，2014，54(4):496 －499.(in Chinese)

[5]Hsu Y，Shu G Q，Lee D.A model－based approach to security flaw detection of network protocol implementations[C]//Proceedings of the 15th IEEE International Conference on Network Protocols.Orlando，FL:IEEE，2008:114 －123.

[6]Xiao M M，Yu S Z，Wang Y.Automatic network protocol automaton extraction[C]//Proceedings of the 3rd Inter-national Conference on Network and System Security.Gold Coast，QLD:IEEE，2009:336 －343.

[7]肖明明，余顺争.基于文法推断的协议逆向工程[J].计算机研究与发展，2013，50(10):2044 －2058.XIAO Mingming，YU Shunzheng.Protocol Reverse Engineering Using Grammatical Inference[J].Journal of Computer Research and Dvelepment，2013，50(10):2044－2058.(in Chinese)

[8]黄笑言，陈性元，祝宁，等.基于状态标注的协议状态机逆向方法[J].计算机应用，2013，33(12):3486 －3489.HUANG Xiaoyan，CHEN Xingyuan，ZHU Ning，et al.Protocol state machine reverse method based on labeling state[J].Journal of Computer Applications，2013，33(12):3486 －3489.(in Chinese)

[9]Wang Y P，Zhang Z B，Yao D F，et al.Inferring Protocol State Machine from Network Traces:A Probabilistic Approach[C]//Proceedings of the 9th Applied Cryptography and Network Security International Conference.Nerja，Spain:IEEE，2011:1 －18.

[10]Trifilo A，Burschka S，Biersack E.Traffic to protocol reverse engineering[C]//Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Security and Defense Applications.Ottawa，ON:IEEE，2009:257 －264.

[11]Shevertalov M，Mancoridis S.A reverse engineering tool for extracting protocols of networked applications[C]//Proceedings of the 14th Working Conference on Reverse Engineering.Vancouver，BC:IEEE，2007:229 －238.