基于蕴含关系的场景测试法路径优化方法研究

摘 要： 针对场景测试法中多场景切换代价优化问题，在复合状态分析、逻辑蕴含概念基础上，从测试场景结构分解的角度，给出状态蕴含和场景蕴含关系的定义及推论，由场景蕴含形成场景蕴含图SIG，然后采用图论方法求解优化路径。给出系统化处理方法，并与其他方法比较。最后实例验证该方法的有效性。

关键字： 场景测试法； 蕴含关系； 路径优化； 场景蕴含图； 状态蕴含

0 引 言

场景测试法[1]（Scenario Test）也称为用例测试法（Use Case Test），是一种软件黑盒测试方法，广泛用于复杂交互式软件测试，尤其适用于嵌入式软件的分布式测试。分布式测试中人员、设备和测试对象都具有特定的地理分布要求，导致测试场景的构建和撤销代价较大。如何通过减少场景数量、避免重建场景、优化场景切换路径来减少代价，提高测试效率，已成为一个重要且亟待解决的问题。场景测试法依据测试需求形成多个不同测试场景。测试实施中先建立场景、执行测试用例、撤销场景，再建下一个场景，如此循环直到完成所有场景。对于多场景执行次序目前缺乏科学有效的定义和方法指导。多场景执行次序如果选择不当，将导致重复建设和浪费。当测试失败时往往需要重建多个场景后重测，代价更大。

Jacobson在文献[2?3]中提出用例驱动的软件工程思想，在此基础上IBM Rational公司在RUP2000中提出场景测试法。该方法未说明多场景执行的次序。文献[4]采用用例行为矩阵度量场景的优先级，通过该优先级对多个场景进行排序和路径合并，从而减少测试代价。文献[5]先依据用例事件流建立事件有向树，然后对该树进行路径搜索，最后合并子路径，提高场景重用率。文献[6]依据业务流选择部分场景优先测试，减少测试代价的同时保证功能可用性。以上研究大多侧重于测试场景的行为特征，而忽视场景结构特性。本文通过研究测试场景结构、复合状态分析、逻辑蕴含概念，通过状态蕴含和场景蕴含关系，探索一种新思路来减少多场景切换代价。

1 测试场景的构成与场景蕴含

首先分析场景简单切换的问题，给出状态蕴含和场景蕴含的关系。

1.1 测试场景的简单切换

在一般场景测试法中，测试一个场景s1前构建该场景，测试完成后需撤销该场景。场景切换就是撤销前一个场景并构建下一个场景的过程，如图1所示。

简单切换的好处是可在任意两个场景之间进行切换，缺点是代价高。

将场景作为结点，简单切换作为有向边，切换代价作为边权值，就可形成一个赋权有向图，而且该图是有向完全图。基于该图选择任何路径都无法得到优化，原因是简单切换边不能表示场景之间内在的蕴含关系。

定义1：测试场景。一个测试场景s是针对一个或几个用例的测试需求，由一组语境对象组成的执行环境，这些对象具有特定的类型、个体及其状态的要求。场景s的语境对象的集合记为c（s）。

图2表示测试场景中的语境对象的性质。

图2 测试场景的构成

图2中一个测试场景包含一个或多个语境对象，而且每个语境对象都具有类型、个体及其状态的限定。语境对象按类别可划分为：测试人员、测试设备、测试对象。其中，测试对象可能是一套受测软件，或者一组构件，或者一组对象，或者单个对象（最简单场景）。

由定义1可知，两个测试场景之间的差别就是其语境对象之间的差别，即对象类型、对象个体及其状态的差别。下面分析对象状态之间关系及其对测试用例（test case，下称测例）执行的作用机制。

直观理解，若较简单场景测试失败，则较复杂场景也失败。

由推论3可能将两个测试场景合并为一个，能同时满足多个测例需求，减少测试场景数量，也就减少测试代价。

1.3 场景蕴含关系

直观理解，两个场景之间的蕴含关系有4种情形：

（1） 相互蕴含；

（2） 后场s2加入新对象；

（3） 后场s2中一个或多个语境对象转入其子状态，往往添加属性值或关联；

（4） 情形（2）、（3）并存。

推论4：场景蕴涵关系是一种偏序关系。

证明：

（1） 自反。对于任一个场景s1，s1蕴含s1，即s1→s1成立，证明略。

2 路径优化方法

场景蕴含图中有向边表示两个场景之间的逆蕴含关系，直观理解为从较简单场景指向较复杂场景，但图中取消了自反所导致的自回路。

推论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的系统化处理方法如下：

方案2：在图中添加第2.1节讨论的简单切换边，每条边添加边权值，边权值表示切换代价，蕴含边的权值是新建对象和转入子状态操作的代价，形成一个赋权有向图，再求解货郎担问题，即遍历所有场景一次且仅一次，而且路径边权之和最小。

情形2，连通。求最长路径P，然后在图G中去掉P中结点和边，剩下子图若连通则继续求最长路径，若不连通则按情形1的子图分割处理。

与其他相关方法进行比较见表1。

4 实例验证

将该方法应用于一个软件测试实例，被测功能是开发人员持续上传新版本移动应用程序，使移动用户能持续更新版本。

功能需求：对于一个移动应用程序，服务器仅保留最新版本，包括一个apk文件，一个xml文件记录当前版本号以及版本说明。apk的版本号应与xml中版本号一致。开发人员上传新版本时，应在页面上输入新版本号及版本说明，然后上传apk文件。页面输入信息将记录到xml文件中。

根据以上功能需求可识别该测试的基本流与备选流，描述如表2所示。

先确定权值量化规则如下：

（1） 添加或修改一个页面属性权值为1；

（2） 打包apk权值为5；

（3） 设置网络权值为3。

然后构建赋权有向图，如图4所示。

5 结 语

本文从测试场景的结构特征的角度，定义了场景蕴含关系，基于蕴含关系提出一种多场景测试路径优化方法，并给出针对场景蕴含图SIG的系统化解决方法。该方法适用于多场景测试，尤其是场景切换代价较大的嵌入式分布式系统测试。

参考文献

[8] 方世昌.离散数学[M].北京：高等教育出版社，2000.