1、2023 年 4 月 Chinese Journal of Network and Information Security April 2023 第 9 卷第 2 期 网络与信息安全学报 Vol.9 No.2 渐进式的协议状态机主动推断方法 潘雁，林伟，祝跃飞（信息工程大学，河南 郑州 450001）摘 要：主动协议状态机推断的理论基础为主动自动机学习，所面临的核心问题是字母表的抽象与映射器的构建。同一类型消息取值的多样性可能导致同一类型的数据包存在不同的响应类型，从而导致当前使用类型作为字母表的方法会丢失状态或状态转移。对此，依据不同的响应将协议类型细化为子类型，提出一种渐进式主动推断方法
2、。基于已有协议数据提取协议状态字段，构建初始字母表与映射器，基于主动推断方法得到初始状态机；对数据进行确定性变异，若输入输出类型序列与当前状态机不符，则将变异后数据视为协议子类型，并添加至字母表，同时依据新的字母表进行新的状态机推断。此外，为减少协议实际交互次数，依据协议特性，在主动推断算法的缓存机制基础上提出一种基于前缀匹配的预响应查询算法。实现了开源框架ProLearner，并以SMTP和RTSP为对象，通过扩展协议子类型获得了更为详细的协议行为，验证了所提方法的有效性；此外，实验结果表明预响应查询算法可有效减少实际交互的次数，平均降低的实际交互次数约为 10%。关键词：协议逆向分析；主动
3、自动机学习；协议状态机推断；Mealy 自动机；映射器 中图分类号：TP393 文献标志码：A DOI:10.11959/j.issn.2096109x.2023023 Progressive active inference method of protocol state machine PAN Yan,LIN Wei,ZHU Yuefei Information Engineering University,Zhengzhou 450001,China Abstract:Protocol state machine active inference is a technique that
4、 relies on active automata learning.However,the abstraction of the alphabet and the construction of the mapper present critical challenges.Due to the diversity of messages of the same type,the response types of the same type are different,causing the method of regarding the message types as the alph
5、abet will result in the loss of states or state transitions.To address the issue,message types were refined into subtypes according to the different responses and a progressive active inference method was proposed.The proposed method extracted the state fields from the existing protocol data to cons
6、truct the initial alphabet and the mapper,and obtained the initial state machine based on active automata learning.It then mutated the existing messages to explore the response sequences,which were inconsistent with the current state machine.The mutated message was regarded as a protocol subtype and
7、 added to the alphabet,and a new state machine was 收稿日期：20221027；修回日期：20230205 通信作者：潘雁， 基金项目：国家重点研发计划（2019QY1300）Foundation Item:The National Key R&D Program of China(2019QY1300)引用格式：潘雁,林伟,祝跃飞.渐进式的协议状态机主动推断方法J.网络与信息安全学报,2023,9(2):81-93.Citation Format:PAN Y,LIN W,ZHU Y F.Progressive active inference
8、 method of protocol state machineJ.Chinese Journalof Network and Information Security,2023,9(2):81-93.82 网络与信息安全学报 第 9 卷 inferred progressively based on the new alphabet.In order to reduce the interactions,a pre-response query algorithm was proposed based on prefix matching for the caching mechanism
9、 in the active automata learning.The ProLearner tool was utilized to evaluate the proposed method in the context of the SMTP and RSTP protocols.It is verified that the pre-response query method can effectively reduce the number of actual interactions,with an average reduction rate of about 10%.Keywo
10、rds:protocol reverse analysis,active automata learning,protocol state machine inference,Mealy automata,mapper 0 引言 网络协议规范是实现计算机网络中互相通信的对等实体之间交换信息时所必须遵守的规则集合，其定义了通信数据的格式以及协议实现处理数据包时的状态切换。协议格式规范分析，又被称为协议逆向工程，它通过对未知协议的通信数据或处理数据的协议实体进行分析，以获取协议的格式与行为。其通常分为 3 个层次：语法、语义及时序。语法指报文的格式及编码，语义指报文的具体含义（包括控制信息、错误处
11、理等），时序指报文之间的通信序列。协议状态机推断对应时序分析，通常是在报文格式、语义信息已知的前提下，根据协议实体接受和拒绝的报文序列，推断其处理报文序列过程中的状态迁移过程，通常采用有限状态机、概率状态机1、前缀树接受器2、马尔可夫模型3等描述状态转移。协议状态机推断根据学习的方式可分为被动推断与主动推断。被动推断是基于离线数据包提取代表报文的状态信息，并分析生成协议对应的处理逻辑；主动推断是将格式良好的数据包发送到服务器，基于查询响应的方式构建状态机，能在一定程度上克服被动学习仅具有正样本的缺点。主动推断的理论基础是主动自动机学习，但其广泛使用的 MAT（minimally adequat
12、e teach）框架4仅适用于输入字母表较小的系统，而现实世界的系统和软件的输入空间是巨大的，如协议实现的输入输出为协议消息。现有的方法通常是对协议消息进行分类，依据协议的已知格式将消息划分为不同的类型，即消息集合可以划分为多个互不相交的子集合，并将类型作为输入字母。在现有的文献中，协议逆向工程和协议状态机主动推断对消息类型均没有明确的定义，对协议进行基于类型的划分所依赖的假设为目标协议具有状态相关字段，即具有特定的字段标识协议类型；同一类型的协议消息具有相近的格式，且与其他类型的消息相似性较弱5。因此可基于关键词分析和相似性的方式对协议消息进行分类。例如，实时流协议（RTSP，real-ti
13、me streaming protocol）的关键词为 DESCRIBE，SETUP、PLAY、TEARDOWN 分别表示不同的协议类型。在实际情况下，同一类型消息取值的多样性（如不同参数的选择）可能导致同一类型的数据包存在不同的响应类型。以 RTSP 为例，SETUP 类型对应的消息所包含的参数不同会导致响应类型不同。因此，直接将类型作为字母表会导致状态或者状态转移丢失。针对上述问题，Cassel 等6提出了寄存器自动机，它是一种能够表达数据对控制流影响的自动机模型，每种状态有一个寄存器用以存储数值，可对下一次输入进行相等性比较，从而直接推断出一部分数据值对控制流的影响，其表达能力相较于 M
14、ealy 状态机有一定的提升，但参数的选定和模型的复杂程度都带来了更大的分析难度，且只能针对数值型的参数进行判断。Szkely 等7基于已有数据包提取子类型，子类型是指在每种状态下使服务器产生的响应类型相同的消息集合。文献7基于自动协议逆向工程对已有数据包进行分析并获得候选子类型，在初始模型的基础上依次添加候选子类型判断是否为子类型，若是则将其添加至模型中，否则进行类型的合并。被动学习同样面临该问题，Sun 等8提出一种基于概率的 Mealy 机描述协议行为，若同一种类型导致了不同类型的响应，则统计已有数据中不同类型的比例，通过概率描述不同的转移过程。综上，当前方法中的寄存器自动机仅针对数值型
15、的参数进行判断，且参数的选定和模型的复杂程度都带来更大的分析难度；Szkely 提出的方法中缺乏对已有数据包的详细分析，且缺少异常数第 2 期 潘雁等：渐进式的协议状态机主动推断方法 83 据的扩展。针对此问题，本文首先借鉴被动学习的预处理过程，将数据包转化为类型序列；而后基于类型相关字段对已有数据包进行分类提取；最后，细化并改进文献7的具体算法，逐步学习状态机。同时，由于正常通信采集的数据包消息格式都是标准格式，缺少异常数据，因此在主动学习的过程中添加变异模块，探索更多的异常子类型。本文的主要贡献如下：1)针对协议状态机推断存在的字母类型与消息一对多的对应关系，基于已有的数据包进行变异，提出
16、了一种主被动结合的渐进式协议状态机推断方法；2)基于协议特点，改进协议主动推断中的缓存机制，提出一种基于前缀的预响应查询算法；3)以 RTSP、简单邮件传送协议（SMTP，simple mail transfer protocol）为对象，成功实践了所提方法的技术思路，验证了该方法的有效性。1 相关工作 本文所涉及的相关工作主要为协议状态机的被动推断和主动推断。1.1 被动推断 被动推断是基于离线数据包提取代表报文的状态信息，并分析生成协议对应的处理逻辑。Leita等9最早使用 Moore 状态机描述协议行为，同一类输入可能造成不同的输出，构成了状态的标签数组。Comparetti 等10先将数据转化为带标签的增强型前缀树接受器，而后将其转化为 Moore 状态机。Wang 等1基于已有数据统计状态类型之间的次序关系和转移概率值，并使用概率状态机描述上述统计数据。Krueger 等11将协议行为建模为隐马尔可夫模型，隐状态为协议内部逻辑状态，输出为协议消息，但协议行为本质上并不满足输出独立性假设。上述基于 Moore 状态机和隐马尔可夫模型的描述方法的前提是输出仅与当前状态有关，丢失了
