黑盒测试中的覆盖率指标及其在错误检测中的应用

理论计算机科学电子笔记111（2005）53-71www.elsevier.com/locate/entcs利用自动黑盒测试Antti Kervinen1 和Pablo Virolainen2坦佩雷理工大学软件系统PO Box 553，FIN-33101 Tampere，FINLAND摘要本文提出了测试引导算法的三个组成部分：步骤评估、状态评估和评估顺序我们展示了如何一个简单的家庭的覆盖标准可以用来评估个人的测试步骤，以及如何测试系统的不确定性行为可以处理和长期的测试步骤计划与状态评估。 我们使用求值顺序来定义哪些状态以及何时被求值。基于这些思想实现了六种启发式算法。其中四个使用类似游戏的方法进行黑盒测试。此外，三个其他的测试指导算法进行了比较。通过测量检测渗透到两种不同大小的会议协议系统保留字：一致性测试、测试自动化、测试选择策略1介绍为了在给定的时间和成本约束下通过测试发现错误，关键问题是：当被测系统（SUT）被引导到以前没有访问过的状态时，故障检测更有可能。为了帮助引导系统进入这些未探索的领域，可以在白盒测试中使用各种覆盖度量，例如语句，决策和条件覆盖。1ask@cs.tut. fi2pablo@cs.tut. fi1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2004.12.00754A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）53在黑盒测试中，我们没有关于SUT内部结构的信息。在本文中，我们表明，几个简单的覆盖率指标仍然可以帮助揭示错误。由于无法测量系统状态的覆盖率，因此可以测量系统特定行为（即与环境的相互作用）的覆盖率。在本文中，我们将使用一个标记的过渡系统（LTS）来模拟SUT的行为。虽然我们的模型是一个单一的“martinat”LTS，我们的算法和结果适用于其他几个形式主义也。例如，可以考虑几个LTS、LOTOS、SDL、Petri网或可以展开到可伸缩状态空间中的任何其他形式的并行组合。然而这很容易导致状态爆炸问题，有一些方法可以用来解决它。状态空间可以组合地构造[17]，或者如果它不能立即构造，它可以通过计算下一个状态到有界深度[14]来生成。并不是所有的算法都适用于最后一种方法，但最好的性能。探索测试[9]，我们称之为测试方法，是自动化的。当系统的预期行为（以确定性LTS的形式）被赋予测试引擎时，它从初始状态开始探索LTS。在每种状态下，引擎决定是否发送输入、侦听输出或重置系统并重新开始测试。只有在LTS的当前状态下可能的那些输入和输出可以被发送到SUT或从SUT接受。问题是如何做出揭示错误的决策，也就是说，使系统给出意外的输出或在应该给出输出时保持沉默，而不探索LTS太长时间。本文的主要目的和贡献是介绍和比较启发式算法，旨在快速发现错误;并显示如何设计一个指定的覆盖辅助测试选择算法的问题可以分为几部分。通过对由两个和三个会议协议实体组成的会议协议系统的运行测试，对所介绍的算法进行了比较。(The会议协议基本上提供具有多个聊天室的聊天服务。 测量并比较发现错误所需的测试步骤数。通过用一个突变的协议对等体替换一个正确的协议对等体，将错误渗透到系统中正确和变异的协议实体在特文特大学实施[4]。这些实现在[1，14]中已经过测试，但是使用了不同的测试设置。虽然在上述出版物中测试了单个会议协议实体，但我们测试了由两个和三个客户端的系统提供的服务。通过这种设置，我们的目标是捕捉真正并发和反应式系统的本质：系统通常能够读取输入A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）5355同时给出几个正确的答案。关于自动测试生成的论文已经有很多Chow在[2他的W方法[3]的一个推广版本，由Luo和v. Bochmann [11]进一步发展，以更好地适合测试并发系统。在基于区分序列和唯一输入/输出序列的方法中，这些方法旨在发现它们逐个转换地检查，在转换之后，SUT和规范进入相同的状态。通常这些方法提供非常强的（或完整的）故障覆盖，但价格也很高。所需的测试非常长，为了确保故障覆盖率，必须对SUT的状态空间的规格和大小进行假设。transition tour方法[13]尝试执行规范中的每个transition至少一次。这种方法比前面提到的方法更实用（例如，允许不完整的规范），尽管它测试较少。我们的方法类似于这种方法，但除了覆盖转换之外，我们还可以同时使用更粗糙的覆盖标准来指导测试运行。在[10]中，Lee等人介绍了用于通信有限状态机的转换之旅。他们提出了一种指导方法，试图在每个状态机中单独执行每个转换，而不是规范的整个状态空间。这是一个有趣且合理的覆盖年龄标准，不幸的是，本文中提出的覆盖类别无法处理。我们的想法是，在这方面的指导是一些类似于PyhalalJanko [14].他们提出了一种启发式方法，可以预先计算规范中的一些未来步骤，以选择下一步。我们也实现了他们的算法进行比较。在第2节中，正式确定了LTS和覆盖标准第3节中介绍了测试引擎架构，以显示测试指导算法运行的环境。第四部分是本文的主要内容。首先，提出了启发式算法的基本组成部分--步骤评价、状态评价和评价顺序的概念。本节的其余部分致力于描述的启发式算法进行比较。比较的测试设置和结果见第5节。2背景我们将使用标记转换系统（LTS）来表示被测系统（SUT）的行为。56A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）53定义2.1[LTS]一个标号变迁系统，缩写为LTS，是一个四足动物（S，S，S，S），其中S是状态的集合，S是可见动作的集合。（alphabet），则τ∈/τi为n时的变换S×（τ∈{τ}）×S不可见作用，且s∈S是初始状态。每个可见的动作都是输入或输出（响应）。一个转换被称为输入（输出）转换，如果它被标记为输入（输出）动作。定义2.2LetL=（S，N，N，sN），即LT S s∈S，NI表示输入动作的集合，NO= N\N I表示输出动作的集合。 T I（s）={（s，a，sJ）∈∆ |a∈ I}是离开状态s的输入转换的集合。相应地T O（s）={（s，a，sJ）∈ N |a ∈ O}是离开状态的输出转换的集合测试引擎是测试SUT的实体，它被赋予一个确定性的LTS（即，没有由不可见操作标记的转换，并且离开同一状态的两个转换永远不会共享相同的标签）作为测试运行的输入。在试运行的每个点，发动机从初始状态开始跟踪LTS的当前状态。离开当前状态的转换指定了下一个测试步骤中允许的操作。执行转换意味着将当前状态更新为转换的目标状态。因为只有离开当前状态的转换才能被执行，并且因为LTS是确定性的，所以我们也可以不混淆地谈论执行动作。确定性是必需的，因为我们想要测量转换的覆盖率在t运行期间执行的LTS（S，S，S，S）的转换存储在多集执行中。 同样，可以将P2Pexec 如果一个过渡t∈n还没有被执行时，n_execute_c（t）=0，w表示t∈/execute_c。 如果thasben执行n >0次，则{t} exec（t）= n，我们也说t∈ {t} exec。将元素T添加到多集中自然地定义为：Jexec = exec+ T，其中对于T中的每个t，它保持Jexec（t）=exec（t）+1，并且对于其他tJ∈，tJ∈/T，它保持jexec（tJ）=我们的测试引擎能够测量八个覆盖类，这些覆盖类由零和一的三元组定义2.3变迁t=（s，a，sJ）是b1b2b3-被变迁te=（se，ae，sJe）i <$（（b1=1）<$（s=se））<$（（b2= 1）<$（a=ae））<$（（b3= 1）<$（sJ=sJe））覆盖。定义2.4LetL=（S，N ，N ，sN）， 并 且 可 执 行c是多个已执行的转换。 b1b2b3（|<$tJ∈exec：tJb1b2b3-coverst}是S.A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）5357v步骤validati）on行动名字）适配器可能第一项（s<\\\）UI--//\执行\（s/\（vtransition覆盖vexecutedtransition命令&响应vTraceinfor mation记录器cov. 因福奥UI纪律试探法你要去哪里？输入映射ExplorerSpecLTS测试引擎被测CPECPEFig. 1. 测试架构在覆盖类别B1B2B3的意义上的未覆盖的转换的集合。在本文中，我们使用三个覆盖类：111，001和010。直观地，为了根据覆盖111覆盖LTS，必须执行LTS的每个转变。覆盖范围001要求到达每个状态，并且010要求在LTS的转换中出现的每个动作也出现在执行的转换中。3测试引擎浏览器是测试引擎的核心（参见图1）。它在一个循环中运行，要求自动化模块执行下一个测试步骤。如果浏览器建议将输入发送到SUT，则浏览器将其转发到适配器模块。适配器将输入操作转换为命令，并将它们发送到SUT中的适当接收器。在我们的情况下，接收器是会议协议实体（CPE）的实际实现的用户接口进程（UI）如果输入操作被接受，这在我们的设置中意味着将命令发送到UI进程的stdin管道是成功的，资源管理器将执行规范中相应的转换。执行更改规范的当前状态、覆盖率值，并记录在执行trace。如果输入操作被拒绝，浏览器将在可能的情况下执行规范中被拒绝的检测拒绝输入的能力使得规范和实现之间的测试关系比ioco[16]关系更广泛。然而，我们在本文中实际上是在测试ioco关系，因为在我们的测试运行中，输入拒绝既没有发生，也没有在规范中考虑。如果资源管理器建议侦听输出，则资源管理器尝试读取58A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）53并移除适配器模块的响应队列中的第一个元素。队列由纪律模块填充，纪律模块从UI的标准输出管道读取响应并将其转换为动作。纪律模块决定进程响应的排队顺序，以防响应同时变得可读。我们使用如果队列为空，资源管理器将一直等待，直到队列中的操作变得可读或发生超时。超时导致资源管理器接收特殊的δ（静止）操作（δ属于指定LTS的字母表，被认为是输出操作）。当从适配器模块接收到输出动作时，浏览器从指定模块验证接收到的动作可以在当前状态下执行。如果不是，它会宣布一个非法的响应错误并停止测试。否则，类似于输入转换执行来执行动作。如果逻辑模块决定不应该从当前状态继续测试，它将“死锁”返回给测试引擎。我们当前的测试引擎实现在死锁之后停止测试4试探法我们将构建测试引导算法的问题分为三个部分。第一部分，步骤评估，为单个输入和输出transi- tions提供值。该值描述其执行的可取性。除了转换数据之外，所执行的转换的多个集合可以选择值。定 义 4.1[St epevaluationfunction]ForanLT S L= （ S ， n ， n ， sn ）astepevaluation function is a function eval：n ×Nn→ R.如果在每个状态中最多有一个可能的输出转换，则测试指导将更加直接。然后，我们可以，给定一个适当的步骤评价函数，预先计算最短的可能序列的过渡后，步骤评价函数是非正的每一个过渡。当然，这不是很实用，因为找到这样的序列很容易成为NP难题。然而，当同时存在多个备选正确输出时，引导变得更加复杂。与状态评估，这是问题的第二部分，我们试图估计最好的步骤序列，通过假设的SUT的行为，当它被允许以几种不同的方式响应状态评估基于A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）5359离开状态的转换（由步骤评估给出）、它们的目的地状态的值（由先前的状态评估给出）、以及根据其对下一输出的期望。我们实施了两种状态评估策略。在第一种情况下，在“悲观玩家”算法中使用，SUT被期望输出动作，以便最大限度在另一种状态评估方法中，在测试运行期间，基于在状态中实际从SUT接收的响应，用其概率加权的响应的能力的平均值用于状态的评估这被应用在“自适应播放器”和“状态空间评估”算法中。该过程的第三个也是最后一个部分是评估顺序：应该评估哪些状态和转换以及何时评估。该算法实现了两个评价顺序。在玩家算法中，计算从当前状态开始的有限数量的这些算法的名字是受测试运行的类似游戏的方法的启发。在每一轮测试中，测试引擎决定它是采取行动（向SUT发送输入）还是让SUT采取行动（监听SUT的响应）。移动是一个过渡的执行：每一次移动都会使分数增加过渡的值（由步骤评估函数给出）。玩家算法是贪婪的：他们试图在计算的步骤中收集尽可能大的分数在“状态空间评估”算法的评估顺序中，在测试运行开始时计算LTS的每个状态的值。在测试期间必要时重新计算这些值。因此，状态空间的所有部分，即使远离当前状态，也会影响下一个测试步骤的决策。我们实现了以下九个测试引导算法，并在测试运行中评估了它们的错误检测性能。前两个是简单的随机算法，它们只是为了与其他七个算法进行辩论而实现的。4.1随机随机试探法随机选择一个离开当前状态的转换如果所选转换由输出操作标记，则测试引擎等待输出。否则，转换的输入动作被发送到SUT。60A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）53hiX--∈|{∈|∈}|||函数播放器（s：状态，深度：整数，EXPERIMETEC：多组转换）ifdep=0orr（TO（s）=0andTI（s）=0）thenreturnn0endifdesirability和P是局部关联映射，初始为空。action是一个全局关联映射。最佳输入是由转换和值组成的结构##计算输入，存储具有最大值的transition-value对最佳输入：= MAXeval（t，xexec）+player（dest state（t），depth−1，xexec+{t}）t∈TI（s）##评估输出，计算期望输出值对于每个t TO（s），desirability[t]：= eval（t，example）+player（dest state（t），depth1，example+t）的范围内端P：=估计输出的概率（TO（s），pixelexec，desirability）o值：=P[t]·期望值[t]t∈TO（s）##返回最佳选择，当输入和输出同样好时，优先选择输出如果TO（s）=0或（TI（s） 0且最佳输入值>0值），则其他action[s]：=best input.transition返回最佳输入值action[s]：=监听输出返回值end if算法1.博弈者算法的状态评估框架4.2贪婪随机这是一个稍微增强的随机启发式。在每个状态下，根据以下规则决定下一步。如果没有输入，或者如果正确的输出肯定会导致新的转换被覆盖，则会监听输出。否则，如果通过执行输入动作覆盖了新的转换，则发送输入。如果不是，则如果SUT可能给出覆盖新转换的输出，则在状态s中监听输出，概率为不T O（s） t /xmlexec/ TO（s）。 如果由于前面的规则而没有监听输出，并且如果在该状态下输入和输出都是可能的，则以概率0监听输出。5. 否则，选择随机输入。4.3悲观主义者有两个版本的悲观玩家算法，具有不同的步骤评价函数。两者在状态评估中使用相同的预测启发式：假设SUT选择其响应，以便最小化执行转换的评估函数值的总和玩家算法的状态评估部分的骨架被表示为算法1。它返回一个值，该值描述了作为第一个参数给定的状态的可取程度。该算法是递归的。 作为递归的底部，它返回A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）5361如果t∈T，将值0转换为以（搜索）深度0调用它的状态如果当深度>0时，计算最佳输入值和用于监听输出的值。输入转换t∈TI（s）的期望值是eval（t，t_exec）（一个阶式评估函数，我们很快就会回到这个问题）和其目的地状态的值。后者是通过递归地调用目标状态的算法来计算的，深度减1，t加到执行的转换的多集中。具有最大期望值的输入转换与最佳输入结构的值一起存储。我们的MAX函数的实现在播放器算法中是确定性的：如果有许多同样需要的输入转换，它总是返回相同的。输出TO（s）的可计算性与输入类似。在悲观玩家算法中，概率估计返回一个映射P，其中P[t] = 1，用于具有最小期望的输出转换t。对于其它输出转变tJ，P[tJ] = 0。因此，可用输出转换的最小期望值存储在ovalue中。最后，best input.value和ovalue的值中的较大者通过将其作为函数的值返回而与状态s相关联。该算法将状态中的最佳操作（监听输出或最佳输入）存储在全局操作表中。玩家算法中的评估顺序是相同的玩家函数在每个测试步骤之前使用以下参数调用：• s=规范的当前状态• 深度= 5• 在目前为止的测试运行过程中，执行已执行转换的多集。当算法停止时，下一个测试步骤的操作存储在action[当前状态]。在算法的简单版本中，仅过渡覆盖（111） 参见下面的等式（2）。因此，所有未执行的转换都被认为是同样可取的。为了避免尝试一次又一次地执行相同的转换序列而失败，转换的执行计数减小了步长评估函数的值。每次执行时，我们使用未执行转换值的1/(1)mem（t，T）=0ift∈/T(2) eval-simple（t，exec）= 10·（t，111（exec））−exec（t）62A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）53(3)eval-comp（t，exec）= 10·（t，111（exec））+50·（t，001（exec））+250·（t，010（exec））−exec（t）复杂评估函数（3）背后的启发式思想是，发送一个以前没有发送过的输入以及请求一个看不见的输出是发现错误的最简单方法。因此，与新的输入和输出转换相比，新的输入和输出操作应该以高优先级进行测试。同样，访问未访问的国家也是值得赞赏的。复评估函数中的因子10、50和250是固定的，假设该算法以搜索深度5调用。 在 在这种情况下，在一个搜索分支中存在未执行的动作使其优于仅包括已经执行的动作的分支。 如果最好的分支包含相同数量的未执行操作，那么包含未访问状态的分支优于没有状态的分支4.4自适应播放器与悲观玩家类似，自适应玩家算法有两个版本。一个使用阶跃评价函数（2），另一个使用函数（3）。自适应和悲观参与者之间唯一的区别是他们估计同时可用的输出概率的方式。而悲观的球员给输出监听的最小值的分支开始输出动作，自适应球员使用输出分支的加权平均值。这个想法是试图根据先前在同一状态下收到的响应来估计输出动作的概率。算法1中的函数估计输出的概率（T_O（s））将以下映射从输出转变返回到概率：1+高级管理人员（t）(4)P[t]=高级（1+高级执行）（tJ））tJ∈TO（s）如果没有输出转换被执行，则它们的概率相等。当执行转换时，转换的概率会增加。因此，玩家算法试图适应SUT的行为4.5状态空间评价状态空间评估算法将期望值与状态和转换两者相关联。与参与者不同，它评估每个状态的值A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）5363∈∪/256最佳输入：= MAXdec（value[dest state（t）]）+eval（t，destexec）functionsseval（（S，s）：LTS，exec：multiset）for eachs s S：value[s]：= 0end for计算值：=S而Calc选择s∈Calc，Calch：=Calc\{s}iXt∈ThI（s）i椭圆形：=P[t]·dec（value[dest state（t）]）+eval（t，destexec）t∈TO（s）new value：=max（best input.value，oval）如果new value=value[s]，则计算：=计算以前的状态value[s]：=new valueend ififbest input.value> oval or（best input.value = oval and rand（）<0. （5）然后choose[s]：=在最佳输入转换action[s]：=best input.transition其他action[s]：=监听输出结束if结束while算法2. 状态空间评价在状态空间中。因此，该算法能够为执行序列制定非常长的计划。 代价是在大的状态空间中计算值可能是昂贵的。状态空间评估算法被呈现为算法2。该算法将为每个状态评估的值存储在值表中，该值表最初包含零。开始时，每个状态都属于Calc集合，这是要（重新）评估的状态的集合。算法循环运行，直到Calc集合为空。在循环中，每次从Calc集合中删除一个状态，并按如下方式计算;让所选状态为s。用于发送输入的值被存储到最佳输入结构中，并具有给出该值的转换。过渡是从同样好的过渡中随机选择的。该值为eval（t，t_exec）与t的目标状态的减小值之和的最大值，其中t∈T_I（s）。在我们的测试运行中，我们选择的减量大约为10%（有一个小的常数递减），并使用8位定点运算。 因此dec（a）=max（0，[230a−1）.实现中的步骤评估函数是(5)eval-sspace（t，exec）= 256·（t，111（exec））其中，n如等式（1）中所定义。递减的结果是，从状态s到达状态所需的序列越短，状态就越合乎需要。利用我们的递减函数和步长评价函数（5），状态s的合意性由离s最多56步的状态的合意性来表示。这是因为64A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）53状态的值可以至多为2511（考虑具有到自身的输入转换t=（s，a，s）的状态S，其中eval-sspace（t，a，s）= 256）。在收听输出的评估中，类似于自适应播放器算法来估计输出的概率：P[t]在等式（4）中定义。存储在变量oval中的输出侦听值是eval（t，valueexec）和转换t的目标状态的减小值之和的加权平均值。所选状态s的值是best input、value和oval中的较大值。如果该值与value[s]不同，则新值将存储到值表中。所有从状态转换到状态s的状态都被添加到Calc集合，因为它们的值可能会被值[s]的更改所影响为了避免永远循环，dec函数应该选择一种状态值不会无限制增长的方式为了使算法更快地停止，我们使用粗定点算法：在评估函数中将函数的值乘以256，dec仅使用分数的整数部分。在阶跃评价函数（5）的测试运行中，状态空间评价算法表现不佳。 问题是算法的速度 一个循环的未执行的转换与一个很长的未执行的转换序列一样好，导致新的状态。我们编写了以下步骤评估函数来增强性能，尽管它没有解决问题。(6)eval-ss2（t，exec）= 256·（t，111（exec））+512·（t，010（exec））4.6Pyhalalal-Heljanko该算法已如[14]中所示实现。该算法旨在覆盖LTS的所有转换。在每个测试步骤之前，算法调用概率为0.75的GreedyTestMove如果子程序没有被调用或者它不能决定下一步，则随机决定。如果存在可用的输入动作，则随机选择决定以概率0.5发送随机输入（来自T1（当前状态））。否则，测试引擎将侦听输出。GreedyTestMove首先检查离开当前状态的转换如果存在未覆盖的输入和输出转换，则以概率0.5选择未覆盖的输入转换的随机动作，并且以概率0.5监听输出。如果存在未覆盖的输入转换，但没有未覆盖的输出动作A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）5365∈则选择随机未覆盖的输入。如果存在未覆盖的输出跳变但不存在未覆盖的输入跳变，则监听输出。如果既没有发现的输入转换，也没有发现的输出transition-itions，然后在LTS中进行有界搜索。该算法构造为短的动作序列σ尽可能地简化，以便执行它需要LTS进入状态S，从该状态S可以执行未覆盖的转换。 搜索是有界的，使得σ的长度至多为十个动作。如果在边界内没有找到所需的状态，GreedyTestMove就无法做出决定，并按照第一个地方的描述进行随机选择。该算法类似于玩家算法：两者都是贪婪的，并使用对LTS的有界前瞻来做出决策。仍然有显著的差异。该算法仅在当前状态中不存在未覆盖的转换时向前看，并且向前看的深度不超过到最近的期望状态的步数。球员们在每一步之前都要向前看，而且总是看得很深。此外，该算法是乐观的：当在当前状态中存在未覆盖的输出时，如果没有未覆盖的输入转换，则总是监听输出。只有当考虑到输入行为时，参与者才会乐观在测试运行期间，自适应播放器对尚未执行的输出动作变得越来越悲观。悲观的参与者总是期望得到最不想要的输出。最后，这个算法是不确定的，而参与者是确定的。5实验5.1执行已测试的会议协议实现可从[5]下载我们通过包中包含的UI在服务级别中测试了该协议[5]。该协议提供聊天服务。用户可以加入会议、向其参与的会议发送消息（这会导致同一会议中的所有其他用户接收消息）、离开会议并从头开始。命令和响应如表1所示。该实现允许每个用户一次最多参与一个会议。通信不保证可靠（消息可能丢失），但不应将消息传递给其他会议中的客户。我们有五个SUT设置。其中两个包含两个客户端进程，其余三个客户端进程。每个设置都包含一个变异的客户端进程，其他客户端是正确的实现。包含相同数量的客户端的设置根据突变客户端所在的位置而不同。66A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）53命令/意义“会议议定书”UI进程启动jme cf使用昵称mesm加入会议cf发送消息m到当前会议l离开会议“““表1命令和响应运行：有时客户端1，有时客户端2或3是坏的。通过这些设置，我们可以使确定性算法的结果有更多的变化，从而使它们与非确定性算法更具可比性。所有客户端进程和测试引擎都在同一台机器上运行（Ultra-PCIe、500MHz、512 MB内存，运行Solaris 8操作系统）。客户端进程通过套接字（数据报类型）进行通信，提供无连接和不可靠的服务。5.2质量标准我们对两个或三个用户通过会议协议进行通信的系统的行为进行了在系统中，有两个会议供用户参加。用户名为CL1、CL2和CL3，他们在加入会议时使用这些用户名作为昵称。用户只能向其会议发送一条消息M1为了简单起见，它指定发送到会议的消息永远不会丢失。也就是说，除了发送者本身之外，会议中的每个人都接收发送的消息。因此，发送消息是有限的，以便我们可以确定是否每个用户都应该收到它们。例如，当用户开始加入会议时，在用户收到提示之前，没有人可以向会议发送消息否则，我们将不知道用户是否应该接收在加入过程中发送的消息。两个和三个客户端的系统使用TVT（坦佩雷验证工具）进行建模[8]。规格是确定性LTS，无τA. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）536710000100010010自适应（3）（3）（2）自适应（2）Greedy random P-H SSeval（6）random SSeval（5）图二、 在两个客户端系统中检测到错误之前的测试步骤数过渡。具有两个客户端3的模型具有671个状态、24个可见动作和1784个转换。另一个有三个客户端的模型4有191995个状态，45个可见动作和853218个转换。5.3结果我们在测试设置中使用了客户端进程的九个不同的突变体每个突变体进行了测试32次，每个不确定性和一次，每个确定性的启发式算法。突变体由[5]中解释的数字识别。结果中使用的突变体是14、17、19、21、22、24、27、28和60。在没有深入研究突变行为的细节的情况下，他们的错误范围从无法接收某些PDU到更新内部数据结构的错误和发送错误。 突变体被选中，使他们产生错误的服务。其他一些突变体符合规范。通过测量检测突变系统中的错误所需的步骤数来比较启发式算法结果见图2和图3。算法按步骤的中值数排序。还显示了最小、最大和平均步数测试运行并没有给出估计状态评估函数的差异的方法：自适应和悲观玩家在相同的步骤评估函数下表现大致相同我们认为3 http://www.cs.tut。文件名/MBT 04/CL 2 CF2 MSG1.lsts.gz4 http://www.cs.tut。文件名/MBT 04/CL 3 CF2 MSG1.lsts.gz最小中位数平均最大68A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）5310000100010010（3）自适应（3）贪婪随机（2）自适应（2）随机P-H图3.第三章。在三个客户端系统中检测到错误之前的测试步骤数错误被发现得太快了适应SUT包含动作名称覆盖率（010）的步骤评估函数的算法比具有更简单函数的算法性能更好。函数（3）的玩家算法总是比函数（2）的玩家算法好。将状态空间评估算法的阶跃评估函数由（5）转换为（6），也提高了状态空间评估算法的性能但即使有了增强，状态空间评估算法的表现不佳。对于671个状态的LTS，状态空间评估算法比玩家算法运行得更快。对于191995个状态的LTS，状态空间评估算法的实现太慢而无法使用。该算法经过优化，以便仅重新计算通过执行测试步骤直接检测到的状态，即，将其放入算法2开始时的Calc集合中。对于步骤评估函数（5），添加到Calc的唯一状态是执行的转换的源状态。具有评价功能(6) 由所执行的动作标记的转换的所有源状态被插入到Calc中。玩家算法决定论的影响可以在图中看到。最小值和最大值之间的差距相对较小，中位数非常接近另一端（恰好是测试运行中的最小值）。如果玩家随机选择输入动作，并在同样好的动作中发送贪婪随机算法的效果出奇的好。即使它监视最小中位数平均最大A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）5369只有过渡覆盖，并不计算未来的步骤，它的工作比球员同样简单的步骤评估功能在三个客户端系统。在这种情况下，非决定论可能会对参与者有所帮助。在两次测试运行中，改进了Pyhal？la？-Heljanko算法这可能是由于贪婪随机的渴望，以听取输出时，它是保证增加覆盖。此外，当不存在这样的保证时，贪婪随机地偏好发送确保增加覆盖的输入，而不是监听不需要增加覆盖的输出。同样，在Pyhal？la？-Heljanko和purerandomwalkintheetestsetupswithtwoclients之间存在明显的差距，正如[14]中所述6结论我们已经介绍了如何在覆盖SUT规范的基础上自动引导测试本文提出的主要测试引导算法包括分步算法和状态评估算法.类似于“偏好未测试的输入/输出而不是测试的输入/输出”、“访问规范的未访问状态”、“执行未执行的转换”和“避免多次执行相同的转换”的启发式可以在步骤评估部分中实现。预测SUT响应的数学模型属于状态评估部分。在某些情况下，更精细的步骤评估函数在分析中可能有用在[6]中，提出了动作之间的距离。问题是，鉴于该行动datareq！CL1！CF1！M1（客户端CL 1将消息M1发送到会议CF 1）被执行，不可见的动作datareq！CL1！CF1！M2离开！CL1！CF 1（客户端1离开会议1）被认为同样有趣。然而，在这种情况下，第一次离开会议可能比发送另一条信息更有趣动作之间的距离将有助于估计如果已经执行了非常相似的动作，那么一些其他的动作（具有更大的距离）将是优选的。在我们的测试运行中，动作之间的距离可能不会有太大的影响。只有24或45个行动。例如，客户端只能向会议发送一种消息因此，执行新的动作同样有趣，不管之前执行过什么动作。当规范是专门为测试目的而编写时，通常会出现这种情况。如果更多的数据被绑定到动作中，情况就不同了：比如说，用户可以发送三条消息而不是一条，并加入五个会议70A. Kervinen，P.Virolainen/Electronic Notes in Theoretical Computer Science 111（2005）53两个人中的一个测试运行表明，当错误很简单时，除了转换覆盖率之外，还测量操作名称覆盖率的评估函数可以更快地检测到错误。确认感谢Jaco Geldenhuys和Antti Valmari的宝贵意见。这项工作是由TEKES，Conformiq Software Oy Ltd和诺基亚研究中心资助的SASOKE项目的一部分。引用[1] Belinfante，A.，Feenstra，J.，德弗里斯河G.，Tretmans，J.，Goga，N.，费斯湖Mauw，S.&Heerink，L.：正式测试自动化：一个简单的实验。通信系统测试国际研讨会，KluwerAcademic，1999年，pp. 179-196.[2] Chow，T.史：“测试软件设计建模的状态机”。IEEE Transactions on Software Engineering，SE-4（3），1978，pp. 178比187[3] Fujivara，S.，v. Bochmann ，G.，Khendek，F.，Amalou ，M. &Ghedamsi ，A. ：“TestSelection Based IEEE软件工程学报，卷。17（6），1991，pp.591-603.[4] 会议协议案例研究，http://fmt.cs.utwente.nl/ConfCase/。最后由Jan Feenstra于1999-11-19更新。[5] 会议协议实现源代码 ， http://fmt.cs.utwente.nl/ConfCase/v1.00/implementations/confprotv3c2.tgz 。文 件包装中的日期为2002年2月25日 至 2 8 日 。[6] 费斯湖M. G.，Goga，N.，Mauw，S. &Tretmans，J.：“测试选择，跟踪距离和启发式。 Proc.TestCom 2002，第14届通信系统测试国际会议，Kluwer Academic Publishers 2002，pp. 267-282.[7] de Vries，R.G. &Tretmans，J.：使用SPIN进行在线一致性测试。Intern