基于协议知识的协议状态机主动推断方法

摘要

本发明提供一种基于协议知识的协议状态机主动推断方法，包括以下步骤：报文格式提取、观察表初始化、观察表闭合性检查、无效询问序列过滤、询问直接响应、候选状态机构造、等价判定、以及依据反例扩展观察表。本发明针对协议状态机主动推断过程中效率偏低的问题，依据协议会话样本集，提取协议报文之间的顺序约束过滤各种无效询问，同时基于协议会话样本集对会话样本中出现过的询问类别进行直接响应，此外，通过基于正例样本变异的方法有效搜寻候选状态机的反例，从整体上提升了协议状态机主动推断的效率。

说明书

技术领域

本发明涉及网络技术领域，具体而言涉及一种依据协议实体程序接收 及发送的网络报文，在分析相应协议具体知识的基础上，通过与协议实体 交互，不断补充需要的协议信息，自动化推断网络协议的协议状态机的方 法。

背景技术

在计算机网络中要保证有条不紊的交换数据，通信双方必须遵守网络 协议。网络协议是网络通信功能实现的核心要素，是网络通信、网络安全 等众多领域的重点研究对象。入侵检测、模糊测试、协议重用、协议脆弱 性分析等大量网络安全技术都依赖于详尽的网络协议规范信息。

网络协议规范主要包括协议格式和协议状态机两部分。协议格式关注 的是通信报文中各个协议域的组成和结构。协议状态机关注的是协议系统 中协议状态的数量以及协议系统在接收不同输入的情况下从一个协议状态 向另外一个协议状态迁移的规则。

网络协议包括公开协议和私有协议。公开协议的内容和细节都有公开 的标准文档，如HTTP、SMTP等通信协议。而私有协议没有公开文档进行 说明，往往被具体的网络应用所使用，如QQ即时聊天软件的通信协议、 Oracle数据库所使用的TNS网络协议以及一些恶意软件所使用的通信协议。

网络中私有协议的广泛使用，使得各类依赖于信息规范的网络安全技 术在应用范围上受到极大限制。为了解决协议信息未知的问题，研究人员 采用协议逆向的方法获取未知的协议规范。协议逆向是指在不依赖于协议 描述的情况下，通过对协议实体的网络输入输出、系统行为和指令执行流 程进行监控和分析，提取网络协议具体规范信息的过程。

传统的协议逆向采用人工方式，过程冗长耗时，准确度依赖于分析人 员的技术水平和实践经验。随着网络规模的扩大和协议种类的增多，对逆 向分析准确度和时效性的要求越来越高，传统基于人工的协议逆向分析已 不能满足实际应用的需要。协议自动逆向可以显著减少人工分析，提高私 有协议的分析效率，获得了越来越高的重视。

目前大部分协议自动逆向研究集中于协议格式的提取，分析结果中缺 乏协议状态机信息，制约了协议逆向结果的实际应用。近年来，随着协议 格式提取技术的相对成熟，一些研究人员开始尝试协议状态机逆向分析， 或者称为协议状态机推断。

依据在协议状态机推断过程中是否需要与协议实体进行交互，协议状 态机推断方法可分为被动推断和主动推断两类。被动推断依据给定的报文 样本集实施推断，在状态机推断过程中不需要与协议实体进行交互。主动 推断在已知样本集的基础上，利用请求询问和应答反馈不断扩充原始样本 集，以此为基础获取协议状态机信息。

在协议状态机主动推断领域，目前的推断方法主要以Angluin等人提出 的L*算法为实施的基础。L*算法维护了一个称为观察表(Observation Table) 的数据结构，观察表被定义为一个三元组(S,E,T)，其中S和E分别为基于 输入符号表Σ的有限长度字符串的前缀闭合集和后缀闭合集，T(s,e)是由 s∈S∪S·Σ，e∈E所确定的函数，符号“·”代表字符间的拼接关系。T(s,e)＝1 表示状态机接受字符串s·e，T(s,e)＝0表示状态机拒绝字符串s·e。观察表通 常采用二维表的表示形式，其中二维表的行是S∪S·Σ中的元素，二维表的 列是E中的元素，表中的条目是T(s,e)的取值。

观察表要求满足闭合性和一致性两种特性。对于任意s,t∈S∪S·Σ，当且 仅当对所有e∈E，均满足T(s,e)＝T(t,e)，称s等价于t，用s≌_Et表示，以[s] 表示所有与s等价的行。若对任意t∈S·Σ，存在s∈S，满足s≌_Et，则称观察 表满足闭合性。若对于任意s,t∈S，满足s≌_Et，那么对于所有的i∈Σ，s·i≌_Et·i， 则称观察表满足一致性。

L*算法假设存在一个可以对成员资格询问(membership query)和等价询 问(equivalence query)做出准确回答的仲裁者(Oracle)。L*算法的实施首先 需要依据成员资格询问构建闭合连续的观察表，进而生成对应的候选状态 机M，在此基础上，依据等价询问判断候选状态机M是否与真实的状态机 一致，是则终止推断，否则依据仲裁者给出的反例(counterexample)，继续 推断状态机。

传统L*算法的推断目标是无输出的确定型有限状态机。这种无输出的 确定型有限状态机，只考虑报文输入，并不考虑报文输出，忽视了协议系 统输入输出报文之间的内在联系。协议系统是带输出的状态迁移系统，采 用无输出的确定型有限状态机作为推断目标，所得到的状态机与实际协议 系统存在较大差异。

Li以L*算法为基础，在论文《Integration testing of components guided by  incremental state machine learning》(Keqin Li,Roland Groz and Muzammil  Shahbaz.Integration testing of components guided by incremental state machine  learning.In Testing:Academic and industrial conference-Practice and research  techniques,59-70,IEEE Computer Society,2006)中首次提出了对Mealy机的 推断算法LM+，算法用输出询问(output query)代替成员资格询问，获得协 议状态机对输入符号序列的输出结果。LM+算法要求观察表S集合内不存 在完全相同的元素，这样就不需要在状态机推断过程中考虑观察表的一致 性。此外，LM+算法改进了L*算法对反例的处理方法，在处理反例的过程 中，确定长度最小的区分序列，避免将过多的后缀扩展到观察表的E集合 中。

Cho等人以协议格式逆向方法Dispatcher和LM+算法为基础，推断出 了僵尸网络MegaD所采用的私有协议的协议状态机。Cho在LM+算法的基 础上进行了两点改进。首先，增加缓存，将串行查询改进为并行查询，减 少了询问等待发送所需要的时间；其次，将询问的返回结果保存在缓存， 对包含自循环结构的询问进行预响应，减少了向仲裁者发送的询问数量。 Cho的改进提升了协议状态机的推断效率。

由于在实际系统中并不存在能够回答各类判定问题的仲裁者，现阶段 比较常用的替代方法是将输出询问的符号序列实例化为报文序列，发送至 协议实体观察其输出。同时，基于输入报文类型集随机生成测试样本，来 判定推断得到的候选状态机是否与真实状态机近似等价。

协议状态机主动推断方法与被动推断方法相比，在推断过程中会不断 补充需要的协议实体信息，收集的信息内容全面，具有推断结果高的优点。 但此类方法的主要缺点是时间开销高、效率较低，对各类询问的反馈依赖 于协议实体程序的运行效率和网络延迟，此外，在等价判定过程中要寻找 有效的反例，反例能够帮助发现在推断过程中遗漏的状态，但反例的寻找 需要较高的时间开销，客观上制约了推断效率。

总体上看，推断效率的提高是协议状态机主动推断方法面临的最突出 的问题。目前协议状态机主动推断方法在推断效率方面的问题主要表现在 以下方面：(1)在状态机推断过程中将各类报文抽象为相互独立，无意义 的符号，忽略了各类报文之间的顺序约束关系，完全随机的产生询问报文 发送给协议实体程序，所产生的大量询问报文会被协议实体程序判定为无 效报文，降低了推断效率；(2)在协议状态机主动推断过程中并没有充分 利用捕获的会话样本集，部分询问的响应信息可以直接通过会话样本集推 断得出，而无需将所有询问都发送至协议实体并等待应答。(3)在推断候 选状态机是否与真实状态机等价时需要构造反例样本，但目前的判定方法 忽略了反例样本与正例样本往往存在部分共同前缀，完全随机地生成测试 样本试图找到能够区分候选状态机与真实状态机的反例，将产生大量无效 的测试样本，降低了等价判定效率。

发明内容

针对现有技术中存在的问题，本发明目的旨在提供一种基于协议知识 的协议状态机主动推断方法。针对协议状态机主动推断过程中效率偏低的 问题，在状态机主动推断算法LM+算法的基础上，依据协议会话样本集， 提取协议报文之间的顺序约束过滤各种无效询问，同时基于协议会话样本 集对会话样本中出现过的询问类别进行直接响应，此外，通过基于正例样 本变异的方法更加有效的搜寻候选状态机的反例，从整体上提升了协议状 态机主动推断的效率。

为达成上述目的，本发明所采用的技术方案如下：

一种基于协议知识的协议状态机主动推断方法，包括以下步骤：

(1)报文格式提取：采用报文格式提取方法获得输入、输出报文的协 议格式，将具有相同格式的报文划分为一类，并用抽象符号表示报文的类 别信息，将输入、输出报文组成的会话序列抽象为抽象符号所组成的字符 串序列。

(2)观察表初始化：观察表为三元组(S,E,T)，观察表的行由S∪S·Σ构 成，S·Σ＝{s·a|s∈S,a∈Σ}，Σ表示作为输入的抽象符号的集合，符号“·”代表 字符间的拼接关系，观察表的列由E构成。函数T将S∪S·Σ与E映射为输 出字符，作为表格中相应表格项的取值。观察表初始化时，令S＝{ε},E＝Σ， 其中ε代表空字符串；为观察表的每个表格项产生对应的输入报文序列， 并依据协议实体相应的输出报文信息给表格项赋值。

(3)观察表闭合性检查：判断初始化后的观察表是否满足闭合性的要 求，如果闭合性条件不满足，需要对观察表进行扩展，并为新增的表格项 赋值。如果闭合性条件满足，将构造与观察表对应的候选协议状态机。

(4)无效询问序列过滤：依据会话样本集，提取各类报文之间的顺序 约束关系，制定相应的过滤规则，如果作为询问的输入报文序列被判定为 无效，则直接过滤；如果作为询问的输入报文序列满足报文间的顺序约束 关系，则进行下一步的处理；

(5)询问直接响应：通过会话样本集的学习，可以对部分作为询问的 输入报文序列直接实施响应，而不需要将询问发送给协议实体；如果依据 报文样本集无法确定相应的响应信息，再将询问发送给协议实体程序进行 交互。

(6)候选状态机构造：当观察表满足闭合性要求后，可以依据观察表 构造候选的协议状态机。协议状态机表示为Mealy机的形式，其中输入集 合和输出集合按照报文格式提取阶段收集的信息填充，其他信息依据观察 表填充。

(7)等价判定：为了确定候选协议状态机是否与真实的协议状态机等 价，需要产生足够数量的测试序列，比较协议实体对相应测试序列的输出 是否与候选协议状态机对相应测试序列的输出相同。测试序列基于正常的 协议字符串序列构造，避免随机生成会导致大量无效测试样本的缺陷。如 果发现导致输出不相同的测试序列，该测试序列即为反例，需要以之为基 础进一步实施状态机推断。

(8)依据反例扩展观察表：在发现作为反例的字符串以后，需要依据 反例的后缀扩展观察表的E集合，在此基础上填充观察表，从而更全面的 将不同协议状态区分开来。重复(3)-(7)的步骤，直到输出与真实的协 议状态机等价的状态机结果。

所述协议报文格式提取阶段的工作流程如下：获取目标协议实体程序 的输入和输出报文，通过报文格式提取方法获得输入、输出报文的协议格 式信息，并依据报文格式进行类别划分，以抽象符号表示报文的分类信息， 进而将输入、输出报文组成的会话序列抽象为抽象符号组成的字符串序列。

所述观察表初始化阶段的工作流程如下：观察表为三元组(S,E,T)，观 察表中S集合对应的字符串代表了协议可能具有的状态，观察表中E集合 对应的字符串起到将不同协议状态区分开的作用。观察表初始化时，在确 定观察表的行与列之后，为观察表的每个表格项构造字符串，字符串的前 缀是表格项所对应的行值，字符串的后缀是表格项所对应的列值。将字符 串依据报文格式进行实例化，生成对应于协议实体程序的输入报文序列， 并获得协议实体程序对于相应输入报文序列的输出报文。将输出报文按照 格式信息抽象为输出字符串，依据表格项的列值的长度，将表格项的取值 设置为相应长度的输出字符串后缀。

所述观察表闭合性检查阶段的工作流程如下：判断初始化后的观察表 是否满足闭合性的要求，即对任意t∈S·Σ，是否都存在s∈S，满足s与t 等价。如果闭合性条件不满足，找到导致闭合性不满足的行t∈S·Σ，将t 移至S，并相应扩展观察表的S·Σ集合。为了填充新产生的表格项，需要产 生询问报文，获取相应的输出信息，从而为表格项赋值。如果闭合性条件 是满足的，将构造与观察表对应的候选协议状态机。

所述无效询问序列过滤阶段的工作流程如下：通过对协议实体程序输 入、输出报文会话样本集的学习，提取各类型报文之间的顺序约束关系， 制定相应的过滤规则，如果某个作为询问的输入报文序列被判定为无效， 则直接过滤，而不需要发送给协议实体程序进行处理；如果作为询问的输 入报文序列满足报文间的顺序约束关系，再进行下一步的处理。

所述询问直接响应阶段的工作流程如下：首先学习由抽象字符串序列 构成的协议会话样本，采用能够准确记录会话样本同时查询简便的数据结 构，例如，增强前缀树转换器EPTT(Extended Prefix Tree Transducer)，记录 会话样本集的信息。在出现作为询问的输入报文序列时，首先尝试利用 EPTT等结构中的信息推断响应结果，而不需要将询问发送给协议实体；如 果依据报文样本集无法确定响应信息，再将询问发送给协议实体程序。

所述候选状态机构造阶段的工作流程如下：若观察表满足闭合性要求， 可以依据观察表构造候选协议状态机。协议状态机表示为六元组的Mealy 机：(Q_M,I,O,δ_M,λ_M,q_0M)，其中代表输入的集合I和代表输出的集合O按照 报文格式提取阶段收集的信息填充。依据观察表填充协议状态机中的其他 信息，有限状态集Q_M＝{[s]|s∈S}；初始状态q_0M＝[ε]；状态转移函数δ_M([s],i) ＝[s·i]，对于任意s∈S，i∈Σ，状态转移函数表示在状态[s]下输入i后转移 的目标状态，目标状态对应于S中等价于s·i的状态；对于任意输入i，输 出函数λ_M([s],i)＝T(s,i)，对应于观察表中以s为行、i为列的表格项取值。

所述等价判定阶段的工作流程如下：为了确定候选协议状态机是否与 真实的协议状态机等价，需要产生足够数量的测试序列。在将测试序列实 例化为协议实体的输入报文后，得到协议实体程序对于这些测试序列的输 出响应，比较协议实体的输出是否与候选协议状态机对相应测试序列的输 出相同。导致两者输出结果不相同的测试序列即为反例。完全随机生成的 测试序列，大部分都是无效的。因此采用在正常报文序列的基础上，通过 插入、替换、删除等操作进行字符串变异，充分利用正常报文序列和反例 在结构上的相似性，从整体上提高测试序列的有效性。如果在发送足够数 量的测试序列后没有找到反例，则认为候选协议状态机在限定范围内与实 际的协议状态机等价。如果找到了反例，则说明候选协议状态机不满足等 价判定条件，需要将反例信息扩展到观察表中进一步实施状态机推断。

所述依据反例扩展观察表的工作流程如下：在发现作为反例的字符串 以后，确定反例的最小区分后缀。令反例c＝u·v，其中u∈S∪S·I，u是c的 前缀中满足输出与协议实体程序输出相同的长度最长的前缀字符串，相应 的，v就是反例中将候选协议状态机与协议实体真实状态机区分开的长度最 短的后缀字符串。在确定v以后，将v和v的所有后缀都加入到观察表的E 中，可以保证观察表的闭合性是满足的，也避免对观察表不必要的扩展。 在此基础上填充观察表，重复之前的状态机推断步骤，直到输出与真实的 协议状态机等价的状态机结果。

由本发明的技术方案可知，本发明的有益效果在于，利用协议实体程 序的输入、输出报文序列，获取协议通信中的相关知识，在协议状态机主 动推断过程中充分利用协议知识，减少不符合协议规范的无效询问报文的 发送，并基于报文样本集的信息，对部分作为询问的输入报文序列直接响 应，减少与协议实体的交互，能够显著提高协议状态机主动推断的效率。 此外，在正常报文序列的基础上构造测试序列，有助于提高测试序列的有 效性，避免将资源浪费在无效的测试用例上，从整体上提升了协议状态机 推断结果的准确度。

附图说明

图1为本发明的整体实现流程示意图。

图2为本发明中观察表的一个示例。

图3为本发明中为了对询问进行直接响应构造的EPTT的示例；其中图 3(a)为符号抽象的会话样本集；图3(b)为由图3(a)中符号抽象的会话样本集 S构造对应EPTT示例。

图4为本发明中依据图2所示的观察表构造的候选协议状态机。

具体实施方式

为了更好的了解本发明的技术内容，特举具体实施例并配合附图说明 如下。

如图1所示，根据本发明的较优实施例，基于协议知识的协议状态机 主动推断方法，包括以下步骤：

(1)报文格式提取：采用报文格式提取方法获得输入、输出报文的协 议格式，将具有相同格式的报文划分为一类，并用抽象符号表示报文的类 别信息，将输入、输出报文组成的会话序列抽象为抽象符号所组成的字符 串序列。

(2)观察表初始化：观察表为三元组(S,E,T)，观察表的行由S∪S·Σ构 成，S·Σ＝{s·a|s∈S,a∈Σ}，Σ表示作为输入的抽象符号的集合，符号“·”代表 字符间的拼接关系，观察表的列由E构成。函数T将S∪S·Σ与E映射为输 出字符，作为表格中相应表格项的取值。观察表初始化时，令S＝{ε},E＝Σ， 其中ε代表空字符串，为观察表的每个表格项产生对应的输入报文序列， 并依据协议实体相应的输出报文信息为表格项赋值。

(3)观察表闭合性检查：判断初始化后的观察表是否满足闭合性的要 求，如果闭合性条件不满足，需要对观察表进行扩展，并为新增的表格项 赋值。如果闭合性条件满足，将构造与观察表对应的候选协议状态机。

(4)无效询问序列过滤：依据会话样本集，提取各类报文之间的顺序 约束关系，制定相应的过滤规则(例如，属于类型4的报文必须出现在属 于类型7的报文之前)，如果作为询问的输入报文序列被判定为无效，则直 接过滤；如果作为询问的输入报文序列满足报文间的顺序约束关系，则进 行下一步处理；

(5)询问直接响应：通过对会话样本集进行学习，如果作为询问的输 入报文序列，可以直接通过会话样本集推断得出响应结果，则直接实施响 应，而不需要将询问发送给协议实体；如果依据报文样本集无法确定相应 的响应信息，再将询问发送给协议实体程序进行交互。

(6)候选状态机构造：当观察表满足闭合性要求后，可以依据观察表 构造候选的协议状态机。协议状态机表示为Mealy机的形式，其中输入集 合和输出集合按照报文格式提取阶段收集的信息填充，其他信息依据观察 表填充。

(7)等价判定：为了确定候选协议状态机是否与真实的协议状态机等 价，需要产生足够数量的测试序列，比较协议实体对相应测试序列的输出 是否与候选协议状态机对相应测试序列的输出相同。测试序列基于正常的 协议字符串序列构造，避免随机生成会导致大量无效测试样本的缺陷。如 果发现导致输出不相同的测试序列，该测试序列即为反例，需要以之为基 础进一步实施状态机推断。

(8)依据反例扩展观察表：在发现作为反例的字符串以后，需要依据 反例的后缀扩展观察表的E集合，在此基础上填充观察表，从而更全面的 将不同协议状态区分开来。重复(3)-(7)的步骤，直到输出与真实的协 议状态机等价的状态机结果。

参考图1所示的整体实现流程，本实施例的协议状态机推断方法主要 包括报文格式提取、观察表初始化、观察表闭合性检查、无效询问序列过 滤、询问直接响应、候选状态机构造、等价判定、依据反例扩展观察表等8 个部分，具体的实施方式以下分别说明。

(1)报文格式提取

本发明实施例首先大量收集协议实体程序网络通信产生的输入输出报 文序列，并采用PI(Protocol Information Project)的报文格式提取方法获取 输入报文和输出报文的格式信息。依据报文格式分别对输入报文和输出报 文进行分类，将具有相同结构的报文归为一类。对于每一类别，使用唯一 的阿拉伯数字(如1、2、3)进行标识。

在报文分类的基础上，以会话为单位，对网络通信行为进行抽象。会 话表示通信参与者之间进行的一次完整数据交换，能够反映在通信过程中 协议状态的迁移情况。为了便于实施状态机推断，本发明将输入、输出报 文组成的会话序列转化为抽象符号构成的字符串序列。

(2)观察表初始化

观察表为三元组的形式：(S,E,T)，观察表的行由S∪S·Σ构成，S·Σ＝{s·a|s ∈S,a∈Σ}，Σ表示作为输入的抽象符号的集合，符号“·”代表字符间的拼接关 系，观察表的列由E构成。函数T将S∪S·Σ与E映射为输出字符，作为表 格中相应表格项的取值。观察表中S集合对应的字符串代表了协议可能具 有的状态，观察表中E集合对应的字符串起到将不同协议状态区分开的作 用。图2为一个观察表的示例。

观察表初始化时，令S＝{ε},E＝Σ，其中ε代表空字符串。在确定观察 表的行与列之后，为观察表的每个表格项构造字符串，字符串的前缀是表 格项所对应的行值，字符串的后缀是表格项所对应的列值。将字符串依据 报文格式进行实例化，生成协议实体程序的输入报文序列，获得协议实体 程序对于相应输入报文序列的输出报文。将输出报文按照格式信息抽象为 输出字符串，依据表格项的列值的长度，将表格项的取值设置为相应长度 的输出字符串后缀。

(3)观察表闭合性检查

观察表必须满足闭合性的要求才能够构造协议状态机，因此需要对观 察表是否满足闭合性要求进行判断：即对任意t∈S·Σ，是否都存在s∈S， 满足s与t等价。例如，在图2中，所有S·Σ中的行在S中都存在等价的行， 该观察表满足闭合性条件。

如果闭合性条件不满足，找到导致闭合性不满足的行t∈S·Σ，将t移至 S，同时需要将t·Σ集合加入观察表原有的S·Σ集合中。为了填充观察表扩 展后新产生的表格项，需要产生询问报文，获取相应的输出信息，从而为 表格项赋值。如果闭合性条件满足，将构造与观察表对应的候选协议状态 机。

(4)无效询问序列过滤

通过对协议实体程序输入、输出报文会话样本集的学习，可以制定过 滤规则，以过滤明显不符合协议要求的报文序列。本发明实施例主要考虑 依据各类型报文之间的顺序关系制定过滤规则。

协议的报文类型之间往往存在一定的顺序关系。例如，SMTP协议以 HELO(或者EHLO)作为会话的开始，以QUIT作为会话的结束。

本发明的分析对象是私有协议，事先无法掌握报文类型之间的顺序关 系，需要充分利用报文会话样本集来获取信息。为了便于分析，过滤规则 的提取在报文格式提取的基础上实施。对于一个以抽象符号表示的输入报 文序列S＝(…4…7…10…)，在该报文序列中符号4位于7之前，符号7位 于10之前。本发明实施例以矩阵的形式记录报文序列中符号间的顺序信息。

若输入报文的类型数量为n，报文样本集上的顺序约束关系集可以用一 个n×n的矩阵表示。矩阵的第j行第k列的元素m_jk表示符号j位于符号k 之前的会话样本的数量。如果m_jk≥10(10为本实施例所设置的阈值)且m_kj＝0， 则认为符号j必须出现在符号k之前。如果在测试序列中，如果符号k出现 在符号j之前，则认为相应的测试序列是无效的。

本实施例将阈值设置为10，主要是考虑到部分符号出现的顺序在协议 中没有严格的限制，两种符号类型的顺序关系必须在样本集中具有足够的 普遍性，才会将这种顺序关系作为无效判定的条件。

以所构造的矩阵为基础，提取各类型报文之间的顺序约束关系，制定 相应的过滤规则，例如，属于类型4和类型7的报文必须出现在属于类型 10的报文之前。如果某个作为询问的输入报文序列被判定为无效，则直接 过滤，而不需要发送给协议实体程序进行处理，同时返回询问无效的信息。 如果作为询问的输入报文序列满足报文间的顺序约束关系，再进行下一步 的处理。

(5)询问直接响应

在状态机推断过程中出现的很多询问，可以利用样本集中学习的信息 直接推断出结果并进行应答，而无需与协议实体程序进行交互。为了达成 此目的，首先学习由抽象字符串序列构成的协议会话样本，采用能够准确 记录会话样本同时查询简便的数据结构，记录会话样本集的信息。

本发明实施例采用增强前缀树转换器EPTT(Extended Prefix Tree  Transducer)的结构记录会话样本集信息。EPTT本质上是一个多叉树，可看 作为一个初始状态机，分支代表了某个会话样本对应的抽象符号序列。

图3(b)展示了由图3(a)中符号抽象的会话样本集S构造对应EPTT的示 例。在图3(b)中，初始状态为根节点，用阿拉伯数字0标识。状态机从初 始状态开始接受输入，如果输入符号序列所到达的状态在原状态机中不存 在，则创建一个新状态，以阿拉伯数字唯一标识，并添加状态转移过程中 相应的输出信息；如果状态已存在，则转移至该状态，接受下一个输入， 重复上述过程直到EPTA接受样本集S中的所有输入符号序列。

EPTT构造完成之后，对于发送来的询问，采用深度优先搜索的遍历方 式进行直接响应。假设输出询问为(1·9,11)，表示询问在状态[1·9]下输入“11” 的输出响应。以图3(b)为例，状态[1·9]对应于从初始状态0下输入符号序列 “1·9”后转移至的状态4，遍历图3(b)可知在状态4下输入“11”的输出响 应为“12”，可以直接响应，更新T(1·9,11)＝12。若输出询问为(1·4,11)，在 EPTT中不包含相应信息，则直接响应失败，需要进一步与协议实体交互。

在询问直接响应阶段，当出现作为询问的输入报文序列时，首先尝试 利用EPTT结构对询问进行响应，而不需要将询问发送给协议实体。如果依 据EPTT记录的报文样本信息无法确定响应，再将询问发送给协议实体程序， 通过交互获得准确的输出结果。此外，可以记录发往协议实体的询问和相 应的输出，更新EPTT，避免后续过程中对类似询问仍无法直接响应，进一 步减少与协议实体的交互次数。

(6)候选状态机构造

若观察表满足闭合性要求，可以依据观察表构造候选协议状态机。协 议状态机表示为六元组的Mealy机：(Q_M,I,O,δ_M,λ_M,q_0M)，其中代表输入的 集合I和代表输出的集合O按照报文格式提取阶段收集的信息填充。依据 观察表填充协议状态机中的其他信息，有限状态集Q_M＝{[s]|s∈S}；初始状 态q_0M＝[ε]；状态转移函数δ_M([s],i)＝[s·i]，对于任意s∈S，i∈Σ，状态转移 函数表示在状态[s]下输入i后转移的目标状态，目标状态对应于S中等价于 s·i的状态；对于任意输入i，输出函数λ_M([s],i)＝T(s,i)，对应于观察表中以 s为行、i为列的表格项取值。

图4为本发明中依据图2所示的观察表构造的候选协议状态机。 Q_M＝{[ε],[1]}；初始状态q_0M＝[ε]；状态转移函数δ_M([ε],1)＝[1],δ_M([ε],2)＝[2]≌_E[ε],δ_M([1],1)＝[1·1]≌_E[1],δ_M([1],2)＝[1·2]≌_E[ε]；输出函数λ_M([ε],1)＝T_M(ε,1)＝10, λ_M([ε],2)＝T_M(ε,2)＝10,λ_M([1],1)＝T_M(1,1)＝11,λ_M([1],2)＝T_M(1,2)＝10。

(7)等价判定

为了确定候选协议状态机是否与真实的协议状态机等价，需要产生足 够数量的测试序列。在将测试序列实例化为协议实体的输入报文后，得到 协议实体程序对于这些测试序列的输出响应，比较协议实体的输出是否与 候选协议状态机对相应测试序列的输出相同。

以r_i表示所需产生的测试序列的数量，本发明实施例将r_i设置为 Angulin在其论文《Learning regular sets from queries and counterexamples》 (Angluin D.Learning regular sets from queries and counterexamples[J]. Information and computation,1987,75(2):87-106)中的数值： 1/ε(ln(1/δ)+ln2(i+1))。其中ε为准确度，表示每次生成的随机符号序列是反 例的概率不大于ε；δ为置信度，i为已经生成的候选Mealy机的个数。Angulin 在论文中使用该数值来判定成员资格询问的上限，本发明的应用场景与其 相似，实施例中利用该值来确定基于输出响应的等价判定的终止条件。

在等价判定过程中，导致两者输出结果不相同的测试序列即为反例。 测试序列如果完全随机生成，则其中大部分都是无效的。本发明实施例采 用在正常报文序列的基础上，通过插入、替换、删除等操作进行字符串变 异，充分利用正常报文序列和反例在结构上的相似性，从整体上提高测试 序列的有效性。

如果在发送足够数量的测试序列后没有找到反例，则认为候选协议状 态机在限定范围内与实际的协议状态机等价。如果找到了反例，则说明候 选协议状态机不满足等价判定条件，需要将反例信息扩展到观察表中进一 步实施状态机推断。

(8)依据反例扩展观察表

在发现作为反例的字符串以后，需要依据反例的后缀扩展观察表的E 集合。本发明实施例首先确定反例的最小区分后缀。令反例c＝u·v，其中 u∈S∪S·I，u是c的前缀中对应的输出与协议实体程序输出相同的长度最长 的字符串。相应的，v就是反例中将候选协议状态机与协议实体真实状态机 区分开的长度最短的后缀字符串。

在确定v以后，将v和v的所有后缀都加入到观察表的E中，可以保 证观察表的闭合性是满足的，也避免对观察表不必要的扩展。例如，如果v 是1·2·3，则1·2·3、2·3和3都应该加入到观察表的E集合中(如果相应元 素在E集合中已经存在，则不必额外增加)。

在此基础上填充观察表，重复之前的步骤，直到输出与真实的协议状 态机等价的状态机结果。

由以上技术方案可知，本发明的基于协议知识的协议状态机主动推断 方法，在状态机主动推断算法LM+算法的基础上，依据协议会话样本集， 提取协议报文之间的顺序约束过滤各种无效询问，同时基于协议会话样本 集对会话样本中出现过的询问类别进行直接响应，此外，通过基于正例样 本变异的方法更加有效的搜寻候选状态机的反例，从整体上提升了协议状 态机主动推断的效率。采用此方法需要获得协议实体程序，并能够根据需 要运行实体程序，向其发送特定的报文序列，并观察相应的报文输出，以 此作为协议状态机推断的基础。

综上所述，本发明的基于协议知识的协议状态机主动推断方法，将协 议系统视为带输出的状态迁移系统，在状态机推断过程中以协议程序的输 入输出报文为推断依据，充分考虑各类报文之间的顺序约束关系，避免了 将大量违背协议基本特性的无效报文发送给协议实体程序。其次，在推断 状态机的过程中，充分利用协议会话样本集尝试对询问报文进行直接响应， 能够减少与协议实体的交互，提高推断效率。此外，在推断候选状态机是 否与真实状态机等价时，以正常报文序列为基础构造测试报文序列，充分 利用正例与反例在结构上的相似性，提高了测试序列的有效性，进而从整 体上提升了状态机推断结果的准确度。

虽然本发明已以较佳实施例揭露如上，然其并非用以限定本发明。本 发明所属技术领域中具有通常知识者，在不脱离本发明的精神和范围内， 当可作各种的更动与润饰。因此，本发明的保护范围当视权利要求书所界 定者为准。