基于蒙特卡洛树搜索的EFSM可执行测试序列生成方法
技术领域
本发明属于协议一致性测试序列生成技术领域，具体涉及一种基于蒙特卡洛树搜索的EFSM可执行测试序列生成方法。
背景技术
通信网络的日趋复杂化使得通信协议开发和测试的难度与日俱增。通信协议软件中的细微错误也可能导致整个通信网络的异常，造成不可估量的损失。为了提升通信协议软件的质量，进行详尽的网络协议一致性测试成为了一种行之有效的途径。网络协议一致性测试作为协议测试的一个重要分支，主要目的是检测协议实现和协议规范的一致性程度；基于形式化模型的一致性测试方法(Model-Based Testing，MBT)有助于提升测试的质量和自动化程度，因此被广泛地推崇。在众多的协议形式化建模技术中，扩展有限状态机(Enhanced Finite State Machine，EFSM)由于其表达形式直观，又兼具刻画系统控制流和数据流的特点，成为了主流测试建模技术之一。
基于EFSM模型的协议一致性测试主要通过给被测系统一系列输入来激发相应的输出，通过观察系统输出是否与协议规范相一致来得出测试结论，这些输入输出对构成的序列，我们称之为一致性测试序列。由于EFSM模型在状态机FSM模型的基础上扩展了变量和谓词条件，从而导致一些变迁的执行相互存在依赖关系；如果直接应用有限状态机FSM模型的测试生成方法来生成EFSM模型的测试序列，可能导致生成的测试序列的不可执行问题。因此，如何自动生成EFSM模型的可执行一致性测试序列成为了一个技术挑战。
针对测试序列的可执行性问题，研究人员开展了许多探索工作，这其中基于遗传算法的搜索技术成为了一个主要阵营，它们把EFSM测试序列生成转化为一个优化问题，采用遗传算法来搜索求解，其中最具代表性的是Kalaji提出的方法《Kalaji,A.S.,R.M.Hierons,and S.Swift,An integrated search-based approach for automatictesting from extended finite state machine(EFSM)models.Information andSoftware Technology,2011.53(12):p.1297-1318.》，该方法首先使用一个算法生成满足覆盖需求的候选测试序列，但是这些测试序列不一定是可执行的，然后使用GA来生成能够触发候选测试序列可执行的测试数据；然而这类方法存在初始种群选择和种群长度设定的困难，生成的测试序列的可执行性仍需额外的步骤来进一步验证和确定。也有一些研究人员提出基于约束求解和符号执行技术来生成测试序列，但是这类方法对被测模型具有一定的约束条件，不具备普适性。
相对于上述方法，变迁可执行分析技术(TEA)更具普适性，它主要通过变迁可执行分析树的扩展搜索来生成目标测试序列，然而针对实际的协议，EFSM巨大的可达状态空间对应的可执行分析树的海量潜在扩展搜索空间，最终导致了状态爆炸问题的产生。
发明内容
鉴于上述，本发明提出了一种基于蒙特卡洛树搜索的EFSM可执行测试序列生成方法，该方法可以有效减少可执行分析树的扩展节点，加速可执行测试序列的生成。
一种基于蒙特卡洛树搜索的EFSM可执行测试序列生成方法，具体地：应用蒙特卡洛树搜索算法(Monte Carlo Tree Search，MCTS)建立EFSM对应的TEA树，从中找到一条满足测试覆盖条件(覆盖所有测试目标变迁)的路径，该路径即为可执行测试序列且该路径及其路径上每条变迁的输入、输出构成一个完整的测试用例。
进一步地，所述蒙特卡洛树搜索算法的具体实施方式为：首先建立EFSM对应的TEA树，所述TEA树中每个节点即对应一个状态且节点包含对应的状态名称以及整个EFSM的变量；从给定的起始状态即根节点开始进行搜索，当某个节点存在有多条输出变迁时，通过计算每条输出变迁的UCT(Upper Confidence BoundApply to Tree)值，经过对应UCT值最大的输出变迁搜索到下一个节点，且每经过一条变迁需查看走过的路径是否已包含所有测试目标变迁，若是则搜索结束，输出路径作为可执行测试序列，否则继续搜索。
进一步地，所述UCT值的计算表达式如下：
其中：N为当前节点，N'为N的父节点，UCT(N)为节点N与N'之间变迁的UCT值，Q(N)为当前节点N的累计奖励值，V(N)为当前节点N的被访问次数，V(N')为父节点N'的被访问次数，η为给定的权重系数。
进一步地，所述累计奖励值Q(N)的计算表达式如下：
其中：Δ(Ni)为在对当前节点N进行第i次蒙特卡洛树搜索过程的模拟仿真阶段中终端节点Ni的奖励值，budget为蒙特卡洛树搜索的搜索开销上限，n为TEA树中当前节点N至根节点路径上已覆盖的测试目标变迁数量，|TS|为所要求覆盖的测试目标变迁数量，|Ni.ω|为在对当前节点N进行第i次蒙特卡洛树搜索过程中根节点到终端节点Ni的路径深度，Max为蒙特卡洛树搜索所设定的最大探索深度。
进一步地，所述搜索开销上限budget通过以下关系式确定；
其中：|TS|为所要求覆盖的测试目标变迁数量，Max为蒙特卡洛树搜索所设定的最大探索深度，|N.path|为当前节点N到根节点的路径深度，μ为给定的开销参数，用于控制budget的缩放。
进一步地，所述蒙特卡洛树搜索算法在继续搜索的过程中，若超过所设定的最大探索深度Max，仍未找到一条从根节点起覆盖所有测试目标变迁的路径，则重新从根节点开始探索或增大最大探索深度Max或增大开销参数μ。
进一步地，本发明将EFSM可执行测试序列生成问题转化为一个基于TEA树搜索的马尔科夫决策过程，并应用蒙特卡洛树搜索算法进行求解。
进一步地，本发明建立了TEA树和蒙特卡洛树搜索算法的融合机制，利用蒙特卡洛树搜索算法来预测TEA树中节点的扩展合理性，即在每次TEA树扩展节点时，建立一棵以蒙特卡洛树搜索方式建立的TEA子树，利用这棵TEA子树状态空间信息选择更合理的扩展方向。
本发明基于蒙特卡洛树搜索算法的EFSM一致性测试序列自动生成方法(MTEA)将EFSM模型的可执行测试生成问题转换为TEA树中路径的马尔科夫决策过程，该方法借助MCTS算法强大的海量状态空间搜索能力，启发式引导TEA树的扩展方向来搜索目标序列，从而极大地提高了测试生成效率，最终避免了状态爆炸。
在本发明MTEA中，测试序列的生成从给定的初始状态格局即TEA树的根节点开始，根据具体的EFSM模型，对应TEA树中的节点可能有多个可执行的输出变迁待扩展，因此根据当时的树节点状态如何从多个可执行的输出变迁中做出选择变成了一个决策问题。正确的选择决策有利于尽早的找到一条满足测试覆盖要求的可执行测试序列，本发明方法基于蒙特卡洛树搜索算法使用随机采样技术来估计每个潜在扩展搜索方向的潜力，如果这种估计是似然正确的，那么TEA树的扩展方向总是能趋向目标节点，最终实现搜索最少的树节点找到一条最优的目标测试序列。
附图说明
图1为NetworkMonitor协议的EFSM模型示意图。
图2为基于MTEA算法生成测试序列的TEA树搜索示意图。
图3(a)为MTEA算法在模型M1下的探索节点数和生成FTS在不同μ值的回归分析示意图。
图3(b)为MTEA算法在模型M2下的探索节点数和生成FTS在不同μ值的回归分析示意图。
图3(c)为MTEA算法在模型M3下的探索节点数和生成FTS在不同μ值的回归分析示意图。
图3(d)为MTEA算法在模型M4下的探索节点数和生成FTS在不同μ值的回归分析示意图。
图3(e)为MTEA算法在模型M5下的探索节点数和生成FTS在不同μ值的回归分析示意图。
图4为MCTS算法的总体流程示意图。
具体实施方式
为了更为具体地描述本发明，下面结合附图及具体实施方式对本发明的技术方案进行详细说明。
本发明MTEA方法的主体框架描述如下：
算法1给定一个系统的测试EFSM模型M，MTEA算法的输入为：初始状态格局SC0、测试覆盖变迁集TS、最大搜索深度Max和开销参数μ，算法返回结果输出为一条满足覆盖要求的可执行测试序列FTS。算法初始化阶段(S1～S2)，使用初始状态格局SC0来初始化TEA树的根节点Nroot；算法的主体部分是一个while循环体(S3～S10)；算法的终止条件为：成功找到一条满足测试覆盖要求的可执行测试序列或TEA树的搜索深度超过最大上限Max。从高层抽象的来看，算法主要通过MCTS技术采样部分TEA树的扩展空间来搜索目标变迁序列，TEA树每一步扩展的决策依据来自于节点仿真和采样的反馈结果，具体由算法S7的函数Search(N)来实现；一旦一个新的子节点被扩展，那么算法立即检查该节点对应的路径是否满足测试要求，如果满足条件那么搜索得到一条FTS。在本算法中，我们采用的测试覆盖准则是全变迁all-transitions，显然本发明方法通过简单的扩展，同样适用于其他一致性测试覆盖准则。
函数Search(N)实现了蒙特卡洛搜索树算法MCTS和TEA方法的融合，它的最终目标是从多个备选待扩展子节点中挑选一个作为新子树的根节点。MCTS过程通常包含四个步骤：选择Selection、扩展Expansion、模拟仿真Simulation和回溯Backprogation。在算法中函数FeasibleOutTrans(N.sc)输出节点N.sc对应的可执行变迁集合，|FeasibleOutTrans(N.sc)|表示备选的可执输出变迁数量；如果当前节点只有一条输出变迁，那么算法直接调用函数Expand(N.Tnext)来实现节点扩展步骤；否则MCTS的四个步骤被迭代执行来选择下一个最优的扩展节点。
上述迭代过程不断进行，除非算法达到开销上限budget，开销上限定义为：
步骤1：选择Selection阶段。
该步骤的主要目的是挑选一个具有最大UCT值的子节点来扩展TEA树，UCT值的计算公式如算法2中S7所示，其中Q(Nchild)和V(Nchild)分别为节点Nchild的累积奖励和总的访问次数，计算公式的左部体现搜索算法鼓励优先搜索奖励值最大的节点，而右部则体现了算法具有鼓励探索较少访问节点的性质。通过这种策略，MTEA可以在搜索开销和最优结果之间实现权衡；具体而言，每个节点被访问的次数越多，那么UCT会相应变小，从而促使算法有机会来探索它的兄弟节点，这样每个节点都有了相应被扩展的机会。
算法2有两个输入参数：N和e，N为当前待扩展的节点，e描述了当前节点在选择步骤的状态。当e为true时，意味着算法当前正在构造一棵子树来探索子节点，在此情况下参数η设为0.5，这样使得奖励值在0～1区间取值并满足Hoeffding不等式；当e为false时，说明此时决策搜索子树已经构建成功，因此仅依靠UCT公式中右部取值来进行节点选择，所以参数η设为0，因此当算法2运行结束，它将返回一个UCT值最大的节点作为下一步待扩展的节点Nbest。
步骤2：扩展Expansion阶段。
算法3显示的Expand函数实现随机地选择当前节点N的子节点，从而实现扩展一步搜索树，节点N是算法2返回的结果。具体地，节点N可能存在多条输出变迁，首先Expand函数随机地执行一条可执行输出变迁来生成对应的尾状态格局，并赋值给Nchild.sc来构造新的子节点(S2～S3)；然后在把生成的子节点存到N的子节点集之前，我们需要初始化它的Q(Nchild)和V(Nchild)；最后返回新扩展生成的节点Nchild。
步骤3：模拟仿真Simulation阶段。
MCTS本质上属于启发式搜索算法，它受益于基于搜索空间采样的仿真过程，采样过程按照具体设定的仿真策略来进行；在本发明中我们基于主流的随机策略来实施TEA树空间的采用，实现MCTS算法的仿真过程。通常，MCTS算法中每轮仿真过程迭代进行，直到到达终端节点为止；在TEA扩展树的上下文中，由于被测协议EFSM模型的强连通性，实际的终端节点并不存在。在算法4中，有两种类型的节点我们用来作为终端节点：一种是当搜索深度达到预先设定的开销上限时的节点，另一种则是节点路径包含了所有测试覆盖目标变迁的节点。
具体地，simulation函数是一个while循环体，循环的结束条件反应了上述讨论的两种情况，即仿真采样深度达到了算法设定的最大上限Max，或者N.ω覆盖了所有的测试目标。当simulation函数执行结束时，它返回一个由函数Reward(N)计算的节点N的奖励值，奖励函数Reward(N)需要根据上述两种情况分别定义，具体如算法5所示：
奖励函数提供了一种机制来量化当前节点扩展方向针对具体测试目标的正确性估计，在测试序列生成的上下文中，奖励函数的定义需要考虑测试的覆盖准则。针对all-transiton的测试覆盖准则，算法5中给出了相应的reward函数。其中，|TS|为测试覆盖集的大小，|N.ω|为仿真过程结束时终端节点的路径长度；算法5中S2～S6计当前节点路径中已经覆盖测试目标变迁的数量，基于上述数据，我们构建了具体的奖励函数S7。
奖励函数的定义考虑了两类仿真的情况：一种是成功的找到一个节点，它的路径包含了所有测试目标变迁的情况，函数的右部
步骤4：回溯Backpropagation阶段。
在每轮搜索迭代过程中的仿真步骤，回溯操作用来更新选择节点的相关统计数据，在算法6所示的Backprogration函数中，两个输入参数N和Δ分别表示新扩展的节点和这轮仿真的奖励值，parent(N)表示N的父节点，通过while循环，该函数将终端节点奖励值Δ沿着它返回根节点的回溯路径来更新节点的统计数据。在这个过程中，从节点N到根节点路径上的所有节点数据将被逐一更新，这些数据包括累积奖励Q(N)和总访问次数V(N)。
以下为MTEA算法的一个实例说明，针对Network Monitor协议EFSM模型(如图1所示)的测试序列生成，图2给出了部分TEA树搜索的实例，在这个例子中，我们假定测试覆盖目标变迁集TS＝{T3，T5，T6，T7}，测试的目标为至少覆盖TS集合所有变迁一次。
根据本发明提出的MTEA算法，我们试图在TEA树空间中搜索一条最短的能够满足覆盖要求的可执行测试序列，在每次树扩展操作之后，算法需要立即判断是否找到了一条满足覆盖要求的变迁序列，如果找到，那么算法终止并输出一条结果序列，否则TEA启发式扩展搜索将继续进行。
正如图2中所示，树的根节点tn1对应的模型状态为S1，它在当前状态格局下只有一条可执行输出变迁T1，因此TEA树直接向前扩展一步，因为没有可选项，T1变迁对应的子节点tn2自然变成了下一步扩展子树的根节点。节点tn2则有两条候选输出变迁T17和T2，它们分别得到扩展，此时我们面临扩展方向的决策，需要从T17和T2的尾节点中挑选一个作为下一步待扩展的子节点，正确的决策应该能够引导TEA扩展朝目标方向进行。本发明采取的方法是发起一轮MCTS搜索，来采样当前节点对应的后续树的扩展空间，从而做出正确的决策，因此tn2节点执行MCTS搜索，构造了一棵sub-TEA-Tree1子树，算法按照MCTS的四个步骤迭代搜索构建搜索子树，基于搜索子树的采样结果来做出扩展方向的最终决策。具体地，在选择步骤中，因为S3对应节点的UCT值大于S1的值，因此S3被选中作为一下步扩展的节点，算法进入扩展步骤，S3只有一条输出变迁T3，T3的尾状态格局S4就被选中作为扩展对象；在仿真步骤中，从S4对应节点迭代进行随机搜索采样，直到找到一条覆盖目标的路径或者耗尽设定的搜索开销为止，算法进入回溯步骤，把终端节点的奖励值沿着历史采样路径回传更新，最终一轮MCTS搜索完成，节点S4被成功的扩展。
每轮搜索迭代都将扩展一个新的子节点并逐步构建整棵MCTS搜索树，当MCTS设定的开销budget耗尽，图2所示的sub-TEA-Tree1子树就被构建完成，可以用来支持TEA树扩展方向的决策。在这个例子里，根据sub-TEA-Tree1子树，由于节点tn4的UCT值最大，因此被选为TEA树扩展的一下个子节点。在测试序列生成的过程中，每当TEA树扩展面临方向决策时，MTEA算法都通过MCTS的采样搜索来辅助决策，最终我们总能相对高效的搜索到一条目标可执行测试序列。
为了验证所提出方法的可行性和有效性，我们基于五个基准协议EFSM测试模型开展了详尽的实验分析，这五个模型分别为：M1(Network Monitor)、M2(Inres initiator)、M3(Class II)、M4(OLSR)和M5(SCP)，具体模型细节如表1所示。实验中采用all-transition为覆盖准则，针对每个模型采用不同的初始状态格局和不同长度的测试覆盖集进行可执行测试序列生成。
表1
具体地，给定一个初始状态格局和测试覆盖集TS，算法将生成一条对应的可执行测试序列，测试序列能够覆盖所有TS中测试目标变迁至少一次。实验中，测试覆盖目标达成的难易程度与TS集合的大小和集合中包含的目标变迁有关，因此针对每个EFSM测试模型，我们随机生成长度为1到模型变迁总数的TS集；针对每种大小，我们分别随机生成20组TS集作为测试目标。
为了详细的研究算法受随机特性和初始状态格局的影响情况，每组实验我们重复100次，通过统计分析来评价方法的性能。为了说明本发明方法的有效性，我们选择了随机TEA方法(RTEA)和基于宽度优先的TEA方法(BTEA)作为基准方法来进行对比实验。具体的实验中，初始状态格局设定如下：M1模型，初始状态设为idle，初始变量值范围为[0,10]；M2模型，初始状态设为Disconnect，初始变量值范围为[0,5]；M3模型，初始状态设为s1，初始变量值范围为[0,1000]；M4模型，初始状态设为idle，初始变量值范围为[0,2]；M5模型，初始状态设为s1，初始变量值范围为[0,3]。本发明方法主要解决TEA方法中的状态爆炸问题，为了实验方便，我们设定当TEA树节点达到2000000时，即意味着产生了状态爆炸，因此2000000成为了我么算法运行的节点数量上限，当达到这个限制算法停止运行。MTEA算法中的初始参数Max设定为50；此外，为了探究算法对参数μ的敏感程度，我们分别基于值20、40、60、80和100开展了相应的实验，具体实验环境为i7-7700 CPU，16GB内存和Windows1064位系统。
表2
表2为平均实验统计分析结果，表2中列#N表示测试生成过程中扩展搜索的节点数，单位为10000；列#L表示生成的结果序列平均长度；列Cov和Gen分别表示平均覆盖变迁集的覆盖率和平均测试序列生成成功率。为了保证比较的公平性，我们只统计比价3种方法在测试生成成功时的平均扩展搜索节点数。表2中的统计数据表明，本发明方法与其他2种方法相比，可以极大的减少所需的TEA搜索空间。针对模型M1-M4而言，与BTEA方法相比，测试生成成功的情况下，MTEA方法减少的平均节点数至少89.72％，最大达到了92.49％。模型M5的实验结果表明，本发明方法和其它2种方法性能相似，仔细研究可以发现，M5的模型非常简单，换言之测试生成中不存在状态爆炸问题。因此，我们可以得出结论：本发明方法针对复杂的测试序列生成场景，具有避免状态爆炸的能力，可以有效应用于基于EFSM模型的协议一致性测试生成工程实践。
表3
表3为实验中的时间性能比较结果。直觉上，启发式的方法需要额外的时间开销来进行决策，可能会造成算法运行的时间成本，然而通过实验数据，我们可以清楚的发现MTEA方法时间性能要优于BTEA方法；究其原因，MTEA减少了大量的节点搜索时间，因此提高总的时间性能。
图3(a)～图3(e)给出了不同的参数μ值情况下，算法生成需要搜索的节点数和结果FTS长度的回归分析结果。从图中数据，我们可以发现μ值越大即搜索开销上限越大，那么算法得到FTS结果长度越短，但是搜索的节点数上升明显，与增加的搜索代价相比，结果长度减少的并不是很明显。通过回归分析，我们给本发明方法的应用给出了一些经验数据，实际应用中可以根据测试的上下文来具体调参。
上述对实施例的描述是为便于本技术领域的普通技术人员能理解和应用本发明。熟悉本领域技术的人员显然可以容易地对上述实施例做出各种修改，并把在此说明的一般原理应用到其他实施例中而不必经过创造性的劳动。因此，本发明不限于上述实施例，本领域技术人员根据本发明的揭示，对于本发明做出的改进和修改都应该在本发明的保护范围之内。
