软件测试（二）图覆盖

发表于 | 分类于

Learning is cheap, writing the code, thinking in depth.

  • 程序的执行可能是非决定性的：定时器硬件中断（异步中断应该都算），非类型安全语言的未定义行为。

1. Overview

基于图覆盖准则生成测试用例，首先要从软件构件中获取图。例如对于源代码：映射执行和分支语句到控制流图。具体生成图的方法，在3，4，5，6节中给出。

基于图的覆盖准则：测试案例对图中路径需要达到何种程度的覆盖。

1.1. 图

  • 一个图G的定义
    • 节点集合N
    • 初始节点集合N0
    • 终止节点集合Nf
    • 边集合E = {(ni, nj)}，是N x N的子集
  • 每一个测试必须从某个起始节点开始，到某个终止节点结束 => 区分测试路径和路径
  • 路径由一个节点序列[n1, n2, ..., nm]给出
    • 每一个相邻节点对(ni, ni+1)都在边集中
    • 路径长度由包含的边数量给出
    • 路径p的子路径是p的一个子序列，也可能是p本身（长度为0）
  • 环是起始节点和终止节点为同一节点的路径
  • 简单路径是内部不存在环的路径，但是起始点和终止点可以相同

1.1.1. 图的相关概念

  • 可达: Reach(n)
    • 语法可达：若存在从ni到n(或边e)的路径，则称节点ni语法可达节点n(或边e)
    • 语义可达：对于某些测试输入若存在至少一条从ni到n的路径，则节点n也是语义可达的。
  • 访问(visit)
    • A test path p visits node/edge n if n is in p
  • 经过(tour)
    • A test path p tours subpath q if q is a subpath of p

通常只考虑所有节点和边均为语法可达的图。

1.1.2. 测试路径和SESE图

  • Test path: 路径p，以N0中某个节点起始，以Nf中某个节点结束，长度可能为0。
    • 某些图以单个节点起始，以单个节点结束。称为SESE(single entry/single exit)图。根据该定义，我们要求nf从任意N中节点语法可达，同时不存在从nf语法可达的点。
  • 定义测试到路径的映射: $path_G$
    • $path_G(t)$是测试t在图G中对应的(测试)y路径。
    • $path_G(T) = {path_G(t),t \in T }$。
    • 我们只考虑测试和测试路径多对一关系的情况，不考虑多对多(非决定性)的情况。

下图给出了一个终止节点nf = 3的SESE(单入单出，single entry single exit)图

soft-test-7.5.png

2. 图覆盖准则

图覆盖准则被分成两类

  1. 控制流覆盖准则，或称结构化的图覆盖准则（structural graph coverage criteria）
  2. 数据流覆盖准则

根据上一篇对覆盖准则的定义，图覆盖可以定义如下：Given a set TR of test requirements for a graph criterion C, a test set T satisfies C on graph G if and only if for every test requirement tr in TR, there is at least one test path p in path(T) such that p meets tr.

2.1. 结构化覆盖准则

  • 节点覆盖(Node Coverage): 测试需求包含了图G中可达的每一个点。
    • 例子：TR = {1, 2, 3, 4}。路径p1 = [1, 3], 路径p2 = [2, 4]。若测试集合T包含{t1, t2}，且path(t1) = p1，path(t2) = p2，那么测试集合T满足G上的节点覆盖。
  • 边覆盖(Edge Coverage): 测试需求包含了图G中可达的长度至多为1的路径。
    • 至多为1表明边覆盖需要包含点覆盖。
  • 边对覆盖(Edge-Pair Coverage(EPC)): 测试需求包含了图G中每一个可达的长度至多为2的路径。

soft-test-7.6.png

一种有用的测试准则如下：从软件某个状态出发，通过边转移，最终回到起始状态(round trip)。这种测试用于验证系统在特定输入下没有变化。

  • 最大长度简单路径覆盖（Prime Path Coverage）: 测试需求包含G中所有prime路径
    • Prime Path (主路径): 从ni到nj为prime路径当且仅当其为简单路径，且非任意简单路径的子路径
      • 内部无环(自身可能是环)
      • 尽可能长
      • 寻找的时候，每个节点均查看一遍，特别是环中节点
      • 寻找的时候，如果一个点有入度则以它为起点的主路径
        • 构成环
        • 属于其父节点的其它分支
      • 当存在自环(self-loop)的时候，主路径无法包含边对覆盖
    • prime path coverage包含了和round trip相关的两种特例，round trip path指的是：长度非0且起始和结束点相同的prime path
      • Simple Round Trip Coverage: 测试需求对G中所有round-trips中的每一个节点包含至少一条round-trip路径。
      • Complete Round Trip Coverage: 测试需求包含G中所有可达节点包含所有round-trips路径。
      • 这两个准则省略了不在round trips中的点和边，因而不包括边对、边或者点覆盖。
  • Complete Path Coverage: 测试需求包含了G中所有路径
    • 若存在环，则有无限测试需求
  • Specified Path Coverage: 测试需求包含了测试路径集合S。

soft-test-7.7.png

2.2. Touring, Sidetrips, and Detours

测试需求中给出的路径和实际的测试路径不同。区分这两者有助于处理不可行的测试需求。

严格的tour的定义要求按子路径的顺序对子路径进行访问。放松这种要求能够将循环包含在tour中。一般从两方面放松这种要求

  1. 允许经旁(sidetrips)：允许暂时偏离子路径顺序，但是需要回到同一个节点。
  2. 允许绕路(detours)：进一步地，允许离开子路径，但要求之后回到子路径中下一个节点，注意，这种偏移会跳过一条边。

给出下面的定义，其中q是简单子路径。

  • Tour: Test path p is said to tour subpath q if and only if q is a subpath of p.
  • Tour with sidetrips: Test path p is said to tour subpath q with sidetrips if and only if every edge in q is also in p in the same order.
    • 边出现的顺序不变
  • Tour with Detours: Test path p is said to tour subpath q with detours if and only if every node in q is also in p in the same order.
    • 节点出现的顺序不变

根据这三种定义可以给出不同级别的覆盖准则。例如，从tour/sidetrips/detours的角度定义Prime Path Coverage。通常将sidetrips用于处理不可行测试需求。

2.2.1. 处理不可行测试需求

某些情况下，如果不允许sidetrips会导致不可行的测试需求，例如对循环结构，如果循环体至少执行一次，则不可避免导致不可行的测试需求。因此，通常在测试需求不可行时放松约束，这也称为尽力而为的touring。

2.2.2. 寻找主路径和测试路径

主路径和对应的测试路径的寻找算法思想是首先找到所有简单路径，之后从中筛选出主路径。

  • 从长度为0的路径开始，对下面两种无法继续扩展的路径给出标记
    • 到达终止节点，无出边
    • 构成环
  • 按路径长度，从上一路径集合的每一个路径出发进行扩展，直到无法继续
  • 消除所有作为子路径存在的路径

从最长的主路径着手开始选择测试路径，直到满足所有主路径的情况。

2.3. 数据流覆盖准则

  • definition：变量值被分配存储空间的代码位置。
  • use：变量值被访问的代码位置。

设V为和程序构件相关的变量集合。定义V 的节点和边集合，称为def(n)或def(e)， 使用V 的节点和边集合，称为use(a)或use(b)。

2.3.1. 测试使用对(du-pair)和测试使用路径(du-path)

du路径一定要相对于某个变量而言，否则没有意义。

  • 从数据流分析的角度，变量定义不一定可达:
    • 变量v在li的定义无法到达lj处的使用，因为不存在li到lj的边。
    • 或者，v在路径上被重新def。
  • def-clear: 从li到lj的路径相对于变量v而言是def-clear的，如果路径中每一个点nk和每一条边ek，v都不在def(nk)和def(ek)中。允许出现use。
  • Reach(可达): 如果相对于变量v，从li到lj存在一条def-clear的路径，则v在li的定义($v\in def(l_i)$)可达其在lj的使用($v\in use(l_j$)。
  • du-pair： A pair of locations $(l_i, l_j)$ such that a variable v is defined at $l_i$ and used at $l_j$.
    • 注：特别要注意循环迭代的情况，例如i++，上一次定义到下一次使用
  • du-path： du-path with respect to a variable v is a simple path that is def-clear with respect to v from a node ni for which v is in def(ni) to a node nj for which v is in use(nj).
    • 简单路径
    • 对某个变量v而言def-clear
  • du-path(ni, v): 从节点ni起始的变量v的du-path集合。
  • du-path(ni, nj, v): 从节点ni到节点nj的变量v的du-path集合 。

soft-test-du.png

对du路径给出如下分类

  • def-path set: $du(n_i, v)$ 对于从ni起始的变量v的du路径集合 => 给出All-Defs准则的定义，每个def-path集合至少一个du-path被toured。
  • def-pair set: $du(n_i, n_j, v)$是变量v从节点ni开始，nj结束的du-paths的集合 => 给出All-Uses准则的定义，每个def-pair集合至少一个du-path被toured。

事实上，有 \(du(n_i, v) = U_{n_j}(n_i, n_j, v)\)

2.3.2. 数据流准则中tour的定义

  • du-tours: A test path p du-tours subpath d with respect to v if p tours d and the subpath taken is def-clear with respect to v.
    • 对于某个变量v而言
    • 子路径def-clear

2.3.3. 数据流准则

  • All-Defs Coverage(ADC): 对每一个def-path集合$S = du(n, v)$，测试需求包括至少一个du路径。
    • each def reaches at least one use
  • All-Uses Coverage(AUC): 对每一个def-pair集合$S = du(n_i, n_j, v)$，测试需求包含至少一个du路径。
    • each def reaches all possible uses
  • All-du-Paths Coverage(ADUPC)：对每一个def-pair集合$S = du(n_i, n_j, v)$，测试需求包含S中每一个路径d。
    • each def reaches all possible du-paths

soft-test-7.14.png

2.4. 图覆盖准则中的包含关系

subsumption-graph-coverage.png

3. 源代码的图覆盖

既然是映射那就看看各种概念的映射关系吧：

  • Graph: 控制流图
  • Node coverage: 执行每一条语句
  • Edge coverage: 执行每一条分支
  • Loops: 对应for循环，while循环
  • Data flow coverage:
    • defs: 变量赋值语句
    • uses: 使用变量语句

3.1. 控制流图

  • 节点: 语句的序列
    • basic block(基本块): a maximum sequence of program statements such that if any one statement of the block is executed, all statements in the block are executed
      • 仅有一个进入点，一个退出点
  • 边: 程序中一种可能的分支，控制转移
  • 循环： 需要加入额外的不用于表示语句或基本块的dummy节点。
    • while循环需要引入dummy节点，引出两个比较分支
    • for循环需要引入dummy节点，赋初始值

各种程序结构的画法就不给出来XD。

3.2. 数据流覆盖

  • def: 给出程序中变量的值在内存中的存储位置。
  • use: 给出程序中变量的值被访问的位置。

变量x的def在下列情况下出现：

  1. x appears on the left side of an assignment statement
  2. x is an actual parameter in a call site and its value is changed within the method
  3. x is a formal parameter of a method (an implicit def when the method begins execution)
  4. x is an input to the program
  • 如果变量x在某个基本块中被定义多次，只有最后一次有效

变量x的use在下列情况下出现：

  1. x appears on the right side of an assignment statement
  2. x appears in a conditional test (note that such a test is always associated with at least two edges)
  3. x is an actual parameter to a method
  4. x is an output of the program
  5. x is an output of a method in a return statement or returned through a parameter
1
2
y = z;
x = y + z;
  • local use: 如上代码，y总是会被z覆写，因此不存在另一个基本块的def能够到达它。y为local use。
  • global use: 如上的z被称为global，因为在其它基本块中定义。
  • 数据流分析仅考虑global use

3.2.1. 各种源代码结构到du对

  • 尤其是loop循环

4. 设计元素的图覆盖

  • 设计元素指的是软件中独立设计和实现的组件，例如面向对象编程中的类
  • OO软件和设计中的图主要给出的是软件间的依赖关系。

4.1. 设计元素的结构化图覆盖

首先还是要创建设计元素对应的图。设计元素的图主要基于软件组件的耦合性。两个组件间的互联方式给出了它们的依赖关系。为了描述这种耦合性，主要使用调用图表示。

4.1.1. call graph

  • 节点：单元（方法）
  • 边：对方法的调用
  • 节点覆盖（Node coverage，也称为method coverage）：调用每个单元至少一次
  • 边覆盖（Edge coverage）执行每一个调用至少一次

调用图最重要还是用于描述函数间的调用关系。

4.1.2. （不常用）：类继承继承图

对于类的继承关系，无法直接测试，需要通过对象

  • 类继承图中每一个类都实例化为一个或多个对象
  • OO调用覆盖：测试需求包含了调用图中各个类对应的一个对象节点
  • OO对象调用覆盖：测试需求包含了调用图中各个类对应的每一个对象节点

对于OO类的测试一般不使用图覆盖准则。

4.2. 设计元素的数据流图覆盖

当测试单个程序单元时，定义和使用在同一个单元内部。当集成测试时，定义和测试分别在不同的单元。

  • caller: a unit that invokes another unit
  • callee: the unit that is called
  • callsite(调用点): the statement that makes the call
  • actual parameter: variable in the caller
  • formal parameter: variable in the callee
  • call interface: 实参到形参的映射

设计元素中我们只关心接口，因此只关心跨接口的数据流变化，因此只用测试数据的最后一次定义和第一次使用。具体而言：

  • 只用关注调用前和返回前最后一次定义和调用后和返回后第一次使用
    • last def: The set of nodes that define a variable x and has a def-clear path from the node through a callsite to a use in the other unit
    • first use: The set of nodes that have uses of a variable y and for which there is a def-clear and use-clear path from the callsite to the nodes

last def和first use对通过使用下面的三元组记法：

  • last def和first use均使用(方法名，变量名，语句)表示
    • 语句一般用行号表示
    • 例如：(A, x, 2)
  • 例如(trash, m, 7) -> (takeOut, a, 19)

4.2.1. 数据流耦合的类型

跨接口的数据存在三种耦合形式：

  • 参数耦合：parameter coupling
  • 共享数据耦合：shared data coupling
  • 外部设备耦合：external device coupling

4.2.2. 数据流覆盖准则

给出如下覆盖准则：

  • Coupling du-path： du path from a last-def to a first-use.
  • All-Coupling-Def coverage: every last def to at least one first use.
  • All-Coupling-use Coverage: every last def to every first use.
  • All-Coupling-du-Paths Coverage: every simple path from every last def to every first use.

5. 规约的图覆盖

5.1. 测试顺序约束

  • sequencing constraints： 顺序约束指的是对方法调用顺序的约束
    • 例如：对于栈数据结构，规约可能要求执行出栈操作前至少应当执行一次入栈操作
    • 考虑一个文件类的打开、关闭、写操作，应当有下面的约束
      • 每一次write前必须有open执行
      • 每一次close前必须有open
      • write禁止在在close后执行，除非他们中间存在open
      • write应当在每一次close前执行
      • close禁止在close之后执行，除非他们之间有open
      • open禁止在open之后执行，除非他们之间有close
    • 存在两种测试的方式
      • 静态测试：针对每一个约束，一一测试
      • 动态测试：生成违反约束的测试需求
        • 包括从起始节点到每一个write节点的路径，且路径中没有open
        • 包括从起始节点到每一个close节点的路径，且路径中没有open
        • 包括从每一个close节点到每一个write节点的路径，且路径中没有open
        • 包括从每一个open节点到close节点的每一个路径，且路径中没有write
        • 包括从每一个open节点到每一个open节点的路径。

5.2. 测试软件的状态行为

使用FSM建模软件的运行行为。

  • transitions
    • guard：前置条件
    • trigger events：触发事件

基于FSM的定义，可以直接使用之前的一些测试覆盖准则：

  • 节点覆盖 -> 状态覆盖
  • 边覆盖 -> transition覆盖
  • 边对覆盖 -> transition-pair覆盖

6. 用例的图覆盖

用例图描述了软件针对用户输入而执行的一系列动作。

一个用例的文本描述通常由下面的组件构成：

  • 用例名
  • 总结
  • 执行者actor
  • 前置条件
  • 后置条件
  • 描述（description）
  • 备选方案（alternatives）

根据其中的描述部分，可以进一步通过活动图给出。活动图包括了两类节点：动作状态 和 顺序分支。

用例图到活动图的转换如下：

  • 用例的description部分给出了执行者采取的动作，对应着动作状态节点。
  • 用例的alternatives给出了顺序分支。

对于活动图，节点和边覆盖较为常见。

根据用户使用场景的相关领域知识，可以给出Specified Path Coverage，包含了用户对软件的所有可能的使用行为。