基于状态标注的协议状态机逆向方法黄笑言

摘要：协议状态机可以描述一个协议的行为，帮助理解协议的行为逻辑面向文本类协议，首先利用统计学方法提取表示报文类型的语义关键字；然后利用邻接矩阵描述报文类型之间的时序关系，基于时序关系进行协议状态标注，构建出协议的状态转换图实验表明，该方法可以正确地描述出报文类型的时序关系，抽象出准确的状态机模型

关键词：协议逆向； 协议语义； 协议会话； 协议状态机； 邻接矩阵

中图分类号： TP393 文献标志码：A

0引言

在网络安全中，很多基于协议的安全技术都以协议规范说明为基础比如为了提高防御粒度，新一代的防火墙[1]和入侵检测系统[2]利用协议规范进行深度包检测和状态行为检测，从而能高效、精确地识别出恶意传输；高交互型蜜罐系统[3]基于协议规范可以生成各种脚本以监听各种远程请求，实现多种服务的仿真

但是很多网络私有协议没有公开自己的规范说明，比如MicroSoft的网络文件共享SMB（Server Message Block）协议[4]、Oracle数据库访问的TNS协议[5]、各种IPTV和及时通信软件使用的协议[6]等另外，即使对于公开规范的协议，不同厂商在软件的具体实现时并没有严格按照规范说明去设计，因此越来越多的研究人员通过协议逆向的方法自动获取协议规范说明，以支撑其他网络安全技术的实施

协议规范定义了协议报文的格式和协议状态机[7]：前者规范了协议报文由哪些字段组成，每个字段的位置、类型和取值含义等[8]；后者规定了协议报文的时序关系，体现出协议的行为逻辑目前大多研究集中于反向推断协议的格式，较少研究协议状态机的逆向事实上，逆向出协议状态机可以描述一个协议的行为，帮助理解协议的行为逻辑，进一步应用到入侵检测或蜜罐系统中，因此本文对协议状态机逆向方法进行研究

1相关研究

目前关于协议状态机逆向的研究分为两类[9]一类是指令级的分析方法这种方法需要在指令级监控协议实体对报文的解析过程，实现起来比较复杂，在实际应用中很难获得对协议实体的控制权，加之很多软件为了防止其代码被逆向，加强了软件的模糊性另一类网流级的分析方法是以嗅探得到的网络数据流为分析对象，它的可行性在于同一报文格式对应的多个报文样本具有相似性，会话内报文的时序关系体现了协议状态转换的信息由于实现起来简单，因此近年来很多研究者开始研究基于网流级的状态机逆向方法

2007年，Shevertalov等[10]提出协议状态机逆向的工具PEXT，将协议的运行过程划分为多个阶段（子会话），每个子会话完成不同的功能，被定义成一个状态PEXT以最长公共子序列长度为相似度指标，对报文样本进行聚类，将协议流转化成一系列的聚类ID，在协议流之间提取相同的聚类ID序列标注成一个协议的状态，根据状态转换序列生成状态机，通过合并算法得到涵盖所有协议会话实例的最小确定状态机

2009年，Trifilo等[11]将会话中的每条报文（包括不同的方向）定义为一个状态，认为协议报文中通常存在一些报文状态域标志了当前的状态逻辑，通过分析二进制协议报文中各字节的变化分布来识别状态域并构建状态机；并考虑通过检测状态的前一状态和随后的状态来区分由同一特征值表示的不等状态，避免构建出的状态机产生错误的报文序列

2011年，Wang等[12]提出了协议的概率状态机（Probabilistic Protocol State Machine，PPSM）模型构建单方向网流的状态机PPSM首先利用统计学的方法找到网流中最频繁的字符串；而后利用围绕中心点的划分（Partitioning Around Medoids，PAM）聚类方法获取协议的状态关键字，根据关键字为每一个数据包分配状态类型；最后以概率的形式描述状态之间的转换，构建概率协议状态机

2009年，Comparetti等[13]综合利用网流级和指令级的信息提出了完整的协议逆向方案Prospex，为客户端的输出报文逆向状态机，旨在识别表示相似应用情景的状态首先利用指令执行序列分析技术，抽取每个报文的格式，继而结合格式特征和执行特征对报文进行聚类，抽取更普遍的报文格式，识别会话中的每个报文类型；然后构建增广前缀树（Augmented Prefix Tree Acceptor，APTA）接受网络会话中的所有报文类型序列，继而从观察到的会话中抽取报文类型之间的顺序特征，以正则表达式表示，称为先决条件；接着对APTA的每个状态用那个状态允许输入的报文类型集合进行标注，表示其符合先决条件的可接受的报文类型集；最后使用Exbar算法将APTA最小化

以上依据网流级状态机逆向的方法有以下不足：Trifilo等[11]的方法依赖于各种报文类型字段在报文格式的同字节偏移位置上出现，不适于报文类型字段的字节位置不固定的文本协议；Wang等[12]的方法适于文本协议，但是只依据频繁字符串标识报文状态，没有区分字符串之间的层次，无法准确提取出报文的语义字段

另外，目前构建状态机的方法都是先构建一棵状态前缀树，再利用启发式方法进行状态机的合并和简化，这会导致初始构建的状态机过于庞大，并且在状态机简化过程中容易导致路径的错误合并，无法准确地描述报文类型之间的时序关系

为解决以上问题，本文依据网络流的分析提出一种面向文本类协议的状态机逆向方法首先利用语义关键字的分布特征和偏移属性提取语义关键字，识别出会话中的报文类型；然后利用有向图的邻接矩阵描述报文类型之间的时序关系，进行状态标注；最后实现协议状态机的逆向，体现协议行为逻辑其流程如图1所示

2状态机逆向方法

2.1语义关键字提取方法

定义1语义关键字报文中表示报文类型的字段称为语义关键字

为了识别文本语义关键字，第一步使用处理文本协议的通用方法，将连续可打印ASCII码（不少于3字节）标记成一个文本块，根据分隔符将文本块划分为一系列的文本token；然后利用启发式规则过滤掉特征明显的参数，包括IP地址、版本号、URL等[14]，过滤后的文本token作为候选语义关键字，并记录它在原文本token序列中的位置第二步通过考察关键字在会话集中的分布特征，来识别常用语义关键字第三步发现关键字在报文中的偏移特征，一方面作为第二步语义关键字识别规则的补充，另一方面提高报文类型的识别速度

2.1.1语义关键字的会话分布特征

语义关键字的分布特征指的是语义关键字通常频繁地出现在会话中，而不是出现在会话的每个报文中本文综合关键字在会话中的频数和报文的频数来刻画语义关键字的分布特征，定义两个识别规则，同时满足两种识别规则的文本token即为语义关键字

2.1.2语义关键字的报文偏移特征

上述识别规则容易忽略很少出现在网流中的语义关键字，由于文本协议有一定的格式规范，语义关键字往往出现在报文的固定位置上，因此本文进一步发现语义关键字的偏移属性，并基于偏移属性对2.1.1节的识别规则进行修正

本文通过发现语义关键字的报文偏移特征，一方面对2.1.1节的识别规则进行修正，补充进出现频率较少的语义关键字；另外，基于语义关键字的偏移特征可以进行语义关键字的迅速定位，实现报文类型的快速识别，将协议的每个会话转化成报文类型序列

2.2状态标注

定义3协议状态是协议的一个逻辑概念，特定状态下协议实体可以接受特定事件和执行相应动作

由于服务器发送的报文多是一些表示服务器服务能力的命令码，无法反映协议的行为逻辑，因此本文同先前的工作一样，从客户端发送的报文类型序列中构建状态机

不同的报文类型可能会引起状态的转换，因此通常利用状态转换图表现报文类型之间的时序关系，描述协议的行为逻辑先前的文献首先构建状态前缀树，接受所有的报文类型序列再进行状态的合并和化简，导致初始构建的状态前缀树过于庞大，且需要大量的比较操作而本文利用邻接矩阵描述报文类型之间的关系，基于报文类型之间的关系对状态进行标注，可以省去状态前缀树的构造，直接构建状态转换图

主要思路是首先将具有强顺序约束的报文类型序列标注为一个状态，然后找到会话的必经报文类型序列，每个必经报文类型序列标注为一个状态，最后基于报文类型之间的弱顺序约束对两两必经报文类型中间的可选报文类型集进行状态标注

2.2.1构造邻接矩阵

2.2.3基于会话必经路径的状态标注

定义6会话必经路径是指所有会话必须出现的报文类型序列，这些报文类型之间有严格的顺序关系

本文首先引入形式概念的表示方法表示报文类型与会话的隶属关系，然后利用这种隶属关系和有向图的最短路径设计会话必经路径搜索算法，找到会话开始和结束之间的必经路径，将必经路径中的每个报文类型标识成一个状态转换

2.3状态转换图的构建

利用2.2节的状态标注方法对报文类型引起的状态转换进行状态标注，构造协议的状态转换图首先将具有强顺序约束关系的报文类型序列定义为一个状态转换；然后依据2.2.3节得到会话必经报文类型画出基本的状态转换图；最后依据2.2.4节方法将具有等价关系的报文类型定义成一个状态转换，构造出完成的状态转换图

3实验验证分析

本文在Windows XP环境下利用Python2.7编写代码实现状态机逆向的方法，为了对本文的方法进行验证，选取广泛应用于网络中的两种文本类协议SMTP和FTP进行状态机逆向通过在Windows XP下利用WebMail搭建SMTP服务器，利用ServU搭建FTP服务器，获取训练数据，然后将某校园网的真实网络流量作为测试数据

由于基于网络轨迹的协议逆向一个普遍存在的缺陷是无法学习到训练集中未出现的行为，因此本文要求训练集覆盖每个协议的主要功能，使得逆向出的状态机能够反映协议的主要行为逻辑

3.1关键字提取

3.2状态机逆向

本文利用在入侵检测和信息检索中广泛使用的两个评估指标——召回率和准确率对逆向的状态机的质量进行评估

3.2.1召回率

为了测试召回率，本文利用真实网络流量，对状态机的召回率进行评估真实网络流量的SMTP会话数为855，FTP会话数为642

图2为利用不同大小的SMTP协议训练集训练出的状态机的召回率实验结果表明训练集的SMTP报文个数达到300时，召回率稳定在94.1%，即逆向出的SMTP状态机可以接受803个FTP会话，余下的52个会话使用了SSL加密传输，没有被状态机识别出来图3为SMTP训练集的报文个数达到200时逆向出的状态机，由于SMTP第一条报文有两种报文类型，HELO和EHLO，图3显示的是第一种报文类型开头的状态机

图4为利用不同大小的FTP协议训练集训练出的状态机的召回率实验结果表明训练集的FTP报文个数达到2000条时，召回率稳定在91.7%，即逆向出的FTP状态机可以接受589个FTP会话，在余下的53个会话中，有12个会话出现了训练集中未出现的命令，另外41个会话使用了SSL加密传输图5为FTP训练集的报文个数达到1500条时逆向出的FTP状态机

3.2.2准确率

状态机的准确率用来衡量状态机的可靠性，表示被状态机接受的会话中，有多少个会话是符合协议规范的，令M表示被状态机接受的会话数，CP表示符合协议规范的会话数，则

为了测试准确率，本文对测试集中的会话以0.1的概率进行随机修改，创建不符合协议规范的会话，包括关键报文丢失和报文之间的乱序通过这种方式，在己经被SMTP协议状态机接受的786个SMTP协议会话中，创建无效会话78个在已经被FTP协议状态机接受的489个FTP协议会话中，创建无效会话64个

对于修改后的会话集，SMTP状态机接受SMTP会话为708个，未被接受的会话均是无效会话；而FTP状态机接受FTP会话为473个经检查发现，由于程序对FTP会话进行随机修改，而FTP规范中的很多报文类型是不需要严格顺序的，随机修改后的会话很多仍然是符合协议规范的，经人工过滤掉这些有效会话后，其状态机的准确率达到了100%

4结语

现有逆向协议状态机的方法需要根据协议会话中的报文类型顺序构建初始状态前缀树，这会出现大量的冗余状态本文利用邻接矩阵描述报文类型之间的时序关系，基于时序关系进行协议状态的标注，构建出协议的状态转换图，并对文本类协议进行了实验验证结果表明，该方法可以正确地描述出报文类型的时序关系，抽象出准确的协议状态机模型下一步，本文准备对二进制类的协议进行逆向实验，以验证本文方法的有效性

参考文献：

[1]KRUEGER T， KRMER N， RIECK K. ASAP： automatic semanticsaware analysis of network payloads [C]// Proceedings of the 2011 International ECML/PKDD Conference on Privacy and Security Issues in Data Mining and Machine Learning， LNCS 6549. Berlin： SpringerVerlag， 2011： 50-63.

[2]郝耀辉，郭渊博，刘伟.基于有限自动机的密码协议入侵检测方法[J].计算机应用研究，2008，25（1）：230-234.

[3]KRUEGER T， GASCON H， KRMER N， et al. Learning stateful models for network honeypots [C]// AISec 12： Proceedings of the 5th ACM Workshop on Security and Artificial Intelligence. New York： ACM， 2012： 37-48.

[4]How samba was written [EB/OL]. [2013-01-16]. http：///ftp/tridge/misc/french_cafe.txt.

[5]李伟明，张爱芳，刘建财，等.网络协议的自动化模糊测试漏洞挖掘方法[J].计算机学报，2011，34（2）：242 -255.

[6]ANTUNES J， NENVES N， VERSSIMO P. Reverse engineering of protocols from network traces [C]// Proceedings of the 18th Working Conference on Reverse Engineering. Piscataway： IEEE， 2011：169-178.

[7]田园，李建斌，张振.一种逆向分析协议状态机模型的有效方法[J].计算机工程与应用，2011，47（19）：63-67.

[8]黎敏， 余顺争.抗噪的未知应用层协议报文格式最佳分段方法[J].软件学报，2013，24（3）：604-617.

[9]潘璠，吴礼发，杜有翔.协议逆向工程研究进展[J].计算机应用研究，2011，28（8）：2801-2806.

[10]SHEVERTALOV M， MANCORIDIS S. A reverse engineering tool for extracting protocols of networked applications [C]// WCRE 2007： Proceedings of the 14th Working Conference on Reverse Engineering. Piscataway： IEEE， 2007： 229-238.

[11]TRIFILIO A， BURSCHKA S， BIERSACK E. Traffic to protocol reverse engineering[C]// CISDA 2009： Proceedings of the 2009 IEEE Symposium on Computational Intelligence for Security and Defense Applications. Piscataway： IEEE， 2009： 1-8.

[12]WANG Y P， ZHANG Z B， YAO D F， et al. Inferring protocol state machine from network traces： a probabilistic approach [C]// ACNS 11： Proceedings of the 2011 Applied Cryptography and Network Security， LNCS 6715. Berlin： SpringerVerlag， 2011： 1-18.

[13]COMPARETTI P M， WONDRACEK G， KRUEGEL C， et al. Prospex： protocol specification extraction[C]// Proceedings of the 30th IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2009： 110-125.

[14]赵咏，姚秋林，张志斌，等.TPCAD：一种文本类多协议特征自动发现方法[J].通信学报，2009，32（S1）：28-35.