ｃＮ４３—１２５８／ＴＰＩＳＳＮ１００７—１３０Ｘ计算机工程与科学ＣＯＭＰＵＴＥＲＥＮＧＩＮＥＥＲＩＮＧ＆ＳＣＩＥＮＣＥ２０１２年第３４卷第２期Ｖ０１．３４，Ｎｏ．２，２０１２文章编号：１００７—１３０Ｘ（２０１２）０２—０１５０—０９一种基于ＵＭＬ状态图的规约变异测试方法ＡｎＡｐｐｒｏａｃｈＴｅｓｔｉｎｇＢａｓｅｄｔｏｏｎＳｐｅｃｉｆｉｃａｔｉｏｎｔｈｅＭｕｔａｔｉｏｎＵＭＬＳｔａｔｅＤｉａｇｒａｍ米磊。贲可荣ＭＩＬｅｉ，ＢＥＮＫｅ－ｒｏｎｇ（海军工程大学计算机工程系。湖北武汉４３００３３）（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ，ＮａＶａｌＵｎｉｖｅｒｓｉｔｙｏｆＥｎｇｉｎｅｅｒｉｎｇ，ｗｕｈａｎ４３００３３－Ｃｈｉｎａ）摘要：规约变异测试从软件功能的角度，对规约进行分析，从而揭示规约中存在的问题。本文提出一种基于ＵＭＬ状态图的变异测试方法，针对每种变异算子，分析其是否会引入冲突，进而有效避免不合理的变异操作；分析了每种变异算子产生等价变异体的条件，能够在生成变异体的同时检测并移除等价变异体，进而减少其对测试过程的影响；给出了杀掉每种变异体所需满足的条件，可在此基础上产生杀掉特定变异体所需的测试用例，从而提高测试用例集的质量。在此基础上，根据变异算子的实际功能，整合了功能相同的算子，减少了变异算子的数量，从而进一步降低了变异测试的开销。实验结果表明，本方法能够较好地提高测试用例的质量，进而提升测试的效率。Ａｂｓｔｒａｃｔ：Ｓｐｅｃｉｆｉｃａｔｉｏｎｍｕｔａｔｉｏｎｔｅｓｔｉｎｇａｎａｌｙｚｅｓｔｈｅｓｐｅｃｉｆｉｃａｔｉｏｎｆｒｏｍｔｈｅｐｅｒｓｐｅｃｔｉｖｅｏｆｓｏｆｔｗａｒｅｆｕｎｃ—ｔｉｏｎｓ，ａｎｄｃａｎｒｅｖｅａｌｔｈｅｅｒｒｏｒｓｉｎｔｈｅｓｐｅｃｉｆｉｃａｔｉｏｎ．Ｉｎｔｈｉｓｐａｐｅｒ，ａｎａｐｐｒｏａｃｈｔｏｍｕｔａｔｉｏｎｔｅｓｔｉｎｇｂａｓｅｄｉｎｔｒｏｄｕｃｅｄｔｏｏｎｔｈｅＵＭＬｓｔａｔｅｄｉａｇｒａｍｉｓｐｒｏｐｏｓｅｄ．Ｆｏｒｅａｃｈｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒ，ａｃｏｎｆｌｉｃｔａｍｌｙｓｉｓｉｓａｖｏｉｄｃａｎｕｎｒｅａｓｏｎ—ａｂｌｅｍｕｔａｔｉｏｎ．Ｔｈｅｃｏｎｄｉｔｉｏｎｏｆｔｈｅｇｅｎｅｒａｔｉｏｎｏｆｅｑｕｉｖａｌｅｎｔｍｕｔａｎｔｓｉｓａｎａｌｙｚｅｄ，ｓｏｔｈｅｓｅｍｕｔａｎｔｓｃａｎｂｅｄｅｔｅｃ—ｔｅｄｉｎｔｈｅｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｆｔｅｓｔｉｎｇ，ａｎｄｔｈｅｉｍｐａｃｔｍａｄｅｂｙｔｈｅｓｅｍｕｔａｎｔｓｃｏｎｄｉｔｉｏｎｏｆｇｅｎｅｒａｔｉｎｇｔｈｅｏｐｅｒａｔｏｒｓａｃｃｏｒｄｉｎｇｔｅｓｔｔｏｃａｓｅｓｂｅｒｅｄｕｃｅｄ．Ｔｈｅｎ，ｔｈｅｒｅｑｕｉｒｅｄａｎｆｏｒｔｈｅｍｕｔａｎｔｓｉｓａｌｓｏａｎａｌｙｚｅｄ．Ｂａｓｅｄｃａｎｏｎｔｈｅｂａｓｉｓ，ｔｈｅｒｅｉｓｃｏｓｔｉｎｔｅｇｒａｔｉｏｎｏｆｔｈｅｉｎｃｌｕｓｉｏｎｒｅｌａｔｉｏｎａｍｏｎｇｔｈｅｍ，ｗｈｉｃｈｃａｎｒｅｄｕｃｅｔｈｅｏｆｔｈｅｍｕｔａｔｉｏｎｔｅｓｔｉｎｇ．ｅｆｆｅｃｔｉｖｅｌｙ，ａｎｄｉｎ—Ｔｈｅｅｘｐｅｒｉｍｅｎｔｓｈｏｗｓｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｐｐｒｏａｃｈｃｒｅａｓｅｉｍｐｒｏｖｅｔｈｅｑｕａｌｉｔｙｏｆｔｈｅｔｅｓｔｃａｓｅｓｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｍｕｔａｔｉｏｎｔｅｓｔｉｎｇ．关键词：变异测试；ＵＭＬ；状态图；变异算子；等价变异体Ｋｅｙｗｏｒｄｓ：ｍｕｔａｔｉｏｎｔｅｓｔｉｎｇ；ＵＭＬ；ｓｔａｔｅｄｉａｇｒａｍ；ｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒ；ｅｑｕｉｖａｌｅｎｔｍｕｔａｎｔｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００７—１３０Ｘ．２０１２．０２．０２８中图分类号：ＴＰ３１１．５文献标识码：Ａ生新的程序，这些新产生的程序可称之为变异体。１引言变异测试‘１１是一种面向缺陷的软件测试方法，每一个变异体都有针对性地模拟了系统中各种可能的缺陷，并寻找能够识别这些变异体的测试用例集，用于改进测试用例集的质量，从而提高测试的效率。变异测试可很好地揭示软件缺陷，也可用来通过使用变异算子对程序进行细微的语法变动，产＋收稿日期：２０１１一０２一ｚ３；修订日期：２０１１一０５—２５基金项目：国家预研基金资助项目（５１３２７０１０４）通讯地址：４３００３３湖北省武汉市海军工程大学计算机工程系软件工程教研室Ａｄｄｌ屯ｓｓ：Ｓｅｃｔｉｏｎｏｆ４３００３３，Ｐ．Ｒ．ＣｈｉｎａＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇ，ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅ“ｎｇ，ＮａｖａｌＵｎｉｖｅｒｓｉｔｙｏｆＥｎｇｉｎｅｅｒｉｎｇ，Ｗｕｈａｎ，Ｈｕｂｅｉ万方数据米磊等：一种基于ＵＭＬ状态图的规约变异测试方法评估测试用例集的质量，以及评价测试的充分性。规约变异测试是变异测试的延伸，通过对规约做合乎语法的变更产生变异体，并通过寻找杀死这些变异体的测试用例，来增强已有测试用例集揭示规约中缺陷的能力。同时，也可以基于变异体生成测试用例，用以检测规约与实现代码间的一致性［２｜。在实际测试项目中，往往存在着软件规约不明确或不完整等问题，这些规约中问题如不及时发现并修正，随着时间的推移将会产生越发严重的影响，消耗大量不必要的资源。同时，依据这些规约设计的测试用例质量也会较低，进而影响着测试的效率。因此，可采用规约变异测试解决这些问题。ＵＭＬ状态图是一种应用较为广泛的规约描述方法，主要用于描述一个对象在其生存期间的动态行为与状态变迁，在软件分析和设计建模中占有重要地位［３］。因此，本文将ＵＭＬ状态图作为研究的对象。与程序变异类似，在对规约进行语法上的微小变化后，生成的变异体可能在语义上与原规约保持一致，可称这种变异体为等价变异体。它们无法用测试用例进行标识，这就造成在变异测试过程中，针对存活变异体生成测试用例时，会因为等价变异体的存在而造成不必要的资源开销。已有研究表明，在变异体产生后对其检测，将会造成较多的资源开销，而且随着测试规模的增加，这种开销也不断攀升，因此等价变异体是制约变异测试效率的重要因素之一［４］。然而在已有研究工作中缺少关于等价变异体的分析，降低了变异测试的可操作性。本文在已有工作基础上，给出状态图的变异算子的定义，并针对每种变异算子是否会引发冲突，是否会产生等价变异体，以及杀掉相应变异体所需满足的条件等问题进行深入分析，从而提高变异测试的可操作性，并能够在生成变异体的同时检测其是否为等价变异体，降低其对测试效率的影响。２相关工作变异算子的定义是变异测试至关重要的问题之一［引。Ｆａｂｂｒｉ等‘６３提出了基于状态图的变异测试方法，给出了一组变异算子，涵盖了部分状态图的元素。Ｌｉ等‘７３针对状态、输入输出、跃迁等相关错误设计变异算子，主要包含跃迁丢失、跃迁冗余、万方数据１５１初始状态变更等共１１种变异算子，并给出从已有测试用例集中，选择能够杀死变异体的测试用例的方法。Ｔｒａｋｈｔｅｎｂｒｏ［８］针对嵌入式实时交互系统的状态图定义了包括继承关系、正交跃迁及时间性等在内的变异算子，可以模拟时间延迟、继承关系变更等错误。Ｈｉｅｒｏｎｓ等凹３则针对概率状态图设计了相应的变异算子，可以模拟概率变化、变更初始状态、变更跃迁的目标状态以及增加跃迁共四类错误。为了简化测试过程，Ｂｅｌｌｉ等［１叩将状态图简化为有向图，即将状态看作有向图中的结点，跃迁看作有向图中的边，不考虑跃迁的触发事件与监护条件。在此基础上，定义了结点增加、结点缺失、边增加以及边缺失４种变异算子。上述工作从不同的侧面定义了相应的变异算子，但这些定义存在一定的片面性，例如Ｌｉ等给出的变异算子中未涉及跃迁监护条件变异以及增加非初始／终止状态变异等算子，而Ｂｅｌｌｉ等的工作中仅包含４种变异算子。此时，变异过程无法模拟未涉及方面的错误，从而降低了变异测试揭示错误的能力。同时，部分变异算子在功能上与其他算子相互重合，其产生的变异体对测试贡献很小，却会增加较多的资源开销，因此需要在定义算子后，对这些算子进行整合。但已有工作很少涉及这部分内容。如果将这些问题遗留到变异测试后期分析与处理，则会增大测试的复杂度。本文基于状态图包含的基本元素，设计相应的变异算子，同时分析了每一种变异算子产生无效或等价变异体的条件，可以在执行变异算子的同时移除相应变异体，从而可以降低测试开销。同时整合了功能重合的变异算子，进一步提高了变异测试的效率。３ＵＭＬ状态图变异算子３．１ＵＭＬ状态图ＵＭＬ状态图由状态和跃迁构成，状态图中的每一个状态是可达的。初始状态是对象的初始状态，而终止状态是对象的最后状态，代表一个状态图的终止点。跃迁使对象从一个源状态到达一个目标状态，源状态和目标状态可以相同，一个跃迁由触发事件、监护条件以及动作三部分组成。当系统处在某一个状态时，如果触发事件被接受，且监１５２护条件的值为真，则这个跃迁被触发，并执行这个跃迁的动作，同时跃迁的目标状态变成当前状态。前提假设：（１）不存在不确定性的状态转换，即当系统离开某状态时能且只能满足一条跃迁的触发事件与监护条件，否则认为状态图中存在跃迁冲突。由于本文涉及的变异测试旨在评估规约及测试规约的用例质量，因此生成的变异体也应满足本假设，所以在特定变异操作后需要进行冲突检查，若存在冲突则停止该变异操作，否则接受该变异操作。（２）不考虑状态图的层次性。本文主要考虑状态图在单元测试中的应用，即对非组合的类或对象进行建模，因此暂不涉及嵌套状态图的分析。基于上述假设的前提下，ＵＭＬ状态图可表示成Ｄ一＜Ｓ，Ｔ，Ｅ，Ａ，ａ，ｐ，ｙ，艿，ｐ＞，其中：（１）Ｓ为状态图Ｄ中状态的集合，ｓ。为初始状态，＆表示终止状态；（２）Ｔ为状态图Ｄ中跃迁的集合；（３）Ｅ为触发跃迁的事件集合；（４）Ａ为触发跃迁后的动作集合；（５）ａ：Ｔ—Ｓ，对于任一跃迁ｆ∈丁，ａ（ｚ）表示￡的源状态；（６）ｐ：ｒ＋Ｓ，对于任一跃迁￡∈Ｔ，ｐ（￡）表示￡的目的状态；（７）ｙ：Ｔ＿＋Ｅ，对于任一跃迁￡∈Ｔ，ｙ（￡）表示触发￡的事件序列；（８）艿：了、Ａ，对于任一跃迁￡∈Ｔ，ｄ（￡）表示￡触发后的执行动作集合；（９）ｐ：Ｔ至表达式ｒ的映射，对于任一跃迁￡∈Ｔ，ｐ（￡）表示￡所需满足的监护条件ｒ。类似地，通过改变Ｄ中元素生成的变异体Ｍ也可以表示成Ｍ一＜ｓ７，Ｔ７，Ｅ７，Ａ７，ａ７，∥，ｙ７，艿７，ＩＤ７＞的形式。变异算子根据其改变的元素可分为跃迁变异、状态变异、触发事件变异、监护条件变异以及动作变异。３．２跃迁变异通过在Ｄ中增加、删除或变更一个跃迁产生变异体Ｍ，主要包含以下变异算子：（１）跃迁增加。通过在Ｄ中增加一个跃迁￡７产生变异体Ｍ。由于增加跃迁可能会引入跃迁冲突，因此需要进行冲突检查。当不存在跃迁冲突时，可生成覆盖状态口７（￡７），且满足ｙ７（￡７）与ＪＤ７（￡７）的测试用例来杀掉Ｍ。若在状态口７（￡７）下，ｙ７（￡７）万方数据计算机工程与科学２０１２，３４（２）与或ｐ７（￡７）不可满足则Ｍ为等价变异体。（２）跃迁删除。通过在Ｄ中删除跃迁￡ｉ∈Ｔ产生变异体Ｍ，这使得覆盖状态口（￡ｉ）且满足ｙ（ｆ。）与ｐ（￡ｉ）的用例能够在Ｄ中正确执行，却无法在Ｍ中正确执行，因此可以用其杀掉Ｍ。（３）跃迁变更。在Ｄ中改变跃迁￡ｉ的源状态口（￡ｉ）或目的状态口（￡；）产生变异体Ｍ，分为以下情况：①改变屯的源状态ａ（￡：），即存在某状态ｓ７∈Ｓ且ｓ７≠口（￡ｉ），使得口７（￡ｉ）一ｓ７。此时，对于状态ｓ７而言，相当于增加一条跃迁，因此应进行冲突检查。当不存在跃迁冲突时，执行覆盖状态ａ（￡ｉ）且满足ｙ（屯）与ｐ（友）的测试用例可以杀死Ｍ。②改变￡ｉ的目的状态口（ｆ，）。此时，执行覆盖状态ａ（￡。）且满足ｙ（￡ｉ）与ｐ（￡。）的测试用例可以检查出Ｍ与Ｄ的差异。③交换跃迁￡ｉ的源状态口（≠ｉ）与目的状态口（￡。），即转换ｆｉ的方向。与情况①类似，首先要进行冲突检查。当不存在冲突时，执行覆盖状态口（岛）且满足ｙ（￡ｉ）与ｐ（岛）的测试用例可杀掉Ｍ。３．３状态变异通过在Ｄ中增加、删除或变更一个状态产生变异体Ｍ，主要包含以下变异算子：（１）状态增加。通过在Ｄ中增加状态ｓ７产生变异体Ｍ，分以下情况：①ｓ７为初始状态，同时需要增加跃迁￡７，使得口７（￡７）一ｓ７。由于初始状态仅起到标识作用，即指示对象开始状态迁移前所处的状态。因此在Ｄ中增加初始状态ｓ７，相当于增加跃迁￡７，使得口７（￡７）一ｓ。。由于初始状态触发的跃迁通常是无条件跃迁，此时增加新的跃迁会引入跃迁冲突，所以应停止该变异操作。②ｓ７为终止状态，同时需要增加跃迁￡７，使得∥（ｆ７）一ｓ７。与情况①类似，终止状态也仅标识状态跃迁的停止，因此本变异操作相当于增加跃迁ｆ７，使得∥（￡７）一％可按３．１小节增加跃迁操作进行处理。③ｓ７为其他状态时，同时需要增加跃迁￡７与￡”，使得口７（￡７）一ｓ７且口７（，）一ｓ７。若，未引入冲突，则生成覆盖ｓ７且能触发ｔ”的测试用例即可杀死变异体Ｍ。（２）状态删除。通过在Ｄ中删除状态ｓｉ∈Ｓ产生变异体Ｍ。在移除ｓｉ的同时，需将以其为源米磊等：一种基于ＵＭＬ状态图的规约变异测试方法状态或目的状态的跃迁一并移除。该操作使得原本覆盖状态ｓ。的跃迁路径发生变更，因此执行覆盖ｓｉ的测试用例将无法正确结束，从而揭示出Ｍ与Ｄ的差异，导致Ｍ被杀。（３）状态变更。通过变更状态ｓｉ∈Ｓ产生变异体Ｍ。状态包括入口动作、活动、内部转换以及出口动作等内容，可将状态的变更细化为对应项的变更。此时，执行覆盖ｓ。的测试用例可以检测出Ｍ。３．４触发事件变异通过增加、删除或变更Ｄ中某跃迁的触发事件产生变异体Ｍ，主要包含以下变异算子：（１）触发事件增加。通过为Ｄ中跃迁￡：∈丁增加触发事件ｅ７产生变异体Ｍ，分为两种情况：①ｙ７（岛）＝ｙ（岛）＾Ｐ７，该操作增强了岛被触发的约束，使得￡ｉ有可能在满足ｙ（￡；）的情况下无法被触发，因此原可以触发跃迁￡。的测试用例无法在变异体Ｍ中正确触发跃迁￡ｉ，从而可用其杀死Ｍ。若处于状态ａ７（反）时，ｙ（￡。）实现时Ｐ７也同时实现，则Ｍ为等价变异体。②ｙ７（岛）一ｙ（￡ｉ）ＶＰ７，则该操作弱化了￡ｉ被触发的约束。若新增ｅ７后，存在跃迁￡ｉ，使得口７（岛）一ａ７（￡ｉ）且ｙ７（￡；）与ｙ７（‘，）、ｐ７（￡。）与ｐ７（￡，）可同时被满足，则执行该变异操作会使得对象处于状态ａ７（￡ｉ）时，可同时触发跃迁￡ｉ与￡ｉ，从而产生冲突，因此需要进行冲突检测。当不存在跃迁冲突时，可通过增加测试用例来杀死Ｍ。新增用例应覆盖状态口７（￡ｉ）且包含事件Ｐ７。若处于状态口７（￡ｉ）时，Ｐ７不可实现，或ｅ７实现时），（￡。）也同时实现则Ｍ为等价变异体。（２）触发事件删除。通过删除Ｄ中跃迁￡ｉ∈Ｔ的触发事件口。产生变异体Ｍ，分为两种情况：①），７（￡ｉ）＝９或ｙ（￡ｉ）一ｙ７（玉）＾幻，该操作弱化了￡ｉ被触发的约束，与增加触发事件变异情况②类似，需要首先进行冲突检查。当不存在冲突时，可生成覆盖状态口７（岛）且不包含％的测试用例，用以杀死变异体。若在状态口７（￡。）下，事件％总是可实现的，则Ｍ为等价变异体。②ｙ（岛）一ｙ７（￡。）Ｖ％，该操作增强了幺被触发的约束。可执行覆盖口７（￡ｉ）且仅包含被删除事件％且满足ｐ７（岛）的测试用例杀死Ｍ。若在状态口７（ｆｉ）下，幻不可实现，则Ｍ为等价变异体。（３）触发事件变更。通过改变Ｄ中跃迁￡ｉ∈Ｔ的一个或全部触发事件产生变异体Ｍ，此时Ｍ中万方数据１５３￡；被触发的约束发生变化，分为四种情况：①用事件Ｐ７睡ｙ（￡；）替换￡。触发事件ｙ（￡；）。首先进行冲突检查，当不存在跃迁冲突时，使用覆盖口７（岛）、满足Ｐ７与Ｊ０７（￡ｉ）的测试用例，可杀掉变异体Ｍ。②若ｙ（￡ｉ）可表示成ｙ（￡。）一ｅ。＾Ｐ：，则ｙ７（岛）＝Ｐ。ＶＰ。，相当于弱化了￡：被触发的约束，因此需要检查变异后是否存在冲突。当不存在冲突时，使用覆盖口７（岛）、仅包含事件Ｐ。（或Ｐ。）且满足ｐ’（￡。）的测试用例在Ｍ与Ｄ中执行会产生相异的结果，因而可以用其杀死Ｍ。若在口７（岛）下，ｇ。与ｅ。总是同时出现，则Ｍ为等价变异。③若），（以）可表示成ｙ（￡ｉ）＝ｅ。ＶＰｚ，则ｙ７（￡；）＝ｅ，＾啦，相当于增强了ｆｉ被触发的约束。使用与情况②相同的测试用例可以杀掉Ｍ。若在口７（￡。）下，Ｐ。与ｅ：总是同时出现，则Ｍ为等价变异。④若存在跃迁￡后Ｔ使得ａ（￡。）一ａ（￡』）且岛≠￡，，则通过交换￡ｉ与￡ｊ的触发事件产生变异体Ｍ，即ｙ７（屯）一ｙ（￡』），ｙ７Ｑｆ）一ｙ（￡。）。在此情况下，使用覆盖ａ７（￡，）且满足ｙ７（￡ｉ）与』Ｄ７（￡ｉ）（或ｙ７（￡ｆ）与ｌＤ７（￡ｉ））的用例可杀掉Ｍ。３．５监护条件变异通过增加、删除或变更Ｄ中某跃迁的监护条件产生变异体Ｍ，主要包含以下变异算子：（１）监护条件增加。通过为Ｄ中跃迁￡。∈Ｔ增加监护条件ｒ７产生变异体Ｍ，分为两种情况：①ｐ７（￡；）一』Ｄ（￡。）＾ｒ７，该变异操作增强了￡。被触发的条件约束，使得￡ｉ有可能无法在满足原有条件的情况下被触发，此时原本可触发￡；的测试用例无法在变异体上正确执行，从而可以杀死该变异体。若在状态ａ７（￡ｉ）下，ｐ（￡；）可满足时ｒ，也可同时满足，则该变异体为等价变异体。②ｐ，（￡；）＝』Ｄ（￡ｉ）Ｖｒ７，该变异操作弱化了￡；被触发的条件约束，因此需要检查是否引入冲突。无冲突时，可通过增加测试用例来杀死Ｍ。新增用例需覆盖状态ａ７（￡ｉ），满足ｙ７（岛）及／，但不满足ｐ（岛）。若在状态ａ７（岛）下，ｒ，不可满足，或者ｒ，可满足时ｐ（￡ｉ）也可同时满足，则该变异体为等价变异体。（２）监护条件删除。通过删除Ｄ中跃迁￡；∈Ｔ的监护条件ｒａ产生变异体Ｍ，分为两种情况：①ＩＤ７（￡；）一彩或ＩＤ（￡ｉ）一ＪＤ７（￡。）＾“，该操作使得触发￡ｉ的条件约束被弱化。需要进行冲突检１５４查，当不存在冲突时，生成覆盖状态ａ７（ｆｉ）且仅满足』Ｄ７（￡；）与７７（￡；）的测试用例，用以杀死变异体。若在状态口７（￡ｉ）下，ｎ总是可满足的，则Ｍ为等价变异体。②ｌＤ（￡。）一ＪＤ７（￡ｉ）Ｖ“，该操作使得触发￡ｉ的条件约束被增强。此时，覆盖状态ａ７（ｆｉ）且仅满足“与ｙ７（￡。）的测试用例可杀死Ｍ。若在状态口７（￡，）下；“总不可满足，则Ｍ为等价变异体。（３）监护条件变更。通过改变Ｄ中跃迁ｆｉ∈Ｔ的监护条件ｐ（￡，），使得￡ｉ被触发的条件约束发生变化，从而产生变异体Ｍ，分为以下情况：①用ｒ７监护条件｜０（￡，）。首先进行冲突检查，当不存在跃迁冲突时，可以使用覆盖状态口７（￡。）、满足ｒ７与ｙ７（￡：）的测试用例杀掉Ｍ。若ｒ，八．０（岛）恒成立，则Ｍ为等价变异体。②若ＩＤ（￡ｉ）可表示成ＪＤ（￡。）一ｎ八ｒ２，则ｌＤ７（￡：）一ｒ。Ｖｒ。，此时触发￡；的约束被弱化，需要进行冲突检测。当无跃迁冲突时，使用覆盖口（￡，）且仅满足ｒ－与ｙ（￡：）（或者ｒ：与ｙ（￡ｉ））的测试用例可以杀掉Ｍ。若在口（￡。）下，ｒ。与ｒ。总是同时成立，则Ｍ为等价变异体。③若』Ｄ（￡ｉ）可表示成ｌＤ（￡。）一ｒ，Ｖｒ２，则ＪＤ７（￡。）一ｒ。＾ｒ。，此时触发￡ｉ的约束被增强，使用与情况②相同的测试用例可以杀掉Ｍ。若在口（￡。）下，ｒ，与ｒ。总是同时成立，则Ｍ为等价变异体。④若存在跃迁￡７∈Ｔ使得口（￡：）一ａ（￡，）且￡ｉ≠‘ｆ，则交换￡。与￡，的监护条件，即１０７（￡ｉ）一ＩＤ（￡ｉ），ｌＤ７０ｉ）一ｌＤ（￡ｉ）。此时，使用覆盖口７（岛）且满足ｌＤ７（￡ｉ）与ｙ７（￡；）（或ＪＤ７（￡，）与７／（ｆ，））的用例可杀掉Ｍ。３．６动作变异通过增加、删除或变更Ｄ中某跃迁的动作产生变异体Ｍ，主要包含以下变异算子：（１）动作增加。通过为Ｄ中跃迁￡ｉ∈Ｔ增加动作口７产生变异体Ｍ，其中艿７（￡ｉ）一艿（岛）Ｕ｛口７）。（２）动作删除。通过删除Ｄ中跃迁￡；∈Ｔ的动作ｎ。∈艿（￡。）产生变异体Ｍ，其中艿７（ｆｉ）＝艿（幺）一｛口ｄ）。（３）动作变更。通过用动作口。∈艿（￡。）替换Ｄ中跃迁￡；∈Ｔ的动作口。∈ｄ（￡ｉ）产生变异体Ｍ，其中艿７（友）一艿（￡。）一（ｎ。）Ｕ｛口。）。上述三种变异均使得对象在触发跃迁￡ｉ后采取的动作发生变化，因此用可以触发跃迁￡ｉ的测试用例来揭示Ｄ与Ｍ的差异，进而杀死Ｍ。万方数据计算机工程与科学２０１２，３４（２）３．７变异算子分析基于上述针对变异算子的分析，可生成如表１所示的分析表。其中“变异算子”分为“变异类型”、“子类型”以及“实际描述”三项内容进行描述；“冲突检查”表示执行相应变异算子后是否需要进行跃迁冲突检查；“等价变异”表示是否会在特定情况下生成等价变异体。对于如跃迁删除等变异算子产生的变异体，能够杀掉这些变异体的测试用例只需能够触发相应的跃迁或覆盖相应的状态，而当测试用例集符合基本测试覆盖准则时，如跃迁覆盖或状态覆盖等，即可包含上述测试用例。也就是说，如果已有测试用例集无法杀掉这些变异体，则表明其不满足相应的测试覆盖准则。因此，可以应用这些变异体评估已有测试用例集是否满足特定准则。在表１中用“覆盖准则评估”来表示相应的变异算子是否具有评估能力。此外，即便已有测试用例集满足相应测试覆盖准则，仍无法杀掉部分变异算子产生的变异体，例如跃迁增加、状态增加等算子。此时，需要生成新的测试用例。也就是说，这些变异算子不考察已有测试用例集是否符合特定的覆盖准则，而是可通过新增测试用例来提升测试用例集的检错能力。因此，在表１中用“提升检错能力”体现变异算子的特点。通过对表１的分析，可得到以下结论：（１）除了“状态增加”中“增加状态ｓ７为初始状态”变异算子外，其他变异算子按照“覆盖准则评估”与“提升检错能力”的值可分为两类。因此，可以依据变异测试的目的，来选择合适的变异算子。（２）“增加状态ｓ７为初始状态”算子由于肯定会引入跃迁冲突，而无法继续变异，因此在实际变异测试中无需选择该变异算子。若增加状态ｓ７为终止状态或其他状态时，会同时增加以其为目标状态的一条跃迁￡７，此时若使得Ｄ与Ｍ都进入￡７的源状态，且能够触发￡７，则Ｄ没有相应的跃迁可执行，而Ｍ可以触发跃迁￡７进入其他状态，从而可以杀死Ｍ。这与对￡７源状态执行增加跃迁变异算子的效果相同。因此，在执行过跃迁变异操作后，无需选择增加状态变异操作。（３）由于在状态删除变异中，可将删除状态ｓｉ的操作看作是删除状态口７（，）的跃迁，的过程，其中∥（∥）一‰因此，当已有变异体中包含了删除状态口７（，）的跃迁，的变异体时，不再需要执行删除状态ｓ。变异。米磊等：一种基于ＵＭＬ状态图的规约变异测试方法表１变异算子冲突检查变异类型子类型跃迁增加跃迁删除１５５变异算子情况分析表覆盖准则提升检错能力√×××××实际描述增加一个跃迁￡７删除跃迁ｆ，∈Ｔ改变ｆ。的源状态ａ（￡，）√×评估×等价变异√×√√√√×跃迁变异跃迁变更√×√×××改变￡。的目的状态口（“）交换跃迁￡：的口（ｆ，）与口（“）增加状态ｓ７为初始状态状态增加状态变异状态删除状态变更增加状态ｓ７为终止状态增加状态ｓ’为其他状态删除状态＆∈Ｓ变更状态矗∈Ｓｑ×√叫×××××√√×××√√××√√√××７，（￡。）一ｙ（￡；）＾ｅ７触发事件增加（ｅ７）ｙ７（ｆ。）一ｙ（ｆｉ）ＶＰ７√√√√×√√×ｑ√××ｙ７（“）一ｐ或ｙ（“）＝７７（ｆ。）＾％触发事件删除（ｅａ）ｙ（￡。）一ｙ７（￡；）Ｖ幻√√√一触发事件变异用事件ｅ’仨ｙ（“）替换７（ｆ，）若ｙ（￡。）一Ｐ１＾Ｐ２，则７／（￡。）一Ｐ１触发事件变更ＶＰ２■√×××ｑ√××√√×若ｙ（ｆ。）一ＰｌＶ８２，则ｙ７（￡，）一Ｐ１＾Ｐ２交换同源跃迁￡。与￡，的触发事件Ｐ７（ｏ＝Ｐ（“）＾ｒ，监护条件增加（ｒ，）Ｐ７（￡，）一Ｐ（ｆ：）Ｖ√√××√√—ｑ√√√××××ｒ，ｑ一×√ｑ××××××××监护条件删除（“）监护条件变异Ｐ，（ｆｆ）一ｐ或Ｐ（ｆ。）一Ｐ７（ｆ；）＾“Ｐ（ｆ，）一Ｐ，（☆）Ｖ“用ｒ，替换ｐ（￡。）若Ｐ（以）一ｒｌ＾ｎ，则Ｐ７（￡。）一ｒ１Ｖｒｚ√ｑ√√√、Ｊｏ√√√×××××监护条件变更若Ｐ（￡。）一ｎＶｒ２，则一（￡。）一ｒｌ＾ｒ２交换同源跃迁岛与‘ｊ的监护条件动作增加增加动作ｎ７动作变异动作删除删除动作。ｄ动作变更用动作ｎ。硭８（“）替换（４）在动作变异中，如果测试用例覆盖变异跃迁即可杀掉该变异体，而这些测试用例可能与在跃迁变异、触发事件变异或监护条件变异等变异中应用的测试用例重复，所以若某跃迁执行了跃迁变异、触发事件变异或监护条件变异等操作，可不再执行动作变异，因为在此种情况下，后者不再能够提升已有测试用例集的质量。（５）若在执行已有测试用例集后，仍有非等价变异体存活，则需要生成杀死这些变异体的测试用例。在状态变更变异中，测试用例能执行到变异的状态即可杀死相应的变异体，除此之外测试用例需要能执行到变异跃迁的源状态且能够触发变异跃迁。因此，执行到特定状态是这些用例均需满足的条件，而存在较大差异是触发跃迁的条件，为了便于指导后续测试用例的生成，可生成如表２所示的触发跃迁条件表。可以在需要时，依据变异算子的类型选择相应的条件，用于生成所需的测试用例。４实验分析实验设置为分析本文提出的变异测试方法的效果，本节４．１选择实际测试工作中某指控系统的三个子系统作为实验对象。表３给出了三个子系统的相关信息，万方数据１５６计算机工程与科学２０１２，３４（２）表２触发跃迁条件表变异算子触发跃迁条件变异类型子类型实际描述增加一个跃迁ｆ７跃迁增加跃迁删除跃迁变异跃迁变更７，（ｆ７）＾ｐ７（ｆ７）删除跃迁“∈Ｔ改变ｆｉ的源状态口（岛）改变如的目的状态口（ｆ。）７，（如）＾／（“）７，（☆）＾／（“）／（“）＾／（“）ｙ’（ｆ。）＾口７（“）交换跃迁ｆ；的口（ｆｉ）与口（☆）状态变异状态变更变更状态以∈Ｓ／（ｆ；）一ｙ（ｆ，）＾Ｐ７ｙ（￡ｆ）＾ｐ（“）触发事件增加（ｅ７）ｙ７（以）一ｙ（￡。）ＶＰ’Ｐ’＾ｐ７（￡；）ｙ７（￡。）一口或ｙ（如）一ｙ７（“）＾ｅｄ触发事件删除（％）ｙ（“）一ｙ７（☆）Ｖ％％＾口７（￡。）／（如）＾／（“）触发事件变异用事件Ｐ７硅ｙ（“）替换’，（￡ｆ）若ｙ（￡ｆ）＝ｇｌ＾即，则ｙ７（“）一Ｐ１ＶＰ２Ｆ７＾７／（“）＾∥（以）触发事件变更若），（如）一ＰｌＶＰ２，则ｙ７（￡。）一Ｐ１＾眈（ｅ１＾Ｐ，（“））Ｖ（Ｐ２＾Ｐ７（￡，））（Ｐ１＾Ｐ７（“））Ｖ（ｅ２＾Ｐ，（如））（ｙ７（￡：）＾Ｐ７（如））Ｖ（７，（ｏ）＾／（巧））ｙ（ｆ。）＾ｐ（ｆ；）交换同源跃迁“与￡，的触发事件Ｐ，（“）一Ｐ（“）＾ｒ，监护条件增加（ｒ７）一（赴）一Ｐ（☆）Ｖｒ，ｙ７（“）＾ｒ，ｙ７（“）＾ｐ７（“）＾一心ｙ７（ｆ；）＾“监护条件删除（“）监护条件变异Ｐ，（ｆ，）一Ｄ或ＩＤ（￡ｆ）一Ｐ７（￡ｆ）＾心Ｐ（“）一／（ｆ。）Ｖ“用ｒ，替换ｐ（“）若Ｐ（“）一ｎ＾ｒ２，则Ｐ７（ｆ。）一ｎＶｒ２ｙ７（‘ｆ）＾ｒ，（７ｌ＾ｙ（如））Ｖ（’２＾ｙ（“））（’ｌ＾ｙ（如））Ｖ（７２＾ｙ（如））（ｙ７（“）＾Ｐ７（“））Ｖ（ｙ７（￡，）＾Ｐ７（０））监护条件变更若ＪＤ（☆）＝ｒｌＶｒ２，则Ｐ７（￡；）＝，１＾ｒ２交换同源跃迁￡。与￡ｉ的监护条件包括系统名称、状态图中状态数与跃迁数以及简要的功能描述。对于每一个待测子系统的状态图，依据状态覆盖与跃迁覆盖准则，生成测试用例，其数量如表４所示。表３待测子系统信息加算子会产生原状态图未包含的状态或跃迁，而基于覆盖准则生成的测试用例无法检测新增的状态或跃迁，肯定无法杀死这些变异体。为避免上述变异体对实验结果的影响，本实验未选择这两种变异算子。表５应用的变异算子及其生成变异体数量表４覆盖准则及其测试用例数量选择跃迁删除、触发事件增加、删除与变更、监护条件增加、删除与变更等７种变异算子，产生相应的变异体，在移除非法或等价变异体后，相应变异体的数量如表５所示。由于跃迁增加与状态增４．２结果分析在变异体中执行测试用例，当变异体产生的行为与原状态图不一致时，则认定变异体被杀，表明万方数据米磊等：一种基于ＵＭＬ状态图的规约变异测试方法测试用例能够揭示被杀变异体所模拟的错误。统计被杀变异体数量，可生成如表６所示的结果。表６不同覆盖准则下杀死变异体的数量依据变异算子类型，统计被杀变异体数量占该类型变异体总数的百分比，可得到如图１所示的实验结果。ａ通信子系统实验结果ｂ存储管理子系统实验结果１００．００％８０．００％６０．００％一蒜渊零４０．Ｏｄ％２０．ＯＯ％Ｏ．００％ｃ操控子系统实验结果图１实验结果通过分析上述实验结果可发现：（１）本文在３．７小节分析变异算子时指出，跃迁删除变异算子可以用于检测已有测试用例集是否满足跃迁覆盖准则，即满足该准则的测试用例集可以杀死跃迁删除变异体。实验结果显示，满足跃万方数据１５７迁覆盖准则的测试用例集杀死了全部的跃迁删除变异体，与预期一致。（２）除上一种情况外，其他变异算子产生的变异体均有一定数量的存活，占相应类型变异体总数的２０％至７５％。这表明已有测试用例集无法检测出存活变异体对应的错误，需要补充新的测试用例，提高其检测错误的能力。而这一实际需求可以通过针对存活变异体生成测试用例的方式实现。这表明本文提出的变异测试方法能够较好地模拟潜在错误并提高测试用例的质量。综上所述，本文提出的变异测试方法在评估与提高测试用例质量方面具有较好的效果，能够保证和提高测试用例检测错误的能力，进而提升测试的效率。５结束语为了提高ＵＭＬ状态图变异测试的可操作性和测试效率，本文给出了较系统的变异算子的定义。针对每种变异算子，分析其是否会引入冲突，并给出产生等价变异体的条件，从而减少不合理的变异过程，而且能够在应用变异算子生成变异体的同时进行等价变异体检测，可以在测试早期识别等价变异体，降低其对测试过程的影响，进而提高了变异测试的效率。此外，本文给出了杀掉每种变异体所需满足的条件，可以用于指导生成杀掉特定变异体所需的测试用例，从而提高测试用例集的质量。最后通过实验说明了本方法的可行性与有效性。本文提出的变异测试方法未考虑状态图嵌套中的变异操作的分析。在今后的工作中，将进一步研究复杂状态图的变异操作，使其可以应用于较高层级的测试中。参考文献：［１］ＪｉａＹ，ＨａｍａｎＭｃｏｎｓｔｒｕｃｔ堍ＳｕｂｔｌｅＦａｕｌｔｓｕｓ崦Ｈｉｇｈｅｒ０ｒ—ｄｅｒＭｕｔａｔｉｏｎｎｓｔｉｎｇ［Ｃ］∥Ｐｒｏｃｏｆｔｈｅ８ｔｈＩｎｔ’１ｗｏ出ｎｇｃｏｎｆ０ｎＳ０ｕｒｃｅＣ０ｄｅＡｎａｌｙｓｉｓａｎｄＭ越ｐｕｌａｔｉｏｎ，２００８：２４９—２５８．［２］Ｂ１ａｃｋＰＥ，０ｋｕｎＶ，ＹｅｓｈａＹ．ＭｕｔａｔｉｏｎＯｐｅｒａｔｏｒｓｆｏｒｓｐｅｃｉ—ｆｉｃａｔｉｏｎｓ［ｃ］∥Ｐｒｏｃｏｆｔｈｅ５ｔｈＩＥＥＥＩｎｔ’１ｃｏｎｆｏｎＡｕｔｏｍａｔｅｄＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇ，２０００：８１—８８．［３］章涛，顾庆，陈道蓄．基于ｕＭＬ状态图的测试技术研究［Ｊ］．计算机科学，２００７，３４（１０）：２６４—２６７．［４］ｓｃｈｕｌｅｒＤ，ｚｅｌｌｅｒＡ．（ｕｎ一）ｃｏｖｅｒｉｎｇＥｑｕｉｖａｌｅｎｔＭｕｔａｎｔｓ［ｃ］∥Ｐｒｏｃｏｆｔｈｅ３ｒｄＩｎｔ’ｌｃｏｎｆｏｎＳ０ｆｔｗａｒｅＴｅｓｔｉｎｇ，ｖｅｒｉｆｉｃａ—ｔｉｏｎａｎｄＶａｌｉｄａｔｉｏｎ，２０１０：４５—５４．［５］０ｋｕｎＶ．ｓｐｅｃｉｆｉｃａｔｉｏｎＭｕｔａｔｉｏｎｆｏｒＴｅｓｔＧｅｎｅｒａｔｉｏｎａｎｄＡ—ｎａｌｙｓｉｓ：［ＰｈＤＴｈｅｓｉｓ］［Ｄ］．ｕｎｉｖｅｒｓｉｔｙｏｆＭａｒｙＩａｎｄＢａｌｔｉｍｏｒｅ１５８Ｃ０ｕｎｔｙ，２００４．［６］ＦａｂｂｆｉＰＦ，ＭａＩｄｏｎａｄｏｓｃ，ｓ“ｇｅｔａＪｃ．ｅｔａ１．ＭｕｔａｔｉｏｎＴｅｓｔｉｎｇＡｐ州ｅｄｔｏＶａｌｉｄａｔｅｓｐｅｃｌｆｌｃａｔｉｏｎｓＢａｓｅｄｏｎｓｔａｔｅｃｈ—ａｒｔｓ［ｃ］∥Ｐｒｏｃｏｆｔｈｅ１ｏｔｈＩｎｔ’ｌｓｙｍｐｏｎＳｏｆｔｗａｒｅＲｅｌｌａｂｉｌｉ‘ｙＥｎｇｌｎｅｅｒｉｎｇ，１９９９：２１０—２１９．［７］Ｉ，ｉＪ—Ｈ，Ｄａｉｏｘ．Ｉ．ｉＨ—ＨＭｕｔａｔｌｏｎＡｎ８ｌｙｓｉｓｆｏｒＴｅｓｔｉｎｇＦｌ—ｎｉｔｅｓｔａｔｅＭａｃｈｉｎｅｓ［ｃ］∥ＰｒｏｃｏｆｓｅｃｏｎｄＩｎｔ’ｌｓｙｍｐｏｎＥｌｅｃ—ｔｒｏｎｌｃＣｏｍｍｅｆｃｅａｎｄＳｅｃｕｒｉｔｙ，２００９：６２０—６２４．［８］Ｔｒａｋｈｔｅｎｂ巾ｔＭ．ＮｅｗＭｕｔａｔｉｏｎｓｆｏｒＥｖａｌｕａｔｌｏｎｏｆｔｌ…ｎｄｓｐｅｃｉｆｉ∞一ｌｍｐｌｅｍｅｎｔａｔｉｏｎＬｅｖｅｌｓｏｆＡｄ。ｑｕａｃｙｍＴｅｓｔｉｎｇｏｆｓｔａｔｅｃｈａｒｔｓＭｏｄｅＩｓ［ｃ］∥ＰｒｏｃｏｆｔｈｅＴｅｓｔｊｎｇ：ＡｃａｄｅｍｉｃａｎｄＩｎｄｕｓｔｒｉａｌＣｏｎｆｅｒｅｎｃｅＰｒａｃｔｉｃｅａｎｄＲｅｓｅａｒｃｈＴｅｃｈｎＩａｕｅｓ－ＭＵ—ＴＡＴＩｏＮ，２００７：１５１—１６０．［９］ＨｉｅｒｏｎｓＲＭ，ＭｅｒａｙｏＭＧ．ＭｕｔａｔｉｏｎＴｅｓｔＩｎｇｆｒｏｍＰｒｏｂａｂｉ—ｌｌｓｔｉｃａｎｄｓｔｏｃｈａｓｔｌｃＦｉｎｌｔｅｓｔａｔｅＭａｃｈｌｎｅｓ［Ｊ］．ｊｏｕｒｎａｌｏｆＳｙｓｔｅｍｓａｎｄＳ０ｆｔｗａｒｅ，２００９，８２（１１）：１８０４一１８１８［１０］ＢｅｕｌＦ，ＢｅｙａｚｌｔＭ．ＡＦｏｒｍａＩＦｒａｍｅｗｏｒｋｆｏｒＭｕｔａｔｌｏｎＴｅｓｔｉ“ｇ［ｃ］∥Ｐｒｏｃｏｆｔｈｅ４ｔｈＩＥＥＥＩｎｔ’ｌｃｏｎｆｏｎｓｅｃｕｒｅＳｏｆｔｗａｒｅＩｎｔｅｇｒａｔＩ…ｎｄＲｅｌｉａｂｉｌｉｔｙｌｍｐｒｏｖｅｍｅｎｔ，２０１０：１２ｌ—１３０．万方数据计算机工程与科学２０１２，３４（２）［１１］ＧｒｕｎＢＪＭ．ｓｃｈｕｌｅｒＤ．ｚｅｌｌｅｒＡ．ＴｈｅＩｍ呻ｃｔｏｆＥｑｕｉｖａｌｅｎｔＭｕｔａｎｔｓ［ｃ］∥Ｐ巾ｃｏｆｔｈｅ４ｔｈＩｎｔ’１ｗｏｒｋｓｈｏｐｏｎＭｕｔａｔｌｏｎＡｎａｌｙｓｌｓ，２００９：１９２１９９．米磊（１９８１一）。男，吉林白城人，博士生，讲师，研究方向为软件测试和故障诊断。Ｅ－ｍｉｌ＝ｍｉｌｅｉｌ９８１＠１２６．ｃｏｍＭｌＩ矗，ｂｏ…ｎ１９８１．ＰｈＤｃａｎｄｉｄａｔｅ．１ｅｃｔｕｒｅｒ．ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｓｏｆｔ—１１ｄｆａｕｌｔｄｉａｚｎｏｓｉｓ．贲可荣（１９６３一），男，江苏海安人，博士，教授，ｃｃＦ会员（Ｅ２００００６６１０Ｓ），研究方向为软件工程和人工智能等。Ｅ．ｍａｉｌＢｅｎｋｅｒｏｎ９０８＠２１ｃｎ．ｃｏｍＢＥＮＫｅ＿ｍ雌．ｂｏｒｎｉｎ１９６３，ＰｈＤ，ｐｒｏ—ｆｅｓｓｏｒ＇ｃｃＦｍｅｍｂｅｒ（Ｅ２００００６６１０Ｓ），ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｓｏｆｔｗ８ｒｅｅｎｇｉｎｅｅｒｉｎｇ，ａｎｄａｒｔｉｆｉｃｉａｌｉｎｔｅｌｌｉｇｅｎｃｅ．