渐进式的协议状态机主动推断方法_潘雁.pdf
《渐进式的协议状态机主动推断方法_潘雁.pdf》由会员分享,可在线阅读,更多相关《渐进式的协议状态机主动推断方法_潘雁.pdf(13页珍藏版)》请在咨信网上搜索。
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先将
17、数据转化为带标签的增强型前缀树接受器,而后将其转化为 Moore 状态机。Wang 等1基于已有数据统计状态类型之间的次序关系和转移概率值,并使用概率状态机描述上述统计数据。Krueger 等11将协议行为建模为隐马尔可夫模型,隐状态为协议内部逻辑状态,输出为协议消息,但协议行为本质上并不满足输出独立性假设。上述基于 Moore 状态机和隐马尔可夫模型的描述方法的前提是输出仅与当前状态有关,丢失了输入输出的关联性。Lee 等12考虑了输入输出的关联性,采用 Mealy 状态机描述行为,提升了模型的表达能力。Lin 等13生成状态机时引入数据流信息,考虑同一类型的协议消息中的参数差异形成的不同状
18、态转移,类似于寄存器状态机,但其必须提前选定关注的参数,同时面临着状态爆炸的问题。Sun 等8则使用带有概率的Mealy 状态机对同一类型下的差异进行描述。被动推断的缺点在于数据包中仅包含正样本,而仅基于已有数据构建最小化状态机是一个NP完全问题14,因此基于被动学习的模型是不够完整的。1.2 主动推断 主动推断的理论基础是主动自动机学习,其广泛使用的框架是 Angluin 于 1987 年提出的 MAT 框架4,框架包含一个学习器和一个预言机,学习器通过向预言机提出查询来学习未知的模型,预言机了解待测系统(SUL,system under learning)的所有内容,而学习器只知道 SUL
19、 的输入/输出字母表。为了学习未知自动机,学习器提出成员查询,即发送一个报文序列至 SUL,若 SUL 接受则返回“是”,否则返回“否”;而后基于一系列查询及其响应尝试构造一个行为与目标自动机相匹配的未知自动机,并提交至预言机,由预言机判断自动机是否正确并给出反例,称这一过程为等价查询。目标状态机以 Mealy 状态机为主,其可以定义 为 在 输 入 输 出 字 母 表,I O上 的 四 元 组0(,)S s=A,其中12,nIi ii=为有限的输入字母表,12,kOo oo=是有限的输出字母表,S是 状 态 集 合,0sS是 初 始 状 态,:SIS是状态转移函数,:SIO是状态输出函数,可
20、写为011011(,)(,)s iss io=,。此外,由字母组成的有序序列,称为串,记为w,串构成的集合记为*I,串的连接记为12ww,特别地,为空串。状态转移函数和状态输出函数可针对串扩充为*:SIS,*:SIO。当目标系统为协议实现时,首先可定义消息的分类函数class:TM,其中12,lTt tt=为协议类型的集合。由该分类函数构建的等价关系为classMM,如果12class()class()mm=,则有1class2mm,由此等价关系形成的等价类classclass|iimmmm=M将协议消息划分为多个消息类型,若class()imt=,将class m记为iM。协议实现在初始状态
21、的输出函数可记为*:AMM,由于本文只关注协议实现的响应类型,因此本文中将协议实现的输出函数简化为*:OAM。84 网络与信息安全学报 第 9 卷 主动自动机推断需要将上述输出函数进一步抽象为*:IOA,因此通常将协议类型作为协议输入字母表,在构建具象化模块时生成的数据包与输入字母是一一对应的关系。Cho等15以僵尸网络的命令控制协议为对象进行研究,通过手动逆向分析命令控制协议的结构,将请求数据划分为多个类型,将获得的类型作为输入字母表,而在具体的学习阶段,需要将字母表具象化为具体的数据包,并将响应数据抽象为输出字母,抽象和具象的实现极大地降低了学习的代价。Aarts16形式化地定义了抽象化和
22、具象化,将其称为映射器,其位于学习器和SUL之间,实现字母与实际数据的转化,现有的映射器都是基于协议技术规范或已有的协议数据包,通过协议逆向工程分析获得协议的类型与具体数据的对应关系,手动构建抽象和具象函数,且考虑的类型较为粗略。综上所述,将主动学习算法应用于实际系统,实现流程如图1所示。首先需要对输入空间进行抽象化,将输入空间划分为特定的类型,形成字母表;而后在MAT框架中,需要构建映射器,映射器包括对输入字母表的具象化模块和对输出字母表的抽象化模块。在实际实现中,映射器与目标系统之间具有缓存机制,对所有的查询进行缓存。在当前的研究中17-19,字母表均是提前确定的,且是手动分析的结果,通常
23、以消息类型表示字母表,且具象化模块是确定的,即该类型的数据包输入目标系统所得到的响应类型是相同的。在此框架基础上,研究人员针对不同协议展开研究。Ruiter等17基于LearnLib开源框架20构建了传输层安全协议(TLS,transport layer security)的映射器,推断了多个TLS开源实现,并且通过手动对比状态机和协议规范来分析逻辑漏洞。申莹珠等18基于LearnLib开源框架对TLS模式下的OpenVPN协议进行了状态机推断,并提出了一种基于时间压缩模型的状态机化简方法,以便进行手动的对比分析。Fiterau-Brostean等19针对数据包传输层安全协议(DTLS,dat
24、agram transport layer security)的特性实现了主动状态机学习,并发现了相应的漏洞;同时针对传输层控制协议(TCP,tronsmission control protocol)实现开展了相关的研究21,并将协议技术规范和协议状态机转化为NuSMV(new sym-bolic model verifier)语法,实现自动化的模型检查,后续基于寄存器自动机对TCP的滑动窗口特性进行了学习22。Guo等23构建了IPSec的输入输出字母表,分析发现了IPSec系统实现中的一些漏洞。王辰等24融合被动推断和主动学习,充分利用已有数据,构建扩展前缀树接收器实现查询的预响应,并提
25、出了一种基于变异的等价查询算法以便更有效地发现反例。图 1 协议状态机主动推断实现流程 Figure 1 The flow chart of protocol state machine active inference 综上所述,由于被动的状态机推断方法中数据包仅包含正样本,因此其模型的泛化是不够完整的,存在一定的局限性,而模型学习技术的发展促进了协议状态机主动学习的应用,如何融合被动和主动学习是值得研究的。同时,模型学习技术应用于实际系统所面临的问题包括:实际系统具有较大的输入输出字母表,应当探讨更有效地构造映射器的方法;实际系统学习过程中时间占比较高的是交互时间,降低实际交互的次数尤为重
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 渐进 协议 状态机 主动 推断 方法 潘雁
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。