Page 112 - 《软件学报》2021年第9期

2736 Journal of Software 软件学报 Vol.32, No.9, September 2021

图的边表示测试用例之间的差异性.则测试用例搜索可以转化为对图的遍历问题.
定义 3. 测试用例搜索图 G=(N,E),其中:N 为节点集合,表征每个测试用例,每个节点包含 2 个属性,即测试用
例的标识和支持度;E 为边的集合,表征测试用例之间的关系,每条边有 1 个属性,即边两端所表征测试用例的差
异性量化值.
本文使用杰卡德距离 [25] 量化测试用例的差异性,具体做法为:获得测试用例 a 和 b 覆盖的服务,分别形成集
合 S a 和 S b ,计算两个集合的杰卡德距离 d j ,即:
| S ∪ S | | S− ∩ S |
(,S
dS ) = a b a b (2)
j a b | S ∪ S |
a b
基于定义 3 即可设计从测试用例集生成搜索图的算法,伪代码见表 4.该算法遍历所有测试用例,为测试用
例创建一个新节点添加到图中(第 1 行~第 3 行),支持度属性为公式(1)中的 c u ,并构造该节点与已有节点的边也
添加到图中(第 4 行~第 11 行),边的属性通过公式(2)计算获得.

Table 4 Searching graph generation algorithm
表 4 搜索图生成算法
算法. generateGraph(T,G).
参数:T,附带支持度信息的测试用例集(输入);G,搜索图(输出).
1 for each t∈T do
2 nn←Graph.create_node(t)
3 G.nodes.append(nn)
4 for each n∈G.nodes do
5 if n≠nn then
6 t n←n.get_testcase(⋅)
7 d←d j(t n,t)
8 e←Graph.create_edge(n,m,d)
9 G.edges.append(e)
10 end if
11 end for
12 end for
由于搜索测试用例的目标是使得测试用例的支持度较大且相互间差异也较大,故本文采用一种启发式算
法——贪心算法,来遍历搜索图,算法伪代码见表 5.
Table 5 Searching graph traversal algorithm
表 5 搜索图遍历算法
算法. searchGraph(G,f,T r).
参数:G,搜索图(输入);f,测试准则判定函数(输入);T r,测试用例缩减集(输出).
1 n s←G.find_max_c u(⋅)
2 while not G=∅ and not f(T r) do
3 v←0, n e←null
4 for each n∈G.nodes do
5 if n≠n s then
6 e←G.get_edge(n s,n)
7 vt←n.c u+e.d j
8 if v<vt then
9 v←vt, n e←n
10 end if
11 end if
12 end for
13 T r.append(n s)
14 G.remove_node_with_edges(n s)
15 n s←n e
16 end while

该算法从图中支持度最大的节点开始遍历(第 1 行、第 2 行),计算当前节点到每一个相连节点的转移值,
该值为相连节点的支持度与边上属性的和,进而查找转移值最大的第 1 个相连节点(第 4 行~第 12 行),然后从图