(1982-), 男, 在站博士后, 主要研究领域为网络测量, 网络性能分析与建模, 网络安全
(1973-), 男, 博士, 教授, 博士生导师, CCF高级会员, 主要研究领域为网络安全, 网络测量与行为学, 未来网络安全
(1980-), 男, 博士, 主要研究领域为分布式存储, 大数据分析, 人工智能
(1991-), 男, 硕士, 主要研究领域为网络安全
(1989-), 男, 博士, 国家互联网应急中心工程师, 主要研究领域为工控系统网络安全, 关键基础设施安全防护
(1984-), 男, 博士, 讲师, 主要研究领域为网络测量, SDN, 网络空间安全
CHENG Guang, E-mail:
协议逆向广泛应用于入侵检测系统、深度包检测、模糊测试、僵尸网络检测等领域. 首先给出了协议逆向工程的形式化定义和基本原理, 然后针对网络运行轨迹的协议逆向方法和工具从协议格式提取和协议状态机推断两个方面对现有的协议逆向方法进行了详细分析, 阐释其基本模块、主要原理和特点, 最后从多个角度对现有算法进行了比较, 对基于网络流量的协议逆向技术的发展趋势进行了展望和分析.
Protocol reverse engineering is widely used in intrusion detection system, deep packet inspection, fuzzy testing, C & C malware detection, and other fields. First, the formal definition and basic principle of protocol reverse engineering are given. Then, the existing protocol reverse methods based on network trace are analyzed in detail from two aspects of protocol format extraction and protocol state machine inference. In addition, the basic modules, main principles, and characteristics of these algorithms are explained. Finally, the existing algorithms are compared from several aspects, and the development trend of protocol reverse technology is discussed.
协议是两个或多个协议实体间完成通信所遵循的规则集合, 其包含3个基本要素: 语法(syntax)、语义(semantics)、时序逻辑(temporal logic)[
协议逆向最早出现在1950年, 在1990年后伴随着软件和网络技术的快速发展, 由于网络安全管理、模糊测试等方面的巨大需求, 该技术得到了快速发展[
协议逆向的方法很多, 按分析对象可以划分为文本协议逆向分析与二进制协议逆向分析, 按协议组成要素可以划分为消息格式逆向分析和协议状态机逆向分析, 按分析方法可以划分为消息序列分析方法和指令序列分析方法等. 在所有的协议逆向方法中, 基于指令序列的分析方法需要得到协议实体, 而基于网络流量的分析方法仅需要得到协议交互实体间的网络流量. 本文仅针对基于网络流量的协议逆向方法进行分析, 由于各类算法或工具的侧重点不同, 本文将所有的算法或工具按照协议逆向的两个阶段进行划分, 然后加以论述. 实际上, 许多面向协议格式的算法需要状态机的信息, 反之状态机的推断也需要协议语法信息, 抑或在推断中迭代使用协议语法信息与状态机信息. 有些算法同时解决了上述两个问题, 如Biprominer[
本文第2节对协议逆向技术框架进行论述; 第3节对协议格式分析技术的算法和工具进行分析; 第4节论述协议状态机推断方法和工具; 第5节对所有算法进行综合对比, 并指出未来研究方向; 第6节总结全文.
协议逆向目标就是获得正确、简洁的协议规范. 协议自动逆向技术的实现可以显著减少人工分析的工作量, 提高对私有协议的分析效率, 并使对网络安全事件的快速自动响应成为可能. 由于协议实体的内部机制不可知, 其协议规范只能通过实体间交互的一系列报文来进行推断, 首先需要会话的划分和报文组装, 然后分析报文格式与推断字段语义, 不同协议状态的格式有可能相同, 在获取协议状态机时需要结合前置格式序列对状态进行合并, 最后在此基础上进行协议状态机的推断. 根据以上分析, 理想的协议逆向模型应当包括预处理、协议格式提取和状态机推断3个阶段, 如
协议逆向模型
在输入预处理阶段, 要对所有的分组进行过滤, 得到要处理的目标协议报文序列. 一般是通过五元组进行过滤的, 即源目的主机地址、双方端口以及协议, 实际上在协议逆向中不考虑采用上述相同信息的不同协议报文. 之后, 就是将所有的分组构建为不同会话, 一般常用的方法是时间阈值法, 如ReverX[
协议格式提取阶段以分组序列为输入, 经过域划分、结构识别和语义属性推断3个步骤, 从而生成协议格式推断报告. 实际上, 多数研究集中在前两个阶段, 特别是第一个阶段, 字段划分最初采用的算法是序列对比、多序列对比[
在状态机推断阶段, 经过状态标注构建部分状态机, 最后经过消除状态冗余和优化化步骤获取对应的最小确定状态机. 状态机的推断既可以通过推断协议字段, 也可不借助于字段信息. 实际上, 由于无法获得完整的协议报文序列, 状态机的化简是个难点, 一般通过一些启发性规则来完成的, 如PEXT[
目前, 关于协议逆向的研究多达20多种算法和工具, 这些工具或算法有的既包含了报文格式和状态机推断, 有的仅是侧重于某个部分, 为了给协议逆向研究人员提供一个较为清晰的研究路线, 将所有的算法从两个角度进行研究, 即协议格式提取技术和状态机推断技术.
协议格式提取主要完成协议字段划分以及字段语义推断. 字段划分又进一步可以分为字段提取以及字段关系推断或协议格式分析, 某些算法还包括格式优化过程. 协议字段的语义推断是一个难点, 往往需要背景知识的支撑, 相关研究较少. 在本节, 针对典型算法PIP、Discoverer、Biprominer、ProDecoder、ProGraph、AutoReEngine、HsMM (hidden semi-Markov modelling)等22种典型的算法进行分析, 为了理清研究思路和脉络, 按照算法的原理将这些算法分为4类, 即基于序列比对的格式推断算法、基于概率模型的格式推断算法、基于频繁集的格式提取算法和基于语义的格式推断算法.
PI是最早成功APRE工具之一[
PI将TCPDump文件作为输入, 在分组中区分长度不变的关键字和可变长度的字段, 并以Byte作为分析对象. 分析结果说明每个字段的变化率, 0变异率表示一个常量, 100%变异率表示高度可变的变量. 该方法使用一种典型的动态规划方法Needleman-Wunsch[
在计算不同分组之间的相似度时, 采用了无权分对分组算术平均方法(unweighted pair group method using arithmetic averages, UPGMAA), 来计算不同类型之间的距离.
其中,
PI将序列比对引入到协议逆向分析中来, 许多算法都是基于该算法进行改进的, 对该工具的全面理解, 有利于研究人员对该领域其他算法的快速认识. 其3个主要的不足[
Discoverer[
Discoverer算法主要思想
由于协议往往无法简单的认为文本或者二进制字节构成, Discoverer可以同时处理文本和二进制协议, 首先对接收到的协议字节流进行扫描, 通过与ASCII码表中所有可打印的字符进行对比, 从而将其标记为二进制或字符串; 为了避免将二进制数据误判为文本字段, 设置了字符串最小长度的阈值, 扫描后的数据构成了文本和二进制字符的序列. 字节序列比对采用的是Needleman-Wunsch算法[
在递归聚类阶段, 主要依据的是格式区别标识(format distinguisher tokens, FD tokens). 为了确定FD标识, 需要进行格式推断和格式对比. 格式从输入的消息集合推断出能够表示消息的标识, 实际上就是一组标识的语义及属性. 之所以采用标识语义, 是由于无法推断每个标识的语义而某些属性也可以表示消息格式. 标识的属性包括两种, 文本或二进制与者常量或变量. 作者将标识的类型定义为语义与属性的集合. 由于标识类别已经在标识识别阶段已经确定, 是否为常量与变量通过比较同类消息部分的值是否变化来区分. 采用RolePlayer[
在第3个阶段, 对于标识化和递归聚类阶段导致的过度分类问题, 寻找格式上相似的进行合并. 为此采用一种基于类型的序列比对, 在此对比阶段每一个类消息的各个表示只能具有相同的格式, 两者语义相同或具有相同的值. 为了避免在标识过程中引入的误差, 引入了“gap”来实现二进制与文本的对齐, 同时引入了限制规则防止过多的加入“gap”.
该算法是较早一个比较完备的处理算法, 从原理看是PI算法改进, 不仅包括报文格式分析还包括字段语义分析, 为完整的协议格式提取算法和工具提供了参考依据. 然而, 该算法仍然无法避免多序列比对的缺陷, 即比对开销和格式进行分组所引入的误差.
Bossert等[
在序列对齐时, 将half-Byte作为比较的单位, 对每个要素进行语义标注. 论文的难点在于如何挖掘语义信息, 论文提出了在消息中采用不同的编码格式, 如高字节序、低字节序、ASCII码或UTF-16, 进行搜索发现主机地址、时间戳或用户名等. 每个要素可以具有多个语义标签, 两个要素比较时不时简单的判定字符串是否相同, 而是语义标签是否完全相同, 或者最为包含与包含于的等关系. 在消息聚类阶段, 不仅考虑NW算法就算得到的相似度矩阵, 还考虑了元素在消息中的所占的比例. 在得到消息的格式后, 作者采用最大互信息系数(maximal information coefficient, MIC)来分析字段间的关系, 考虑到校验字段的非线性关系, 同时计算了皮尔逊相关系数r (Pearson correlation coefficient). 文献[
作者将这一算法在开源项目Netzo[
杜有翔等人[
为了解决上述问题, 潘璠等人[
孟凡治等人[
Esoul等人[
Razo等人[
Wang等人先后提出了Biprominer[
Biprominer 算法推断示意图
Biprominer算法仅适用于二进制协议, Wang等人进行了扩展和改进, 提出了ProDecoder, 其不仅支持二进制协议还支持文本协议. 算法分为4部分, 其中前两个步骤与Biprominer算法一致, ProDecoder不再采用转移概率矩阵, 将关键字和转移概率作为特征, 在此基础上引入信息瓶颈(information bottleneck, IB)作为距离测度进行层次聚类. 采用信息瓶颈作为测度的优点在于: (1)在计算复杂度与精度之间有个较好的平衡; (2)不用预先计算各个类之间的相似度. 在进行聚类后, 将所有的信息采用NW (Needleman-Wunsch)算法进行序列比对从而推断出报文的格式.
该算法将概率统计和数据挖掘的思想引入到协议字段的识别和划分过程中来, 为协议格式字段分析带来了新的思路, 许多后续的算法都是以Biprominer[
该算法是第一个同时可以针对bit和Byte两个不同级别进行格式推断的工具[
该算法采用一种自底向上的方法, 将协议分组构建为一棵树, 节点为协议字段, 边表示不同字段的依赖性, 最初所有的叶子节点和边都为空, 通过学习得出每个字段的合法取值范围, 并计算每两个叶子节点的互信信息熵是否超过一定的阈值从而决定是否为两个节点添加边. 然后对所有的字段进行合并, 合并的依据是: (1)两个字段之间具有高度的相关性; (2)两者在分组中的位置相近; (3)两个字段都与具有相同的邻居节点, 满足前两个条件. 合并后, 对整个树进行更新, 重新计算字段间的相关性, 依次迭代直到停止更新. 在计算过程中, 阈值通过MDL算法进行自动设定, 字段之间的相关性通过有向边表示, 一般由取值较少的字段指向取值较多的字段.
DNS协议字段的合并过程
该算法可以处理bit和Byte级的细粒度的协议, 同时也带来了较大的计算量, 可以在改进算法中考虑协议的规范以及协议的特征, 从而减少搜索空间以提高协议分析的效率.
在文献[
其中,
协议分析的HsMM模型
该算法通过tshark[
HsMM算法主要思想
隐马尔可夫已经广泛应用于文本分词, 其与协议逆向中的格式分析由许多相似之处, 在协议格式推断方面具有一定的创新性, 论文主要关注的是协议格式和消息分类的推断, 在字段语义和状态机方面研究较少.
Krueger 等人[
AutoReEngine算法[
而报文则是由一个个字符域构成的:
一个会话则定义为通信双方所有交换信息的集合:
两个站点间的通信则定义为若干会话的集合:
多数的协议逆向工具是从从左到右来识别协议的格式, 然后有些协议是从协议的右侧开始定义的. AutoReEngine算法的贡献在于两点: 提出了一种基于字符串频率的关键字提取方法; 在确定字符串的长度时分别从消息和行的头部、尾部分别进行定位.
AutoReEngine算法识别关键字基于这个直觉一个常见的模式的字串也是高频的. 算法分为4个部分, 首先将每个Byte视为一个关键字, 第2步计算每个字符串的频率是否超过一定的阈值, 如果超过就将其加入到频繁集中; 第3步增加一个Byte重新统计其是否超过一定的阈值, 对存在交叠的关键字进行合并, 计算其频率从而判定其是否为关键字. 最后一步当上述迭代停止, 直到频繁集中字符串都是完全字符串(closed string)时, 则为关键字集合.
为了确定关键字的准确位置, 该算法分别计算每个关键字到消息开始、结束的位置, 以及其到行首与行尾的位置, 将其表示为一个向量, 然后分别计算每个元素位置的方差, 从而确定关键字的准确位置. 通过比较关键字其实位置方差的变化来确定关键字, 关键字的结尾往往通过检测回车位置变化来确定. 采用AutoReEngine算法与Discoverer 算法, 对HTTP, POP3, SMTP, FTP, DNS和NetBIOS等协议进行了对比, 由于其能够识别关键字的起始位置, 因此具有更高的准确性. 该算法同时采用了Apriori算法来进行状态机的推断和构建.
Wang等人[
AC-FP算法主要思想
首先, 数据捕获阶段获取无线信号过滤掉噪音将其转换为比特流. 然后, 采用信号的前导码进行帧边界的确定, 由于802.11x采用的是伪随机序列, 因此采用多模式进行匹配, 采用最长的重用序列, forcanset = {cset1, cset2,…,cset
基于类似的想法, Hei等人[
Fan等人[
SPREA算法主要架构
在SPREA中所有的关键字分为两类即位置固定的关键字, 和位置不固定的关键. 在初始阶段, 对个每个Byte的数据进行统计, 计算其支持度, 当其支持度大于min_sup=0.6时, 则认为其可以独立的成为一个关键字. 当两个邻近的字符串具有重叠部分时, 进行合并, 字符的最小长度min_len的阈值设置为2. 对于识别为关键字的字节, 通过一个5元组进行标识(标识名, 频率, 偏移量, 重叠数, 父节点), 构建树时采用了FP-tree, 不同的是不按照支持度对所有的元素进行重排列, 从而保持元素前后之间的关系不变. 在协议推断时, 采用了改进的PrefixSpan算法[
在加密字段识别时, 首先计算所有字节的信息熵, 然后通过最大似然估计就算分组中
Goo等人[
在语法推断阶段, 作者将所有的字段分为4类: SF(v)、DF(v)、DF和GAP. SF(v)表示静态有固定长度的字段; DF(v)表示动态具有固定长度的字段. DF和GAP表示随机性很强, 无法预测其取值范围的字段, 两者的区别在于DF字段的长度是变化在一定的范围内, 而GAP字段的长度则无法预测. 因此, 在分析过程中, SF(v)、DF(v)、DF等3类字段的最小、最大和平均长度会进行存储. 在进行语法分析时, 采用了一种自底向上的分析方法, 算法分为4个步骤, 首先是SF(v)类字段的提取, 然后是DF(v)类字段的提取, 然后消息格式的和额外格式的提取. 在提取SF(v)字段时采用Apriori算法, 输入的字段的长度从一个bit到一个Byte. 此阶段提取的结果, 将作为DF(v)字段的输入, 算法同样采取Apriori算法计算字符间的频繁集, 其包含3个特征位置变化不大, 支持度不为1 (表示值是变化的), 字段的长度变化不大. 在此基础上, 再次使用Apiori算法, 从而得到根据字段间长度的方差, 以及最大最小值之间的差异来判定其为DF或GAP类型, 从而将分组中4中类型的字段都识别出来.
在字段的语义推断过程, 算法采用了FieldHunter[
IPART算法[
在字段推断部分, 首先通过n-gram算法选择出高频的字段, 然后采用全局投票算法(global voting expert algorithm, GVE),判定将相邻的字段进行合并. 在字段识别时, 设计了4种不同的字段识别算法, 包括常量、长度字段、序列号和功能码. 论文在功能码识别时考虑了字段取值、偏移量等因素, 从而计算每个字段的得分, 将得分高的定为功能码. 最后, 算法根据数据传输的方向和功能码进行分类, 将同一种类型的分组格式进行合并, 从而推断协议的分组格式.
FieldHunter[
FieldHunter系统架构
字段分隔符的确定: 一般字段分割符的特征包括3点: (1)一般为的不是字符1或者2两个符号, 如“#”“&”等; (2)分隔符在文本协议中相对于其他非字符符号出现的频率高; (3)一个协议一般只有一个字段分隔符. 基于上述发现, 通过统计非字母的符号频率获得出现频率最高的符号即为该协议的字段分隔符.
键值对分隔符的确定. 算法分为3个步骤: (1)通过最长前缀法提取对分组进行分类; (2)对分类结果重新进行聚类, 避免具有少数共同关键字引起的误差, 如Port: 与Point: 具有两个“Po”相同的字符; (3)在关键字中将共同非字符符号后缀提出来作为分隔符.
在确定了字段后, 字段类型推理工具负责确定每个字段的语义, 文献[
Choi等人针对基于IEEE 802.15.4的无线协议提出了WASp (WPAN automatic spoofer)[
WASp算法主要思想
上一节讲述了如何推断协议的语法, 而本节则关注于协议状态机推断的相关算法和工具分析. 实际上, 前者是对一个消息内部的数据进行聚类, 而后者则是对不同消息本身进行聚类. 协议状态机的重构主要基于通信数据帧中状态相关字段的取值以及它们之间的顺序关系. 数据帧中不同的状态相关字段反映了协议实体所在的不同状态,数据帧间的顺序关系反映了状态之间的转换关系. 因此, FSM工具的处理对象往往是两个通信实体间包含不同消息队列的会话集合. 一般此类工具包含4个步骤, 首先从网络通信数据中提取两个主机的通信数据包, 然后将这些信息进行聚类获得一个有限的类型集合称为状态, 第3步将观测到的不同聚类间的状态转移定义为它们之间的边, 第4步对边和状态进行简化.
协议状态机推断的一般示例
本节将所有的状态机推断算法分为两类: 被动式协议状态机推断算法和主动状态机推断算法, 然后逐一进行分析.
PETX (protocol extraction)[
ReverX是Joao等人[
Trifilo 在PEXT 的基础上, 提出了基于二进制特征选择(binary features selector, BFS)状态机推断方法[
Antunes等人[
Veritas[
在包分析阶段通过K-S (Kolmogorov-Smirnov) 检测来发现高频的字节单元, 然后通过报文组装来实现报文格式推断, 其主要包括3个步骤: (1)从流量中随机选择一组报文; (2)将高频的信息字符串, 进行组合在这些报文中进行匹配; (3)所有匹配的字符串作为协议格式消息.
在协议状态推断阶段, 为了定义分组之间的相似性引入了相似性测度Jaccard index, 在分类过程中引入了PAM (partitioning around medoids)算法, 与k-means算法相比对噪声和异常数据更加鲁棒, 在类别参数的选择中采用了邓恩指数(Dunn index), 选择使得邓恩指数最大的
除此之外, 孟凡治等人[
关于状态机推断的最早起源于基于到达的消息进行自动的信息回复, 典型算法如ScriptGen[
Veritas系统主要模块
上述算法都是基于采集的网络流量进行协议状态机的推断, Laroche等人[
Zhang等人[
本文第3节系统梳理了协议逆向工程中关于格式分析的主要算法, 按照算法基本思想进行了分类, 并按照其演化过程对算法的主要思想进行了详述. 本节将对主要的算法从过个维度进行分析, 然后从不同的角度对现有的研究成果进行评述.
格式提取算法对比
序号 | 算法名称 | 时间 | 分析
|
协议类型 | 字段提取 | 格式推断 | 语义
|
状态机构造 | 测试协议 |
1 | PI[ |
2004 | Byte | Text | 多序列比对 | UPGMA | No | No | HTTP, ICMP |
2 | Biprominer[ |
2011 | Byte | Binary | 统计 | 转移概率模型 | No | Yes | Xunlei, QQLive, SopCast |
3 | ProDecoder[ |
2012 | Byte | Binary+Text | n-grams | Needleman-Wunsch | No | No | SMB, SMTP |
4 | RMSE[ |
2012 | Bit | Binary+Text | 序列比对 | 递归聚类 | Yes | No | FTP, DNS, Emule, SIP, SMB |
5 | AutoReEngine[ |
2013 | Byte | Binary+Text | 字母统计 | Apriori | No | Yes | HTTP, POP3, SMTP, FTP, DNS, NetBIOS |
6 | Discoverer[ |
2013 | Byte | Binary+Text | 多序列比对 | 递归聚类 | Yes | No | HTTP, RPC, SMB |
7 | AC-FP[ |
2013 | Hex | Binary | AC | FP-tree | No | No | ARP, ICMP |
8 | Semantic-PI[ |
2014 | Hex | Binary+Text | 多序列比对 | UPGMA | No | No | FTP, SMB, ZA, VoIP |
9 | ProGraph[ |
2015 | Bit, byte
|
Binary+Text | 统计频率 | 图论 | No | No | HTTP, DNS, BitTorrent |
10 | FieldHunter[ |
2016 | Byte | Binary+Text | 统计频率, n-gram | 启发式规则 | Yes | No | STUN, FTP, HTTP, POP3, SMTP, MSNP, RTSP |
11 | HsMM[ |
2016 | Byte | Binary+Text | 字母统计 | HMM | No | No | HTTP, SSDP, BitTorrent, QQ, DNS, NetBIOS |
12 | SoundComm-CISEG[ |
2016 | Byte | Binary | 序列比对 | UPGMAA | No | No | Blooteeth |
13 | WASp[ |
2016 | Byte | Binary | n-gram, Zero熵检验等 | 启发式规则 | Yes | No | IEEE 802.15.4 |
14 | Segment-Based NW[ |
2017 | Byte | Binary+Text | 序列比对 | UPGMA | No | No | HTTP, SIP, TFTP, SMB |
15 | IPFRA[ |
2018 | Bit | Binary+Text | 序列比对 | UPGMAA | No | No | HTTP, FTP |
16 | MSA-HMM[ |
2018 | Byte | Binary | 序列比对 | HMM | No | No | EthernetIP-ICMP |
17 | SPREA[ |
2018 | Byte | Binary | FP-tree | PrefixSpam | Yes | Yes | SSL, SSH, NS, SOF |
18 | HIERARCHICAL CSP[ |
2019 | Byte | Binary+Text | Apriori | Apriori | Yes | Yes | HTTP, DNS |
19 | CFI[ |
2019 | Bit | Binary+Text | AC | Apriori | No | No | - |
20 | IPART[ |
2019 | Bit | Binary | n-gram | GVE | Yes | Yes | Modbus, IEC104, Ethernet/IP |
从分析粒度来看, 多数算法分析粒度在Byte级别, 而少数算法在bit级别, 这主要是多数的研究是针对互联网协议设计的, 互联网协议的设计无论是应用层还是传输层都是以Byte作为单位的, 但是在物联网、工控协议中许多协议是bit作为基本单元的. 因此, 目前多数的算法在对于细粒度协议格式分析方面存在不足. 协议类型分析类型来看, 以文本协议、二进制和兼容二进制协议算法数目相差不大.
字段提取与格式推断是算法设计重点也是两个关键的阶段. 字段提取主要采要分为4类, 即多序列比对、频率统、n-grams和频繁集算法, 其中后3者从原理上都是通过统计备选的字段出现的频率来进行可能字段的挖掘, 与最初的多序列比多在原理上有着较大的区别. 在格式推断方面, 主要分为3类型, 层次聚类方法、频繁集挖掘、以及概率模型, 第1类方法本质上强调了个字段在编辑距离上的关系, 而后两类则是关心的统计意义上的相关性.
协议字段的语义推断是个难点, 在此方面FieldHunter、WASp[
第3节所关注的算法主要针对协议格式提取进行研究, 即便某些算法和系统具备状态机的推断能力, 也都是现有算法的应用. 从分析协议对象看, 主要是传统的应用层协议, 很少出现无线协议和物联网或工控协议.
状态机描述了协议实体间的动态交互行为, 既依赖于格式推断的效果, 同时又具有相对的独立性, 对协议格式的推断具验证作用. 协议状态机可以用于软件的交互测试, 从而发现漏洞或者更多的协议状态. 与协议格式提取算法相比, 协议状态机的研究较少.
(1)近年来在协议状态机推断方面的研究较少, 多数协议状态机推断算法同时支持二进制协议和文本协议, 且以被动方式为主, ScriptGen和RolePlayer两个工具并不算严格的协议逆向工具, 然而它们的研究思路是状态机推断算法的起点, 因此也进行了论述.
(2)在协议状态机提取方面, 目前采用的方法主要分为两类: 一类是按照消息的自然时序来提取协议部分状态机, 一类是通过聚类分析从而减少状态的数目避免状态膨胀. 只有一些综合性的算法如NetZob综合考虑了分组类型的划分.
(3)在协议状态机构造方面, 多数的状态机化简都是基于启发式规则来进行的, 采用的自动化简方法较少, 或是与分组类型的分类相结合的.
协议状态机推断算法对比
序号 | 算法名称 | 时间 | 协议类型 | 交互方式 | 状态提取 | 状态机构造 | 分析对象 |
1 | ScriptGen[ |
2005 | Binary+text | 主动 | 序列比对 | 时序构建 | HTTP, NetBIOS, SMB |
2 | RolePlayer[ |
2006 | Binary+text | 主动 | 时序构建 | - | SMTP, DNS, HTTP等 |
3 | PEXT[ |
2007 | Binary+text | 被动 | LCS聚类 | 启发式约减 | FTP |
4 | POA-Greedy[ |
2009 | Binary | 被动 | 序列比对 | 时序构建 | FTP |
5 | BFS[ |
2009 | Binary | 被动 | VDV | 时间窗口化简 | ARP, DHCP, TCP |
6 | Veritas[ |
2011 | Binary+text | 被动 | 频率统计 | PAM | SMTP,PPlive, Xunlei |
7 | ReverX[ |
2011 | Binary+text | 被动 | 分组划分 | 启发式约减 | FTP, SMTP, POP |
8 | NimsGP[ |
2013 | Binary | 被动 | 线性页面基因
|
时序构建 | FTP, DHCP |
9 | MQSM[ |
2012 | Binary+Text | 主动 | EDSM | 时序构建 | HTTP, ISAKMP, SNMP |
10 | NetZob[ |
2014 | Binary+ Text | 主动 | 序列比对 | 时序构建 | FTP, SMB, Zaccess等 |
通过对于协议逆向主要算法分析发现, 总体而言针对协议格式分析相对较多, 状态机的较少, 但是总体而言协议逆向仍属于初级阶段, 但是由于其在网络入侵检测系统、深度包检测、模糊测试、僵尸网络检测等方面具有广泛的应用前景, 未来依然是个研究的热点. 建议从以下几个方面进行开展研究:
(1)研究工控等物联网专有协议的特征, 设计更加有效的识别方法. 从格式提取算法演化过程看, 伴随着机器学习、人工智能技术的兴起, 大量自动学习算法被引入到协议分析中来, 而每种算法往往是针对特定的协议特征而设计的, 目前算法多是针对互联网协议而设计, 没有考虑物联网或工控协议, 协议简短、粒度细、无定界符的特征, 而这些协议数目在未知协议中比重较大, 因此需要考虑其特征对算法进行重新设计. 其次, 现有协议分析格式算法或系统中, 仅有少数考虑了一些协议设计的原理, 通过引入先验知识来解决识别中的冲突问题, 而完善协议分析的迭代过程, 可有效解决单纯依靠分类和数据挖掘算法不能解决的问题.
(2)提出系统的协议语义体系, 丰富协议字段的语义推断方法. 由于字段语义的推断, 需要应用背景的支撑, 而在分析中很难得到, 协议语义一直没有得到系统的研究. 文献[
(3)研究交互式增量协议逆向分析技术, 提高协议分析的完备性. 无论是协议格式提取还是协议状态机的构建都需要大量能够涵盖启动、运行、结束等全生命周期的报文, 然而基于网络流量的分析方法, 缺点就是无法获得完整的报文, 因此, 设计交互学习机制, 结合模糊测试技术采用主动的方法实现与分析对象报文交互, 从而提高协议逆向分析的完备性. 同时由于算法的效率较低, 无法对长周期、海量报文进行分析, 设计在线以及面向大量数据的高效分析方法也是未来研究方向之一.
(4)研究多种方法综合集成机制. 从现有的协议逆向各个阶段所采用的方法看, 无论基于序列比对还是数据挖掘的方法, 其或考虑了协议字段的前后关系或者统计关系, 均有一定的效果. 在未来研究应当将这两种技术进行结合或进行交互验证, 从而提高整体的推断率. 如Bossert等人[
伴随世界各国对网络空间安全日益重视, 对于网络流量监控、僵尸网络的识别、入侵流量过滤、恶意软件分析的需求变得更加迫切. 协议逆向技术有效可以实现对未知协议特征、格式以及交互行为的描述, 从而得到学术界和工业界的重视. 特别是伴随着5G网络技术和边缘计算的兴起, 物联网和工控协议以及新型应用必将大量涌现, 本文针对基于网络流量的分析技术进行了全面的分析, 对于协议逆向分析所涉及各个环节中的关键技术和演化过程进行了剖析, 指出了现有的研究不足与未来研究方向. 建议研究人员建立完善的分析理论, 充分考虑协议设计特点, 设计主被动的交互机制, 综合应用各种技术以提高协议逆向分析准确率和自动化程度.
doi: 10.7666/d.D01107920]]]>
doi: 10.7666/d.D01107920]]]>
Narayan J, Shukla SK, Clancy TC. A survey of automatic protocol reverse engineering tools. ACM Computing Surveys, 2016, 48(3): 1–26.doi: 10.1145/2840724
Lee D. Yannakakis M. Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE, 1996, 84(8): 1090–1123 doi: 10.1109/5.533956
http://www.samba.org/ftp/tridge/misc/french_cafe.txt]]>
http://www.winehq.org/about/]]>
doi: 10.1109/PDCAT.2011.25]]]>
https://netzob.org/]]>
Luo JZ, Yu SZ. Position-based automatic reverse engineering of network protocols. Journal of Network and Computer Applications, 2013, 36(3): 1070–1077.doi: 10.1016/j.jnca.2013.01.013
doi: 10.1109/WCRE.2011.28]]]>
doi: 10.1109/TrustCom.2013.21]]]>
doi: 10.1145/2939918.2939921]]]>
doi: 10.1109/ICNP.2012.6459963]]]>
doi: 10.1109/IFIPNetworking.2015.7145325]]]>
Cai J, Luo JZ, Lei FY. Analyzing network protocols of application layer using hidden semi-Markov model. Mathematical Problems in Engineering, 2016, 2016: 9161723.doi: 10.1155/2016/9161723
潘璠, 洪征, 杜有翔, 吴礼发. 基于递归聚类的报文结构提取方法. 四川大学学报(工程科学版), 2012, 44(6): 137–142.doi: 10.15961/j.jsuese.2012.06.016
Pan F, Hong Z, Du YX, Wu LF. Recursive clustering based method for message structure extraction. Journal of Sichuan University (Engineering Science Edition), 2012, 44(6): 137–142 (in Chinese with English abstract).doi: 10.15961/j.jsuese.2012.06.016
doi: 10.1109/IFIPNetworking.2015.7145307]]]>
Bermudez I, Tongaonkar A, Iliofotou M, Mellia M, Munafò M M. Towards automatic protocol field inference. Computer Communications, 2016, 84: 40–51.doi: 10.1016/j.comcom.2016.02.015
Goo YH, Shim KS, Lee MS, Kim MS. Protocol specification extraction based on contiguous sequential pattern algorithm. IEEE Access, 2019, 7: 36057–36074.doi: 10.1109/ACCESS.2019.2905353
doi: 10.1109/WCRE.2007.6]]]>
doi: 10.1109/CISDA.2009.5356565]]]>
http://www.phreakocious.net/PI/PI_Toorcon.pdf]]>
Needleman SB, Wunsch CD. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecular biology, 1970, 48(3): 443–453.doi: 10.1016/0022-2836(70)90057-4
doi: 10.1145/2590296.2590346]]]>
Reshef DN, Reshef YA, Finucane HK, Grossman SR, McVean G, Turnbaugh PJ, Lander ES, Mitzenmacher M, Sabeti PC. Detecting novel associations in large data sets. Science, 2011, 334(6062): 1518–1524.doi: 10.1126/science.1205438
杜有翔, 吴礼发, 潘璠, 洪征. 一种基于报文序列分析的半自动协议逆向方法. 计算机工程, 2012, 38(19): 277–280.doi: 10.3969/j.issn.1000-3428.2012.19.071
Du YX, Wu LF, Pan F, Hong Z. A semiautomatic protocol reverse method based on message sequence analysis. Computer Engineering, 2012, 38(19): 277–280 (in Chinese with English abstract).doi: 10.3969/j.issn.1000-3428.2012.19.071
doi: 10.1007/978-3-030-00015-8_28]]]>
doi: 10.1109/ICBDA.2018.8367724]]]>
doi: 10.1109/QRS.2017.49]]]>
doi: 10.1109/MALWARE.2016.7888724]]]>
doi: 10.1007/978-3-642-19896-0_5]]]>
http://www.wireshark.org]]>
Baum LE, Petrie T, Soules G, Weiss N. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. The Annals of Mathematical Statistics, 1970, 41(1): 164–171.doi: 10.1214/aoms/1177697196
Frey BJ, Dueck D. Clustering by passing messages between data points. Science, 2007, 315(5814): 972–976.doi: 10.1126/science.1136800
10.1109/MC.1984.1659158]]]>
Vyas K, Sherasiya S. Modified Apriori algorithm using hash based technique. International Journal of Advance Research and Innovative Ideas in Education, 2016, 2(3): 1229–1234.
doi: 10.1109/TrustCom/BigDataSE.2019.00094]]]>
doi: 10.1109/CompComm.2018.8780606]]]>
Han JW, Pei J, Yin YW. Mining frequent patterns without candidate generation. ACM SIGMOD Record, 2000, 29(2): 1–12.doi: 10.1145/335191.335372
doi: 10.1109/SP.2009.14]]]>
Pei J, Han JW, Mortazavi-Asl B, Wang JY, Pinto H, Chen QM, Dayal U, Hsu MC. Mining sequential patterns by pattern-growth: The PrefixSpan approach. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(11): 1424–1440.doi: 10.1109/TKDE.2004.77
Wang XW, Lv KZ, Li B. IPART: An automatic protocol reverse engineering tool based on global voting expert for industrial protocols. International Journal of Parallel, Emergent and Distributed Systems, 2020, 35(3): 376-395.doi: 10.1080/17445760.2019.1655740
https://www.di.fc.ul.pt/~nuno/PAPERS/INFORUM09.pdf]]>
doi: 10.1007/978-3-642-21554-4_1]]]>
doi: 10.1109/WARTIA.2014.6976411]]]>
doi: 10.1109/CSAC.2005.49]]]>
doi: 10.1109/CEC.2013.6557965]]]>
doi: 10.1109/ICDMA.2012.125]]]>
Dupont P, Lambeau B, Damas C, van Lamsweerde A. The QSM algorithm and its application to software behavior model induction. Applied Artificial Intelligence, 2008, 22(1–2): 77–115.doi: 10.1080/08839510701853200
doi: 10.23919/SOFTCOM.2018.8555813]]]>