严悍，许昌年，朱文，丁锋，王宇
（南京理工大学计算机科学与工程学院，江苏南京210094）
摘要：针对场景测试法中多场景切换代价优化问题，在复合状态分析、逻辑蕴含概念基础上，从测试场景结构分解的角度，给出状态蕴含和场景蕴含关系的定义及推论，由场景蕴含形成场景蕴含图SIG，然后采用图论方法求解优化路径。给出系统化处理方法，并与其他方法比较。最后实例验证该方法的有效性。
关键字：场景测试法；蕴含关系；路径优化；场景蕴含图；状态蕴含
中图分类号：TN911-34；TP311 文献标识码：A 文章编号：1004-373X（2015）12-0118-05
收稿日期：2014-12-12
基金项目：国家自然科学基金（61300053）
0 引言
场景测试法[1]（Scenario Test）也称为用例测试法（Use Case Test），是一种软件黑盒测试方法，广泛用于复杂交互式软件测试，尤其适用于嵌入式软件的分布式测试。分布式测试中人员、设备和测试对象都具有特定的地理分布要求，导致测试场景的构建和撤销代价较大。如何通过减少场景数量、避免重建场景、优化场景切换路径来减少代价，提高测试效率，已成为一个重要且亟待解决的问题。场景测试法依据测试需求形成多个不同测试场景。测试实施中先建立场景、执行测试用例、撤销场景，再建下一个场景，如此循环直到完成所有场景。对于多场景执行次序目前缺乏科学有效的定义和方法指导。多场景执行次序如果选择不当，将导致重复建设和浪费。当测试失败时往往需要重建多个场景后重测，代价更大。
Jacobson在文献[2-3]中提出用例驱动的软件工程思想，在此基础上IBM Rational公司在RUP2000中提出场景测试法。该方法未说明多场景执行的次序。文献[4]采用用例行为矩阵度量场景的优先级，通过该优先级对多个场景进行排序和路径合并，从而减少测试代价。文献[5]先依据用例事件流建立事件有向树，然后对该树进行路径搜索，最后合并子路径，提高场景重用率。文献[6]依据业务流选择部分场景优先测试，减少测试代价的同时保证功能可用性。以上研究大多侧重于测试场景的行为特征，而忽视场景结构特性。本文通过研究测试场景结构、复合状态分析、逻辑蕴含概念，通过状态蕴含和场景蕴含关系，探索一种新思路来减少多场景切换代价。
1 测试场景的构成与场景蕴含
首先分析场景简单切换的问题，给出状态蕴含和场景蕴含的关系。
1.1 测试场景的简单切换
在一般场景测试法中，测试一个场景s1前构建该场景，测试完成后需撤销该场景。场景切换就是撤销前一个场景并构建下一个场景的过程，如图1所示。
图1中假设场景s1的构建代价为b1，撤销代价为d1，场景s2的构建代价为b2，撤销代价为d2，那么在由s1切换到s2时，切换代价可量化为d1+b2，由s2切换到s1时，代价为d2+b1。这种切换称为简单切换。这种切换可能导致重复构建/撤销。以s1切换到s2为例，如果s1中的部分对象在s2中也要使用，那么切换时就额外增加了撤销和重建的代价。
简单切换的好处是可在任意两个场景之间进行切换，缺点是代价高。
将场景作为结点，简单切换作为有向边，切换代价作为边权值，就可形成一个赋权有向图，而且该图是有向完全图。基于该图选择任何路径都无法得到优化，原因是简单切换边不能表示场景之间内在的蕴含关系。
1.2 场景和状态蕴含关系
定义1：测试场景。一个测试场景s 是针对一个或几个用例的测试需求，由一组语境对象组成的执行环境，这些对象具有特定的类型、个体及其状态的要求。场景s 的语境对象的集合记为c（s）。
图2表示测试场景中的语境对象的性质。
图2中一个测试场景包含一个或多个语境对象，而且每个语境对象都具有类型、个体及其状态的限定。语境对象按类别可划分为：测试人员、测试设备、测试对象。其中，测试对象可能是一套受测软件，或者一组构件，或者一组对象，或者单个对象（最简单场景）。
由定义1可知，两个测试场景之间的差别就是其语境对象之间的差别，即对象类型、对象个体及其状态的差别。下面分析对象状态之间关系及其对测试用例（test case，下称测例）执行的作用机制。
UML状态机定义了一个对象的2个状态s1s2之间可能具有子状态的复合关系。假设s1是s2的一个子状态，若处于s1态则必处于s2态，反之不然[7]。
定义2：状态蕴含。设一个语境对象有状态s1和s2，若s1 是s2 的一个子状态，则s1s2 有状态蕴含关系，记作s1→s2。
直观理解，若s1→s2，则s2态表示较简单场景，s1态较复杂且具有更多属性限制要求，即针对s1态测试的判定断言比针对s2更多。
推论1：一个测例tc对s1s2态分别测试，有s1→s2，若s2测试失败，则s1也失败，记为fai（l tc，s2）→fai（l tc，s1）。
直观理解，若较简单场景测试失败，则较复杂场景也失败。
证明，因s1→s2，s1验证需要比s2更多判定断言，且增加的断言（记为s1.newAssert）都以合取式出现。假设s2的断言为s2.assert，那么s1的断言式为s2.assert∧s1.newAs-sert。若s2测试失败，则s2.assert为假，此时s1的断言式也为假，故s1测试也失败，证毕。
该推论的逆否形式也成立，若s1测试成功，则s2也成功，记为success（tc，s1）→succss（tc，s2）。
推论2：一个测例tc在s1s2两个状态分别测试，且有s1→s2，则应先创建s2场景测试，再切换到s1场景测试。
这是推论1的一个简单延伸。先测试简单场景s2，后测试较复杂场景s1。若s2测试成功，再测试s1。若s2测试失败，由推论1知，s1也推定失败而无需再切换到更复杂场景，从而减少代价。该推论为多场景测试提供了优化依据：从较简单到复杂场景逐步测试，若测试成功则进入子状态来测试更复杂场景，而未撤销任何语境对象，直接减少代价；若测试失败则可立即断定从成功场景到失败场景的新加断言失败，范围小易分析原因，也减少测试代价。
推论3：设有两个不同测例tc1，tc2，若tc1需测试状态s1，tc2需测试状态s2，且有s1→s2，则只需状态s1就能满足tc1和tc2的测试要求。
实际上，tc2测试s1与测试s2具有相同的判定断言的结果。
证明：因tc2针对s2态测试，故tc2仅持有s2的判定断言s2.assert。而tc1 持有断言为s2.assert∧s1.newAssert。由推理1，success（tc2，s1）→succss（tc2，s2），即tc2 测试s1若成功，则测试s2也成功。若tc2测试s1失败，则其断言s2.assert判定为假，故此测试s2也失败。两者断言判定结果相同，证毕。
由推论3可能将两个测试场景合并为一个，能同时满足多个测例需求，减少测试场景数量，也就减少测试代价。
1.3 场景蕴含关系
定义3：场景差。设s1，s2是2个测试场景，场景差是从场景s1切换到s2的语境对象的差别，记为c（s2）-c（s1）。
定义4：场景蕴含。设s1 ，s2 是两个测试场景，c（s2）-c（s1）=M，若M= - ，或M 非空，且M 仅包含新建对象；或至少一个语境对象从场景s1到s2转换为其一个子状态，即有状态蕴涵；前两种情形兼有，则称场景s2蕴含s1，记为s2→s1。
若c（s1）-c（s2）= - ，表示2个场景具有相同的对象类别、数量和状态，此时2 个场景s1s2 互相蕴含，语义上表示从测试等价类角度看，这2个场景属于同一类。
直观理解，两个场景之间的蕴含关系有4种情形：
（1）相互蕴含；
（2）后场s2加入新对象；
（3）后场s2 中一个或多个语境对象转入其子状态，往往添加属性值或关联；
（4）情形（2）、（3）并存。
推论4：场景蕴涵关系是一种偏序关系。
证明：
（1）自反。对于任一个场景s1，s1蕴含s1，即s1→s1成立，证明略。
（2）反对称。对于任意2个不同场景s1和s2，若s1→s2，则s2→s1不成立。
证明：反证法，假设s1→s2 成立时，s2→s1 也成立，则由定义4 可得c（s2）-c（s1）=M，c（s1）-c（s2）=M，则c（s1）=c（s2），s1与s2是相同场景，与前提矛盾，证毕。
（3）传递性。对于任意3 个不同场景s1、s2 和s3，若s1→s2，s2→s3，则s1→s3。
证明：由定义4，可得c（s1）-c（s2）=M1，c（s2）-c（s3）=M2，两式相加，得c（s1）-c（s3）=M1+M2，M1+M2 满足定义4中M 的条件（子状态的复合关系有传递性），故s1→s3成立。
2 路径优化方法
定义5：场景蕴含图SIG（Scenario ImplicationGraph）。一个场景蕴含图G={V，E}是一个有向图，其中V 是场景集合，E 是有向边集合，若e=<s1，s2>∈E，当且仅当s2→s1且s1≠s2成立。
场景蕴含图中有向边表示两个场景之间的逆蕴含关系，直观理解为从较简单场景指向较复杂场景，但图中取消了自反所导致的自回路。
推论5：场景蕴含图不存在回路。
证明：由推论4，场景蕴含关系是一种偏序关系，在取消自回路的前提下，场景蕴含图是哈斯图，哈斯图无回路[8]。
推论6：一个场景蕴含图作为有向无环图，若存在一条哈密尔顿路径[8]（Hamilton Path，简称H路径），则该路径就是优化的场景切换路径。
证明：
（1） 由H 路径定义可知，覆盖所有场景一次且仅一次；
（2）H路径从简单场景到复杂场景，由推论2可知，沿该路径测试无论成功或失败，场景切换代价都可控制到最低。
一个场景蕴含图不一定存在H 路径。若不连通则不存在H 路径。即便连通也不一定存在H 路径。对于一个有向无环图，难以简单求解H 路径。文献[9]给出一种复杂的求解方法。
因此本文主张，对有向无环图先求其最长路径，尝试覆盖尽可能多的场景结点。若能覆盖所有结点则得到一条H路径；若不能覆盖，所得到的最长路径也可作为次优解。
推论7：场景蕴含图中存在入度为0 的场景结点。证明略。
选择入度为0的一个或多个场景作为起始结点，寻求最长路径，再判断处理。
如果图中只有一个入度为0的结点，则作为单源最长路径求解；如果有多个入度为0的结点，则分别作为源结点求最长路径，然后在多条路径中选择最长路径。
下面算法是对无环有向图求单源最长路径，采用广度优先搜索。然后找出最长路径。算法如下：
（1）根据广度优先算法标记每一个结点到源结点的距离并按距离的大小形成队列。具体过程略。
（2）从距离最大的结点开始按距离递减顺序搜索父结点，直至到源结点，形成路径。
输入：排序后的场景队列，按开始场景的距离降序排列；
输出：最长路径。
过程：path（R）
1. P ：= -
2. ENQUEUE（P，R.first）
3. d ：= R.first.d
4. for each vertex u in R
5. d ：= d-1
6. if u.d == d && u == P.last.super then
7. ENQUEUE（P，u）
8. end if
9. end for
10. return P
3 讨论与比较
对一个场景蕴含图G 的系统化处理方法如下：情形1，不连通。有2种方案可选：
方案1：子图分割，形成多个连通子图，再分别对各连通子图按情形2处理。
方案2：在图中添加第2.1节讨论的简单切换边，每条边添加边权值，边权值表示切换代价，蕴含边的权值是新建对象和转入子状态操作的代价，形成一个赋权有向图，再求解货郎担问题，即遍历所有场景一次且仅一次，而且路径边权之和最小。
情形2，连通。求最长路径P，然后在图G 中去掉P中结点和边，剩下子图若连通则继续求最长路径，若不连通则按情形1的子图分割处理。
与其他相关方法进行比较见表1。
4 实例验证
将该方法应用于一个软件测试实例，被测功能是开发人员持续上传新版本移动应用程序，使移动用户能持续更新版本。
功能需求：对于一个移动应用程序，服务器仅保留最新版本，包括一个apk文件，一个xml文件记录当前版本号以及版本说明。apk的版本号应与xml中版本号一致。开发人员上传新版本时，应在页面上输入新版本号及版本说明，然后上传apk文件。页面输入信息将记录到xml文件中。
根据以上功能需求可识别该测试的基本流与备选流，描述如表2所示。
将基本流和备选流组合形成9个测试场景，如表3所示。分析场景间蕴含关系，形成场景蕴含图，如图3所示。为展示清楚，省略一些间接蕴含关系。对图3计算最长路径：场景6→场景5→场景7→场景1→场景4→场景8→场景9。该路径未覆盖场景3和2。根据第3节讨论应构建赋权有向图。
先确定权值量化规则如下：
（1）添加或修改一个页面属性权值为1；
（2）打包apk权值为5；
（3）设置网络权值为3。
然后构建赋权有向图，如图4所示。
对图4 再计算路径：场景6→场景5→场景7→场景1→场景4→场景8→场景3→场景2→场景9，此路径边权和为37。若9个场景简单随机选择，经计算其平均边权和为106。此实例的优化率为(106 - 37) 106 =65%。采用文献[5]的优化率为44%。
5 结语
本文从测试场景的结构特征的角度，定义了场景蕴含关系，基于蕴含关系提出一种多场景测试路径优化方法，并给出针对场景蕴含图SIG的系统化解决方法。该方法适用于多场景测试，尤其是场景切换代价较大的嵌入式分布式系统测试。
作者简介：严悍(1967—)，男，山西运城人，博士，副教授。主要研究方向为信息安全与软件工程。
教育期刊网 http://www.jyqkw.com
参考文献
[1] 杜庆峰.高级软件测试技术[M].北京：清华大学出版社，2011.
[2] JACOBSON I. Object oriented software engineering：a use casedriven approach [M]. USA：ACM Press，1992.
[3] JACOBSON I. Basic use-case modeling [J]. The Road to theUnified Software Development Process，2000，18：167-172.
[4] KIM Y，CARLSON C R. Scenario based integration testing forobject-oriented software development [C]// Proceedings of 1999Eighth Asian Test Symposium. [S.l.]：IEEE，1999：283-288.
[5] 潘建勇，陈邦兴.基于场景的测试用例设计方法研究[J].通信技术，2012，44（12）：77-80.
[6] 刘春玲，雷海红.基于场景的信息系统黑盒测试方法[J].信息与电子工程，2012，10（4）：509-512.
[7] 刘佳，尹治本.基于对象状态的面向对象软件测试方法研究[J].电脑知识与技术，2008，4（35）：2169-2170.
[8] 方世昌.离散数学[M].北京：高等教育出版社，2000.
[9] ADLEMAN L M. Molecular computation of solutions to combi-natorial problems [J]. science-AAAS-Weekly Paper，1994，266（5187）：1021-1023.
