改进的安全协议自适应分析算法研究

陈远武

东莞市电子科技学校

改进的安全协议自适应分析算法研究

陈远武

东莞市电子科技学校

修正学习算法La⋆属于改进的安全协议自适应分析算法，它能够避免教师经验不足，并实现字符集扩展。立足于正确性和复杂度方面，对修正学习算法进行分析和证明，其为安全协议自适应模型检测提供助力，实现成本控制，有效缓解状态空间爆炸，使协议对环境和各种攻击方法极具防御性。

安全协议；自适应；分析算法

1 前言

安全协议的形式化分析方法包括形式逻辑方法、模型检测方法和定理证明三类。修正学习算法La*属于改进的安全协议自适应分析算法，从两个方面对La*学习算法进行修正。一方面可以将大字符集作为字母表，对符号自动机进行应用，并对观察表进行扩展，使之成为符号观察表；与此同时，对教师进行修正。其能够使安全协议自适应模型达到良好的监测效果，实现成本控制，对状态空间爆炸进行有效缓解，实现协议对环境和各攻击方法的自适应防御。

2 L＊学习算法

2.1 算法背景

从单个集合的成员和非成员中对未知正则语言集合进行识别。最小胜任教师教师给定正则语言集合，继而接收集合成员的资格询问，对假定集合进行判定，看其是否与未知集合等同，如果不同则给出反例。正确集合和假设集合的对称差即为反例。L*学习算法可以JFLAP的DFA工具为基础实现。多项式时间内，L*算法依从于最小胜任教师，对正则语言进行学习。假定背景为比较随机，可应用随机采样语言机对假设测试能力进行替代。

2.2 算法过程

学习者L*对观察表（S，E，T）进行维护，S代表前缀封闭集合，E代表后缀封闭集合，其分别是状态集合和区分状态的集合。T是一个函数，在中的元素字符串进行映射。假定se∈U，则T（s,e）=1；反之，T（s,e）=0。具体流程如下：

（1）初始化。对S和E进行初始化，使其成为空串λ，并以λ和字母表A的各个字母进行成员资格询问，对初始化观察表（S，E，T）进行构建。（2）检验完备性和一致性：假定（S，E，T）不具备一致性，需找出S中的s1和s2，a∈A，e∈E，使row（s1）和row（s2）相同，且T（s1ae）≠T（s2ae），在E中对ae进行添加，询问成员资格将T扩展为（S∪SA）。如果（S，E，T）不完备，需分别找到s1∈S、s2∈S使对于任意a∈A，row（s1a）和row（s）不相同，在S中添加s1a。借助成员资格询问实现T到（S∪SA）的扩展。（3）假定（S，E，T）完备且一致，对状态机M进行构建，构成等价询问。如果教师将一个反例ce返回，在S中对该反倒和全部前缀进行添加，并应用成员资格对T到（S∪SA）的扩展进行询问。再回归到步骤（2），校验其一致性和完备性，达标后，做步骤（3）的等价询问，直至回归到M=L（U）停止，输出M[1]。

3 修正学习算法

安全协议呈现发送者、接受者、加密、认证等诸多状态，很多应用背景下，教师或许不能对部分成员的资格询问做出解答。故而借助修正学习算法，对符号自动机进行应用。教师的定位是经验不足的教师，进行大字符集学习。

3.1 缺乏经验教师

受学习对象的不完全具体性或不可观察性限制，这些询问有可能得不到具体回答。最小胜任教师不能够满足这种实际需求，对缺乏经验教师进行引入，并向其学习，以获得所需知识。缺乏经验的教师有权对两个不相交的语言集进行询问，并对成员资格询问和包含关系询问进行回答。

对缺乏经验教师进行设定，通过资格询问和等价询问，对可行的符号自动机进行获取。具体而言，学习者的任务是分别对∠1的超集和∠2的符号自动机进行接受和拒绝。语言集分别为∠1和，呈不相交状态。具体情况有三种：（1）假定∠1和∠2都是正则语言，会有极具可行性的DFA。例如，可对∠1进行精确接受。（2）假定∠1和∠2都能够对上下文无关语言进行确定，该判定性问题能否被判定，无从得知。（2）假定∠1和∠2都是非确定性上下文无关语言，该判定性问题不具备可判定性。借助简单的归类对上下文无关语言是否为正则语言进行判定。

该算法能够在大字符集场景中进行应用，经验不足教师无法回答相关问题，需改进之前算法。它属于主动学习算法，能够对正则语言进行识别。假定教师能够对成员资格询问和包含关系询问进行回答。通过候选生成器对候选生成步骤进行操作，并对扩展的L*算法和符号学习算法进行运用，生成一系列候选自动机，其目标是3DFA C。继而进行完备性校验。完成操作后，对最小化符号自动机进行计算。最后校验其可行性。应用修正学习算法对最小化符号自动机进行计算，并通过集合包含关系询问，对∠1和∠2的区分度进行验证。如果验证成功，即对正确结果进行输入。反之，在第一步中输入反例，不断循环，直到输出正确结果。

3.3 证明正确性和分析复杂度

定理1能够终止修正学习算法，并实现最小的符号自动机，它能够对∠1和∠2进行有效区分。

引理1将Bi假定为Li的最小化符号自动机，能够对正则语言进行接受i=1,2。最小化的对∠1中所有字符串进行接受，并对所有字符串的C(3DFA)大小不超过|B1|×|B2|进行拒绝。

定理2与引理1的假设条件相同，修正学习算法对∠1和∠2的最小化符号自动机所需成员资格询问数目进行区分[2]。

证明将C假定为最小化的3DFA，能够分别对∠1和∠2中的所有字符串接受和拒绝。候选生成器所需要的成员资格询问数目最多为，错误假设背景下C（3DFA）的大小不超过经过一系列证明，修正学习算法需要2次包含关系询问对完备性和可行性进行检验。

4 结语

安全协议能够保障网络安全。学习算法在安全协议自适应分析框架中尤为重要。改进的安全协议自适应算法能够对部分教师经验缺乏问题进行有效解决，并实现字符集扩展。修正学习算法能够提高安全协议自适应模型检测效率，控制分析和设计成本，不断提高自适应防御能力。

[1]杨京,范丹,等.改进的安全协议自适应分析算法[J].通信学报,2015,(S1):266-276.

[2]王虎强，李东.一种基于自适应能力改进的AFSA算法研究[J].信息通信，2015,(10):47-49